毕业论文：正文
学生姓名：何文俊 定稿时间：2012-05-24
低频成分，然后对不同频率做不同的处理。例如，文献[28]先是用离散小波变换把图像分解成高频部分和低频部分，然后对图像不同频率的部分用不同的参数系分别进行计算。图像的低频部分采用中值滤波和基于曲率驱动扩散相结合的方法进行修复。而高频部分则因为表示图像的边缘轮廓信息，且具有很强的方向性，所以对高频图像数据先进行分块，先用线性拟合求出每一块的方向，再根据方向信息进行修复；文献[29]的例子就是在小波域中利用小波系数的能量来确定待修复块的填充顺序，再结合纹理合成的方法来填充待修复区。因为是在小波域进行的，所以能够充分保留图像的细节信息，同时提升视觉效果。
分形理论的修复算法的基本原理是：先在待修复区域边界处取样，计算样本图像的分形维度，然后依据一定的搜索顺序在图像的已知点区域寻找与样图分形维度最接近的图像块，并将其填充到相应的待修复区域。这类算法的核心在于邻域搜索和相似度匹配[30,31]。就拿文献[30]来说，它在图像的结构部分采用的是成熟的基于偏微分方程的图像修复技术；而对于图像的纹理部分，却采用分形维度作为纹理的主要特征，再用分形纹理合成的方法进行修复。该算法的运用大大提高了修复速度，并且克服了先前的图像修复技术在边界、拐角点等位置不连续的缺点；文献[31] 先是在图像的完整区域中选取不互相重叠覆盖的定义模块，用分形理论的仿射变换形成码本后在码本中寻找与待修复模块最匹配的定义模块，并依靠基于方差和内积的方法缩小搜索范围和缩短搜索时间；最后，用最佳匹配块去填充待修复块。
2.2 本章小结
综上所述，基于像素的处理方法，通过算法的不断迭代，对于划痕、噪声、或是纹理特征不明显的小块破损区域的图像修复处理十分有效，但是对于带修复区域块较大、划痕较宽或者纹理结构特征明显的图像，修复后容易引起模糊，而且当这些矛盾更突显时，引起的模糊会更大；而基于块操作的图像修复方法则适用于修复丢失区域较大的图像，通过将目标块不断与源图像区域中已知模块的不断匹配进行填充，既能复制图像结构还能复制纹理特征。但是最大的不足则是由于匹配的像素块数量和重复次数太多，会使运行时间变得很长，因而在分形理论和小波域的处理方式上都针对这一缺点先进行分类，再分别用算法处理以求缩短程序执行时间，还有一项不足则是由于每次填充的都是包含纹理的块形区域，且填充的信息均来自图像的已知部分，因而当图像内容相对单调或是纹理特征相当精细复杂的图像，处理后会造成目标域整体上的内容缺乏多样性。
总之，基于像素在修复小区域面积的图像上效果极好，但适用范围有限；而
- １０ -
毕业论文：正文
学生姓名：何文俊 定稿时间：2012-05-24
基于块状区域的修复方法应用范围较广，但是尚有许多不足，最明显的是运行时间过长。
- １１ -
毕业论文：正文
学生姓名：何文俊 定稿时间：2012-05-24
第3章 基于样本块的修复算法
3.1 Criminisi 算法
Criminisi等人在2002年提出的一种基于像素块级的算法是十分具有代表性的一种图像修复算法，因为之后的大部分算法都是在此算法上的改进。
Criminisi算法的原理是先从图像I的整个已知区域I-Ω和未知损坏区域Ω之间找出其边缘δΩ，并在边缘域内选取样本块，样本块与邻接样本块之间存在像素点的重叠，形成样本块集合P={P（x1），P（x2），…，P（xN）}，其中p（xi）包含于I\\Ω，N是样本块的总个数，xi是样本块的中心像素。先按照一定原则确定待修复区域像素点的优先级，并以优先级最高的点为中心建立目标块（即样本块），然后在P中寻找与目标块最相似的模板，将得到的最佳匹配模板块的像素值填充到目标块的对应位置处。这样，经过多次迭代处理，最终完成整个破损区域的修补问题。
Criminisi算法思路清晰，也符合图像修复处理的逻辑过程，但显然，这样的算法运行时间不会太短。很遗憾的是，作者未找到Criminisi算法的源代码，且发现在寻求与目标块匹配时（可能是为了降低算法复杂度）搜索的区域为边缘点为中心的模块域，这种搜索方式在设计程序时需要考虑模板是否会超出整个图像的边界，不易操作，且这种方式的处理需要一个固定尺寸的模板，否则不但程序难以实现，还可能增加程序的运行量，得不偿失。
作者在自己的程序中使用的是一个可供用户自主选择大小的模板，因而这里不对Criminisi的算法做过多赘述。
3.2 传统基于样本块的图像修复算法的实现
传统基于样本块的图像修复算法大致可以分为以下几个步骤：首先，根据待修复图像的结构特征确定一个适宜大小的样本块，目前的文献大多默认选择9*9型。
然后确定各待修补块的优先级系数，其定义为： P(p)=C(p)*D(p) （3-1） 其中，C( p)为可信度项，D( p)为Ψp中的结构信息，且定义：
- １２ -
毕业论文：正文
学生姓名：何文俊 定稿时间：2012-05-24
?C(p)?D(p)?q?Ψp?(L??)C(q) （3-2）
|?p||?Ip?*np|? （3-3）
式中，Ω为破损区域，点P为破损区域边沿上的指定一点，Ψp 为以P为中心的待修复块， | Ψp | 表示模板区域的大小（即其中的像素个数），?Ip⊥和np都是单位向量， p ?Ip⊥代表p点的等照度线的方向，可以用灰度梯度表示，α 为归一化因子（对于常用的灰度图像，α =255），np是填充前缘?Ω 上p 点处的法向量。
最后，将最优匹配块中的信息复制到待匹配块中，并重复上述步骤，直到全部破损区域修复完成为止。
基于样本块修复算法的原理如图3-1：
图 3-1 基于样本块修复方法
- １３ -
毕业论文：正文
学生姓名：何文俊 定稿时间：2012-05-24
第4章 作者改进后的算法
4.1 本文算法的特点
无论是Criminisi的算法还是传统基于样本块的图像修复算法中，在整个修复过程中样本块的大小是固定不变的。然而，一幅图像中通常具有各种不同的纹理结构，对所有位置都采用相同大小的样本块进行修复，容易对图像修复的最终成果造成影响。因此，许多研究者设计程序时，都希望样本块大小能够根据待修复区域的局部结构信息进行自动调节，以满足不同结构区域信息自动修复的需要。为此，有人就提出一种样本块大小的自适应选取方法，即通过一定的规则让程序针对输入图像的不同纹理结构自动选择一种最佳的样本尺寸，这种规则在附录中会详细介绍，这里不做赘述。
本文在研究了Criminisi的算法后，运用控件将样本尺寸改成了可供用户自定义选择的方式，这样再每次处理时就可以直接选择所需要的模板而不需要修改程序的数据，方便我们研究比较。
此外，为方便处理不同的图像，本文的程序可将待修复区域根据图像特点用一种纯色填充后进行处理；且对处理后的结果进行运行时间、图像大小和匹配程度等的统计，以此来作为研究算法质量的依据。
4.2 改进后的处理方式
4.2.1 算法的思想
本文的算法思想与Criminisi和传统的基于样本块的算法思想大致相同，原理亦如图3-1，只是在一些细节上都采用自己的实现方法。比如，前面介绍的自定义模板大小和颜色选择等，还有在程序中对置信度的更新均直接采用填充的已知值，这样既不影响图像修复结果，也简化了运算；此外，还在搜索最佳匹配块的步骤中采用先求模板中匹配块与目标块像素点的方差和，再求求标准差的运算方法，并结合算法复杂度和图像处理效果两方面的考虑，对方差和相同的结果（如4个2的平方和与1个4的平方和，两者值相同，但为了视觉上的全局一致性，我们会选择采用前者的值）做了一个求4次方的运算，以获得更好的匹配，且也不会增加太多的运算量。
- １４ -