图像分割在计算机视觉里的位置有点像“人人都知道重要但真正用起来总是不顺手”的公共组件。早些年做识别、检索、目标提取第一步几乎都是先把图像切成有意义的块这几年深度模型虽然端到端扛起了大局但凡是需要精确边界、小目标提取或者区域特征统计的任务经典分割算法依然会被翻出来当作后处理或特征生成器。这篇论文笔记的主角是 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 邻域约为 2n8 邻域约为 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_connectivityTrue): 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], axis2).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], axis2).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], axis2).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], axis2).ravel() edges.extend(zip(diff.tolist(), src.tolist(), dst.tolist())) return edges def segment(image, k300, min_size50, sigma0.8, use_8_connectivityTrue): 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(keylambda e: e[0]) # 4. 并查集初始化 合并 dsu DisjointSet(h * w) internal np.zeros(h * w, dtypenp.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, dtypenp.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, k150, min_size20, sigma0.8) # 可视化用每个区域的平均颜色渲染 out image.astype(np.float32).copy() for label_id in np.unique(labels): mask labels label_id out[mask] image[mask].mean(axis0) 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 邻域保留斜向边界线索。弱边缘明显时宁可保留少量碎片也不要直接粘连。这类问题很多是参数权衡不存在万能组合。我的经验是固定 sigma0.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你会立刻从结果的变化里体会到每一个设计决策的分量。这种“把为什么写进代码里”的实践方式比读十遍论文都更能长本事。
