Benbrook Chen Leckie Lopez

Introduction

Image alignment is the process of matching one image called template with another image. It is a crucial step in many image systems engineering applications such as video stabilization, summarization, and the creation of panoramic mosaics.

Background

Previous work on image alignment algorithms fall into two categories: intensity-based and feature-based. Intensity-based algorithms compare the spatial intensity in sets of images, while feature-based algorithms detect image features like objects or lines. Image alignment algorithms can alternatively be sorted according to the transformation on the target image space to the reference image space. Some models use linear transformations, while other models use non-linear transformations that are elastic or non-rigid.

Methods

The main goal of this project is to experiment with existing image alignment algorithms and analyze their performance. We will focus on comparing algorithms that utilize feature-based, linear transformation models. We used data from the ISET3D software on simulated images taken by various cameras and sensors, and images where the object is moving as well as the global scene. Once we align images, we can use root mean squared error or SSIM (structural similarity) as metrics to compare the results between algorithms.

Algorithms

Speeded Up Robust Features (SURF)

Our first two algorithms are based on Speeded Up Robust Features (SURF), a patented feature detector and descriptor. SURF accomplishes the task of finding correspondences between two images of the same scene. It accomplishes this in three steps: (1) “interest points” are selected at distinctive locations in the image, (2) the neighborhood of every interest point is represented by a feature vector, and (3) the descriptor vectors are matched between the different images. It is important that the detector is repeatable so that it can reliably find the same interest points under different viewing conditions. It is also important for the descriptor to be distinctive so that it can be broken out from noise, errors, and deformations.

Random Sample Consensus (RANSAC)

RANSAC is a paradigm that fits a model to experimental data, and it is capable of interpreting and smoothing data containing errors, or outliers. This is ideal for interpreting data that comes from error-prone feature detectors, such as SURF. Unlike least squares, RANSAC is capable of smoothing data that contains a significant percentage of gross errors, which is common in scene analysis. Instead of using as much of the data as possible to obtain a solution, RANSAC uses a small initial data set and then enlarges it with consistent data. Once a set of mutually consistent points is identified, a smoothing technique such as least squares is used to compute an improved estimate.

Least Squares

A classical technique for parameter estimation that optimizes a fit to all of the presented data. It does not detect and reject gross errors, or outliers. It relies on the assumption that the size of the dataset will be large enough that there will be enough good values to smooth out any gross deviations. The least squares method solves the image alignment problem by minimizing the sum of the squared residuals using a cost function. It is also possible to do weighted least squares, which defines how far the image is from the mean. The least squares method can be computationally costly depending on the matrix size.

Enhanced Correlation Coefficient (ECC)

ECC is an image alignment algorithm that achieves high accuracy in parameter estimation. It combines the low computation cost of gradient-based approaches with the performance of direct search techniques. Furthermore, it improves on the problem of brightness constancy. Since it considers the enhanced correlation coefficient, its performance remains unchanged in illumination changes and photometric distortions. The iterative scheme used for the optimization problem turns out to be linear, which reduces computational complexity.

Test Metrics

In order to test the results of our alignment algorithms, we used two different test metrics to evaluate our images.

Structural Similarity Index (SSIM)

The SSIM quantifies the degradation of image quality after processing or losses during data transmission.The SSIM takes two images from the same image capture and measures the perceptual difference. SSIM was created as an improvement to other traditional methods like peak signal-to-noise ratio (PSNR) and mean squared error (MSE).

While MSE and PSNR estimate absolute errors, SSIM calculates changes in structural information and takes into account image perception through luminescence masking and contrast masking components. Structural information is defined as the strong correlation between pixels that are spatially close. The correlations can elucidate structural information of the image scene, like objects. Luminance masking is the concept that distortions are more visible in darker regions. Contrast masking is the concept that distortions are less noticeable in areas of the image that are highly textured.

References

[1] Oleg Krivtsov, “Image Alignment Algorithms,” Code Project, 2008.

[2] Richard Szeliski (2007), "Image Alignment and Stitching: A Tutorial", Foundations and Trends® in Computer Graphics and Vision: Vol. 2: No. 1, pp 1-104.

[3] H.Bay, A.Ess, T.Tuytelaars, L.V.Gool, “SURF: Speeded Up Robust Features”, Computer Vision and Image Understanding (CVIU), Vol. 110, No. 3, pp. 346–359, 2008.

[4] Martin A. Fischler and Robert C. Bolles (June 1981). “Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography”. Comm. of the ACM 24 (6): 381–395.

[5] G.D. Evangelidis, E.Z. Psarakis, Parametric Image Alignment using Enhanced Correlation Coefficient Maximization", IEEE Trans. on PAMI, vol. 30, no. 10, 2008.

Appendix

You can write math equations as follows: $y=x+5$

You can include images as follows (you will need to upload the image first using the toolbox on the left bar, using the "Upload file" link).