Kyle Halbach

Brian Hook

Mike Treffert

Automating Photomosaic Creation

Abstract

From millions to one - this was the idea that became Robert Silvers' claim to fame. During his time at MIT, Silvers gained worldwide acclaim for his ability to mold countless pictures into one, a method known as photomosaic. They are commonly used in puzzles distributed in your local department store. This paper discusses four different implementations for creating photomosaics along with some tricks we learned along the way to make the process of creating them more efficient.

Introduction

This relatively new style of art utilizes a technique which transforms an input image into a grid of thumbnail images while preserving its overall appearance. The typical photomosaic algorithm scans through a large database of images for pictures that closely match each block of pixels in the main image. Unfortunately as your image collection becomes large this can process of finding best matches for each tile can chew up a significant amount of time. We combatted this hurdle by using several smart procedures in congruence with each other to speed up the creation of photomosaics without degrading the quality of the resulting image. With this improved performance, it also gives us the ability to use a much larger database on images for tile consideration.

Problem Statement

To implement an application that automatically creates a photomosaic given an input image and a directory containing a sufficient number of images from which to choose tiles from that preserve the overall appearance of the original image.

Methodologies

For our project we decided to implement four different methods of generating a photomosaic. In this section we will briefly explain each of these methods.

Method One

We decided to start simple for our first implementation of creating a photomosaic. Essentially, we just use a single tiling image to tile another input image. We do so by down sampling our tiling image to a significantly smaller size. We then convert this RGB image into a gray scale image by taking the average values of all three channels. This step is needed in order to preserve the underlying tile image in the output image. Then we do something similar with the main input image that we are attempting to tile. Namely, we convert it to a grayscale image by averaging the RGB channels for each pixel. Finally, by combining these two results into a weighted average of their pixels, the output image acquiresa corresponding gray scale value. Using this process, we are able to create an output image which appears as a grayscale version of the original image from far away, while resembling a rectangular grid of the tiling image close up.

Figures 1 and 2: Photomosaics using Method 1

Method Two

We decided to expand on method 1 by integrating color back into the output image. In order to do so, rather than computing the gray scale version of the input image that we are tiling, we use the color values when combining it with the individual tiles. In order to get a true color value out this requires some other processing on the tiling image. In order to get a value between 0 and 255 for each of the RGB channels we divide each pixel in the gray scaled tile image by the max value. This will result in values between 0 and 1 for each pixel in the tiling image. Then by simply multiplying this newly acquired value by the color in the main image we are able to create an output image that preserves the color of the main input image while adding a notion of darkness to make the underlying tile images detectable.

Figures 3 and 4: Photomosaics using Method 2

Method Three

Our third method of generating a typical photomosaic is more of a traditional algorithm for creating photomosaics. For this approach, we went tile by tile in the input image. For each tile area, we searched through the database for the image that best resembles the area we are trying to tile. We then find all database images whose differenceis less than or equal to (1 + threshold) * (best resemblance). From this new collection of images, we then select a random image to place in the tiling area of the input image.

For this method, we were originally searching through the database image by image for the best match for each tile in the input image. However, on a database with approximately 800 images, the algorithm took multiple hours to complete. In order to speed this up, we pre-compute an array of feature vectors which contains a feature vector for each of the images in our database. To compute our feature vector we down sample each database image into a 10x10 grid. Hence, our feature vector is a 10x10 array of average colors of that database image. Since we pre-computed these feature vectors into a multi-dimensional array, we were able to load it at run time and use Matlab’s built in functions on arrays to speed up our run time. This method reduced our runtime from multiple hours using 800 images to just a few minutes using26,000+ images running on an Intel Core-i7 950 with 6GB DDR3 Ram and a solid state drive.

One aspect of generating photomosaics in this manner is ensuring that the same tile is not used repeatedly in the same general area. For example, if you had a very homogeneous area such as water, a blue tile image that matched the color of the water in the input image, that tile image would be used numerous times in that water area of the input image. This example would typically happen if we were using the best fit tile image for that section of the input image. However, if you don’t use the best image but use an image that is “good enough”and close to the best match instead, the repetitiveness of tiles can be decreased. This is the method that we implemented in our algorithm. To obtain all pictures that were a close match, we multiplied the best match by a threshold and selected all images within this range as a potential tiling image. Figure 5show an example of a run simply using the best tile image match. Figure 6 shows an example of using the threshold in order to generate more random tiles. One thing that we realized in moving between using the best match and using the threshold was that there was a trade-off between repetitiveness of the tile images and quality of the output image. As we used a bigger and bigger threshold, the quality of the output photomosaic decreases gradually. However, when we simply use the best match, the quality of the output is very good. This is to be expected because as the threshold increases, we allow for images that are not entirely the same color as the input images tiling area. This trade off is shown in the following two figures.

Figure 5: Best Match (no randomness) / Figure 6: Selection with randomness
Figures 7 and 8: Additional Photomosaics using Method 3

Figure 9: Zoomed in view of Figure 7

Method Four

Our final method is a combination of methods 2 and 3. Essentially, rather than using a single tiling image as described in the second method, we randomly select images from a directory of images to paste in each tile location. The database of images that we used for this is a database of 26,000+ images. For this method we tried various tile sizes to see which would give us the best input. When using large photos we realized that tiling with a large tile size and we select a dark tiling image, the photomosaic was essentially ruined. This is because when we paste the color on top of that dark tiling image, it is not as noticeable since the tiling image is so dark. However, as the tiling size decreased, this problem vanished because when the tile size got small enough, getting a dark tiling image every so often did not ruin the overall look of the photomosaic. For our final product, we used a final tile size of 30x30 pixel tiling blocks. We felt that at this size, the tiling images weren’t pixilated to the point of being undistinguishable and that this was the point where a dark tiling image didn’t ruin the overall mosaic.

Figures 10 and 11: Photomosaics using Method 4

Limitations

With our unique implementation of creating photomosaics we were able to cut down on the running time of our program significantly. With that being said there is still a limitation on how many photos can be scanned for a best match in a reasonable amount of time. For example, our procedure is still not effective enough to scan all images on the large web image databases, such as Flickr, to find best matches. Rather we are still required to manual select a subset of photos for consideration. Throughout the results seen in the paper we used approximately 26,000 photos.

Final Comments

As shown above, we were able to receive the best results while using the classical style for photomosaic creation. Our iterative process of gradually enhancing our results proved very useful though in that we picked up a quick and efficient ways of doing certain tasks along the way. We also found it very interesting how tweaking a few parameters, such as the tile size or number of images being considered for each tile placement, can radically alter the final result.

We feel as though the photomosaicing portion of our application definitely lives up to our initial expectations. Although we were a little leery of running into performance issues in the beginning stages, we were able to overcome these obstacles to create some pretty neat photomosaics.

For more results please visit our website at

References

[1] Smart Ideas for Photomosaic Rendering - Gianpiero Di Blasi, Giovanni Gallo, Maria Pia Petralia

[2]

1