title: Optimal image alignment with random projections of manifolds: algorithm and geometric analysis.
abstract: This paper addresses the problem of image alignment based on random measurements. Image alignment consists of estimating the relative transformation between a query image and a reference image. We consider the specific problem where the query image is provided in compressed form in terms of linear measurements captured by a vision sensor. We cast the alignment problem as a manifold distance minimization problem in the linear subspace defined by the measurements. The transformation manifold that represents synthesis of shift, rotation, and isotropic scaling of the reference image can be given in closed form when the reference pattern is sparsely represented over a parametric dictionary. We show that the objective function can then be decomposed as the difference of two convex functions (DC) in the particular case where the dictionary is built on Gaussian functions. Thus, the optimization problem becomes a DC program, which in turn can be solved globally by 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 curvature, which is closely related to the 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.
authors.affiliation: Seminar for Applied Mathematics, Department of Mathematics, ETH Zurich, CH-8092 Zurich, Switzerland. effrosyni.kokiopoulou@sam.math.ethz.ch
authors.forename: Effrosyni
authors.initials: E
authors.lastname: Kokiopoulou
authors.forename: Daniel
authors.initials: D
authors.lastname: Kressner
authors.forename: Pascal
authors.initials: P
authors.lastname: Frossard
mesh_terms: D000465:Algorithms; D007089:Image Enhancement / Q000379:methods*; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D010363:Pattern Recognition, Automated / Q000379:methods*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D013382:Subtraction Technique