A combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotation

The problem of two-dimensional pattern matching invariant under a given class of admissible transformations F is to find matches of transformed versions f(P) of a pattern P in a given text T, for all f in F. In this paper, pattern matching invariant under compositions of real valued 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(m2n6) for patterns of size m2 and texts of size n2. We conclude with an experimental section to support the practical use of our results.