Jaewon Lee

Project 1: Colorization

Images of the Russian Empire -- Colorizing the Prokudin-Gorskii Photo Collection.

In this project, we colorize the Prokudin-Gorskii photo collection. We accomplish this by taking the RGB glass plate negatives and aligning them such that we produce a coherent, full-color image. The negatives are split into B, G, and R channels arranged vertically, and we align the green (G) and red (R) channels to the blue (B) channel to reconstruct the original color photograph.

For the alignment, we apply different techniques based on the image resolution: a naive single-scale algorithm is used for smaller JPG images, while a pyramid multi-scale approach is employed for larger TIF images. Beyond these two approaches, I also implemented a single-scale algorithm that utilizes Fourier transforms and phase correlation that works on all images.

Naive Single-Scale: Small Images

• Max normalized cross-correlation (over min Euclidean distance)
• 3.2326s on average

For implementing the naive single-scale search, I used the max normalized cross-correlation to find the best offset between the green (G) and red (R) channels to align to the blue (B) channel. Given that this algorithm is computationally expensive and uses exhaustive search, the naive single-scale algorithm is used for smaller JPG images. I initially tried to find the most optimal (dx, dy) displacement by finding the minimum Euclidean distance between the two channels that are being compared. The Euclidean distance, aka the L2 norm, has the following form:

L2(image1, image2) = sqrt(sum(sum((image1-image2).^2)))

This, however, kept on giving me artifacts in the output images, so I decided to use the max normalized cross-correlation instead. The max normalized cross-correlation, aka the NCC, has the following form (the dot product of the normalized vector representation of the images):

NCC(image1, image2) = (image1/||image1||) · (image2/||image2||)

In summary, I found the most optimal (dx, dy) displacement by finding the maximum value of the NCC between the two channels that are being compared, after realizing that finding the minimum L2 distance was not as effective (for some reason).

Pyramid Multi-Scale: Large Images

• Max normalized cross-correlation, recursively/iteratively
• 21.5253s on average

When we try to align larger images, naive search simply isn't enough anymore because it's too computationally expensive. To address this, we use the pyramid multi-scale algorithm to align the green (G) and red (R) channels to the blue (B) channel for larger TIF images. In my implementation, I (1) created an image pyramid with the smallest image being at least 256x256 pixels, (2) iteratively aligned the green (G) and red (R) channels to the blue (B) channel, and (3) used the max normalized cross-correlation to find the best offset between the two channels. In terms of pseudocode, the pyramid multi-scale algorithm has the following form:

pyramid_t, template_i := the image pyramid for template and alignee, respectively
best_offset := (0, 0)
for i in range(len(pyramid_t)):
	best_offset = process_level(pyramid_t[i], pyramid_i[i], i)
return best_offset

The method process_level is essentially a modified version of my naive single-scale algorithm. The only difference is that I'm iterating through the image pyramid and iteratively aligning the green (G) and red (R) channels to the blue (B) channel, as we scale back up to the original image size. This worked perfectly for all of the .tif images except for emir.tif—we do resolve this by using the Fourier single-scale algorithm, which will be discussed in the next section. On the whole, we can see that the runtime has increased significantly, but this is still much faster than the naive single-scale algorithm if we were to apply it to these larger images.

(Bells & Whistles) Fourier Single-Scale: All Images

• Fourier transforms and phase correlation
• 0.0232s on average for jpg
  1.3789s on average for tif

Finally, for my bells & whistles, I implemented a single-scale algorithm that utilizes Fourier transforms and phase correlation to align the green (G) and red (R) channels to the blue (B) channel for all images. To do this, I first converted the images to the frequency domain using the Fourier transform, and then computed the cross-power spectrum to find the phase correlation. In pseudocode, the Fourier single-scale algorithm has the following form:

template_fft, image_fft := the Fourier transforms of the template and image
cross_power_spectrum := template_fft * conj(image_fft)
normalized_cps := the normalized cross-power spectrum
dx, dy := the offset that maximizes the normalized_cps

This method ended up being the most effective, as it was able to align all of the images without any artifacts and ran much faster than the other two methods as evidenced by the average times for both the jpg and the tif files.

Acknowledgements

This project is part of the Fall 2024 offering of CS180: Intro to Computer Vision and Computational Photography, at UC Berkeley. This website template is modified from HTML5 UP, and the images are from the Prokudin-Gorskii photo collection.