Colorizing the Prokudin-Gorskii Photo Collection

Introduction

This webpage mainly introduces the steps I took to solve the problem, and the results.

First attemp

With the start code, I first tried to simply combine original RGB channels, getting unaligned result. Apparently, it needs a certain shift.

Single-scale implementation

As discussed above, we need to find a certain shift(i, j) for every channel, where i refers to the vertical shift, and j refers to the horizontal shift. Suppose we have a 3-channel image, fix the blue channel, and try to find the best shift for the green and red channel. This could be done by brute-force search through shifting window of size 15. Namely, i and j are both in the range [-15, 15]. For each pair of (i, j), we calculate the sum of squared difference (SSD) between the channels, and take the pair with the smallest SSD as the best shift.

Metric

I tried both SSD and normalized cross-correlation(NCC) as the metric to find the best shift. In provided dataset, I didn't see clear difference between the two. Eventually I picked SSD since it's faster.

Here is the aligned result for calthedral image.

Coarse-to-fine pyramid speedup

Noticing that for single-scale implementation, our data is of very small size(390*1024), actually we have pretty large-scale images sizing approximately 4000*10000. In this case, a window of size 15 probably is not large enough to find the best shift. A naive solution is to increase the window size, while it is extremely time-consuming to calculate the metrics given such a large image.

Therefore, we need to find a more efficient way to solve the problem. We use image-pyramid to speed-up the search. The idea is to first find the best shift for the coarsest image, and then multiply the shift by 2 for the next level as its initial shift. It might also need a little adjustment to the shift, but this shift has a smaller range, which is more efficient to calculate.

A problem: image doesn't align well

A naive implementation didn't work well for me. After visualizing the stacked output from each level, I found that even for the coarsest image, the algorithm didn't find the best shift and the image stays unaligned.

I first attempted to solve this by increasing the window size, but the result remains almost the same(Actually it took me a lot of time to adjust parameters of window sizes in different levels, but the result just didn't become better). I inferred that the marginal pixels is a factor. Since the pixel values change dramatically(from white to black to the image itself), when we do np.roll, it generates a considerable loss that makes the result worse.

Solution: naive cut-off

Therefore, I tried to crop the image to remove the marginal pixels, and the result becomes better. Here I simply cut off 100 pixels from each side. Here are my results.

Improvement

With the naive cut-off, the result becomes better. However, the result is still not perfect. I further defined a range in the middle of the image, and only calculate the metric in this range. This approach is more efficient, and the result becomes better.