# Fully Parallel Homological Region Adjacency Graph via Frontier Recognition
## 2 Related Work  
There are numerous works that represent images as neighborhood graphs. For example, nodes can represent pixels of the image, and edges the connection between adjacent pixels. If the 4-adjacency relation for pixels is considered, the topological information can be condensed into a graph, where regions will be represented by nodes, and edges are boundaries between regions. \(RAG\) representations are useful and intuitive models to be used for image segmentation problems, but, usually, difficult and complicated algorithms are required to manage \(RAG\) native graph structures. In this sense, working with edges or contours can produce enhanced image segmentations but with an efficiency that must be carefully analyzed because graph approaches are commonly impractical for large graphs [11]. On the other hand, although connected-component analysis (CCA) has been used in the last decade in many imaging applications (X-ray computed tomography, medical imaging, real-time automotive applications, etc. ), and parallel algorithms for them are appearing [12], our proposal here tries to go further by considering the complete set of adjacency relations among CCs. More complex representations have been developed to overcome the aforementioned \(RAG\) problems. For example, in dual graphs [13], images are represented by a pair of finite planar graphs that are dual to each other. These graphs allow the construction of a hierarchy of partitions (dual graph pyramids). Furthermore, processing these two graphs may not provide an efficient result; therefore, its application to real images has been quite limited. In [14], it was proved that a topologically consistent representation of an \(n\)-dimensional segmentation requires explicit representation of all cell types up to dimension \(n\). Combinatorial maps [15] are representations of an image as a set of half-edges, called darts, and two permutation functions. They store cells and their adjacencies and encode the topology of their embedding into 2D space. These maps have certain limitations: (a) they require a massive number of auxiliary darts, so they are not feasible for big images, and (b) they are difficult to manipulate. In this paper, we used the \(ACC\) representation [10], which needs significantly less storage and allows a \"smooth\" transference to adjacency graph representations [16]. It compiles numerous local and global topological statistics of the image at a cellular level that allow it to be analyzed from a probabilistic or fractal point of view [17]. Hence, the efficient construction of \(RAG\) is a rare topic in the literature, and it has usually been related to methods for computing max and min trees and other hierarchical representations. There is plenty in the literature dealing with homological tools applied to digital images (see, for instance, [18; 19; 20]). In this paper, we follow the principles and ideas provided by the Homological Spanning Forest (\(HSF\)) model of the image [21]. Using this parallel combinatorial technique, the processing of high-level segmentations can be solved through topological reductions in \(ACCs\) and leads to improved parallel processing to every \(n\)-dim cell and incidence of the image where computing time was near the logarithm of the width plus the height of the image. In this sense, another type of representation is the so-called \(CRIT\) (Contour Region Incidence Tree, [17]); that is, a topologically informative connectivity graph, extracted by compacting an image's \(ACC\) and whose 2-cells represent the image's constant color regions. The \(CRIT\) overcomes the previous difficulties of the \(RAG\) and is a topologically consistent representation, which is obtained using the previously mentioned Homological Spanning Forest (\(HSF\)). Other parallel algorithms for computing \(RAG\) information through the Homogeneous Spanning Forest model under an \(ACC\) scenario have been developed in [19; 22].