Vacant Nebula superfans may recall that I wrote a brief review of Anathem by Neal Stephenson on this blog about two years ago. I have recently recommended the book to at least two people, and started to worry that maybe it wasn’t as good as I remembered it being. I’ve had a similar situation with movies before, where I think a movie is really good the first time I watch it, then I watch it a second time and think it is pretty awful. (The most egregious example that comes to mind is Phone Booth.)

So I recently embarked upon the task of rereading Anathem. I believe this is actually the first time I have re-read a novel in over a decade. And I’m happy to stay that I stand by my original review. In fact, I liked it a little better the second time because I remembered a lot of the Orth and Fluccish vocabulary, so I didn’t have to consult the glossary all the time. And I believe the previous sentence tells you enough about the book to determine if it would be interesting to you.

Over the holidays, Stephanie’s family was working on a jigsaw puzzle which featured an image from Winnie The Pooh, which was made up of hundreds of tiny animation cells from Winnie The Pooh cartoons. The puzzle was super tedious, but it did inspire me. I realized it would be a fun programming exercise to try to write a program to generate one of these mosaic images. So that’s what I did that evening, staying up till about four in the morning.

In this post, I’ll be talking about some of the challenges I faced in writing the code. If this doesn’t sound at all interesting to you, but you’d like to see the images I created, you can just view my mosaics photo album that I just posted.

Here is the original image I’ll be working with in this example:

To start with, I take a library of images and reduce them all to 12×9 pixels. This takes a while, so this library is cached. I then use these simplified images to determine which image to use for each tile in the mosaic.

In my first try, I picked the best match possible for each tile. Unfortunately, this results in a lot of duplication, which doesn’t actually look that great.

So, my next attempt was to prevent any image from being used twice. Unfortunately, you need lots of suitable images for this to work; my library of photos wasn’t sufficient. Additionally, because I was processing tiles column-by-column, from left to right, the mosaic generally was truest to the original image on the left, and furthest from the image on the right.

My next idea was to allow an image to be reused, but to limit reuse. So I implemented a system where an image receives a “penalty” each time it is used. The next time I check to see how suitable that image is for a given tile, I add the penalty to that tile’s score. This has the effect of allowing other similar images to be substituted. But after other similar images also have the same penalty, the original image will be selected again. And it will get another penalty. This produces a better image, but it still has the problem of the image getting worse as you go from left to right.

So, I next decided I would fill in the tiles in a random order. This gives better results:

Next, I had the idea that instead of filling them in randomly, I should fill in the tiles with the most detail first. (For those curious, I calculate the level of detail in a tile by computing the average RGB color of each pixel in the tile. Then I take the standard deviation of the “distance” of each pixel’s color from the mean color in the RGB color space. So the most detailed image would be one that is half black and half white. And the least detailed would be one that is one solid color. This isn’t perfect: a tile that is a black and white checkerboard pattern is more detailed than one that is half white and half black, split evenly down the middle. I suppose a better approach would be to do a frequency analysis, and find the areas of highest frequency changes. Similar to the way JPEG compression works. But I thought that was too much work for what I was trying to do.)

So now we have something that I’m pretty pleased with. The next step was just to up the resolution. The image below has 4560 individual tiles:

I’m not releasing the program right now because the code is way too bad. It is very sloppy, nothing is parameterized. (I adjust the parameters right now by editing the code and running from within Eclipse.) Plus, I’m sure there are programs out there already that do the same thing better. If you’re really interested, you can email me. If there’s enough interest, I can try to make the code presentable. But I don’t have any plans for that now.