Project 1: Image Alignment with Pyramids

Hua Guo

In this project, algorithms have been implemented to align gray scale images from the Prokudin-Gorskii collection to produce color images. The algorithm has been implemented to work with either color intensity or edge information as alignment feature. Image pyramid has been implemented to accelarate image processing speed. Automatic cropping of the borders, automatic contrasting and gray world assumption are implemented to enhance image quality.

SSD v.s. NCC

Both sum of squared difference and normalized cross-correlation have been implemented and tested as difference metrics. Normalized cross-correlation is implemented using matlab's normxcorr2 function. To remove the potential distraction from the borders, only the center of the images (that is, sub-images that are half of the width and half of the height of the original images) are taken when performing comparison. There is no observable difference between these two metrics when testing on most of the images, and SSD is used in the subsequent implementation.

Edge as feature v.s. color intensity as feature

The algorithm is implemented to work with either color intensity information or edge information when calculating sum of squared difference. To obtain edge information, matlab's edge function is used to find edges in the images using a canny edge detector. When testing on the images, the edge feature outperforms the color intensity feature on some of the images given the same window size, as shown below.

Using color intensity as feature
Using edge information as feature

Implementation of Image Pyramid

An image pyramid with level 4 is implemented to speed up the image processing. The image pyramid is contructed by starting from the original image and iteratively producing images that are half the width and half the height of the previous image. To produce a smaller image, the original image is first blurred using the matlab imfilter function with a Gussian filter, and then sampled by taking only pixels from the odd numbered rows and columns. After constructing the image pyramid, the algorithm then aligns each of the images in the image pyramid, starting from the smallest one. In each round, the best shift vector is recorded as v_best. When aligning the next image, the shift window is centered at v_best * 2. In this way, the algorithm only needs to search over a very small shift window in each round and thus speed up the alignment.

Automatic cropping

Automatic cropping of the borders have been implemented by using edge information extracted from the images. After the shift vectors have been computed and the images have been shifted accordingly, edge detection is performed on the shifted images using a canny edge detector. Then, the algorithm finds all the rows and columns that have a large portion of pixels marked as being on the edge and are close to the border of the image. It then forms the new border of the image by takeing the rows and columns from the previously determined sets that are closest to the center of the image.

Original image
The image with the borders automatically removed

Gray world assumption

As the color mapping of the original images is not necessarily perfect RGB mapping, the gray world assumption - the assumption that the average value of red, green and blue components of a given image should average out to be a common gray value - has been adopted to adjust the image color. After the image is shifted and the border is chopped, the average values of the red, green, blue channels are calculated, and so is the average value of the three channels. The pixel values in the red channel are then adjusted by p(r)_new = p(r)_old * avg_gray / avg_red, and the pixel values in the other two channels are also adjusted in a similar manner.

Without gray world assumption
With gray world assumption

Automatic contrasting

Two different ways were applied to perform automatic contrasting. Initially, I attempted to find the darkest pixel x and the brightest pixel y from the pixels from all the channels, calculate the ratio = (y-x)/(255/256), and adjust each pixel to be p_new = (p_old - x) / ratio. However, this algorithm does not seem to have a significant effect on the images that I have tested, presumbly because this algorithm enhances the contrast in a relatively gentle way and that the darkest pixel and bright pixel in the images are close to 0 and 1 respectively already. Therefore, I instead applied a matlab function histeq, and the result is shown below.

Without automatic contrast
With automatic contrast

Gallary

Below are the other images from Prokudin-Gorskii that have been reconstructed using the algorithms described on this page.