(On the left, a target image. On the right, a mosaic made from thumbnails of all the Ludum Dare 32 games, positioned using an MSE score metric.)
Making mosaics is in two steps:
- score each tile in each position
- determine the optimal positioning of all tiles to maximize the total likeness
The second part is easy (although I tried imprecise approximations at first, and only discovered it fairly recently): use the Hungarian Algorithm.
Its that first step that’s tricky.
I have been using Mean Square Error (MSE) and have been fairly happy with the result. But readers have pondered if there aren’t better metrics that better account for shape and contrast and such…
So to please some Ludum Darers (and because I was curious), I tried out some algorithms.
First, Peak Signal to Noise Ratio (PSNR) is just a rephrasing of MSE and the results are much the same.
Second, I tried Structural Similarity (SSIM) index. This was a promising avenue to explore. My mosaic maker is Python and there’s a scikit helper, but scikit doesn’t work with pypy (and neither does a stock numpy; trying to get the mosaic maker to work happily in pypy with these kinds of dependencies has been a nightmare). In the end I went with pyssim which turned out to not work in pypy either due to dependencies but I stuck with it on cpython anyway. Its about 4x slower than MSE and most of the cost seems to be comparison overhead and not really affected by how big the patches I compared were.
SSIM is actually working in luma (eh fancy term for grayscale) and trying to account for shape not colour.
The results:
(On the left, the original. In the middle, MSE. And on the right, SSIM. Tiles are the thumbnails of 2819 Ludum Dare 32 games (omitting 2 games with broken thumbnails!))
So I tried blending the MSE and SSIM scores (suitably scaled of course) but couldn’t get even a little bit of SSIM to help:
(Here 70% MSE and 30% SSIM. I even tried 8% SSIM and it looked much the same.)
I also tested using the YCbCr colour-space too; results were much the same (as all the tiles are screenshots they are invariably natively RGB; if the tiles were made from photos there’s a good chance that YUV makes much more sense).
Now I am making a novice interpretation of this but my guess is that in mosaics, which are best viewed from a great distance where the tiles are increasingly pixel-sized, tile colour dominates over shapes within the tile?
