ImageMosaics

Psychology 221
Winter 1999
Prof. Brian Wandell
David Merrill

Motivation

My motivation in doing a project involving Professor Wandell's algorithm for creating image mosaics was twofold: I wanted to:

1) Work with and understand the mosaic-creation algorithm
2) Develop an elegant interface for the creation of image mosaics

Process

In this section I will outline Professor Wandell's algorithm for the creation of image mosaics. This algorithm is distinct from Robert Silvers' algorithm for creating PhotoMosaics. I will explain the key difference in the following section.

What you need:

As you can probably guess, the creation of a photomosaic requires 2 things:

1) An "base" image. This is the picture that emerges if you take a step back and squint your eyes at your finished mosaic.
2) A collection of "tile" images. These are the little sub-images which will make up the larger image.

Step one: Process the tiles

The tiles to be used go through the following steps:
1) Convert images to black and white. This is accomplished by taking the mean of the R, G, and B values of each pixel, then setting all 3 of the R, G, and B values to equal the mean.

2) Shrink the tile images, if necessary, so that they are all a uniform size with equal width and height. This is done by blurring, then subsampling the image. Blurring is achieved by convolving the image with a gaussian.

The processed tile images are saved to a seperate directory


Before	After

Step two: Resize the base image

In order to have an easy time of creating a grid of tiles which is the same size as the base image, we crop the base image so that its dimensions are a multiple of the size of a (processed) tile. Since the size of the tiles is generally small and this cropping will take at most tileSize - 1 pixels from each dimension, which is usually not a problem. (where tileSize is the width or height of a processed tile)

Step three: Create the mosaic template

Creating an image mosaic is conceptually closer to building a new image based on characteristics of the base image, rather than altering the base image, or imbedding tiles onto it, etc..

Creating the mosaic template goes as follows: 1) Create a new, blank image the size of the (cropped) base image. 2) Iterate over this blank image, and grid it with tiles, chosen at random from the collection of tiles which have been specified.

The finished product looks something like this:

Note that since the tiles have been chosen at random, there is no pattern or semblance of the base image yet.

Step four: Blend the original image with the mosaic template

In this step, the algorithm iterates over the base image, and analyzes each tile-sized region of the image, gathering 2 characteristics of each region:

1) Mean R, G, and B values
2) Singular Value Decomposition

Using these values, each tile of the template is transformed into the new color indices as generated from the corresponding region of the original image.

Note: There is a key difference between Professor Wandell's image mosaic creation algorithm and Robert Silvers' algorithm (PhotoMosaics). The difference is as follows: Silvers' algorithm takes in a huge collection of tiles, and chooses a tile to represent a particular region in the base image using similarity heuristics to find the best match. Wandell's algorithm picks a tile at random from a (usually) smaller set of possible tiles, and transforms the tile to match the color and contrast information of the region it is meant to represent.

Here's what the base image looked like (after cropping):

Note: Wandell's algorithm contains another step, in which a spline operation is performed over the tiles in the image. I have omitted this step for the time being.

Implementation

Being familiar with the scripting language Tcl, and a newcomer to Matlab, I decided to take on the project of developing an implementation of this image mosaic creation process in Tcl.

One of Tcl's selling points is that it comes bundled with the graphical toolkit Tk, which allows for the development of graphical interfaces which can interact with the rest of the scripted code.

I am interested in interface design as well as vision, so I wanted to create something which would be easy for anyone to use in order to create an image mosaic.

Here is a screen shot of the main window of the interface.

Clicking "find" opens a file selection dialogue, so that the user can select which image they want to use for their mosaic. Clicking "view" opens a scrollable canvas upon which are displayed all of the tiles from the tile image directory. Here is what that window looks like:

Conclusions:

The "question" I had set out to answer was really more of a challenge as to whether I could make this algorithm work in Tcl, and to what extent could the interface be made simple. In the process of working on this project, I have learned about image-shrinking, colormaps, Singular Value Decomposition, converting images to black & white, how image data is stored, the difference between an 8 and a 24-bit image, and more..

Tcl turns out to have fairly limited image-processing tools built in. However, there are a variety of extensions to TCL which provided the functionality I needed to read/write various image types, and even to perform some non-trivial matrix calculations. (Unfortunately I found the matrix package late in the game, and I am still learning how to integrate it into my project) I have been able to implement the image mosaic creation process in Tcl up to the point of the mean/svd calculations. At that point I handed my Tcl results back to some modified Matlab code to finish the mosaic creation.

I have been able to create a simple and elegant (entirely my own opinion of course!) interface for this process, which has the potential to be useful to others wishing to create image mosaics.

Professor Wandell's image mosaic algorithm provided an interesting challenge for this project, which I have enjoyed.