The task for this project was to take scans of original glass plates from the Prokudin-Gorskii photo collection and combine them to create color images. The original glass plate for a single photo actually contains three images, one for each of the red, green, and blue color channels. To create a color image, the three channels must be separated, aligned with each other, and then combined again into a single color image.
Before trying to align the channels in an image, I used a Canny edge detector to find all the edges in the three channels. The rationale for this was that three color channels will have different brightness values which might throw off any template matching algorithm I might use, but their edge images should be nearly identical, so matching on the edge images should produce better results. Channels in the small images are only a few pixels off from each other, so to align two small images I exhaustively shift one of the images plus or minus 25 rows and columns, computing the sum of squared differences (SSD) between the two images for each shift. The shift that produces the minimum SSD is the best alignment. I also tried a different method called normalized cross correlation (NCC) to align the images. NCC did not seem to produce better results so I kept my SSD algorithm since it was a simpler algorithm and search a 50x50 pixel area did not take a significant amount of time.
The larger images were misaligned by over 100 pixels in some cases, so exhaustively computing SSD over a window of shifts on the full size image was not an option. Instead I made the matching function that was used on the small images recursive. If the function receive images that are larger than 20% of the original image size, it cuts the sizes of the input images in half and gets the shifts needed to align the smaller images. It then computes the shifts needed to align the original inputs over a small window (again plus or minus 25 rows and columns) using SSD, doubles the shifts returned by the recursive call, and adds them to the newly computed shifts.
The resulting images are almost all perfectly aligned. The exceptions are the large images of the train and the bible. These images have at least one channel still misaligned by a small amount. One possible explanation for this is that the misaligned channels are rotated differently than the other channels, although this is not likely since the three channels sit on top of each other in the original plate. A more likely explanation that the results from the edge detector I used were too coarse and the edge images from the channels were too different to improve alignment. Most likely is that a large enough window wasn't used (larger than 50x50 pixels was necessary) when exhaustively searching SSD.
Results from sample images:
Large sample image results (click for full size):
Results from other images:
David Klionsky, 1/27/2010