Image Quadrangulation

I want to represent an image with a bunch of rectangles. Let’s say that each shape has constant color, as a start. First, fill a rectangle with the average color that it covers. That’s the initial approximation. Wherever the error in a rectangle (between the original image and the approximation) is too big, subdivide that rectangle into four equal parts. Repeat this process, until the error in a rectangle is lower than a given threshold.

For example, here’s the Mona Lisa and its subdivisions. Each of the examples I’ll show here have the same error threshold. I’m allowing substantial error so that we can see the regions more clearly. This method is basically quadtree refinement:

Quadtree subdivision with 1321 rectangles.

You can see that in uniform regions, it doesn’t do much refinement at all. In contrast, it has lots of tiny rectangles around sharp edges, like the hair.

But that’s been done a lot, so it’s not very exciting. How about adapting the sizes of the rectangles? For example, if the top third of the image is very dark, and the bottom two-thirds are very light, splitting it horizontally in the middle isn’t a great idea. And splitting it vertically in the middle is a worse idea. Instead of dividing a rectangle into four pieces, let’s just split it in two. That’s simple enough that we can find the splitting direction and location that minimizes the error with the new rectangles. Check it out:

Subdivided to minimize error, with 571 rectangles

For the same error level, the new version uses 43% as many rectangles! That’s a substantial improvement. It also avoids the sterile look of using lots of identically-sized rectangles. How’s it look with differerent error levels? Well:

29, 77, 195, and 463 rectangles. Not many!

Or how about we shift away from uniformly-colored rectangles? Here, the color inside a rectangle is interpolated from the values at its corners. The first result is a quadtree again. The second result splits the rectangles at their points of maximum error.

Smooth rendering, subdivided at the centers. Used 832 rectangles.
Smooth rendering, subdivided at worst-error points. Used 712 rectangles.

The streakiness isn’t very pretty, unfortunately. I prefer the average-color rectangles, as they look like deliberate stylizations. But it can work well in some cases.

All of these methods could be considered to be image compression techniques, but they’re not very practical. Still fun, though!

And it turns out that this has all been done before, of course, under the name Binary Space Patritioning, by Hayder Radha. It’s very hard to come up with a new idea, especially when it’s this simple.

Now for some more examples! Here are animations of the convergence for The Girl With The Pearl Earring, both with constant colors and interpolated colors. I like how the interpolated version fixates on the white in the collar and eyes, and those pop out early on in the refinement

Thanks, Vermeer!

2 replies on “Image Quadrangulation”


Thank you for sharing this!

How do you find the optimal “splitting direction and location that minimizes the error with the new rectangles”? Do you use some analytical approach or just iterative error descend?

I wish that I had come up with a clever way to do it, but I just brute-forced it. For both the x- and y-direction, I stepped along and checked the error where the first part is the average of those pixels, and the second part is the average of the second part. Then I picked the direction and location with the minimum error, and split it there.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.