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

1、使用图割的快速近似能量最小化 姓名：梁瑷云 时间：2016.5.17 目录 l摘要 l早期视觉的能量最小化 l相关工作 l算法综述 l寻找最优交换移动（算法） l寻找最佳扩展移动（算法） l最优性能 lPOTTS模型 l实验结果 l结论 摘要 作者提出两种基于图割的算法：-expansion和-swap移 动算法，可以同时改变标签任意大的像素集。目的:找到一个有 效的局部最小值，已达到找全局最小值的目的。能处理更一般 的能量函数。主要用于图像恢复、立体声、运动方面。精确度 能达到98%。 早期视觉的能量最小化 许多早期视觉领域，通常需要估计一些空间（像素平面）上变化的量（ 如图像灰度、视差大小

2、）。这些量在块的内部变化平滑，在块与块之间（ 物体边界）变化很大，像素点pP被分配给有限集合fpL。将每个像 素映射到标签集中的某个标签上，这里标签函数（映射）f不仅需要满足 分块平滑的特点而且需要和观测到的数据一致。 能量函数： E(f)=Esmooth(f)+Edata(f) 在能量函数的构造上一般有数据约束和平滑约束，体现了区域内部的连 续性和边界的不连续性。Esmooth(f)表达的是f分块不平滑的程度，Edata(f)表达的是标签 函数f与观测到数据的不一致性。Edata(f)的一般形式是 Edata(f)=(pP)Dp(fp) Dp来度量标签与观测数据的一致性，在图像恢复Dp(fp

3、)=(fp-Ip)2,Ip表 示在像素点p处的灰度值。（Edata(f)在本文不作讨论） 能量最小化难点：计算花销大，很多能量函数有许多局部最小值(非 凸)，空间维度多。 本文考虑的能量函数为： Esmooth=p,qNVp,q(fp,fq), N：相邻像素对集合。Vp,q(fp,fq)表示像素对p,q在标签 函数f下生成的标签(fp,fq)之间的距离（相似度、平滑程 度）Dp非负，其他任意。 该论文中提出了两种对任意有限大小的标签集L进行近似能量最小 化的算法：-expansionand-swap，分别针对两种互作用势（ interactionpenalty）：度量（metric）、半度量（

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

5、拟退火速度非常慢。时间够长，能找到全局最小值。效率低。 3）平均场退火算法： v梯度下降法，通常仅能保证能量函数的局部最优，并且依赖于近似的数值计算 模式(如有限差分、有限元)，需要对数值计算进行很好的设计以保证解的鲁棒 性和收敛性 v图割：通过提供代价函数(costfunction)，将区域、边界及一些拓扑限制很自 然地融入到代价函数中，能够实现能量的全局最优化。 算法综述 1、分割和移动空间 每一个标签映射函数fpL与图像分割方式是一一对应的关系，而 fp（后简写为f）是能量函数的自变量，因此我们可以称所有可能的f 的取值所组成的集合为操作空间或移动空间. 用数学描述如下： 任意一种标签方

6、式f都能通过像素的一个分割来表示：P=Pl|lL,其中 Pl表示标签为l的像素点集合。可以看到标签方式f与分割P成一一对 应关系。 如图2： 每一次标签调整，也就是f在操作空间中的每一次移动遵循一定规定的我们称之 为交换（swap）和扩张（expansion）操作，swap和expansion操作的具体意 义： -swap:给定一对标签,，从一个分割P到另一个分割P的移动（变动）在满 足以下条件时称之为一次-swap标签调整操作：对任意l,都有Pl=Pl 。也就是说在一次-swap调整操作后，一些原来是标签的像素被标记为 ，一些原来是标签的被标记为，简而言之就是被标记为,标签的像素 集合之间进

7、行了交换。(图2c) -expansion:给定一个标签，从一个分割P到另一个分割P的移动（变动）在 满足以下条件时称之为一次-expansion标签调整操作：对任意标签l都有 PlPl。也就是说在一次-expansion调整操作中，除了标签以外的集合都是 原来的子集，简而言之就是被标记为标签的像素集合扩大了，这也是该算法名 称的由来。(图2d) 上面定义了一次expansion（swap）操作对象是具体的一（两）个标签集合，和 操作规范，并没说明具体哪些像素进行扩张或交换操作。对不同的操作对象，必 然产生截然不同的expansion（swap）操作，相同的操作对象，对不同的像素操 作，也是不

8、同的expansion（swap）操作。 -标准移动：ICM和退火使用标准移动只允许一个像素改变其强度,标准移 动的实例如图2（b） 理解： 在进行能量函数的最优化过程中，仅改变图像中一个像素点的视差标记值,如图 2（b）示。通过这种标准移动很容易遇到局部极小值，从而不能准确的计算出能量 函数的最小值。而-expansion移动则是对那些视差标记不为的集合同时进行大 规模的优化（多个像素同时进行标准移动），使其中的一部分像素点的视差标记重 新被标记为，剩余的像素点集合的视差标记值保持不变，如图4-2（c）示，视差 标记为和中的部分像素点被重新标记为。而交换移动则是在一次交换移 动（可以理解为优

9、化）的过程中，视差标记像素点集合和视差标记为的像素点 集合同时大规模进行交换（swap），而那些视差标记不等于和的像素点集合则 不改变，如图4-2（d）示，标记为的像素集合没有发生改变，视差标记像素点 集合和视差标记为进行了部分交换。 算法流程和属性 图3算法：高效的基于图割的方法找到最优的-swap或者-expansion标 签f，可以有效地找到相应的局部最小值.算法如下： 算法步骤：1、2迭代；2、3、4一个循环；每个周期中扩展和交换算法执行一次（固定/随机执 行），其中一个循环需要|L|迭代，一个循环在扩张算法中需|L|迭代。 图中上部分是swap算法，下部分是expansion算法，可

10、以看 到两种算法基本结构相同：在3中遍历所有可能的标签调整对象，并对 该调整对象具体调整方式寻求最优f，如果找到的当前调整对象的最 优调整有效即：E(f)E(f)使得能量下降，则接受这个调整f:=f 。对标签不断的进行调整，直到没有标签调整能使能量函数下降为止。 两种算法区分就在对当前标签对象进行具体调整的方式3.1-3.2这两步 上，两种标签调整方式在上一部分已经进行了说明。 该文中的算法就是每一次在整个操作空间的一个有限的（ swaporexpansion操作对象所决定）子空间内寻找最优点并移动， 直到在一次操作中对能量没有减小作用。此时得到的能量值是一个局部 极小值，并不是全局极小值，有

11、相关证明expansion算法得到的标记与 全局最优成可控的倍数关系。 给定一幅无向带边权图 G=(V,E), V是顶点（vertex）集， 对应图像的像素点为P，V中包含了两个特殊的节点（终端）， 源节点 source （S），汇节点 sink（T），E为边集，t- links(terminal links)、n-links(neighborhood links).图 的一个割就是边集合 E 的一个子集 CE 称为割集，有它导 出子图G(C)=(V,E-C).使得在图中去除割边集合后源点和汇点 不能联通， 一个割的代价记为 |C| 就是割集中所有边权之和。 最小割问题就是找到一个割使得代价最

12、小。这是一个很成 熟的问题，已经提出了不少低阶多项式复杂度的算法，例如 Ford-Fulkerson，Push-relabel，这些算法在实际中都是近乎 线性复杂度。 3、图割 本文图割最关键步骤就是在图3.1中：在当前标签对象的一次swap或 expansion调整中找到的最优标签方式，这里我们通过图割的方法来有 效的找到。 寻找最优swap移动 对于一个输入的标记方式f（也即是分割方式P）和一对标签,，我 们期望找到一个具体的标记方式f，使得总能量E在此时f上的-标签 对的swap调整操作中最小。注意这里的最小是针对当前输入的标记方式f 和-标签集上的一次swap操作而言的。这里采用构建图

13、 G= V,E 并在图上解最小割问题的方式来找到当前f在标签对上 最佳-swap调整。这个图的结构是由当前f和标签对-所决定的。 基于当前分割f和标签对-来构建图G的，在一维情形下： 图4中，顶点集合包含终端, 和像素点 pPP，p 与终端分别连接边，称之为 t-link，每对相邻的像素点之间 连接一条边，称之为 n-link，我们用 p,qN 来表示两个 像素相邻。那么图 G 的边集合 每条边的权值： 最小割与最佳swap移动 对于构造的图中的一个割有如下的几种情况： 从图中可以看到每个像素顶点有且仅有一条t边在割集中（也意味着每个像素只能 拥有一个标签），如果两个相邻的像素被标记为不同的标

14、签，那么他们之间的n边也 属于割集。 v v v v证明： v (f的最佳-swap是f=fc，这里C是图G上的最小割。) 寻找最优扩展移动 对于一个输入的标记方式f（也即是分割方式P）和一个 标签，我们期望找到一个具体的标记方式f使得总能量E 在此时f上的标签的expansion调整操作中最小。 这里采用构建图G= V,E 并在图上求解最小割问题的 方式来找到当前f对标签的最佳expansion调整。图的结 构是由当前f和标签所决定的，并假设平滑项Vp,q是度 量的，也就是满足三角不等式。 从一个定理中得到一个推论讲明了我们主要结果就是所需的标签f是fc。C是 Gc上的最小割 构建图 基于当

15、前分割f和标签来构建图G的，在一维情形下： 终端分别代表标签和其他标签，与上一算法的不同之处在于： -图在整幅图像的所有像素点上构造； -在相邻且具有不同标签顶点（p,qNandfpfq）间添加额外的辅助节点ap,q， 也就是在分割边界上需要辅助节点； -相应的对于辅助节点我们需要添加额外的三条辅助边，分别与两个边界点和相连 ，并且在构造权重时使得他们之间满足三角不等式。 3条辅助边集： 标签集： 边缘集： 最小割与最佳expansion移动 v 图中中间情形：当之前相邻边界像素相邻边界像素保留原标签（fa=），那么由于中间的辅助 节点三条边满足三角不等式三条边满足三角不等式，就必须切t边（t

16、a）。 -图中右边情形：当之前相邻边界像素相邻边界像素其中一个变成标签，另一个保留原标签，那 么还是由于三角不等式三角不等式，ep,a必定包含在割集中。 三角不等式在这里的意义就是尽量只切辅助节点的某一条边三角不等式在这里的意义就是尽量只切辅助节点的某一条边。 与上一部分类似，通过之前定义的割边权值计算最小割代价可以证明|C|=E(fC)。 那么有： 性质5.2在图7所示 v 最优性能 v算法的最优性能：使用expansion移动算法生成的局部最小 值在已知因素中全局最优，适用于度量。交换移动算法更适 用于半度量，但可能无法保证性能最优。使用Potts模型可能 获得好的解决方案。 总结 整个系统的目的就是最小化能量E，我们控制的输入变量是标记函数f。算法 就是在当前输入下找到下一步所能达到的最小值，然后移动，如此循环，直至 下一步找不到更小的能量值了。 本文中提出的两个算法都能同时改变大范围像素集的标号;而其它的标准算法一 般用微小的移动，一次仅能改变一个像素的标号。 算法可以类比于梯度下降法：在操作空