A parallel Homological Spanning Forest framework for 2D topological image analysis

• Published in: Pattern recognition letters 2016-11, Vol.83 (1), p.49-58
• Main Authors: Diaz-del-Rio, Fernando, Real, Pedro, Onchis, Darian M.
• Format: Article
• Language: English
• Subjects: 2D digital image; Algorithms; Combinatorial analysis; Computational algebraic topology; Computer simulation; Computers; Data structures; Digital imaging; Forests; Homological Spanning Forest; Homology; Image analysis; Image processing; Interrogation; Mathematical models; Object recognition; Parallel algorithm; Parallel processing; Pixels; Primal–dual abstract cell complex; Prototypes; Software; Symmetry; Topological analysis; Topology; Two dimensional analysis
• ISSN: 0167-8655; 1872-7344
• DOI: 10.1016/j.patrec.2016.07.023

•A framework for topological computation in a pre-segmented 2D digital image.•A new mathematical model for digital objects: primal–dual abstract cell complex.•It is oriented to maximize the degree of parallelization for parallel computers.•Algorithms avoid iterative and conditional sentences.•Complex data structures have been avoided to promote efficient parallelism. In [14], a topologically consistent framework to support parallel topological analysis and recognition for 2D digital objects was introduced. Based on this theoretical work, we focus on the problem of finding efficient algorithmic solutions for topological interrogation of a 2D digital object of interest D of a pre-segmented digital image I, using 4-adjacency between pixels of D. In order to maximize the degree of parallelization of the topological processes, we use as many elementary unit processing as pixels the image I has. The mathematical model underlying this framework is an appropriate extension of the classical concept of abstract cell complex: a primal–dual abstract cell complex (pACC for short). This versatile data structure encompasses the notion of Homological Spanning Forest fostered in [14,15]. Starting from a symmetric pACC associated with I, the modus operandi is to construct via combinatorial operations another asymmetric one presenting the maximal number of non-null primal elementary interactions between the cells of D. The fundamental topological tools have been transformed so as to promote an efficient parallel implementation in any parallel-oriented architecture (GPUs, multi-threaded computers, SIMD kernels and so on). A software prototype modeling such a parallel framework is built.