Abstract: In combination of NVIDIA's Graphics Processing Unit (GPU) parallel architecture and hardware features under Compute Unified Device Architecture (CUDA) architecture, a new parallel labeling algorithm of connected domain was proposed for binary images. It effectively located the connected domain of the binary image and recorded its size at high speed, and significantly reduced the marking time. It recognized the connected domain through searching the minimum labeled pixel value in neighborhood. Because the processing sequence of each pixel is not in particular order and independent from each other, it can be dealt in parallel. The calculation efficiency of the algorithm is independent of the shapes and the quantity of the connected regions, and the algorithm has good robustness. The experimental results show that the algorithm fully plays the parallel processing capability of GPU, and can get a more than 300 times speedup than general algorithm based on CPU and 17 times speedup than OpenCV function (CPU) in processing high-resolution images and multi-connected-domain images.

Key words: GPU acceleration, connected-domain labeling, parallelization, Compute Unified Device Architecture (CUDA), 8-neighborhood

摘要： 结合NVIDIA公司统一计算设备架构(CUDA)下的图形处理器(GPU)并行结构和硬件特点，提出了一种新的二值图像连通域标记并行算法，高速有效地标识出了二值图的连通域位置及大小，大幅缩减了标记时间耗费。该算法通过搜索邻域内最小标号值的像素点对连通域进行标记，各像素点处理顺序不分先后并且不相互依赖,因此可以并行执行。算法效率不受连通域形状及数量的影响，具有很好的鲁棒性。实验结果表明，该并行算法充分发挥了GPU并行处理能力，在处理高分辨率与多连通域图像时效率为一般CPU标记算法的300倍，比OpenCV的优化函数(CPU)效率高近17倍。

关键词: GPU加速, 连通域标记, 并行化, 统一计算设备架构, 8邻域