Abstract
Image matching is an important problem in image processing and arises in such diverse fields as video compression, optical character recognition, medical imaging, watermarking etc. Given two images, image matching determines a transformation that changes the first image such that it most closely resembles the second. Common approaches require either exponential time, or find only an approximate solution, even when only rotations and scalings are allowed. This paper provides the first general polynomial time algorithm to find the exact solution to the image matching problem under projective, affine or linear transformations. Subsequently, nontrivial lower bounds on the number of different transformed images are given which roughly induce the complexity of image matching under the three classes of transformations.
Supported by DFG research grant RE 672/5-1.
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
Bovik, A. (ed.): Handbook of Image and Video Processing. Academic Press, San Diego, California (2000)
Amir, A., Butman, A., Crochemore, M., Landau, G., Schaps, M.: Two dimensional pattern matching with rotations. Theor. Comput. Sci. 314(1-2), 173–187 (2004)
Amir, A., Chencinski, E.: Faster 2-Dimensional Scaled Matching. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol. 4009, pp. 200–210. Springer, Heidelberg (2006)
Amir, A., Tsur, D., Kapah, O.: Faster Two Dimensional Pattern Matching with Rotations. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol. 3109, pp. 409–419. Springer, Heidelberg (2004)
Brown, L.G.: A survey of image registration techniques. ACM Computing Surveys 24(4), 325–376 (1992)
Cox, I.J., Bloom, J.A., Miller, M.L.: Digital Watermarking, Principles and Practice. Morgan Kaufmann, San Francisco, California (2001)
Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer, Berlin (1987)
Edelsbrunner, H., O’Rourke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput. 15, 341–363 (1986)
Fredriksson, K., Ukkonen, E.: A rotation invariant filter for two dimensional string matching. In: Proc. CPM. LNCS, vol. 1448, pp. 118–125 (1998)
Ukkonen, E., Navarro, G., Fredriksson, K.: Optimal Exact and Fast Approximate Two Dimensional Pattern Matching Allowing Rotations. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol. 2373. Springer, Heidelberg (2002)
Hagedoorn, M.: Pattern matching using similarity measures, PhD Thesis, Univ. Utrecht (2000)
Hundt, C., Liśkiewicz, M.: On the Complexity of Affine Image Matching. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 284–295. Springer, Heidelberg (2007)
Hundt, C., Liśkiewicz, M.: Two-dimensional Pattern Matching with Combined Scaling and Rotation. In: Proc. CPM 2008. LNCS, vol. 5029 (2008)
Indyk, P.: Algorithmic aspects of geometric embeddings. In: Proc. FOCS, pp. 10–33. IEEE Computer Society Press, Los Alamitos (2001)
Kasturi, R., Jain, R.C.: Computer Vision: Principles. IEEE Computer Society Press, Los Alamitos (1991)
Keysers, D., Unger, W.: Elastic image matching is NP-complete. Pattern Recogn. Letters 24, 445–453 (2003)
Kropatsch, W.G., Bischof, H. (eds.): Digital Image Analysis - Selected Techniques and Applications. Springer, Berlin (2001)
Landau, G.M., Vishkin, U.: Pattern matching in a digitized image. Algorithmica 12(3/4), 375–408 (1994)
Maintz, J.B.A., Viergever, M.A.: A survey of medical image registration. Medical Image Analysis 2, 1–36 (1998)
Modersitzki, J.: Numerical Methods for Image Registration. Oxford University Press, Oxford (2004)
Moeslund, T.B., Hilton, A., Krüger, V.: A survey of advances in vision-based human motion capture and analysis. Computer Vision and Image Understanding 104(2-3), 90–126 (2006)
Shi, Y.Q., Sun, H.: Image and video Compression for multimedia engineering. CRC Press, Boca Raton (2000)
Solanki, K., Madhow, U., Manjunath, B.S., Chandrasekaran, S., El-Khalil, I.: ’Print and Scan’ Resilient Data Hiding in Images. IEEE Transactions on Information Forensics and Security 1(4), 464–478 (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hundt, C., Liśkiewicz, M. (2008). Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations. In: Ochmański, E., Tyszkiewicz, J. (eds) Mathematical Foundations of Computer Science 2008. MFCS 2008. Lecture Notes in Computer Science, vol 5162. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85238-4_32
Download citation
DOI: https://doi.org/10.1007/978-3-540-85238-4_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85237-7
Online ISBN: 978-3-540-85238-4
eBook Packages: Computer ScienceComputer Science (R0)