Compresses images by recursively dividing them into quadrants based on color uniformity. Regions that are similar enough collapse into a single block filled with their average color; regions with too much variation keep subdividing. The result preserves detail in complex areas while smoothing out uniform ones.
The algorithm starts with the entire image as one region and asks: is this area uniform enough? Uniformity is measured as the maximum per-channel difference between any pixel and the region's mean color. If that error is within the threshold, the region becomes a leaf node and gets filled with the mean color. If not, it splits into four equal quadrants (NW, NE, SW, SE) and the process repeats recursively on each one.
This is a region quadtree — every node represents a rectangular area of 2D space, and internal nodes always have exactly four children. Leaf nodes are the compressed representation: instead of storing every pixel, the image is stored as a tree of colored rectangles at varying scales.
python compress.py [-h] [-o OUTPUT] [--max-depth MAX_DEPTH]
[--threshold THRESHOLD] [--min-size MIN_SIZE]
image
| Argument | Default | Description |
|---|---|---|
image |
(required) | Path to the input image |
-o, --output |
<input>_compressed.png |
Output path |
--threshold |
20 |
Max per-channel error before splitting stops. Lower = more detail, more leaf nodes. |
--max-depth |
8 |
Maximum recursion depth. Caps the smallest possible region at image_size / 2^depth pixels. |
--min-size |
2 |
Minimum region side length in pixels. Prevents splitting below this size regardless of error. |
# Default compression
python compress.py photo.jpg
# High quality (stricter threshold, more leaf nodes)
python compress.py photo.jpg --threshold 5
# Heavy compression (coarser blocks)
python compress.py photo.jpg --threshold 50 --max-depth 6
# Large minimum block size for a strong pixelated effect
python compress.py photo.jpg --min-size 16 -o blocky.png- The input image is cropped to a square and resized to the nearest power-of-2 side length before compression. The squared version is saved alongside the input as
<name>_square.png. - Supports any image format PIL can read (JPEG, PNG, BMP, etc.). Output is always PNG.
| Case | Time |
|---|---|
| Best | O(1) — root region is uniform, no splits |
| Average | O(n log n) — tree stays reasonably balanced |
| Worst | O(n) — heavily varied image, tree degenerates toward one leaf per pixel |
Space is O(n) for the leaf nodes in the balanced case.