Abstract
All the effective object recognition systems are based on a powerful shape descriptor. We propose a new method for extracting the topological feature of an object. By connecting all the pixels constituting the object under the constraint to define the shortest path (minimum spanning tree) we capture the shape topology. The tree length is in the first approximation the key of our object recognition system. This measure (with some adjustments) make it possible to detect the object target in several geometrical configurations (translation / rotation) and it seems to have many desirable properties such as discrimination power and robustness to noise, that is the conclusion of the preliminary tests on characters and symbols.
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
Ma, B., Hero, A., Gorman, J., Michel, O.: Image registration with minimal spanning tree algorithm. In: IEEE International Conference on Image Processing, Vancouver (October 2000)
Graham, R., Hell, P.: On the history of minimum spanning tree problem. IEEE Annals of the History of Computing 7(1), 43–57 (1985)
Hero, A., Michel, O.: Robust entropy estimation strategies based on edge weighted random graphs. In: SPIE, International Symposium on Optical Science, Engineering and Instrumentation, San Diego (July 1998)
Hero, A., Michel, O.: Asymptotic theory of greedy approximations to minimal k-point random graphs. IEEE Transactions on Information Theory, IT 45, 1921–1939 (1999)
Hu, M.: Visual pattern recognition by moment invariants. IEEE Transactions on Information Theory, IT 8, 179–187 (1962)
Khotanzad, A., Hong, Y.: Rotation invariant image recognition using features selected via a systematic method. Pattern Recognition (23), 1089–1101 (1990)
Kita, N.: Object locating based on concentric circular description. In: Proceedings of 11th IEEE International Conference of Pattern Recognition, The Hague, pp. 637–641 (1992)
Karger, D., Klein, P., Tarjan, R.: A randomized linear-time algorithm to find minimum spanning trees. Journal of the Association for Computing Machinery (ACM) 42(2), 321–328 (1995)
Kresch, R., Malah, D.: Morphological reduction of skeleton redundancy. Signal Processing 38, 143–151 (1994)
Cormen, T., Leiserson, C., Rivest, R.: Introduction to algorithms. The MIT Press, Cambridge (1994)
Lin, C.: New forms of shape invariants from elliptic fourier descriptors. Pattern Recognition (20), 535–545 (1987)
Mai, L.C.: Introduction to computer vision and image processing. United Nations Educational, Scientific and Cultural Organisation, UNESCO (2000)
Maragos, P., Shafer, R.: Morphological skeleton representations and coding of binary images. IEEE Transactions on Accoustics, Speach and Signal Processing 34(5), 1228–1244 (1986)
Pei, S., Lin, C.: Normalisation of rotationally symmetric shapes for pattern recognition. Pattern Recognition (25), 913–920 (1992)
Redmond, C., Yukich, J.E.: Limit theorems and rates of convergence for euclidean functionals. Annals of Applied Probability 4(4), 1057–1073 (1994)
Reiss, T.: Recognizing planar objects using invariants image features. LNCS. Springer, Berlin (1993)
Rény, A.: On measures of entropy and information. In: Symposium on Mathematics Statistics and Probabilities, Berkeley, pp. 547–561 (1961)
Ravi, R., Marathe, M., Rosenkrantz, D., Ravi, S.: Spanning trees short or small. SIAM, Journal on Discrete Mathematics 9, 178–200 (1996)
Serra, J.: Image analysis and mathematical morphology. Theoretical Advances, vol. 2. Academic Press, London (1988)
Soss, M.: On the size of the sphere on influence graph. PhD thesis, Mc Gill University Scholl of Computer Science Montreal (1998)
Teague, M.: Image analysis via the general theory of moments. Journal of the Optical Society of America 70, 920–930 (1980)
Tabbone, S., Wendling, L., Tombre, K.: Indexing of technical line drawings based on f-signatures. In: 6th International Conference on Document Analysis and Recognition (ICDAR), Seattle, Washington, USA, September 2001, pp. 1220–1224 (2001)
Ye, M.: Symbol recognition package (2000); In http://www.ee.washington.edu/research/ ..., by the Intelligent Systems Lab. Depart. of Elect. Engin. University of Washington
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
Franco, P., Ogier, JM., Loonis, P., Mullot, R. (2004). A Topological Measure for Image Object Recognition. In: Lladós, J., Kwon, YB. (eds) Graphics Recognition. Recent Advances and Perspectives. GREC 2003. Lecture Notes in Computer Science, vol 3088. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-25977-0_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-25977-0_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22478-5
Online ISBN: 978-3-540-25977-0
eBook Packages: Springer Book Archive