非均匀纹理图像大区域修复算法

何 凯，焦青兰，孟春芝，王 伟

(天津大学电子信息工程学院，天津 300072)

非均匀纹理图像大区域修复算法

何 凯，焦青兰，孟春芝，王 伟

(天津大学电子信息工程学院，天津 300072)

为了改善实际非均匀纹理图像大区域修复效果，提出了一种改进的纹理合成算法．在传统图像修复算法优先权系数的基础上，增加了方向性优先权系数，为纹理合成时各点的传播方向和进度提供索引；同时，针对非均匀纹理图像渐近变化的特点，将以待修复块为中心的扇形区域作为最优匹配块的搜索区域，以减少误匹配．仿真实验结果表明，该方法能够有效克服传统纹理合成方法没有考虑方向性的缺点，对实际大区域非均匀纹理图像取得了较好的修复效果．

图像修复；纹理合成；非均匀纹理；方向性优先权系数

图像修复是图像处理领域中的重要研究问题之一，也是计算机图形学以及计算机视觉等众多领域的研究热点．目前，小区域图像修复问题(如附加文字、划痕去除等)已经基本解决，当前的研究热点主要集中在大区域图像的修复研究．鉴于基于偏微分方程(partial differential equation，PDE)的修复方法具有容易产生模糊的缺点[1-2]，基于纹理合成的图像修复技术以其相对理想的修复效果，成为当前大区域图像修复的主流．

2003年，Drori等[3]首先提出了基于块的图像修复算法，按照置信度的高低将图像分为 3个部分，对不同置信度的区域采取不同的修复算法．在此基础上，Criminisi等[4]提出了在优先级基础上的基于样本块的图像修复算法，通过计算构造的优先权函数来确定填充最匹配样本块的顺序，由于该算法可以同时兼顾纹理信息和较为简单的结构信息，保持了纹理的自然过渡和主要结构的连贯性，取得了较好的处理效果，可用于大面积信息缺损区域的修复，代表了当前图像修复算法的主流方向．2005年，Xue等[5]提出了基于颜色比梯度的修复方法，对最优纹理块的匹配准则进行了调整．随后，Kuo等[6]提出了一种基于梯度分析的自适应修复算法，在一定程度上避免了图像的模糊化效应．同年，Wong和 Orchard[7]将非局部均值的概念引入到图像修复技术中，利用多样本的非局部图像信息修复破损区域，改善了图像的修复质量．Liu等[8]将数字图像修复技术应用到文物保护中，采用局部搜索法加快了基于样本的修复过程，提高了修复效率．

近年来，国外还涌现出了一批结构传播和纹理合成相结合的算法，其共同特点是首先修复图像的结构信息，然后利用结构信息来指导纹理的填充过程，如文献[9]提出了基于边缘的图像修复算法，利用最小代价法来实现多边缘的匹配和自动连接；Shen和Li[10]依据边缘信息来重构图像的结构，可消除边缘结构的模糊化；Wang等[11]利用纹理特征和结构信息将图像分为几个部分，然后依次修复结构和填充纹理，取得了不错的结构修复效果．

综上所述，近年来图像修复算法的改进主要集中在结构修复以及提高修复效率等方面，但在纹理合成方面仍沿袭 Criminisi等[4]提出的基于样本块的修复算法；该方法虽然在均匀纹理图像大区域修复方面取得了很好的效果，但对于实际拍摄的非均匀图像(如海天、晚霞、云雾等背景)极易产生误匹配，导致修复效果不理想．为此，笔者根据实际拍摄非均匀纹理图像方向性较强的特点，在原有优先权的基础上增加了方向性优先权系数，为纹理合成的方向和进度提供索引，从而保证纹理合成的过程中始终保持合理的进度和方向，以改善修复效果．

1 基于样本块的纹理合成算法

基于样本块的纹理合成修复原理如图1所示，其中Ω为源区域(有效信息区域)，Φ为破损区域，Ω∂为待修复区域边界．

图1 基于样本块的纹理合成示意Fig.1 Schematic diagram of exemplar-based texture synthesis algorithm

Criminisi等[4]提出的基于样本块的纹理合成修复方法可以概括叙述如下．

首先确定待修补纹理块的优先权，然后按照优先权的顺序对破损区域逐次进行修复．图1中，点p为边沿上的指定一点，为以 p点为中心的待修复块．设表示目标区域中的已知信息量，表示Ψp中的结构信息量，则优先权系数定义为

其中

Cp取决于待匹配块Ψp中已知的像素信息，位置越向修复区域内部，其值就越小，从而在一定程度上引导了图像由破损区的外围向中心扩散进行修复．

2 本文改进算法

基于样本块的纹理合成修复方法在对均匀纹理的合成方面取得了较好的处理效果；然而，由于实际拍摄影像纹理经常表现出非均匀性的特点，在纹理合成的过程中对传播方向有很高的要求，仅仅依靠边沿法向量的方向来限制纹理传播方向很容易发生误匹配，进而影响图像最终修复效果．

鉴于此，本文首先按照由内到外的原则确定待修复区域的等高线分布，再利用求等高线的方法确定方向性指数，通过与传统的信息量和结构性指数相结合，形成新的优先权指数，为纹理合成的方向和进度提供索引，从而保证在大区域纹理合成的过程中能够始终保持正确的方向和进度，以减小误匹配，满足实际非均匀纹理合成的要求．算法同时改进了最优匹配块的搜索区域，使得最优匹配块的搜索更为精确有效．

2.1 改进后修复优先权系数的计算

理想的纹理修复顺序应该是从图像的破损区四周向重心逐步扩散，同时兼顾信息量和结构性信息．为此，本文通过定义方向性优先权系数，对破损区域内所有点在不同方向上的优先权进行定量描述，并将其与传统方法优先权系数相结合，来保证纹理合成能够始终保持正确的方向．具体方法如下所述．

首先计算破损区域Φ的重心O坐标

其中S为待修复区域Φ的面积(所有待修复点数的总和)，

然后，以点O为起点做 360条射线，按角度将破损区域Φ等分为360等份，如图2所示．

图2 方向性优先权系数示意Fig.2 Schematic diagram of directional priority coefficient

将任意一条射线OLn(按逆时针方向依次排列，其中n∈N)和区域Φ边界的交点到重心O的距离记作dn，其中n为整数，．对于破损区Φ内的任一点p，其到重心O的距离记为dp，如果射线Op与射线OL0的夹角θ满足关系

则令 nθ= ，其中n为整数，1 360n≤ ≤ ．因此点p的方向性优先权系数可以定义为

最后，将图像的方向性系数和原有的信息量系数、结构性系数结合，重新定义新的优先权系数pT，即

式中：pC和pD分别代表信息量和结构性系数；1λ和 λ2为权重系数，它们满足关系；1λ和2λ可以根据具体图像进行选取，实际纹理图像的方向性越强，的值也应该越大．利用改进后的优先权系数来确定图像破损区的修复顺序(由大到小)．

2.2 纹理合成

根据实际非均匀纹理图像方向性的特点，本文将最优匹配块的选择区域由原来的矩形区域转换为扇形区域，沿待修复点所在的方向进行搜索，以提高搜索效率，如图3所示．

图3 方向性纹理修复及样本块搜索区域Fig.3 Diagram of directional texture completion and exemplar-searching area

对于破损区内的任一点p，扇形区域Ψ中任一点q( x,y)须满足

式中d和dθ根据实际情况选取，本文取

图4 改进算法流程Fig.4 Flow chart of improved algorithm

3 实验仿真结果与比较

为了验证上述方法的有效性，本文选取几幅实际拍摄纹理图像(如海洋、天空、晚霞以及几种纹理的混合图像)进行实验仿真．其中1λ、2λ分别取0.3和0.7，实验结果如图5～图7所示(椭圆曲线标示差异)．

从图中可以看出，利用传统方法的纹理合成效果(见图 5(c)、图 6(c)和图 7(c))出现了误匹配，具有明显的修复痕迹，而本文方法由于加入了方向性系数，使得修复顺序更加合理，符合人眼的视觉要求，取得了良好的修复效果(见图5(d)、图6(d)和图7(d))．

图5 天空和海洋的修复效果Fig.5 Texture completion effect of sky and ocean

图6 天空和沙滩纹理的合成效果Fig.6 Texture synthesis effect of sky and sandy beach

图7 天空、树林和草地的合成效果Fig.7 Texture synthesis effect of sky, wood and grass

表1比较了Criminisi算法和本文算法的时间复杂度，其中图5～图7待修复区域的像素总数分别为5 727、9 911和15 614．

从表 1中可以看出，加入方向性优先权系数之后，本文算法的时间复杂度和原方法相差不大．实验选用 MATLAB语言进行实验仿真，计算机配置为Pentium IV、2.66,GHz、内存1.00,GB．

表1 Criminisi算法和本文算法时间复杂度比较Tab.1 Complexity comparison between Criminisi algorithm and our algorithm

4 结 语

本文针对传统基于样本块优先权的纹理合成方法在纹理传播方向上的不足，对原有优先权进行了改进．以图像方向性特征为基础增加了方向性优先权系数，同时改进了最优匹配块的搜索区域．仿真实验结果表明，与原算法相比，该算法能够有效改善修改图像的整体视觉效果，对实际非均匀纹理图像取得了理想的修复效果．

本文算法的目的是改善非均匀纹理合成效果，对图像结构修复效果改善不明显，对于结构信息显著的自然纹理图像修复，还需要在今后做进一步的研究．

［1］ Bertalmio M，Sapiro G，Caselles V，et al. Image inpainting[C]//Proceedings of SIGGRAPH 2000. New Orleans，USA，2000：417-424.

［2］ Chan T，Shen J，Vese L. Variational(PDE)models in image processing[J]. Notices Amer Math Soc，2003，50(1)：14-26.

［3］ Drori I，Cohen-Or D，Yeshurun H. Fragment-based image completion[C]//Proceedings of ACM SIGGRAPH. New York，USA，2003，22(3)：303-312.

［4］ Criminisi A，Perez P，Toyama K. Object removal by exemplar-based inpainting[C]//Proceedings of 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Wisconsin， USA，2003：721-728.

［5］ Xue Yanbing，Zhang Hua，Wang Fayu，et al. Exemplar-based image completion using color ratio gradient[J]. Image and Signal Processing，2008，5(3)：569-572.

［6］ Kuo C M，Yang N C，Chang W H，et al. Image recovery based on effective image completion[C]//Intelligent Information Hiding and Multimedia Signal Processing. Harbin，China，2008：393-396.

［7］ Wong A，Orchard J. A nonlocal-means approach to exemplar-based inpainting[C]// IEEE International Conference on Image Processing. Piscataway，NJ，USA，2008：2600-2603.

［8］ Liu Liping，Li Haisheng. Image completion and its application in cultural relic preservation[C]// Image and Signal Processing. Tianjin，China，2009：1-5.

［9］ Rares A，Reinders M J T，Biemond J. Edge-based image restoration[J]. IEEE Transactions on Image Processing，2005，14(10)：1454-1468.

［10］ Shen Minfen，Li Bin. Structure and texture image inpainting based on region segmentation[C]//Proceedings of IEEE International Conference on Acoustics，Speech and Signal Processing. Hawaii，USA，2007：701-704.

［11］ Wang Minqin，Han Guoqiang，Tu Yongqiu. Edge-based image completing guided by region segmentation[C]//Proceedings of ISECS International Colloquium on Computing，Communication，Control，and Management. Guangzhou，China，2008：152-156.

Non-Regular Texture Image Completion Algorithm in Large Region

HE Kai，JIAO Qing-lan，MENG Chun-zhi，WANG Wei
(School of Electronic Information Engineering，Tianjin University，Tianjin 300072，China)

In order to improve the completion effect of actual non-regular texture images in large region，an improved texture synthesis algorithm was proposed. Based on the traditional priority coefficient，the completion algorithm was improved by adding a directional priority coefficient to index the texture propagation direction and process of each point. Moreover，in order to reduce the mismatch，the patch-centered sector was taken as the searching scope for the best matching sample，taking into account the gradual changing characteristic of non-regular texture images. The results of the simulation experiment show that the algorithm can effectively overcome the directional problem，which was not covered by traditional texture synthesis methods，and get perfect completion effect on actual nonregular texture images in large region.

image completion；texture synthesis；non-regular texture；directional priority coefficient

TK391

A

0493-2137(2012)04-0314-05

2010-01-28；

2011-03-31.

国家自然科学基金资助项目(61002030).

何 凯（1972— ），男，博士，副教授.

何 凯，hekai626@163.com.