On the Computational Complexit of Projective Image Matching

Image matching is an important problem in image processing and arises in such diverse elds as video compression, optical character recognition, medical imaging, watermarking and others. Given two digital images A and B, image matching determines a transformation f for A such that it most closely resembles B. Conventional approaches require either exponential time, or nd only an approximate solution, even when f has to consist of only rotations and scalings.
This thesis introduces the rst known discretization technique for the class Fp of projective transformations. Based on this, it shows a polynomial bound on the cardinality of D(A), the set containing all di erent transformations of A with f 2 Fp. Accordingly, structural properties of D(A) lead to a polynomial time algorithm that nds the exact solution to the projective image matching problem by searching through the complete set D(A). The algorithm is applicable for various natural subclasses of projective transformations, such as e. g. ane transformations.
From a theoretical point of view providing a polynomial time algorithm for projective image matching is not enough to completely characterize the complexity of the problem. Accordingly, TCO, a class of problems deep in the hierarchy within PTIME, is shown to exactly describe the complexity of image matching with projective transformations. This relates the problem to a number of most basic challenges in computer science, like integer multiplication, division and sorting. Beyond this, the containment in TCO implies extremely ecient parallel algorithms for image matching.