IMALIGN __ Writeup

Sam Potasznik (spotaszn)
January 29, 2010

Algorithm Description

For this project, I used a fairly basic image aligning algorithm. At the lowest level, to check how well two images match up, I took the total difference between each pixel in both images. The lower the difference, the better the alignment.

For single scale implementation, the algorithm moves the comparing image 20 pixels in all directions and finds the best match.

For multi scale implementation, I used a recursive algorithm. At the highest level, with the original images, since we do not want to search over a 20x20 window, the algorithm asks for the best displacement to align shrunken images. This level will in turn either ask again to get a displacement on shrunken images, or the base case is reached. The base case is reached not by size of the shrunken image (only compare images 100x100 or smaller for example), but by a set number of recursions. This is desirable because a 100x100 representation of a gigantic .tif image may not contain enough useful data. Shrinking the image a set number of times keeps data relevant while improving speed.

How much an image is shrunk is dependent on the SHRINK_FACTOR. I used a factor of 2, meaning each image is halved at each recursion. Moreover, the shrink factor decides the size of the search window for non-base case images. If an image was shrunk by a factor of 4, each pixel on the smaller image represents 4 pixels on the current image. Thus, we need to search a 4x4 window to find new alignments. Anything outside of this window was effectively searched by the shrunk image.

At the base case, the search works exactly like single scale implementation. However, to prevent comparing very large matrices to each other many times,

One very important improvement I made for my implementation was cutting off the borders of each image. This helps the algorithm only look at important data, ignoring photographers notes and many blemishes.

Results Images

Big Train
I'M ON A BOAT
Sarah Plain and Tall (and her 2 sisters) Holy Relics, Batman!
Woman in Repose
Sage Wisdom