Report 2009-41

Optimal image alignment with random projections of manifolds: algorithm and geometric analysis

E. Kokiopoulou, D. Kressner and P. Frossard

Abstract: This paper addresses image alignment based on random measurements. Image alignment consists in estimating the relative transformation between a query image and a reference image. We consider the specific problem where the query image is not given exactly, but rather provided in a compressed form with linear measurements captured by a vision sensor. According to the theory behind compressed sensing, image alignment can still be performed effectively in this case, provided that the number of measurements is sufficiently large. We cast the alignment problem as a manifold distance minimization problem in the linear subspace defined by the measurements. We then show that, when the reference image is sparsely represented over parametric dictionaries, the corresponding objective function can be decomposed as the difference of two convex functions (DC). Thus the optimization problem becomes a DC program, which in turn can be solved globally optimally by, e.g., a cutting plane method. The quality of the solution is typically affected by the number of random measurements and the condition number of the manifold that describes the transformations of the reference image. We show that the manifold condition number remains bounded in our image alignment problem, which means that the relative transformation between two images can be determined optimally in a reduced subspace.

Paper: Available as PDF (564KB) or as hardcopy to order reports@sam.math.ethz.ch.