图像分割理论笔记

图像分割将图像划分成不同部分，其核心思想是将图像分解成同质的像素组，按照判别标准的不同可以实现不同的分割方法，分割可以是完整的也可以是不完整的，取决于具体情况。

分割在大方向上分为两类，语义分割和实例分割:

• 语义分割
• 实例分割
• 在医学图像处理中，语义分割可以标注出不同种类的细胞，实例分割可以详细识别同种细胞的个体

竞赛与训练集

图像分割是计算机视觉的重要课题，那肯定少不了很多竞赛，比如说，2021 年的“越野图像分割挑战”（Off-road Image Segmentation Challenge），需要在越野场景中分割道路、树木、岩石，这种分割就很特殊，一方面要处理复杂地形问题，还要考虑驾驶员视角、光照变化的情况。 也有很多大规模标注数据集，比如 COCO 数据集。

分割标准

图像分割的的核心在于选择哪种同质性标准来进行分割，同质性可以理解为共同的特点，我们找到哪些像素是一家的，哪些像素是另一家的，因此有以下几种同质性标准:

• 像素强度: 也就是亮度/灰度，比如简单的黑白图像可以通过亮度差来实现分割
• 颜色: 利用RGB值来进行分组，比如说包含不同水果的彩色图像，西瓜是红色的，那么和蓝莓就可以分开
• 纹理: 利用图像粗糙度或者重复图案来进行分组，比如毛衣、草地、墙砖

这只是最开始图像分割的方法，随着图像变得越来越复杂，这些方法只能作为图像分割算法的基石，现在需要高级算法来找到一副差不多图像中的不同区域特征的边界。

Horowitz 定义

Horowitz 在 1975 年提出了一种分割数学模型，用来描述分割的性质和目标。

1. 一幅图像 I 可以被划分为 N 个不相交的子区域 S_i -->（ S_1, S_2, \dots, S_N ），即：

• 注意，子区域是不相交的，也就是不重叠的，并且要覆盖完整个图像（好比拼图）

2. 每个子区域 S_i 必须是连通的，也就是一个区域内，像素是相互连接的，不会有河流把同一区域内像素分开，不是东一块、西一块的，比如说一张猫的图片，猫的身体部分是一个区域，这个区域内，猫的头和脖子是不分家的，分开的那是路易十四

   \forall i \in [1, N], \; S_i \text{ 是连通的} \Rightarrow P(S_i) = \text{True}

3. 相邻两个区域 S_i 和 S_j 如果属性不同，则不可以合并，也就是绝对没有交集。比如说猫的头和背景绝对不能合成一个区域，或者蓝色和红色绝对不能合并成一个区域。

   \forall i, j \in [1, N], \; i \neq j \Rightarrow P(S_i \cup S_j) = \text{False}

在上面三个定义中， P 用来表示区域是否满足某种分割的标准，我们可以用方差标准:

• \sigma_R 表示区域 R 的像素值的方差，如果方差 \sigma_R 小于某个阈值，那么这个区域 R 就是同质的。

我们同样可以用均值标准

• 代表了区域 R 中每个像素值 I(p) 与区域平均值 \mu_R 的差异，如果差值较小，那么说明区域像素集中且均匀。

​

分割算法需要满足下面三个条件:

• 唯一性: 同一张图像经过相同标准分割后应该产生一致的结果
• 稳定性: 对噪声具有鲁棒性，不会显著影响分割结果
• 可计算性: 计算代价不能太高，也就是算法要保证速度

图像分割的常见方法

• 基于阈值化分割: 最简单的方法，设置阈值把图像分割成不同的区域
• 基于区域生长分割: 从一个种子点或者多个种子点开始生成，逐渐扩展形成区域
• 基于边界检测分割 : 检测图像中的边缘（像素值变化剧烈），并以此来将图像划分成不同区域
• 基于深度学习分割: 例如 U-Net 和 Mask R-CNN，可以自动学习如何分割复杂场景。

基于阈值化/分类的分割方法

我们先看第一种最简单的方法，只通过简单的规则就可以把图像划分为前景和背景两类，即二分类。

二值化过程

对于一副灰度图像中的每个像素 I ，阈值化过程可以用下面的公式表示:

• 1 为前景，0为背景

阈值化分割的优缺点

优点

• 算法逻辑简单，计算量小，适合实时处理，特别是用于单一目标的快速分割。
• 适用于对比明显的图像，前景和背景的像素值差异大时，分割效果很好。
• 便于实现，只需设定一个阈值即可完成分割，无需复杂的模型或训练数据。

缺点

• 对阈值选择敏感，阈值设定不当会导致分割结果不理想。
• 不适用于复杂图像。
• 不适合多类别分割，多区域划分做不了。

阈值选择

不同的阈值会导致完全不同的分割结果，因此我们要想办法确定最佳阈值。因此选择阈值的方法主要包括：

• 监督式方法

  观察直方图，手动选阈值。适用于简单图像，复杂图像的直方图分布不明显。

• 自动选择

  利用算法（如 Otsu 方法或 K-means）自动计算最优阈值，适合批量处理图像。

现在我们研究监督式方法中的直方图来找到阈值，其思想是我们把像素强度分布排开，如果直方图呈现双峰（前景、背景），那么这种情况直接中间一刀切开，阈值化方法就很适用。如果图像再复杂一点，两个峰之间有重叠，那么就麻烦了，我们对阈值的选择就有讲究了，一般来讲，低阈值可以保留细节，但是噪声多，中高阈值会导致细节丢失，但是能去噪。

有的时候图像直方图不仅仅是理想双峰形式，而是单峰形式（不可能分离），或者多峰形式，这个情况下我们要找到更灵活的分割方法，比如说 多阈值分割，比如说下一章节的区域生长法，比如说 K-means 聚类算法，或者基于深度学习求解

多阈值分割

下面我们先介绍多阈值分割方法，我们设置多个阈值，来将图像划分为不同区域，数学描述形式为:

• s_b 和 s_h 是低阈值和高阈值。

• 满足条件 s_b \leq I \leq s_h 的像素被归为前景，其余像素被归为背景。

• 比如挑苹果，我们把100g到200g之间的苹果挑出来

Naïve 自动阈值化方法

也是老派分割方法，它核心是计算像素分组的平均灰度值，然后慢慢调整阈值，一直到结果稳定，下面我们介绍其流程

1. 首先我们要计算他的直方图，统计每个灰度值的像素数量，得到灰度值分布情况，标准操作。

2. 然后我们要设置初始阈值 T_0 ，随便设就行，可以选灰度值范围中点 T_0 = 127 。

3. 再根据阈值 T_0 将像素进行分组，灰度值小于 T_0 的像素叫做 G_1 ，灰度值大于等于 T_0 的像素叫做 G_2 ，因此我们可以分别计算出 G_1 和 G_2 的平均灰度值:

4. 最后使用平均灰度值来更新阈值 T :

5. 不断循环迭代，重复上面步骤，直至收敛（阈值的变化小于一个预设的阈值 \varepsilon ）:

这个算法有点天真，虽然是自适应算法，但是迭代来迭代去针对的还是直方图双峰分布，对复杂多峰直方图弄不了，很容易陷入局部最优解

Fisher 算法

还是针对直方图来找到最佳阈值，我们的目标是将像素划分为不同的类别，同时最小化类别内的灰度值波动（惯性），这样像素就尽可能不偏离所属类别中心。

首先我们需要先定义一个分区 P = \{C_1, C_2, ..., C_N\} ，也就是直方图被划分为 N 个类别（ C_1, C_2, ..., C_N ），每个类别对应一定的灰度值范围。例如： C_1 = [0, t_1] ， C_2 = [t_1 + 1, t_2] ，这里的 t_1, t_2, ..., t_{N-1} 就是不同类别之间的分割阈值，算法的目标就是找到这些最优分割阈值。

然后我们需要计算惯性 W(P) ，它表示像素灰度值偏离类别区域中心值的平方误差加权和:

• h(k) 表示灰度值 k 的频率（直方图的高度）

• G(C_i) 表示类别 C_i 的中心值，计算公式为：

最后我们调整分割点，然后找到能使 W(P) 最小化的最佳分区，从而实现最佳的灰度值分割。

Otsu 算法（Fisher加速版）

Fisher 算法的确能找到最佳的阈值，但是我们也看到了其数学公式计算的复杂度，因此Otsu 算法是它的加速版本（只适用于二值分割）。它的核心思想是最大化类间方差来加速算法，通俗一点就是衡量两划分区域之间的差异，两区域差别越大，那么分割效果就越好。

以上就是阈值分割方法，我们可以看到其优点是，算法简单，原理简单，找到阈值就可以了，而且计算复杂度相比而言比较低，适合快速处理。

K-means 聚类算法

下面我们看一种 新的算法，叫做 K-means 聚类算法，它是一种常用的无监督学习算法，可以将数据聚类（就是分组），它的核心目标是最小化数据点到所属簇中心的距离平方和，从而将数据划分为 K 个簇。一般我们用它来完成多维度特征的分割。

给出其算法流程:

1. 首先进行初始化，随机选择 K 个点作为初始聚类中心（质心）

2. 然后分配簇，计算每个数据点到 K 个质心的距离，将数据点分配到最近的质心所在的簇

3. 然后更新质心，具体为对每个簇中的数据点求平均值，将该平均值作为新质心

• 其中 n_j 为簇 j 中的点数， x_i 表示簇中的点。

4. 重复步骤 2 和 3，反复分配点和更新质心，直至质心位置不再发生显著变化（达到收敛）

这个算法的优点是原理简单，找质心 - 分配点 - 更新质心，适合快速处理。它的缺点是 a)我们需要一个初始 K 值，也就是预设簇数，很多情况下这个 K 未知。并且 b)算法对初始聚类中心 K 值很敏感，选的不好就导致局部最优解。c)同时 K-means 假设每个簇是球形且等方差的，如果是数据分布复杂，那就没得玩了。 d) 最怕遇到极端点，那么质心位置就直接被显著影响了，聚类效果直接被破坏。

与阈值方法相比，K-means 更加灵活，能处理高维特征。

连通组件标记

在图像分割中，二值化是最基础的步骤，用来粗略分离前景和背景，不能区分前景中不同对象，因此我们现在需要对前景的独立兑现进行标记，赋予唯一的标签，这一步叫做对象标记

接下来我们介绍连通组件标记算法，它用来识别二值图像中的独立区域，判断哪些像素是连通的，并将这些连通像素赋予相同的标签，从而区分不同的对象。

2011年，Lacassagne 提出了针对传统连通组件标记算法的三步法优化，相较于两步法（初始标记和标签合并），三步法显著提高了效率，降低了计算复杂度：

1. 首先初始标记，快速扫描图像，初始分配临时标签，记录像素可能属于的区域
2. 优化合并策略，减少不必要的合并，防止增加计算量

基于区域划分的分割

我们之前讨论了基于阈值的分割方法，然后介绍了 K-means 聚类算法，并能够给前景内容贴标签，下面我们要讨论基于区域划分的分割方法，它也是一种递归算法，反复的将图像划分为更小的子区域，最终实现分割。其分割标准依旧基于同质性判断。

原理

对于区域划分，我们把整个图像作为初始区域，然后根据同质性标准判断区域内像素是否一致。然后应用递归方法，如果当前区域满足同质性标准，那么就停止划分保留该区域，否则我们需要进一步给它划分为更小的子区域，不断重复这个过程，直到划分为最小的区域单位

算法步骤

a) 开始的时候，我们将整个图像或者感兴趣区域视为单一的区域

b) 然后判断区域的同质性，如果满足，停止分割，如果不满足，那么就将其划分为更小的子区域

c) 将当前区域划分为多个大小相等的子区域，然后对每个子区域检查其同质性，不断重复。在划分子区域过程中，我们更偏向于生成最多的同质子区域。

d) 分割过程在以下条件满足之一的时候停止:

• 满足同质性标准，当前同质性值超过了预设阈值，不需要进一步分割
• 达到了最小面积，避免过度分割

几何划分的影响

区域划分的几何形状会影响分割结果，比如说正方形划分更适合规则图像，一旦区域被错误划分，那么就只能从头来，否则后续靠递归分割是救不了的

基于四叉树的分割方法

还是递归的规则分割方法，将图像反复划分为4个像素逐层均匀子区域，直到满足停止条件。分割结果以树状结构展示，有层次化特性。

原理

首先我们将整幅图像看作树的根节点，作为初始区域，然后每次划分将当前区域均匀划分为四个大小相等的正方形子区域，也就是生成四个子节点，每个子区域都需要检查是否满足同质性标准: 如果满足就不分割了，这个区域成为叶节点，如果不满足继续分割一直到最小单位阈值。

最终我们形成一颗四叉树，我们可以用层次化的方式来表示图像的区域划分结果，每个叶节点（最终区域）和图像中的区域是对应的

算法流程

a) 将整个图像初始化视为根节点（初始区域）。

b) 判断同质性进行划分，满足还是不满足，继续划分还是停止

c) 停止条件，如果区域同质性高于阈值，或者某区域面积小于面积阈值

d) 最后生成四叉树，树上每个叶节点都代表满足同质性的最终区域

优缺点

原理简单，分四块就行，但是它是刚性划分，不自然的划分，就分成四个小正方形，无法理解图中特性，显得机械死板。

区域融合分割

我们之前都是划分图像，把大的化成小的，区域融合分割是把小的合体，不断合并相似的图像区域，把像素层次相似的内容融合成有意义的区域图像。最终图像被划分为若干互不重叠的区域。

因此为了实现这个过程，需要把每个像素都看成一个小小的区域，然后建立邻接图（RAG），它用来描述小小区域之间的连接关系，然后算法会合并相似度高的相邻区域，完成融合

邻接图（RAG）

每个节点代表一个区域（小到像素，大到区域），每个边表示两个区域之间的相邻关系，这个边是带权重的，用来表示两个区域的相似程度（举个例子，我们可以用颜色来表示两区域的相似度，颜色越近相似度越高）

如图所示，有四个相邻区域，R1, R2, R3, R4，可以变成右边四个节点，颜色代表相似性

算法步骤

a) 首先我们进行初始化，图像被视作分为小单元，基于这些像素级别的单元，我们构建初始RAG邻接图，来此记录区域之间的相邻关系和相似性

b) 先找出所有的相邻区域对，然后计算相邻区域的相似性，把他们的相似性从高到低排列，储存为一个列表

c) 我们通过迭代寻找最佳的融合对: 在排序列表中找到两个最相似的相邻区域，判断他们是否满足融合条件，如果满足，最后将这两个选择后的区域合并为一个新区域，用一个新节点表示合并后的区域，删除旧节点的边，重新连接和其他区域的关系，重新计算与其他区域的相似性

d) 重复迭代进行区域融合，直到所有区域都不能再融合了（达到阈值、达到分割区域的数量）。

通俗来讲，区域融合分割就是拼图游戏，每个像素是初始拼图块，RAG图是拼图说明书，哪些拼图相邻、哪些图案类似，融合过程就是根据图案相似性把相邻拼图块拼到一起，构成一个大拼图单元最后把几个大区域合并到一起。

区域相似性与同质性

在区域融合分割中，判断区域是否可以合并的关键在于相似性和同质性。

我们用以下指标来判断合并后区域是否合理:

• 全局方差: 如果合并后的区域方差过大，说明区域内部差异过大，可能不该合并。 方差越小，表示区域内部的像素值更一致，也就是同质性更高。

• 偏离平均值的比例: 合并后的区域中像素值与平均值偏离一个标准差以上的像素所占比例，比例越低，说明区域内部的像素更趋近于平均值，表示区域更“均匀”或同质性更高。

当前我们可以在合并前进行初步分析，来大体推测一下能否判断它们的相似性:

• 归一化的差异分散度: 如果两个区域的像素值分布非常接近，说明可以合并
• 最小区域的大小: 小区域通常不稳定，优先考虑将两个小区域合并，形成一个更稳定的区域。
• 边界长度比例的倒数: 如果两个区域共享的边界较长，说明它们连接更紧密，适合合并。

将上述标准综合起来，可以定义一个混合相似性函数 f(R_i, R_j)，用于量化两个区域的相似性：

• f_{sim}(R_i, R_j)：表示区域间的内容相似性。
• f_{size}(R_i, R_j)：考虑区域大小的标准。
• f_{frontier}(R_i, R_j)：反映两个区域的边界关系。

自适应金字塔融合

传统区域融合是把相邻两个区域逐对合并，金字塔融合则一次性合并多个区域，按组合并，显著加速算法效率。

同时，它是分层来分割图像的，先从底层像素级开始合并，一直到顶层大区域合并。每次保留幸存节点，合并非幸存节点以减少冗余

算法步骤

a) 首先初始化，从像素开始，构建 8-邻接 邻接图，记录像素级别区域连接关系

b) 然后选择符合标准的幸存节点，幸存节点不允许相邻，避免冗余

c) 把非幸存节点合并到幸存节点中，这个合并到依据是之前的相似性函数f(R_i, R_j)，选择最相似的幸存区域。

d) 最后迭代根据合并后的新节点，重新建立关系，逐层合并，一直到顶层

从上图可见，最左边图像被分割成大量的小块，作为最底层的分割单元，然后选中白色的幸存节点，代表当前层级中保留的代表性区域，然后非幸存节点和幸存节点合并变成黑色，这个时候初步区域划分已经形成，然后再次选中幸存节点，再次和非幸存节点合并生成了顶层区域。

Split & Merge 方法

Horowitz 和 Pavlidis 于 1976 年提出Split & Merge 方法，结合了区域划分和区域融合两种策略，两策略交替执行，能实现局部到全局的分割优化

原理

Split & Merge 方法分为两个阶段：基于划分的分割和基于融合的分割

首先我们先执行分割操作，我们将整个图像视为一个初始区域，然后用四叉树算法进行递归分割，变成小的子区域，然后和之前分割算法步骤相同，分割后检查同质性，满不满足继续划分的条件？最后到达阈值时候终止。

然后再执行融合操作，还是之前那一套，检查相似性，如果满足相似性标准就合并，然后用RAG拼接图表示区域连接关系，逐渐合并相邻同质区域，一直到达阈值。

算法流程

上面已经介绍差不多了，首先初始化，构建四叉树，其次Split 阶段，开始划分图像，然后Merge 阶段，开始合并区域，两阶段交替进行，不断优化分割结果。

优缺点

交替划分融合可以平衡过度分割或者欠分割的情况，比如说复杂区域可以不断分割来细化结果，均匀区域可以融合防止冗余

从上图可见，这个方法的缺点在于分块情况明显，纹理复杂的区域存在过多的小块

Graph-Cut 分割方法

我们利用图切割算法找到最佳的分割方案，来将图像分割成不同区域。

原理

图像被表示为一个无向图 G = (V, E)：

• 节点集 V：每个节点代表图像中的一个像素或区域。
• 边集 E：连接节点的边，表示像素之间的相似性关系。

切割

切割是从图中选取一组边，从而将图划分为两个子集 A 和 B。切割是有代价的，其代价被定义为切割边的权重之和:

• W(u, v) 是边 (u, v) 的权重，表示像素 u 和 v 的相似性。
• W(A, B) 表示从 A 到 B 的所有被切割边的权重之和。

最优分割

让上面切割代价最小，就是最优分割

A) 最小切割: 需要找到一种切割来让切割代价最小，也就是我们要找到一组权重之和最小的边，将图像划分为两个部分

B) 归一化切割: 最小切割方法可能导致不平衡的分割，比如说孤立小区域，因此我们需要引入归一化因子，平衡切割代价与区域大小，更适合复杂情景

• W(A, V) 和 W(B, V) 表示区域 A 和 B 与整个图的连接权重和。

分割流程

a) 首先将图像像素作为节点，基于相邻像素特征来定义边的权重

b) 利用最小切割或者归一化切割算法来找到最佳切割位置

c) 不断递归分割，对每个部分都应用Graph-Cut，细化分割区域

优缺点

很好的平衡内部区域的相似性和区域的差异性，适合分割复杂图像，避免过度分割问题

计算代价高，不适合处理大规模图像

区域生长

基于种子的分割方法，从一个初始点开始（种子），将与当前区域相邻且满足同质性条件的像素加入到区域中，逐步的生长出整个区域。方法简单直观，但是对初始种子选择和生长条件依赖大。

核心步骤

首先进行种子初始化，可以从一个初始点开始，也可以从一个区域开始，可以手动指定，也可以通过算法自动选择。

然后按照同质性的标准，找到与当前区域相似的像素，把它们加入到区域中，生长过程会一直重复到不再有像素可以加入其中。

如果我们同时有多个初始化种子，那么不同区域会并行增长，如果某个像素邻接多个区域的时候，会根据规则分配到最近的区域。这个时候可能存在多区域竞争问题，也就是不同区域的生长会竞争未分配的像素，这种竞争结果可能导致边界模糊。

生长停止的条件一般是达到某个相似性阈值，也就是区域内像素基本没差，区域间的像素差别很大，所有像素均已分配

算法流程

a) 在初始化操作中，我们先选择一个种子区域 R，并将其边界像素加入一个 FIFO 队列 S（先进先出队列）。

b) 随后进行迭代生长操作:

• 从队列 S 中取出一个像素 p
• 判断像素 p 是否与当前区域 R 同质
• 如果 p 符合条件：
  • 将 p 加入区域 R。
  • 将 p 的未被访问过的邻域像素加入队列 S。

c) 终止条件: 当队列 S 为空时，停止生长，表示区域已经完全扩展。

阈值的影响

阈值决定了像素能否加入当前区域。如果阈值较小，只有非常像的像素才能加入，这样虽然会很精确，但是一方面增加计算量（过度分割），另一方面可能产生像素遗漏，丢失区域。如果阈值很大，那么可能把一些本不相关的区域也划分进来

优缺点

原理简单，容易实现，计算效率高，对于同质区域处理的很好，但是初始种子的选择很重要，阈值的选择很重要，对噪声也很敏感

分水岭算法

这个算法模拟一座山丘被水淹了的过程，按照像素梯度进行区域分割。我们把图像看成一个三位地形，亮的地方是山峰（梯度高的区域，例如边缘），暗的地方是山谷（梯度低的区域，例如区域中心），分水岭算法就可以把它们通过注水的方式分开。

算法流程

首先我们要找到图像的梯度值（橙色的部分），然后逐步注水，水从最低点不断填充低谷，然后随着水位上升不断扩大浸没区域，形成盆地，当不同盆地的水要相遇的时候，也就是分水岭线的时候，这个地方就是边界，因此分水岭线把地形分割成多个独立的区域，这就是最终分割。非常适用于处理图像中的目标分离或者边缘检测。

基于浸没线的分水岭算法（LPE算法） 宇宙无敌复杂

a) 首先我们要通过输入图像的梯度计算梯度范数图像 G，梯度范数指的是图像中像素变化的强度，后续分割的时候要用。

b) 然后我们利用 G 的局部最小值（梯度极小值）来生成二值图像 B，这些局部最小值是图像中潜在的分割边界。

c) 将二值图像 B 中的 1（局部最小值）赋予唯一标签，标签组成标签图E ，这个标签图 E 代表着分割区域，其中每个像素存储着一个区域标签或者未分配标签。

d) 然后按梯度值从低到高顺序遍历图像像素来更新标签，逐步扩展区域确保从低梯度向高梯度区域生长

• 选择图像 G 中梯度值为 g 的像素点 s （尚未被标记的）
• 构造向量 E_s，记录 s 邻域中 E 的所有标签
• 根据邻域标签为像素点 s 分配新标签:
  • 如果 E_s 中存在区域标签或“LPE”标签，分配这些已有标签（代表 s 属于已有区域）
  • 如果 E_s 中没有标签，那么就分配一个新标签 M
• 将所有标记为 S 的像素点添加到列表 L （FIFO顺序队列）

e) 遍历列表 L，每次都从L 中提取一个像素点 s，查看这个 s 邻域的所有标签:

• 如果邻域只有一个区域标签或者LPE标签，则将该标签分配给 s
• 如果邻域中有多个标签冲突，则将 s 标记为 LPE（分水岭线）。
• 将 s 的未被访问的邻域像素添加到 L 中。

f) **新盆地生成：**找到所有标记为 M 的像素点（未明确归属区域的点），使用这些点生成新的二值图像 B，作为下一步新盆地的起点。

g) 更新标签图 E: 对新的二值图像 B 赋予新的区域标签，更新后的标签图 E_M 表示新增的分割区域。

h) 将 E_M 中的新标签合并到标签图 E 中，确保标签值唯一性（避免冲突），通常通过偏移当前最大标签值来调整。

• 数字 1 2 3 代表已经标记的区域，代表不同的盆地
• M 表示未确定的像素，比如说新的区域种子，或者是分水岭线
• S：表示某个区域的边界点。
• 黄色高亮框：表示当前正在处理的像素点。

所以我们可以看到，最开始的初始种子区域被赋予唯一标签 1 2 3 ，然后种子向外扩展，邻域中的像素被加入到相邻的区域，如果一个像素状态不确定，那么就先暂时标记为 M，如果遇到 S 这个情况，那么就说明遇到了分水岭线

接下来我们将不确定的像素 M 分配区域，如果 M 周围只有一个标签，那么标记为区域，并根据邻域情况判断他是新标签还是已知标签，如果有多个标签并且无法归类，那么就是 LPE。

局限性：

图像中梯度的局部极小值过多时，会导致LPE算法产生过多的分割区域（过分割）。

改进方法：

• 在梯度计算之前，对图像进行平滑处理（例如高斯模糊）以减少梯度的局部极小值数量。减少分割的初始区域数量，从而降低过分割现象。

• 替换梯度极小值盆地为先验区域: 不再依赖梯度局部最小值作为算法初始化了，而是我们给他提供一些标记点，比如说先手动把蓝天白云标出来

上面我们介绍了基于梯度的局部极小值与标签传播的分割 LPE 方法，适用于图像梯度显著的场景，现在我们介绍一种可以适用于统计分析的场景（如纹理区域分割）的方法——马尔可夫分割，它更关注随机性和局部依赖性

马尔可夫分割原理

马尔可夫分割是一种基于**马尔可夫随机场（Markov Random Field, MRF）**的图像分割方法，它将图像分割建模为一种概率优化问题，利用像素间的局部依赖性来推断分割结果。

观察图像 A 的建模

图像被视为多个高斯随机过程的拼接结果，也就是说，每个区域都是由一个随机过程生成的，每个像素点强度值具有特定的统计特性（例如均值和标准差）。因此我们的目的就是根据像素的强度分布，把像素划分到不同的区域。

**分割结果\Lambda的建模 **

分割结果被建模为一个隐藏的马尔可夫场随机过程，图像中的每个像素的标签都是一个随机变量，标签分布会服从马尔可夫场的性质: 像素标签的概率仅仅由它邻域像素的标签来决定，专业一点叫做，条件概率仅仅依赖于邻域信息。

符号定义

• S（像素集合）： S = \{s_1, s_2, \dots, s_N\}，图像中的像素集合，包含N个像素点

• A（强度图像）： A = \{a_s \,|\, s \in S\}，每个像素点 s 的强度值构成强度图像 A。

• \Lambda（标签图像）： \Lambda = \{\lambda_s \,|\, s \in S\}，每个像素 s 的分割标签 \lambda_s 构成标签图像 \Lambda。

应用场景

马尔可夫分割适用于具有明确统计特性的图像场景，特别是涉及纹理、模式或统计特性区域的分割任务。

• 一阶统计量：均值（表示每个区域内像素值的平均强度）
• 二阶统计量：标准差（表示区域内像素强度的变化幅度）

马尔可夫分割数学建模

后验概率的分解

我们要找到能让后验概率 P(\Lambda | A) 最大化的那个分割标签图像 \Lambda，因此根据贝叶斯公式，后验概率分布 P(\Lambda | A) 被分解为两个项：

• P(A | \Lambda)：条件似然项，描述给定标签图像 \Lambda 时，观测图像 A 的生成概率。
• P(\Lambda)：先验概率项，描述标签图像 \Lambda 的空间一致性。

条件似然项 P(A | \Lambda)

条件似然项假设像素强度值相互独立，可以分解为：

• 对每个像素点 s，强度值 a_s 依赖于其所属的标签 \lambda_s。

高斯分布建模

假设每个标签 \lambda_s 对应一个高斯分布，像素强度 a_s​ 的条件概率为：

• \mu_{\lambda_s}：标签 \lambda_s 的强度均值。
• \sigma_{\lambda_s}：标签 \lambda_s 的强度标准差。

条件似然项 P(A | \Lambda) 建模了像素强度分布，适用于纹理区域或强度有统计特性的场景。这正是之前提到的基于一阶和二阶统计量分割图像的基础。

先验概率项 P(\Lambda)

先验概率项 P(\Lambda) 被建模为一个马尔可夫随机场，描述标签图 \Lambda 的空间一致性：

• \nu(s)：像素点 s 的邻域。

这表明每个像素点的标签 \lambda_s 仅依赖于其邻域 \nu(s) 的标签状态。

与吉布斯场的等价性

根据马尔可夫场和吉布斯场的等价性，先验概率 P(\Lambda) 可以表示为：

• U(\Lambda)：系统的能量函数，表示标签图 \Lambda 的能量代价。
• 能量越低，P(\Lambda) 越大，对应更可能的标签分布。

能量函数的定义

能量函数 U(\Lambda) 表示为所有“团”（cliques，即互为邻域的像素集合）的代价总和：

• W_c(\Lambda_c)：团 c 中标签的代价函数。
• C：图像中所有的团集合。

团代价函数 W_c 的定义

一个简单的形式是自逻辑势函数（potentiel autologistique）：

• \beta：正则化参数，控制分割的平滑程度。
  • \beta > 0 倾向于邻域标签一致（平滑分割）。
  • \beta < 0 倾向于邻域标签不一致（更复杂分割）。

目标函数形式：

综上所述，马尔可夫分割问题等价于最小化一个能量函数 E(A, \Lambda)，即找到最优的标签图 \Lambda：

• P(A | \Lambda)：条件似然项，表示观测图像 A 在给定分割标签 \Lambda 下的概率。
• P(\Lambda)：先验概率项，表示标签 \Lambda 的空间一致性。

通过对概率取负对数，将分割问题从概率最大化转化为能量最小化。

能量函数的分解

能量函数 E(A, \Lambda) 包括两部分：条件似然项和先验项：

• 第一部分（条件似然项）：

  \sum_{s \in S} \left( \log(\sigma_{\lambda_s} \sqrt{2\pi}) + \frac{(a_s - \mu_{\lambda_s})^2}{2\sigma_{\lambda_s}^2} \right)
  • 对每个像素点 s 计算高斯分布的代价，基于标签 \lambda_s 的统计特性（均值 \mu_{\lambda_s} 和标准差 \sigma_{\lambda_s}）。
  • 这一项与观测图像 A 的强度分布相关，表示像素值 a_s 偏离其标签区域特性的程度。

• 第二部分（先验项）：

  \sum_{c \in C} W_c(\Lambda_c)
  • 通过所有“团”（cliques）的代价函数 W_c(\Lambda_c)，描述标签 \Lambda 的邻域一致性。
  • 这一项与马尔可夫场建模的先验概率 P(\Lambda) 对应。

局部能量 e_s 表示单个像素 s 的能量贡献：

• 第一部分（高斯代价）：像素 s 的强度值 a_s 偏离其标签 \lambda_s 的统计特性的程度。
• 第二部分（邻域代价）：像素 s 与其邻域标签一致或不一致的代价。

全局能量 E(A, \Lambda) 是所有像素点局部能量 e_s 的累加：

优化算法：ICM 和 Metropolis 方法

在上述马尔可夫分割中，图像分割问题被建模为最小化能量函数 E(A, \Lambda) 的优化问题，目标是找到一个标签分配 \Lambda，使得能量函数最小化。

因此介绍两种常用优化算法：ICM（迭代条件模式）和Metropolis 方法，来解决马尔可夫分割能力最小化问题。

iterated conditional mode (ICM)

ICM 是一种确定性贪心算法，通过逐步优化每个像素的标签来最小化局部能量。它的特点是简单高效，但容易陷入局部最优，并且容易被噪声干扰，难以得到全局最优的分割结果。

a) 首先进行初始化，从一个质量较高的初始分割标签开始，质量较高意味着初始标签要尽量接近全局最优，初始标签越好，那么就更容易找到全局最优的结果

b) 然后我们进行迭代优化，在收敛条件没有满足的时候，依次遍历每个像素点 s，并执行以下步骤：

• 首先遍历像素点中的每个可能的标签，然后计算局部能量 e_s(\lambda_s)，包括数据项和先验项
• 数据项：衡量像素强度 a_s 与标签 \lambda_s 的匹配程度。
• 先验项：衡量标签 \lambda_s 与邻域标签的一致性。
• 然后为 s 分配使 e_s(\lambda_s) 最小的新标签 \lambda_s

c) 这样不断循环迭代，一直到整体能量E(A, \Lambda) 收敛到一个局部最小值

这个算法的优点是，是确定性算法，保证收敛，缺点是初始标签一定要选好，不然容易局部最优，算法就废了。

Metropolis 方法

Metropolis 是一种随机优化算法，通过引入随机性和接受“坏解”的机制来避免陷入局部最优。它适合优化复杂的能量函数，尤其是在分割问题具有多个局部最优时。

首先我们先进行初始化，生成初始标签分配\Lambda，并且设置温度参数 T，温度参数 T 控制接受“坏解”的概率。温度设置的越高，算法越容易接受坏解；温度设置的越低，算法更倾向于优化当前解。

然后进入迭代过程，依次遍历每个像素点 s，并且执行以下步骤:

• 先随机生成一个候选标签 x，然后计算候选标签 x 对应的局部能量 e_s(x)，计算当前标签 \lambda_s 的局部能量 e_s(\lambda_s)，计算能量变化 \Delta e = e_s(x) - e_s(\lambda_s)
• 根据条件决定是否接受新标签 x：
  • 如果 e_s(x) < e_s(\lambda_s)，直接接受 x。
  • 如果 e_s(x) \geq e_s(\lambda_s)，以概率
    e^{-\Delta e / T}
    接受 x，其中 \Delta e = e_s(x) - e_s(\lambda_s)。
• 随着迭代进行，逐步降低温度 T，减少接受坏解的概率。

最后收敛，当温度接近于 0 的时候，标签分配且不再变化的时候，算法收敛，获得分割结果。

这个算法的优点是，由于它是随机算法，可以接受局部劣化（坏解）状态，可以跳出局部最优。同时温度不断降低，算法搜索范围会逐渐收缩，可以最后收敛到全局最优解。

相比 ICM，metropolis 的随机性使得它适合复杂的能量函数优化，尤其是在存在多个局部最优的情况下能找到更优解。但代价是执行时间较长，效率低于 ICM。

模拟退火算法

模拟退火（Simulated Annealing）是对 Metropolis 算法的改进和扩展，是一种全局优化算法，基于物理学中的退火过程。通过引入温度参数 T，算法在初期允许较大的随机跳跃，逐步探索全局解，随着温度逐步降低，随机性减小，算法逐渐收敛到一个局部解，最终可能接近全局最优。

原理

模仿金属退火的过程： 金属在高温下具有较大的粒子运动自由度，能够探索多种状态。随着温度逐渐降低，粒子运动受限，最终趋于稳定状态。

算法流程

a) 首先初始化，生成初始标签分配 \Lambda，作为初始分割方案。设定一个较高的初始温度，用于大随机跳跃探索全局解

b) 然后进入优化收敛过程，针对每个像素点 s 进行以下步骤:

• 随机选择一个候选标签 x，候选解表示像素 s 被赋予新标签 x。
• 算新标签 x 的局部能量 e_s(x)，以及当前标签 \lambda_s 的能量 e_s(\lambda_s)。
• 条件接受标签 x：
  • 如果 e_s(x) < e_s(\lambda_s)，直接接受标签 x。
  • 如果 e_s(x) \geq e_s(\lambda_s)，以概率
    e^{-\Delta e / T}
    接受候选解 x，其中 \Delta e = e_s(x) - e_s(\lambda_s)。
  • 按照规则
    T \leftarrow kT
    逐步降低温度 T，其中 k \in [0.8, 0.999]是递减因子，用于控制温度下降的速度。

优缺点

继承了 Metropolis 算法的随机性。在高温阶段允许接受劣解，能够避免陷入局部最优解。控制温度逐步下降，可以减少随机性，最终收敛到一个稳定解，可能接近全局最优。更适合复杂能量函数优化问题，例如之前的

初始温度 T 和递减因子 k 的选择直接影响算法性能，并且算法计算复杂度高

Superpixels 方法

Ren和Malik在2003年提出Superpixels方法，通过聚合相邻像素，将其分组为更大的“超级像素单元”，代替逐像素处理。

核心思想

把图像中的相似像素（如颜色相似、纹理一致）聚合成一个个区域，称为“Superpixels”，每个 Superpixel 是一组相邻的像素，具有相似的视觉属性。因此分组是基于图像的内容特征，而不是简单的网格划分，更加接近真实图像的分割结果。

同时相比逐像素处理，大大提高了计算效率。

Superpixels算法种类

• Watershed 方法：基于分水岭算法（如 Compact Watershed）。

• 聚类方法：如 SLIC（Simple Linear Iterative Clustering），基于颜色和空间位置聚类，是最流行的方法之一。

• 图论方法：如 Random Walks，利用图的连接关系生成 Superpixels。

• 路径方法：如 Path Finder，通过像素的路径相似性生成 Superpixels。

• 密度方法：如 Mean Shift，利用像素的密度分布生成 Superpixels。

• 轮廓进化方法：如 Turbo Pixels，模拟轮廓进化过程生成 Superpixels。

算法特性

• Superpixels 的数量直接决定了分割的精细程度。
• 紧致的 Superpixels 边界更平滑，而非紧致的 Superpixels 更能贴合图像内容。

SLIC（Simple Linear Iterative Clustering）

SLIC 是一种基于 k-means 聚类思想的 Superpixels 分割算法，通过混合颜色和空间距离，生成紧凑、均匀的 Superpixels，既保留图像的局部特性，又显著减少处理单元数量。

几何特性

固定数量的 Superpixels：SLIC 根据规则网格初始化聚类中心，控制 Superpixels 的数量和大小，生成平均尺寸一致的区域。

混合距离度量：SLIC 使用混合距离 D，综合衡量颜色相似性和空间位置紧致性。

• 颜色距离 d_{lab}：反映 Superpixels 对图像内容的依附性。

• 空间距离 d_{xy}：控制 Superpixels 的形状紧致性。

  d_{xy} = \sqrt{(x_k - x_i)^2 + (y_k - y_i)^2}

• 参数 m：控制颜色和空间距离的权重。

  • m 大：更规则的形状，内容细节可能忽略。
  • m 小：更贴合图像内容，但形状可能不规则。

• 参数 S：控制 Superpixels 的平均大小，影响分割细腻程度。

复杂度控制： SLIC限制搜索范围为每个中心的 2S \times 2S 邻域，时间复杂度与像素数量线性相关，效率较高。

算法流程

首先进行初始化，在规则网格上初始化聚类中心 C_k，表示颜色和空间位置 [l_k, a_k, b_k, x_k, y_k]。将初始聚类中心移动到局部梯度最小的位置，以提高结果的稳定性。

然后进入分配阶段，在每个中心的 2S \times 2S 窗口内，计算像素到聚类中心的混合距离 D。然后将像素分配给最近的聚类中心。

最后是更新阶段，我们重新计算每个聚类的中心点为当前聚类中所有像素的平均值。不断迭代，重复分配和更新阶段，一直到 E 收敛或达到最大迭代次数：

可以进行额外的边界后处理，合并小区域，保证分割的连贯性

优缺点

效率高，复杂度低，适用于大规模图像处理，可以通过 m 和 S 调节分割细腻程度与区域规则性。

Mumford-Shah 模型

核心思想

Mumford-Shah 模型通过最小化一个全局能量函数，将图像分割成多个均匀区域，兼顾区域的内容一致性和边界的规则性，生成全局优化的分割结果。

全局能量函数形式

Mumford-Shah 模型的全局能量函数为：

• E_i(R_i)：内部能量，描述分割区域内的均匀性；
• E_C(R_i)：复杂性能量，描述分割边界的长度或其他复杂性。
• \lambda：权重参数，控制两个能量项的相对权衡性。
  • \lambda小：复杂性限制较弱，分割边界更多，细节更加丰富；
  • \lambda大：复杂性限制较强，边界更简单，分割更规则。

(A) 区域内部能量 E_i(R_i)

表示区域 R_i 内像素值的一致性，基于统计特性定义：

• V为区域的协方差矩阵，NT_r为核迹运算符，描述区域内部的统计特性。

(B) 复杂性能量 E_C(R_i)

• 描述区域边界的长度或复杂性，鼓励分割结果更加规则。

• 边界过多会增加复杂性能量，从而被模型惩罚。

可变形模型（Deformable Model）

可变形模型是一种基于轮廓演化的图像分割方法，目标是通过迭代优化，使初始轮廓逐步贴合图像目标的边界。其经典方法是活动轮廓模型（Active Contour Model），又称“蛇”（Snakes）。

Kass等人在1987年提出了活动轮廓模型， 它通过能量最小化和迭代更新，实现轮廓的自适应演化。其初始条件和能量函数的设计关键，是图像分割中的重要方法之一。

能量函数

活动轮廓模型的能量函数表示为：

• 内部能量（平滑性约束）： 控制着曲线的几何性质，保证曲线平滑且连续
  • \alpha: 控制曲线长度，抑制曲线过长。
  • \beta: 控制曲线弯曲程度，避免曲线不连续。
• 外部能量（图像驱动）： 依赖图像梯度\nabla I，驱动曲线靠近强边缘区域。
• \lambda: 平衡内部能量和外部能量的权重。

离散化与迭代过程

首先离散化初始轮廓，首先它被离散为 N 个点，形成向量表示：

• 其中X_0和Y_0分别表示曲线各点的横纵坐标。

然后进行迭代优化，每次迭代中，都会更新新的曲线点位置:

• A: 包含\alpha和\beta的矩阵，描述内部能量的约束。
• \gamma: 时间步长，控制轮廓移动的速度。
• f_X, f_Y: 由图像梯度计算的外部能量。

迭代更新直到曲线收敛到能量最小值，贴合目标边界。

优缺点

• 能够生成平滑的分割边界，避免噪声干扰，在连续边界的目标分割中效果良好。

• 依赖初始轮廓位置，若初始轮廓偏离目标，可能无法收敛到正确边界。容易陷入局部最优，尤其是在复杂图像中。