基于稀疏块的块传播图像修复

基于稀疏块的块传播图像修复摘要本文介绍了一种通过调查自然图像块稀疏性的基于样本的图像修复算法。这里提出了两个新的概念，运用这两个新概念来建立块优先级和块表示方式的模型。块优先级和块表示方式是基于样本的图像修复算法中两个重要的步骤。首先，块结构稀疏是指通过测量相邻块间的非零相似的稀疏性来确定图像结构（例如：边或角）修复中的候选图像块。结构稀疏性较大的块拥有更高的修复图像的优先级。第二，我们假定需要被修复的块可以用稀疏表示框架约束下候选块的稀疏线性组合来代替。相较于传统的基于样本的图像修复方法，结构稀疏能够加强结构和纹理的识别力，而块稀疏表示则加强了修复区域与周围纹理的连续性。利用合成图或者自然图的实验展示了上述提出方法的优势。索引图像修复，块增殖，块稀疏，稀疏表示，纹理合成。I 介绍丢失区域的图像修复是计算机视觉和图像处理中一个很重要的课题。图像修复技术已经广泛应用到数字特效（例如：对象移除），图像复原（例如：消除照片中划痕和文本），图像编码和传输（例如：丢失块的恢复）等领域中。最基础的图像修复方法是基于扩散的方法1-3：用已知区域中的像素去填充丢失区域。这样的算法在偏微分方程（PDE）和变分法理论经常出现。Bertalmio等人1通过不断增加等照度线（即等灰度线）修复丢失区域的方法弥补了一些算法的缺陷。在图像修复2工作中，他们也引入了流动体力学中的纳维五笔方程。Chan和Shen3提出了一种基于全变差（TV）的变化框架来修复丢失区域。随后又提出了一个曲率驱动扩散方程来实现连图像的连贯性，这在TV模型中并不常见。一个等灰度方向和灰度级的联合插补修复方法也引入了变化框架5里的连贯性规则。最近，图像统计学也被应用于图像修复工作6-8。基于扩散的图像修复算法已经在修复非纹理区域或者修复相对较小的丢失区域方面有了一个不错的成果。但在修复工作中，这种算法不可避免地引入了平滑效应。第二类方法是基于样本的图像修复算法。这类方法用已知区域中的图像块来修复丢失区域。这个想法来自于纹理合成技术，图像中的纹理是利用已知区域中的最佳匹配块合成的。但是，自然图像是由纹理和结构组成的，结构构成了一副图像（例如：边或角）的原始草图，纹理则是带有同类图案或者统计特征（包括平面图案）的图像区域。纯纹理合成技术不能修复既有纹理又有结构的丢失区域。Bertalmio等人10将图像分解为结构层和纹理层，然后使用基于扩散的方法去修复结构层，使用纹理合成技术去修复纹理层。它克服了基于扩散的图像修复算法存在的平滑效应，可是它仍然很难去复原大面积的丢失结构。Criminisi等人提出了11将已知块（即样本）逐渐扩散到丢失区域的基于样本的图像修复算法。为了修复既有纹理又有结构的丢失区域，我们提出了块优先级这个概念，它能促进结构的修复。Wu12分析了各向异性扩散的跨灰度线，提出了一个基于样本的跨灰度图像修复算法。Wong3为基于样本的图像修复算法提出了一种非局部化的处理方法，通过用一组已知区域的候选块替代一个最佳匹配块来推断丢失区域的图像块。后来提出了更多基于样本的图像处理算法4-6来修复图像。相较于基于扩散的图像修复算法，基于样本的图像修复算法已经能够较好地修复大面积的丢失区域。最近，图像修复问题也引用图像稀疏表示这一概念17-21。这种方法的基本思路是通过一组完整的变换（例如：小波，轮廓波，DCT等）的线性组合来表示图像，然后通过自适应更新的稀疏方式来推断丢失的像素。Guleryuz等人18-20根据图像的自适应稀疏表示提出了一种新的图像修复算法。Elad等人17将图像分解成草图层和纹理层改进了这种方法，并且通过两个不相干过完备变换分别稀疏地表示这两层。这种算法运用纹理和结构复合的块可以有效地修复丢失区域，特别是修复丢失块。但是和基于扩散的方法一样，它有可能在修复大面积丢失区域的结构时或因引入平滑效果而失效。本文致力于研究通过块传播的基于样本的图像修复算法。块传播的两个基本步骤是块选择和块修复。在块选择中，先选择一个在丢失区域边缘中优先级最高的块去修复丢失区域。优先促进结构修复的块具有更高优先级，也就是说先修复结构再修复纹理，这样就能更好的修复既有纹理又有结构的丢失区域11,22。传统上，用等灰度方向和丢失区域分界线11,22正常方向的内积来定义块优先级。在块修复中，丢失块被已知区域中的候选块（即样本）修复。11和22中的方法利用了最佳匹配候选块来修复丢失块。13中的方法使用了一种候选块的非局部处理法来强化块的修复。为了解决块选择和块修复的问题，基于样本的图像修复算法又增加了两个自然图像的块稀疏新概念，即块结构稀疏和块稀疏表示。首先，我们给稀疏的非零相似相邻块定义一个新的块优先级。在本文中，这种稀疏性叫做结构稀疏。它是基于观察一个结构块和与之相邻的纹理块的稀疏非零相似性而得出的。相较于等灰度的优先级，这样的定义能更好地区分纹理和结构，并能够加强丢失区域的边缘定位。第二，为了修复一个在丢失区域边缘上的选定块，我们运用一个样本的稀疏线性组合来推断稀疏表示框架下的块。线性组合的稀疏优先原则规范了块的线性组合。也就是说，只有非常少的样本能组成一组非零稀疏块。在本文中，这种表示被称作块稀疏表示。块稀疏表示也受在本地块一致性的约束。这个模型通过线性组合扩展了块的多样性，通过稀疏假设保留了纹理，避免了平滑效应。更重要的是，被修复的块在本地块的一致性约束下与周围的纹理和结构更加一致。总的来说，基于块级的结构稀疏和块稀疏表示构成了块稀疏性。块结构稀疏的想法来自于最近对自然图像稀疏优先原则的研究进展。以前的稀疏优先原则一般地建立了图像非零特征的稀疏模型，例如梯度和滤波器响应。这种稀疏优先原则已经成功地应用到图像去噪8,23，超分辨率24,25,图像修复6-8,去模糊26,27等等中去。结构稀疏也建立了自然图像的稀疏性模型。它建立的相邻块间非零相似稀疏性模型替代了高通功能。块稀疏表示的想法来自稀疏表示的最新进展，它假定图像或者信号被表示为稀疏规范 (0=p2)下的过完备转换的线性组合。这个框架已经广泛运用于图像去噪29,30,边缘检测31,识别32,33,超分辨率34,纹理合成35,等，并且达到了先进水平。在本文中，假定丢失区域能被稀疏的候选块的线性组合表示的情况下，基于样本的图像修复算法引入了稀疏表示，进而为块修复建立了一个新的模型。本文安排如下。在第二节，介绍基于样本的图像修复算法的概述。第三节，介绍图像修复算法的细节包括块稀疏和块稀疏表示。第四节，讲解算法实验间的对比。第五节，对此项工作下结论。II. 算法综述给出一个带有丢失区域的图片I和一个已知区域，图像修复任务是利用源区（即已知区域）的图像信息填充目标区域（即丢失区域）。目标区域的边缘表示为，叫做基于样本的图像修复算法的前向填充。我们用表示像素p点所在位置块的中心。这个思路的主要过程在图1中给出。这个算法是基于从已知区域到目标区域的块传播原理。在每个块传递迭代过程中都有两个步骤：块选择和块修复。在块选择的步骤中，块优先级是指具有更高优先级的块先去修复丢失区域。我们通过测量相邻块间的相似性稀疏度来确定结构稀疏。然后块优先级用结构稀疏来定义。在图1（a）中，块和块分别表示处于结构边缘和平坦纹理中的像素点p和p。图1 （a）块选择 （b）块修复图1左下的部分（a）展示了它们与相邻块的相似性地址。显然，块有更加稀疏的非零相似度：因此，它有更高的块优先级。在前向填充时具有更高优先级的块会被优先选择。块修复程序使用前向填充时选中的块去修复图像，而非使用已知区域中的一个最佳匹配样本或者一定数目的的样本去修复图像，我们设在源区中通过稀疏优先原则的块的稀疏线性组合为选中块。在图1（b）中，系数为的候选块的稀疏线性组合去修复块。在中的相邻块通过本地块一致性约束来限制块的出现。在第三节，我们会详细地介绍块优先级和块稀疏表示。III. 通过块稀疏的图像修复A. 运用结构稀疏的块优先级自然图像一般由结构和纹理组成。一种好的块优先级定义是能够较好地区分结构和纹理，并且对于前向填充的方向是鲁棒的。为了满足这些要求，本文提出了一个新的关于块优先级的定义。我们现在来介绍关于块优先级定义的主要部分，即结构稀疏。1）结构稀疏：结构稀疏是用来测量结构块而非纹理块的准确度。结构稀疏来源于下列观测资料：结构稀疏地分布在图像域中，例如：边和角以1-D曲线分布或者像0-D点集在2-D图像域中的分布。不过，纹理是按图像域中的2-D子区域分布的。另一方面，对于某些块，它的具有更高相似性的相邻块也分布在相同的结构或者纹理中。因此，我们可以通过测量相邻块间的非零相似性稀疏为一个块建立一个准确的结构模型。带有更多稀疏分布的非零相似性的块由于结构的高稀疏性易于在结构中定位。假定是一个在前向填充中的块，它的相邻块是像素点附近的以为中心的已知区域，即属于一组 （1）是一个以为中心比块大的相邻窗口。假设是提取丢失块的一个矩阵，提取已知块，和的相似度为 （2）表示测量平均平方距离，是归一化常数例如 ，设置到5.0。对于块，我们测量在区域它与相邻块间的相似性稀疏。（3）是的向量，是元素数。属于,区间为，虽然它的值对不同块来说是一样的。图2处于角落，边缘和纹理上的块的结构稀疏值图3块优先级的比较这种阐述体现了一个事实，即在更大区域中更大相似平方和意味着更大的稀疏度。在接下来的段落中，我们称块相似性稀疏为结构稀疏。为了定义的结构稀疏，我们来证明下列结论。定理1：如果单个非零相似性存在，块的结构稀疏有最大值，如果所有相似性是一样的并且等于，有最小值。证明：我们看到和单调性相同。为了找到最大值和最小值，我们只需要计算的最大值和最小值。首先，为了找到的最小值，我们让归一化约束在中。这可以通过拉格朗日乘子法得出，即最大化: 。很容易证明当，时，能达到最小值。然后我们最大化。根据，所以。当仅有一个时值相等，等于1，所有别的相似性等于0。所以当只有一个相似性是非零并且等于1时，有最大值。最后，通过在（3）代入的最大值和最小值，我们很容易得到的最大值和最小值。定理告诉我们当块相似分别以稀疏和流畅的形式分布时，结构稀疏达到它的最大值和最小值，并且结构稀疏随着相邻块的非零相似性的增加而增加。我们现在研究结构稀疏是如何来测量自然图片中不同类型块的结构准确性。0-D中的块例如：图2（a），它在本地区域显著分布；因此，它具有最高的结构稀疏。由于图像边缘稀疏，1-D边缘例如：图2（b）有相似的块稀疏地沿着相同边缘散布；因此，它们有更高的结构稀疏。但是，对于纹理块例如：图2（c）和（d），它们在2-D本地区域中有更相似的块，因此，他们有更接近的结构稀疏值。在结构稀疏的指引下，相较于纹理区域，处于边缘和角落的块有更高的优先级。2）块优先：最后的块优先级被定义为带有块置信期的结构稀疏乘变换：。是块的准确度，指出了块中颜色和强度的可靠性。11和12类似：，是像素的颜色和强度的准确度，并且从丢失区域中的0或者已知区域中的1开始增减。在块修复的每个步骤之后，新填充的像素的准确度被块核心像素的准确度取代。是从它的原始区间到区间的线性变换，设为0.2。这种变换使其结构稀疏与的比较等级不同。通过将这两个变量相乘，图像修复算法将先修复处于图像结构中的块，并带有更高的颜色和强度的准确度，然后就能更好地修复带有纹理和结构的丢失区域11,22。B. 比较基于等灰度的优先级基于结构稀疏的优先级比基于等灰度的优先级能够更好地识别结构11,22，它运用了等灰度方向的内在产物和前向填充的正常方向。图3三展示了一个关于具有纹理和模糊边缘图像的修复例子。图3（a）表明了基于等灰度优先级的图像修复过程，图3（b）表明了使用结构稀疏优先级的图像修复过程。11和22中的纹理合成技术包含了两种情况。丢失区域右上角的块通过使用基于等灰度的优先级有更大的优先权，因为等灰度方向与在中心像素中前向填充的拼写方向几乎一样。比如，图3（a）中的第一幅图像的纹理区域中的块有最高优先级，并且模糊边缘不能被准确地恢复。但是不论前向填充是怎么样的形状，基于结构稀疏的优先级能够更好地识别出结构。比如，图3（b）中的有最高优先级的块，利用基于优先级的结构稀疏，它完美地修复了丢失区域。C 利用块稀疏表示的块修复先用带有最高块优先级的前向填充块来修复图像。在传统的基于样本的图像修复技术11,22中, 被已知区域中的最佳匹配块填充。最近，一个非局部化的处理方法13被提出，即用几个非局部处理的相似块取代一个最佳匹配块。利用多重抽样，它能更好地预测丢失信息并达到更好的修复效果。但它常常会在修复图像过程中引入平滑效应。我们通过稀疏表示框架下的多个样本的稀疏组合建立一个新的模型去修复丢失块。这种方法通过组合系数的稀疏优先达到了修复形状的效果，并且通过本地相邻的块外观的约束和周围纹理达到了一致的修复效果。1）块稀疏表示：表示要修复块，从图像源区取样一组候选块，是的候选块数。和准备工作13,36类似,候选块作为的最相似块，的选择在IV-E中有所讨论。表示中的未知像素的矩阵。基本上，是近似为的线性组合（4）然后未知像素集被中对应的像素填充，即（5）组合系数是通过稀疏表示框架下的降低约束最优化问题得出的。因为我们已经假定是的最稀疏线性组合，约束最优化问题的目标是最小化的规范，即的非零元素数。接下来，我们将介绍线性组合约束。我们现在介绍第一种类型的外观约束，称作本地块一致性约束。首先，我们设定估计的块应该近似目标块，即（6）是这个近似值的控制误差容限的范围。第二，我们进一步设定目标区域中新填充的像素应该和相邻块在外观上一致，即（7）和（2）中一样。这种约束测量了目标块和丢失像素相邻块的加权平均值的相似度。平衡了（6）和（7）中的的约束强度。它设为0.25。本地块一致性约束能在一个更紧凑的制定中被改写（8）（9）第二种约束的类型是向量的系数和为1：。这种约束被广泛地运用到当从的相邻候补块36,37重建目标块的本地线性嵌入图文的转换不变性中。在这种约束下，当只有的一个元素非零，那个元素一定是1。然后模型和传统基于样本的图像修复方法22一样，也就是使用最佳匹配块来填充修复块。最后，通过优化约束最优化问题来推断线性组合系数：（10）这个约束优化模型也能表示为能量最小化问题。（11）当和合适时，它相当于（10）中约束最优化问题。2）优化算法：一般来说，规范常规化重构模型是很难解决的因为它的组合性质。匹配追踪（MP）或者正交匹配追踪（OMP）38,39算法和基础追踪（BP）40算法能有效地检索稀疏表示和近似的最优解。另一种优化规范的方法是用规范突出问题。规范的重建模型是在统计文献中著名的拉索41。图4 使用块稀疏表示的前向填充的图像修复算法在实际应用中，简单OMP算法被广泛应用到凸显稀疏表示当中，也用在图像去噪29,30，编码42,边缘检测32,音频信号源分离43等中。对于（10）中的优化问题，为了获得稀疏线性组合系数，我们需要提出一个新的算法。与匹配追踪算法相同，我们逐渐从候选块组中选择非零系数块。假设我们已经在步骤m(denoted as中选择m个非零候选块，这步中的稀疏表示是下一步m+1，我们从剩余候选块中选择一个新的候选块。在（8）中带有最佳本地块一致性的块被选为新的非零元素，即（13）对于每个候选块，（13）中的系数组合通过优化取得。（14）在文献局部线性嵌入（LLE）37主流学术中，这个优化问题（14）有了不错研究成果。我们定义格拉姆矩阵，是数组的矩阵，是1的列向量。然后有个封闭形解（15）每一步中进行块的选择直到满足本地块一致性约束（8）或者的值增加。总的来说，用块稀疏表示来修复块丢失像素的算法如图4所示。最后的基于块稀疏的图像修复算法如图5所示。图6展示了三个例子，金字塔的右上角，窗框的穿越结构，弯曲失踪结构都被删除。如图6（b）（d）所示，用该方法逐渐修复丢失区域，图6（d）是用我们的方法修复的结果，里面删除的结构被成功地还原。在图6（e）中，我们也展示了22中与之最相似的算法的修复结果。与我们的结果相比，长方形结构没有被很完美的恢复。成功修复复合结构的重点在于，首先，基于稀疏的优先级能更好地控制块的填充要求；其次，块稀疏表示比22中单个最佳匹配样本提高了样本的泛化能力。图7给出了图8第二个例子丢失区域中200个块的非零系数数。由于系数的稀疏约束，只有候选块的稀疏数被相应地选择。相比以前的工作，这里使用了一个最佳匹配块或者固定数量的块的组合，这是一个很大的区别。稀疏表示的定量优势会在IV-B中阐述。IV. 实验和比较在这节中，我们会在自然图像中测试基于样本的块修复算法。我们提供我们的算法来除去划痕和文本，移除物体和修复块。在这些例子中，我们将拿我们的算法和基于扩散的算法，基于样本的算法以及基于稀疏的图像修复算法做比较。在接下来的例子中，如果没有特别说明，块大小为7X7，相邻块大小（即（1）中周围的）为了计算块相似设为51x51，、（10）中的容错范围设置为块中像素数的25倍，候选块的数目设为25。图5通过块稀疏的基于样本的修复算法图6图像修复的例子。（a）带有位置区域的输入图像。（b）（d）我们的方法的图像修复程序和最后结果。（e）22中方法的结果。（f）实际图像图7，给出了图8第二个例子丢失区域中200个块的非零系数数A. 出去划痕和文本的实验和比较现在用我们的修复算法以及基于扩散的和基于样本的图像修复算法来去除划痕和文本，然后做一下比较。由于基于扩散图像修复方法的过平滑效应，我们选择纹理和结构通道同时进行的修复算法10作为一个基于扩散修复算法的改进版本来比较。纹理和结构同时进行的修复算法表现为同时修复纹理层和结构层。实验采用相同的原始文件10中结构纹理分离方法和结构层中图像修复方法。Criminisi基于样本的算法修复修复了纹理层，它比纹理合成的方法9更适合纹理修复。我们将比较我们的方法和Criminisi基于样本的算法11,22和Wong基于样本的算法。图8 结构和文本移除比较。表1图8的展示了结构和文本移除的5个例子。第一行是原始图像。在余下的行中，从第一到第五行的图都是降解图，分别为用10的修复算法修复同通道纹理和结构的结果，基于样本修复算法11,22，Wong的基于样本的图像修复算法13,和我们提出算法的修复结果。通过测量被修复图像和原始图像峰值信号信噪比（PSNR）来定性比较修复结果的好坏。此外，每个颜色通道中的PSNR值会被归类展示。如图8所示，第三列中表示了Criminisi算法的形状修复结果。但是由于只有一个最佳匹配块被使用，结果中引入了一些不好的产物。例如，图8第二行红色框中是 Criminisi算法修复后产生的多余结构。由于使用了更多候选块，Wong的算法效果更好。例如，红色矩形框中的多余结构在Wong的算法修复结果中有所减少。同通道的纹理和结构修复算法很好地修复了图像的纹理和结构，并达到了很高的PSNR值。但是，就像11中观察到的那样，它引入了由扩散引起的沿结构产生的模糊效应。我们提出的算法强化了块优先级，候选块也相应地约束在稀疏表示的框架下，所以得到了准确而稳定的PSNR值。B 块稀疏对图像修复表现的影响这节中，我们从数量上来证明由结构稀疏和块稀疏表示能改进图像修复效果。为此，我们拿传统的Criminisi的基于样本的图像修复算法22作为基线，然后用基于结构稀疏优先级替代基于等灰度的优先级或者（和）用基于稀疏表示的块修复替代基于纹理合成的块，然后测量一下修复后的效果。表I 展示了六种修复算法的性能：Wong的基于样本的算法13（Wong），Criminisi的基于样本的算法22（Crim），基于等灰度优先级和基于稀疏表示的块修复模型44（Crim_Spar1）的方法，基于等灰度优先级和基于稀疏表示的块修复模型10 （Crim_Spar2），基于结构稀疏的优先级和纹理合成图像修复的方法（Spar_Crim），和提出的运用块稀疏（Spar）的修复算法。由此可见，Spar_Crim和Crim_Spar2的平均性能较基线分别增加了1.27和3.78dB。这说明了（10）中使用稀疏表示的块修复模型比基于结构稀疏优先级有更好的性能。如果用块稀疏更新块优先级和块修复，Spar的性能较基线增加4.16dB。Wong的算法33增加了2.55dB，比Crim_Spar2低。44中的修复模型利用基于等灰度优先级和稀疏表示模型没有本地块一致性约束，所以Crim_Spar1的方法比Crim_Spar2和Spar差。C 物体移除的实验和对比我们用提出的算法去修复在物体移除后的丢失区域。我们也来比较提出算法和相关的基于样本的修复算法。看图9的例子。第一和第二列是原始图像和降解图像。第三到第五列是Criminisi算法22，Wong的算法和我们的算法的结果。在Criminisi算法结果中，被修复块与周围纹理不一致，例如，例1图中的水中倒映的树木，例3图中石头边上的草。Wong的算法用了几个最佳的样本来推断未知块，所以修复效果较为一致。但是，它引入了平滑效应。就提出的算法来讲，因为受到本地一致性的约束，所以被修复块能与周围的纹理连贯。另外，修复块是通过候选块的稀疏组合来推断的，所以结果中只出现少量的平滑效应。图10中，我们来比较我们的算法和半自动修复算法45以及Criminisi算法22。半自动的修复算法45通过人工标记解决了丢失区域中结构模糊不清的情况，能很好地修复复杂结构。在第一个例子中，我们的方法自动地修复了移除汽车后的大面积丢失区域，结果能与45的结果相媲美。在第二个例子中，被隐藏的结构合理地被算法45恢复出来。但是，我们的算法只能恢复横向结构不能恢复被物体隐藏的围栏结构。这表明了我们算法的不足之处，即它不能恢复在已知区域中不能得到任何线索的丢失区域。在这两个例子中，我们的结果明显比22中的算法的要好，它有更好的视觉效果。图9物体移除的比较图10 45中例子的比较用16中的两个具有挑战性的例子比较我们的方法和基于片段的方法16，结果如图11所示。在第一个例子中，两种算法都达到了令人满意的视觉效果。在第二个例子中，方法16的结果使得苹果模糊不清。但是，我们的方法精确而合理地恢复了原始图像移除前的苹果。原因是块样本的稀疏组合给与了样本的表达能力同时保留了结构的锐度。图11 利用基于片段的方法和我们的方法完成16中的例子的结果图12，比较基于稀疏的图像修复算法。D. 比较基于稀疏的完整丢失块图像修复算法我们也来比较我们的算法和其他基于稀疏表示的修复算法。Guleryuz1820通过在变换域中适当地更新图像稀疏表示恢复了丢失块。Elad等人17通过把图像分解成纹理层和结构层46改进了这种方法，并且通过稀疏表示修复了图像。Fadili等人21提出了一个基于最小期望（EM）的贝叶斯模型，使用稀疏表示来修复图像。他们的算法已经达到了非常好的修复效果，特别是修复大小不超过16X16的的块。为了便于比较，我们从Guleryuz，Elad和Fadili的网页上下载了他们的算法源代码然后来修复大面积的丢失区域。对于Guleryuz的算法，我们用离散余弦变换（DCT,大小32X32）作为稀疏表示的基底。对于Elad和Fadili的算法，我们运行MCALab代码。我们设纹理层字典为大小是3