Project 1: Color Alignment

Diana Huang (dkh) - February 5, 2010

Description

For this project, I implemented a simple algorithm to line up the three different images, each corresponding to a different color channel of the image. In order to do this, I attempted to find the best offset for the red and green channels that would align the image. I found the best offset by finding the minimum Euclidian distance between the blue channel and an offset green or red channel.

I implemented two different methods for searching for a good offset. One of these was simply an exhaustive search over the space of (-15, -15) to (15, 15) offsets to see which offset produced the best results. Overall, this produced good results, but the program is also very slow.

In order to get faster results, I used Gaussian triangles to cover a wider area. This strategy involves searching over the space of (-2, 2) to (-2, 2) offsets on a smaller image, and after selecting the best offset for that image, then, on a slightly larger image, searching over the space of (-2,2) to (-2, 2) offsets centered around the best offset previously found. Since the major slowdown in the exhaustive search is the calculations of the Euclidean distance for each offset, we get a major speedup by doing comparisons of smaller images as well as doing fewer comparisons than in the method with a larger search space. For my implementation, I resized the image a varying number, each resize half the size of the previous one using a recursive helper method to shrink the image by half each recursive call. I stop recurring when the size of the image drops below 100 pixels.

While doing the comparison, I do a few modifications to the image. I use edge detection to try to compensate for the fact that the channels will have different values corresponding to the same pixel, since the channels represent different colors. I am trying to only use the center of the image when doing the comparison, removing 20% off each of the sides.

To remove the white borders, I implemented a crop that tries to remove the white and black edges from the image before aligning the images. It moves in from the top left and bottom right to remove the white borders, and then tries to step in from the sides to remove the black borders. The idea behind this was because the corners would not work as well as the sides, since the corners would move diagonally, and they might run into issues due to that behavior. This produced fairly good but not excellent results, as the images were not perfectly aligned in a rectangle on the white background.

Extra Credit

I also implemented a simple white-balance algorithm for this project. To do this, I assumed the gray world hypothesis and averaged together all the values of the channel and then scaled those values against some assumed gray value that the channel is 'supposed' to average across all the pixels of that channel.

Results Images

Slow Results

As you can see here, the slow version for the most part produces very good results, except in the cases where the sum of squared differences has problems matching up the images perfectly.

Gaussian Pyramid Results

The Gaussian pyramid results were very similar to the slow version, except for a few cases where it did slightly worse. This is probably due to the fact that some details were lost in the resizing, which meant that the original offsets may not have been very good.

Other Downloaded Images

These images were downloaded from the website, and they had a variety of different results, though most were good. I couldn't test on any very large, uncompressed images, because when I tried to download one, the machine complained that it did not fit on the disk. The images that seemed to be the hardest to match up correctly are the ones without huge color differences and also a lot of really tiny details.