Developing new algorithms for photomosaics

January 17th, 2013, Published in Articles: EngineerIT

by Dr. MC du Plessis, Nelson Mandela Metropolitan University

An image mosaic, or photomosaic as the name suggests, is a mosaic created using images. When viewing the photomosaic from a distance, images combine to create the visual effect of one larger image. This image is called the target image while the images making up the target image are called tiles. “If an image is worth a thousand words, an image mosaic is worth a million” – unknown.

The first photomosaic created with the use of a computer was by Joseph Francis in 1993 as an advertisement for Bell Labs. In the following years various algorithms were developed to create photomosaics without any human intervention. The leading algorithms work by dividing the target image into a grid. For each grid section the average colour value is computed and compared to the average colour value of a tile. The tile whose colour value is the closest to a grid section is then placed on that section. While this approach is able to create photomosaics on a consistent basis they all look similar. Running the algorithm multiple times would create identical photomosaics.

Fig. 1: A video animating the process of compiling
a photomosaic image of Oscar Pistorius, using
Weitz’s algorithm, was put on Youtube,
and viewed in 100 countries
(view at
www.nmmu.ac.za/cs)

Chris Allen (University of Wisconsin, Madison, USA 2003) created a hill climb algorithm to produce photomosaics. In his algorithm the optimal values of a tile’s location and rotation are found by iteratively adjusting the values until no improvements in the photomosaic are observed. The algorithm, however, has some limitations. Initially the target image is manually decomposed into different regions based on colour. Tiles that are placed in those regions are initially selected purely through colour mapping, after which the hill climb algorithm is used to improve the arrangement of the selected tiles.

Jonty Weitz, an honours student in the Department of Computing Sciences at the Nelson Mandela Metropolitan University, has devised a novel way of creating photomosaics using an alternative hill climb-based approach, in an attempt to address some of the shortcomings in algorithms such as the one developed by Chris Allen. The algorithm selects a random tile from a database. The tile location, size, rotation and transparency is then randomly assigned and placed on the photomosaic. If the tile improves the photomosaic the tile is kept, otherwise it is discarded. This process is repeated until a photomosaic of sufficient quality is produced. To determine whether a tile improves the photomosaic, the difference between the photomosaic and the target images pixels are taken. A decrease in the difference obviously indicates an improvement of the photomosaic.

Fig. 2: Results of experiment
to determine the impact
of applying various tile
attributes
.

Fig. 3: Using fixed sized
tiles that are
not rotated or
transparent.

Fig. 4: Allowing arbitrary
tile rotations,
sizes and
transparencies.

Fig. 5: The visibility of individual tiles in this photomosaic is closer to the spirit of what is understood as a photomosaic.

Weitz’s algorithm creates photomosaics that have the visual effects of a collage, while still being able to faithfully recreate the target image. Using this approach, interesting photomosaics can be created by limiting either of the following attributes of a tile: rotation, tile size and transparency.

An experiment was conducted to determine the impact of applying the above- mentioned attributes. Fig. 2 is the target image used for the experiment. By using fixed sized tiles that are not rotated or transparent, the algorithm produced Fig. 3. Although the algorithm was able to create a photomosaic resembling the target image, it has sharp lines when viewed up close. The resulting visual effect therefore distracts from the overall image. When allowing arbitrary tile rotations, sizes and transparencies, the algorithm produced Fig. 4, which clearly differs significantly from Fig. 3. The overall photomosaic is a closer representation of the target image and the smooth difference between tiles does not distract the eye like the photomosaic in Fig. 3. Allowing for different tile attributes, this allows the algorithm to create photomosaics that are visually appealing and unique.

However, a disadvantage of the photomosaic shown in Fig. 4 is that individual tiles are not clearly visible. The algorithm produced a near perfect replication of the target image, however individual tiles could not be identified. This begs the question, what constitutes a photomosaic? Should individual tile details be visible? One could argue that by the definition of a photomosaic individual tile details need not be visible. Weitz argues, however, that what makes photomosaic interesting is seeing the individual tiles as they add to the character of a photomosaic.

In an effort to improve the algorithm, a limit was placed on tile size and transparency. This would prevent tiles from becoming too small and from blending seamlessly into the background by being too transparent. The minimum transparency value that each tile could have was set to 50% while tile sizes were limited to a minimum of 50% of their original sizes. The resulting photomosaic is given in Fig. 5. The visibility of individual tiles in this photomosaic makes it match the target image less well (compared Fig. 4 to Fig. 5), but is closer to the spirit of what is understood as a photomosaic. Weitz feels that the algorithms that make use of restrictions on tile sizes and transparencies yield more aesthetically pleasing results.

Contact Dr. MC du Plessis, NMMU Tel 041 504-2076,
mc.duplessis@nmmu.ac.za

Related Articles

  • Telecoms Developments in Africa – September 2019
  • SABS to host 42nd ISO General Assembly and ISO Week
  • Digitalisation brings auto manufacturer up to speed
  • Make your data actionable from edge to cloud
  • Research initiative aims to boost SA mining