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

Abstract

In [14], a topologically consistent framework to support parallel topological analysis and recognition for2 D digital objects was introduced. Based on this theoretical work, we focus on the problem of findingefficient algorithmic solutions for topological interrogation of a 2 D 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 ofparallelization of the topological processes, we use as many elementary unit processing as pixels theimage I has. The mathematical model underlying this framework is an appropriate extension of the clas- sical concept of abstract cell complex: a primal–dual abstract cell complex (pACC for short). This versatiledata structure encompasses the notion of Homological Spanning Forest fostered in [14,15]. Starting froma symmetric pACC associated with I , the modus operandi is to construct via combinatorial operationsanother asymmetric one presenting the maximal number of non-null primal elementary interactions be- tween the cells of D . The fundamental topological tools have been transformed so as to promote anefficient 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.