Abstract
The two-dimensional pattern matching problem is to find all occurrences of a two-dimensional m × m matrix P (called the pattern) in another (larger) two-dimensional n × n matrix T (called the text). Most known algorithms for the problem first pre-process the pattern or patterns to make subsequent searches fast. Since each search still takes time proportional to the size of the text, such algorithms are inappropriate in applications in which the text is large and fixed and one will search for many different patterns in the text. We propose an algorithm that first processes the text into an index structure in such a way that subsequent searches with different patterns can be performed very quickly. The construction of the index takes O(n 2log n) time and O(n 2) space. The algorithm may produce false matches, in which the algorithm claims a “match” between P and some submatrix of T while they are actually not equal. However, as will be seen, the probability that a false match can occur is negligible. All occurrences of P in T, probably with a few false matches, can be found in O(m 2) time in the worst case, regardless of the distribution of the elements in T and P. Under the assumption that both T and P are random matrices, the algorithm can find all (correct) occurrences of P in T in O(m + log n) expected time. We applied our algorithm to a digital image search problem and we will present experimental results.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Amir, A., Benson, G., Farach, M.: Alphabet Independent Twodimensional Matching. In: Proc. the 24th annual ACM Symposium on Theory of Computing, pp. 59–68 (1992)
Aho, A.V., Corasick, M.: Efficient string matching: an aid to bibliographic search. Communications of the ACM 18(6), 333–340 (1975)
Amir, A., Landau, G.: Fast parallel and serial multidimensional approximate array matching. Theoretical Computer Science 81, 97–115 (1991)
Baker, T.J.: A Technique for Extending Rapid Exact-Match String Matching to Arrays of More Than One Dimension. SIAM J. on Computing 7, 533–541 (1978)
Bird, R.S.: Two Dimensional Pattern Matching. Information Processing Letters 6(5), 168–170 (1977)
Boyer, R.S., Moore, J.S.: A fast matching algorithm. Commun. ACM 20, 762–772 (1977)
Giancarlo, R.: The Suffix of a Square Matrix, with Applications. In: Proc. Fourth Symposium on Discrete Algorithms. ACM-SIAM, pp. 402–411 (1993)
Giancarlo, R., Grossi, R.: Suffix Tree Data Structures for Matrices. In: Apostolico, A., Galil, Z. (eds.) Pattern Matching Algorithms, pp. 293–340. Oxford University Press, Oxford (1997)
Galil, Z., Park, K.: Truly Alphabet-Independent Two-dimensional Pattern Matching. In: Proc. 33th Symposium on Foundations of Computer Science, IEEE, pp. 247–256 (1992)
Knuth, D.E., Morries, J.H., Pratt, V.B.: Fast pattern matching in strings. SIAM J. on Computing 6, 189–195 (1977)
Karp, R., Rabin, M.: Efficient Randomized Pattern Matching Algorithms. IBM J. Res. Develop. 31(2), 249–260 (1987)
Manber, U., Myers, G.: Suffix Arrays: A New Method for On-Line String Searches. SIAM Journal on Computing 22, 935–948 (1993)
Rosser, J.B., Schoenfeld, L.: Approximate Formulas for Some Functions of Prime Numbers. Illinois J. Math 6, 64–94 (1962)
Shi, F.: Suffix arrays for multiple strings: a method for on-line multiple string searches. In: Jaffar, J., Yap, R.H.C. (eds.) ASIAN 1996. LNCS, vol. 1179. Springer, Heidelberg (1996)
Zhu, R.F., Takaoka, T.: A Technique for Two-Dimensional Pattern Matching. Communications of the ACM 32(9), 1110–1120 (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shi, F., AlShibli, A. (2005). An Indexing Method for Two-D Pattern Matching with Applications to Digital Image Searches. In: Zhang, Y., Tanaka, K., Yu, J.X., Wang, S., Li, M. (eds) Web Technologies Research and Development - APWeb 2005. APWeb 2005. Lecture Notes in Computer Science, vol 3399. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31849-1_84
Download citation
DOI: https://doi.org/10.1007/978-3-540-31849-1_84
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25207-8
Online ISBN: 978-3-540-31849-1
eBook Packages: Computer ScienceComputer Science (R0)