CS 129 Project 1 Writeup

Jonathan Mace (jcmace)
September 16 2012

Part 1

For part 1 of the project, I implemented the sum of squared differences and the normalized cross correlation metrics to align the images. The implementations iterate over possible displacements and calculates the difference between the two images using the respective metrics. The displacement that results in the least difference is then chosen for the alignment.
For small images using a small window, the algorithms were fairly fast - completing in less than one second per image. For large images however, it took a very long time to complete, since the window had to be much larger (proportional to the size of the image)

The quality of the alignments vary. Some of the images lacked diversity of colour and did not align too well - presumably because there was just too much difference in intensity for each of the colour channels. The images that had a diverse range of colours did align quite well. Presumably, this was because the diversity of colours ensured that there was some good correlation in some parts of the image - enough to ensure a good alignment.

Sum of Squared Differences

Normalized Cross Correlation

Part 2

For the second part, I implemented the image pyramid algorithm using both SSD and NCC. The main effect of the algorithm was to substantially speed up the computation of the alignment. Computation for large images using NCC still took around a minute, but for SSD took only a few seconds. In a couple of cases, it introduced misalignments. Still, the alignments were not very successful when the borders were still present on the images, but very successful with a bit of a border crop.

Sum of Squared Differences (Pyramid method + Cropping), Small Images:

Sum of Squared Differences (Pyramid method + Cropping), Large Images:

Extra Credit

In addition to the regular assignment tasks, I implemented the following three enhancements:

Intensity adjustment

I investigated the effect on alignment that intensity adjustment had. I added a preprocessing step which calculated the means and standard deviations of the pixels for the three colour channels, then adjusted the pixels so that anything below two standard deviations from the mean went to 0, anything above two standard deviations from the mean went to 1, and the mean was scaled to become 0.5.

Smart Edge Cropping

For some of the images, it is clear that the border was having a negative effect on the image. For example, in the following images, the one on the left shows an SSD alignment with the border, and the one on the right shows an SSD alignment with a 10% border chopped off.

I implemented smart border cropping of the images in two ways. The first, more naive way, does the following:

  • Iterate over the columns and rows of the image
  • Count the number of pixels in a column whose intensity is either greater than 0.8 or less than 0.2
  • If a column has more than 80% of its pixels then it is considered to be a border column
  • Blur using a [1,1,1,1,1] box filter, in case an erroneous border column is sandwitched between two good border columns
  • Trim the edges of the image so long as they are borders
  • This method worked a little bit. Very well for some images, but still strangely for others. It would, for the most part, pick up solid-coloured borders, but unfortunately it would miss smudgy borders. Therefore, images still did not necessarily align that well:

    The second smart border cropping method I used was to consider standard deviations. It would do the following:

  • Calculate the standard deviations for every column in the image
  • Calculate the average standard deviation, and the standard deviation of the standard deviations
  • Any column whose standard deviation was outside 2x of the mean would be considered part of the border
  • Crop the image appropriately
  • Iteratively apply this technique until the dimensions of the image stabilise
  • This technique must be applied iteratively, because cropping off some border may then make other parts of the image become border where they previously were not considered to be. For example, a white border surrounding a black border surrounding the image would typically require 2 passes; the first would correctly crop the outer white border but not the black border. The second pass would then crop the black border.

    Using this technique resulted in nicely cropped images. Sometimes it would be a bit too liberal with chopping off borders

    From left to right, the following images show an uncropped original, the same image cropped using the first technique, and the same image cropped using the second technique. I have added a 1px red outline to indicate the extent of the images.

    Edge detection

    I added an additional preprocessing step before calling imalign that performed Sobel edge detection on the image. This step was done before constructing the image pyramid. Alignment was then performed on the edge-detected images. As can be seen, this did not always work, but still also provided decent alignments sometimes.