کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431345 688509 2011 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
New complexity bounds for image matching under rotation and scaling
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
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).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 9, Issue 1, March 2011, Pages 122–136
نویسندگان
, ,