  We examine in this paper the problem of image registration from the new
perspective where images are given by sparse approximations in parametric
dictionaries of geometric functions. We propose a registration algorithm that
looks for an estimate of the global transformation between sparse images by
examining the set of relative geometrical transformations between the
respective features. We propose a theoretical analysis of our registration
algorithm and we derive performance guarantees based on two novel important
properties of redundant dictionaries, namely the robust linear independence and
the transformation inconsistency. We propose several illustrations and insights
about the importance of these dictionary properties and show that common
properties such as coherence or restricted isometry property fail to provide
sufficient information in registration problems. We finally show with
illustrative experiments on simple visual objects and handwritten digits images
that our algorithm outperforms baseline competitor methods in terms of
transformation-invariant distance computation and classification.

Computer Vision and Pattern Recognition