连通分量标记（CCL），又称连通分量分析、团块提取、区域标记或团块发现，是图论的一种算法应用，其中连通分量的子集根据给定的启发式规则被唯一标记。它用于计算机视觉中检测二值数字图像中的连通区域，尽管彩色图像和高维数据也可以处理。CCL与图像分割不同，团块提取与团块检测相关但有所区别。
在实践中，CCL作用于根据输入数据构建的图，其中顶点表示像素或元素，边表示相邻点之间的连通性。算法遍历图，根据连通性和相对值给顶点分配标签。标记后，图可以被划分为子集，从而允许恢复和处理原始信息，用于计数、过滤和跟踪团块等任务。
定义与术语
术语“连通分量标记”在学术文献中一致使用，而“连通分量分析”（CCA）在术语和问题定义上都有所不同。Rosenfeld等人将CCL定义为创建标记图像，其中与二值输入图像同一连通分量相关联的位置具有唯一标签。Shapiro等人将CCL描述为一种算子，其输入是二值图像，输出是符号图像，其中每个像素的标签是唯一标识其连通分量的整数。
关于CCA的定义没有共识；它经常与CCL互换使用。Shapiro等人更广泛的定义指出，CCA包括黑色像素的连通分量标记，随后对分量区域进行属性测量和决策。本文采用更广泛的解释，融合了这些观点。
图构建与连通性
根据相关输入数据构建图，顶点包含比较启发式所需的信息，边表示相邻点的连通性。算法遍历图，根据连通性和相对值标记顶点。连通性由介质决定；对于图像图，常见邻域包括4连通（北、南、东、西）和8连通（包括对角线）。
标记后，图可以被划分为子集，之后可以恢复和处理原始信息。这种方法推广到任意维度，但时间和空间复杂度相应增加。
一次一个分量算法
一次一个分量算法快速、实现简单，基于图遍历方法。它是Vincent和Soille的分水岭分割算法的一部分，也有其他实现。该方法使用链表来保存连通像素的索引，深度优先或广度优先搜索的选择对此应用没有实际区别。
该算法假设二值图像具有前景和背景像素，旨在标记前景中的连通分量。步骤：
- 从第一个像素开始，将当前标签设为1。
- 如果像素是前景且未标记，则分配当前标签并将其添加到队列；否则，移动到下一个像素。
- 从队列中弹出一个元素，检查其邻居（基于连通性类型）。如果邻居是前景且未标记，则分配当前标签并将其添加到队列。重复直到队列为空。
- 移动到下一个像素并递增当前标签。
像素在入队前被标记，每个前景像素的邻居只检查一次；背景像素的邻居不被检查。伪代码使用两个队列来管理像素处理，确保高效遍历。
计算机视觉中的应用
CCL广泛用于计算机视觉中检测二值图像中的连通区域，通常在阈值化步骤之后。团块提取也可以应用于灰度图像和彩色图像。团块可以被计数、过滤和跟踪，使CCL在图像识别系统和人机交互界面中具有价值。
例如，在Machine learning流程中，CCL可以预处理图像以用于目标检测或分割任务，补充U-Net架构等技术。它也用于Artificial intelligence系统中分析医学图像、工业检测和自动驾驶，其中识别连通区域至关重要。
相关概念与扩展
CCL与团块检测相关但不同，后者侧重于基于强度变化识别感兴趣区域。相比之下，CCL基于连通性标记所有连通分量。该算法可以扩展到高维数据，如医学成像中的3D体积，但计算成本增加。
Deep learning和Neural network模型的最新进展导致了学习型分割方法，但CCL仍然是后处理和分析的基本工具。其简单性和效率使其成为计算机视觉库和框架中的常用工具，通常与Data Augmentation和Loss Functions在训练流程中结合使用。
参见
- 计算机视觉
- 图像分割
- 团块检测
- 图论