Project1 - Images of the Russian Empire

Yan Gu

Overview

In this project, I finished a MATLAB program that will automatically align three different color channels (Red, Green, Blue) and combine then into a color photograph. The algorithm is implemented in two ways: naive implementation and multi-layer implementation, which will be described in the Framework part in detail.

Framework

Both implementations are basically doing the same process: first aligns the Blue channel (background) and Green channel (foreground) , and then aligns the Blue channel (background) and Red channel (foreground) .

For each query of two photos, I use a brute-force method to align then, that is, moving the foreground image one by one on pixel and computing the minimum ‘Sum of Square Differences’ (SSD) between two images.

I first define MaxShift, which means the maximum shift pixel in both directions we tried. Then for each iteration, I move the foreground by pixel and compute the SSD. Notice that in order to get better performance, image borders need to be cut out.

Naive Implementation

In naive implementation, I define MaxShift to be 15 and the results show that it is enough.

pseudocode:

Equally cut the photo into 3 parts B, G, R in vertical direction

Process (B, G)

Process (B, R)

Automatically combine 3 channels and cut the border.

Process (A, B):

Define MaxShift

for i = -MaxShift : MaxShift

    for j = -MaxShift : MaxShift

        Compute the SSD between A and B with offset (i,j)

        Update the best solution

The time complexity of this algorithm is O(height*width*MaxShift^2).

The execution time is approximately less than 1 second for small images.

Possible Optimization

I made a simple observation on small images. It seems that on each column and/or row, the SSD results is a single-peak function, and keep monotone on each side. ( I'm sorry that I don't know the word for this function in English, although I have tried to find it. )

Although it is nearly impossible to prove this property, it seems very reasonable. So it is possible to reduce the time complexity to O(height*width*MaxShift) or O(height*width*log(MaxShift)). I do not have enough time to implement this, but I think it might be a good idea if we have a huge amount of small images. (Pyramid wouldn't help a lot if the image is very small I think.)

Multi-Layer Implementation

In multi-layer implementation, the main framework is the same. when process two images, I use a image pyramid to accelerate the algorithm. When aligning two images, I first check whether it is small enough to run the naive algorithm. If not, I use a Gaussian filtering and then down-sampling. After that, recursively call the function to align two small images, and then use the offset on the lower layer ±2 pixels to check this layer.

Multi-Layer Process (A, B):

if A is small enough

    call Process(A, B)

else

    Gaussian Smooth A to A'

    Gaussian Smooth B to B'

    Half Down-sampling A'

    Half Down-sampling B'

    call Multi-layer Process(A', B') , offset results are: dx, dy

    for i=dx-2 : dx+2

        for j=dy-2 : dy+2

            Compute the SSD between A and B with offset (i,j)

            Update the best solution

The execution time is approximately 2-3 second for large images.

Display

The green and red channel images are shifted by the offsets calculated by the method above, and then but the border in order to get better vision effort.

 

Small Image Results – Naive Method

Click images to download full-size file

 

File: 00106v_res.jpg

Offset: Green [-4, -1], Red [-10, 1]

File: 00757v_res.jpg

Offset: Green [-2, -3], Red [-5, -5]

File: 00888v_res.jpg

Offset: Green [-6, -1], Red [-12, 0]

File: 00889v_res.jpg

Offset: Green [-2, -1], Red [-4, -3]

File: 00907v_res.jpg

Offset: Green [-2, 0], Red [-6, 1]

File: 00911v_res.jpg

Offset: Green [2, 3], Red [-10, 4]

File: 01031v_res.jpg

Offset: Green [-1, -1], Red [-4, -2]

File: 01657v_res.jpg

Offset: Green [-5, 0], Red [-11, -1]

File: 01880v_res.jpg

Offset: Green [-6, -2], Red [-14, -4]

 

Large Image Results – Multi-Layer Method

Click images to download full-size file

 

File: 00087u_res.tif

Offset: Green [-48, -40], Red [-108, -57]

File: 00128u_res.tif

Offset: Green [-35, -25], Red [-52, -37]

File: 00458u_res.tif

Offset: Green [-42, -6], Red [-98, -33]

File: 00737u_res.tif

Offset: Green [-15, -5], Red [-49, -14]

File: 00822u_res.tif

Offset: Green [-57, -25], Red [-124, -34]

File: 00892u_res.tif

Offset: Green [-16, -3], Red [-43, -5]

File: 01043u_res.tif

Offset: Green [15, -10], Red [-11, -19]

File: 01047u_res.tif

Offset: Green [-24, -19], Red [-71, -33]

File: 00029u_res.tif

Offset: Green [-38, -19], Red [-91, -31]