基于图割的能量最小化演示文稿ppt课件.ppt

《基于图割的能量最小化演示文稿ppt课件.ppt》由会员分享，可在线阅读，更多相关《基于图割的能量最小化演示文稿ppt课件.ppt（16页珍藏版）》请在三一办公上搜索。

1、基于图割的能量最小化,基于图割的能量最小化方法，在某些情况下可以提供能量的全局最小化;在其他一些情况下，即使产生的结果是局部最小值，这些最小值也是具有很强性质的局部最小值。这种算法都包含两个通常的约束：数据项约束和平滑项约束。然而对于具体问题来说，我们可以在这两项的基础上加上符合自己问题的约束条件。,基于图割的能量最小化,它的基本原理是为能量函数构造一个特定的图，这样在这个图上的最小割就会最小化这个能量函数，而最小割可以有效地通过最大流来计算出来。算法总体思想和框架：,基于图割的能量最小化,图中的最小割也就可以最小化能量E。如果对于每一个问题，都需要针对其实际情况具体构造一个图，那么用图割法来

2、进行能量最小化仍然是一个很复杂的问题。如果可以精确描述能通过图割法进行最小化的能量函数的特征，并且对这些能量函数给出统一的构造图网络的方法，那么在实际应用中最小化问题就会变得非常简单。,基于图割的能量最小化,利用图分割方法快速近似地计算方程的最小能量 在扩展景深系统中 ，有 n幅预先载入的源景深图像 S1 , , Sn。为了形成一幅合成图像必须为每个像素 p选择一幅源图像映射Si ,代表此像素点的颜色取自源图像Si对应位置的像素点。把像素点和源图像之间的映射叫做“标记法”,并且将每个像素p的标记指示为 约定：如果 则在合成图像两相邻像素 p, q之间存在一条接缝。,基于图割的能量最小化,Boy

3、kov提出了两种计算局部最小量的图分割算法：扩张，对于一种标记,此变动将任意一部分像素集的标记赋为；另一种是-交换,对于一对标记 , ,此变动将任意一部分标记为的像素集与任意一部分标记为的像素集之间相互交换标记。这两种算法都将最终生成能量最小的标记法。,基于图割的能量最小化,标记问题的能量函数一般形式为：式中 为数据项， 表示对应像素匹配一致性程度， 为 平滑项，用于约束邻接像素间具有一致视差。其中，p和q是像素位置，N代表某种邻接关系， 是标记，D是衡量标记值与观测值误差的补偿函数，V是衡量相邻标记不一致程度的相对势能函数。能量最小化是一个迭代过程，在每一步，针对某个标记或某对标记建立相应的

4、图，使得由对该图的最小切割所得到的标记能最小化能量。,：,基于图割的能量最小化,图的知识双终端图：一个有向加权图G=，由一个结点集合V和有向边集合E组成。通常来说结点对应像素、立体像素或者其它特征。一个图通常包含一些附加的被称为“终端”的特殊结点。在立体视觉中，“终端”可以对应于像素上的标记集合。双终端图中，两个终端分别称为“源”s和“汇”t。,基于图割的能量最小化,边和流：图中所有的边都被赋予一个权值或代价值，一个有向边可能和有向边的代价值不同。实际上，对于和分配不同边的权值在基于图像的视觉应用方面是非常重要的。一般来说，在图中有两种类型的边N-links和T-links。,N-links连

5、接相邻像素点或立体像素点，所以它们代表的是图中的邻接系统。其权值取决于像素之间的不连续性情况通常是由能量公式中的相对势能继承而来的。T-links连接图的终端像素(或标记点)。T-link连接一个像素或者一个终端的权值取决于分配给像素点的标记值。这些权值通常是由能量公式中的数据补偿函数决定。,基于图割的能量最小化,割： 一个s-t切割(可以简称为割)C=S, T把图分成两个不相交的集合S和T，使得 , 。切割的代价为从集合S到集合T的所有边的权值的和，即：这样，最小割的问题就归结为找到包含最小代价的切割C。这个问题等同于计算从源点到汇点的最大流。,基于图割的能量最小化,最大流最小割算法的实现过

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

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

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