Warning: this document is still work in progress. Feel free to send comments but do not consider it final material.

Colour dithering <<<
>>> Bibliography
^^^ Index

7. Photographic mosaics

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:

Patterns taken from Lena

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.

7.1. Image classification

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:

1 feature extracted from Lena patterns

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:

Lena (detail) Mosaic created from Lena’s detail

Better results can be achieved by storing four colour values, one for each corner of the tile:

4 features extracted from Lena patterns

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:

Lena (detail) Mosaic created from Lena’s detail

7.2. Error diffusion

TODO

7.3. Colour ASCII art

ASCII art tiles

Colour dithering <<<
>>> Bibliography
^^^ Index