An Optimized Union-Find Algorithm for Connected Components Labeling Using GPUs

Jun Chen, Qiang Yao, Houari Sabirin, Keisuke Nonaka, Hiroshi Sankoh, Sei Naito

Abstract

In this paper, we report an optimized union-find (UF) algorithm that can label the connected components on a 2D image efficiently by employing the GPU architecture. The proposed method contains three phases: UF-based local merge, boundary analysis, and link. The coarse labeling in local merge reduces the number atomic operations, while the boundary analysis only manages the pixels on the boundary of each block. Evaluation results showed that the proposed algorithm speed up the average running time by more than 1.3X.

Introduction

Connected Components Labeling (CCL) is a fundamental task in computer vision where pixels are grouped into "objects" based on their connectivity. While simple in theory, it remains a computational bottleneck for real-time systems such as motion detection or 3D shape measurement. The primary challenge lies in parallelization; traditional CPU algorithms are sequential, and GPU implementations often suffer from massive overhead when managing "label equivalence"—the process of realizing that different initial labels belong to the same object.

Existing GPU methods typically fall into two categories: "multi-pass" algorithms that iterate until convergence (often slow) or "one-pass" Union-Find (UF) methods that can become complex as label counts grow. This paper introduces an optimized UF approach designed to be leaner and faster by leveraging shared memory and reducing global synchronization requirements.

Methodology

The proposed algorithm optimizes the labeling process through three distinct phases:

1. Local UF Merge with Coarse Labeling

Instead of immediate global Union-Find, the algorithm first performs "coarse labeling" using row-column unification within small pixel blocks. This step is executed in shared memory, which is significantly faster than global memory. This pre-processing simplifies the label map and shortens the "chains" the algorithm must follow to find an object's root ID, effectively suppressing the path compression overhead.

Coarse labeling process using row and column scans to simplify local connectivity.

2. Boundary Analysis

To merge local blocks into a global map, traditional algorithms often inspect every pixel. This method optimizes global synchronization by only launching threads for pixels situated on the boundaries of the blocks. This transformation ensures that the problem scales with the perimeter of the blocks rather than the total number of pixels, drastically reducing the number of active CUDA threads required.

Boundary analysis phase where connectivity is determined by examining block edges.

The final phase utilizes the results from the boundary analysis to associate independent local label maps into a single, consistent global map.

Experimental Evaluation

The authors evaluated the algorithm on an NVIDIA GeForce GTX 1070 using standard benchmarks (Lena and Peppers) at resolutions ranging from $512 \times 512$ to $4096 \times 4096$.

  • Speedup: The proposed method outperformed all competitors, achieving approximately 5x faster performance than the Label Equivalence (LE) method and 3x faster performance than conventional parallel UF.
  • Scaling: Compared to the previous state-of-the-art (Line-based UF), the proposed method was consistently 1.3x faster. The performance gap widened as image resolution increased; for a $4096 \times 4096$ image, the algorithm processed "Lena" in just 3.36ms, compared to 18.64ms for the LE method.

Conclusion

By combining shared-memory coarse labeling with boundary-focused global merging, this optimized UF algorithm significantly reduces the computational cost of CCL on GPUs. While currently focused on 2D 4-connectivity, the efficiency gains make it highly suitable for real-time industrial inspection and live video analytics. Future work may involve extending these optimizations to 8-connectivity and 3D voxel data structures.

Summary updated

Abstract

In this paper, we report an optimized union-find (UF) algorithm that can label the connected components on a 2D image efficiently by employing the GPU architecture. The proposed method contains three phases: UF-based local merge, boundary analysis, and link. The coarse labeling in local merge reduces the number atomic operations, while the boundary analysis only manages the pixels on the boundary of each block. Evaluation results showed that the proposed algorithm speed up the average running time by more than 1.3X.
BibTeX
@misc{chen2017optimized,
  author = {Jun Chen and Qiang Yao and Houari Sabirin and Keisuke Nonaka and Hiroshi Sankoh and Sei Naito},
  title = {{An Optimized Union-Find Algorithm for Connected Components Labeling Using GPUs}},
  year = {2017},
  eprint = {1708.08180},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1708.08180},
}
Figure