Automatic Mosaics

Overview

A mosaic is a picture that is produced by arranging smaller pieces of stone, tile, glass or other colorful materials. For this project, we form a mosaic by applying affine transforms on smaller images to form a larger image. The desired visual effect is similar to that of the Italian painter Giuseppe Arcimboldo who is best known for portraits created by painting arrangements of fruits, vegetables, flowers or other common items. One of his more famous paintings is shown in Figure 1.

Figure 1 : The Spring by Giuseppe Arcimboldo

Automatic Generation

This project seeks to develop a software system that takes a target image T and an image database DB that contains single objects rendered on a transparent background. The system will identify major shapes in T (via segmentation) and find the image in DB that most closely matches each of these major shapes. Each matching database image will then be placed onto the output image to form a composite whole. This project requires that we solve several important problems related to shape matching and segmentation. These problems are briefly described below.

Segmentation

Image segmentation is the process of breaking an image into it's component parts. Especially for this project, the sementation must take into account not only the visual structure of the target image, but also the desired aesthetics of the output image. That is, the output image should not have a distribution of database tiles that includes several tiles of large size and numerous tiles of smaller size. The tile sizes should be distributed within a generally narrow range. Figure 2 shows a target image and a segmentation. Objects in the segmented image are denoted by using various colors. The target is overlayed with the segmented image in Figure 2C to aid in visualizing the segmentation.


Figure 2A : Target

Figure 2B: Segmented
Figure 2C : Overlayed

Shape Matching

Our shape matching algorithm should be rotation, scale and translation invariant. That is, the shape matching algorithm should identify similar shapes even if one is a scaled, rotated and translated version of the other. We expect to use something like the earth-movers-distance (EMD) [1] technique for shape matching. Figure 3 gives a visual example of what types of images a database might contain.

Figure 3 : An image database of objects

Global Optimization

Of course it is possible to perform different segmentations and to select database tiles in various ways in order to compose a mosaic image. Finding the segmentation and shape-matching strategy that produces the most aesthetic result will be difficult. Figure 4 shows a partial (and contrived) result.

Figure 4 : A partial output with several objects placed

References

  1. Haibin Ling, "An Efficient Earth Mover's Distance Algorithm for Robust Histogram Comparison".