russiantequila

I've always gotten a kick out of those giant mosaic posters - you know, the "picture made of pictures" stuff. Turns out, they're pretty straightforward to make.

Here's a quick stab at one (target and source both taken from public news sources):

source image

The basic algorithm is this:

assuming you have a target image, t and a set of thumbnails, s0..sN, all of a fixed square with a side s

1. take all thumbnails, compute their average color* and put that in a map, keyed by thumb filename
2. take t, and subdivide it into square tiles with a side s
3. for every tile, compute the average color, and iterate over the map up above, looking for the closest average color**
4. for simplicity's sake, rather than drawing a new image, i just generate a little html table with pointers to the images. makes things a bit simpler

* average color is figured out by using the python image library's getcolors() method. it returns a list of (count, color) tuples, telling you the full range of rgb values that occur, along with the number of times they occur. then, take an a weighted average of the individual r,g,b values, and that's your average color

** closest average color is almost as simple as it sounds. with two rgb values, just do (abs(r-r1) + abs(g-g1) + abs(b-b1))/3. the reason you want the absolute value of the difference is this - let's say we have colors 50,100,150 and 150,100,50. if you compute it without the absolute values, the fact that the 50 and the 150 are in different channels won't matter - they'll cancel each other out: (50-150)+(100-100)+(150-50) == -100 + 0 + 100 == 0. the absolute value lets you register that difference = abs(50-150)+abs(100-100)+abs(150-50) == 100 + 0 + 100 == 200.

here's the end result:

not bad, but not great either. the problem is that if a tile is half black and half white, the average color will end up being the equivalent of grey. so let's try a modification.

1. for all thumbnails: take each thumbnail, divide it into four quadrants, and compute the average color value of each of the quadrants. store the list of averages into a map, as before.
2. take t, and subdivide it into square tiles with a side s
3. for every tile, divide it into four quadrants, like the thumbnails, compute the average color, and iterate over the map up above, looking for the closest average color. this time, closest average color is computed as the average of the color distances of each quadrant (color distance is the result of the computation shown above)

aand... voila

that's better. now, you could ostensibly do the same thing with further subdivision (16 sections instead of 4), but that will probably get more and more limited results, unless you have a massive thumbnail library. these mosaics were built with a library of ~1000 thumbnails.

now, all this said, there's lots of room for improvement. the current search algorithm is simply unscalable, especially if you want to go past a 4-quadrant tile. my next stab at it will be some variation of a binary search (though the fact that it's 3 values instead of 1 combined with me not wanting to give any one color priority complicates things a bit).

source code here