Image Alignment with Pyramids

Overview

As detailed in the project specification, my code aligns three similar images recorded in different color channels, and combines them to form a single color image. All data used is drawn from the Prokudin-Gorskii collection in the Library of Congress.

Algorithm

The single-dimensional algorithm for my image alignment is fairly straightforward, as it is mostly a variation on the brute-force "test every offset and choose the best" approach. Steps are as follows:

  1. Crop the image to its middle two-thirds to avoid artifacts caused by differing borders.
  2. Derive a Prewitt filter, which will emphasize the image's horizontal edges, multiply it by its transpose (which emphasizes vertical edges), and convolve this product with the cropped image.
  3. Iterate over possible alignments between offsets of -15 through 15 pixels in both width and height, comparing
    sum(sum((image_2 - image_1).^2)) between each offset and recording the maximum. This value approximates the summed difference between the values of the pixels, and is thus at least a mediocre metric of the two images' similarities.
  4. Return the offset corresponding to the least sum of squared differences, and circshift() the second image before combining the two.

The multi-dimensional algorithm takes advantage of the fact that resizing a large image is much quicker than testing alignment across many possible offsets. This algorithm extends the above like so:

  1. If the smallest dimension of the image is below a minimum size (150 pixels seems to work well, from experimentation), evaluate the above procedure and return the result.
  2. Otherwise:
    1. Downsize the image by half (after applying a Gaussian filter to counter aliasing).
    2. Pass the resized images to the multi-dimensional alignment algorithm recursively to determine the best offset for the smaller images.
    3. Double the offset values from the above step (so they apply to the larger images).
    4. Calculate (as in the single dimensional image) the best alignment of the two original images, though now only over the range of the doubled smaller offset ±1.

Results

Following are example outputs from my program, for eight different sets of images within the Prokudin-Gorskii collection. Four are from images provided with the stencil (though all 16 align properly with my algorithm) and four are others found on the Library of Congress site and then aligned using my program. As you can see, they all align with the best possible offsets, though there are still some artifacts due inconsistencies in the positioning of the photo subjects. This is most noticeable with the head of the furthest left man in the last photo.

September 17th, 2012