Image Alignment

Part I: Due Tues. Sept. 21
Part II: Due Tues. Sept. 28

In this project, you'll automatically create color images from the black and white photographs of Sergei Mikhailovich Prokudin-Gorskii (1863-1944). The download directory contains scanned negatives of the Prokudin-Gorskii images from the Library of Congress.

Programming [20 points]

You should write a single function that takes a grayscale Prokudin-Gorskii image as input, and returns a high quality RGB image as output. Your function should be completely automatic, i.e. it should require no help from the user! Note that the order of the color channels, from top to bottom, in the Prokudin-Gorskii images is BGR, not RGB.

For Part I [10 points], write a simple brute-force alignment algorithm that first splits the image into 3 parts. Use the G channel as the anchor channel, and find the best displacements for the R and B channels over a +/- D pixel window. Once you have the displacements, you can construct the RGB image by put them into corresponding color channels and display one the screen. How do you determine which is the best displacement? Use a simple image comparison metric such as the sum of squared difference (SSD) or the normalized cross correlation (NCC). NCC is the dot product between two normalized vectors. You may want to do normalization on small images blocks instead of the whole image. You also may want to exclude the border from the comparison.

You'll notice that if D is large or if the images are large, then this solution is prohibitively slow: The time complexity is O(n*D^2), where n is the number of pixels in the image.

For Part II [10 points], implement the image alignment on an image pyramid so that the complexity drops to O(n). You should be able to search over just a 3x3 (or maybe 5x5 to be safe) window at each pyramid level. Your goal is to have a single algorithm that can align and assemble any input image completely automatically and also efficiently.

Matlab Tips

  1. Keep the images as uint8 to save memory, but beware of using uint8 data in computations: Integer arithmetic in matlab is saturating! For most computations, you'll want to convert the image to single or double if you can afford the memory.

  2. Don't use loops for things like SSD and NCC. SSD is easily computed as sum((a(:)-b(:)).^2), and NCC as dot(a(:),b(:))/norm(a(:))/norm(b(:)).

  3. For the pyramid based algorithm: Write a recursive function to compute the displacements, and a separate function to assemble the result.

  4. Matlab functions that may be useful for this assignment:
    • help - as always!
    • cell - create an empty cell array (array of null pointers)
    • tic, toc - timer
    • circshift - one easy way to deal with displacement
    • cat - for creating the RGB image from the 3 parts
    • imfilter - image filtering (convolution) with helpful boundary options
    • conv2 - raw 2D convolution
    • imresize - resize an image
    • im2col - extracting image blocks and put them into columns
    • norm, dot - basic vector operations
    • sprintf - for creating filenames

Writeup [10 points]

Show the aligned RGB image for each input image in the download directory. If you cannot align an image, explain why. Also, for each image, report the time your code took for both the brute force and pyramid based algorithms.

Extra Credit

Does SSD or NCC make more sense? Can you find a better error function?

Handle the border correctly. Using circshift() is convenient, but introduces error.

The output contains color spots where there is missing data. Can you automatically detect these areas? If you can detect them, can you use that information to improve the alignment and/or clean up the final image?

What to Hand In

Submit your code and writeup electronically to the black board system. You do not need to hand in a printout.

The images and the idea for the project is from Alyosha Efros. This web page is modified from David Martin's 2009S course project.