Quadtree

The picture above is made of nothing but squares. Every square is one solid color, and no two squares overlap. Some are huge, some are tiny, and where they land is decided by one greedy rule that never looks at what the photo shows.

Start with one square

The algorithm begins with the laziest possible picture: a single square that covers the whole image, painted with the image’s average color. That is the best one color can do, but it is obviously wrong almost everywhere.

To know how wrong, the algorithm compares the flat square with the original pixels. For every pixel it takes the difference in red, green and blue, squares each difference, and adds them all up. The result is the square’s total squared color error. A square sitting on a smooth patch of sky has a small error. A square covering an eye, a whisker or a sharp edge has a large one.

Split the worst square

Next, the square is split into four equal children, and each child gets its own average color. Already the picture looks a little less wrong.

Then the rule repeats, forever:

1. Look at every square on the canvas.
2. Find the one with the biggest total squared color error.
3. Split it into four and give each new square its own average.

That’s the whole algorithm. Each split removes one square and adds four, so the count grows by three every time: 1, 4, 7, 10 … In the reel, the counts shown on screen (10, 100, 1,024 and 4,096) are all real, reachable counts.

The structure this builds is called a quadtree: every square either stays a leaf or has exactly four children. The squares you see are the leaves.

Why the small squares go where the detail is

Because the rule always picks the worst square, the budget flows to wherever the picture is hardest to approximate. Small squares gather around sharp details. Smooth patches can keep big ones, because one average color already describes them well.

In the reel, the same cat photo was drawn with exactly 4,096 squares in two ways: the adaptive quadtree, and a plain 64 × 64 grid of equal squares. On that photo, the adaptive version had about 24% less squared color error. Same number of squares, better placed.

Two honest caveats from that experiment:

• Square count is not file size. About four thousand squares replaced over 262,000 pixels, but storing a quadtree also means storing the tree, so this says nothing direct about compression in bytes.
• Greedy is not optimal. Splitting the worst square right now is a good habit, not a proof that no better arrangement of the same number of squares exists. It is also not how JPEG works.

And there is no cat detector anywhere. The algorithm only ever asks one question: which square is the most wrong?

What the controls change

Squares is the leaf budget: how many squares the final picture may use, from 1 to 65,536. The algorithm keeps splitting the worst square until it reaches that number. Because every split adds three squares, the slider moves in steps of three.

• At 1, you get a single flat square in your photo’s average color.
• Around 10 to 100, the composition appears: big blocks for the background, the first small ones on the subject.
• Around 1,000 to 4,000, faces and objects become readable. The reel stopped at 4,096.
• Far beyond that, many squares are only a few pixels wide, and the picture creeps back toward the original photo. Flat areas still keep their large tiles, which is the quadtree’s signature look.

The slider moves on a log scale, so each part of it covers a similar ratio of squares. That matches how the picture changes: going from 10 to 100 squares matters as much as going from 1,000 to 10,000.

Outlines darkens the border of every square, so you can see the tree itself: where the splits piled up and where one big square was enough.

While it runs, the counter on the canvas shows how many squares exist at that moment, so you can watch the split order unfold just like in the reel.

Try this

• Pick a photo with one sharp subject on a plain background, like a pet against a wall or a person against the sky. Set the slider low (around 40) and look where the first small squares appear. They head straight for the edges.
• Compare with the original. Use the split view and drag across an edge: the squares are tiny right on the outline and huge a few pixels away.
• Save the process clip. It replays the run from one square to the full budget, the same build-up the reel showed, ready to post.

Your photo is processed on your own device. Nothing is uploaded.