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

Don't get me wrong, there are plenty of people that do, but there's even more that couldn't give two (insert appropriately grotesque object) about it. I'll give you an example. About 3 weeks ago, I gave notice. I'm leaving a job I liked quite a bit that paid well and a position of some power at that. Certainly, everyone's first question from there on was "where you goin'? whatcha doin' next?", and I would always answer "I'm doing my own thing, trying out a startup".

9 times out of 10, their reaction would be a mix of benign jealousy and admiration, followed quickly by rapid questions about the startup and a series of "good luck"s and "you'll do great"s. It's not that they aren't entrepreneurial (to a certain extent), or that they don't have ideas of their own. It's more that they have kids and wives and dogs and mortgages and a 401k and ... and ... and ... stuff. And all of us in the startup community have at least some subset of all those, but we make a choice. We choose to not get enough sleep and work after hours, or we choose to cut into the nest egg (or the piggy bank) and quit and try it out and see. None of us know ahead of time, all of us hope that we're the next (insert inspirational startup founder). But all of us think that what we're doing is a natural progression; after all - everyone around us is doing it, right?

But who's everyone? Everyone is the community of driven risk-takers that post to hacker news, that read joel on software, that know about gigaom and all the other bloggers in our sector of the blogosphere (g-d i hate that word). And like in so many other communities, we assume that the vast majority of people not there are just like us too, because - come on, just continue the model outward, right? If 90% of the people here are in startups or trying to get in, shouldn't the rest of the world follow suit?

The startup community, and its flagship blogs and forums have rallied around them those few in the world that are willing to take that plunge with no bottom in sight. And it has gathered so many of us that we think that everyone we meet thinks the same way, wants the same things and is willing to take the same risks.

They are not. Take a moment, and reflect on the decision you are about to make. If you are reading this, chances are this decision will cost you dearly. And chances are, it's the right decision, and one that few will make.