New complexity bounds for image matching under rotation and scaling

Image matching under rotation is a computational problem to determine for two given images A and B a rotation of A that most accurately resembles B. The research in combinatorial pattern matching led to a series of improved algorithms which commonly solve this problem by a sophisticated search in the set of all rotations of A  . This paper provides the lower bound Ω(n3)Ω(n3) on the worst case cardinality of this set for images of size n×nn×n and presents the first optimal algorithm of such kind, i.e., one that solves image matching under rotations in time O(n3)O(n3). Moreover, for image matching under compositions of rotation and scaling a new lower bound Ω(n6/logn) on the worst case cardinality of the set of rotated and scaled transformations of an n×nn×n image is provided. This bound almost matches the upper bound O(n6)O(n6).