Assignment #1 - Colorizing the Prokudin-Gorskii Photo Collection
Brief Overview
I began by naively stacking the cathedral image using the given starter code. This gave
some intuition on how the alignment should proceed:
From the above image, I inferred that shifts are primarily translational and
fitting like homography may not be necessary.
Simple Methods
I first started with simple methods like SSD and Normalized Cross Correlation. Here's one example
shown below:
def get_SSD_alignment(img_to_align, ref_image, x_shifts=[-20, 20], y_shifts=[-20, 20]):
best_shift = (0, 0)
min_ssd = np.inf
for u in range(x_shifts[0], x_shifts[1], 1):
for v in range(y_shifts[0], y_shifts[1], 1):
# shift the image
img_to_align_shifted = np.roll(img_to_align, u, axis=0)
img_to_align_shifted = np.roll(img_to_align_shifted, v, axis=1)
# compute the sum of squared differences
ssd = np.sum((ref_image - img_to_align_shifted) ** 2)
if ssd < min_ssd:
best_shift = (u, v)
min_ssd = ssd
return best_shift
Large Images and Pyramids
However, simply using SSD/NCC on the cathedral image seemed to work, but the runtime on larger
images like emir.tif or village.tif was too long. To fix the issue of handling larger images,
I implemented an image pyramid based approach where shifts are calculated at the highest
levels of the pyramid (small images) and the calculated shifts are used to update the lower
levels of the pyramid.
Finally, the last level of the pyramid (original image) gets the aggregate information from
all higher layers. This funciton is shown below:
def align_SSD_pyramid(img_to_align, ref_image, num_scales):
# define the range of motion which could have led to the misalignment
x_shifts = [-20, 20] # unit = pixels
y_shifts = [-20, 20]
# downsample the images as a gaussian pyramid
# image_pyramid is a list of images, where image_pyramid[0] is the smallest image
img_to_align_pyramid = get_gaussian_pyramid(img_to_align, num_scales=num_scales)
ref_img_pyramid = get_gaussian_pyramid(ref_image, num_scales=num_scales)
image_shift = (0,0)
# iterate over the pyramid and apply the SSD alignment iteratively
for i in range(len(img_to_align_pyramid)):
# apply shift from the previous iteration
img_to_align_pyramid[i] = np.roll(img_to_align_pyramid[i], image_shift[0], axis=0)
img_to_align_pyramid[i] = np.roll(img_to_align_pyramid[i], image_shift[1], axis=1)
# new_shift = get_SSD_alignment(img_to_align_pyramid[i], ref_img_pyramid[i],
# x_shifts=x_shifts, y_shifts=y_shifts)
new_shift = get_n_cross_correlation(img_to_align_pyramid[i], ref_img_pyramid[i],
x_shifts=x_shifts, y_shifts=y_shifts)
# combine the previous shift and the new_found_shift to get the overall shift for next iteration
image_shift = ((image_shift[0] + new_shift[0])*2, (image_shift[1] + new_shift[1])*2)
# reduce search range for the next iteration (which will have larger image)
x_shifts[0] += 4
x_shifts[1] -= 4
y_shifts[0] += 4
y_shifts[1] -= 4
# since we are returning the shift for the input image level (not going down the pyramid),
# we need to divide the shift by 2
return (image_shift[0]//2, image_shift[1]//2)
Border Effects
The above pyramid method helped reduce runtime substantially, but the alignment was still not good enough.
I realised that the border of each image has a lot of noise which would negatively affect the
alignment. Hence, I also cropped the images slightly to be able to estimate a good alignment
which can then be applied onto the uncropped images:
def align_SSD_with_pyramid(blue, green, red):
"""
Align using SSD but at different scales using a guassian pyramid
"""
# crop image to remove edge effects (we will only calcuate the shift using these cropped images)
crop_width = 100
green_cropped = green[crop_width:-crop_width, crop_width:-crop_width]
red_cropped = red[crop_width:-crop_width, crop_width:-crop_width]
blue_cropped = blue[crop_width:-crop_width, crop_width:-crop_width]
final_green_translation = align_SSD_pyramid(green_cropped, blue_cropped, num_scales=4)
final_red_translation = align_SSD_pyramid(red_cropped, blue_cropped, num_scales=4)
print("final green translation: ", final_green_translation)
print("final red translation: ", final_red_translation)
# use the final green and red shift to apply the shift onto the original images
green_aligned, red_aligned = apply_shift(green, red,
final_green_translation, final_red_translation)
return blue, green_aligned, red_aligned
Results
Non-Pyramid Image Alignment
(Without Bells and Whistles and Non-Pyramid)
SSD Shifts and Timing:
green translation: (5, 2)
red translation: (12, 3)
Simple SSD alignment time: 0.5632369518280029
NCC Shifts and Timing
green translation: (5, 2)
red translation: (12, 3)
Simple NCC alignment time: 1.0155351161956787
Comparisions
| Naive Stacking | NCC Alignment | SSD Alignment |
|---|---|---|
|
 |
 |
Pyramid Based Image Alignment Results
(Without Bells and Whistles)
Emir
| Emir Naive Stacking | Emir NCC Alignment |
|---|---|
 |
 |
final green translation: (49, 24)
final red translation: (52, 34)
Pyramid alignment time: 0.7592649459838867
Harvesters
| Harvesters Naive Stacking | Harvesters NCC Alignment |
|---|---|
 |
 |
final green translation: (60, 16)
final red translation: (120, 13)
Pyramid SSD alignment time: 0.7597112655639648
Icon
| Icon Naive Stacking | Icon NCC Alignment |
|---|---|
 |
 |
final green translation: (40, 17)
final red translation: (89, 22)
Pyramid SSD alignment time: 0.7817261219024658
Lady
| Lady Naive Stacking | Lady NCC Alignment |
|---|---|
 |
 |
final green translation: (55, 0)
final red translation: (137, -17)
Pyramid alignment time (pytorch) : 0.7727265357971191
Self Potrait
| Self Potrait Naive Stacking | Self Potrait NCC Alignment |
|---|---|
 |
 |
final green translation: (80, -1)
final red translation: (170, -3)
Pyramid alignment time (pytorch) : 0.7856488227844238
Three Generations
| Three Generations Naive Stacking | Three Generations NCC Alignment |
|---|---|
 |
 |
final green translation: (54, 12)
final red translation: (111, 9)
Pyramid alignment time (pytorch) : 0.9627277851104736
Train
| Train Naive Stacking | Train NCC Alignment |
|---|---|
 |
 |
final green translation: (43, 2)
final red translation: (87, 29)
Pyramid alignment time (pytorch) : 0.978093147277832
Turkmen
| Turkmen Naive Stacking | Turkmen NCC Alignment |
|---|---|
 |
 |
final green translation: (56, 4)
final red translation: (114, 26)
Pyramid alignment time (pytorch) : 0.9880940914154053
Village
| Village Naive Stacking | Village NCC Alignment |
|---|---|
 |
 |
final green translation: (64, 0)
final red translation: (90, 0)
Pyramid alignment time (pytorch) : 1.0284287929534912
Trials on New Images from Prokudin-Gorskii Collection
Without changing any parameters from the original method, I attempted to align random
images from the online dataset
Random Example From Collection - 1
| Naive Stacking | NCC Alignment |
|---|---|
 |
 |
final green translation: (33, 55)
final red translation: (78, 108)
Pyramid alignment time (pytorch) : 0.7616608142852783
Random Example From Collection - 2
| Naive Stacking | NCC Alignment |
|---|---|
 |
 |
final green translation: (57, 12)
final red translation: (107, 24)
Pyramid alignment time (pytorch) : 0.7630753517150879
Random Example From Collection - 3
| Naive Stacking | NCC Alignment |
|---|---|
 |
 |
final green translation: (52, -3)
final red translation: (108, -7)
Pyramid alignment time (pytorch) : 0.7700011730194092
Failure Cases
The Emir image fails on all methods I tried.
I suspect the issue with this emir image to be that the individual channels vary too much
in brightness (The blue clothes of the Emir are too strong in blue channel and weak in the
other channels). This is illustrated in the comparison below:
| Blue Channel | Green Channel | Red Channel |
|---|---|---|
 |
 |
 |
Bells and Whistles (Extra Credit)
To improve upon the alignment through image pyramids, I tried two things:
- Implement image pyramid alignment thorugh PyTorch
- Used CLAHE (Contrast Limited Adaptive Histogram Equalization)
The PyTorch changes were simple (replacing all numpy functions with PyTorch). I used the
OpenCV implementation of CLAHE as a preprocessing step on all the individual channels.
Adaptive Histogram Equalization computes several histograms, each corresponding to a distinct section of the image, and uses them to redistribute the luminance values of the image.
Since images like Emir have highly varying luminance, I estimated this to be a good approach. However, it did not
seem to have much of an effect on the alignment. I estimate this is because the variance in luminance
is still too high (shown below).
| Blue Channel | Green Channel | Red Channel |
|---|---|---|
 |
 |
 |
Improved Alignment with CLAHE
| Village Without CLAHE | Village With CLAHE |
|---|---|
|
 |
| Green, Red Translations = (64, 0)(90, 0) | Green, Red Translations = (66, 12)(138, 23) |
| Self Potrait Without CLAHE | Self Potrait With CLAHE |
|---|---|
|
 |
| Green, Red Translations = (80, -1)(170, -3) | Green, Red Translations = (79, 28)(175, 36) |
| Turkmen Without CLAHE | Turkmen With CLAHE |
|---|---|
|
 |
| Green, Red Translations = (56, 4)(114, 26) | Green, Red Translations = (57, 21)(116, 29) |
| Lady Without CLAHE | Lady With CLAHE |
|---|---|
|
 |
| Green, Red Translations = (55,0)(137, -17) | Green, Red Translations = (57, 0)(120,12) |