# Fully Parallel Homological Region Adjacency Graph via Frontier Recognition
## 5 Parallel Algorithm for Computing the _HomDuRAG_
\(n_{\mathit{n_{\mathit{next}}}}=0\) number of homological representative cells (of 0D and 1D);_  
_for \(0-cells\), \(c\)do_  
_switch cross_type(\(c\))do_  
_/* \(\mathit{n_{\mathit{neigh}}},\mathit{n_{\mathit{inc}}},\mathit{n_{\mathit{ inc}}},\mathit{n_{\mathit{\mathit{\mathit{\mathit{\mathit{\mathit{\mathit{\mathit{\mathit{\mathit{\mathit{\mathit{\mathit{\mathit{\mathit{ \mathit{ \mathit{ \mathitmathitmathit{ \mathitmathitmathitmathitmathitmathitmathitmathitmathitmathit {      }}}}}}}}}}}}}}}}\) ** _/* _* _*Later on, the main loop (Steps 4 and 5 of Algorithm 1) iterates. Figure 9 depicts values for \(Ja\) at the end of two iterations: the first and last iterations (Iteration 5). During each iteration, jump distances are exponentially increased if no cross is reached. In our example and at the end of the first iteration, most 0-cells have doubled in distance (obvious for values, \(-2\), \(2\), \(-20\), and \(20\) and for \(-9\), \(9\), \(-11\), and \(11\) which mean that a row and column hop has been chosen). Only \(Ja\) (or \(Jb\), not shown here) remains with the same values (\(-1\), \(1\), \(-10\) or \(10\)) when it has already reached a cross. At the end of the loop, the \(Ja\) value for each 0-cell points towards the corresponding cross. Note that jumps to the other direction are stored in \(Jb\) (not shown here). The special case of a frontier cycle is solved as follows: the 0-cells that form the cycle have been exponentially increasing their \(Ja\); thus, they have cycled around the perimeter with uninteresting values. However, thanks to the propagation of the biggest labels (99 for the case of the cycle, see Figure 10), the loop finishes at Iteration 5 when each cell detects that its own label matches that of its pointed 0-cell. At last, note that any 0-cell that is not interior to a region has been set to one of the cross labels (15, 35, 65 or 85) or to the representative label 99 of the cycle (see Figure 10). On the other hand, colored cells correspond to 0-cells inside regions (thus, labeling has not been performed for them). Figure 8: **(Left)**: example values of the image in Figure 1 (K = 2, H = 4, L = 8, X = 9). **(Center,Right)**: initial \(Ja\) and \(Jb\) for the 0-cells of this image (orange cells represent crosses). Figure 7: Three cases showing how the jump distances of each 0-cell increase with each new iteration of the algorithm shown in Algorithm 1. Black circles numbered 1 and 2 represent crosses. Red arrows represent jumps in one direction and blue arrows in the opposite direction. **(Left)**: regular exponential increasing of jump distances. **(Center)**: reaching crosses. **(Right)**: when both jumps go to the same 0-cell, a cycle is detected in a frontier; then, no additional jump increase is required. Figure 9: Exponential growth of \(Ja\) values for the image in Figure 1. At the end, a new 0-cell representative of the hole is detected and marked in the bottom rightmost element. \(Jb\) presents values in a similar pattern but in opposite directions. (orange cells represent crosses)  
Implementation of the presented method is quite straightforward when following the diagram of the algorithm in Algorithm 1. Although an optimized code for the current proposal has not yet been written, the following theoretical estimation of the time complexity is \(O(log(M\times N))\) if massive parallelism were employed, \(M\) and \(N\) being the width and height of image \(I\), respectively. This is because the parallel algorithm for computing _HomDuRAG_ follows the same logarithmic procedure for pixel jump calculation as in previous works such as for the Connected Compmonent Label Tree (\(CCLT\)) algorithm [21]--exponentially increasing jump distances through the iterations until no new jumps are assigned. Hence, it is expected that computation time costs reach those which occurred in the case of the \(CCLT\).