**Colorizing the Prokudin-Gorskii Photo Collection** Introduction =============================================================================== Background ------------------------------------------------------------------------------- Sergei Mikhailovich Prokudin-Gorskii was a pioneer of color photography who documented the Russian Empire with the support of Tsar Nicholas II. He used a three-color technique to capture thousands of images of diverse subjects, from Leo Tolstoy to landscapes. He hoped to educate the Russian people with his photographs, but his project was interrupted by the revolution of 1917. He left Russia and his negatives were later acquired by the Library of Congress, which has digitized them and made them accessible online. Overview ------------------------------------------------------------------------------- Our task is to colorize the images taken by Gorskii automatically. The images takes by him are on a single plate with 3 images stacked vertically. The images from top to bottom are the blue, green and red channels respectively. Now since these 3 images are taken with 3 filters in succession, they are not perfectly aligned. So naively stacking them will create a dizzying result shown in the image below.

So we will devise more sophisticated methods to align the plates. First, we will normalized cross-correlation (NCC) directly on the grayscale images to align them. Next we will convert the images to edge images before applying NCC. We will compare both these methods and then try to make the results more appealing by removing the borders as much as possible, and do some minor contrast boosting. Methods =============================================================================== Brute-force NCC ------------------------------------------------------------------------------- Normalized cross-correlation is a classical method of matching a greyscale template image with a target image. It is pretty robust to changes in brightness levels (due to the normalization). We will arbitrarily use the blue plate as the target , and use the red and green plates as templates to align them to the blue plate successively. Assuming the template to be $g[i, j]$ snd the target to be $I[i,j]$, where $i, j$ are pixel indices the NCC can be written as: $h[i, j] = \cfrac{\sum_{k,l} (g[k,l] - \bar{g})(I[i+k, j+l] - \bar{I_t}[i, j])}{\sqrt{\sum_{k,l} (g[k,l] - \bar{g})^2 + \sum_{k,l}(I[i+k, j+l] - \bar{I_t}[i, j])^2}}$ where, $\bar{I}[i,j]$ is a version of $I[i,j]$ filtered with a box filter that has the same size as the template $g[i,j]$ and is normalized to sum to 1. Once the cross-correlation has been computed, the shift can be computed as $[s_x, s_y] = argmax_{(i,j)}h[i,j]$
To obtain a baseline, we first center-crop the images, keeping 80% of the total image area. This is done to remove the white borders and any border artifacts. This crop will only be used for the alignment step, but when the images are stacked, the whole image will be used. We search a window of $[-x, +x]$ to find the maximum cross-correlation. This method works well for some images, but is computationally expensive. The cost of searching for the ideal shift increases quadratically as we increase the window size. As an example, processing the image lady.tif takes over 1 hour for searching on a window of [-200, 200] producing the result shown below.

Though the result is good in this case, the time taken is prohibitively expensive. So, we will make this more efficient using a gaussian pyramid. This will enable us to search over more pixels effectively. Gaussian pyramid with NCC ------------------------------------------------------------------------------- A simple modification to the brute force algorithm is to downsample the images and calculate the shifts on the smaller images. Say we downsample the original image by a factor of 2, then the shifts obtained from this half-sized image can be multiplied by 2 to get a good estimate of the actual shift. Now if we repeat this step $N$ times, we will start with an image that is only $1/2^N$ of the original image resolution, get the shifts from it, and keep refining our estimates as we go up in resolution until we reach the original resolution resolution. The advantage of this is, we can try larger window sizes on the lower resolution images and keep reducing our window size as we move up the "pyramid". This significantly speeds up the template matching phase of the alignment process. It is to be noted that naively downsampling images leads to aliasing artifacts, so its better to smooth the image with a gaussian filter before downsampling. In our experiments, we used a gaussian pyramid of depth 5, with the search window starting from $[-30, 30]$ at the lowest resolution, going up to only $[-2, 2]$ at the highest original resolution. This algorithm ran under 90 seconds to give the results shown below! (Zoom in to see the details in the images)

However, there is one image where this method fails - the image of emir.

The failure is due to the stark brightness and exposure differences in the three plates (See Emir's plates). It is interesting to see how the intricate pattern on the dress looks different in each of the plates. So we need something extra to handle such complicated textures that might throw off NCC if ran directly on the greyscale images. Image gradient+NMS features (Bells & Whistles #1) ------------------------------------------------------------------------------- For the image of Emir, and other possible images with complex textures, gradient computation followed by non-maximal suppresion (NMS) along the gradients led to much better alignment. The gradient of the images gets rid of the unnecessary information in between the patterns, while NMS refines the gradients to give sharper edges.

Using these edge features instead of the grayscale images, gives much better alignment with the same NCC and gaussian pyramid based algorithm used in the last section.

The only disadvantage to this method is that it takes an additional 90 secs for gradient computation and non-maximal suppression. However, its still pretty fast and the quality of the results make it worth the time! Auto-cropping (Bells & Whistles #2) ------------------------------------------------------------------------------- The colorized images by default have bands of single colour borders that are a by-product of the alignment process. I devised two simple heuristics to get rid of the borders.

1. Get rid of row or columns where greater than 30% of the pixels are completely white (> 0.95)
2. Get rid of row or columns where greater than 30% of the pixels are completely black (< 0.1)

The logic behind this heuristic is that the only discernible anomaly in the border is that they are bands of a particular color. Atleast one of the channels in the border is completely absent. This simple heuristic works to some extent to get rid of the borders, but it fails where the color artifacts are more complex.

All results that will be shown in Results section will be after Auto-cropping Contrast boosting (Bells & Whistles #3) ------------------------------------------------------------------------------- If you notice the auto-cropped image in the last section, you will see that the image looks more vibrant than the non-cropped version. For example, the skirt looks like it has a more saturated shade of blue. This is due to the auto-contrast adjustment step applied after the cropping. The algorithm is simple : Calculate the average intensity value of each channel, and then slightly boost the pixel values that are higher than the average, and decrease the pixel values that are lower than the average. Effectively, it makes the shadows darker and the highlights brighter. The values are clipped so that they stay between 0 and 1 even after this step. Here is another side by side comparison.

Final Results and Metrics =============================================================================== Results on given images ------------------------------------------------------------------------------- Shown below are all the results obtained after alignment using edges, auto-cropping and contrast-boosting. The offset of the Red and Green plates with respect to the Blue plate is hsown in the captions. The offsets are in order [x_offset y_offset]. It took an average of 2min 56secs to align colorize each image. (Without edge detection, the average was 1min 24secs)

Results on extra images from the collection -------------------------------------------------------------------------------