毕业论文：正文
学生姓名：何文俊 定稿时间：2012-05-24
第1章 绪论
1.1 课题背景
1.1.1 图像修复起源
图像修复技术是图像处理中的一个重要组成部分。它是一项十分古老的艺术，最先起源于欧洲文艺复兴时期。当时，为了恢复美术作品中丢失或被损坏的部分，保持作品的整体效果，人类凭借丰富的想象力，运用各种手段来填补裂缝、划痕，尽量恢复作品原貌。那时的目标对象还不是数字图像，没有备份，没有撤销，完全是针对原作实体的手工操作，因而需要由经验丰富的专业技术人员来处理，而且由于处理过程的不可逆性，使得一点点的疏漏都会让珍贵的艺术瑰宝得到致命的损坏，这种处理方式由于技术的限制，具有相当高的风险。
图像修复技术应用到数字图像领域的处理可以追溯到19世纪50至60年代早期美国和前苏联的空间项目。恶劣的成像环境、设备的振动，飞行器旋转等因素使图像产生不同程度的退化、损坏。在当时的技术背景下，这些损坏造成了巨大的经济损失。为此，许多科研工作者围绕着图像的还原、修复问题展开了研究。
1.1.2 图像修复发展历程
图像修复的原理是给定一幅有破损区域或空白区域Ω的图像I，尝试用该图像的已知信息来填补位置信息Ω，要求最终结果符合人眼的视觉习惯。当破损或待修复区域面积较大时，我们修复后的图像可能并不与原先的完整图像相同，因为未知区域Ω只是用人眼能接受的已知信息代替而已，而不是对未知信息的还原。这也就是数字图像修复作为图像复原技术的一个分支与其他图像复原方法最本质上的区别。
图像修复这一概念最早由Bertalmio[1]等人在2000年ACM SIGGRAPH会议上提出，这是一种通过解偏微分方程（PDE）完成的修复过程。由于基于PDE的算法其本质是平滑扩散的过程，因此基于PDE[1-3]或变分法[4-5]的图像修复技术只适用小范围、非纹理结构的修复问题，而当用来修复大片的空白区域是，此类方法会导致带填充区域的模糊[6-7]。
另一类图像修复技术，即基于样本块的修复能较好地处理大范围缺失或空白的图像。Drori[8]等人通过合成自适应片来不断迭代逼近未知区域，然而这种在图
- ５ -
毕业论文：正文
学生姓名：何文俊 定稿时间：2012-05-24
像的不同尺度内找最佳匹配的填充块的方法需要花费大量的运行时间。Jia[9]等人则要考对输入图像的分割来进行图像修复。另外有些方法采用用户交互的方式，如Sun[10]等人提出的方法要求用户指定结构性强的曲线，算法运用动态规划或置信度算法优先修复这些区域，然后运用一般的图像算法修复剩余区域。这些算法均采用贪婪性的修复原则，即像素块一旦填充便不再修改。近些年许多算法也多基于此思想，如一些学者尝试在小波域下进行修复[11]，或用优化算法优化能量函数来解决此问题，典型的优化算法有动态规划、置信度扩散[13]、EM算法[14-15]等，这些方法虽然这某些情形下处理后的全局效果会更好，但相应的算法复杂度也较贪婪性方法打打增加了。
1.1.3 本次论文的研究意义
Criminisi[16]等人在2002年提出了一种基于像素块级的算法是具有代表性的图像修复算法，之后的大部分算法都是在此算法上的改进[17-18]。此类算法都将样本块集合固定在一定大小的区域内，通过遍历整幅图像，不断匹配样本块与已知区域模块的SSD相似度来获取最佳匹配块进行填充，直至所有未知区域都被填充后，程序终止。
之所以选择实现这一类型的算法，是因为运用Criminisi的算法，不但能处理刮痕、噪声，还能处理块状区域信息丢失或者带有纹理结构信息的图像。这种方法已经能适用绝大多数类型的数字图像的修复了，这比较符合作者追求全面、完美的性格。然而，这类算法也有其不足之处。比如，由于每一次填充都要遍历整幅图像的所有像素模块，且需要对模块中的每个像素点值进行比较运算等操作，因此其程序的执行效率并不高。
对于本文实现的算法，作者在Criminisi算法的思想基础上，增加了自己的一些想法，并通过程序加以实现。比如，有一些研究者已提出自适应模板的方法，对纹理内容丰富程度不同的图像在模板上用特定方法加以选择，得出相对合适的样本块进行匹配，以满足样本多样性要求，有时也能提高算法效率。作者又在此基础上使用自定义模板，以便选择一种最佳尺寸模板，并可以对不同模板下的修复结果进行比较。其它，作为算法的研究，对图像的执行时间，处理质量等也做了比较研究。
1.2 本文研究的主要内容和组织框架
在本文第二章全面总结了近些年数字图像修复技术研究的现状。作者通过翻阅、查找文献了解了目前该项技术领域常见的模型和方法，其中包括BSCB模型、
- ６ -
毕业论文：正文
学生姓名：何文俊 定稿时间：2012-05-24
TV模型、CDD模型、纹理合成、基于样本匹配块以及小波、分形等的图像修复方法。在第三章，对基于样本块的一类算法进行了重点介绍，对比各种算法的优缺点和可行性。有了前两章节的基础，在本文的第四章当中，作者基于自身能力，以Criminisia基于样本的图像修复算法为基本指导思想，在脱离源代码的基础上构建一个简便、可行性好的程序完成这一算法，并在样本尺寸、模块匹配等方面做出改进。最后，在全文的结尾第五章中再对各种算法的优缺点做一次对比总结，提出数字图像修复技术在今后的研究中应该注意的一些问题。
- ７ -
毕业论文：正文
学生姓名：何文俊 定稿时间：2012-05-24
第2章 图像修复技术研究现状
2.1 图像修复技术研究
目前，国内外在图像修复技术的研究上主要集中于两个方面：基于像素操作的方法、基于块操作的方法，如图2-1：
图2-1 国内外图像修复技术研究现状
（1）基于像素操作的算法。这类算法的处理对象是像素点，常用于修复小面积破损区域，主要包括偏微分方程（PDE） 模型、基于邻域模板和插值的算法等。
PDE模型的主要利用待修复区域的边缘信息来估计等照度线(isphoto)方向，再利用传播机制将信息沿着等照度线的方向传播到待修复区域内。又可分为BSCB(Bertalmio-Sapiro-Caselles-Bellester)模型、整体变分(total variation，TV)模型和基于曲率驱动扩散的修复模型[19] (curvature-driven diffusions，CDD)模型三种模型。
还有就是基于邻域模板和插值的算法，这类算法采用的不是循环迭代的方法来求待填充点的值，而是套用范本或代入插值公式将其领域点的值直接计算来得
- ８ -
毕业论文：正文
学生姓名：何文俊 定稿时间：2012-05-24
到待填充点的值，这类算法主要分为如下几种：根据邻域现有的像素，采用插值的方法来计算待修复区域的像素值[20]；或是依靠定义修复区域像素点的优先级，来对优先级最高的点，用一个以待修复点为圆心的模板，筛选模板内与待修复点在同一等照度线的已知点，并用已知点与圆心的距离作为权值，计算出待修复点的值[21，22，23，24]；比较常见的还有通过去噪的方法来进行修复的，这种方法用邻近像素点的信息作为噪声检测依据来扫描图像中的每一个像素点，若是噪声点则它的值完全可以被代替，若是非噪声点就先保持原像素值不变，再根据损坏程度，利用加权方程计算出最终像素值[25]。
（2）基于块操作的算法。此类算法的处理对象是块状模板，例如5×5、7 × 7的目标块，这类方法比较适合修复信息丢失区域较大的图像，主要包括：基于样本的修复算法、基于纹理合成的修复算法、基于小波变换的修复算法以及基于分形理论的修复算法等.
基于样本的修复算法的主要思路是：先得到破损区域的填充前缘，计算填充前缘上所有点的优先级；然后选取优先级最大的点，按照一定尺寸的模板，在源图像中搜索与模板中已知部分点像素的均方误差最小的块，最后传播纹理及结构信息并更新置信度。这种方法拥有变分PDE 模型和纹理合成两种方法的优点，因为照片通常是由线性结构和纹理结构复合组成的，不同图像区域之间的边界是不同纹理之间相互影响形成的，所以单一纹理合成方法不能解决这样的问题；至于变分模型则是通过把线性结构传播至目标区域来填充图像中的空洞，其扩散过程会引发一些模糊，当填充较大的区域时，由变分PDE 模型引起的模糊就变得尤为明显了。而基于样本的图像修复算法正好既复制纹理又复制结构，且其纹理和结构信息的传播只需要一个单独、有效的算法就能实现。
基于纹理合成的图像修复算法是图像修复过程中应用了纹理合成方法，典型的主要有两种方法：非参数取样的纹理合成算法[26] 和基于块拼贴的纹理合成算法[27]。其中，非参数取样的纹理合成算法是用Markov 随机域(MRF)作为模型进行非参数特征匹配的。这种算法从样本块开始，由内到外逐点扩散纹理。这种算法的实现步骤大致为：选择一个待修复点，然后根据其领域已知的或已合成的纹理点的值来计算该点的值，对待修复区域逐点进行计算修改，直到整幅破损图像都被修复完成为止。基于块拼贴的纹理合成算法[27]在纹理合成上的时间及视觉效果方面较其它方法都得到了很大的提高，并解决了纹理错位严重和容易产生模糊的问题。其实现原理是：先从待修复区域的边界上选取一个像素点，并以这一点为中心，以图像的纹理特征为判断标准，选取大小合适的纹理块建立模板，然后在图像源区域中搜索与之最匹配的纹理块来填充该纹理块的丢失部分。
小波域的修复算法的主要思想是先利用小波变换把图像分解成高频成分和
- ９ -