A Study of Algorithmic and Input Variation in Photo Mosaic Generation

Peter Bodechtel
Cape Town,
South Africa

Abstract. A study of the properties of algorithmic and input variations in the generation of photo mosaics. We start by defining a general framework for understanding how photo mosaics are generated. We then present a series of different algorithmic and input properties and explore their qualitative effects.


To generate a photo mosaic a source image is broken into a set of tiles. These tiles are then compared against a set of candidate images. For each source tile, the candidate image which is found to be most similar, is selected and replaces the source tile.

Overall Effect

The overall effect of a photo mosaic derives from the shift in perspective that occurs when a viewer moves close enough to the image to resolve its constituent parts, or far enough away that the parts merge into a coherent whole.

Candidate Image Selection

It was found a photo mosaic is made more impactful by considered selection of candidate images. For example, when generating a photo mosaic of Nelson Mandela, candidate images with South African themes were selected. The hope is that as a viewer inspects the work closely they are made aware of the connection between the overall subject and its constituent parts.

Tile Count

It was found that the number of tiles in a photo mosaic has a range qualitative effects. Too few tiles resulted in under-resolved mosaics where the source image could not be easily distinguished. Too many tiles resulted in over-resolved images where individual tiles could not be easily distinguished. There also seems to be an inverse correlation between tile count and saturation of the mosaic.

Candidate Image Count

It was found that the number of candidate images available while generating a photo mosaic has a positive result. On average, more candidate images resulted in a better overall match with the source image. This dramatically increased the quality of the mosaic when viewed at a distance. It should be noted that the rendering time of the mosaic increased linearly with candidate image count.

Unique Matching Candidate Images

Allowing candidate tiles to be selected more than once resulted in a higher overall resolution in photo mosaic. This is because the best match is always selected as there is no chance that the best match was matched on an inferior match for another tile. This very apparent on mosaics with many tiles. The down side is that when these mosaics are inspected closely, large swathes of the same image become apparent, detracting from the overall effect of the mosaic. This defect is most apparent in areas that had relatively little detail to begin with.

Rendering Order: Random vs Linear

It was found that the order in which tiles from the source image were processed had a qualitative effect. When processed linearly the mosaic would resolve with a higher quality in the direction of the render. Randomizing the order produced a more even quality to the mosaic.

Rendering Order: Random vs Entropic

While random order provided even levels of quality, an automatic method for prioritizing edges in processing order was attempted. This was achieved by sorting based on an entropy calculation. This resulted in higher quality around edges adding contrast to the photo mosaic. In some cases (especially against a black background) this created an unwanted halo around objects.

Sample Resolution

When comparing each tile to candidate images the resolution of the comparison was found to have a qualitative effect. At the lowest level the average color of the entire tile can be compared to the average color of each candidate image. A technique for comparing the tiles at different resolutions was developed which calculated the delta of all image data in a tile. This allowed sampling at different resolutions. This technique was found to result in a higher overall smoothness in the mosaic. Due to limitations in the size of the candidate image pool this technique was found to have diminishing returns. This technique also increased rendering time asymmetrically with the resolution.

Desaturated Sampling

When generating a mosaic that was intended to be desaturated the algorithm was optimised to only match the gray channel instead of the red, green and blue channels. This greatly reduced rendering time and allowed for better overall resolution in the mosaic.

Asymmetric Tile Sizing

Some mosaics may have a candidate image set which is predominantly rectangular and in one orientation. A technique was developed to create a mosaic with these properties in mind. The example is a rendering of the New York Public Library logo made out of book covers. The tiles are in a 3:4 ratio.

Resizing Algorithm

The resizing algorithm used when analyzing tiles in the source image was found to have a dramatic effect on the quality of the render. A Bicubic algorithm was compared to an Antialiased algorithm. While the antialiased algorithm increased rendering time slightly, it dramatically increased the resolution of the render.