Warning: this document is still work in progress. Feel free to send comments but do not consider it final material.
Photographic mosaics are montages of smaller images creating the illusion of a bigger image.
Since we don’t have many images at our disposal, we will simply cut Lena into small chunks (called tiles) and use these parts to create mosaics. This is our tile database:
Generating a photomosaic consists in subdividing the original picture into x rectangular cells and find x tiles in the database (with or without duplicates, depending on the set of rules that is decided) so that when recombined the resulting image resembles the original picture. By the way, this technique is covered by Runaway Technology Inc.’s U.S. patent 6137498 [9].
Picking the right tile for the right cell in the grid is a very expensive and complicated operation. One of the biggest problems is the cost of a database lookup: comparing each tile area pixel-by-pixel is an O(N) operation where N is the size of the database. We can resort to image classification in order to speed up database lookups.
One of the simplest image classification techniques is the storage of each tile’s average colour into a separate database that is used for best match lookups. Of course, this computation should be gamma-corrected:
When creating the mosaic, we then only need to check the average colour instead of comparing each pixel one by one. Below is the result of the technique applied on a portion of the Lena picture:
Better results can be achieved by storing four colour values, one for each corner of the tile:
Having 12 values per tile (4 RGB triplets) is still a lot less than the original count of 3072 (for 32×32 tiles), and the results show clear improvement. For instance the feathers-hat frontier is now a lot smoother:
TODO
