کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431345 | 688509 | 2011 | 15 صفحه PDF | دانلود رایگان |

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).
Journal: Journal of Discrete Algorithms - Volume 9, Issue 1, March 2011, Pages 122–136