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.