Hriday Sheth Project 1 — Images of the Russian Empire; Colorizing the Prokudin-Gorskii Photo Collection

Project Information

Overview

Sergei Mikhailovich Prokudin-Gorskii traveled across the Russian Empire, taking photos and recording exposures of each scene onto a glass plate using a red, a green, and a blue filter. The Library of Congress digitized the negatives. This project is about using different techniques so that for each scene, we "align" the red, green, and blue "images" to produce a color image.

Exhaustive Search

The initial, basic technique used to align images is just an exhaustive search where we try every possible combination of vertical and horizontal displacements in a window (in our case, [-15, 15] both vertical and horizontal). We set the "blue" image (aka the negative produced via the blue filter) as the "base" for each scene, and worked to align the green and red images to each blue image. We can use the Euclidean Distance between images to score the alignment from each displacement, and take the best-scoring displacements for both the green and red images for each scene. Then, we apply the green and red images on top of the blue image with such optimal displacements.

This technique is not very "intelligent" and relies on brute-forcing through all possible displacements in a certain window of pixels. If this window of pixels is too large, the algorithm can be very slow; however, if the window of pixels is too small relative to the amount of pixels in the overall images, then we may not get an strong result image because the optimal displacements for the green and red images may not be within the window itself. As a result, the technique is good for cases where the images don't have as many pixels (in this case, the JPEG images), and we're forced to rely on more efficient techniques for higher-resolution images like the TIF images.

Image Pyramid

Pyramid alignment works by aligning images from coarse to fine resolutions. Alignment starts at the most coarse resolution, where the image has fewer pixels, making it easier to find a rough alignment by searching a smaller, more manageable area via exhaustive search. At each step, the alignment from the previous (lower resolution) step is used to guide the next, more detailed alignment. This method speeds up the process, even for high-resolution images, by narrowing the search space at each level, making the alignment more efficient as it becomes more refined. Here, Euclidean Distance was also used to score alignment.

We used image pyramids to align the TIF images, which were much larger and had lot more pixels/resolutions than the JPEG images.

Debugging and Optimizations

One thing I did to optimze the algorithms for image alignment was to crop the image before scoring via Euclidean Distance. I took out 20% of both the height and width (10% next to each edge). This is because the borders are very "noisy" and contain scratches, misalignment marks, or stains, and I don't want to consider the "alignment" of these noisy pixels when getting the optimal displacement values for the green and red images.

Another thing I did to further optimize the alignment was tinker with the window of potential displacements used in each step of the image pyramid algorithm. I was originally trying a range of [-5, 5] for both vertical and horizontal displacements (for every step after the initial, most-coarse image alignment that used a [-15, 15] range). However, I noticed that a few TIF images were not well-aligned, so I inreased this range to [-7, 7]. This led to much better results, without a catastrophic runtime increase.