二值图像的最大后验估计外文翻译资料

英语原文共 114 页，剩余内容已隐藏，支付完成后下载完整资料

二值图像的最大后验估计

D. M. Greig; B. T. Porteous; A. H. Seheult

英国杜汉姆大学

1987六月获得，1988九月最后修订

摘要

在本文中，对于一个退化的双色或二元的场景，我们展示了如何用最大后验概率（MAP）估计的图像准确地评价使用高效的变体的Ford-Fulkerson算法寻找最大流容量网络。准确估计的可用性允许的性能评估模拟退火算法及其在这个限制环境中的映射。不幸的是，简单的网络流算法并没有以任何明显的方式扩展到多色的场景。然而，双色图像的实验结果表明，在一般情况下，根据切实可行的“温度”的时间表模拟退火，可以产生无穷近似于收敛时候的MAP估计。

关键词：贝叶斯方法；约束网络；ford-fulkerson算法；图像处理；迭代条件模式；马尔可夫随机领域；最大posterlori估计；模拟anneallng

1.简介

人们对图像分析的贝叶斯方法有极大的兴趣：例如，Geman and Geman (1984) and Besag (1986)。在本文中，我们展示了最大的海报归RI的真实评价场景可准确找到的退化的二值图像。这允许有限估计的评估和模拟退火逼近它。我们还与条件迭代模式（ICM）的方法进行了对比；从Besag（1986）可以看出。

所有允许的图片中一个贝叶斯公式指定一个先验分布p（x），其中xi表示像素的图像x的类别或值，i=1,2......,n）。通常，P（x）时采取的是本地依赖马尔可夫随机场（MRF），它是一个未知真实场景X *包含的量化的信念所简化的模型，例如，大齐补丁，或偶尔会发生变化水平间断的平滑变化的灰度级。其中y=（Y 1，...，Yn）表示的X *观察到的记录，任何图像x的可能性L（Y|X）与P（x）的组合，根据贝叶斯定理,形成正比于l(ylx)p(x)的后验分布p(xl y)。X *的MAP估计是图像最大化P（X|Y）。

然而，的直接计算在计算一般禁止的，因此，作为一个近似，杰曼和格曼（1984）提出了利用模拟退火，随机松弛算法，一个合适的“温度”的时间表，收敛于。在二进制图像的特殊情况下，Greigetal（1986）表示如何将准确地找到。非常有限的试验，然后建议模拟退火可产生近似差，用抚育比退火逼近它顺畅。

第二部分，在一定的获能网络中最大后验概率的二进制图像估计重新作为最小切问题以及经典的福特Fulkerson算法可以用于求的。第3节产生了大量的试验结果报告：福特-Fulkerson算法，的更快版本。这一版本利用了相关的图像的网络的本地连通性，在第4节中有所描述。

2.精确的最大后验估计对于二进制图像

在本节中，我们提出了二进制图像MAP估计的网络改写的细节

问题。每个像素被分成两个一无序的颜色或类别，我们称之为白和黑，并分别编码为xi=0和XI=1。继Besag（1986年），我们采用了以下假设。这些记录Y1... ，YN是取决于给定的x，每个已经知道条件密度函数f（Yilx），依赖于X且仅依赖于X I。因此，该对于x的似然函数可被写为下面公式(1)：

....................(1)

现有分布p（x）的建模为以下形式的对相互作用MRF (如公式2，其中szlig;ii = 0 ， szlig;ij = szlig;jige;0;

.....................(2)

在严格的不等式中，我们称i和j为相邻的。这种分布是在一般成对相互作用MRF的特例等式，在Besag的（1986）中的等式（9）有提到;其实，本文对于任何二进制成对MRF的结果表示，在Besag（1986）表示法中，当X I= X j时，GIJ（xi,xj）非负，否则，非正。如果szlig;ij=beta;，如果i和j是相邻的，则szlig;ij=0，否则，P（X）包含于EXP(beta;v)，其中V是相近的颜色相邻的对数。因此，除了常数恒定，LNP（x|y）可写为以下公式（3）：

................(3)

其中lambda;i = ln{f(YiI1)/f(yi|0)},在像素i上数似然比。 MAP的估计是该图像最大化L.L的个可能的值和n可以是订单256times;256，使得直接搜索不可行的。幸运的是，最大化L的高效算法，就是我们现在所描述的。

考虑一个容量网络，包括N 2个顶点，是一个源S，水槽t和n个象素。如果lambda;igt;0，有向边（S，I）从s到容量CSI= lambda;i的像素i;否则，有向边（I，T）从i到容量Cit=-lambda;i如果相应象素是相邻的，两个内部顶点（象素）之间的容量为

Cij=beta;ij的无向边（i，j）的i和j。

F或任何二进制图像X =（X1，...,XN）让B ={S}U{i:xi=1}，W ={i：xi= O}U{t}定义为网络顶点的两盘的分区，并把公式（4）：

....................................................(4)

该组与B中的顶点和W中一个顶点的边被称为切割和C（x）的称为容量晋级。容易看出，C（X）可以写成公式（5）：

......(5)

这不同于L - （X|y）的通过不依赖于x的项;又见皮卡德和Rat1iff（1975年）。此外，由于福特和富尔克森（1962年）显示，最低的C（x）的最大流量，通过从源网络向下沉受边缘能力，并且它们得到解决该问题的一个有效的算法。对应的切被称为最小割。因此，最大化的L（X|y）是相当于发现网络中的最小割：在最大后验概率（MAP）的估计中，如果他们是在最小的切割的源极侧，那么像素是黑色上，否则是白色。

3之间的精确极大一些数值COMPARISONS后验估计，

模拟退火和条件迭代模式

两个合成二进制场景在我们的实验中使用，并显示在图 Besag（1986）4a和图L（A）上 。从已知的分布通过用随机噪声破坏合成场景和从这些相同的噪声分布使用独立实现来复制实验，不同的方法被应用到创建的记录。简单的现有分布p（x）使EXP（beta;V）在整个包含每个像素的八个相邻邻域系统保存为明显边界的修改，其中v表示具有类似颜色的相邻对的使用数量。对变量beta;的影响进行了研究和不同退火进度进行比较。在这项研究中，beta;在遍及ICM的每个应用程序使用的八次迭代中均不变。

第一个影像纪录，通过加入独立的高斯噪声产生方差从0.9105到Besag的图4a（1 986）0-1版本图中显示的88times;100的白色和黑色的景象。这对于最大似然分类器将导致30％的预期误分类率。研究中的估计被应用到对beta;进行五次重复记录的五个值中的每一个。在表1中总结的结果将会在这里详细地讨论。

第二图像记录是由将25％错误率的二进制信道应用到64times;64的白色和黑色的场景中而创建的 ，从而导致对于最大似然分类器产生25％的预期误分类率;一个例子被显示在图b中。研究的估计被应用到对beta;进行五次重复记录的三个值中的每一个。结果总结在表2中，一些相应的图像估计的显示在图1。

对于每个beta;和对于所考虑的每个估计，复制的意思和误判率的标准偏差在表1和2以上部分中给出。对任何复制，把对数后验概率的偏差考虑成相应的最大后验概率估计。对这些后侧偏差而复制平均值和标准偏差在表1和表2的下段给出了，除了MAP估计，由于省略了加常数，只复制的标准偏差是相当的。

图一（一）真正的64times;64的二进制现场;

（二）现场真实与错误率25％二进制信道损坏;

（三）准确估计的MAP（szlig;=0.3）;

（四）模拟退火估计有几何时间表一升，其中A= 2 / LN2，rho;=0.99，K =565（beta;= 0.3）（K = 1，，，K）;

（五）ICM估计（beta;=0.3）;

（六）确切的MAP估计（beta;= 0.7）;

（七）模拟退火估计有几何时间表扩升（K = 1，，，K），其中A= 2/2，rho;=0.99，K =565（beta; =0.7）;

（八）ICM估计（beta;= 0.7）;

（九）准确的地图估计（beta;=1.1）;

（十）模拟退火估计几何时间表

（K = 1，，，K），其中A= 2/2，rho;=0.99，K =565（beta;=1.1）;

（十一）估计ICM（beta;=1.1）

表格1

MAP估计的比较，模拟退火和ICM对beta;的各种值

基于五高斯噪声replicptions叠加在图1

所示的88times;100真实场景。Besag（1986）

对于模拟退火，形式C / LN对数的时间表（1 k）和形式（K = 1，K）的几何时间表被用于两个图像。值A =2/ LN2用在每一个几何安排的两个实验中，给予同样的起始温度与C =2的对数时间表每个几何时间表，K被选择，使得最终温度为刚刚小于0.01。

几何时间表通常在模拟退火的应用中来解决一般复杂的优化问题;例如，柯Kirkpatrick et al（1983）中记载：几何时间表的对数多一个的时间表明显的优势是，气温接近零可以从一个高起点温度达到相当少的迭代。然而，在理论上，一个几何时间表太快和存在着局部最大值可以达成从中退火算法无法逃脱的风险。

我们现在讨论在表1和表2中的结果。作为一般的模式是相似的两个图像，参照表2，只有当出现分歧时，我们将注意力主要集中在表1中。平均错误率一般为一切估计beta;的U形功能：对于beta;估计量较小的值往往渐近正态性，而对于很大的beta;值，他们往往渐远正态性。价格与beta;增加最迅速的MAP估计和至少对于迅速ICM，而增加模拟退火的中间。因此，MAP估计对现有的规范的变化非常敏感，而ICM是普遍强劲到这样的变化。模拟退火的价格低估那些MAP，特别是用于beta;的更高的值。正如我们所期望的，几何时间表率倾向于为相应的率rho;增加MAP估计。对训练数据的标准差显示了变化不大模拟退火的和ICM，虽然它往往是最大为beta;大的值不过，对于MAP估计的增加的标准偏差，然后减小，与增加beta;，因为，对于很大的beta;，MAP估计趋于一种颜色。

从表1中，我们可以看到，表示与登录后验概率偏差增加beta;为ICM和三个几何退火的估计，但U型的这三个数退火估计。几何时间表给出结果，即是非常接近的MAP估计在0.3和0.5之间的beta;和比更好相应的对数的时间表，这大概是因为在这个范围内有较少的的被困在一个局部最大值rho;（X|y）的比为较大的值的机会szlig;。然而，对于beta;的大的值的相对似乎是的情况下，这表明在此范围内的几何下降太快。这些意见被支持在对数后验偏差的标准偏差的相应增加，并

有关的由里普利（1 988）报告给我们的实验结果，这表明，对于beta;认为是较大的值，几何进度根据该种子修复用于启动退火算法产生本质上的不同。从而，对于模拟退火算法有机会成为被困在一个地方最大rho;（X| y）的，与特别是如果使温度增加beta;的增加会迅速下降。朱万曙温度下降的速度的重要性是几何图示时间表在平均随着rho;登录后验概率偏差减小。为对数调度结果表明起始温度等角度。因此，对于一个缓慢的进度大型beta;开始在一个较高的温度，多次迭代将被要求产生良好的模拟退火近似到MAP估计，而对于快进度的值小的szlig;在较低温度下开始迭代应该是足够的。我们结束本节与自己对MAP估计的一些看法。我们的研究结果表明确切的MAP估计对先验分布极为敏感。因此，在图像恢复和分类，例如，我们知道，这样的假设错误可以导致剧烈偏离正态性和误判。然而，可能有其他情况下，诸如边界检测，其中MAP估计是首选的方法;例如，参见Geman et alpha;1（1 988）。

4福特-Fulkerson算法更有效的VARIANT

第一组的第3节中描述的实验是基于尺寸的图像上88times;100，并为确定性，我们现在考虑beta; = T。在一个阿姆达尔470计算机，基本算法需要3000的中央处理单元（CPU）时间来寻找在MAP估计。但是，基本的算法的一个变体具有降低这250秒。该变体是如下：将图像划分成连接的子图像，然后单独计算每个子图像的MAP估计。这可以解释为通过网络找出最大流，但根据所施加的约束条件没有流跨边界子图像允许。在下一阶段，我们放松一些没有流跨允许子图像边界约束。因此，相应的子图像被合并形成新的，然后获得较大的子图像和MAP估计其中的每一套。这个过程继续，直到在最后阶段，我们会留下的是MAP估计完整的图像，以实现在CPU时间减少12倍所提到的，88times;100的图像首先划分成16times;16的阵列大致大小相等的矩形子图像。一旦已取得个人MAP估计，周边有子图像在合并四肢留下一个新的8times;8矩阵的子图像。这个过程是持续直到获得所述MAP估计的完整图像。分区的这种选择是不太可能是最佳的，但与未分区版本比较，分区的任何明智的选择将导致大量减少CPU时间。

5.讨论

本文描述了二值图像的精确MAP估计的方法。由这个简单的例子的结果可以直接与使用这些模拟退火得进行比较，并且该生产MAP估计的方法可以评估。我们的结果表明，施加切实可行的模拟退火，日程安排，并不一定会产生一个好的能近似到MAP估计的估计。然而，我们的实验结果表明，良好的近似更有可能为参数beta;的较小的值，并且在这种情况下，几何时间表优于对数时间表。此行为的一个非正式的解释是，平滑所需的量，以获得带beta;的MAP估计的增加和，如Besag（1986），第298记载的，有猜测，模拟退火算法随后出现

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[153008]，资料为PDF文档或Word文档，PDF文档可免费转换为Word