Parallel homological calculus for 3D binary digital images. (English) Zbl 1539.68352
Summary: Topological representations of binary digital images usually take into consideration different adjacency types between colors. Within the cubical-voxel 3D binary image context, we design an algorithm for computing the isotopic model of an image, called \((\mathbf{6}, \mathbf{26})\)-Homological Region Adjacency Tree (\((\mathbf{6}, \mathbf{26})\)-Hom-Tree). This algorithm is based on a flexible graph scaffolding at the inter-voxel level called Homological Spanning Forest model (HSF). Hom-Trees are edge-weighted trees in which each node is a maximally connected set of constant-value voxels, which is interpreted as a subtree of the HSF. This representation integrates and relates the homological information (connected components, tunnels and cavities) of the maximally connected regions of constant color using 6-adjacency and 26-adjacency for black and white voxels, respectively (the criteria most commonly used for 3D images). The Euler-Poincaré numbers (which may as well be computed by counting the number of cells of each dimension on a cubical complex) and the connected component labeling of the foreground and background of a given image can also be straightforwardly computed from its Hom-Trees. Being \(I_D\) a 3D binary well-composed image (where \(D\) is the set of black voxels), an almost fully parallel algorithm for constructing the Hom-Tree via HSF computation is implemented and tested here. If \(I_D\) has \(m_1 \times m_2 \times m_3\) voxels, the time complexity order of the reproducible algorithm is near \(O(\log (m_1 +m_2 +m_3))\), under the assumption that a processing element is available for each cubical voxel. Strategies for using the compressed information of the Hom-Tree representation to distinguish two topologically different images having the same homological information (Betti numbers) are discussed here. The topological discriminatory power of the Hom-Tree and the low time complexity order of the proposed implementation guarantee its usability within machine learning methods for the classification and comparison of natural 3D images.
MSC:
| 68U10 | Computing methodologies for image processing |
| 55N31 | Persistent homology and applications, topological data analysis |
| 68U03 | Computational aspects of digital topology |
Keywords:
3D digital images; binary images; parallel computing; cavity; connected component; homological spanning forest; inter-voxel; homological region adjacency treeSoftware:
ChainConReferences:
| [1] | Hensel, F.; Moor, M.; Rieck, B., A survey of topological machine learning methods, Front. Artif. Intell., 4, 52 (2021) · doi:10.3389/frai.2021.681108 |
| [2] | Pun, CS; Lee, SX; Xia, K., Persistent-homology-based machine learning: a survey and a comparative study (2022), Rev: Artif. Intell, Rev |
| [3] | Sanfeliu, A.; Alquézar, R.; Andrade, J.; Climent, J.; Serratosa, F.; Vergés, J., Graph-based representations and techniques for image processing and image analysis, Pattern Recognit., 35, 3, 639-650 (2002) · Zbl 1009.68178 · doi:10.1016/S0031-3203(01)00066-8 |
| [4] | Klette, R.: Cell complexes through time. In: Vision Geometry IX, SPIE, vol. 4117, pp. 134-145. (2000) |
| [5] | Pavlidis, T., Structural pattern recognition (1977), New York: Springer-Verlag, New York · Zbl 0382.68071 · doi:10.1007/978-3-642-88304-0 |
| [6] | Rosenfeld, A., Adjacency in digital pictures, Inf. Control, 26, 1, 24-33 (1974) · Zbl 0284.68072 · doi:10.1016/S0019-9958(74)90696-2 |
| [7] | Serra, J., Image analysis and mathematical morphology (1982), Acad: Press, Acad · Zbl 0565.92001 |
| [8] | Real, P., Molina-Abril, H., Díaz-del-Río, F., Blanco-Trejo, S.: Homological region adjacency tree for a 3D binary digital image via HSF model. In: Int. Conf. CAIP19, pp. 375-287. Springer, Cham (2019) |
| [9] | Molina-Abril, H.; Real, P., Homological spanning forest framework for 2D image analysis, Ann. Math. Art. Int., 64, 4, 385-409 (2012) · Zbl 1270.55005 · doi:10.1007/s10472-012-9297-7 |
| [10] | Molina-Abril, H.; Real, P.; Nakamura, A.; Klette, R., Connectivity calculus of fractal polyhedrons, Pattern Recognit., 48, 4, 1150-1160 (2015) · Zbl 1374.68668 · doi:10.1016/j.patcog.2014.05.016 |
| [11] | Latecki, LJ, 3d well-composed pictures, Graphical Models and Image Processing., 59, 3, 164-172 (1997) · doi:10.1006/gmip.1997.0422 |
| [12] | Cerman, M.; Janusch, I.; González-Díaz, R.; Kropatsch, WG, Topology-based image segmentation using LBP pyramids, Mach. Vis. Appl., 27, 8, 1161-1174 (2016) · doi:10.1007/s00138-016-0795-1 |
| [13] | Delgado-Friedrichs, O.; Robins, V.; Sheppard, A., Skeletonization and partitioning of digital images using discrete morse theory, IEEE Trans. Pattern Anal Mach Intell., 37, 3, 654-666 (2015) · doi:10.1109/TPAMI.2014.2346172 |
| [14] | Damiand, G.; Lienhardt, P., Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing (2014), Boca Ratón: CRC Press, Boca Ratón · Zbl 1305.68012 · doi:10.1201/b17403 |
| [15] | Abrams, L.; Fishkind, DE, The genus of a digital image boundary is determined by its foreground, background, and reeb graphs, Discret. Comput. Geom., 37, 4, 629-640 (2007) · Zbl 1124.94001 · doi:10.1007/s00454-007-1315-x |
| [16] | Bertrand, G., Simple points, topological numbers and geodesic neighborhoods in cubic grids, Pat. Rec. Let., 35, 1003-1011 (1994) · doi:10.1016/0167-8655(94)90032-9 |
| [17] | Klette, R.: Skeletons in digital image processing. Glen Innes: Comput. Sci. Dept. University of Auckland 21 (2002) |
| [18] | Diaz-del-Rio, F., Real, P., Onchis, D.M.: A parallel homological spanning forest framework for 2D topological image analysis. Pat. Rec. Let. 49-58 (2016) |
| [19] | Diaz-del-Rio, F.; Sanchez-Cuevas, P.; Molina-Abril, H.; Real, P., Parallel connected-component-labeling based on homotopy trees, Pat. Rec. Let., 131, 71-78 (2020) · doi:10.1016/j.patrec.2019.11.039 |
| [20] | Romero, A.; Rubio, J.; Sergeraert, F., Effective homology of filtered digital images, Pat. Rec. Let., 83, 23-31 (2016) · doi:10.1016/j.patrec.2016.01.023 |
| [21] | González-Díaz, R.; Real, P., On the cohomology of 3D digital images, Discret. Appl. Math., 147, 2-3, 245-263 (2005) · Zbl 1099.68120 · doi:10.1016/j.dam.2004.09.014 |
| [22] | Pilarczyk, P.; Real, P., Computation of cubical homology, (co)homology and (co)homological operations via chain contractions, Adv. Comput. Math., 41, 1, 253-275 (2015) · Zbl 1312.55005 · doi:10.1007/s10444-014-9356-1 |
| [23] | Delgado-Friedrichs, O., Robins, V., Sheppard, A.: Morse theory and persistent homology for topological analysis of 3D images of complex materials. IEEE Int. Conf. Image Process. (ICIP) 4872-4876 (2014) |
| [24] | Chung, YM; Day, S., Topological fidelity and image thresholding: A persistent homology approach, J. Math. Imaging Vision, 60, 7, 1167-1179 (2018) · Zbl 1433.68510 · doi:10.1007/s10851-018-0802-4 |
| [25] | Kong, TY; Rosenfeld, A., Digital topology: Introduction and survey, Comput. Vision Graphics Image Process., 48, 3, 357-393 (1989) · doi:10.1016/0734-189X(89)90147-3 |
| [26] | Kong, T.Y., Roscoe, A.W., Rosenfeld, A.: Concepts of digital topology. Topol. Appl. 219-262 (1992) · Zbl 0780.57008 |
| [27] | Khachan, M.; Chenin, HP, Deddi: Polyhedral representation and adjacency graph in n-dimensional digital images, Comput. Vision Image Underst., 79, 3, 428-441 (2000) · Zbl 1010.68547 · doi:10.1006/cviu.2000.0859 |
| [28] | Kovalevsky, V., Modern Algorithms for Image Processing: Computer Imagery by Example Using C (2018), New York: Apress, New York |
| [29] | Gray, SB, Local properties of binary images in two and three dimensions, IEEE Trans. Comput., 20, 5, 551-561 (1970) · Zbl 0216.50101 · doi:10.1109/T-C.1971.223289 |
| [30] | Lee, C.N., Rosenfeld, A.: Computing the euler number of a 3d image. Proc. IEEE First Int. Conf. Comput. Vision 567-571 (1987) |
| [31] | Munkres, JR, Elements of Algebraic Topology (1984), California: Addison Wesley, California · Zbl 0673.55001 |
| [32] | Kovalevsky, V.: Algorithms in digital geometry based on cellular topology. 10th IWCIA, Springer, Berlin Heidelberg 3322, 366-393 (2004) · Zbl 1113.68589 |
| [33] | Lundell, AT; Weingram, S., The Topology of CW-complexes (1969), Springer, New York: Van Nostrand Reinhold, Springer, New York · Zbl 0207.21704 · doi:10.1007/978-1-4684-6254-8 |
| [34] | Real, P., Díaz-del-Río, F., Onchis, D.: Toward parallel computation of dense homotopy skeletons for nD digital objects. Combinatorial Image Analysis. IWCIA 2017. LNCS. 10256 (2017) · Zbl 1486.68197 |
| [35] | Forman, R., Morse theory for cell complexes, Adv. Math., 134, 90-145 (1998) · Zbl 0896.57023 · doi:10.1006/aima.1997.1650 |
| [36] | Komura, Y., GPU based cluster-labeling algorithm without the use of conventional iteration: Application to the Swendsen-Wang multi-cluster spin flip algorithm, Comput. Phys. Commun., 194, 54-58 (2015) · doi:10.1016/j.cpc.2015.04.015 |
| [37] | Díaz-del-Río, F., Blanco-Trejo, S., Real, P., Molina-Abril, H., Onchis, D.: HSF and Hom-Tree of 3D images. https://www.mathworks.com/matlabcentral/fileexchange/80503-hsf-and-hom-tree-of-3d-images. Accessed March 25, 2022 (2022) |
| [38] | Gonzalez-Lorenzo, A.; Bac, A.; Mari, J-L; Baudrier, É.; Naegel, B.; Krähenbühl, A.; Tajine, M., A heuristic for short homology basis of digital objects, Discrete Geometry and Mathematical Morphology, 60-70 (2022), Cham: Springer, Cham · Zbl 1522.68618 · doi:10.1007/978-3-031-19897-7_6 |
| [39] | Bukkuri, A.; Andor, N.; Darcy, IK, Applications of topological data analysis in oncology, Front. Arti. Intell., 4, 38 (2021) |
| [40] | Molina-Abril, H.; Real, P.; Díaz-del-Río, F., Generating (co) homological information using boundary scale, Pat. Rec. Let., 133, 240-246 (2000) · doi:10.1016/j.patrec.2020.02.028 |
| [41] | Díaz-del-Río, F.; Sánchez-Cuevas, P.; Molina-Abril, H.; Real, P., Parallel connected-component-labeling based on homotopy trees, Pat. Rec. Let., 131, 71-78 (2000) · doi:10.1016/j.patrec.2019.11.039 |
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.
