CS 7495 – Computer Vision

Description

This page showcases my favorite project from CS 7495 Computer Vision, titled “Large Tile Photo Mosaics”

I worked on this project with David Stolarsky. Below is a description of the project, its approach, and its results.


Large Tile Photo Mosaics


Problem Statement

The first computer-generated photo mosaic was created in 1993 for a Bell Labs promotion. Since then, few improvements have been made to the technique; photo mosaics all basically require their component images to be very small in order to effectively re-create a target image. The component images are really just glorified pixels; it is hard to see their content. The goal of this project is to create a photo mosaic made of very few component images, where the component images are large enough to convey their own meanings and the target image is clearly represented.
The images below illustrate an example of a target image and an associated large tile mosaic. The picture on the right is taken from the “The Creation of Adam”, painted by Michelangelo, and the mosaic on the left was painted by the artist Lewis Lavoie.


Related Work

The basic technique of generating a photo mosaic uses a database of images and a target image. The target image is split into R x C cells and each cell is replaced with a “similar” image from the database (1). A number of extensions have been explored, like video mosaics (3), speed improvements (2), and using as many database images as possible (4). However, none of these extensions tackle the problem of cell images being too small to be much more than glorified pixels.


Approach

For this project we built a system to create Large Tile Photo Mosaics. Our system takes as input a target image and an image database, and outputs a reconstruction of the target image made of images from the database arranged in a grid. To decide which database images to use in the resulting photo mosaic, our system compares the “structure” of each database image with the “structure” of each tile of the target image. The comparison takes into account a segmentation and the average color of each segment when determining how closely a database image “matches” a tile of the target image. We assume that database images that closely match a target tile image’s segmentation and color data will provide a well suited candidate for use in creating a large tile photo mosaic. In more detail:

[ Image Gathering ]
We built three Large Tile Photo Mosaics: one of a circle, one of a hand-painted photo mosaic of a face, and one of the original version of that face. To reconstruct the circle, we used the database shown in the results sections. For both the face and the photo mosaic face, our database consisted of the tiles from the hand-painted mosaic face. We chopped each target image up into uniformly sized tile images. We then resized each database image to match the size of the target image tiles.

[ Segmentation ]
For each database image and also for each target tile, we create a segmentation. We create the segmentation by first using the Berkeley Segmentation Engine to generate a superpixel segmentation. Then we merged adjacent superpixels based on colors within a thresholded Pythagorean distance of each other in RGB space. This gives us an optimized segmentation of our images.

[ Matching ]
Using the colored segmentations, we calculate a match score for each database image paired with each target tile image. The match score is equal to: (“matching area” / total area) * “color score”. To calculate the matching area, we intersect each segment from the tile with each segment from the database image, and assign each database image segment to the tile segment it overlaps with the most. Then for each tile segment, we take the database segment that overlaps it the most. The “matching area” is the sum of the latter intersections. To calculate the “color score” we subtract from one the Pythagorean distance between the average colors of paired segments divided by the maximum such distance.

[ Selection ]
To render the large tile photo mosaic we place the database image with the highest “match score” for a given tile in its corresponding tile position.


Results

To test our approach we used three test cases:

[ Case 1 ]
As a sanity check, we built a photo mosaic using a database of images that was exactly equivalent to the tiles of the target image. In this case, using the 1 image above as our target image, we successfully placed every database image into the correct tile position and recreated the target image.

[ Case 2 ]
Using the same image database as in case 1, we attempted to recreate a target image below with content similar to the target image in case 1, but with different pixel values. Some database images were placed in the correct positions, but not all. In this case, we searched for a more accurate result by varying the color distance threshold within which superpixels join to become segments.

[ Case 3 ]
As shown above, we built a photo mosaic of a circle using a set of horizontally and diagonally split black and white images.


Works Cited

[1] S. Battiato, G. Di Blasi, G. M. Farinella, and G. Gallo. Digital mosaic frameworks – an overview. Eurographics – Computer Graphic Forum, 26(4):794–812, 2007.
[2] Gianpiero Di Blasi and Maria Petralia. Fast photomosaic. In poster proceedings of ACM/WSCG2005, 2005.
[3] Allison W. Klein, Tyler Grant, Adam Finkelstein, and Michael F. Cohen. Video mosaics. In NPAR 2002: Second International Symposium on Non Photorealistic Rendering, pages 21–28, June 2002.
[4] Michihiro Mikamo, Marcos Slomp, Shungo Yanase, Bisser Raytchev, Toru Tamaki, and Kazu- fumi Kaneda. Maximizing image utilization in photomosaics. International Conference on Natural Computation, 0:275–278, 2010.


What I Learned

From working on this project I’ve learned that it is definitely possible to create large tile mosaics using our approach. In the case 2 our project did not actually preform very well, but we did not really expect it to since the coloration of the tiles where not necessarily going to match well with the target image. However, case 3 shows that our approach can work when colors are similar and enough database images are provided. I believe we could further improve our results by increasing the number of database images we used to generate mosaics along with improving our heuristics for matching in database images with target tiles.


Why I Liked This Project

I liked this project because I had a lot of fun working on it. From the beginning my group had a clear idea of how we would approach the problem of matching the structuring of different images. As we were working on the project it was great to see the individual parts coming together and working as we expected them to. Currently, we are considering continuing this project outside of the course and making a web app that would allow people to create large tile mosaics.


Mini-project Papers

The link below leads to a .zip file that contains the 3 mini-project papers writing for my computer vision course.

Type
computer vision, photo mosiac, segmentation, large tile photo mosaic