The generic combinatorial algorithm for image matching with classes of projective transformations

Image matching is an important task arising in video compression, optical character recognition, medical imaging, watermarking and in many others fields. Given two digital images A and B, image matching determines a transformation f for A such that it most closely resembles B. In this paper, we introduce the first general discretization technique that works for the class of projective transformations as well as plenty of its subclasses such as affine transformations and several combinations of scaling, rotation and translation. Based on this, we provide a fully generic image matching algorithm for all these classes that runs in polynomial time.