图像分割在计算机视觉里的位置，有点像“人人都知道重要，但真正用起来总是不顺手”的公共组件。早些年做识别、检索、目标提取，第一步几乎都是先把图像切成有意义的块；这几年深度模型虽然端到端扛起了大局，但凡是需要精确边界、小目标提取或者区域特征统计的任务，经典分割算法依然会被翻出来当作后处理或特征生成器。这篇论文笔记的主角，是 Efficient Graph-Based Image Segmentation——一篇很经典的图模型分割论文。它把像素看成图的顶点，把像素间的差异看成边的权重，通过并查集做贪心合并，在接近线性的时间内把图像切成语义上相对一致的连通区域。整个方法的核心优势就三点：速度快、参数少、对局部差异自适应。只要你想理解“怎么把图论算法落到图像上”，或者“如何给视觉系统设计一个可用性极高的预处理模块”，这篇都值得认真读一遍，最好亲手复现一次。
1. 项目概述：这篇论文到底解决了什么问题
1.1 老问题的新解法
图像分割的定义本身不复杂：把图像划分成互不相交的连通区域，让每个区域内部足够一致，区域之间又足够不同。难点从来不是定义，而是怎么高效地算出来。传统思路大概有阈值、边缘检测、区域生长和聚类几类，但都有各自的坑。阈值法适合全局光照稳定的简单图像，一旦图像里有纹理或者渐变，就很难找到一个全局阈值同时照顾亮部和暗部。边缘检测得到的通常是一堆断续线段，要把线段围成闭合区域，还得另做大量修补。区域生长依赖种子点选择，种子点选不好，一个物体很容易被从中间切成两半。聚类方法做得最多的就是 k-means 这一类，它本质上是在颜色特征空间里做划分，没有显式考虑像素之间的邻接关系，所以经常出现同一个物体碎成几块、不同物体却粘连在一起的情况。
图模型从更根本的角度处理了这个问题：它的顶点天然带着空间位置，边天然带着相邻关系，特征差异则放到边的权重里。这样一来，分割问题就变成了一个“把哪些顶点归并成一组”的组合优化问题。论文中的方法没有去追求全局最优解，而是取了一个非常工程化的路线——局部自适应的贪心合并。它每一步都只看“当前这对相邻区域到底像不像”，像就合并，不像就保留，然后用并查集持续迭代。这种取舍让算法牺牲了一部分理论上的最优性，却换来了实践中最看重的速度和内存。
1.2 适合谁看、用在什么场景
这篇论文笔记适合三类人。第一类是刚接触图像分割的研究者，可以用这篇文章快速建立“从图论模型到分割结果”的完整闭环，而且代码量小，适合精度式学习。第二类是写视觉系统的工程师，想找一个稳定快速的前处理阶段，把像素级冗余降下来，或者给下游检测、分类提供超像素/候选区域。第三类是单纯对算法设计感兴趣的人，这篇论文把“如何设计一个局部自适应的合并判据”讲得很清楚，这种设计思路迁移到别的领域也很有价值。
关于适用场景，我的判断是：它非常适合做粗分割和预处理的中间层，不适合做需要逐像素精确语义标签的最终输出。比如医学图像里的肿瘤边界、遥感图像里的精细地物分类，这些任务需要的精度远超这种贪心方法的范畴，应该交给专门的分割网络或更精细的能量优化方法。但反过来，在目标候选区域生成、超像素提取、前景背景粗分离、交互式抠图的前置步骤里，这个算法是性价比极高的选择。
2. 算法原理拆解：三个关键定义和一个合并判据
2.1 把图像变成图：模型怎么建
算法第一步，把图像表示成无向带权图 G=(V, E)。顶点 V 对应每个像素，边 E 则连接相邻像素。这里的“相邻”一般用 4 邻域或 8 邻域。4 邻域只连接上下左右，边数少，处理快；8 邻域额外连接对角线，能保留更多斜向边界的线索，分割出来的区域边缘更贴合真实物体轮廓。
边的权重定义是不相似度，而不是相似度。对灰度图，最常见的就是像素灰度差的绝对值；对彩色图，论文作者建议用颜色空间里的欧氏距离。实际操作里，直接使用 RGB 空间的距离虽然简单，但光照变化时很容易把同一物体内部也切碎；我自己的经验是先用 Lab* 空间再做欧氏距离，Lab* 把亮度通道 L 和颜色通道 a、b 分开，对光照变化更稳定。关于颜色空间的影响，后面实操部分还会细说。
这张网格图不需要像超像素方法那样提前做特征提取，能不能分割好，关键全在“相邻像素的颜色差异”和“合并判据”配合得是否合理。
2.2 内部差异、外部差异与最小内部差异
合并判据要用到三个定义。
第一个是组件内部差异 Int(C)。对一个已经形成的像素集合 C，论文里的定义是：C 的最小生成树中权重最大的那条边的权重。换句话说，它代表“为了让这个区域保持连通，必须承受的最大内部跨度”。如果区域内部颜色都很接近，Int(C) 就会很小；如果区域内部本身就包含明显的纹理变化，Int(C) 就会偏大。
第二个是组件外部差异 Dif(C1, C2)。它定义为连接 C1 和 C2 的所有边当中权重最小的那条边的权重。通俗理解就是这两个区域之间“最像的一对像素”有多像，也就是两者之间的最小连接成本。
第三个是合并判据里真正用到的“最小内部差异” MInt(C1, C2)，形式如下：
MInt(C1, C2) = min( Int(C1) + τ(C1), Int(C2) + τ(C2) )
其中 τ(C) = k / |C|，|C| 表示组件里像素的数量，k 是用户传入的尺度参数。
可以看出来，MInt 取的是两边“内部差异+尺寸惩罚”的较小值。为什么是较小值而不是较大值？这保证了只要其中一个区域足够“稳”，整体就不容易被外部弱边界强行拆开，从而保留弱边界的可能性更大。
2.3 合并判据为什么合理
有了这三个定义，合并条件本身只有一行：
Dif(C1, C2) ≤ MInt(C1, C2)
也就是说，两个区域之间的“最小外部差异”小于等于两边各自“内部差异”的较小者，就合并。这个条件的直觉可以这样理解：两个区域的边界隔开它们的理由，必须比它们内部自身的波动更强。如果一个区域内部颜色本来就很跳跃，那么一条外部弱连接就不足以证明两个区域是不同的东西。
打个比方：判断相邻两个小区要不要合并成同一个物业管理。Dif 是两小区之间最矮的那道围墙；Int 是每个小区内部最差的一段内部道路。如果内部道路已经坑坑洼洼，围墙反而比这段路还矮，那道围墙就没有存在意义，当然应该合并。反过来，如果围墙又高又新，内部路又平整，那说明两边确实是两个不同小区，不该合并。
加在 Int 后面的 τ(C)=k/|C| 也很讲究。它是对小区域的“保护费”。区域越小，|C| 越小，τ(C) 就越大，合并阈值越高。这带来一个效果：小区域不会被随便并到隔壁，就算它和邻居之间有稍大的颜色差异，也有机会保留下来。这正好抑制了分割中常见的“碎片被大区吞并”问题，也是论文中“保留感知上重要的边界”这一性质的关键来源。
2.4 唯一核心参数：k 如何控制分割粒度
k 是论文里最需要用户关注的参数，它的直观作用是控制最终区域的大小。k 越大，τ(C) 越大，合并条件越宽松，算法越倾向于把差异不太大的区域并在一起，最终区域数量减少、面积增大。k 越小，分割越碎，小目标和小边界更容易被保留。
具体选多大没有绝对标准，和颜色空间的尺度关系很大。用 RGB 或 Lab* 空间中 0 到 255 量级的欧氏距离时，我常用的范围是 100 到 500。如果图像内容复杂、目标大小悬殊，可以先用较小的 k 保住细节，再在后处理阶段用 min_size 把过小的碎块合并掉，效果比一味调大 k 更好。
3. 算法流程与复杂度：为什么能做到近线性
3.1 并查集视角下的完整流程
整个算法可以拆成五步：
- 建图：对每个像素建顶点，按邻域关系连边，计算每条边的权重。
- 排序：将所有边按权重从小到大排序。
- 初始化：每个像素自己单独成一个组件，组的内部差异设为 0。
- 合并：遍历排序后的边，对每条边连接的两个像素，先判断是否属于同一组件；若不属于同一组件，则比较当前边权和两个组件的 MInt，满足条件就合并，并更新新组件的内部差异。
- 后处理：把小于最小尺寸 min_size 的组件强制合并到邻近组件，避免最终结果出现过多碎片。
合并阶段需要维护的信息并不多：每个组件的父节点、每个组件的尺寸、每个组件的内部差异。后两者只需要对根节点更新，因为组件合并时总有一个根被并到另一个根下面。
更新内部差异时的规则是一个很容易被忽略的细节：新组件的 Int 不是直接取当前边权，而是要取“合并前两个组件的 Int 以及当前边权”三者的最大值。这样 Int 表示的一定是区域内部最小生成树上的最大边权，保证它在合并过程中单调不减。
3.2 复杂度来源与剪枝思路
最耗时的操作是排序。网格图的边数 m 和像素数 n 的关系是：4 邻域约为 2n，8 邻域约为 4n，所以边数和像素数线性相关。排序的复杂度是 O(m log m)，即 O(n log n)。之后的并查集 find 和 union 带有路径压缩与按秩合并，均摊下来近似常数时间。整体复杂度可以认为是近线性，这就是它在百万像素级别图像上还能跑得动的根本原因。
与经典的全局优化类分割方法相比，这个优势特别明显。那些方法往往要构建很大的稀疏矩阵，求解特征分解或者迭代优化能量函数，对一张几十万像素的图就要消耗几秒甚至更久。而这个方法的整个合并过程不需要任何迭代求解，一轮边扫描就能形成主要分割结果，工程实现极其干净。
3.3 工程上的几个关键数据结构
- parent：一维数组，长度 n，存并查集父节点。
- size：一维数组，长度 n，存组件大小，只在根节点有效。
- internal：一维 float 数组，长度 n，存组件内部差异，只在根节点有效。
- edges：数组或结构体列表，每条边存两个顶点索引和一个 float 权重。
用 C++ 写的时候，我习惯直接用 vector 存边结构体，用原生数组做并查集。用 Python 写时可以用列表或 NumPy 数组。注意 internal 只对根节点维护，如果 find 后根节点变了，internal 也要跟着重定向，否则合并条件里的 Int(C) 会读脏数据。这个问题我实际调试时踩过，初始化时把 internal 全部置 0，合并时再更新，逻辑上最干净。
4. 实操复现：从零实现一个可用版本
4.1 环境准备与测试数据
复现这篇论文只需要基础的 Python 环境，依赖 numpy、matplotlib、scikit-image、scipy。安装命令一行即可：
pip install numpy matplotlib scikit-image scipy测试图像建议选择两类：一类是自然风景图，有明显的天空、山地、树木分块；另一类是纹理丰富的织物或草地特写。这样能同时观察算法对强边界和弱边界/纹理区域的表现。为了加快调试，可以先从 320×240 或 640×480 的小图开始，等参数稳定后再换高分辨率图。
4.2 Python 实现完整代码
下面这套代码基本按照论文流程编写，并查集部分用了路径压缩和按秩合并，边构建部分做了向量化处理，避免 Python 双重循环在大图上慢到不可接受。
import numpy as np from skimage import color, io from scipy.ndimage import gaussian_filter from matplotlib import pyplot as plt class DisjointSet: def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n self.size = [1] * n def find(self, x): while self.parent[x] != x: self.parent[x] = self.parent[self.parent[x]] x = self.parent[x] return x def union(self, a, b): ra, rb = self.find(a), self.find(b) if ra == rb: return ra if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra self.parent[rb] = ra self.size[ra] += self.size[rb] if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1 return ra def build_edges(lab, use_8_connectivity=True): h, w, _ = lab.shape edges = [] # 水平边 xs = np.arange(0, w - 1) ys = np.arange(0, h) xv, yv = np.meshgrid(xs, ys) src = (yv * w + xv).ravel() dst = (yv * w + xv + 1).ravel() diff = np.linalg.norm(lab[yv, xv] - lab[yv, xv + 1], axis=2).ravel() edges.extend(zip(diff.tolist(), src.tolist(), dst.tolist())) # 垂直边 xs = np.arange(0, w) ys = np.arange(0, h - 1) xv, yv = np.meshgrid(xs, ys) src = (yv * w + xv).ravel() dst = ((yv + 1) * w + xv).ravel() diff = np.linalg.norm(lab[yv, xv] - lab[yv + 1, xv], axis=2).ravel() edges.extend(zip(diff.tolist(), src.tolist(), dst.tolist())) if use_8_connectivity: # 主对角线 xs = np.arange(0, w - 1) ys = np.arange(0, h - 1) xv, yv = np.meshgrid(xs, ys) src = (yv * w + xv).ravel() dst = ((yv + 1) * w + xv + 1).ravel() diff = np.linalg.norm(lab[yv, xv] - lab[yv + 1, xv + 1], axis=2).ravel() edges.extend(zip(diff.tolist(), src.tolist(), dst.tolist())) # 反对角线 xs = np.arange(1, w) ys = np.arange(0, h - 1) xv, yv = np.meshgrid(xs, ys) src = (yv * w + xv).ravel() dst = ((yv + 1) * w + xv - 1).ravel() diff = np.linalg.norm(lab[yv, xv] - lab[yv + 1, xv - 1], axis=2).ravel() edges.extend(zip(diff.tolist(), src.tolist(), dst.tolist())) return edges def segment(image, k=300, min_size=50, sigma=0.8, use_8_connectivity=True): h, w, _ = image.shape # 1. 高斯预平滑，抑制噪声引起的过分割 smooth = np.dstack([gaussian_filter(image[..., i], sigma) for i in range(3)]) # 2. RGB 转 L*a*b*，光照变化下更稳 lab = color.rgb2lab(smooth) # 3. 建边、排序 edges = build_edges(lab, use_8_connectivity) edges.sort(key=lambda e: e[0]) # 4. 并查集初始化 + 合并 dsu = DisjointSet(h * w) internal = np.zeros(h * w, dtype=np.float32) for wgt, a, b in edges: ra, rb = dsu.find(a), dsu.find(b) if ra == rb: continue tau_a = k / dsu.size[ra] tau_b = k / dsu.size[rb] if wgt <= min(internal[ra] + tau_a, internal[rb] + tau_b): new_root = dsu.union(ra, rb) internal[new_root] = max(internal[ra], internal[rb], wgt) # 5. 后处理：强制合并过小区域 if min_size > 1: for _ in range(50): changed = False for wgt, a, b in edges: ra, rb = dsu.find(a), dsu.find(b) if ra != rb and (dsu.size[ra] < min_size or dsu.size[rb] < min_size): new_root = dsu.union(ra, rb) internal[new_root] = max(internal[ra], internal[rb], wgt) changed = True if not changed: break # 6. 给每个像素生成最终标签 labels = np.zeros(h * w, dtype=np.int32) root_to_label = {} cnt = 0 for i in range(h * w): r = dsu.find(i) if r not in root_to_label: root_to_label[r] = cnt cnt += 1 labels[i] = root_to_label[r] return labels.reshape(h, w) if __name__ == "__main__": image = io.imread("test.jpg") image = image[:, :, :3] # 去掉Alpha通道 labels = segment(image, k=150, min_size=20, sigma=0.8) # 可视化：用每个区域的平均颜色渲染 out = image.astype(np.float32).copy() for label_id in np.unique(labels): mask = labels == label_id out[mask] = image[mask].mean(axis=0) out = out.astype(np.uint8) plt.subplot(1, 2, 1) plt.imshow(image) plt.subplot(1, 2, 2) plt.imshow(out) plt.show()这段代码已经把论文核心流程完整实现了一遍。build_edges 里用 np.meshgrid 一次性生成了所有边，比双重循环快很多。internal[new_root] 的更新用了 max 而不是直接赋值，这是保证内部差异定义正确的关键。
4.3 参数调节与效果对照
调参时最需要理解的三个量是 k、sigma、min_size。k 是主控，sigma 控制预平滑强度，min_size 是对结果做“事后清理”。我用一张 640×480 的风景图做过一组对照，大致的规律可以描述如下。
k 偏小，比如 50 以下，图像里纹理丰富的区域（草地、树叶）会被过度分割成大量小块，天空这种大平缓区域倒是不会被切开，但整体区域数量会多到无法用于下游任务。k 到 150 到 300 之间，视觉上最能平衡细节和整体：树干、建筑、天空这些主要物体基本能分成完整区域，草地纹理还有一些破碎，但已经可以被 min_size 清理。k 超过 500，小目标容易被大区域吞掉，比如远处的人、电线杆、树枝这类面积小但语义重要的对象会直接消失。
sigma 的作用可以看作“给图像提前抹匀”。sigma 越大，预平滑越强，合并时小差异被磨平，分割倾向更整。但 sigma 太大会把真实边界也磨掉，造成物体粘连。我实践下来，0.5 到 1.0 是个比较稳的范围。
min_size 是一个“兜底”参数，它不会影响大区域的形状，只负责把小块并掉。设置 min_size 后，小于该阈值的区域会被强制合并到一边，数量级和 k 一样需要根据图的分辨率调整。比如 640×480 图上设 20 比较合适，高分辨率图可以按比例增大。
4.4 实操中容易踩的坑
我在复现时踩过的坑集中在三处。
第一处，颜色空间转换前忘了做归一化。scikit-image 的 rgb2lab 默认要求输入是 0 到 255 的 uint8，或者 0 到 1 的 float。如果读进来的是 float32 且范围是 0 到 255，转换结果会异常，边权重偏大，整个分割直接过碎。
第二处，后处理里的“反复遍历边直到收敛”在高分辨率图上可能比较慢。教学版这么写没问题，工程上更好的做法是先压缩边表，把连接同一对根节点的最小边留存下来，再对小块组件做合并，速度会快一个数量级。
第三处，用 8 邻域时边数翻倍，但内存也翻倍。对超大图，可以先降采样，也可以先用 4 邻域做粗分割，等到了边界优化阶段再用 8 邻域重算局部结果，不要一上来就塞进 8 邻域全图。
5. 常见问题与排查技巧实录
5.1 过分割与欠分割的调参方向
问题：同一片纹理被切成无数小区域。 原因：k 过小，或图像噪声大，或直接用了 RGB 距离。 对策：先提高 sigma 到 1.0 左右，再把 k 翻倍尝试。不要只调 k，有时候预平滑收效更快。
问题：不同物体粘连在一起，边界不清晰。 原因：k 太大，或者 sigma 太大把弱边缘磨没了。 对策：降低 k，减小 sigma，必要时切换到 8 邻域保留斜向边界线索。弱边缘明显时宁可保留少量碎片，也不要直接粘连。
这类问题很多是参数权衡，不存在万能组合。我的经验是固定 sigma=0.8，先调 k 找到视觉上“刚刚好”的分割粒度，再用 min_size 清理碎片，这样整个调参过程只需要关注一个主变量，心里负担小很多。
5.2 速度与内存问题
问题：代码跑得很慢，尤其图像超过百万像素。 原因：边表构建和排序是瓶颈，Python 版尤其明显。 对策：用向量化 NumPy 构建边；边用 np.array 而不是 Python list 存储，排序用 np.lexsort；后处理只针对小区域做局部合并，不要遍历全图所有边来扫描。更极端的情况，先把图像缩小 1/4 分割，再把分割边界映射回原图，速度提升非常可观。
5.3 边界质量问题
问题：分割出的区域边缘锯齿明显，轮廓不平滑。 原因：像素级分割天然就是逐格子的，不会像曲线拟合那样圆润。 对策：如果只是可视化，可以用轮廓多边形的逼近；如果用于后续处理，可以把这个结果作为超像素边界，再用 CRF 或边缘感知滤波器做细化。论文方法负责“找到哪些像素应该在一起”，平滑边缘是下游任务的事，不必在算法层硬解。
另外，用平均颜色渲染分割结果时，如果出现偏色，先检查是不是图像本身有 Alpha 通道没去掉，或者 PNG 转 RGB 时通道错位。这类低级错误很容易让人误判算法效果。
6. 这篇论文的后续影响力与现代视角
6.1 从超像素到候选区域生成
Efficient Graph-Based Image Segmentation 是早期最有代表性的超像素生成方法之一。后来大家更熟悉的 SLIC 走的是局部聚类路线，生成的超像素均匀紧致，更像规则网格；而图方法生成的区域更贴合图像本身的边缘，形状自由度更大。两者对比，SLIC 方便控制数量和大小，图方法则更依赖图像内容本身的颜色结构。
在候选区域生成的流程里，这个方法的思想也被广泛吸收。很多目标检测框架里候选框的生成依赖“先分割、再合并”的思路，Selective Search 的出发点之一就是把颜色、纹理相似的相邻区域不断合并成候选目标区域。这种局部合并的思想源头，可以追溯到这篇论文对“区域差异”和“合并条件”的建模方式。
6.2 与深度学习方法的衔接
深度学习统治视觉任务之后，这篇论文并没有被彻底边缘化。在语义分割、实例分割相当普及的今天，模型输出的分割图依然常见锯齿、孤立点、边缘粘连问题，很多工程方案会用经典图分割或 CRF 做后处理修正。这个方法的计算成本低，拿模型输出的概率图作为边权重，让并查集合并语义一致的连通块，是有效的边缘锐化手段。
另外，不少弱监督分割方法和交互式分割工具也会借鉴它：用户提供少量标记，算法基于图合并扩展标记区域。它不需要大量训练数据，能在小样本和交互场景里快速出结果，这是“轻量级算法”在深度学习时代仍然有位置的典型例子。
6.3 反复重读后仍觉得值得吸收的设计细节
这篇论文对我个人最大的影响，不只是它教我一个图像分割算法，而是它演示了一种设计方法论：不要把问题做成黑盒，把所有决策都交给损失函数或通用优化器；而是先把问题拆成几个能被解释的组成部分，再让每个部分承担明确职责。内部差异负责度量区域一致性，外部差异负责度量边界强度，尺寸惩罚负责保护小区域，合并规则负责组合前面三者。每个模块单独看都很简单，组合起来却能得到数学上可分析、工程上可复现的性质，比如不产生过碎区域、能保留弱边界、运行时间近线性。
我后来在做别的图像处理模块设计时，也经常借鉴这种“局部自适应阈值”的思路：与其用一个全局参数控制所有区域的合并行为，不如让每个区域根据自己的尺寸和内部变化动态计算阈值。很多“看起来要调一堆参数”的问题，换成这种思路后反而变得更简单、更稳定。
如果让我给后来者一个建议，我会说：读这篇论文不要只停留在“哦，原来是用并查集做分割”这个结论上。亲手实现一遍，再改一改合并条件中的细节，比如去掉 τ(C) 或者把 min 改成 max，你会立刻从结果的变化里体会到每一个设计决策的分量。这种“把为什么写进代码里”的实践方式，比读十遍论文都更能长本事。
