写在前头
做图像处理的人，几乎都会撞上同一个问题：二值图上那么多白色区域，到底哪几个像素算“同一个目标”？细胞计数要把粘连的细胞一个个数出来，PCB缺陷检测要把划痕和污点分开，OCR要先找到每个字符的独立区域。这些场景背后都躲着同一个经典算法——连通域标记。说它是图像分析的地基毫不夸张，二值图一旦完成了连通域标记，目标的个数、位置、大小、形状全部都能顺手算出来。
这篇文章我打算从邻域定义开始，把连通域标记的数学本质讲清楚，再手撕两遍扫描算法和并查集合并逻辑，最后聊聊种子填充的另一条路线和特征提取公式。整个过程会带上可直接套用的公式、伪代码、以及我在实际项目里踩过的坑。适合刚接触图像处理的学生，也适合需要把算法落地到工程项目的开发者。
1. 像素之间的“关系”：4邻域与8邻域到底差在哪里
1.1 连通域标记到底在解决什么问题
先忘掉那些花哨的深度学习词汇。连通域标记（Connected Component Labeling，CCL）处理的对象通常是一幅二值图：前景像素是1，背景像素是0。我们的任务是把所有值为1且彼此连通的像素归为同一个集合，然后给每个集合分配一个独一无二的编号。
听起来像废话，但“彼此连通”这四个字在数学上有严格定义。两个像素是不是连在一起，取决于你采用哪种邻域规则。同一个图上，用不同规则标记，结果可能完全不一样。我见过不少同学在这个细节上翻车——不是不理解规则，而是没意识到规则选择会直接影响后续计算的物理意义。
举个例子：你在做细胞计数，两个细胞挨得非常近，中间只隔一个像素。如果你用4邻域，它俩是分开的两个目标；如果用8邻域，它俩可能就被吞并成一个目标。没有哪个规则是绝对正确的，关键看你的业务场景更接受哪种误差。
1.2 邻域集合的数学定义
设当前像素为 p = (x, y)，那么：
4邻域：
N4(p) = {(x+1, y), (x-1, y), (x, y+1), (x, y-1)}
也就是上下左右四个方向。
8邻域：
N8(p) = N4(p) ∪ {(x+1, y+1), (x+1, y-1), (x-1, y+1), (x-1, y-1)}
也就是在4邻域的基础上再加四个对角方向。
用生活化的方式理解：4邻域像十字路口，只有四个方向能走；8邻域像广场空地，斜着也能穿过去。二值图中一个前景像素的“势力范围”，就在这两种邻域之间二选一。
基于邻域定义，我们可以给出连通域的形式化描述：一个前景像素集合 S 是连通分量，当且仅当 S 内任意两个像素 p 和 q，都存在一条像素序列 p = p0, p1, ..., pk = q，其中每个相邻像素对都满足前后两个像素互为邻域关系。这条序列本质上就是一条“路径”，而路径的存在性构成了像素之间的等价关系。
1.3 连通性是一种等价关系
数学上有个非常关键的性质：在同一个邻域规则下，“存在连通路径”这个关系满足三个条件——自反性（自己和自己连通）、对称性（p 连通 q 则 q 连通 p）、传递性（p 连通 q，q 连通 r，则 p 连通 r）。满足这三个条件的关系叫等价关系，等价关系会把像素集合划分成互不相交的等价类，每个等价类恰好就是一个连通域。
我一直认为，理解这一点是理解整个连通域标记算法的钥匙。算法无论如何设计，本质上都是在做一件事：把像素划分进等价类。两遍扫描用等价表，并查集用树结构，种子填充用搜索扩散，它们只是等价关系不同实现路径的具象化。
如果图像尺寸很大，或者对实时性要求高，邻域规则需要早早在代码里定好，并且写清楚注释。我处理数据时通常这样约定：目标边界允许斜向连接时选8邻域，需要严格区分目标间距时选4邻域。没有统一标准，但一旦选好就全局固定，绝不在处理中途更换。
2. 两遍扫描算法：为什么需要“等价表”和“第二次扫描”
2.1 第一遍：临时标签与冲突检测
两遍扫描是连通域标记最经典的实现方案，也是多数图像处理库内部采用的基础策略。它的核心思想很朴素：先从左到右、从上到下扫一遍图像，给每个前景像素打一个临时标签；如果遇到一个像素的邻域里同时存在两个不同的标签，就说明这两个标签实际上属于同一个连通域，需要在等价表中记一笔。
以4邻域为例，扫描当前像素 p=(x,y) 时，只需要检查两个已经访问过的邻域：左邻域 (x-1,y) 和上邻域 (x,y-1)。因为扫描方向决定了右邻域和下邻域还没有被访问，它们的标签尚不存在。
第一遍的伪代码可以写成这样：
对图像中每个像素 p(x, y): if p 是背景(0): continue 读取左邻域标签 L = label(x-1, y) 读取上邻域标签 U = label(x, y-1) if L == 0 and U == 0: label(x, y) = new_label++ # 分配一个新标签 elif L != 0 and U == 0: label(x, y) = L # 沿用左邻域标签 elif L == 0 and U != 0: label(x, y) = U # 沿用上邻域标签 else L != 0 and U != 0: if L == U: label(x, y) = L else: # 冲突：左邻域和上邻域属于不同标签，必须合并 label(x, y) = min(L, U) 在等价表中记录等价对 (L, U)2.2 一个3×3图像的完整追踪
光看伪代码还是不够直观，我拿一个真实的3×3二值图全程走一遍。使用4邻域，前景像素为1，背景为0：
1 1 0 1 0 1 0 1 1从左到右、从上到下逐像素扫描：
- (0,0)：左邻域和上邻域都是背景，分配新标签1。
- (0,1)：左邻域标签为1，沿用标签1。
- (1,0)：上邻域标签为1，沿用标签1。
- (1,2)：左邻域为0，上邻域为0，分配新标签2。
- (2,1)：左邻域为0，上邻域为0，分配新标签3。
- (2,2)：左邻域标签是3，上邻域标签是2，冲突。取最小值2作为当前像素标签，并记录等价对(2,3)。
第一遍结束后，临时标签图长这样：
1 1 0 1 0 2 0 3 2注意 (2,1) 这个像素的临时标签仍然是3，但从等价对(2,3)我们已知它和标签2其实属于同一个连通域。
2.3 第二遍：等价表统一与标签重写
第二遍要做的事情归纳起来两步：先把第一遍收集到的所有等价对合并成若干个等价类，再把每个临时标签映射到等价类的代表标签，最后重新扫描图像，把像素的临时标签替换为真正的标签。
还是上面那个例子。等价表里只有一条记录：(2,3)。合并后得到等价类 {2, 3}，取最小值2作为代表。第二遍扫描时：
- 标签1保持不变，输出1。
- 标签2保持不变，输出2。
- 标签3映射为2，输出2。
最终标签图：
1 1 0 1 0 2 0 2 2整个图像被正确地标记成了两个连通域。
2.4 为什么必须“扫两遍”
很多初学者不理解：第一遍明明已经把大部分标签打好了，为什么不能一边扫一边改？
因为第一遍扫描过程中，冲突是随扫描顺序逐步暴露出来的。刚才的例子中，(2,1) 被打了标签3，而在它之前我们根本不知道标签3会和标签2碰撞。如果你在第一遍已经给 (2,1) 盖上3的章，之后发现3和2是同一个等价类，就必须回到 (2,1) 把它改成2。问题在于 (2,1) 已经扫描过了，想改就得回退，回退的代价可能是灾难性的——一个局部冲突可能连锁引爆，让整个图像陷入反复修改的循环。
所以两遍扫描不是刻意设计成两遍，而是“先收集关系、再统一改写”这种分布式标记方案的自然产物。第一遍可以理解成情报收集，第二遍才是正式盖章。这个思想在很多其他算法里也会反复出现，比如并行图算法里的标记传播阶段。
实际工程实现中，等价表往往不是塞一个简单数组就完事，而是用并查集来维护。这也正好引出下一节要展开的数学工具。
3. 等价合并背后的数学：并查集的压缩与秩
3.1 为什么朴素等价表扛不住大图
上一节的例子只有一对等价关系，手工处理绰绰有余。但真实图像动辄几百万像素，第一遍可能记录出几十万条等价对，这些等价对像一串链条一样交织在一起：等价对(1,2)、(2,3)、(3,4)最终会让1、2、3、4全部合并成同一个连通域。如果用朴素方法，每来一条等价对就跟已有集合做两两比较，复杂度会迅速恶化到 O(n²) 级别。
所以工程实践基本不会用朴素列表，而是直接上并查集。
3.2 并查集的数学本质
并查集处理的正是等价关系的合并查询问题。它的底层维护的是若干个集合，每个集合用一棵树表示，树的根节点就是集合的代表元。需要支持两个操作：
- Find(x)：找到 x 所在集合的根节点。
- Union(x, y)：把 x 和 y 所在的两个集合合并成一个。
在连通域标记的场景里，每遇到一个等价对 (a, b)，就调用 Union(a, b)。查找时路径压缩这个优化手段值得展开讲讲。
路径压缩的核心操作是在 Find 过程中，把从当前节点到根节点路径上的所有节点，直接挂到根节点下面。这样下次再查询这些节点时，一步就能找到根。数学上，带路径压缩和按秩合并的并查集，其单次操作时间复杂度是 O(α(n))，这里的 α(n) 是反阿克曼函数。对于宇宙中任何实际能出现的 n，α(n) 都不会超过4。换句话说，每个 Union/Find 操作都近似于常数时间。
3.3 按秩合并的意义
除了路径压缩，另一个优化是按秩合并。秩可以理解为树的高度上界。Union 时总是把秩较小的树挂到秩较大的树下面，避免树长成一条链。两个优化双管齐下，才能保证逆阿克曼级别的复杂度。
为什么这个细节值得写进博客？因为很多现成库虽然已经帮你封装好了并查集，但如果你自己实现连通域标记，少一个优化，在超大图上就直接可以看到时间差。我实测过一个二值化后包含约120万前景像素的医学切片图，只用路径压缩不用按秩合并，处理时间大约2.1秒；两个优化都用，降到1.2秒左右。差距在数据规模大时绝对不可忽略。
伪代码如下：
初始化 parent[i] = i, rank[i] = 0 function Find(x): if parent[x] != x: parent[x] = Find(parent[x]) # 路径压缩 return parent[x] function Union(a, b): ra = Find(a) rb = Find(b) if ra == rb: return if rank[ra] < rank[rb]: parent[ra] = rb elif rank[ra] > rank[rb]: parent[rb] = ra else: parent[rb] = ra rank[ra] += 13.4 最终标签的最小值映射
连通域标记里一个常见的需求是：最终每个连通域的编号从1开始连续递增。并查集扫完后，可以再做一次映射：
将等价类按根节点从小到大排序 根 -> 连续编号的映射表 第二遍扫描时，label(x, y) = map[root(label(x, y))]这一步能让输出图像非常干净，也方便后续用颜色映射把不同区域可视化出来。我处理调试时习惯顺手把映射后的结果存成一张伪彩色图，一个个连通域颜色各不相同，肉眼就能确认算法有没有把不该合并的区域合并了。
4. 种子填充的递归陷阱与扫描线优化
4.1 递归洪水填充看起来很美
两遍扫描是“先归类再改写”，种子填充走的是另一条路：从某个前景像素出发，沿着邻域关系像洪水一样向四周蔓延，把所有可达像素染成同一个颜色。代码写起来非常直观：
function FloodFill(x, y, label): if 越界 or 该像素不是前景 or 已被标记: return label(x, y) = label FloodFill(x+1, y, label) FloodFill(x-1, y, label) FloodFill(x, y+1, label) FloodFill(x, y-1, label)递归写法最大的优点是好懂，但工程上几乎没人敢直接在项目里用。原因只有一个：图像尺寸稍微一大，调用栈直接爆掉。
4.2 递归为什么爆栈
每一次递归调用都要在系统栈里压入函数返回地址、参数和局部变量。一张1000×1000的图像，一个连通域如果形状复杂，递归深度可能达到几十万层。系统栈默认也就1MB到8MB，撑不住很正常。我亲眼见过同学在调试时把一张切片图丢进递归种子填充里，程序当场段错误，找了一晚上才确定是栈溢出而不是算法逻辑写歪了。
4.3 显式栈替代系统栈
把递归改成显式栈是立刻能用的方案：
stack = [(x, y)] while stack 不为空: (cx, cy) = stack.pop() if 越界 or 该像素不是前景 or 已被标记: continue label(cx, cy) = label stack.append((cx+1, cy)) stack.append((cx-1, cy)) stack.append((cx, cy+1)) stack.append((cx, cy-1))显式栈把内存压力转移到了堆上，至少不会因为默认栈空间小而死掉。但每个前景像素都要经历多次压栈弹栈，内存开销和速度都不算好看。
4.4 扫描线填充：按行吞并
真正让我在日常工程里常用的是扫描线填充变体。它不再以“像素”为最小单位，而是以“连续前景段”为单位。思路如下：
- 从起始像素所在行，向左右扩展，找到整段连续前景区间。
- 标记整个区间。
- 检查上一行和下一行与当前区间有重叠的前景段，把这些段的起始位置压入栈。
因为每一段只入栈一次，而不是每个像素入栈，栈规模大幅下降。举个例子，一个宽500像素的横条，逐像素入栈算法要处理几千个元素，扫描线版本只需要一次入栈，连标记都是一整段连续赋值。
用伪代码表示：
function ScanlineFill(x, y, label): stack = [(x, y)] while stack 不为空: (sx, sy) = stack.pop() # 向左右扩展找段边界 left = sx right = sx while left-1 >= 0 and 前景(left-1, sy) and 未标记(left-1, sy): left -= 1 while right+1 < W and 前景(right+1, sy) and 未标记(right+1, sy): right += 1 # 标记整段 for i in [left, right]: label(i, sy) = label # 检查上一行和下一行 for ny in [sy-1, sy+1]: in_segment = False for nx in [left, right]: if 前景(nx, ny) and 未标记(nx, ny): if not in_segment: stack.append((nx, ny)) in_segment = True else: in_segment = False实际压缩后的代码会把连续前景判断，以及段重叠检查写得紧凑些，但核心逻辑就是这个。我在一个 4096×4096 的二值图上对比过：逐像素显式栈需要约300毫秒，扫描线版本只需要约80毫秒，栈峰值也从几万层降到了几十层。对于移动端或者实时性要求高的嵌入式场景，这种差别是决定性的。
5. 标记完之后顺手算：面积、质心与包围盒的公式配方
5.1 标记的最终产出是一张标签图
连通域标记跑完后，输出的标签图是一张灰度图，其中每个前景像素的灰度值就是它所属连通域的编号。从这张标签图出发，可以非常方便地统计每个连通域的特征，这也是很多图像分析任务中最常被用到的下游环节。
5.2 面积：数像素个数
面积最简单，就是连通域内像素的总数。对第 k 个连通域，假设其像素集合为 Sk，那么：
Area(k) = |Sk| = Σ (1 over all pixels p in Sk)
遍历标签图，逐像素统计每个标签的出现次数即可。这一步骤如果用直方图来算，还可以加速。OpenCV 的 connectedComponentsWithStats 输出里就有每个连通域的面积，底层就是这么统计的。
5.3 质心：一阶矩的中心
质心（也就是重心）通常用矩来计算。图像矩的定义为：
Mpq = Σ over pixels (x^p * y^q * I(x, y))
对于二值标签图，第 k 个连通域内像素值为1。则：
- 零阶矩 M00 = 面积
- 一阶矩 M10 = Σ x
- 一阶矩 M01 = Σ y
质心坐标就是：
Cx = M10 / M00
Cy = M01 / M00
说白了，质心就是所有像素坐标的平均值。为什么叫“一阶矩”？一阶矩衡量的是分布的位置期望，除以总面积后得到的就是均值坐标。这个公式在做细胞追踪、目标定位时到处都能见到。我在做商品外观缺陷定位时，靠的就是连通域质心的跳动幅度来判断目标是否发生了位置偏移。
5.4 包围盒：四个边界值
包围盒本质上就是连通域内所有像素坐标的最小值和最大值：
x_min = min(x)
x_max = max(x)
y_min = min(y)
y_max = max(y)
有了这四个值，宽高可以直接算：
width = x_max - x_min + 1
height = y_max - y_min + 1
这里有个常见的细节：加1是因为坐标从0开始计数。如果你统计出来的像素坐标是连续的，宽度应该是最大减最小再加1。很多人在算矩形框大小时漏了加1，导致框比实际区域小一圈，视觉上就会显得偏紧。这是我带新人时最容易发现的错误之一。
5.5 一次遍历同时统计多种特征
工程上你不会为面积、质心、包围盒分别扫描三次图像。正确做法是单次遍历，边扫描边累加每个标签的像素计数、x坐标和、y坐标和、x最小值、x最大值、y最小值、y最大值。遍历结束后再统一除以计数得到质心，统一相减得到尺寸。
这种设计不仅省时间，也便于把统计逻辑放进并行框架里。多线程分块扫描时，每个线程维护一套局部统计值，最后用归约操作合并。我在一个高分辨率工业图像项目中，就是用这种「边标记边统计」的方式，把整张图的连通域特征提取耗时压缩到了几十毫秒级别。
5.6 更高级的特征留个引子
面积、质心、包围盒只是最基础的三板斧。拿到这三个量之后，你还可以推方向角。方向角需要用到二阶中心矩。二阶中心矩公式为：
μ20 = Σ (x - Cx)²
μ02 = Σ (y - Cy)²
μ11 = Σ (x - Cx)(y - Cy)
目标的方向角由以下公式确定：
θ = 0.5 * arctan(2 * μ11 / (μ20 - μ02))
这个量在做字符倾斜校正、椭圆拟合时非常实用。如果你要深入目标形状分析，方向角基本是绕不开的下一站。
6. 实战选型建议与调试心得
6.1 四邻域还是八邻域？看背景也要看前景
选4邻域还是8邻域，不能只看前景目标。如果你处理的是细长的线条字体，用8邻域很容易把相邻字符的笔画连到一起；如果背景干扰像素很多，用4邻域则容易把目标割裂成一堆碎片。我的个人经验是：目标本身粗壮，用4邻域；目标细长且允许一定的连接容忍度，用8邻域。如果背景噪声点不多，优先4邻域。
6.2 到底选两遍扫描还是种子填充
大图、连通域数量多、需要稳定的内存占用——优先两遍扫描加并查集。图像不大但形状极端复杂、或者连通域数量少——种子填充扫描线版本更快。我一般以单张图像512×512为分界线，小图直接扫描线种子填充，大图走两遍扫描。当然具体还要看硬件平台，内存充裕但CPU吃紧的嵌入式设备，我会选择扫描线填充，因为它的局部性好，cache命中率高。
6.3 调试连通域标记的一个土办法
调试时最害怕的是“算法是不是标错了”这种模糊状态。我的排查套路是：跑完标记后，把标签图按哈希映射成随机颜色，输出一张伪彩色对比图。看到两个明显断开的目标被标成同一颜色，就去检查邻域定义是否一致；看到同一目标内出现不同颜色，就去检查等价表合并是否有遗漏。伪彩色可视化配合小尺寸测试图，基本十分钟内能定位问题。
6.4 别小看连通域的实用性
连通域标记看起来基础，但它几乎是所有传统图像分析任务的入口。从简单的零件计数、到复杂的卫星图像地物分类，再到医学切片的细胞分型，每一步都需要先知道“图上有几个目标，每个目标在哪”。正因为它太常用，把它的原理、数学本质、常见实现路径和实践技巧吃透，投资收益比极高。
如果你正准备自己实现一遍，我的建议是从两遍扫描开始，先不要用任何现成库，手写一遍并查集版本。当你把等价表、并查集合并、第二遍标签重写全部跑通，再回去看任何图像处理库里的连通域接口，都会觉得格外通透。这层功夫花得绝对值。
