图像修复毕业论文

摘要

摘要

摘要

随着计算机的普及和数字图像技术的广泛应用，数字图像处理技术已成为计算机视觉领域的一个研究热点。图像修复是图像处理的重要组成部分，是对图像中的受损区域进行信息填充的过程，其目的是恢复受损的图像，并使观察者无法察觉图像曾经缺损或已被修复。

目前，图像修复算法根据待修复区域的大小，可以分为两类，即基于偏微分方程(PDE)的图像修复和基于纹理的图像修复。Bertalmio等人把偏微分方程引入了图像修复领域，其基本思想是根据物理学中信息扩散原理来完成受损区域的修复，当受损区域较小时，修复效果很好，没有任何修复痕迹，但当受损区域较大时，会出现模糊效应。因为这个缺点，基于纹理的图像修复逐渐成为该领域的主流算法，吸引了众多学者进行研究，该类算法不论对受损区域较大还是较小时都能取得很好的效果。

本文重点研究了Criminisi算法，在Criminisi算法的基础上，对模板大小、优先权计算方式、最佳匹配块的寻找等进行了改进。论文考虑模板边缘像素点的梯度信息，提出了自适应模板大小策略，以判断能否扩展，从而适应不同的纹理图像；同时对优先权的计算方式进行了改进，考虑了周边信息，引入相关项，同时为置信度、数据项和相关项分配相应权重，避免了单一乘法带来的缺陷；引入颜色直方图以改进最佳匹配块的寻找，颜色直方图定义了图像或图像中区域的颜色分布，并且颜色直方图具有旋转不变性和缩放不变性等。通过两个模块间颜色直方图的相交距离，从整体上考虑两个模块的相似性，从而减少错误匹配的概率。

最后通过对不同类型，包括纹理较丰富，结构较复杂，曲线较多的图片进行仿真实验，并与Criminisi算法和Sun等算法进行对比，说明了改进算法的有效性。

关键词：Criminisi，纹理合成，优先权，颜色直方图

ABSTRACT

摘要

PAGE

57

ABSTRACT

4.AnoveltruncationspuriousfreeDDFSstructureandalgorithmisproposed.ByintroducingacomparatorandanadderintothetraditionalDDFSarchitecture,thesinelookuptablecanbecompressedwithoutsignificanthardwarechangeinthedesigntoeliminatethetruncationspurswithoutincreasingthesizeofthelookuptable.

Keywords:frequencysynthesis,phasenoise,spurious,frequencyhopping

目录

目录

第一章绪论

1

1.1研究背景与意义

1

1.2国内外研究现状

1

1.3本论文的结构安排

1

第二章数字图像修复算法及模型

2

2.1图像的基础知识

2

2.2图像修复的问题描述

2

2.3基于偏微分方程的图像修复

2

2.3.1BSCB模型及原理

2

2.3.2TV模型及原理

2

2.3.3CDD模型及原理

3

2.4基于纹理合成的图像修复

2

2.4.1非参数采样纹理合成

3

2.4.2基于块的纹理合成

3

2.5本章小结

4

第三章基于纹理合成的改进算法

5

3.1Criminisi算法的缺点

5

3.2自适应大小的样本块

5

3.3优先权计算方式的改进

5

3.4模板匹配方式的改进

5

3.4.1模板的局部搜索过程

2

3.4.2SSD模板匹配方式的缺陷

2

3.4.3基于图像特征的模板匹配

3

3.5平滑过渡处理

5

3.6本章小结

5

第四章实验结果及性能分析

5

4.1实验环境及评价标准

5

4.1.1实验环境说明

2

4.1.2修复结果的评价标准

2

4.2仿真实验结果说明及对比

5

4.3本章小结

5

第五章总结与展望

5

5.1论文总结

5

5.2进一步研究工作

5

致谢

6

参考文献

7

攻

硕期间取得的研究成果

8

电子科技大学硕士学位论文

第一章绪论

第一章绪论

1.1研究背景与意义

图像修复技术，指用图像中的已知部分区域来填充修补图像中的受损区域，比如污点，裂缝等。广义上说，图像修复技术拥有十分悠久的历史，在中国，早在古代就已经有对书画文物、壁画等进行修复；在国外，图像修复早在欧洲文艺复兴时期就得到快速发展。由于历史和年代久远和保存不当等许多原因，许多珍贵的图片、文献、油画、雕塑等文物都出现了不同程度的破损，比如出现了折痕、斑点，或者缺失了一部分等。基于这些原因，出现了对这些受损文物进行修复的工作，对于破损区域较小的部分，修复过程称之为图像润饰(retouching)，比如划痕、污点；对于破损区域较大的部分，修复过程称之为图像补全(completion)。然而不管是图像润饰还是图像补全，都需要人们手工进行操作，而且是在原有文物上直接进行，这需要修复工作者具有丰富的经验和专业的技术，一旦修复者因为各种不可预计的原因而有所失误都会对这些珍贵文物造成不可逆转的破坏，同时因为是手工进行修复，因而修复的时间和质量都有严重限制，得不到良好保证。

随着因特网的不断普及以及图像处理技术的日益成熟，数字图像的应用领域越来越广。近几十年来，图像的存储方式也变得多样化，不再只是单一的纸张，而是包括相机、MP3、照片、胶卷等各种媒介。然而照片中有可能需要去除不该出现在照片中的物体，胶卷经过长久时间的放置或经常使用也会受到损害，从而可能会影响图片的质量，也影响了图片的美观和使用价值。图像日益影响着人们的日常生活和科学研究，在对图像处理过程中难免碰到各种图像的修复和补全问题，比如许多出土的珍贵历史文物往往是受损的，需要进行补全，以还原其真实面貌；或者在某张很珍贵的照片里，有可能出现不相干的路人，需要进行去除。如果再依靠手工这种低效的修复方式已经不合实际，同时也反应出图像修复潜在的巨大价值和市场。

计算机的出现使得图像修复工作不再需要手工操作，与手工修复相比，这不仅能极大的提高修复效率，同时对类似文物、书画等珍贵作品不会产生实质性损害，并且可以广泛应用到上述的各种图像处理中。

Bertalmio等人[1]在参考了修复者手工修复过程后，于2000年提出了数字图像修复这一概念。从这之后，图像修复开始受到广泛关注，中西方学者不断对其进行研究，并取得了重大成果。

1.2国内外研究现状

数字图像修复这一术语从2000年提出到现在已经超过10年，期间取得了重大突破。目前，按图像的结构、纹理和统计信息和先验概率等，图像修复算法主要分成三类：如图1-1所示。

图1-1图像修复算法类别

基于结构的图像修复技术，目前大多数都是基于偏微分方程模型来进行修复，而偏微分方程模型的主要思想是利用物理学中的信息扩散原理，即根据受损区域的边界信息，来确定沿着什么方向进行扩散和需要扩散哪些信息，从边界向里面扩散，使得受损区域越来越小，最终完成修复。该类方法主要用于修复受损区域较小的情况，例如划痕、污点等。

PDE模型在图像处理中得到广泛应用，包括图像去噪、图像放大、图像还原等。经典的基于PDE模型的图像修复算法有三个：BSCB模型、TV模型、CDD模型。Bertalmio，Sapiro，Caselles和Ballester[1]四人（即BSCB模型）最先使用PDE模型来解决图像修复问题。BSCB模型是根据手工修复原理，模拟其修复的整个过程，通过进行不断的迭代，根据物理学中的信息扩散原理，将已知信息沿着等照度线的方向不断向内传播，从而不断减小受损区域，最终完成修复的过程。等照度线是梯度的法向方向，即与梯度垂直，而梯度是信息变化最大的方向。所以沿着等照度线也就是沿着受损区域边界变化最小的方向。图1-2是使用该算法修复的结果。

图1-2Bertalmio算法去除划痕的修复结果[1]

结果表明，该算法适合于修复图像中的结构部分，修复效果明显，颜色过渡平滑，没有任何人工痕迹。与以前的图像修复算法相比，该算法的优点在于一旦启动后，无需人工干预，将人机交互最小化。但是，该算法的缺点也很明显，时间复杂度太高，执行速度非常慢；对大的缺陷区域的修复，会产生模糊效应等。

随后，Chan和Shen[2]提出了另一种基于变分原理的图像修复模型，基于这种模型的算法称为整体变分（TV）模型。TV模型采用了欧拉-拉格朗日方程，并结合各向异性扩散方程，然后利用变分方法求解。全变分模型为数字图像修复提供了一个有效的数学模型，该模型的主要优点是：实现更加容易，速度与BSCB相比成倍提升，并且修复区域的边界会尽可能的保持平滑。然而，TV模型也有很大缺陷：它不满足人们视觉的连接性准则，因为为了使能量函数最小化，它总是倾向于用最短的直线来连接断裂的线性结构物体，即在进行信息扩散时，只考虑了等照度线的强度，而没有考虑它的几何信息，从而出现断裂。

针对TV模型的这种缺陷，Chan和Shen在TV模型扩散机制的基础上提出了一种新的修复模型，这种模型考虑了曲率，即等照度线的几何信息，因而被称为曲率驱动扩散模型（CDD）[3]。引入曲率项后，信息扩散强度的值不仅依赖于等照度线的对比度或者强度，还依赖于等照度线的几何信息。在曲率值大的地方扩散强度大，曲率较小的地方扩散逐渐消失。CDD模型与TV模型和BSCB模型一样，都是基于偏微分方程，因而也与TV和BSCB一样，适用于无纹理的图像，但由于其是三阶偏微分方程，其计算复杂度较高，运行速度就相对较慢。

其它基于偏微分方程的方法还有Euler弹性模型[4][5]，Mumford-Shash模型[6]，Mumford-Shash-Euler模型[7]等。由于偏微分算法本身的信息扩散机制，它们对于缺失区域较小的受损图像，比如划痕，污点等，会有较好的效果；而对于受损区域面积较大时，不仅运算量剧增，而且会造成修复结果的模糊效应，这主要是因为连续迭代导致的图像过平滑现象。

纹理是图像中除结构外另一重要信息，它反映了图像的整体视觉特性。基于纹理的图像修复算法[13-16]该领域的另一重大突破，与基于PDE的图像修复相比，它能充分利用视觉认知规律的相似性原则，追求整体一致性，解决缺失面积较大时造成的模糊效应。目前，基于纹理合成的技术主要可以分为两类，这两类算法采用的思想大相径庭，其代表有Bertalmioetal[11]，H.Yamauchi[12]等。

Bertalmio等人提出对图像进行分割[8-10]，首先将图像分割成两部分：结构部分和纹理部分，然后分别对这两部分采用完全不同的修复技术，上述提到的基于PDE的算法能够很好的保持图像的线性结构，所以可以用来修复结构部分，而纹理部分可以采用基于非参数的纹理采样[17]进行合成，最终的修复结果通过将结构部分的修复效果和纹理部分的合成效果组合而得到。当缺失区域较大时，偏微分方程会产生明显的模糊效应，但会得到较好的结构信息。而纹理合成能够保存图片的纹理信息，而不用关注其结构部分。当最后叠加时也会存在模糊，不过与单纯偏微分相比，其修复质量还是有明显提高。

H.Yamauchi等人则采用纹理合成技术，这可以通过对样本自身不断复制来进行合成，也可以在已知区域中不断采样来进行纹理合成。基于样本的纹理很成技术，由于是在全局搜索以寻找最优匹配，利用的信息更充分，修复的结果也更明显。其主要思想是：由未缺损区域中根据相似性的定义采样合适的图像块，将其复制或合成到选定的缺损区域中，重复这一步骤，直到受损区域全部修复完成，同时保证纹理结构的连续性和相似性。这种方法不仅适用于修复受损区域较小的图像，同样适用于受损区域较大或者较大目标去除的图像。

2003年，Drori[18]等人提出了一种基于碎片的修复算法，该方法利用自相似原理，并提出置信度的概念来指导受损区域的修复顺序。该算法采用高斯金字塔，对待修复区域不断进行上下采样，并且对该区域不断进行快速平滑的迭代近似，将图像的已知部分拷贝到受损区域。在进行纹理合成时，通过拉普拉斯金字塔不断进行断上下采样来消除纹理合成时造成的过渡痕迹，使得修复区域更加平滑。但是由于该算法在多个层次上进行全局搜索匹配，因而修复速度十分缓慢，其论文说明，处理一副192*128的图片，耗时120s到419s之间，极大的影响了其适用范围。

2004年，Criminisi[19]等人提出一种基于样本块的修复方法。该修复方法同时考虑了图像的结构和纹理信息，以等照度线法线方向，待修复区域边界像素点的优先级，采用SSD来搜索最优匹配块的方法。其修复过程主要包括三个部分：计算、搜索、合成。计算是确定边界像素点的优先级，目的是为了确定边界像素点的修复顺序，搜索就是根据纹理的相似性在未受损区域内寻找纹理最匹配的块，合成过程就是将搜索步骤寻找到的最优匹配块中的信息拷贝到待修复模块中的未知部分，同时更新这些未知部分的优先权和置信度等信息。Criminisi算法是典型的贪心算法，每个搜索过程中都寻找最匹配的模板，这样将每个过程的最优作为全局最优解。由于其合成是以块而非像素点为单位，所以与PDE模型相比，其速度得到大幅度提高。Criminisi在论文中给出的修复效果说明，该算法不仅对破损区域较小时有效，对破损区域较大时修复效果同样很显著，其运行时间和其它算法相比也得到很大提高，成为图像修复领域里的经典算法，因此受到国内外学者的广泛关注。

随后，在此基础上，Wu等人[20]修改了优先权的计算方法，不再沿着等照度线方向，而是与它垂直的方向，这种改进能更高的保存图像的结构信息，所以修复效果得到一定提高；Nie等人[21]在基于相似度的图像修复算法上对Criminisi算法的优先权的计算进行改进，对构成优先权的置信度和数据项进行归一化，保证两者对优先权具有相同程度的影响力，同时该算法引进了距离项，避免修复过程中多次选取相同的图像块进行填充从而造成视觉上的人工痕迹。

与Criminisi采用的贪心算法相比，微软亚洲研究院的Sun等人[22]出了一种基于结构传播的图像修复算法，该算法通过人工标注图像受损区域中重要的结构信息，采用基于贝叶斯信任传播算法，根据能量最小化机制，沿着用户标注信息首先修复其结构部分，故在修复过程中能很好的保持待修复区域的结构部分，然后再采用纹理合成修复剩余部分，是一种全局最优算法。但根本限制是需要手工绘出缺失部分的结构信息。

Komodakis等人[22]提出的基于优先权的BP传播算法，其将图像修复问题描述成离散全局最优问题，其目标函数即求马尔科夫随机场（MRF）的能量最小化函数。其基本思想即是将图像修复问题当成一个七巧板问题，每一块的修复过程不仅考虑自身的相似性，同时需要考虑与邻居的契合程度，以达到一个全局最优，即能量最小化状态，所以在修复过程中，会不断进行回朔，与邻居交换匹配块的信息，以保证能达到全局最优。与传统BP算法相比，他们提出了基于优先权的消息调度机制和动态标签削减机制，以避免传统BP算法不可忍受的计算量，大大提高了计算效率和计算复杂度，但尽管如此，该算法的时间复杂度仍是很高。

随着相机、电影等图像技术的飞速发展，使得图像与人们的生活变得密不可分，图像修复也成为一个重要课题，是图像处理的重要组成部分，图像修复简而言之就是利用图像中的已知信息，修补图像中丢失信息，从而得到完整图像的过程。因为其解的不确定性和病态性，吸引了越来越多的学者投入更多的精力不断进行研究。

1.3本论文的结构安排

本文简要的讲述了图像修复的背景和目前流行的两大类的图像修复算法，即基于PDE模型的算法，包括BSCB、TV、CDD三个模型，该类算法主要应用于修复破损区域较小的情况；而纹理合成算法则应用于破损区域较大的修复情况，是目前图像修复中较热门的研究方向。本文的主要章节安排如下：

第一章对目前图像修复领域的发展进行了简单讲解，包括其研究背景和图像修复领域两大类修复算法的优缺点。

第二章简述了图像的基础知识，并详细阐述了基于偏微分方程的三种修复模型：BSCB、TV、CDD，和基于纹理修复的两种经典算法：非参数采样的纹理合成和基于块的纹理合成。

第三章详细分析了Criminisi算法的优缺点，然后针对这些缺陷，提出了自己的改进方式。

第四章给出本文针对Criminisi算法进行改进后的仿真实验结果，并和其它算法进行了对比，证明改进的合理性。

第五章对本文研究工作进行总结并提出了一些需要继续深入研究的问题。

第二章数字图像修复

第二章数字图像修复

上一章简要介绍了图像修复的起源，以及对其发展现状做了简要描述。本章将首先对图像的基本知识、图像修复问题以及图像修复问题的三个基本原则进行简单介绍，然后详细讲述当前流行的几种图像修复算法即数学模型，为下一章的改进算法做好准备。

2.1图像的基础知识

本小节将介绍图像修复中要使用到的一些图像基本知识，包括颜色直方图[25]、灰度图等。

对于一副彩色图像而言，知道对于每个像素点，其常用的表示方式是通过R、G、B三个颜色通道来表示，每个颜色通道的取值在0到255之间，因而一个像素点的值能达到1600多万。将彩色图像转换成灰度图像的过程称为灰度化处理，灰度图像是每个像素点只有一个颜色采样的图像，所以其取值范围只能在0到255之间，是R、G、B三个分量都相同的一种特殊彩色图像。灰度图像与彩色图像一样，同样能反映图片中局部和整体的结构、纹理、亮度等图像信息，同时与彩色图像相比，计算量大幅缩小。

颜色直方图是在许多图像检索系统中被广泛采用的颜色特征。颜色特征应用最为广泛，是人类识别图像的主要感知特征，也是人对图像的第一印象。与其他的视觉特征相比，颜色特征对一副图片的缩放、旋转、视觉角度的依赖较小，所以颜色特征是最显著、最可靠、也最稳定的视觉特征，从而具有较高的鲁棒性。

颜色直方图反映的是图像中颜色的组成分布，即出现了哪些颜色以及各种颜色出现的概率，Swain和Ballard最先提出了使用颜色直方图作为图像颜色特征的表示方法。直方图具有旋转不变性和缩放不变性，即说明在旋转和缩放过程中没有信息的丢失和增加。而且直方图对视觉角度的变化，其变化很小，所以一个三维物体可以通过很少数量的直方图来展示。如图2-2所示，三张图片的直方图在细节上出现了少许的差异，但在总体形态和能量分布上是十分相似的。

有了图像的颜色直方图，我们根据直方图的不变性，可以通过直方图的相似性来判断两幅图片的相似程度，这为寻找相似图片提供了有效的手段。而有多种方法来度量两个图片颜色直方图间的相似性，包括直方图相交法，直方图匹配法，直方图间的矢量距离等。

图2-2直方图的旋转不变性和缩放不变性

2.2图像修复问题及修复原则

2.2.1图像修复问题描述

一般的，图像处理的基本模型可以表示成输入输出模型，如图2-3所示。

图2-3图像处理基本模型

其中，输入是待处理的图像，为线性或非线性的图像处理器，如去噪，放大，压缩，修复等，为处理结果。

图像修复是利用图像中的已知信息，修补图像中丢失信息，从而得到完整图像的过程。设表示完整的矩形图像，为受损或者丢失区域，为图像已知即未受损区域，为缺失区域边界，如图2-4所示。

图2-4图像修复问题

一般情况下，图像修复分为两个步骤，第一：确定待修复区域，这可通过人工或计算机决定；第二：利用(即)内的已知信息，通过各种修复算法来填充未知区域，从而得到一副完整看似未受损的图像。图像修复一般有以下两个特点：

图像修复是一个病态问题。因为没有充分足够的信息来保证修复结果的惟

一性，任何数据的微小变动都会造成问题解的不确定性。而且，一副图像中可能包含丰富的纹理结构等信息，这些信息不符合任何分布，所以很难找到一个通用算法，能同时兼顾图像的纹理和结构，针对不同的角度，不同的算法能达到不同的效果。同时，图像修复解的合理性是按照人类视觉来刻画，遵从人类视觉和心理，所以图像修复是将图像信息和视觉信息等结合起来得到的解。

当缺失区域是一整块时，那么对图像缺失区域的信息时完全未知的，因此

只能在人类视觉的判断下，通过已知区域的信息来猜测缺失区域的信息，这即是视觉研究中的“最佳猜测”。最佳猜测原理[26]指出，人类视觉系统感觉到的就是对世界信息形态的最佳猜测。根据最佳猜测原理，图像修复的问题可以转化为求贝叶斯最大后验概率的问题[27]。在贝叶斯概率公式下，使得图像修复结果与完整图像最为相似，即相似概率最大。根据贝叶斯公式，则：

(2-1)

其中，是修复后的结果，为待处理图像，为图像中的缺失区域，越大，那么修复结果与原图则越相似。

2.2.2图像修复原则

通过上面对图像修复问题的简要描述可以知道，在修复过程中，缺少明显的信息来确定待修复区域里应该填充什么东西。图像修复过程是一个非常主观的过程，从不同的角度考虑，得到的解也不相同，所以目前缺少一个统一的算法，能保证修复结果。Bertalmio等人在咨询专业的文物管理员后，提出了以下四个基本原则来指导修复过程：

图像的整体决定了如何修复缺失区域，修复的目的就是为了保证图像整体的一致性；

待修复区域周围的结构信息通过信息传播延伸到待修复区域内部，这样就能修复断裂物体的边界曲线；

在待修复区域内部，对于不同的位置，其颜色和结构应该与相应周围的颜色信息相匹配

同时还必须考虑微小的细节，需要将纹理考虑进去

上述四个基本原则，第（1）条原则很难实现。因为图像修复本身就是一个病态性问题，缺少足够的信息来确定解的唯一性，其解的合理性是通过视觉来判断的，与人类的视觉心理紧密联系。而第（4）条原则，对于基于PDE方程的修复方式，根据PDE的信息扩散原理，也很难满足这条原则。第一个基于偏微分方程的修复模型BSCB便是通过不断对第（2）条和第（3）条原则进行迭代，达到收敛时即完成修复过程。

Chen等人在2002年针对非纹理图像首次提出了局部修复的概念。局部修复意味着修复模型不再依赖于图像的全局特征或模式识别，而仅仅依赖于待修复区域周围的信息，并从人类视觉的观点考虑了局部性对修复模型的影响，从而提出了以下三个修复原则:

修复模型应该是局部的。因为模型限制了不能考虑全局信息，因而待修复区域的内容完全由它周边的已知信息来决定；

修复模型应该能够修复狭窄的光滑的受损边缘。模型必须考虑边缘修复，因为边缘对物体的识别和图像分割至关重要，这只限制于狭窄边缘，对于受损区域较大的边缘情况，模型通常而言是无法修复的；

修复模型必须对噪声具有较强的鲁棒性。根据人类视觉而言，从含有噪声的数据中提取干净的特征并将它们扩展到待修复区域是很容易的。

通过以上的修复原则，可以知道，图像修复本身就是一个病态问题，不存在一个通用的模型能够处理所有的受损图片。

2.3基于偏微分方程的图像修复

偏微分方程（PDE）进入图像处理[28][29]领域是从上世纪70年代开始，起源于Koenderink和Witkin各自独立的研究，其主要思想是利用物理学中的热扩散方程，将待修复区域周围的信息向待修复区域传播。PDE为图像处理问题提供了统一的理论框架，几乎涉及所有图像处理领域，PDE最早用于图像处理领域中的图像分割和图像增强，在2000年，Bertalmio等人率先把PDE引入图像修复领域，并取得很好的效果，开辟了图像修复领域的一个新天地，引起众多学者的兴趣和对其的深入研究。其中，较为经典的PDE模型有BSCB模型，TV模型和CDD模型。

2.3.1BSCB模型及原理

BSCB模型是Bertalmio，Sapiro，Caselles和Ballester[1]提出，他们第一次把PDE模型引入图像修复领域并取得巨大成功。Bertalmio等首先咨询博物馆的管理员如何手工进行图像修复，然后将其用数学和算法表达出来，并采用迭代的方法，所以其实质就是模拟手工进行修复的过程。该算法一旦选定待修复区域后就不需要任何人工交互，适用于修复图像中的结构部分。令离散二维灰度图为受损图像，且，因为采用的是不断迭代的过程，所以在修复过程中，会产生一系列的中间图像集合，初始时，有，并且有：

(2-2)

其中，是最终的修复结果。因此，BSCB模型的迭代方程式如下：

(2-3)

其中，是迭代次数，是像素点的坐标，为迭代速率，表示每次迭代的更新值，是待修复区域。越大，表示迭代次数越多，最后得到的结果也就更精确，算法运行时间也就越长。当越大增大到一定数量时，算法收敛，即

，到达此时，算法结束。

在修复过程中，需要将待修复区域边界上中断的线条给连续起来，换句话说，该算法需要将带修复区域周围已知的信息平滑的传进待修复区域内部。令是需要传播的信息，是信息传播的方向，因此有：

(2-4)

其中，是的变化率。当足够大时，迭代达到稳定状态，即，根据公式2-3和2-4，可知：，这表示信息已经沿着方向传播进待修复区域了。

因为希望扩散过程尽可能的平滑，所以在文中被刻画成图像的平滑度，并以拉普拉斯算子实现，即：。为了计算沿方向的变化率，就必须首先确定信息的传播方向，即的值，作者选择的是沿着等照度线的方向。等照度线是一条灰度值相等的曲线，即颜色变化最小的曲线。令在点处的离散梯度是，梯度反应的是在该点色彩空间（灰度图即是灰度值）变化最大的方向，那么将该梯度方向旋转90°，得到，即色彩空间变化最小的方向，也就是等照度线的方向，故有等式：

(2-5)

为了保证方向场的正确变化，信息的扩散过程与图像的修复过程是交叉的，也就是说，先执行A步图像修复，然后执行B步信息扩散，文中A、B的取值分别是15和2，信息扩散是为了避免曲线的相互交叉。为了达到平滑扩散的目的，同时避免修复过程中损失清晰度，采用了各向异性扩散，其扩散方程式为：

(2-6)

其中，是以为半径的球形邻域，是图像的等照度线的欧几里得曲率。为上的平滑函数，并且满足：在上，，在里，。

在修复开始之前，需要进行预处理，即整个图像需要先进行一次各向异性的平滑扩散，目的是为了将噪声对图像等照度线方向计算的影响减小到最小。然后算法进入修复循环，每迭代几次，就会进行一次各向异性扩散，直到算法趋于稳定状态。上面已经提及算法的迭代方程：，其中：

(2-7)

(2-8)

(2-9)

(2-10)

(2-11)

公式(2-9)是图像的平滑度，公式(2-10)是等照度线的方向归一化后的向量，式子(2-11)的变化率在等照度线方向上的投影。其修复效果如图2-5所示：

（a）受损图像（b）BSCB模型修复效果

图2-5BSCB模型去除文字修复效果图[1]

2.3.2TV模型及原理

Chan等[2]基于变分原理建立了一种比较通用的数字图像修复模型，即全变分（TV）模型。

令是待修复区域，且具有分段光滑的边界，是待修复区域周边的一个闭集，并且假设在区域中受到均匀白噪声污染。如图2-6所示：

图2-6TV模型修复示意图[2]

定义能量函数为：

(2-12)

边界约束条件为：

(2-13)

其中，为原始图像信息，函数为输入非负时，输出也非负的实函数，为白噪声的标准差。公式2-12满足修复修复的局部性(local)原则，即只在待修复区域周围寻找已知有用信息，公式2-13满足对噪声的鲁棒性原则。然而为了满足修复细长的受损边缘，必须选择一个合适的函数，并且使得代价函数有限，即：

(2-14)

而函数可以展开成：

(2-15)

当时，公式2-14就是图像修复领域中经典的TV模型。但变分法的实践证明，无约束的TV问题更容易解决，所以将原能量函数转化成以下新能量函数：

(2-16)

其中，是拉格朗日乘子。的欧拉朗格朗日方程为：

(2-17)

其中，当时，，当时，。用最速下降法求解，可得：

(2-18)

通过公式2-18，TV模型完成了受损区域的修复。其数字实现简要介绍如下，令表示目标像素点，、、、表示目标像素点的四个邻域，、、、表示相应的中间位置的像素点，如图2-7所示：

图2-7目标像素点和其邻居

令，,则通过中心差分可将散度进行离散化，即

(2-19)

其中，为步长，这里取值为1。下面分别对、、、进行求值，以为例子，计算方式如下：

(2-20)

(2-21)

将公式2-19、2-20、2-21带入公式2-17可得：

(2-22)

令，，。公式2-22变为：

(2-23)

并且满足条件：。通过Gauss-Jacobi迭代算法得：

(2-24)

对于待修复区域内的每个像素点，都可以用公式2-24进行迭代求解。最后，若图像未被噪声污染，则就为的边界，否则只需要从向外扩几个像素点即可。其修复效果如图2-8所示

（a）受损图像（b）TV模型修复效果

图2-8TV模型去除文字效果图[2]

2.3.3CDD模型及原理

上一小节讲述了TV模型及其修复原理，在修复例如污点或者刮痕时，TV模型能有较好的效果。然而TV模型有个很致命的缺陷，即不满足人类视觉连续性原则，因为TV模型为使能量函数最小化，总是倾向于用最短的直线来连接断裂的线性结构物体。如图2-9所示：

(a)(b)(c)

图2-9人类视觉连接性原则[17]

(a)受损图像，其中(b)符合人类视觉连接原则的修复结果(c)TV修复结果

为了克服TV模型的这个缺点，Chan和Shen在TV模型的基础上提出了新修复模型，新模型在信息扩散时不仅考虑图像的梯度，还考虑了等照度线的几何信息，引进了曲率这一参数，所以称之为曲率驱动扩散模型（CDD）[3]。

在CDD模型中，扩散强度被定义为：

(2-25)

其中，一个像素点的曲率被定义成穿过等照度线的标量曲率，而对于平面曲线，它的几何信息就被描述成标量曲率。其几何表达式为：

(2-26)

函数的作用是抑制大的曲率，激励小的曲率，故有：

(2-27)

该函数对于曲率值较大的地方，扩散强度也大，而曲率较小的地方，扩散则逐渐消失。所以对于图2-9中的图(c)，TV模型在此时达到稳定状态，将停止迭代，完成修复。而对于CDD模型，在a，b，c，d四点处的曲率为无穷大，所以处于不稳定状态，还会继续进行信息扩散，从而避免了TV模型的不连续缺陷。

在文中作者对时，，其中。所以，CDD修复模型为：

(2-28)

其中，为待修复区域，而为周围的已知信息。然而对于大多数情况，中包含的信息都被噪声污染，而公式2-28描述的CDD模型对噪声什么敏感，所以在修复时往往需要对图像进行去噪。所以CDD模型分为两个部分：在已知区域的去噪部分和在受损区域的修复部分，其去噪模型与TV模型相同，即

(2-29)

这两个部分可以简单的通过以下公式连接起来，并且两个部分的转换发生在待修复区域的边界上。

(2-30)

其中，扩散强度和拉格朗日乘子都有阶段取值：

(2-31)

在不考虑噪声的情况下，令，那么公式2-28化为：

(2-32)

其迭代方程为：

(2-33)

其中，是迭代的时间步长，是迭代次数，。

CDD模型是三阶偏微分方程，并且呈发散形式。在一副给定的图像中，采用半点中心差分法来求解扩散系数，如图2-9。也就是说，对于一个像素点，比如其坐标为（0,0），假设，其扩散系数为：

(2-34)

要得到公式2-33的值，还需要知道以下系数的半点值：

以为例子，如图2-10所示：

图2-10：CDD模型的数字实现

那么，的取值为：

(2-35)

而对于上式中新的半点值，其值可以通过计算和的平均值求得。

公式2-26讲解了曲率的计算方式，该公式还可以进一步化成：

(2-36)

同样的，可以采用中心差分法来求解在半点处的曲率值，例如在点处，有：

(2-37)

对于公式2-36中引入的新项：，可以简单的通过中心差分来求解。通过这样的方式，在半点处的曲率就可以用图像的像素点的值来表示了。

因为CDD模型在数字实现过程中，只采用了中心差分方法，所以即使对图像进行旋转，也能保持结果不变。随着时间步的增长，原始受损图像中的受损部分逐渐达到稳定收敛，并形成最终修复结果。其修复效果如图2-11所示：

（a）受损图像（b）CDD模型修复效果

图2-11：CDD模型修复效果图[3]

不论是BSCB模型，还是TV模型或者CDD模型，三者都是基于偏微分方程（PDE）进行建模求解的。由于偏微分算法本身的信息扩散机制，导致它们对于缺失区域较小的受损图像，比如划痕，污点等，会有较好的效果；而对于受损区域面积较大时，不仅运算量剧增，而且会造成过度修复，使修复结果出现模糊。

2.4基于纹理合成的图像修复

有些图像在局部区域内呈现不规则性，而在整体上表现出某种规律性，习惯上，把这种局部不规则而宏观上有规律的特性称之为纹理。纹理是图像中除结构外另一重要信息，它反映了图像的整体视觉特性。由于纹理合成[30-33]技术能很好的参照图像的纹理，从宏观角度考虑受损区域的修复过程，因而不会出现PDE模型那样的模糊效应，纹理合成技术主要基于纹理合成的图像修复算法，根据每次修复区域的大小，可以分成基于单个像素点的纹理合成和基于块的纹理合成，其代表有A.Efros等人[17]提出的非参数采样纹理合成和Criminisi等人[19]提出的基于块的纹理合成，下面详细介绍着两种方法。

2.4.1非参数采样纹理合成

非参数采样的纹理合成技术是由A.Efros、K.Leung于1999年提出[17]方法的主要思想是，以单个像素点为单位，这样就能尽可能的捕获图像中的高频信息，并且将纹理合成建模成马尔科夫随机场(MRF)，并假设一个像素点亮度值的概率分布只与其邻居有关，与图像中其它像素点无关。邻居被塑模成以待修复像素点为中心的一个矩形框，矩形的大小由用户自己指定。更具体的是，位于图像中的空间高频部分，纹理合成更加规则化，位于空间低频部分，纹理合成则更加随机化。基于上述假设，逐渐合成每个像素点，如图2-12所示。在图2-12中，a为纹理样本图，b为待修复图，b图矩形框中央的像素点为待修复像素点。算法首先在a图中寻找与b图矩形框最为相似的区域，然后将其中心点的颜色值拷贝到b图。下面详细描述整个算法的细节流程。

(a)纹理样本图(b)待修复图

图2-12非参数采样纹理合成算法示意图[17]

首先是该算法的一些变量定义，是待修复的图像，是可供采样的样本纹理块，是待修复的像素点，即未知区域的像素点，是以为中心的矩形区域，即窗口，是两个窗口和的感知距离。为了修复像素点,需要首先构建出条件概率分布的近似值，然后从进行采样。因为是基于马尔科夫随机场模型，因此论文假设像素点的值只和其邻居有关，而与邻居之外(即)的像素点无关。为了确定的值，文中定义了一个候选集合，的值将从候选集合中选取：

(2-38)

然而实际上，在有限的里，很难有匹配块能严格满足，故采用另一启发式方法，即：，将严格满足改为近似满足，选取个能满足下式的邻居即可：

(2-39)

然后是关于的定义。最常用的方式是计算像素点颜色差值的平方和，即SSD(sumofsquareddifferences)。然而A.Efros等指出这种方式对于任何错误匹配的像素点，不论是靠近矩形框中心或者是窗口的边缘都具有相同的权重是不合适的，因此，A.Efros等为了尽可能的保护纹理的局部结构信息，所以在SSD的基础上引入了一个二维的高斯核心，已达到对于错误匹配的像素点，距离越远其权重越低，距离越近其权重越高，公式如下：

(2-40)

其中是二维高斯核。

整个过程通过不断的对单个像素点进行纹理合成，最终修复整个缺失区域。该算法与以前的方法相比，能很好的照顾图片的纹理信息，修复质量得到很大的提高，但是，由于以像素点为单位，因而计算复杂度颇高。其修复效果如图2-13所示：

图2-13非参数采样纹理合成效果图[17]

图2-13为对于给定的一块样本纹理（左边的小图），对于不同的矩形区域的大小，其合成的效果图。从左到右，使用的矩形区域大小依次为：5，11，15，23。从其合成效果来看，知道矩形区域的大小对纹理的合成效果有很大影响。

2.4.2基于块的纹理合成

与前面介绍的基于非参数采样的纹理合成相比，Criminisi等在2003年提出的基于块的纹理修复在两方面进行了改进，第一是修复顺序，A.Efros等人的修复顺序类似于“剥洋葱”，即从最外面一层一层往里修复，而Criminisi则提出了优先权的概念，认为待修复区域边界上的像素点其优先值比待修复区域内部的像素点更高，因此Criminisi算法能更好的修复物体的边界，而A.Efros算法则往往造成不连续的结果。第二是每次修复的大小，A.Efros算法每次只修复一个像素点，这也导致其计算复杂度比其他算法都高，而Criminisi算法每次则修复一个块，所以相对而言，算法速度得到很大提升。因为修复效果好，计算复杂度低而成为图像修复领域的经典算法。下面将详细介绍Criminisi算法过程。

变量的定义

在介绍具体算法之前，先介绍算法中需要到的一些变量。表示源图像，即需要修复的图像，为图像中的已知区域，即未受损区域，为图像中的受损区域，为已知区域与受损区域的边界，为目前优先权最高的像素点，为以点为中心而确定的矩形块，为点的等照度线方向，为与边界正交的单位向量，如图2-14所示：

图2-14：Criminisi算法变量示意图

算法流程步骤

本质上，Criminisi算法属于贪心算法，因为以每次匹配时最优作为全局最优。算法的基本流程如图2-15所示：

图2-15：Criminisi算法流程图

在图2-15中，当边界为空时，表示修复完成，再没有区域需要进行修复，算法结束。下面详细讲解每个步骤的细节。

步骤1、2：确定待修复区域和边界。这可以通过人工标注或者计算机提取，在下一章将会介绍一中自动提取前景的方法。这一步确定哪些区域需要进行修复，或者哪些物体需要去除，标记出其边界信息，若边界为空，则退出。

步骤3：计算边界上所有像素点的优先权。

对于非参数的纹理合成，其合成顺序至关重要，不同的顺序会导致不同的修复结果。Criminisi在文中提出优先权的概念，纹理合成顺序是按照优先权的大小进行，而不再是像A.Efros那样“剥洋葱”一层一层从外往内修复，所以优先权的计算方式也关系算修复结果的优劣。对于边界上的任意一点，以该点为中心，确定一个矩形块，点的优先权计算方式如下：

(2-41)

其中，的定义如下:

(2-42)

是矩形块内像素点的个数，也即是块的大小。在初始化阶段，的取值如下：对于内的任何像素点，即待修复区域内部的像素点，，而对于内的任何像素点，。对于边界上的像素点则采用公式2-39来计算。置信度可以认为是度量点周围可靠信息的数量，刚开始时，待修复区域边界上的像素点其置信度最高，里面的较低。若仅仅考虑置信度，那么随着算法的运行，因为边界上的像素点，其置信度较高，所以会先修复，而待修复区域中心部分则会后修复。这就会和上一节讲述的A.Efros、K.Leung算法一样，也是按照“剥洋葱”的方式，一圈一圈的从外往内修复，这不利于图片中具有线性结构的物体，所以Criminisi等又引进了数据项，充分考虑了物体的结构信息，从而避免了与A.Efros等的修复方式。

为数据项，其公式定义如下：

(2-43)

其中，为归一化因子，例如，对于灰度图来说，的值为255。是在点与边界曲线正交的单位向量。表示在点的梯度向量，即颜色变化最大的方向。表示向量旋转90度，所以是在点的等照度线方向，如图2-14所示。

等照度线即为灰度值相同的一条曲线，故该曲线方向的颜色变化值最小。

论文指出，数据项是关于边界上等照度线强度的函数，它能促进修复按照等照度线方向从外向里修复，这是非常重要的，尤其是对于具有线性结构的物体，能够保证首先被修复，这样就保证了物体的连通性原则。

对于置信度和数据项，它们之间应保持微妙的平衡。数据项能保证沿着等照度线快速向内修复，因为在这个方向上，带修复区域的数据项取值更大，然而置信度则在越靠近待修复区域中心时，其值越低，从而导致优先权也相应减小。所以在沿着等照度线从外往内修复时，置信度项会起到一定的抑制作用，从而保证图像的纹理整体的连续性。

步骤4、5：以优先权最大的像素点为中心形成待修复模块，并在图像已知区域内寻找最匹配的模块。

对于任意两个模块，都有一个感知距离定义，这个距离用来描述两个模块间的相似程度。距离定义如下：

(2-44)

简而言之，即两个模块内对应像素点差的平方和，此即SSD(sumofsquareddifferences)的定义。因此，若目前优先权最大的像素点为，以它为中心形成待修复模块，找与其最相似的模块，即是与其距离最小的模块，即：

(2-45)

在该算法中，感知距离的计算采用的是Lab颜色空间，而不是常用的RGB，因为其具有属性的感知一致性。对于颜色空间，在本章第一节已经讲述过了。

步骤6：复制复中相应的像素点到中。

通过上一步骤，就可以找出最佳匹配的模块。然后把中的像素点复制到中的未知部分，已知部分不做任何修改。以此通过不断在已知区域中进行采样然后复制到缺损区域来达到纹理合成的目的。

步骤7：更新模块中像素点的自信度和边界等信息。

这是该算法单个修复过程中的最后一步。每修复一个模块，那么该模块原来未知的像素点现在变成已知，根据置信度的定义，知道该模块内像素点的置信度也会发生变化，边界同样会发生变化，置信度的更新方式如下：

(2-46)

随着修复进行，置信度将会衰减，这说明对于靠近待修复区域中心的像素点的值更加不能确定。通过对置信度的更新，可以重新计算该模块内像素点的优先权，以此来决定下一阶段的修复顺序。图2-16显示了修复一个模块的示意图：

图2-16：合成一块纹理过程

（a是待修复原图，b中待修复模块，c寻找最优匹配模块，d复制最优模块到未知模块）

Criminisi算法实现细节

1）模块大小的选择

模块大小的选择与图像修复的质量和速度都有很大关联。模块较大时，则只需要少数几次修复过程就能完成未知区域的修复，然而却会造成边界纹理出现明显的过渡痕迹。模块较小时，更容易保持纹理的整体一致性，但是容易出现块间效应，且计算复杂度会提高。以往传统的基于纹理合成算法，模块大小的选择都是通过多次实验，然后对结果不断调整，选择能达到最优修复效果的大小。然而这样的选择方式却缺乏自适应性，需要人工干预较多，而且对于不同的纹理图片，最佳模块的大小也往往并不相同。而Criminisi等也是根据实验结果和经验，只是简单的把模块大小固定为9*9，这也是该算法中的一个不合理的地方。

2）优先权的计算细节

优先权由置信度和数据项构成。数据项中的计算可采取不同的方式，在文中是等照度线的方向，也就是当前模块内梯度最大的已知像素点，其梯度的法线方向。而对于梯度的计算，有前向差分、后向差分、中心差分等计算方法。这三种方法在讲述基于偏微分方程的图像修复模型时已经提及，根据三种差分定义，可知在模块边界，只能采用前向或后向差分，而模块内部，采用的是中心差分。下面简要介绍下中心差分的计算公式：

||是梯度求模算子。上式即找出梯度最大值点的横坐标和纵坐标。

为与边界在点的正交方向，可理解为边界切线的法线法向，而切线方向为：

又，所以为：

Criminisi算法实验结果

Criminisi等在其论文中给出了丰富的实验结果，本文也对Criminisi算法进行模拟实现。下面例举出数个Criminisi论文中的修复实例，并与其他算法进行对比。图2-17为去除图片中文字的效果图，从结果可以看出，Criminisi算法对于破损尺度较小的待修复区域，其修复效果也很好。图2-18为从原图中去除较大块的物体。

（a）待修复图（b）出去字母后的修复效果

图2-17：Criminisi算法去除文字效果图

（a）原图（b）掩码（c）修复结果

图2-18：Criminisi算法去除人物效果图

（a）原始图像（b）受损区域

（c）其他算法修复结果（d）Criminisi算法修复结果

图2-19：Criminisi算法与其他算法对比效果图

从实验结果来看，无论对于受损区域较小时，比如字母、污点等，如图2-17，或者受损区域很大，比如去除多余目标，如图2-18，Criminisi算法均能取得较好的效果，并且图2-19中对修复结果的对比可以看出Criminisi算法的优越性。但从图2-18中最后的修复结果来看，屋顶并没有得到很好的处理，结构出现不连续，并且河流中也出现多余的树，因此表明Criminisi算法还是有待改进的。

2.5本章小结

本章首先提出了什么是图像修复，指出图像修复的病态性，以及图像修复领域的四个基本原则。然后主要讲解了两大类的图像修复算法和模型：基于偏微分方程的修复模型和基于纹理合成的算法。第一节对图像修复问题进行了简要的描述，了解什么是图像修复及图像修复的一般过程。第二节详细介绍了三种基于偏微分方程(PDE)的修复算法，分别是BSCB模型，TV模型和CDD模型。简要分析了三种模型的优缺点，对其进行了公式推导。第三节介绍了基于纹理合成的图像修复算法，包括A.Efros等提出的非参数采样的纹理合成和Criminisi等基于样本快的纹理合成。A.Efros算法将图像修复塑模成马尔科夫随机场模型(MRF)，采取“剥洋葱”似的修复方式，不断从外层往里扩散，取得了很好的效果。但由于该算法是以单个像素点为单位，所以计算复杂度很高，而且“剥洋葱”似的修复方式不利于保持物体的结构信息，会出现断裂的现象。而Criminisi算法则在纹理合成的基础上，采用了优先权的概念，并且不再以像素点而是以块为修复单位，避免了A.Efros算法的缺点，不但能保持图片的纹理信息，也能较好的保持图片的结构信息，时间复杂度也有很大提高。但最后的实验结果指出，Criminisi算法中还是有很多不足的地方，可以对这些缺陷进行该界，也为下一章做好了铺垫。

第四章实验结果及性能分析

第三章基于纹理合成的改进算法

上一章介绍了基于纹理合成的两种算法，并且详细讲述了Criminisi算法的流程和细节，并给出实验效果图。实验说明，Criminisi不论是修复划痕、污点等狭长的区域，还是去除多余物体等较大区域，都能取得较好的效果，但是也存在一些不足。这一章将介绍Criminisi算法的一些缺陷，然后针对这些缺陷提出自己的改进算法。

3.1Criminisi算法的缺点

Criminisi算法属于贪心算法的范畴，虽然Criminisi等在论文中给出的实验效果比其他算法不论从速度还是修复效果都有很大提升，充分考虑了图像本身的梯度和结构等信息，属于图像修复领域中的里程碑，但也存在很多值得改进的地方。

首先，在修复过程中，不论对于纹理较丰富还是纹理单一的区域，Criminisi算法都采用固定模块大小，这是不合理的。对于纹理单一的区域，图像信息的变化较平缓且信息很有规律可循，此时模块的大小可以适度增大，这可以有效减少算法的运行时间，加快修复速度；然而对于纹理较丰富的区域，其信息变化较大，若此时模块较大，则单个模块内包含的纹理信息较多，这样极易造成前后两个匹配块在边界上的不协调，出现明显过渡痕迹，也就是块间效应，但若选择的匹配块太小，又会造成算法运行时间的显著增加。后续章节会提出一个自适应的模板大小的计算方法，以此来避免上述情况。

同时，Criminisi算法中，优先权的计算方式是：。表示的是以为中心的待修复块的置信度，它越大，说明该块中的已知信息越多，表示和边界相交的等照度线的强度。若和均很大时，那优先权自然很高，这并没有任何问题，然而，在修复过程中，有可能会出现和呈两个极端（即一大一小）的情况，这个时候若还是以原来的计算方式，即只是采用简单的乘法计算，这样得到的优先权就会极小，其修复顺序就靠后，这实际情况不符合。同时，文中对的更新方式是直接复制，但若是匹配过程中出现误差，则会造成误差累积，并不断蔓延，最终会严重影响修复效果。

Criminisi算法在搜索匹配块的过程中，采用全局搜索方式。但全局搜索过程不仅十分耗时，而且并没有考虑到图像的局部自相似性，实际上，待修复区域周围的结构纹理信息很大程度上决定了最终的修复结果，同时，在寻找最佳匹配模块时，只考虑了匹配块的颜色信息，采用SSD（sumofsquareddifferences）来计算两个模块间的相似性，对纹理部分比较简单时没有什么问题，但对于纹理较丰富的区域，极易出现错误匹配，而且SSD值并不能完全反应模块中颜色的变化情况，因此该算法存在错误匹配的情况。

3.2样本块大小自适应算法

在基于纹理合成的图像修复算法中，块的大小对最终的修复结果会产生很大的影响，同时还能影响算法的运行速度。在众多的纹理合成算法中，块的大小一般都是固定的选择为7*7或者9*9，然而这并不合理，不能适应具体情况，对于不同的纹理图像，不同的块大小能有不同的修复效果。

对于Criminisi算法而言，该算法是以串行方式运行，不断的将前一个模块匹配修复后的结果作为后续的输入，若上一次匹配就出现错误，那就会错误的指导后续匹配过程的进行，后面得到的结果自然也不正确，所以匹配正确度十分重要，而模块的大小对匹配的正确度有很大影响。从算法运行速度的角度考虑，那么模块当然较大时更好，这样只需要经过较少几次的修复过程就能修复整个待修复区域，算法即可结束，但模块较大时，单个模块包含的信息则较多，容易造成错误匹配，并且由于串行方式会令误差逐渐累积，从而影响最终结果；而且块与块之间容易出现裂缝和不连贯的情形。若从修复效果考虑，那么模块则较小时比较好，这样单个模块包含的信息较少，不易造成错误匹配，合成的纹理块边界过渡会比较光滑，但算法运行时间显著上升，并且容易造成块间效应，不能很好的反应纹理的全局特性。

Criminisi等经过多次修复试验，经过折衷，选择令最终修复效果相对较好的固定模块大小9*9，然而不同的图片包含不同的纹理和结构信息，其模块的大小自然应该不一样，这也是Criminisi算法的一个重要不足。不同模块大小的修复效果如图3-1所示。

从图3-1的修复结果中可以看出，对于不同的模板大小，其修复效果也并不相同。当模板大小是7*7时，屋顶出现错误匹配，将一部分树叶匹配到屋顶上去，同时河边的树也不断的往河里延伸，造成一种不真实的感觉。模板大小是9*9时，修复结果更符合人类视觉特征，河边的树并没有往河里延伸，屋顶的修复却出现缺口，但还是出现了缺口。模板大小11*11时，其修复结果与模板大小为7*7的修复结果相差无几，但屋顶的修复效果却是上述效果图中最为合理。模板大小为13*13时，因为模板较大，包含的信息更加丰富，极易出现错误匹配，该修复结果也说明了一点，在树林中修补出屋顶的一部分，显得分外突兀，不符合人类视觉标准。

(a)原始图像(b)掩码图像(c)7*7修复效果

(d)9*9修复效果(e)11*11修复效果(f)13*13修复效果

图3-1：Criminisi算法不同模板大小的修复结果

针对Criminisi算法固定模板大小的缺点，本文提出了自适应模板大小的方法。即使在同一副图像内，不同模块间达到最佳修复效果的模块大小也不尽相同。前面已经提及，当在纹理较丰富的区域，图像的信息变化比较快，此时若模板较大，则更容易出现误差。所以，在纹理发生变化时，模板大小不能再继续增加。本文采用的自适应模板大小，其中心思想采用的还是对信息从内往外进行扩散，从初始的模板大小开始（本文采用的是5*5），然后向外扩展一个像素点，并计算扩展前后，模板内信息的变化是平缓还是具有跳跃性，若信息变化较平滑，则继续向外扩展一个像素点，否则，退回到上一模板大小，并停止扩展。如图3-2所示：

图3-2模板大小扩展

图3-2中，曲线是待修复边界，为当前优先权最高的点，以为中心，形成初始模板（即最内的矩形框）。然后向外扩展，计算扩展后信息的变化情况，若信息变化较平缓，则继续向外扩展（最外的矩形框）。而信息的变化是平滑还是剧烈，主要是以信息的变化率来体现，而变化率则是以颜色值变化情况来衡量，这与该像素点处的梯度有关，所以是以扩展前后，两个模块间的各个像素点梯度的差值是否超过某个阈值来衡量。具体实现过程如下：

令第次扩展后模板的边界为，即矩形框的四条边与图像已知区域相交部分，那么对于该边界上任意的已知像素点，即，假设它是由外扩后对应的点，令其梯度为，其中以中心差分法计算。而点向外扩展后成为，同样以中心差分计算在的梯度，那么扩散条件为：

(3-1)

其中，是取绝对值函数，是梯度的模。模板自适应大小过程的伪代码如下。

其中表示目前模板的宽度。表示模板往外扩展一层，表示扩展条件不成立，模板回退到上一层大小。阈值是通过进行多次试验而得的对修复结果较好的经验值，本文中取值为10。

通过上述模板自适应过程后，Criminisi算法能针对不同的纹理结构采取不同的模板大小，具体试验结果将在下一章详细讲解。

3.3优先权计算方式的改进

基于纹理合成的算法，最终修复的质量和结果的合理性很大程度上依赖于修复的顺序。因此，一个合理的修复顺序往往能得到好的修复结果，所以修复顺序是纹理合成算法的关键。

在Criminisi算法中，其合成顺序主要是通过一个预先计算的优先权来决定的，而算法中最关键的三步便是计算优先权，选择最佳匹配块，复制并进行信息更新，第三步只是前两步结果的执行，所以影响修复结果的核心步骤便是前两步。对于优先权越高的块，越会被先修复。假设在边界上选择一个像素点，以其为中心形成的块为，其优先权的计算方式为：。从公式中可以看出，其优先权由两项决定，与。其中，表示的是中已知信息的数量，其值越大，表明像素点周围的可靠信息越多，也就应该越先被修复，这主要用于决定图像的纹理部分；表示的是该点在边界上等照度线的强度，主要决定图像的结构部分，可以保证图像中具有线性结构的物体先被修复。与相互补充又相互制约，可使得修复沿着等照度线方向快速向内进行，而则对这种过程起着抑制作用，因为越靠近待修复区域的中心，值越小，故和保持着微妙的平衡。

然而通过多次试验发现在实现过程中，置信度会急剧下降，直到降为0为止。我们知道在数字乘法中，若两个乘数中任何一个处于极值（极大或极小）状态，那么另一个乘数是大还是小就不重要，因为它对结果没有任何影响，此时两者相乘其结果也是极值。所以当急剧下降时，项也就变得无关紧要，根据优先权的计算方式，这使得优先权的值也不再可靠，这会导致出现随机的选择修复顺序，进而造成单步修复结果错误，并且因为Criminisi算法是串行的运行方式，所以错误会不断累积，并且最终得到极差的修复结果。图3-3反应的是在修复过程中，、、的变化情况。

图3-3置信度、数据项、优先权的变化情况

其中，（a）图为数据项的变化趋势，（b）图为置信度的变化趋势，（c）图为优先权的变化趋势。从图3-3中可以看出，置信度随着修复的进行，急剧下降，而数据项除了在具有较强结构的地方出现峰值，其它地方变化则较平缓。而优先权其发展趋势与几乎相同，这是因为在变化缓慢的情况下，的发展趋势决定了优先权的变化情况。

造成上述结果的根本原因是优先权的计算方式不合理，因为乘法不能刻画两个乘数一大一小的极端情况。数据项反应的是图像中的结构部分，然而在优先权的计算过程中，因为乘法却根本没有发挥应有的作用，这与实际情况不相符，实际情况应是随着修复过程的进行，越靠近待修复区域中心，项的作用应越来越小，但应越来越大。从数学的观点来看，本文中将优先权的计算方式由乘法改为加法，并为和分配相应的权重，这对于类似于噪声和其它不确定因素更加稳定：

(3-2)

公式（3-2）增加了的权重，使得其在优先权的计算中能够发挥作用。不会再出现上述的情况。但在实际修复过程中，当遇到“十”字型的待修复区域时，这时图像的结构信息较为复杂，其修复过程往往沿着其中一种结构不断修复，直至将其完成，然后再修复另一结构。这将会使得最终的修复图像在结构相交处出现断层。如图3-4所示。

（a）受损图像（b）修复效果图

图3-4：具有“十”字形结构的修复效果图

图3-4中（a）图为模板图，窗子框架间缺失了一个“十”字形结构。从（b）图中可以看出，窗子只有横着的结构被修复，竖着的结构缺失了一部分。

根据图像的局部自相似性原理，考虑待修复块周边邻域的信息与待修复块的相关性，并将其作为优先权计算的一部分考虑进去，若邻域内有与其相似的信息，说明是结构的延伸。所以，最终优先权的计算方式为：

(3-3)

公式（3-3）中，和仍然为置信度和数据项，与Criminisi相同，而为待修复块与其周围信息