数字图像修复技术

毕业论文（设计）正文

题目：图像修复技术研究

（Research on Digital Image Inpainting）

学 院：计算机与信息工程学院 专 业：计算机科学与技术 班 级：计科0802 学 号：0812300225 学生姓名：何文俊 指导教师：朱云芳

二○一二 年 五 月

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

图像修复技术研究

摘 要：

数字图像修复技术对局部区域有数据丢失或损坏的数字图像按照某种特定规则进行处理，以恢复原图像的完整性。数字图像修复技术在修复破损文物字画、修复由网络传输等原因引起的残缺图像、去除图像及视频中的文字和划痕、以及移除目标物体后的背景恢复等方面都有广泛的应用。

本文首先阐述数字图像修复技术的基本原理、起源和目前国内外的研究状况，并对当前存在的一些典型的数字图像修复算法进行介绍、分析，指出其优缺点和适用范围。对某些算法作重点论述，并在分析其算法后提出适当的建议改进。在此基础上，结合毕业设计的要求，研究Criminis基于样本的图像修复算法思想，并给出实验结果，分析其优缺点及产生原因，并作出进一步改进。

在文章的结尾，将会对之前提到的算法进行归类总结，依据现有各种算法其自身的优缺点或是其在适用范围上的局限性等，总结当代数字图像修复技术的特点和发展趋势，提出该技术在今后的进一步研究发展中需要注意的几个问题。

关键词：

数字图像修复； 曲率驱动扩散；置信度；纹理；优先级

- １ -

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

Research on Digital Image Inpainting

Abstract:

In order to restore the integrity of the original image, Digital image inpainting techniques using a certain rule to deal with the loss data and corrupted image on the local area. Digital image inpainting techniques has a wide range of applications in many areas, it can repair damaged cultural relics calligraphy and painting, reapir incomplete images which caused by network transmission, remove the words, scratches and noise in picthures or videos, and it can also recover background while an object on it has been removed.

This paper describes the basic principles, the origin and the present research status about digital image inpainting at first. Then it displays some current digital image restoration algorithm and point out their advantages and disadvantages and scope of application by comparison. Focused on some algorithms, it makes some appropriate recommendations to improve the analysis algorithm. On this basis and combined with the graduation project requirement, this paper researches Criminis’s repairing algorithm and has gotten the experimental results to analyze the advantages and disadvantages of the algorithm and at last makes a further improvement.

At the end of the article, we summarize the algorithm that are mentioned before and then get out the advantages and disadvantages, and the limitations on the application scope based on these existing algorithms. At last, we come up with several issues about the development of digital image inpainting technique in the future, in according to the characteristics and the development trends of the digital image techniques.

Keywords: Image restoration technology; curvature-driven diffusions; confidence term; texture; priority.

- ２ -

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

正文目录

第1章 绪论........................................................................................... ５

1.1 课题背景...................................................................................................... ５

1.1.1 图像修复起源 .................................................................................................. ５ 1.1.2 图像修复发展历程 .......................................................................................... ５ 1.1.3 本次论文的研究意义....................................................................................... ６

1.2 本文研究的主要内容和组织框架.............................................................. ６

第2章 图像修复技术研究现状 .......................................................... ８

2.1 图像修复技术研究...................................................................................... ８ 2.2 本章小结.................................................................................................. １０

第3章 基于样本块的修复算法 ...................................................... １２

3.1 Criminisi 算法 ......................................................................................... １２ 3.2 传统基于样本块的图像修复算法的实现.............................................. １２

第4章 作者改进后的算法 .............................................................. １４

4.1 本文算法的特点...................................................................................... １４ 4.2 改进后的处理方式.................................................................................. １４

4.2.1 算法的思想 .................................................................................................. １４ 4.2.2 算法的大致实现步骤................................................................................... １５ 4.2.3 图像处理的结果对比................................................................................... １６

4.3 本章总结.................................................................................................. ２２

第5章 全文总结和前景展望 .......................................................... ２４

5.1 全文总结.................................................................................................. ２４ 5.2 数字图像研究前景.................................................................................. ２４

参考文献 ............................................................................................. ２５ 致谢 ..................................................................................................... ２８

- ３ -

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

附录 ..................................................................................................... ２９

- ４ -

毕业论文：正文

学生姓名：何文俊 定稿时间：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]在纹理合成上的时间及视觉效果方面较其它方法都得到了很大的提高，并解决了纹理错位严重和容易产生模糊的问题。其实现原理是：先从待修复区域的边界上选取一个像素点，并以这一点为中心，以图像的纹理特征为判断标准，选取大小合适的纹理块建立模板，然后在图像源区域中搜索与之最匹配的纹理块来填充该纹理块的丢失部分。

小波域的修复算法的主要思想是先利用小波变换把图像分解成高频成分和

- ９ -

毕业论文：正文

学生姓名：何文俊 定稿时间：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次方的运算，以获得更好的匹配，且也不会增加太多的运算量。

- １４ -

4.2.2 算法的大致实现步骤

算法的大致实现步骤：

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

首先根据图像特征用绘图工具将待修复区域用一种纯色填充；（1） 假设待修复区域已经人为标记为红色，那么对整幅图像进行扫描后，将带修复区域的点用0表示，已知图像区域的点用1表示；（2）

寻找填充前缘。条件：在填充前缘的点自身标记为1，且其上下左右四个邻近点的标记至少有一个1和一个0；（3）

计算边缘上每个点所在目标块的优先级。P(p)=C(p)*D(p)。每个像素点的初始置信度设置分别为C(p)=0（p为待填充点）和C(p)=1（p为已知点）。等照度线方向的单位向量可用图像在x和y方向的灰度梯度表示，边缘法线单位向量用做好标记的点（即用0和1分别表示了未知和已知点）的梯度表示；（4）

在所有目标块中找出最高优先级的目标块Ψp；（5）

对灰度图像进行扫描，在已知图像区域φ中找出与Ψp最匹配的模块Ψq，用于填充Ψp区域。可将Ψp中已知点的灰度值与Ψq中对应点的灰度值进行标准差运算，得出标准差结果中最小的Ψq就是我们想要的填充块；（6）

将Ψq的像素值复制到Ψp位置；（7）

修改填充后模块Ψp的置信度值：C(p)=C(q)（这里的C(q)是最佳匹配块Ψq的置信度值），同时将已填充了的点标记为1；（8）

重复(3)~(8)步骤（注：像素点的置信度已不再需要初始化）；（9） 程序结束。当边缘点个数为0时，程序结束退出。（10）

图 4-1 程序运行时的部分界面截图

- １５ -

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

图 4-2 界面右侧显示的图像属性

4.2.3 图像处理的结果对比

以下是作者参照软件测试的原则用不同的输入图像对程序做出的测试结果中的部分截图比较，以验证程序的可行性和执行结果。图4-3和图4-4是未损坏的完整图像，之后的组图都用一幅损坏的输入图像和经修复处理后的图像作比照。（文中采用的图像均为位图，jpg格式的可先另存为位图后再进行操作）

图 4-3 完整图像一。大小100*100.

图 4-4 完整图像二。大小480*300.

图4-5至图4-8的组合表明，本程序适用于不同颜色、不同形状的待修复区

- １６ -

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

域，采用不同的模板时处理效果和运行时间都不相同（图4-7中处理后的杂质是由画笔颜色的不纯引起的，因此用9*9模板显得小了，未能修复所有点）。

(a) (b) 入图像；图（b）为处理后的输出图像。

图 4-5 图像大小100*100，采用模板大小15*15，用时5.36 s。图（a）为输

(a) (b) 入图像；图（b）为处理后的输出图像。

图 4-6 图像大小100*100，采用模板大小15*15，用时4.36 s。图（a）为输

(a) (b) 图像；图（b）为处理后的输出图像。

- １７ -

图 4-7 图像大小100*100，采用模板大小9*9，用时1.75 s。图（a）为输入

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

(a) (b)

图 4-8图像大小100*100，模板大小15*15，用时2.25 s。图（a）为输入图

像；图（b）为处理后的输出图像。

图4-9、图4-10和图4-11三组图像的大小均相同，但在图像修复处理时采用了不同尺寸的模板，用15*15的模板时，可见眼睛和鼻子的特征被填充到待修复域当中了，这是因为输入图像原本就比较单调，且眼睛处的纹理特征与待修复区域十分相似，因而出现了图4-9的结果。但当我们采用3*3模板时，由于每一次迭代时几乎只填充了模板中一个像素点，而其余的点都用来做运算判断了，所以尽管输入的仍然是这幅较为单调的小图像，在用3*3模板处理后已经有十分不错的处理结果了。然而，我们能够发现，虽然图4-11的处理效果较好，但是由于每一次迭代时被真正被填充的个数变少了，导致相应的迭代次数增加，所以总的运行时间变长了。这在处理较大图像时，增加的时间复杂度会更多。

(a) (b)

图（b）为处理后的输出图像。

- １８ -

图 4-9 图像大小100*100，模板15*15，用时3.61 s。图（a）为输入图像；

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

(a) (b)

图（b）为处理后的输出图像。

图 4-10 图像大小100*100，模板9*9，用时3.98 s。图（a）为输入图像；

(a) (b)

图（b）为处理后的输出图像。

图 4-11 图像大小100*100，模板3*3，用时4.29 s。图（a）为输入图像；

现在，我们增加图像的尺寸，并选取纹理结构更丰富的图像来检验我们的程序。图4-12的输入图像较之前的图像已经大了许多，因而在处理过程中的运行时间也上升了一个数量级，这主要是由于搜索的像素模块和搜索次数增加的缘故。我们看到，用25*25的模板处理时用时相对较短，待填充域中纹理特征也很明显，但是这种纹理特征并不是我们想要的结果；而在图4-14的结果中，我们采用5*5的模板，这种模板的耗时较25*25的模板只增加了少许，但处理效果却好上很多，因为用5*5的模板时每次填充的像素点较少，增加的纹理特征效果也相应弱了许多。但是，我们能够发现，使用5*5的模板填充时，待填充域出现了些许的模糊，这与基于像素点的匹配方法情况十分相似。

- １９ -

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

图 4-12 输入一幅有纹理区域丢失的图像，图像大小336*210.

图 4-13 输出结果，图像大小336*210，模板25*25，用时41.86 s。

图 4-14 输出结果，图像大小336*210，模板5*5，用时43.63 s。

由于处理划痕耗费的算法复杂度较小，这允许我们采用的输入图像更大了，虽然相应的运行时间也仍旧变得更多了，但我们可以清晰地看到处理划痕时，采

- ２０ -

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

用较小的模板，不仅耗时少，而且处理效果也较好，唯一的遗憾是出现轻微的模糊。

图 4-15 输入一幅待划痕的图像，图像大小480*300

图 4-16输出结果，图像大小480*300，模板25*25，用时210 s。

图 4-17 输出结果，图像大小480*300，模板9*9，用时145 s。

- ２１ -

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

图 4-18 输出结果图像大小480*300，模板5*5，用时131 s。

4.3 本章总结

结合第3章的介绍，本章第一节简要地论述了本文算法的优越之处。首先，最惹人注目的是本章的样本模板大小是可调的，这比自适应样本大小的算法思想又向前迈进了一步。因为自适应样本大小的方法虽然已经选取了较为合适的样本尺寸，但由于真实世界的图片内容丰富多彩，图片大小并不固定，而且破损程度和破损位置也具有很大的随机性，因此，在自适应样本大小选取法则的固定限制下，这种算法很难找出最合适的样本大小。而对本算法采用的正方形样本，只要其大小在Int范围内，那么其边长可以选取自3开始的所有奇数。因而，我们总能找到最合适的样本尺寸以使修复后的图像更合理。

其次，本文在程序中增加RGB三种基色的控件响应事件，这样覆盖区域的初始填充颜色可以是RGB的任何一种颜色的纯色，这样就可以针对不同色彩分布的图像选取相应的纯色来做第一次的赋值处理，使得图像算法的匹配程度会更高。当然，（若脱离本次毕设的要求）我们还可以稍稍修改下算法，使得处理的对象不再是纯色，而是一定范围内的所有图像值，这样还能在处理划痕时避免因画笔颜色不纯而引起的误差。如此安排，虽然算不上是太多的创新，但显然使我们操作起来方便了许多。

第三，本文在现有基于样本的图像修复算法的基础上，在寻找匹配块的算法中，还增加了一条用于判断最优匹配块的运算（详见本文4.2节）。这样，既能增加匹配度，也不会对运算造成太大的负担。

当然，本文算法仍存在许多不足。比如，对于大图像的处理时间打几十秒甚至上百秒，这对于大多研究者来说都是不能接受的；其次，本文算法在计算纹理

- ２２ -

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

结构信息时沿用了传统基于样本的算法（即梯度算法），因此，对于纹理结构特征突出的图像块区域处理时仍存在无力感，这是因为图像结构纹理、特征的丰富多变，而算法只能设定有限的规则，满足不了所有的结构信息变化。

- ２３ -

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

第5章 全文总结和前景展望

5.1 全文总结

全文首先介绍了数字图像修复原理，产生和发展的历史背景，数字图像修复的应用；接着在第2章介绍了国内外数字图像修复算法的研究现状，并对基于像素和基于块区域的两大类算法中的几个分支的特点做了简单的介绍，并分析了它们的优缺点；在第3章中介绍了基于样本块修复算法的典型Criminisi算法的基本思想，紧接着又详细叙述了传统的基于样本块的修复算法的原理和计算方法，为第4章中的本文算法的导出做了铺垫；在第4章，又是先描述了其它研究者在Criminisi算法和传统基于样本块算法的基础上尝试的改进，在这一层渲染之后，最后论述了本文算法的思想和实现步骤，阐述本文算法的优越之处。而且，还通过不同类型的测试图像的处理结果对比，进一步验证了本文算法的优点和可行性，也总结出算法本身仍然存在的不足之处。

5.2 数字图像研究前景

数字图像修复技术是一门实践性和应用性都很强的现代技术，它涉及很多门学科领域的研究成果，有着广泛的应用空间。但是，纵观全文的论述，不难发现当前的图像修复技术尚未纯熟，都有着这样那样的不足之处。究其原因，是因为数字图像修复反映的结果是人们视觉上觉得合理、易于接受的图像形式，意即是对人类思维的模拟。因此，作者认为，到了科学技术发展的某一天，人类可以扫描大脑所期待的图像亦或是能够根据人类的思维认知模拟出结果，那么得出的结果必将是令人满意的。

- ２４ -

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

参考文献

[1] Bertalmio M，Sapiro G，Caselles V，et al. Image inpainting [C]// Proceedings

of SIGGRAPH. New York，USA：ACM，2000:417-424.

[2] Bornemann F，Marz T. Fast image inpainting based on coherence transport [J].

Journal of Mathematical Image and Visual，2007，28（3）：259-278. [3] Tschumperle D，Deriche R. Vector-valued image regularization with PDE’s：

a common framework for different applications [C]// Proceedings of IEEE Computer Vision and Pattern Recognition (CVPR). Madison，USA：University of Wisconsin，2003：651-656.

[4] Ballester C，Bertalio M，Caselles，V，et al. Filling-in by joint interpolation of

vector fields and gray levels [J]. IEEE Transactions on Image Processing，2001,10（8）：1200-1211.

[5] Chan T，Shen J H. Euler’s elastica and curvature based inpainting [J]. SIAM

Journal on Applied Mathematics，2002，62（3）：1019-1043.

[6] Shao X W，Liu Z K，Song B. An adaptive image inpainting approach based on

TV model [J]. Journal of Circuits and Systems，2004,9（2）：113-117. [邵肖伟，刘政凯，宋壁. 一种基于TV模型的自适应图像修复方法[J]. 电路与系统学报，2004,9（2）：113-117.]

[7] Ding W. One class of nonlinear diffusion equation and its application in image

inpainting [J]. Journal of Shanghai Jiaotong University，2004,38（1）：153-156. [丁雯. 一种非线性扩散问题及其在图像修复中的应用[J]. 上海交通大学大学学报，2004,38（1）：153-156.]

[8] Drori I，Cohen-Or D，Yeshurun H. Fragment-based image completion [J].

ACM Transactions on Graphics，2003，22（3）；303-312.

[9] Jia J，Tang C K. Inference of segmented color and texture description by

tensor voiting [J]. IEEE Transactions on Pattern Analysis and Machine Itelligence，2004,26（6）：771-786.

[10] Sun J，Yuan L，Jia J，et al. Image completion with structure propagation [J].

ACM Transactions on Graphics，2005，24（3）；861-868.

[11] Chen R H，Wen Y，Yip A M. A fast optimization transfer algorithm for image

inpainting in wavelet domains [J]. IEEE Transactions on Image Processing，2009，18（7）；1467-1476.

- ２５ -

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

[12] Chen Z G，Liu L G，Wang G J. Examplar-based image completion using global

optimization [J]. Journal of Computer Research and Development，2009，46（1）：144-150. [陈中贵，刘利刚，王国瑾. 基于全局优化的图像块填充修复方法[J]. 计算机研究与发展，2009,46（1）：144-150. ]

[13] Komodakis N，Tziritas G. Image completion using efficient belief propagation

via priority scheduling and dynamic pruning [J]. IEEE Transactions on Image Processing，2007，16（11）；2649-2661.

[14] Kwatra V，Essa I，Bobick A，et al. Texture optimization for example-based

synthesis [J]. ACM Transactions on Graphics，2005，24（3）；795-802. [15] Xiao C X，Huang Z Y，Nie Y W，et al. Global texture optimization

incorporating with image detail [J]. Chinese journal of Computers，2009,32（6）：1196-1205. [肖春霞，黄志勇，聂勇伟，等. 结合图像细节特征的全局优化纹理合成 [J]. 计算机学报，2009，32（6）：1196-1205.]

[16] Criminisi A，Perez P，Toyama K，Region filling and object removal by

examplar-based inpainting [J]. IEEE Transactions on Image Processing，2004，13（9）；1200-1212.

[17] Peng K Y，Dong L F. A fast image inpainting algorithm based on average gray

value [J]. Journal of Image and Graphics，2010，15（1）：50-55.[彭坤杨，董兰芳. 一种基于图像平均灰度值的快速图像修复算法[J]. 中国图像图形学报，2010,15（1）：50-55. ]

[18] Orii H，Kawano H，Maeda H，et al. Image complection with generation of

rotated patterns and efficient matching [C] // Proceedings of IEEE International Symposium on Circuits and Systems （ISCAS）. Taipei，Taiwan，China：University of the National Cheng Kung，2009:3190-3193.

[19] Chan T, Shen J. Non-texture inpainting by curvature-driven diffusions (CDD).

Journal of Visual Communication and Image Representation, 2001, 12 (4):436-449.

[20] 樊红丽， 焦永和， 程颖. 基于插值的残缺图像的修复算法[J]. 兵工学报，

2005，26（1）：86-89.

[21] 周春霞， 吴锡生. 基于方差和边缘插值的邻近点图像修复算法[J]. 计算机

工程与应用，2008，44（14）：184-186.

[22] 檀结庆， 汪忠庆. 一种新的基于邻近像素点的图像修复算法[J]. 合肥工业

大学学报，2006，29（9）：1072-1076.

[23] 段汉根，汪继文. 基于邻域滤波的图像修复[J]. 计算机技术与发展， 2007，

- ２６ -

17（10）：34-36.

毕业论文：正文

学生姓名：何文俊

定稿时间：2012-05-24

[24] Alexandru T. An image inpainting technique based on the fast marching

method [J]. Journal of Graphics Tools，2004，9（1）：25-36.

[25] Luo Wenbin. An efficient algorithm for the removal of impulse noise from

corrupted images [J]. Int J Electron Communication，2006，10：1-5. [26] A.Efros，T.Leung. Texture Synthesis by Non Parmaetric Sampling.

Proeeedings of the Seventh IEEE International Conefreneeon Computer Vision. 1999：1033-1038.

[27] A.A.Efros，W.T.Freeman. Image Quilting of Texture Synthesis and Transfer.

Proceeding of ACM SIGGRAPH，2001：241-246.

[28] 张平，檀结庆，何蕾. 基于离散小波变换的图像修复方法[J]. 计算机应用

研究，2007，24（9）：287-289.

[29] 肖志云，张文霞. 小波域的纹理图像快速修复算法[J]. 仪器仪表学报，

2008，29（7）：1422-1425.

[30] 白宗文，基于分形的数字图像修复算法研究[D]. 延安：延安大学硕士学位

毕业论文，2008，6.

[31] 杨秀红，数字图像修复技术的研究[D]. 西安：西安建筑科技大学硕士学位

论文，2009，7.

[32] 沈峘，理顺明，毛建国，辛江慧. 数字图像复原技术综述[J]. 中国图像图

形学报，2009，14（9）：1006-8961.

[33] 孟春芝，何凯，焦青兰. 自适应样本块大小的图像修复算法[J]. 中国图像

图形学报，2012，17（3）：337-341.

[34] Yonatan Wexler, Member, IEEE Computer Society,Eli Shechtman, Student

Member, IEEE Computer Society, andMichal Irani, Member, IEEE Computer Society, Space-Time Completion of Video, IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 29, NO. 3, MARCH 2007.

[35] 徐梦溪，徐枫，黄陈蓉，李铭. 优化-最小求解的广义总变分图像复原[J]. 中

国图像图像学报，2011，16（7）：1317-1325.

[36] 张晴，林家骏. 纹理分布分析的快速图像修复算法[J]. 中国图像图形学报，

2012，17（1）：123-129.

- ２７ -

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

致谢

随着告别母校、迈入社会的钟声渐渐临近，我的人生也将迈向一个新的起点，而此次毕业设计，将是我在母校完成的最后一件作品了。在本文即将完结之际，我的心中对本次课题的研究学习感触颇多，而心中更是充满了对老师、朋友、同学和父母亲人的感激之情。仔细想来，在浙江工商大学的4年如白驹过隙，在执着求学、在青春热血、在放肆哭笑中就这么匆匆过去了。时光飞逝，岁月如梭，大学生活去得匆忙，留下得点点滴滴却回味不尽。

在大学的四年里，学会了数月不回家的独立生活，学会了对着程序手指如飞，学会了释放青春的疯狂，学会了面对未来的成熟淡然。这一切的喜怒哀乐，这一切的成长，都让我的人生真实又真实。老师的谆谆教导，同学的扶持互助，一个个熟悉而又陌生面孔的善意提点，还有家人的牵挂眷顾，这所有伴随我成长的人，我都要感谢他们。

在论文结尾之际，我首先要感谢我的知道老师朱云芳老师。朱老师在整个过程中牢牢替我们几个学子把关，认真负责地监督教导我们完成毕业设计的一步一跬，悉心地为我们答疑解惑。正是因为朱老师尽职尽责的工作态度和尽心尽力的教学指导，我才能顺利地完成我的毕业设计和毕业论文。在我的心中，朱老师是一个学识渊博、热心待人、认真负责、以身作则的好教师，这也对我的待人处事产生了很大的影响，再一次感谢我的导师朱云芳老师！

当然，大学并不止于毕业设计的终结，更不是一片《致谢》所能描画的。对此，我只能对所有辛勤工作的老师和朝夕相对的同学们表示感谢。正是因为有了你们，才让我在即将面对社会漩涡冲刷涤荡前的四年里体会到了年轻人的朝气，让我有能力有信心面对未知的恐惧与迷茫。感谢你们无私的支持与帮助！

最后，我必须要感谢我的父母。生我养我二十多个寒暑里，我的父母总是无私地支持和关怀着我。父母用自己额头一根根的白发始终为我维持了一个温馨舒适的家，这是我永远的避风港湾。无论多么地疲累，无论多么地伤怀，当再次走出家门面对世界时，展现的又是一个充满阳光自信我。我，爱我的父母，大恩不言谢，但不谢更让为人子女心中感愧！

有始有终，终点又变成新的起点。大学四年里我积累了一笔宝贵的财富，新的财富要从新的人生中获取。走出校门，我笑对一切！

祝愿所有热爱世界、热爱生命的人都能心想事成，实现自己的理想！

- ２８ -

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

附录

在附录自适应样本大小确定原理的图中，Ω为破损区域，其余部分信息为信息完好区域，图f-1中以p1、p2、p3、p4为中心的矩形块表示以破损区域边界像素为中心的待匹配块。从图f-1中可以看出，椭圆线条所包围的区域结构变化比较明显，因此其附近的像素点，如点p1、p2处，应该选用较小的样本块进行修复；而对于结构平坦的区域，如点p3、p4处，则应该选择较大的样本块。

图f-2右上角标出了以像素p为中心的3个不同大小的样本块，其中p为待修复图像破损区域边缘处具有最大优先权的像素点。从图中可以看出，当样本块大小由较小的矩形框（短划线）扩大到最大的矩形框（虚线）时，图像中信息完好区域的结构信息发生了显著变化，因此若采用图中最大的矩形框（虚线）的大小作为最优的样本块大小，容易产生结构错位的现象，而选取较小的矩形框（短划线）的大小则不会产生上述问题。

然而，从图f-2中也可以看出，若选择矩形框（短划线）作为样本块大小，在图像完好区域内无法找到与之具有较高匹配度的样本块，最多只能找到左下角以q2点为中心的矩形块。为此，这里在选取最优匹配块的过程中，对于源匹配块与待匹配块之间的误差进行了一定限制，当无法找到满足条件的匹配块时，减少样本块大小，从而在样本块尽量大的前提下保证图像修复效果，即点p应该选取最小的矩形框（实线）的大小为最佳修复块大小，此时能够找到图f-2左下角以q1点为中心的矩形框作为其最优匹配块。

- ２９ -

图f-1 选取模板块原理图

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

图f-2 选取匹配块原理图

本算法的步骤可以归纳如下： （1）

确定待修复区域各像素点的优先权，选取具有最大优先权的像素点p，通过一定方法判断、对比、分类计算后得出最优样本块大小；

（2） （3） （4）

备注：本附录引用 孟春芝，何凯，焦青兰. 自适应样本块大小的图像修复算法[J]. 中国图像图形学报，2012，17（3）：337-341.

在图像信息完好区域搜索最优匹配块，计算匹配误差，若满足约束条件式，则执行步骤（3），否则降低样本尺寸重新执行步骤（2）； 填充待修复点信息，更新置信度； 重复上述步骤，直到修复完成为止。

- ３０ -

图f-1 选取模板块原理图

毕业论文：正文

学生姓名：何文俊 定稿时间：2012-05-24

图f-2 选取匹配块原理图

本算法的步骤可以归纳如下： （1）

确定待修复区域各像素点的优先权，选取具有最大优先权的像素点p，通过一定方法判断、对比、分类计算后得出最优样本块大小；

（2） （3） （4）

备注：本附录引用 孟春芝，何凯，焦青兰. 自适应样本块大小的图像修复算法[J]. 中国图像图形学报，2012，17（3）：337-341.

在图像信息完好区域搜索最优匹配块，计算匹配误差，若满足约束条件式，则执行步骤（3），否则降低样本尺寸重新执行步骤（2）； 填充待修复点信息，更新置信度； 重复上述步骤，直到修复完成为止。

- ３０ -

本文来源：https://www.bwwdw.com/article/4zc6.html