基于图割的能量最小化演示文稿

1、基于图割的能量最小化v 基于图割的能量最小化方法，在某些情况下可以提供能量的全局最小化;在其他一些情况下，即使产生的结果是局部最小值，这些最小值也是具有很强性质的局部最小值。这种算法都包含两个通常的约束：数据项约数据项约束束和平滑项约束平滑项约束。然而对于具体问题来说，我们可以在这两项的基础上加上符合自己问题的约束条件。基于图割的能量最小化v它的基本原理是为能量函数构造一个特定的图图，这样在这个图上的最小割就会最小化这个能量函数，而最小割可以有效地通过最大流最大流来计算出来。v算法总体思想和框架：图像优化拼接景深问题求解尽可能大的对比度求解尽可能小的拼合边界差能量最小化方法化 图分割最优化 最

2、大流最小割算 基于图割的能量最小化v 图中的最小割也就可以最小化能量E。如果对于每一个问题，都需要针对其实际情况具体构造一个图，那么用图割法来进行能量最小化仍然是一个很复杂的问题。如果可以精确描述能通过图割法进行最小化的能量能量函数的特征函数的特征，并且对这些能量函数给出统一的构造图网络构造图网络的方法，那么在实际应用中最小化问题就会变得非常简单。基于图割的能量最小化v利用图分割方法快速近似地计算方程的最小能量利用图分割方法快速近似地计算方程的最小能量v v在扩展景深系统中 ，有 n幅预先载入的源景深图像 S1 , , Sn。为了形成一幅合成图像必须为每个像素 p选择一幅源图像映射Si ,代表

3、此像素点的颜色取自源图像Si对应位置的像素点。把像素点和源图像之间的映射像素点和源图像之间的映射叫做“标记法标记法”,并且将每个像素p的标记指示为 约定：如果 则在合成图像两相邻像素 p, q之间存在一条接缝。pfpqff基于图割的能量最小化vBoykov提出了两种计算局部最小量的图分割算法：扩张，对于一种标记,此变动将任意一部分像素集的标记赋为；另一种是-交换,对于一对标记 , ,此变动将任意一部分标记为的像素集与任意一部分标记为的像素集之间相互交换标记。这两种算法都将最终生成能量最小的标记法。基于图割的能量最小化v标记问题的能量函数标记问题的能量函数一般形式为：v式中 为数据项， 表示对应

4、像素匹配一致性程度， 为 平滑项，用于约束邻接像素间具有一致视差。其中，p和q是像素位置，N代表某种邻接关系， 是标记，D是衡量标记值与观测值误差的补偿函数，V是衡量相邻标记不一致程度的相对势能函数。能量最小化是一个迭代过程，在每一步，针对某个标记或某对标记建立相应的图，使得由对该图的最小切割所得到的标记能最小化能量。( )dataEf：, , ()()()(,)()datasmoothp qpqppp qNpPEfEfEfVffDf( )smoothEff基于图割的能量最小化v 图的知识图的知识v双终端图双终端图：一个有向加权图G=，由一个结点集合V和有向边集合E组成。通常来说结点对应像素、

5、立体像素或者其它特征。一个图通常包含一些附加的被称为“终端”的特殊结点。在立体视觉中，“终端”可以对应于像素上的标记集合。双终端图中，两个终端分别称为“源”s和“汇”t。基于图割的能量最小化v边和流边和流：图中所有的边都被赋予一个权值或代价值，一个有向边可能和有向边的代价值不同。实际上，对于和分配不同边的权值在基于图像的视觉应用方面是非常重要的。一般来说，在图中有两种类型的边N-links和T-links。v N-links连接相邻像素点或立体像素点，所以它们代表的是图中的邻接系统。其权值取决于像素之间的不连续性情况通常是由能量公式中的相对势能继承而来的。T-links连接图的终端像素(或标记

6、点)。T-link连接一个像素或者一个终端的权值取决于分配给像素点的标记值。这些权值通常是由能量公式中的数据补偿函数决定。基于图割的能量最小化v割割：v 一个s-t切割(可以简称为割)C=S, T把图分成两个不相交的集合S和T，使得 , 。切割的代价为从集合S到集合T的所有边的权值的和，即：v这样，最小割的问题就归结为找到包含最小代价的切割C。这个问题等同于计算从源点到汇点的最大流。,(,)(,)(,)uS vTu vEc S Tc u vsStT基于图割的能量最小化v最大流最大流最小割算法的实现过程如下：最小割算法的实现过程如下：v 两个不重叠的搜索树，一条是以源s为根的S树，一条是以汇t为

7、根的T树。S树中从父节点到子节点的边都是不饱和的，而T树中从父节点到子节点的边也都是不饱和的。不在S和T中的节点称为自由节点。主动节点代表S或T的外部节点（叶子节点），被动节点代表S或T的内部节点（非叶子节点）。关键区别就是主动结点可以从自由结点集合中接收新的子结点来扩展，当然条件是沿着非饱和路径当然条件是沿着非饱和路径。被动结点无法扩展，因为它们被本搜索树内的其它结点封锁着。还有一点很重要的是主动结点可以和另主动结点可以和另一个搜索树中的结点连接一个搜索树中的结点连接，当一个搜索树中的主动结点发现它的邻接结点是属于另一棵搜索树时，就获得了一条连接两个搜索树的增广路径。基于图割的能量最小化v算

8、法迭代地重复以下3个步骤:v(1)生长阶段：搜索树S和T逐渐扩展，直到它们相交 给出一条从s到t的路径。v(2)增广扩展阶段：已寻找到的路径被增广扩展,搜索 S树被分割为s森林。v(3)“采用”阶段：搜索树S和T被存储下来。v 在生长阶段，搜索树是扩展的主动结点搜索邻主动结点搜索邻近的非饱和边近的非饱和边，接收自由结点集合中的新的子结点。最新加入的结点变为相应搜索树中主动结点集合的成员。当给定主动结点的所有邻接结点都被搜索完成后，该结点变为被动结点。当主动结点遇到一个它的邻接结点属于另一个树时增长阶段结束。由此找到了一个从源到汇的路径，如图所示。基于图割的能量最小化v图：算法结束时搜索树和结点

9、的状态v 如图所示，这是两个搜索树S(红色结点)和T(蓝色结点)增长的最后阶段，即当一个从源到汇的路径(黄色线)被找到后的情况。主动结点和被动结点分别用字母A和P来表示，自由结点用黑色圆圈表示。基于图割的能量最小化v 在扩展阶段对增长阶段所找到的路径进行扩张。我们将最大可能的流从源沿路径推向我们将最大可能的流从源沿路径推向汇，则路径中的一些边就会变成饱和的汇，则路径中的一些边就会变成饱和的。因而一些S和T中的结点会变成孤儿结点，因为连接它们到其父结点的边将不再有效(因为这些边已经饱和了)。实际上，扩展阶段会使搜索树S和T分裂为森林。这时源s和汇t仍然是两棵搜索树的根，而孤儿结点则变为其它搜索树的根节点。 基于图割的能量最小化v v采用阶段的主要目标就是存储以源s和汇t为根节点的两棵单树结构。我们试图为每个孤儿结点找一个有效的父结点。一个孤儿结点的新找到的父结点应该和该孤儿结点一样属于同一个集合S或者T，这个新的父结点还应该与一个非饱和边界连接。如果没有这样的父结点，那么就把它从S或T中移除，让它变成自由结点，孤儿节点的所