CS 180 Project 1

I experimented with 4 metrics:

• L2 Distance: ||im1 - im2||_2, where ||x||_2 = sqrt(sum(x**2))
• Normalized L2 Distance: ||normalize(im1) - normalize(im2)||_2, where normalize(x) = (x-mu(x))/std(xu)
• L1 Distance: ||(im1 - im2)||_1, where ||x||_1 = sum(abs(x))
• Normalized Cross-Correlation (NCC): (im1/||im1|| * im2/||im2||), where * denotes an elementwise product

The broad approach was to exhaustively search about a [-15, 15] interval for different alignments of the green and red channel to the blue channel. For each offset, we calculate the metric and we pick the "best" one. In practice, I negated the NCC so that this meant picking the offset that minimizes the metric of choice.

I thought of using normalized L2 distance to compensate for brightness differences, and L1 distance because it might be more robust to outliers, but experimentally, this did not hold. The alignments were being thrown off due to the edges of the picture needlessly adding to the score, so I introduced a parameter k that specified what margins to disregard when computing the metric. I played around with k=5, 10, 20 and noticed that the outputs could be slightly sensitive to that factor. Note that both NCC and L2 Distance gave similar outputs, I picked L2 Distance for the following example with the cathedral. Note how k=20 performs best, but k=10 performs worse than when k=5. Future steps could incorporate automatic cropping or hyperparameter tuning to pick the best value of k. My function does also support float values of k between 0 and 1 (percentages of height or width), but I felt the hardcoded values were clearer to me. For the higher resolution images, this would have a marginal effect even with the multiscale approach described in the next section.

Other pictures also turned out quite fine with the same parameters, below I show tobolsk, monastery with the default parameter I found, k=5. I also found that L2 Distance was more sensitive to the choice of k, hence I opted to use NCC in the below cases, even though both provided the same outputs on these specific images:

With higher-resolution images, the same exhaustive search took too long. This called for the use of a pyramid scheme (not the scam). Effectively, the logic goes: downsample the image (while avoiding aliasing) till it is small enough to do a naive search, then go up to progressively higher resolutions, using a smaller [-2, 2] interval search to gradually mak finer-grained movements towards a reasonable offset. My pseudocode looked like:

def align_multiscale(im1, im2, depth):
if depth is 0:
find_best_offset(im1, im2, [-15, 15] search space)
else:
rescale im1 and im2 by 0.5, ensure anti-aliasing is on
x, y = align_multiscale(im1_rescaled, im2_rescaled, depth-1)
dx, dy = find_best_offset(im1, translated(im2, dx, dy), [-2, 2] search space)
return 2*x + dx, 2*y+dy

Generally I found a lot more success here. As opposed to aligning the .tif images on the order of minutes, within 15 seconds I got well-aligned images. Some examples below:

The emir proved to be more difficult, largely due to the stark differences in brightness between the red filter and the other two filters. I found this effect was particularly emphasised with L2 distance. Instead of aligning red and green to blue, I found success in aligning red and blue to green instead. I did also have to tune the margin-cropping parameter k more to achieve this outcome. While I dabbled with Canny edge detection, the tradeoff in terms of time didn't seem proportional for generally equivalent results to the green-aligned version.

With higher-resolution images, the same exhaustive search took too long. This called for the use of a pyramid scheme (not the scam). Effectively, the logic goes: downsample the image (while avoiding aliasing) till it is small enough to do a naive search, then go up to progressively higher resolutions, using a smaller [-2, 2] interval search to gradually mak finer-grained movements towards a reasonable offset. My pseudocode looked like:

def align_multiscale(im1, im2, depth):
if depth is 0:
find_best_offset(im1, im2, [-15, 15] search space)
else:
rescale im1 and im2 by 0.5, ensure anti-aliasing is on
x, y = align_multiscale(im1_rescaled, im2_rescaled, depth-1)
dx, dy = find_best_offset(im1, translated(im2, dx, dy), [-2, 2] search space)
return 2*x + dx, 2*y+dy

Generally I found a lot more success here. As opposed to aligning the .tif images on the order of minutes, within 15 seconds I got well-aligned images. Some examples below:

The emir proved to be more difficult, largely due to the stark differences in brightness between the red filter and the other two filters. I found this effect was particularly emphasised with L2 distance. Instead of aligning red and green to blue, I found success in aligning red and blue to green instead. I did also have to tune the margin-cropping parameter k more to achieve this outcome. While I dabbled with Canny edge detection, the tradeoff in terms of time didn't seem proportional for generally equivalent results to the green-aligned version.

Exhaustive searching takes time and is overly reliant on pixel values. In practice, experimenting and tuning the margins, the range to search over, which channel to align to all takes time. We don't want to take time. Enter phase correlation. I came across it in the textbook, and Wikipedia provided a formula. The premise is, let's move from the time domain to frequency domain using a 2D fourier transform, compute the cross-correlation there very efficiently, and then move back into the time domain using a 2D inverse FFT and find the offset which maximizes the cross-correlation. It's beautiful, and much faster than anything above, especially given that it's performing a global search (not just over the interval specified).

It worked wonders for both the jpgs and tifs, including the infamous emir. Note that the really large offsets are a consequence of the fact that it returns x, y that are positive. In a image that is 3900 pixels wide, a shift 3800 to the right is the same as -100. This also proved to be useful for visual debugging, especially when working with the cathedral and emir images. For example, I could glean that the Green to Blue shift was fine in the case of the emir since both my pyramid and phase correlation method got (24, 49), but the red to blue shifts were very different.

These pictures are old. Pretty cool, but old. I wanted to see separate pictures I had taken, and then use my algorithm to align them again. So I took my own LinkedIn picture and a sunset picture I had taken from the fire trails, tinkered with photoshop and aligned them using the multiscale and phase correlation approaches.