New complexity bounds for image matching under rotation and scaling

Christian Hundt*, MacIej Liskiewicz

*Korrespondierende/r Autor/-in für diese Arbeit
1 Zitat (Scopus)


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) on the worst case cardinality of this set for images of size n×n and presents the first optimal algorithm of such kind, i.e., one that solves image matching under rotations in time 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×n image is provided. This bound almost matches the upper bound O(n6).

ZeitschriftJournal of Discrete Algorithms
Seiten (von - bis)122-136
PublikationsstatusVeröffentlicht - 01.03.2011


Untersuchen Sie die Forschungsthemen von „New complexity bounds for image matching under rotation and scaling“. Zusammen bilden sie einen einzigartigen Fingerprint.