Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-066 | 24th April 2007 00:00

A Combinatorial Geometric Approach to Linear Image Matching


Authors: Maciej Liskiewicz, Christian Hundt
Publication: 23rd July 2007 16:11
Downloads: 3233


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.

ISSN 1433-8092 | Imprint