一种基于样图的图像修复改进算法

康凯，尹东，张荣

中国科学技术大学电子工程与信息科学系，合肥230027

1 引言

图像修复[1]是一门传统技艺，它的目的是以不易觉察的方式重建艺术作品中丢失的或损坏的区域，或者去除不愿让其出现的区域，以恢复艺术作品原来的质量，增加艺术表现力或隐藏信息等。数字图像修复技术是这门传统技艺的发展，它利用计算机对数字图像进行与手工图像修复相似的操作。

数字图像修复算法大致分为两类：基于变分偏微分方程的算法和基于纹理合成的算法[2]。基于变分偏微分方程的算法通过建立图像的先验模型和数据模型，将图像修复问题转化为一个泛函求极值的变分问题。这类方法适用于修复图像中小尺度的缺损区域，对大尺度的缺损区域进行修复时得到的结果比较模糊。这方面的主要文献有[1，3-5]。基于纹理合成的图像修复算法利用已知图像数据模型，将纹理信息复制到破损区域，对于大面积的图像破损，能获得较好的主观效果。文献[6]中提出的Criminisi算法是这一方面的典型算法。

Criminisi算法是基于样图复制粘贴的，不会产生模糊现象，而且其不仅可以修复破损区域的纹理信息，还可以修复破损区域的结构信息。Criminisi算法简单有效，学者们在其基础上，提出了不少改进算法。有的研究从填充优先级角度进行改进，如文献[7-10]。一些研究通过改进搜索顺序或限定搜索范围等来提高Criminisi算法的修复速度，如文献[11-13]。

Criminisi算法在图像平滑区域和突变区域均鼓励优先填充线性边缘结构，这样可能会在图像的平滑区域填充虚假的线性边缘结构。本文针对于此对数据项进行改进。此外本文还针对最优匹配块搜索过程的时间复杂度高的缺点，对SSD算法进行优化，在进行SSD计算的同时更新最佳匹配块。

2 Criminisi算法描述

设I为输入图像，Ω为其待修复区域，∂Ω为Ω的边界，Φ=I-Ω为I中的完好区域。p为∂Ω上一像素点，Ψp是∂Ω上以p为中心的一图像块，如图1所示。

图1 Criminisi算法中符号约定

在利用Criminisi算法[6，14]进行图像修复之前，需要人工交互选定待修复区域Ω。然后按照下面的算法对图像进行处理：

（1）计算∂Ω上各像素点的优先级，以确定修复次序。

优先级的计算采用两个指标，置信度项C(p)和数据项D(p)，最终的优先级定义为两者之积。

置信度项用于保证由外向内地填充待修复区域。首先需要根据人工交互的结果确定图像中各点置信度的初始值：

式中d(Ψ，Ψq)表示两图像块差异的度量，通常选择两图像块各对应像素点各对应通道的颜色值的差的平方和（SSD）。

然后按照式（1）计算边界上各点的新置信度，式中|Ψp|表示以p为中心的窗口区域内的像素总数。

数据项用于鼓励线性结构优先填充，以避免其可能受到的破坏。式中np为点p处的单位法向量；为点p处的等照度线向量，它正交于该点处的梯度向量∇Ip。∇Ip=[Ix，Iy]，，式中Ix和Iy分别表示点p处x和y方向的偏导数。α是归一化因子，对于灰度图像通常有α=255。

（2）搜索最优匹配块并填充：

搜索得最优匹配图像块Ψq后，将其中的像素点复制到Ψ∩Ω中对应的位置。

（3）更新置信度项，待修复区域和完好区域。

Ω=Ω-Ψ∩Ω和Φ=Φ+Ψ∩Ω

（4）重复步骤（1）～步骤（3），直到Ω=∅，即待修复区域修复完毕。

3 本文改进算法

在介绍改进算法之前，先引入一些背景知识。

对于灰度图像，可以在任意像素点p处建立(η，ξ)局部坐标系，其中η轴平行于该点处的灰度梯度方向，ξ轴正交于该点处的灰度梯度方向，即平行于该点处的等照度线或边缘方向。设η和ξ分别为η轴和ξ轴方向的单位向量，已知∇Ip和∇I⊥p分别表示点p处的梯度向量和等照度线向量，所以可以得到：和。设Iη和Iξ分别为p处梯度方向和边缘方向灰度变化率，可得：ξ=0。设Iξξ为p处边缘方向灰度的变化率的变化率，或称为灰度加速率，Iηη为p处梯度方向灰度的加速率，根据数学知识可得[15]：

上式中，Ix和Iy分别为p处x和y方向的偏导数；Ixx，Ixy和Iyy为相应的二阶偏导数。

3.1 Criminisi算法数据项的局限性

利用

一个图像可以分为平滑区域和突变区域，在平滑区域几乎没有边缘结构，而在突变区域存在丰富的边缘结构。因此对数据项的合理约束是在图像的平滑区域，各方向的填充没有优先差别，而在图像的突变区域，鼓励优先填充边缘方向。而原Criminisi算法的数据项在图像平滑区域和突变区域均鼓励优先填充与np夹角小的线性边缘结构，这样可能会在图像的平滑区域填充虚假的线性边缘结构。于是考虑定义新的数据项。

3.2 本文对数据项的改进

可以使用梯度方向和边缘方向的灰度加速率来表征图像位于平滑区域还是突变区域。一般地，在平滑区域，像素点的梯度方向和边缘方向的灰度加速率较小，而在突变区域，像素点的梯度方向和边缘方向的灰度加速率较大。

再结合上面对数据项的约束条件，认为对于∂Ω上的像素点p，在置信度项给定的条件下，该点的填充优先级由该点处的梯度方向和边缘方向的灰度加速率共同决定。详细地，如果点p在图像的平滑区域，其梯度方向和边缘方向的灰度加速率无差别地决定填充优先级；而如果点p在图像的突变区域，为了鼓励图像的边缘结构优先填充，其边缘方向的灰度加速率对填充优先级的贡献率要不小于梯度方向的灰度加速率。综合起来考虑，定义如下的数据项：

式中k是调节因子且k∈[0，1]，其他符号的意义可以参见前文。新的数据项除了满足上面对数据项的要求之外，还有如下特点：鼓励优先填充与np夹角小的边缘结构，并且鼓励优先填充图像的突变区域。

大家知道，在图像平滑区域，||∇2I较小；而在图像边缘处∇2I=0，边缘点附近∇2I则存在较大的波动，故可以认为在突变区域，||∇2I具有较大的值。于是可以定义：

式中β为归一化因子，这里设置β=2×255。

3.3 优化最佳匹配块搜索

为了加快搜索最佳匹配块，在计算SSD时，维护几个变量：当前最佳匹配块及其与待填充块之间的SSD（记为m in_ssd）和距离（记为best_dist）。一开始将当前最佳匹配块与待填充块之间的SSD和距离初始化为很大的数，接着按照算法1，更新最佳匹配块及其与待填充块之间的SSD和距离。在对图像中所有的候选块进行如下算法操作之后，便可以得到最终的最佳匹配块。

由算法描述可见，当待填充块和当前候选块的部分对应像素点的SSD大于当前维护的最小的SSD时，可以断定当前候选块肯定不是最佳匹配块，不再进行两块剩下对应像素点SSD的计算，也不更新维护的变量，直接进入到下一轮待填充块与新的候选块SSD的计算。这一算法可以避免计算待填充块和候选块之间的完整的SSD，从而减少了计算量。

算法1 SSD算法描述

CALCULATE_SSD（待填充块，候选块）

current_ssd=0

for i←0 to图像块的高度

for j←0 to图像块的宽度

do current_ssd+=

对应像素点各通道颜色的差的平方和

do if current_ssd>m in_ssd

then return

current_dist=两图像块之间的距离

if current_ssd==m in_ssd

if current_dist<best_dist

then最佳匹配块=候选块

best_dist=current_dist

else

m in_ssd=current_ssd

最佳匹配块=候选块

best_dist=current_dist

4 实验结果及分析

本文算法实现使用了OpenCV 1.0开源库，实验环境为PC机，硬件配置：CPU为AMD A thlon II X 2 240 Processor（2 800MHz），内存容量为2.00GB。

实验选取了一些典型的图像，填充图像块的大小均为7×7。图像修复的结果图一般没有参考图像，一些客观评价指标如PSNR等已不适用，如果将原图像作为参考图像，由于图像修复的结果以尽可能貌似合理为目的，而不是与原图像的一致性，计算得到的指标也不能正确反映实际的修复效果。因此本文采用主观的评价方法。除了Criminisi算法，实验还选取了文献[7]中的算法结果图像作为对照，在那里数据项被定义为D(p)=，其余的算法流程与Criminisi算法一致。

图2是算法在修复破损照片中的刮痕中的应用，由于刮痕结构简单，Criminisi算法，文献[7]中的算法和本文改进算法的修复效果均比较理想。图3是算法在大目标对象去除中的应用，Criminisi算法由于在平滑区域和突变区域无差别地鼓励优先填充与np夹角小的线性边缘结构，使河岸交界处出现了多余块，以及岸上区域出现了白色杂块，而改进算法修复的结果图没有。图4是算法修复结构图像的示例，Criminisi算法由于相同的原因以及误差传播而使内部产生孔洞，而改进算法会使修复后的边缘因为较为平滑，而且没有产生孔洞。对于文献[7]中提出的算法，线性结构对应于较低的数据项值，所以不会鼓励线性结构的优先填充，如图3（d）中的屋顶和图4（d）的黑色条带的线性结构就被修复断裂。

表1是各算法的运行时间比较，其中的Criminisi算法没有采用3.3节中提出的优化算法，而表中的Criminisi 2算法、文献[7]算法和本文算法均使用了3.3节中提出的优化算法。

图2 实验结果一

图3 实验结果二

图4 实验结果三

表1 运行时间比较

5 结束语

针对Criminisi算法提出了改进和优化。实验表明，本文改进算法的修复效果要优于原来的算法，而且修复时间也有比较可观的减少。

本文还在以下方面进行了尝试：（1）将本文的SSD算法与螺旋线搜索或菱形搜索结合，以期加快最佳匹配块的搜索速度。（2）填充优先级鼓励边缘结构优先填充，但不能保证边缘结构正确填充。于是笔者在SSD计算之前根据某种结构度量淘汰结构差异大的图像块，以避免结构差异大而SSD小的候选块被填充到待填充块。可是这些尝试的效果不是太理想，这是今后的工作方向之一。本文还可以在如下方面进行改进：填充图像块的大小设置对实验效果的影响较大，为了避免这种影响，可以将本文算法与填充图像块大小自适应算法相结合。

[1]Bertalm io M，Sapiro G，Caselles V，et al.Image Inpainting[C]//Proceedings of Computer Graphics，Annual Conference Series，New Orleans，Louisiana，USA，2000：417-424.

[2]张红英.数字图像修复技术综述[J].中国图象图形学报，2007，12（1）：1-10.

[3]Bertalm io M，Bertozzi A L，Sapiro G.Navier-stokes，fluid dynamics，and image and video inpainting[C]//Proc of Conf on Comp Vision Pattern Rec，2001：355-362.

[4]Chan T F，Shen J.Mathematical models for local non-texture inpainting[J].SIAM Journal of Applied Mathematics，2001，62（3）：1019-1043.

[5]Chan T F，Shen J.Non-texture inpainting by Curvature-Driven Diffusions（CDD）[J].Journal of Visual Communication and Image Representation，2001，12（4）：436-449.

[6]Criminisi A，Pérez P，Toyama K.Object Removal by Exemplar-Based Inpainting[C]//Proc of Conf on Computer Vision and Pattern Recognition，Madison，W I，June 2003.

[7]Wu Jiying，Ruan Qiuqi.Object removal by cross isophotes exemplar-based inpainting[C]//Proceedings of the 18th International Conference on Pattern Recognition，2006.

[8]Wu Jiying，Ruan Qiuqi.A novel exemplar-based image completion model[J].Journal of Information Science and Engineering，2009，25（2）：481-497.

[9]陈龙.基于样本块的图像修复方法的改进[J].计算机应用，2011，31（S1）：47-49.

[10]刘奎.基于样例的图像修复改进算法[J].计算机工程，2012，38（7）：193-195.

[11]Tang Feng，Ying Yiting，Wang Jin，et al.A novel texture synthesis based algorithm for object removal in photographs[C]//Proceedings of the 9th Asian Computing Science Conference，Thailand，2004：248-258.

[12]朱霞.一种基于颜色区域分割的图像修复算法[J].计算机工程，2008，34（14）：191-193.

[13]张晴，林家骏.纹理分布分析的快速图像修复算法[J].中国图象图形学报，2012，17（1）：123-129.

[14]Criminisi A，Perez P，Toyama K.Region filling and object removal by exemplar-based image inpainting[J].IEEE Trans on Image Processing，2004，13（9）：1200-1212.

[15]吴亚东.数字图像修复技术[M].北京：科学出版社，2010.