英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
通过图割的快速近似能量最小化
摘要
在本文中，我们解决早期视觉中出现的的一大类能量函数的最小化问题。主要的限制是，能量函数的平滑项只涉及像素对。我们提出了两种算法，使用图割来计算局部极小值时即使非常大的动作是允许的。第一次移动，我们考虑的是一种alpha;-beta;交换：对于一对alpha;、beta;标签，这次移动交换了任意一套标记为alpha;的像素和另外任意一套标记为beta;的像素之间的标签。我们第一算法产生一个标记，以便不会进行减少能量的交换移动。第二次移动我们考虑一种alpha;-扩展：对于标签alpha;，此举将指定任意一套像素标签alpha;。我们的第二算法，要求光滑项为一个度量，产生一个标记以便不会发生减少能量的扩展移动。此外，这种方法包括一个全局极小值的已知因素。我们用实验证明我们的方法在图像复原、立体声及运动方面的有效性。
1 早期视觉的能量最小化
许多早期的视觉问题需要从噪声测量中估计一下空间变化量（如强度或差距）。这样的量往往是分段光滑的，它们大多数情况下平滑变化，但在对象边界发生显著变化。每一个像素pP在一些集合L中必须被指定一个标签，对于运动或立体声，标签是不等的，而对图像恢复它们代表强度。目标是要找到一个标记来指定每个像素个标签，其中 是分段光滑的，这与所观察的数据相一致。根据能量最小化，这些视觉问题可以很自然地得到确切的阐述。在这个框架中，一个寻求能量最小化的标记
这里表示不分段光滑的程度，而表示和观察到的数据之间的不符合程度。文献中已经提出了许多不同的能量函数。的形式通常是
，
这里表示如何对所指定的观察到的数据中的像素设定一个标签。例如在图像复原中，通常是，其中是所观察到的像素的强度。的选择是一个关键问题，并提出了许多不同的函数。例如，在基于视觉的，使到处都很光滑。这会导致在对象边界处几乎没有结果。没有这个问题的能量函数被称为“不连续性保护”。
已经提出了大量的不连续性保护的能量函数（见例如）。杰曼和杰曼的开创性论文为许多能量函数给出了贝叶斯解释，并提出了基于不连续性的能量函数的马尔可夫随机场（的）。
早期视觉能量最小化的主要困难在于巨大的计算成本。通常这些能量函数有许多局部极小（即它们是非凸的）。更糟糕的是，可能的标记的空间维数，这是成千上万的。有无数次尝试设计能量最小化的快速算法。模拟退火算法通过在计算机视觉中得到了广泛的推广，得到了广泛的应用，因为它可以优化任意的能量函数。不幸的是，最大限度地减少一个任意的能量函数需要指数时间，作为结果，模拟退火是非常缓慢的。在实践中，退火是低效的，部分原因是在每一个步骤，它改变了一个单一的像素值。
在本文中我们考虑，在各种不同的语境中产生的能量函数，包括马尔可夫的贝叶斯标记。
我们允许是任意的，并考虑平滑的形式
(1)
其中N是相邻像素对的集合形式。在特殊情况下，这样的能量可以完全地被最小化。如果可能的标签的数量是=2，那么精确解可以通过计算某一图的最小成本在多项式时间内发现。如果是一个有限的一维集且相互作用势是，那么通过图割也可以有效地发现精确的最小化。一般来说，然而，问题是NP-难。
在本文中，在两类相对公平的相互作用势：半度量和度量下，我们开发的算法大概能最大限度地减少任意一组有限的标签的能量。如果对于任意一对标签alpha;，beta;，它满足2个属性：和。被称为标签空间上的半度量。如果也满足三角不等式
(2)
对于任意属于的，，，那么被称为度量。请注意半度量和度量都包括不连续性保持相互作用势的重要情况。例如，截断的L2距离和Potts互动罚都是度量。
本文中所描述的算法概括了我们最初开发的情况下的Potts模型的方法[2]。特别是，我们计算了一个标签，这是一个地方的最小，即使非常大的动作是允许的。我们首先概述了我们的基于图割的能量最小化算法。我们在第3节中描述的第一个算法，是一种基于alpha;-beta;互换的移动，并为任何半度量工作的。我们在第4节描述的第二种算法，是基于更有趣的alpha;-扩展移动，但是仅仅适用于度量的（即额外的三角不等式是必须的）。注意：alpha;-扩展移动产生一个已知的E的最小的因素的解决方案。这一个证明可以在[8]中找到。
2通过图割的能量最小化
这些方法的最重要的属性是它们能产生局部极小，即使在允许大动作时。在这一节中，我们讨论我们允许的移动，这是就分割而言的最好描述。我们简述算法和列出它们的基本属性。然后，我们正式的介绍图割的概念，这是我们的方法的基础。
1.以任意一个标记开始
2.设置成功率：=0
3.对于每一对标签
3.1在中的一个alpha;-beta;交换得到的中找个（第3节）
3.2如果，设和成功率：=1
- 如果成功率=1则转去2
- 返回
1.以任意一个标记开始
2.设置成功率：=0
3.对于每一个标签
3.1在中的一个alpha;-扩展得到的中找个（第4节）
3.2如果，设和成功率：=1
- 如果成功率=1则转去2
- 返回
图1：我们的交换移动算法（顶部）和扩展移动算法（底部）
2.1分区和移动空间
任意标记可以唯一地表示图像像素的一个分区，其中是一个子集的像素分配标签。因为在标记和分区有一个明显的对应关系，我们可以互换地使用这些概念。
给定一对标签alpha;，beta;，如果对于任何标签有，从一个分区（标记）到一个新的分区（标记）的一个移动被称为一个alpha;-beta;交换。这意味着，和之间唯一的区别是一些像素以前在中标记为alpha;，现在在中标记为beta;和一些像素以前在中标记为beta;，现在在中标记为alpha;。
给定一个标签alpha;，如果对于任何标签有和，从一个分区（标记）到一个新的分区（标记）的一个移动被称为一个alpha;-扩展。换言之，一个alpha;-扩展移动允许任何一组图像像素把它们的标签改为alpha;。
注意到一个给一个单一像素的任意标签的移动是一个alpha;-beta;交换和alpha;-扩展。作为结果，标准的移动空间用于退火是我们的移动空间的一种特殊情况。
2.2 算法和性质
我们已经开发了两个能量最小化算法，这是图1显示的。算法的结构是非常相似的。我们将称步骤3.1-3.2一个单一的执行为一个迭代，步骤2-4的执行为一个周期。在每个周期中，算法对进行迭代的每一个标签（扩展移动算法）或每队标签（交换移动算法），在一定的顺序可以是固定的或随机的。如果在任何迭代中发现一个严格更好的标签，那么这个周期是成功的。该算法在第一次不成功的循环后停止，因为没有进一步的改进是可能的。显然，在交换移动算法进行周期为的迭代，在扩展移动算法进行周期为的迭代。
这些算法有几点重要性质。首先，该算法是保证在一个有限数量的周期终止；事实上，在相当一般的假设下，我们可以证明终止在周期[8]。然而，在我们报告的5节中的实验中，该算法在几个周期后停止，并在第一个周期中发生大部分改进。其次，一旦该算法已终止，所得到的标签的能量是一个本地最小值相对于一个交换或扩展移动。最后，我们在[8]中证明扩展移动算法产生的标记，这样，其中是完全最小值和。
2.3 图割
每个算法的关键部分是步骤3.1，其中图割是用来有效地找到。让是两个重要的顶点加权图称为终端。一个的分割是一组边缘，这样终端在诱导图中是被分离的。此外，没有适当的C的子集能在G(C)中分离终端。割C的费用表示|C|，等于它的边的权重的总和。
最小割问题是要去找到最小的费用。对于这个问题的低阶多项式复杂度有许多算法；实践这些方法在近似时间运行。
步骤3.1在一个图的容量是上用了一种单一的最小割。每一次迭代后，该图是动态更新的。这个最小割的细节有很大的不同，用于交换移动和扩展移动算法，如下两节所描述的。
3 寻找最优的交换移动
给定一个输入标记（分区P）和一对标签alpha;，beta;，我们希望找到一个标记，在的一个alpha;-beta;交换中的所有标记中最小化E。这在图1的顶部所给定的算法中是至关重要的步骤。我们的技术是基于计算一个标记对应一个图上的最小割。这个图的结构是由当前分区P和标签alpha;，beta;动态确定的。
本节组织如下。首先我们描述构建对于给定的（或P）。我们表明，在上的割C对应的自然方法是在的一个alpha;-beta;交换移动中标记。定理1表示了一个割的费用是加一个常数。这一推论定理证明了我们的主要结果是，所需的标记等于，其中C是的最小割集。
图2：图的一维图像的例子。图像中的像素集是，其中，
图的结构示于图2。易读性，此图显示一维图像的实例。对于任何图像的结构将如下。顶点集包括两个终端alpha;和beta;，以及在集合和的图像像素p（那是）。因此，顶点集包括alpha;，beta;和。每个的像素通过边缘和分别连接到终端alpha;和beta;。为简便起见，我们将参考这些边缘作为（终端连接）。对于每对相邻（即）像素的边缘，我们将其称为（相邻连接）。因此边缘集包括（）和（）。分配给边缘的权重是
任何上的割C必须完全地切断（包括）对于任何像素的一个：如果在C上没有，在终端之间有一条路径；而如果所有的被切断，然后C的一个真子集将是一个割。因此，任何割遗留的每个像素完全是一个。这定义了一个自然标记对应于上的一个割C。
(3)
换言之，如果像素p是在上，那么当割C从终端alpha;中分离p时，p分配了标签alpha;；类似的，当割C从终端beta;中分离p时，p分配了标签beta;。如果p不在上，那么我们保持其初始标签。这意味着
引理1 一个对应于上的一个割C的标记是远离初始标记的一个alpha;-beta;交换。
一个割C切断上相邻像素之间的一个当且仅当C遗留了连接到不同终端的像素p和q是很容易的。形式上
属性1 对于任何割C和任何：
这些属性的说明在图3。下一个引理是属性1和公式3的结果。
引理2 对于任何割C和任何
引理1和2加上属性1产生
定理1 在上的割集C和从中的一个alpha;-beta;交换的标记之间有着一对一对应。此外，上的一个割C的费用是加一个常数。
证明：第一部分是从一个事实，即被切断的唯一确定分配给像素的标签p和必须被切开。我们现在计算一个割C的费用，这是
（4）
图3：对于通过连接的两个像素的的一个割C的属性。虚线显示了通过C边缘的切割，实线显示了在诱导图中边缘的剩余
注意对于我们有
引理2在（4）中给出了第二个术语。因此，一个割C全部的费用是
这可以改写为，其中
对于所有的割C是相同的常数。
推论1 中最优的alpha;-beta;交换是，其中C是上的最小割。
4 寻找最优的扩展移动
给定一个输入标记（分区P）和一个标签alpha;，我们希望找到一个标记，在的一个alpha;-扩展中的所有标记中最小化E。这在图1的底部所给定的算法中是至关重要的步骤。在这一节中，我们描述了一种技术解决这一问题。假设每个是一个度量，从而满足三角不等式（2）。在介绍中给出了一些重要的度量的例子。我们的技术是基于计算一个标记对应一个图上的最小割。这个图的结构是由当前分区P和标签alpha;确定的。像以前一样，在每一次迭代后，图都动态变化。
图4：图的一维图像的例子。图像中的像素集是以及当前分区是，其中，，。在当前分区引入相邻像素之间的两个辅助节点，。在集合的边界处添加辅助节点
本节组织如下。首先我们描述构建对于给定的（或P）和alpha;。我们表明，在上的割C对应的自然方法是在的一个alpha;-扩展移动中标记。然后，根据一些简单的属性，我们定义了一类基本割。定理2表示了基本割是在的一个alpha;-扩展中标记之间的一对一对应，同时，一个基本割的费用是。这一推论定理证明了我们的主要结果是，所需的标记等于，其中C是的最小割集。
图的结构示于图4。易读性，此图显示一维图像的实例。顶点集包括两个终端alpha;和，以及所有的图像像素。此外，对于在当前分区（即）分割的每队相邻像素，我们创建了一个辅助顶点。当时，在分区集之间的边界介绍了辅助节点。因此，顶点集合是。每个的像素相应地通过和被连接到终端和。不是被分区P（即）分割的每对相邻像素连接了一个。对于每对相邻像素，如此，我们创建了一个三重的边缘，其中是相应的辅助节点。边缘和连接像素p和q到，及连接辅助节点到终端。所以我们能够写出所有边缘集合如下
分配给边缘的权重是
就像在第3节，任何上的割C必须完全地切断（包括）对于任何像素的一个。这定义了一个对应于上的割C的自然标记。形式上，
（5）
换言之，如果割C从终端alpha;中分离p时，那么像素p分配了标签alpha;；以及如果割C从终端中分离p时，p分配了原来的标签。注意到对于的终端代表的标签分配给其初始标签。显然我们有
引理3 一个对应于上的一个割C的标记是远离初始标记的一个alpha;-扩展。
一个割C切断上相邻像素之间的一个，以至于当且仅当C遗留了连接到不同终端的像素p和q是很容易的。换句话说，当我们用替代beta;时属性1保持。我们将把这个作为属性1（）。类似的，对于里的，我们可以证明，属性1和方程（5）建立引理2。
图5：对于两个像素以使得的上的最小割C的属性。虚线表示被C分割的边缘，而
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[151642]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
