A generalized GPU-based connected component labeling algorithm

2016/03/28 by Yukihiro Komura, Komura, Yukihiro
Computer Science · Physics and Astronomy · #Computational Physics (physics.comp-ph) #Digital Image Processing Techniques #FOS: Physical sciences #Theoretical and Computational Physics #Topological and Geometric Data Analysis #physics.comp-ph

paper · pdf · doi:10.48550/arxiv.1603.08357

arxiv created 2016/03/28 · openalex publication_date 2016/03/28 · arxiv updated 2016/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose a generalized GPU-based connected component labeling (CCL) algorithm that can be applied to both various lattices and to non-lattice environments in a uniform fashion. We extend our recent GPU-based CCL algorithm without the use of conventional iteration to the generalized method. As an application of this algorithm, we deal with the bond percolation problem. We investigate bond percolation on the honeycomb and triangle lattices to confirm the correctness of this algorithm. Moreover, we deal with bond percolation on the Bethe lattice as a substitute for a network structure, and demonstrate the performance of this algorithm on those lattices.

Related

• Simple Concurrent Labeling Algorithms for Connected Components
• Efficient Parallel Connected Components Labeling with a Coarse-to-fine Strategy
• An Optimized Union-Find Algorithm for Connected Components Labeling Using GPUs
• A New Run-based Connected Component Labeling for Efficiently Analyzing and Processing Holes
• Optimal component labeling algorithms for mesh-connected computers and VLSI