I've been playing with making image mosaics. My script takes a large number of images, scales them down to thumbnail size and then uses them as tiles to approximate a target image.
The approach is actually quite pleasing:
I compute the mean square error for every thumb in every tile position.
At first I just used a greedy placement: put the thumb with the least error on the tile it best fits, and then the next and so on.
The problem with greedy is that it leaves you eventually placing the most different thumbs on the least popular tiles, whether they match closely or not. I show examples here: http://williamedwardscoder.tumblr.com/post/84505278488/making-image-mosaics
So I then do random swaps until the script is interrupted. The results are quite OK.
A random swap of two tiles is not always an improvement, but sometimes a rotation of three or more tiles results in a global improvement i.e.
A <-> B may not improve, but
A -> B -> C -> A
For this reason, after picking two random tiles and discovering they do not improve, I pick a bunch of tiles to evaluate if they can be the third tile in such a rotation. I do not explore if any set of four tiles can be profitably rotated, and so on; that'd be super-expensive real soon.
But this takes time.. A lot of time!
Is there a better and faster approach?
I tested out various Python implementations and bindings of the Hungarian Method.
By far the fastest was the pure-Python https://github.com/xtof-durr/makeSimple/blob/master/Munkres/kuhnMunkres.py
My hunch is that this approximates the optimal answer; when run on a test image, all other libraries agreed on the result but this kuhnMunkres.py, whilst being orders of magnitude faster, only got very very very close to the score the other implementations agreed on.
Speed is very data-dependent; Mona Lisa rushed through kuhnMunkres.py in 13 minutes, but the Scarlet Chested Parakeet took 16 minutes.
Results were much the same as random swaps and rotations for the Parakeet:
(kuhnMunkres.py on the left, random swaps on the right; original image for comparision)
However, for the Mona Lisa image I tested with, the results were noticeably improved and she actually had her defined 'smile' shining through:
(kuhnMunkres.py on the left, random swaps on the right)