15-463(15-663):Computational Photography

Project #1 IMAGE OF THE RUSSIAN EMPIRE: Colorizing the Prokudin-Gorskii photo collection

Cheng-Yang Liu

Overview:

Two major problems to solve:
1. Alignment
2. Computational Time

Approach:

  1. Alignment:
To align R,G and B channels, we have to find the similarity of three images. I have apply both Sum of Squared Differences (SSD) and Normalized Cross-correlation (NCC) metrics.

Sum of Squared Differences (SSD): SSD is simply compare the L2 norm distance between every pixels, and sum up all the distance. Two images are regarded as identical, while the score is zero. Therefore, we are looking for the lowest value of the sum.
Normalized Cross-correlation (NCC): On the other hand, NCC is a dot product between two normalized vectors. The range of NCC score is between -1 to 1. By normalizing the image signal, two images are similar when the NCC score close to 1. Hence, we are looking for the highest score.

For the overall process, first I set the Blue channel as the reference image, which is stable. Second, by shifting Red and Green channel images pixel-wise in two directions, we could compare the similarity with reference image, and find the best shifting distances by the above matching methods.

  2.Computational Time:
When we compare the similarity by shifting images pixel-wise, the computational time grows dramatically, specially to TIF file. To deal with this problem, we implement image pyramid trick. An image pyramid is a way to reduce computational cost. First, it compares the images in a coarser scale (smaller image) to get a rough guess of the shift. Then, based on the previous guess, we can search for a relative small area in a finer scale. Each scale can be regarded as a layer of pyramid.
For this approach, I set three layers for the small images, and five layers for the large images. Also, for the smallest scale, the search area is set as [-5,5], while each finer layer reduce [-1 1] pixels searching area.

Bells and Whistles:

Results:

Example Images:

Name: 00106v.jpg; offset: Green[1 4], Red[-1 9];

Name: 00757v.jpg; offset: Green[3 2], Red[5 5];

Name: 00888v.jpg; offset: Green[1 6], Red[0 12];

Name: 00889v.jpg; offset: Green[2 2], Red[3 4];

Name: 00907v.jpg; offset: Green[0 2], Red[0 6];

Name: 00911v.jpg; offset: Green[-1 1], Red[-1 13];

Name: 01031v.jpg; offset: Green[1 1], Red[2 4];

Name: 01657v.jpg; offset: Green[1 5], Red[1 11];

Name: 01880v.jpg; offset: Green[2 6], Red[4 14];

Large Images:
Click the image to download the original size of images.
offset: Red[Green X, Green Y]; Red[Red X, Red Y]

Name: 00029u.jpg; offset: Green[16 39], Red[33 91];

Name: 00087u.jpg; offset: Green[38 48], Red[55 107];

Name: 00128u.jpg; offset: Green[25 35], Red[38 51];

Name: 00458u.jpg; offset: Green[5 42], Red[32 87];

Name: 00737u.jpg; offset: Green[6 14], Red[14 49];

Name: 00822u.jpg; offset: Green[25 57], Red[33 125];

Name: 00892u.jpg; offset: Green[2 16], Red[4 42];

Name: 01043u.jpg; offset: Green[10 -16], Red[17 11];

Name: 01047u.jpg; offset: Green[20 24], Red[33 71];

Example Prokudin-Gorskii Collection Result

Name: 00245u.jpg; offset: Green[-7 28], Red[-19 108];

Name: 00253u.jpg; offset: Green[17 17], Red[30 89];

Name: 00617u.jpg; offset: Green[18 51], Red[21 118];

Name: 01736u.jpg; offset: Green[-10 53], Red[-34 117];

Name: 01886u.jpg; offset: Green[24 49], Red[55 103];