RASL: Robust Batch Alignment of Images by Sparse and Low-Rank Decomposition
Pixelwise image alignment is an important problem in computer vision since domain transformations make it difficult to measure image similarity for recognition or classification. Thus, the problem is to align multiple images of an object or objects of interest to a fixed canonical template.
Suppose we are given n images of an object, I1,..., In that are not well-aligned to each other. Assuming that the degree of misalignment is not too large, we model the misalignment as a global domain transformation belonging to a finite-dimensional group. Thus, we have transformations τ1,...τn such that the transformed images I1 ο τ1,..., In ο τn are well-aligned. The goal is to compute these transformations.
Let A be a matrix whose columns represent well-aligned images of an object. Since these images exhibit high linear correlation, the matrix A is expected to have low rank. However, in practice, we have various sources of error in images (self-shadowing, specularities, etc.) that violate this model. We represent such large, sparse errors by the matrix E. Thus, A + E represents a matrix whose columns correspond to well-aligned images of an object. By our formulation, we have [I1 ο τ1,..., In ο τn] = A + E. Thus, our goal is to find a low-rank matrix A and a sparse matrix E such that this equation is satisfied. This can be more precisely formulated as an optimization problem (using a Lagrangian form) as :
where D is a matrix whose columns represent the misaligned input images, τ is the set of all transformations such that D ο τ = [I1 ο τ1,..., In ο τn], γ is a positive weighting parameter, and ||E||0 represents the number of non-zero entries in the matrix E. Although the above problem follows naturally from our problem formulation, the cost function is highly non-convex and discontinuous, and the equality constraint is highly non-linear. Thus, it is intractable, and of little practical use.
Recent work in compressed sensing and matrix completion suggests that the above problem can be efficiently solved, under quite general conditions, by replacing the cost function with its convex surrogate, as shown below:
where ||A||* represents the nuclear norm of A (the sum of its singular values), ||E||1 represents the 1-norm of E (the sum of absolute values of its entries), and λ is a positive weighting factor. Although the cost function is convex and continuous, the constraint is non-linear. Therefore, we solve the optimization problem by iterative linearization of the constraint. For more details on the algorithm and implementation, please refer to our paper.
Robust Image Alignment via Sparse and Low-Rank Decomposition
The above code and data can be used to generate most of the example images in our paper. The images in the folder 'LFW' are part of the Labeled Faces in the Wild dataset.
If you use the above code or data, please cite our paper.
RASL: Robust Alignment by Sparse and Low-rank Decomposition for Linearly Correlated Images,| Problem Description | Introduction | Sample Code | Publications |
 |
 |
 |
 |
| Input images chosen at random from the internet. |
Input images realigned using the transformations computed by RASL. |
Low-rank representation computed by RASL. The images are free of misalignment and large corruptions (like magazine logos, etc.) |
Problem
Formulation
Pixelwise image alignment is an important problem in computer vision since domain transformations make it difficult to measure image similarity for recognition or classification. Thus, the problem is to align multiple images of an object or objects of interest to a fixed canonical template.
Suppose we are given n images of an object, I1,..., In that are not well-aligned to each other. Assuming that the degree of misalignment is not too large, we model the misalignment as a global domain transformation belonging to a finite-dimensional group. Thus, we have transformations τ1,...τn such that the transformed images I1 ο τ1,..., In ο τn are well-aligned. The goal is to compute these transformations.
Robust Alignment by Sparse and Low-Rank Decomposition
Let A be a matrix whose columns represent well-aligned images of an object. Since these images exhibit high linear correlation, the matrix A is expected to have low rank. However, in practice, we have various sources of error in images (self-shadowing, specularities, etc.) that violate this model. We represent such large, sparse errors by the matrix E. Thus, A + E represents a matrix whose columns correspond to well-aligned images of an object. By our formulation, we have [I1 ο τ1,..., In ο τn] = A + E. Thus, our goal is to find a low-rank matrix A and a sparse matrix E such that this equation is satisfied. This can be more precisely formulated as an optimization problem (using a Lagrangian form) as :
Recent work in compressed sensing and matrix completion suggests that the above problem can be efficiently solved, under quite general conditions, by replacing the cost function with its convex surrogate, as shown below:
Sample Code and Data
A MATLAB implementation of our algorithm, along with some sample data, can be downloaded at the following link:
Robust Image Alignment via Sparse and Low-Rank Decomposition
The above code and data can be used to generate most of the example images in our paper. The images in the folder 'LFW' are part of the Labeled Faces in the Wild dataset.
If you use the above code or data, please cite our paper.
Publications
Yigang Peng, Arvind Ganesh, John Wright, Wenli Xu, and Yi Ma. Submitted to IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), July 2010.
[Conference version presented at CVPR 2010]
Please contact the webmaster Arvind Ganesh if you have any questions or comments regarding the paper or code.