Abstract
We address the problem of searching for a two-dimensional pattern in a two-dimensional text (or image), such that the pattern can be found even if it appears rotated and brighter or darker than its occurrence. Furthermore, we consider approximate matching under several tolerance models. We obtain algorithms that are almost worst-case optimal. The complexities we obtain are very close to the best current results for the case where only rotations, but not lighting invariance, are supported. These are the first results for this problem under a combinatorial approach.
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., Butman, A., Crochemore, M., Landau, G.M., Schaps, M.: Two-dimensional pattern matching with rotations. In: Baeza-Yates, R., Chávez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol. 2676, pp. 17–31. Springer, Heidelberg (2003)
Brown, L.G.: A survey of image registration techniques. ACM Computing Surveys 24(4), 325–376 (1992)
Crawford, T., Iliopoulos, C., Raman, R.: String matching techniques for musical similarity and melodic recognition. Computing in Musicology 11, 71–100 (1998)
de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 2nd rev. edn. Springer, Heidelberg (2000)
Fredriksson, K., Mäkinen, V., Navarro, G.: Rotation and lighting invariant template matching. Technical Report TR/DCC-2003-3, Dept. of Comp.Sci., Univ. of Chile (2003), ftp://ftp.dcc.uchile.cl/pub/users/gnavarro/lighting.ps.gz
Fredriksson, K., Navarro, G., Ukkonen, E.: Faster than FFT: Rotation Invariant Combinatorial Template Matching, vol. II, pp. 75–112. Trans.Res.Net (2002)
Fredriksson, K., Navarro, G., Ukkonen, E.: Optimal exact and fast approximate two dimensional pattern matching allowing rotations. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol. 2373, pp. 235–248. Springer, Heidelberg (2002)
Fredriksson, K., Ukkonen, E.: A rotation invariant filter for two-dimensional string matching. In: Farach-Colton, M. (ed.) CPM 1998. LNCS, vol. 1448, pp. 118–125. Springer, Heidelberg (1998)
Fredriksson, K., Ukkonen, E.: Combinatorial methods for approximate image matching under translations and rotations. Patt. Rec. Lett. 20(11-13), 1249–1258 (1999)
Fredriksson, K., Navarro, G., Ukkonen, E.: An index for two dimensional string matching allowing rotations. In: Watanabe, O., Hagiya, M., Ito, T., van Leeuwen, J., Mosses, P.D. (eds.) TCS 2000. LNCS, vol. 1872, pp. 59–75. Springer, Heidelberg (2000)
Lemström, K., Tarhio, J.: Detecting monophonic patterns within polyphonic sources. In: Proc. RIAO 2000, pp. 1261–1279 (2000)
Mäkinen, V., Navarro, G., Ukkonen, E.: Algorithms for transposition invariant string matching. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 191–202. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fredriksson, K., Mäkinen, V., Navarro, G. (2004). Rotation and Lighting Invariant Template Matching. In: Farach-Colton, M. (eds) LATIN 2004: Theoretical Informatics. LATIN 2004. Lecture Notes in Computer Science, vol 2976. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24698-5_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-24698-5_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21258-4
Online ISBN: 978-3-540-24698-5
eBook Packages: Springer Book Archive