Faster Two Dimensional Scaled Matching

作者：Amir Amihood^*; Chencinski Eran

来源：Algorithmica, 2010, 56(2): 214-234.

DOI：10.1007/s00453-008-9173-3

• Multidimensional pattern matching
• Scaled pattern matching
• Theory of discrete image processing

The rapidly growing need for analysis of digitized images in multimedia systems has lead to a variety of interesting problems in multidimensional pattern matching. One of the problems is that of scaled matching, finding all appearances of a pattern, proportionally enlarged according to an arbitrary real-sized scale, in a given text.
The currently fastest known algorithm for this problem uses techniques from dictionary matching to solve the problem in O(nm (3)+n (2) mlog m) time using O(nm (3)+n (2)) space, where T is a two-dimensional nxn text array and P is a two-dimensional mxm pattern array.
We present a new approach for solving the scaled matching problem improving both the running time and the space requirements. Our algorithm runs in O(n (2) m) time and uses O(n (2)) space.

• 出版日期2010-2