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.