Abstract
We introduce a method for computing homology groups and their generators of a 2D image, using a hierarchical structure i.e. irregular graph pyramid. Starting from an image, a hierarchy of the image is built, by two operations that preserve homology of each region. Instead of computing homology generators in the base where the number of entities (cells) is large, we first reduce the number of cells by a graph pyramid. Then homology generators are computed efficiently on the top level of the pyramid, since the number of cells is small, and a top down process is then used to deduce homology generators in any level of the pyramid, including the base level i.e. the initial image. We show that the new method produces valid homology generators and present some experimental results.
Supported by the Austrian Science Fund under grants P18716-N13 and S9103-N04.
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
Kovalevsky, V.A.: Finite topology as applied to image analysis. Computer Vision, Graphics, and Image Processing 46, 141–161 (1989)
Kovalevsky, V.A.: Digital Geometry Based on the Topology of Abstract Cellular Complexes. In: Chassery, J.M., Francon, J., Montanvert, A., Réveillès, J.P., (eds.): Géometrie Discrète en Imagery, Fondements et Applications, Strasbourg, France, pp. 259–284 ( 1993)
Agoston, M.K.: Algebraic Topology, a first course. Pure and applied mathematics. Marcel Dekker Ed. (1976)
Allili, M., Mischaikow, K., Tannenbaum, A.: Cubical homology and the topological classification of 2d and 3d imagery. In: Proceedings of International Conference Image Processing. vol. 2, pp. 173–176 ( 2001)
Sonka, M., Hlavac, V., Boyle, R.: Image Processing, Analysis and Machine Vision. Brooks/Cole Publishing Company (1999)
Kaczynksi, T., Mischaikow, K., Mrozek, M.: Computational Homology. Springer, Heidelberg (2004)
Niethammer, M., Stein, A.N., Kalies, W.D., Pilarczyk, P., Mischaikow, K., Tannenbaum, A.: Analysis of blood vessels topology by cubical homology. In: Proceedings of International Conference Image Processing. vol. 2, pp. 969–972 ( 2002)
Damiand, G., Peltier, S., Fuchs, L.: Computing homology for surfaces with generalized maps: Application to 3d images. In: Bebis, G., Boyle, R., Parvin, B., Koracin, D., Remagnino, P., Nefian, A., Meenakshisundaram, G., Pascucci, V., Zara, J., Molineros, J., Theisel, H., Malzbender, T. (eds.) ISVC 2006. LNCS, vol. 4292, pp. 1151–1160. Springer, Heidelberg (2006)
Munkres, J.R.: Elements of algebraic topology. Perseus Books (1984)
Jolion, J.M., Rosenfeld, A.: A Pyramid Framework for Early Vision. Kluwer, Dordrecht (1994)
Meer, P.: Stochastic image pyramids. Computer Vision, Graphics, and Image Processing 45, 269–294 (1989) Also as UM CS TR-1871, June, 1987
Kropatsch, W.G.: Building irregular pyramids by dual graph contraction. IEE-Proc. Vision, Image and Signal Processing 142, 366–374 (1995)
Kannan, R., Bachem, A.: Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM Journal on Computing 8, 499–507 (1979)
Dumas, J.G., Heckenbach, F., Saunders, B.D., Welker, V.: Computing simplicial homology based on efficient smith normal form algorithms. In: Algebra, Geometry, and Software Systems, pp. 177–206 ( 2003)
Storjohann, A.: Near optimal algorithms for computing smith normal forms of integer matrices. In: Lakshman, Y.N. (ed.) Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, pp. 267–274. ACM Press, New York (1996)
Peltier, S., Alayrangues, S., Fuchs, L., Lachaud, J.O.: Computation of homology groups and generators. Computers and graphics 30, 62–69 (2006)
Kaczynski, T., Mrozek, M., Slusarek, M.: Homology computation by reduction of chain complexes. Computers & Math. Appl. 34, 59–70 (1998)
Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational Homology. Springer, Heidelberg (2004)
Damiand, G., Peltier, P., Fuchs, L., Lienhardt, P.: Topological map: An efficient tool to compute incrementally topological features on 3d images. In: Reulke, R., Eckardt, U., Flach, B., Knauer, U., Polthier, K. (eds.) IWCIA 2006. LNCS, vol. 4040, pp. 1–15. Springer, Heidelberg (2006)
Peltier, S., Ion, A., Haxhimusa, Y., Kropatsch, W.: Computing homology group generators of images using irregular graph pyramids. Technical Report PRIP-TR-111, Vienna University of Technology, Faculty of Informatics, Institute of Computer Aided Automation, Pattern Recognition and Image Processing Group (2007) http://www.prip.tuwien.ac.at/ftp/pub/publications/trs/
Haxhimusa, Y., Kropatsch, W.G.: Hierarchy of partitions with dual graph contraction. In: Michaelis, B., Krell, G. (eds.) Pattern Recognition. LNCS, vol. 2781, pp. 338–345. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Peltier, S., Ion, A., Haxhimusa, Y., Kropatsch, W.G., Damiand, G. (2007). Computing Homology Group Generators of Images Using Irregular Graph Pyramids. In: Escolano, F., Vento, M. (eds) Graph-Based Representations in Pattern Recognition. GbRPR 2007. Lecture Notes in Computer Science, vol 4538. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72903-7_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-72903-7_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72902-0
Online ISBN: 978-3-540-72903-7
eBook Packages: Computer ScienceComputer Science (R0)