CS 129 Project 1 Writeup

Introduction

In this project, I designed an algorithm to align and colorize the photographs of Sergei Prokudin-Gorskii, using scans from the Library of Congress. To find the best alignment, the algorithm evaluated a [-25, 25] window of shifts in each direction. Sum of square differences (SSD) was used to evalute the alignments. In addition, a pre-alignment automatic crop was applied to the images to remove the white and black borders surrounding the images. The crop used basic edge detection to locate the borders.
A coarse-to-fine search with image pyramids was used to speed up the alignment of large images. The pyramid was constructed by first blurring the image using a Gaussian filter, then sampling every other pixel. The image was successively filtered and halved until both dimensions of the image were under 400px. This bottom level is then searched over the full [-25, 25] window; the best alignment found at this level is used at an estimate in the next larger level. In each level above the bottom, a much smaller search window of [-2, 2] was used.

Results

The automatic alignment worked surprisingly well.










Additionally, the pre-alignment crop significantly improved results. For example, the alignment for this image without using the crop is quite terrible: the image on the left was aligned without any pre-processing, and the image on the right was aligned using pre-processing.



While the crop removes the unnatural borders, there are still artifacts of the alignment process present in the image as smears of colors along the edges. Post-process cropping could remove these, but would require a different cropping algorithm.

The alignment failed to align two images:




These images are both similar in that each separate color plate of the image (especially in the first) appears to vary in exposure. Additional preprocessing to normalize brightness prior to alignment could perhaps fix this.

The alignment runs quite well: on a modern Macbook Pro, small images take 10s and large images take about 1min (this is mostly due to unoptimized cropping).