New complexity bounds for image matching under rotation and scaling

Christian Hundt*, MacIej Liskiewicz

*Corresponding author for this work
1 Citation (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).

Original languageEnglish
JournalJournal of Discrete Algorithms
Issue number1
Pages (from-to)122-136
Number of pages15
Publication statusPublished - 01.03.2011


Dive into the research topics of 'New complexity bounds for image matching under rotation and scaling'. Together they form a unique fingerprint.

Cite this