GPU加速连通组件标记算法的全面综述与性能评估：二十年研究进展与代码实现

《IEEE Transactions on Parallel and Distributed Systems》：A State-of-the-Art Review with Code about Connected Components Labeling on GPUs

为解决GPU上连通组件标记（CCL）算法性能优化问题，研究人员系统回顾了过去二十年的GPU加速CCL算法，通过YACCLAB基准测试平台对多种算法进行多环境评估。研究发现基于块处理的算法（如BKE、BUF）在2D图像和3D体积数据上均表现最优，该研究为图像处理领域提供了可复现的算法比较框架，对医学影像分析和计算机视觉应用具有重要意义。

　　

在计算机视觉和图像处理领域，连通组件标记（Connected Components Labeling, CCL）作为基础算法扮演着关键角色。从医学影像分析到文档数字化，从目标跟踪到工业检测，CCL都是提取和分析图像中独立对象的核心步骤。随着图像数据量的爆炸式增长和实时处理需求的提升，传统的CPU串行算法已难以满足现代应用对效率的要求。

尽管CCL任务的结果具有确定性——给定输入图像和连通性定义后，输出是唯一的——但不同算法在执行时间和内存需求上存在显著差异。特别是在处理复杂几何形状的对象时，CCL的计算复杂度远高于其他二值图像操作。更关键的是，标记过程无法通过纯粹的并行局部操作完成，本质上包含顺序处理环节，这为GPU并行化带来了独特挑战。

研究人员针对这一难题开展了系统性的研究，对过去二十年提出的GPU加速CCL算法进行了全面回顾。研究团队通过创新的YACCLAB（Yet Another Connected Components LAbeling Benchmark）基准测试平台，首次实现了多种算法在统一框架下的公平比较。该研究不仅提供了详细的算法分类和理论分析，还公开了所有算法的源代码，确保了研究的可复现性。

关键技术方法包括：1）基于联合查找（union-find）数据结构的标签等价解决机制；2）块处理（block-based）方法，将2×2像素块作为处理单元；3）迭代与直接算法的优化策略；4）针对不同连通性（4-连通、8-连通、26-连通）的专用算法设计。研究团队在多个实验环境（包括不同操作系统、编译器和GPU架构）下测试了算法性能，使用了真实场景图像和合成数据集进行评估。

算法分类与描述

研究将GPU CCL算法分为迭代算法和直接算法两大类。迭代算法如邻域传播（NP）、局部邻域传播（LNP）等需要多次运行内核直至收敛，而直接算法如联合查找（UF）、块等价（BE）等通过固定次数的内核调用完成标记。研究还按最小处理单元将算法分为像素基、行程基和块基算法，其中块基算法通过处理2×2像素块显著减少了内存访问次数。

评估方法与数据集

研究采用YACCLAB基准测试系统，包含2D图像（3DPeS、指纹、医疗、MIRflickr、Tobacco800、XDOCS）和3D体积（OASIS、线粒体、Hilbert曲线）等多类数据集。测试涵盖不同前景密度（0%-100%）和粒度（1-16）的合成图像，全面评估算法在各种场景下的性能表现。

性能分析结果

实验结果显示，基于块处理的算法BKE（Block-based Komura Equivalence）和BUF（Block-based Union-Find）在大多数测试场景中表现最优。在2D图像处理上，BKE在OpenCV库中已有实现；在3D体积数据上，BUF因更适应复杂拓扑结构而表现更佳。研究还发现内存分配时间占总执行时间的显著部分，建议在嵌入式应用中尽量避免动态内存分配。

粒度测试分析

通过变化前景密度和粒度的测试发现，当密度低于10%或高于90%时，基于决策树的算法（C_SAUF、C_BBDT、C_DRAG）因分支发散减少而性能接近最优。而在密度50%左右时，这些算法因线程执行路径不统一而性能下降。块基算法在不同密度下都保持稳定性能，证明了其鲁棒性。

环境因素影响

研究在多种硬件配置（NVIDIA Quadro K2200、P1000、A100）和操作系统（Windows、Linux）下测试算法，发现不同GPU架构间性能差异可达数量级，但算法相对排名保持稳定。操作系统主要影响内存分配效率，而不改变算法间的性能关系。

研究结论强调，基于块处理的CCL算法在当前GPU架构上具有明显优势，特别是BKE和BUF算法在各自适用场景下表现卓越。该研究为CCL算法的选择和应用提供了实践指导，推动了可复现研究在图像处理领域的发展。未来工作将聚焦于连通组件分析（CCA）的集成优化以及在嵌入式系统上的算法适配。