基于区域分割和样本信息的图像修复算法

摘 要：本文提出了一种通过区域分割和样本信息的图像修复算法，该修复算法是迭代的搜索原域和利用原域中最相似的修补块来填充目标域。首先采用区域分割的方法对图像中目标域进行区域划分，确定不同的目标域的修补区域，从而减少对整个原域的搜索；然后利用修补区域中的样本信息选择修补块大小；最后对图像进行修复。实验结果表明，该算法是有效的，从视觉修复效果较其他算法有了显著提高。

关键词：图像；区域分割；样本信息；修复

中图分类号：TP391.41

目前数字图像修复[1]技术主要算法分为两类：基于结构修复和基于纹理修复。基于结构的修复算法主要思想是利用待修补区域的边缘信息，确定扩散信息和扩散方向，从区域边界各向异性地向边界内扩散。这类算法对细长的线段有较好的修复效果，不适合于纹理修复。基于纹理修复算法主要借鉴了纹理生成方法中的思想来寻找样本并进行匹配复制。其中包括了基于图像分解的修复技术和Criminisi等人[2]提出的基于样本的纹理合成算法。这类修复算法对于单一纹理中较大破损区域的图像和文献[6]对多纹理图像有较好的修复效果。但是这几类算法都采用全局搜索，所以计算量大，耗时长。在此基础上本文提出了一种采用区域分割和样本信息的图像修复算法，在此基础上也降低了计算量，从而减少计算时间。

1 本文修复算法

设输入图像I，对其进行区域分割，得到目标域的分割图M，这些分割区域的边界线是通过结构信息进行曲线轮廓的拟合。对于拟合的曲线得到的不同区域，使用原域中的匹配块来进行填充。首先，在目标域的边界上，结合文献[5]计算每个目标修补块的优先级；然后，提出适应性地选择修补块的大小和搜索匹配块，实现对优先修补块的填充；最后，通过新的置信度更新方法，实现对图像的修复。

1.1 区域分割

本文结合文献[3]的分割算法，对分割图M建立曲线图G=（V，E），其中V表示最初的点集合，E表示相应的边缘集，分割图M提供图像I中的结构信息，通过分割过程中不断的迭代合成，M就被分为适当的和准确的区域集合。在每个合成步骤中，如果M域中相邻的两个部分中各自像素点均值的差大于设定的阈值时，则这两个部分不能合成一个部分。即两个部分间就会存在一条边缘集E。这种区域分割实现了两个主要的功能：一是目标域得到了有效的划分；二是有效的选择修补块大小和减少了搜索区域。

1.2 样本信息的匹配和修复

采用分割图M将输入一幅壁画图像I分成若干个区域（包括目标分割域），将其表示为，其中Ri表示图像I的第i个分割部分，N表示总的分割区域。修补块至少属于其中一个部分Ri。通过这种分割结果，对于合适的修补块大小和候选搜索区域而言，该算法能够有效的进行修复。

在自适应选择修补块大小中，如果当前修补块处于几个部分Ri相交的边界上时，预设窗口大小为9X9的模板。如果当前修补块属于其中Ri时，对窗口进行相应的扩大，设置最大修补块窗口为17X17的模板，从而实现高质量的修复。该算法能够减少搜索区域，从而减少运算时间和降低错误率。通过利用分割图中的结构信息，对破损边界进行曲线拟合，结合文献[4]中的Bezier（贝塞尔）曲线，连接不完整的边界线。

1.2.1 搜索最佳匹配块

为了得到最佳的匹配块，通常算法是根据样本信息中像素点的颜色差平方和，选取其中相似度最高的块作为匹配块。由于这种算法只是根据颜色差值进行计算，忽略了其中的结构特征，为了更好的符合人的视觉特征，本文引入了像素点的梯度值，通过梯度相似性和颜色的相似度的结合，取其平均值作为匹配块的选择。

以像素点为中心的最大优先权的修补块和以像素点为中心点的最佳匹配块，在源域中找到与修补块最小距离的匹配块。

（1）

（2）

其中Np是待修补块中的像素点个数之和，C是颜色相似度，G是梯度向量。

1.2.2 匹配块填充和更新置信度

由于优先修补块中各已知像素点的值和匹配块中对应位置处的值之间存在误差，一旦填充这时图像的边缘就发生了变化，对应的边缘点的置信度值也发生了变化，以及这些带有误差的值就会作为其他未知点的已知信息，随着修补的进行而不断的传递，导致错误越来越大。为了防止这种错误，本文提出了新的置信度更新方法。

（3）

其中r和s分别是修补块和匹配块中的像素点，当修补块中任意像素点r属于它与目标域相交的部分时，用匹配块对修补块进行填充；当修补块中任意像素点r属于目标域与原域相交的部分时，用匹配块中的像素点和原像素点的平均值填充重叠区域，使其置信度和边界得到更新。

2 实验结果与分析

本算法是在2.67GHZ CPU，4G内存的PC机上使用VC++ 6.0和OpenCV_1.0实现对图像的修复。首先，对下图“蹦极”预设默认窗口大小为9X9和限制最大窗口为17X17，通过实验结果比较了已有算法和本算法的性能。图中展示了本算法和已有3种修复算法之间的比较，其中（a）为输入图像和（b）为目标域和曲线连接，（c）文献[2]criminisi算法（d）为文献[5]黄伟等人算法（e）为文献[6]吴晓军等人算法。（c）显示了在河畔和建筑物上不自然的纹理模型。（d）比（c）在结构信息方面有更好的重建效果，然而却出现了一些模糊的区域和建筑外形上的弯曲曲线，显得不够自然。（e）和（c）在建筑物的底部阴影部分都出现了不可取的纹理，得到了不自然的填充效果，而（e）却比（d）在建筑外形上显得更加的自然。（f）为本算法的修复结果，从中可以看出视觉上的自然效果，以及结构部分和纹理部分都得到了较好的修复。下图1为本实验图“蹦极”。

（a） （b） （c）

（d） （e） （f）

图1

3 结论

在本文中提出的基于区域分割和样本信息的图像修复算法，本算法通过分割图得到结构和纹理信息，利用结构和纹理信息决定合适的修补块大小和候选域。该算法能够减少由原修补块不正当的匹配引起的反复迭代和错误填充。通过实验结果显示了该算法的有效性，从视觉修复效果较其他算法有了显著提高。

参考文献：

[1]Bwetalmio M，Spairo G，Caselles V，and Ballester C.Image Inpainting.In；Proceedings of ACM SIGGRAPH 2000.New York： ACM Press，2000：417-424.

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

[3]P.F.Felzemszwalb and D.P.Huttenlocher，“Efficient graph based image segmentation”puterVision，vol.59，no.2，167-181sep.2004.

[4]J.Lee and R.-H.Park，“Adaptive exemplar-based inpainting algorithm using region segmentation”in Proc. 26th IEEE Int.Technical Conf.Circuits/Systems，Computers and communication，503-506，Gyeongju，Korea，Jun.2011.

[5]黄伟，王书文.一种结合结构和纹理特征修复敦煌壁画的方法[J].西北民族大学学报，2009.

[6]吴晓军，李功清.基于样本和线性结构信息的大范围图像修复算法[J].电子学报，2012，8.

作者简介：田野，男，硕士研究生，研究方向：数字图像处理与多媒体通信；王慧琴，女，教授，博士生导师，研究方向：网络安全、图像处理、数字水印、智能控制理论与方法等；吴萌，女，讲师，博士研究生，研究方向：数字图像处理和信息管理系统；李俊杰，男，硕士研究生，研究方向：数字图像处理与模式识别。

作者单位：西安建筑科技大学 信息与控制工程学院，西安 710055

基金项目：教育部归国留学人员科研扶持项目：彩绘与壁画文物的数字修复及数字信息安全技术研究（K05055）；陕西省科技厅自然基金：高清唐墓壁画数字图像修复技术的研究（2013JM8015）；陕西省教育厅自然科学类专项研究项目（11JK1027）；复杂背景下的图像分割及在工程中的应用（ZC1103）；数字图像修复技术的研究与应用（QN1022）。