15-463: Computational Photography

Project 1: Colorizing the Prokudin-Gorskii collection by Joman Chu

Overview

My algorithm for colorizing the Prokudin-Gorskii plates consists of 3 stages:

1. Align the color channels

The algorithm first calculates the offset vectors necessary to translate the green and red layers of into alignment with the blue layer.

The general approach is to shift a layer by some amount of rows and columns, then compare that layer to the blue layer using normalized cross correlation (NCC). The green and red layers are handled independently of each other.

The algorithm uses the pyramid refinement method. The pyramid refinement method uses scaled-down images to progressively refine a guess for the proper shift at the full size. For the low-resolution plates, the initial image is scaled down to 1/2 size. For the high-resolution plates, the initial image is scaled down to 1/32 size. (My implementation does not automatically detect the size of the image, so the user will need to change a line in colorize_skel.m.)

This allows the algorithm to use a smaller search window because the guessed center is being continually refined, so an additional required shift to refine the center is never that far away.

At each level in the pyramid, the algorithm does a brute-force search for the maximum correlation over a window of [-5, 5] pixels in both directions. Additionally, the image edges had colored bands which were throwing off the correlation calculations, so the algorithm only compares on the middle 65% of the image.

After determining the best shift at the scaled-down size, the algorithm will first shift the next level of the pyramid, which is double of the previous size (eg, 1/32 to 1/16), by the best guess shift determined at the scaled-down size before doing the brute-force search. Eventually, the algorithm reaches full size and runs one last search and terminates.

The effectiveness of the pyramid method borne out in practice. Prior to implementing the pyramid method, I needed to use a window of [-15, 15] to get good results on the low-resolution photos. As a result the algorithm had to run NCC on 31^2 photos per layer to find the best shift. This took several minutes. By using a window of [-5, 5] and scaling down to a minimum of 1/2 size, the algorithm had to run NCC on 2*(11^2) photos per layer, which took the run time down to under 2 seconds.

2. Auto-cropping by edge detection

I noticed that many of the colored bands showed up as strong vertical or horizontal edges. Using MATLAB's built in edge detector (Sobel method, threshold of 0.05), the algorithm determined which pixels were part of an edge. This threshold is user configurable.

Then, if the number of edge pixels in any row or column was over a certain threshold (15% of the rows or columns in the photo), then the image would be cropped at that row or column. This threshold is user configurable.

The cropping was limited to only the outside of the image. This value is user configurable as a percentage of the rows and columns to determine an outside border to operate in.

This algorithm successfully cropped out most of the colored edges, but left some colored portions where one color was present but it faded into the rest of the image.

One major disadvantage with this algorithm is that it does not handle slightly slanted edges well. Imagine a vertical edge that spanned three pixels horizontally. Approximately 1/3 of the edge would exist in each column. Depending on the thresholds used, the algorithm would not handle this edge. An algorithm that calculated the edge length would work on this edge, but that would be getting pretty complicated.

3. Auto-cropping by color similarity

To crop out these sections, I needed to do color similarity and remove rows and columns where one color was overwhelmingly present and the other colors were not.

The algorithm finds the average value of the three channels of color of each pixel, and if any individual channel is outside a threshold of variance from the average (70%), then the pixel was considered improperly colored. This threshold is user configurable.

Then, if the number of improperly colored pixels in any row or column was over a certain threshold (80% of the rows or columns in the photo), then the image would be cropped out at that row or column. This threshold is user configurable.

The cropping was limited to only the outside of the image. This value is user configurable as a percentage of the rows and columns to determine an outside border to operate in.

This algorithm had significant issues with overcropping on the lower resolution images. Lowering the variance threshold, decreasing the border percentage, and increasing the cropping threshold could decrease the incidence of these issues. Additionally, it did not crop all of the discolored portions.

As somewhat of a preservationist, I was somewhat disappointed with the results of this cropping. I feel that cropping out the black edges which were not part of the original plates is a good addition, but cropping out sections of the image that had degraded with time removes information at the edges that the photographer attempted to convey.

However, at this point, I was tweaking constants and not programming, and I was having much less fun so I left it as is. I suppose an algorithm to try ranges of constants and a scoring function based on the number of pixels kept could help me refine the constants...

Results

High-resolution images

Click for 100% resolution

Colorized Cropped by edge Cropped by color Notes
00458u 00458u-c1 00458u-c2 Green: (43,6)
Red: (87,32)
Time: 240s
original
data
00911u 00911u-c1 00911u-c2 Green: (13,-6)
Red: (133,-12)
Time: 242s
original
data
01043u 01043u-c1 01043u-c2 Green: (-16,10)
Red: (11,17)
Time: 235s
original
data

This image is slightly misaligned. I believe the bold colors of the girls' dresses created large contrast between the plates, so the plates would not correlate.

01047u 01047u-c1 01047u-c2 Green: (24,20)
Red: (71,33)
Time: 236s
original
data
01194u 01194u-c1 01194u-c2 Green: (50,39)
Red: (106,60)
Time: 236s
original
data

I think this is my favorite image because its aligned really well and its a very intricate object.

01657u 01657u-c1 01657u-c2 Green: (55,9)
Red: (117,11)
Time: 240s
original
data
01861a 01861a-c1 01861a-c2 Green: (71,39)
Red: (148,63)
Time: 237s
original
data

Low-resolution images

Colorized Cropped by edge Cropped by color Notes
00125v 00125v-c1 00125v-c2 Green: (5,2)
Red: (10,1)
Time: 1.64s
original
data

This picture was significantly overcropped on the bottom, using the edge cropper. I believe the grass was detected as individual edges so a higher edge detector threshold would help mitigate this problem.

00153v 00153v-c1 00153v-c2 Green: (7,3)
Red: (14,5)
Time: 1.72s
original
data

This time, the left side is overcropped since the wood panel that should be there is missing. I believe the a higher average color variance would have helped here.

01112v 01112v-c1 01112v-c2 Green: (0,0)
Red: (5,1)
Time: 1.62s
original
data

This picture was significantly overcropped on the right side. Notice the building has three columns of windows in the first image, and only two in subsequent images. The edge detector may have found the light pole. A higher edge pixels threshold would have helped here.

00398v 00398v-c1 00398v-c2 Green: (5,3)
Red: (11,4)
Time: 1.71s
original
data

The color cropper worked really well here.

00640v 00640v-c1 00640v-c2 Green: (2,0)
Red: (9,0)
Time: 1.64s
original
data

The color cropper saw the red splotches and ended up removing that entire set of rows.

00149v 00149v-c1 00149v-c2 Green: (4,2)
Red: (9,2)
Time: 1.76s
original
data

You can see severe overcropping on the bottom. The edge detector saw the shadow as an edge. I'm not really sure how to get around this. Even a higher threshold would probably detect this edge.

00351v 00351v-c1 00351v-c2 Green: (4,1)
Red: (13,1)
Time: 1.73s
original
data

The steeple on the building to the right was cropped out. The edge detector may have found each brick in that building as an edge and cropped accordingly. I believe the only reason why the edge detector did not crop more of the building is because of the border limits. If you look at my program output, it seemed to have cropped the maximum it was allowed.

00163v 00163v-c1 00163v-c2 Green: (-3,1)
Red: (-4,1)
Time: 1.61s
original
data
31421v 31421v-c1 31421v-c2 Green: (8,0)
Red: (13,0)
Time: 1.62s
original
data

Hey, that's not Russian...

00564v 00564v-c1 00564v-c2 Green: (5,0)
Red: (11,0)
Time: 1.58s
original
data

Images of my own choosing

Images were taken semi-randomly from the Library of Congress's digitized Prokudin-Gorskii Collection

Colorized Cropped by edge Cropped by color Notes
00959v 00959v-c1 00959v-c2 Green: (2,2)
Red: (8,3)
Time: 1.67s
original
data

Again, severe overcropping from the edge cropper, likely due to the grass.

00961v 00961v-c1 00961v-c2 Green: (-3,1)
Red: (1,0)
Time: 1.69s
original
data
00969v 00969v-c1 00969v-c2 Green: (2,-1)
Red: (7,-3)
Time: 1.74s
original
data

Bells and Whistles

In addition to the cropping algorithms described earlier, my web page also validates! I always do my part to promote open standards. Can I get extra credit for that? :)

Valid XHTML 1.0 Strict