Parallel homological calculus for 3D binary digital images

Abstract

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 (6, 26)-Homological Region Adjacency Tree ((6, 26)-Hom-Tree). This algorithm is based on a flexible graph scaffolding at the inter-voxel level called Homological Spanning Forest model (HSF). HomTrees are edge-weighted trees in which each node is a maximally connected set of constantvalue 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 EulerPoincaré 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 ID 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 ID has m1×m2×m3 voxels, the time complexity order of the reproducible algorithm is near O(log(m1+m2+m3)), 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.