×

Decomposing cavities in digital volumes into products of cycles. (English) Zbl 1261.68146

Brlek, Srečko (ed.) et al., Discrete geometry for computer imagery. 15th IAPR international conference, DGCI 2009, Montréal, Canada, September 30 – October 2, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-04396-3/pbk). Lecture Notes in Computer Science 5810, 263-274 (2009).
Summary: The homology of binary 3-dimensional digital images (digital volumes) provides concise algebraic description of their topology in terms of connected components, tunnels and cavities. Homology generators corresponding to these features are represented by nontrivial 0-cycles, 1-cycles and 2-cycles, respectively. In the framework of cubical representation of digital volumes with the topology that corresponds to the 26-connectivity between voxels, we introduce a method for algorithmic computation of a coproduct operation that can be used to decompose 2-cycles into products of 1-cycles (possibly trivial). This coproduct provides means of classifying different kinds of cavities; in particular, it allows to distinguish certain homotopically non-equivalent spaces that have isomorphic homology. We define this coproduct at the level of a cubical complex built directly upon voxels of the digital image, and we construct it by means of the classical Alexander-Whitney map on a simplicial subdivision of faces of the voxels.
For the entire collection see [Zbl 1176.68004].

MSC:

68U10 Computing methodologies for image processing
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

CAPD
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Delfinado, C., Edelsbrunner, H.: An incremental algorithm for Betti numbers of simplicial complexes on the 3–sphere. Comput. Aided Geom. Design 12, 771–784 (1995) · Zbl 0873.55007 · doi:10.1016/0167-8396(95)00016-Y
[2] Dey, T., Guha, S.: Computing homology groups of simplicial complexes in \(\mathbb{R}\)3. Journal of the ACM 45(2), 266–287 (1998) · Zbl 0904.68117 · doi:10.1145/274787.274810
[3] González-Diaz, R., Jiménez, M., Medrano, B., Molina-Abril, H., Real, P.: Integral operators for computing homology generators at any dimension. In: Ruiz-Shulcloper, J., Kropatsch, W.G. (eds.) CIARP 2008. LNCS, vol. 5197, pp. 356–363. Springer, Heidelberg (2008) · Zbl 05376136 · doi:10.1007/978-3-540-85920-8_44
[4] González-Diaz, R., Real, P.: On the cohomology of 3d digital images. Discrete Applied Math. 147, 245–263 (2005) · Zbl 1099.68120 · doi:10.1016/j.dam.2004.09.014
[5] Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational homology. Applied Mathematical Sciences (2004) · Zbl 1039.55001 · doi:10.1007/b97315
[6] Mischaikow, K., Mrozek, M., Pilarczyk, P.: Graph approach to the computation of the homology of continuous maps. Foundations of Computational Mathematics 5(2), 199–229 (2005) · Zbl 1104.55001 · doi:10.1007/s10208-004-0125-2
[7] Molina-Abril, H., Real, P.: Cell at-models for digital volumes. In: Torsello, A., Escolano, F., Brun, L. (eds.) GbRPR 2009. LNCS, vol. 5534, pp. 314–323. Springer, Heidelberg (2009) · Zbl 1180.68002 · doi:10.1007/978-3-642-11447-2
[8] Mrozek, M., Pilarczyk, P., \.Zelazna, N.: Homology algorithm based on acyclic subspace. Computers and Mathematics with Applications 55, 2395–2412 (2008) · Zbl 1142.15300 · doi:10.1016/j.camwa.2007.08.044
[9] Peltier, S., Alayrangues, S., Fuchs, L., Lachaud, J.: Computation of homology groups and generators. Computer & Graphics 30(1), 62–69 (2006) · Zbl 1119.68209 · doi:10.1016/j.cag.2005.10.011
[10] Computational Homology Project, http://chomp.rutgers.edu/
[11] Gameiro, M., Mischaikow, K., Kalies, W.: Topological Characterization of Spatial-Temporal Chaos. Physical Review E 70 3 (2004) · doi:10.1103/PhysRevE.70.035203
[12] Gameiro, M., Pilarczyk, P.: Automatic homology computation with application to pattern classification. RIMS Kokyuroku Bessatsu B3, 1–10 (2007) · Zbl 1213.35086
[13] Krishan, K., Gameiro, M., Mischaikow, K., Schatz, M., Kurtuldu, H., Madruga, S.: Homology and symmetry breaking in Rayleigh-Bénard convection: Experiments and simulations. Physics of Fluids 19, 117105 (2007) · Zbl 1182.76403 · doi:10.1063/1.2800365
[14] Niethammer, M., Stein, A., Kalies, W., Pilarczyk, P., Mischaikow, K., Tannenbaum, A.: Analysis of blood vessel topology by cubical homology. In: Proc. of the International Conference on Image Processing, vol. 2, pp. 969–972 (2002) · doi:10.1109/ICIP.2002.1040114
[15] \.Zelawski, M.: Pattern recognition based on homology theory. Machine Graphics and Vision 14, 309–324 (2005)
[16] Serre, J.: Homologie singulière des espaces fibrés, applications. Annals of Math. 54, 429–505 (1951) · Zbl 0045.26003 · doi:10.2307/1969485
[17] Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2001) · Zbl 1044.55001
[18] Eilenberg, S., Mac Lane, S.: On the groups h({\(\pi\)},n), i, ii, iii. Annals of Math. 58, 60, 60, 55–106,48–139, 513–557 (1953, 1954) · Zbl 0050.39304 · doi:10.2307/1969820
[19] Sergeraert, F.: The computability problem in algebraic topology. Advances in Mathematics 104, 1–29 (1994) · Zbl 0823.55011 · doi:10.1006/aima.1994.1018
[20] Barnes, D.W., Lambe, L.A.: A fixed point approach to homological perturbation theory. Proc. Amer. Math. Soc. 112, 881–892 (1991) · Zbl 0742.55010 · doi:10.1090/S0002-9939-1991-1057939-0
[21] Forman, R.: A Discrete Morse Theory for Cell Complexes. In: Yau, S.T. (ed.) Topology and Physics for Raoul Bott. International Press (1995) · Zbl 0867.57018
[22] Molina-Abril, H., Real, P.: Advanced homological information on 3d digital volumes. In: da Vitoria Lobo, N., Kasparis, T., Roli, F., Kwok, J.T., Georgiopoulos, M., Anagnostopoulos, G.C., Loog, M. (eds.) S+SSPR 2008. LNCS, vol. 5342, pp. 361–371. Springer, Heidelberg (2008) · Zbl 05487445 · doi:10.1007/978-3-540-89689-0_40
[23] González-Diaz, R., Medrano, B., Real, P., Sanchez-Pelaez, J.: Algebraic topological analysis of time-sequence of digital images. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) CASC 2005. LNCS, vol. 3718, pp. 208–219. Springer, Heidelberg (2005) · Zbl 1169.68642 · doi:10.1007/11555964_18
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.