Proj 1

Jingtao Zhang jingtaoz

14 Feb, 2024

1 Single-scale Implementation

First, we work on the small "cathedral.jpg" to implement the single-scale algorithm, where we simply use a shifting window (in this case, window size = 15, which means the translation range is (-15, 15)) on the green and red channels. For each shift, we calculate the Sum of Squared Distances(SSD) or Normalized Cross Correlation(NCC), which can be implemented as below:
def SSD(A, B):
  return np.sum((A - B) * (A - B))
def NCC(A, B):
  return np.sum((A / np.linalg.norm(A))*(B / np.linalg.norm(B)))
The result is shown below:

The green coordinate is the translation for the g channel, and the red coordinate is the translation for the r channel. For SSD and NCC, the results are the same.(It also applies for the following results) For Simplicity, I will just show the results of SSD in following discussions.

2 Multi-scale Implementation

The window size is too small, so the window can not move to the right place. However, if we set the window size to 200, it takes more than 0.5 hr to determine the translation for each image. So, it's necessary to divide this translation into layers, where we can adjust the window from coarse to fine.

In the multi-scale implementation, I first downsample the image. The number of layers are adaptive to image size, since I repeat downsampling twice until maximum(height, width) < threshold. In this way, we can get a list of images of different sizes like a pyramid. Then we start from the top of the pyramid to align each layer of source image to target images and get a translation value. Each time we go down the pyramid, we multiply the translation value by 2 to reconstruct the translation on the original image. In this way, we can get a large translation value with a small window size, so we can cover the whole image much more quickly.
Below shows the results on the given dataset.(threshold = 200, window_size = 10)

Generally, this performs much better and faster than the single-scale method. For each image, it takes around 30s, which is acceptable. However, if we raise our standard, only "icon", "lady", and "three_generations" are satifactory. The rest still have obvious disalignment. This might be because we use the original pixels as feature. But the pixel value might be in disagreement with each other for each channel. (For example, if there is a red dot in the image, the red channel might have high values while green and blue channels have low values). So we need better features to improve this.

3 Bells & Whistles

The feature I selected was edge, which focuses more on the pixel gradients rather than values. If we can first detect edges of images, hopefully we can get a better representation of images to help alignment.
In my implementation, I used skimage.filters.sobel to detect edges. Here are the results. (threshold = 200, window_size = 10)

We've made huge progress with this method, even though some cases are still not well-aligned. A possible explanation is that some images have blurred edges(eg. lady), and some images have complicated edges(eg. turkmen & harvesters).

4 Happy Hour

Regardless of the artifacts, let's pick some old pictures and have fun!(edge = True, threshold = 200, window_size = 10)