I’ve started looking at what I’ll need to do for my Warhammer Table program, but, in the meantime, I thought I would write about another bit of software that will always be a work in progress: my photomosaic program. At present, this program is not yet complete – it lacks any form of interface, which means that anytime I create a new mosaic, I need to recompile.
At any rate, the purpose of this post is to talk about what this program does, and what challenges I am trying to solve. Later, I’ll get into the particular algorithms I used and why.
First, I should mention that in some sense, it’s easy to write a naive photomosaic algorithm – one could simply pick a bunch of images and put them together in a random fashion. Then, as a finishing touch, bleed through the original image until it looks “good”. This is computationally easy, but not very satisfying – the only mechanism we have for increasing the quality of the mosaic is increasing the bleedthrough.
However, my goal is to do something a little better. First, I want to choose the images and their location in the goal image so that the two match as close as possible. Second, where possible, I want to use each image only once. This defines a matching problem (or assignment problem) and an associated weighted bipartite graph – each image of the image library could go in a particular spot on the goal image with a “cost” of the placement as the sum of the absolute value of the differences between the two.
This leads to the other end of the spectrum – solve the minimum cost assignment problem. Using the Hungarian algorithm, this turns out to be about O(n3), and at best is about O(n2.5). With n on the order of 10,000, this becomes both computationally expensive and expensive storagewise (the entire nxn weights matrix must be stored). To make creating a photomosaic reasonable on a PC, this needs to be approximated as inexpensively as possible.
That’s all to be described later.