Abstract:
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.