TR07-066 Authors: Maciej Liskiewicz, Christian Hundt

Publication: 23rd July 2007 16:11

Downloads: 3465

Keywords:

The problem of image matching is to find for two given digital images $A$ and $B$

an admissible transformation that converts image $A$ as close as possible to $B$.

This problem becomes hard if the space of admissible transformations is too complex.

Consequently, in many real applications, like the ones allowing nonlinear elastic

transformations, the known algorithms solving the problem either work in exponential

worst-case time or can only guarantee to find a local optimum. In this paper we study

the image matching problem for affine transformations, an important class of functions,

from the image matching point of view, and we give a generic exhaustive search algorithm

solving the problem in polynomial time. Next, we apply the algorithm for some important

subclasses of affine transformations like translations, rotations, scalings, and linear

transformations and we prove lower and upper bounds for the corresponding search spaces.

Furthermore we extend the results to projective transformations which are a natural

generalization of affine transformations.