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

2017/08/28 by Jun Chen, Chen, Jun, Qiang Yao +9
Computer Science · #Computer Vision and Pattern Recognition (cs.CV) #Digital Image Processing Techniques #FOS: Computer and information sciences #Image and Object Detection Techniques #Medical Image Segmentation Techniques #cs.CV

paper · pdf · doi:10.48550/arxiv.1708.08180

openalex publication_date 2017/08/28 · arxiv created 2017/08/29 · arxiv updated 2017/08/30 · openalex created_date 2017/09/25 · openalex updated_date 2026/07/28

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.

Related

• Efficient Parallel Connected Components Labeling with a Coarse-to-fine Strategy
• Adaptive Work-Efficient Connected Components on the GPU
• A generalized GPU-based connected component labeling algorithm
• A New Run-based Connected Component Labeling for Efficiently Analyzing and Processing Holes
• Computation of gray-level co-occurrence matrix based on CUDA and its optimization