The parallel version of the union-find algorithm [1]} is presented by Oliveria et al. [2]}.
They executed two merges successively, local merge and global merge, to overcome the drawback that it may need to follow a long path to reach the root of two connected pixels.
Although this algorithm outperforms most of the pixel-based CCL algorithms because all the kernels are spawned once, searching for the root of a specific pixel is computationally heavy.
Stava et al. [3]} designed a solution in the similar manner.
In the local merge stage, they improved the label-equivalence algorithm by implementing all iterations inside the kernel, such that no synchronization between host and device is required.
In the global merge stage, they use the connectivity between all border elements of two neighboring blocks to merge their equivalence lists.
It is necessary to perform the operations of global merge several times to guarantee that all equivalence lists are merged.
Kumar et al. [4]} implemented the CCL algorithm using a divide and conquer technique [5]} on CUDA that solves the local connection using the Floyd-Warshall algorithm [6]} and merges blocks by considering three different cases.
Here, the various processing approaches for the three cases leads to thread divergence thus limiting the performance.
