Yan Gu
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.
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.
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).
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.)
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.
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]