Lecture Notes in Computer Science, 2008, Volume 5029/2008, 5-17, DOI: 10.1007/978-3-540-69068-9_4

Two-Dimensional Pattern Matching with Combined Scaling and Rotation

Christian Hundt and Maciej Liśkiewicz

View Related Documents

Abstract

The problem of two-dimensional pattern matching invariant under a given class of admissible transformations F\mathcal{F} is to find in text T matches of transformed versions f(P) of the pattern P, for all f in F\mathcal{F} . In this paper, pattern matching invariant under compositions of real scaling and rotation are investigated. We give a new discretization technique for this class of transformations and prove sharp lower and upper bounds on the number of different possibilities to transform a pattern in this way. Subsequently, we present the first efficient pattern matching algorithm invariant under compositions of scaling and rotation. The algorithm works in time O(m 2 n 6) for patterns of size m 2 and texts of size n 2. Our method can also be applied to the image matching problem, the well known issue in the image processing research.

Keywords  combinatorial pattern matching - digital image matching - discrete rotations and scalings - discrete algorithms

Supported by DFG research grant RE 672/5-1.

Fulltext Preview

Image of the first page of the fulltext document