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.
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.
In addition to the regular assignment tasks, I implemented the following three enhancements:
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.
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:
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:
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.
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.