基于图割的快速的近似能量最小化

使用图割的快速近似能量最小化姓名：梁瑷云时间：2016.5.17目录摘要早期视觉的能量最小化相关工作算法综述寻找最优交换移动（算法）寻找最佳扩展移动（算法）

最优性能POTTS

模型实验结果结论摘要作者提出两种基于图割的算法：α-expansion和α-β-swap移动算法，可以同时改变标签任意大的像素集。目的:找到一个有效的局部最小值，已达到找全局最小值的目的。能处理更一般的能量函数。主要用于图像恢复、立体声、运动方面。精确度能达到98%。早期视觉的能量最小化

许多早期视觉领域，通常需要估计一些空间（像素平面）上变化的量（如图像灰度、视差大小）。这些量在块的内部变化平滑，在块与块之间（物体边界）变化很大，像素点p∈P被分配给有限集合fp∈L。将每个像素映射到标签集中的某个标签上，这里标签函数（映射）

f

不仅需要满足分块平滑的特点而且需要和观测到的数据一致。

能量函数：E(f)=Esmooth(f)+Edata(f)

在能量函数的构造上一般有数据约束和平滑约束，体现了区域内部的连续性和边界的不连续性。Esmooth(f)

表达的是

f

分块不平滑的程度，Edata(f)

表达的是标签函数

f

与观测到数据的不一致性。Edata(f)

的一般形式是

Edata(f)=∑(p∈P)Dp(fp)

Dp来度量标签与观测数据的一致性，在图像恢复Dp(fp)=(fp-Ip)2,Ip表示在像素点

p

处的灰度值

。（Edata(f)在本文不作讨论）能量最小化难点：计算花销大，很多能量函数有许多局部最小值(非凸)，空间维度多。本文考虑的能量函数为：

Esmooth=∑{p,q}∈NVp,q(fp,fq),N：相邻像素对集合。Vp,q(fp,fq)

表示像素对

{p,q}

在标签函数

f

下生成的标签

(fp,fq)

之间的距离（相似度、平滑程度）

Dp非负，其他任意。

该论文中提出了两种对任意有限大小的标签集

L

进行近似能量最小化的算法：α-expansionand

α-β-swap，分别针对两种互作用势（interactionpenalty）：度量（metric）、半度量（semi-metric）。在标签L的空间中V是否以下条件满足：则V是一个度量。如果只满足（2）、（3）则为半度量。需要注意的是不论是度量还是半度量互作用势，都包含重要的“非连续性保留”的互作用势。这个特性在后续证明中是会用到的，也说明了两种算法分别适用的情况相关工作之前的算法大多数是寻找局部最小值，存在低效率、收敛速度慢的问题1.相对于能量函数来说，局部能量最小化的办法都有哪些？标准移动：1）迭代条件模式（ICM）对于每一个像素,标签赋予最大的减少能量函数的选择,直到收敛到局部最小值。

2）

模拟退火：优：优化任意能量函数。缺：任意能量函数最小化需要指数时间和结果模拟退火速度非常慢。时间够长，能找到全局最小值。效率低。

3）平均场退火算法：

梯度下降法，通常仅能保证能量函数的局部最优，并且依赖于近似的数值计算模式(如有限差分、有限元)，需要对数值计算进行很好的设计以保证解的鲁棒性和收敛性

图割：通过提供代价函数(costfunction)，将区域、边界及一些拓扑限制很自然地融入到代价函数中，能够实现能量的全局最优化。算法综述1、分割和移动空间

每一个标签映射函数

fp∈L

与图像分割方式是一一对应的关系，而

fp（后简写为

f）是能量函数的自变量，因此我们可以称所有可能的

f

的取值所组成的集合为操作空间或移动空间.用数学描述如下：

任意一种标签方式

f

都能通过像素的一个分割来表示：

P={Pl|l∈L},

其中

Pl

表示标签为

l的像素点集合。可以看到标签方式

f

与分割

P

成一一对应关系。

如图2：每一次标签调整，也就是f在操作空间中的每一次移动遵循一定规定的我们称之为交换（swap）和扩张（expansion）操作，swap和expansion操作的具体意义：swap:给定一对标签α,β，从一个分割P到另一个分割P′的移动（变动）在满足以下条件时称之为一次α-βswap标签调整操作：对任意l≠α,β都有Pl=Pl’。也就是说在一次α-β-swap调整操作后，一些原来是α标签的像素被标记为β，一些原来是β标签的被标记为α，简而言之就是被标记为α,β标签的像素集合之间进行了交换。(图2c)

-expansion:给定一个标签α，从一个分割P到另一个分割P′的移动（变动）在满足以下条件时称之为一次α-expansion标签调整操作：对任意标签l≠α都有Pl’⊂Pl。也就是说在一次α-expansion调整操作中，除了α标签以外的集合都是原来的子集，简而言之就是被标记为α标签的像素集合扩大了，这也是该算法名称的由来。(图2d)上面定义了一次expansion（swap）操作对象是具体的一（两）个标签集合，和操作规范，并没说明具体哪些像素进行扩张或交换操作。对不同的操作对象，必然产生截然不同的expansion（swap）操作，相同的操作对象，对不同的像素操作，也是不同的expansion（swap）操作。标准移动：ICM和退火使用标准移动只允许一个像素改变其强度,标准移动的实例如图2（b）理解：

在进行能量函数的最优化过程中，仅改变图像中一个像素点的视差标记值,如图2（b）示。通过这种标准移动很容易遇到局部极小值，从而不能准确的计算出能量函数的最小值。而α-expansion移动则是对那些视差标记不为α的集合同时进行大规模的优化（多个像素同时进行标准移动），使其中的一部分像素点的视差标记重新被标记为α，剩余的像素点集合的视差标记值保持不变，如图4-2（c）示，视差标记为β和γ中的部分像素点被重新标记为α。而α−β交换移动则是在一次交换移动（可以理解为优化）的过程中，视差标记α像素点集合和视差标记为β的像素点集合同时大规模进行交换（swap），而那些视差标记不等于α和β的像素点集合则不改变，如图4-2（d）示，标记为γ的像素集合没有发生改变，视差标记α像素点集合和视差标记为β进行了部分交换。

算法流程和属性

图3算法：高效的基于图割的方法找到最优的α-β-swap或者α-expansion标签f，可以有效地找到相应的局部最小值.算法如下：算法步骤：1、2迭代；2、3、4一个循环；每个周期中扩展和交换算法执行一次（固定/随机执行），其中一个循环需要|L|²迭代，一个循环在扩张算法中需|L|²迭代。

图中上部分是

swap

算法，下部分是

expansion

算法，可以看到两种算法基本结构相同：在3中遍历所有可能的标签调整对象，并对该调整对象具体调整方式寻求最优

f^，如果找到的当前调整对象的最优调整有效即：

E(f^)<E(f)

使得能量下降，则接受这个调整

f:=f^。对标签不断的进行调整，直到没有标签调整能使能量函数下降为止。

两种算法区分就在对当前标签对象进行具体调整的方式3.1-3.2这两步上，两种标签调整方式在上一部分已经进行了说明。

该文中的算法就是每一次在整个操作空间的一个有限的（swap

or

expansion

操作对象所决定）子空间内寻找最优点并移动，直到在一次操作中对能量没有减小作用。此时得到的能量值是一个局部极小值，并不是全局极小值，有相关证明expansion算法得到的标记与全局最优成可控的倍数关系。

给定一幅无向带边权图G=(V,E),V是顶点（vertex）集，对应图像的像素点为P，V中包含了两个特殊的节点（终端），源节点source（S），汇节点sink（T），E为边集，t-links(terminallinks)、n-links(neighborhoodlinks).图的一个割就是边集合E的一个子集C⊂E称为割集，有它导出子图G(C)=(V,E-C).使得在图中去除割边集合后源点和汇点不能联通，一个割的代价记为|C|就是割集中所有边权之和。最小割问题就是找到一个割使得代价最小。这是一个很成熟的问题，已经提出了不少低阶多项式复杂度的算法，例如Ford-Fulkerson，Push-relabel，这些算法在实际中都是近乎线性复杂度。3、图割本文图割最关键步骤就是在图

3.1中：在当前标签对象的一次

swap

或

expansion

调整中找到的最优标签方式

，这里我们通过图割的方法来有效的找到

。

寻找最优swap移动

对于一个输入的标记方式

f（也即是分割方式

P）和一对标签

α,β，我们期望找到一个具体的标记方式

f^

，使得总能量

E

在此时

f

上的

α-β

标签对的swap调整操作中最小。注意这里的最小是针对当前输入的标记方式

f

和

α-β

标签集上的一次swap操作而言的。

这里采用构建图

Gαβ=⟨Vαβ,Eαβ⟩

并在图上解最小割问题的方式来找到当前

f

在标签对上

最佳α-β

-swap调整。这个图的结构是由当前

f

和标签对

α-β

所决定的。

基于当前分割f和标签对α-β来构建图Gαβ的，在一维情形下：

图4中，顶点集合包含终端α,β和像素点p∈Pα∪Pβ，p与终端分别连接边，称之为t-link，每对相邻的像素点之间连接一条边，称之为n-link，我们用{p,q}∈N来表示两个像素相邻。那么图Gαβ

的边集合每条边的权值：

最小割与最佳swap移动对于构造的图中的一个割有如下的几种情况：从图中可以看到每个像素顶点有且仅有一条t边在割集中（也意味着每个像素只能拥有一个标签），如果两个相邻的像素被标记为不同的标签，那么他们之间的n边也属于割集。

证明：

(f

的最佳

α-β

swap是

f^=

fc，这里

C

是图

Gαβ

上的最小割。)

寻找最优扩展移动

对于一个输入的标记方式

f（也即是分割方式

P）和一个标签

α，我们期望找到一个具体的标记方式

f^

使得总能量

E

在此时

f

上的

α

标签的expansion调整操作中最小。

这里采用构建图

Gα=⟨Vα,Eα⟩

并在图上求解最小割问题的方式来找到当前

f

对标签

α

的最佳expansion调整。图的结构是由当前

f

和标签

α

所决定的，并假设平滑项

V{p,q}

是度量的，也就是满足三角不等式。从一个定理中得到一个推论讲明了我们主要结果就是所需的标签

f^是

fc

。C是Gc上的最小割构建图基于当前分割

f

和标签

α

来构建图

Gαβ

的，在一维情形下：

终端分别代表标签

α

和其他标签

α¯，与上一算法的不同之处在于：

-图在整幅图像的所有像素点上构造；

-在相邻且具有不同标签顶点（{p,q}∈Nand

fp≠fq）间添加额外的辅助节点

a{p,q}，也就是在分割边界上需要辅助节点；

-相应的对于辅助节点我们需要添加额外的三条辅助边，分别与两个边界点和

α¯

相连，并且在构造权重时使得他们之间满足三角不等式。

3条辅助边集：标签集：边缘集：

最小割与最佳expansion移动

图中中间情形：当之前相邻边界像素保留原标签（fa=α¯），那么由于中间的辅助节点三条边满足三角不等式，就必须切t边（tα¯a）。

-图中右边情形：当之前相邻边界像素其中一个变成

α

标签，另一个保留原标签，那么还是由于三角不等式，e{p,a}

必定包含在割集中。

三角不等式在这里的意义就是尽量只切辅助节点的某一条边。

与上一部分类似