基于纹理结构引导自适应的改进Criminisi算法

2016-06-15 09:25汪方正吴建鑫
武汉科技大学学报 2016年2期
关键词:自适应

汪方正,吴建鑫

(1.盐城卫生职业技术学院,江苏 盐城,224005; 2.南京大学计算机科学与技术系,江苏 南京,210023)



基于纹理结构引导自适应的改进Criminisi算法

汪方正1,2,吴建鑫2

(1.盐城卫生职业技术学院,江苏 盐城,224005; 2.南京大学计算机科学与技术系,江苏 南京,210023)

摘要:针对缺损图像修复时容易产生纹理紊乱、边界残缺等问题,基于Criminisi算法提出一种纹理结构引导的自适应图像修复算法。首先对决定合成顺序的优先级进行改进,在数据项中加入结构张量,使图像修复从结构区域向无结构区域填充;其次根据原图像区域纹理结构信息自适应地改变模板块的尺寸,这在一定程度上避免了纹理块过小或过大带来的弊端,从而使合成效果更为自然。实验结果表明,本文提出的改进算法不仅保证了修复图像结构信息的合理填充,还较好地保持了修复边界的完整性,图像修复后具有较佳视觉效果。

关键词:图像修复;Criminisi算法;纹理合成;结构张量;纹理块;自适应

在数字图像的传输和使用过程中,由于某些原因其部分信息可能会丢失或损坏,导致数字图像残缺不整,而图像修复技术可以恢复残缺图像的基本信息。图像修复的实质是利用图像中的已知信息对缺失信息进行填充或替换,这与纹理合成的原理是相同的。

最早的图像修复算法是采用扩散机制的非线性偏微分方程方法。2000年,Bertalmío等[1]借鉴流体扩散的思想提出了一个三阶偏微分方程,这是基于非纹理结构图像修复的基础,随后出现的一些典型算法如全变分模型算法[2]、曲率驱动扩散模型算法[3]、Mumford-Shah算法[4]、Euler’s elastica模型算法[5]、Mumford-Shah-Euler模型算法[6]等都属于此类。基于非纹理结构的图像修复算法对于小面积图像缺失的修复有效果,但用于大尺度破损区域的修复则容易产生模糊现象。

基于纹理的图像修复方法主要有两种,一种方法是利用图像分解的思想,另一种则是运用基于块操作的纹理合成,实际中多采用后者,其中Criminisi算法[7]得到较为广泛的使用。然而,Criminisi算法在修复过程中易将纹理误认为图像边缘,造成修复顺序偏差,最终会影响修复效果,因此对Criminisi算法的改进就成为一个研究热点。文献[8]提出了基于自适应模板的图像修复算法,即根据当前模板块与尺寸扩大后的模板块之间的灰度均值及方差的变化情况来自适应地扩大模板尺寸,以降低误修复率,从而有效提高图像修复精度;文献[9]引入差别因子,改进优先权模型,并通过新的搜索方式来克服修复过程中易产生瑕疵点的不足以完善修复效果;文献[10-14]都是采用不同的策略来改进优先权函数的计算方式,完善最优匹配块搜索策略,提高图像修复精度。

本文基于Criminisi算法提出一种纹理结构引导的自适应图像修复算法,不仅采用结构张量对优先级数据项进行改进,还根据图像结构信息在合成过程中自适应地改变单元块的大小,解决以块为单位进行拼接的纹理合成过程中块大小对合成效果的影响问题,以期使图像修复质量更佳。

1Criminisi算法简介

Criminisi算法主要是对图像修复中的合成顺序作了比较大的改进,从而获得了不错的修复效果。该算法主要有以下三个步骤。

1.1计算待修复块的优先权

优先权的计算关系到图像修复的顺序,是该算法的关键。对于待修复边缘上的每一个像素点,都设定一小块以该像素为中心的区域,优先权最大的目标块最先进行修复。优先权的大小取决于以下两个因素:① 目标块内像素的置信度大小;② 目标块中心点周围结构信息的强弱。Criminisi算法的示意图如下。

图1 Criminisi算法示意图

图1中,Ω表示待修复区域,∂Ω代表其边界轮廓,Φ表示已知区域。对于以轮廓上的点p为中心的目标块,其优先权定义为:

(1)

式中:C(p)为置信度项,表示目标块所含已知像素的比例;D(p)为数据项,表示沿等照度线方向到达边界点p的信息强度函数。C(p)和D(p)分别定义为:

(2)

(3)

式中:Ψp代表目标块;C(q)为目标块中已知像素点的个数;np为垂直于边缘线∂Ω上p点的法向量;代表p点等照度线的方向和强度;α为归一化因子。

1.2搜索最佳匹配块并填充

(4)

1.3更新待修复边缘的优先权

完成以上步骤后,目标块内的未知像素点变为已知像素点,需更新待修复区域边缘的优先权。对于新加入到修补区块内的像素,都要将其与p点像素设为相同置信度,然后循环读取边界点链表中的像素点,计算最佳匹配源块,修补并更新置信度及链表直至链表为空,修复完毕。

1.4Criminisi算法的不足

Criminisi算法对基于纹理合成图像修复的合成顺序给出了置信度C(p)和数据项D(p)的优先级公式,但该算法在图像修复的过程中易将纹理误认为边缘,造成修复顺序偏差,影响修复效果。另外,在以块为单位进行拼接的纹理合成过程中,块的大小对合成效果也有很大的影响。如果单元块小于纹理单元,可能会破坏结构信息;如果单元块比纹理单元大太多,又可能会导致合成效果模糊[15]。由于现实中的图像纹理结构通常是不规则的,为此本文主要针对上述不足之处加以改进,以完善图像的修复效果。

2基于结构张量改进修复算法合成顺序

2.1结构张量的推导

计算各像素点处的梯度向量即可获得该点的结构强度和方向信息,但是单个像素点处的梯度信息并不能充分体现图像的局部结构特性。结构张量相比梯度向量能更好地描述出图像目标的边缘、形状、角点等局部特征,可以丰富图像的局部结构信息。这里定义图像Q的梯度为:

(5)

式中:Qx、Qy分别为x、y方向上的偏导数,Qx=∂xQσ,Qy=∂yQσ,其中Qσ=Gσ*Q,*为卷积算子,可以降低噪声对求导运算的影响,从而提高边缘检测的鲁棒性。

定义初始张量内积φ0为:

(6)

其中δ12=δ21,·代表笛卡尔内积。由上式可知φ0为一个对称半正定2×2矩阵。下面通过推理来进一步说明初始张量内积φ0的特性:

(7)

(8)

通过对φ进行主轴变换就可以提取特征值和特征向量。设λn为张量内积φ的特征值,θn为特征向量:

(9)

(10)

(11)

(12)

另外,张量内积φ的迹可以表征结构强度Pt:

(13)

图像数据的相干性C的计算公式如下:

(14)

2.2基于结构张量待修复块优先权的改进

根据上一节对张量内积φ的推导和计算,下面主要阐述利用其分析图像的局部结构特征,并提取各点局部结构测度。假设导数的加权期望值Ex(Qx)=Ex(Qy),则有:

(15)

根据式(15)可以得知,结构张量φ表征了两个偏导数的联合分布,而协方差矩阵是对称正定的,从而说明结构张量φ存在两个非负特征值λ1和λ2,这里可以将特征值和特征向量理解为椭圆主轴的长度和方向。根据非负特征值λ1和λ2的取值,本文分三种情况对图像局部结构特征进行讨论。

(1)当λ1≈λ2≈0时,表示图像在该点附近沿任何方向的灰度变化都很小,结构强度Pt和相干性C也都很小,此时图像符合平坦区的特征;

(2)当λ1≥λ2≈0时,表示图像在该点附近沿某一方向的变化率远大于沿垂直于此方向的变化率,有较大的结构强度Pt和相干性C,局部的灰度值有很强的相干性,此时图像表现出明显的边缘特征;

(3)当λ1≈λ2≫0时,表示图像在该点附近两个相互垂直的方向上灰度变化都相当快,有较大的结构强度Pt和较小的相干性C,此时图像存在拐角的特征。

为了量化局部结构测度,本文以结构张量φ的两个非负特征值λ1和λ2来进行计算。

方向一致性测度即边强度的计算公式如下:

(16)

角点测度即角强度的计算公式如下:

(17)

为提升修复图像从结构区域向无结构区域填充的效果,这里将图像的局部结构测度加入到决定修复块优先权的因素中,从而得到数据项D(p)的计算公式:

(18)

最后将优先权P(p)更新为:

(19)

式中:ω、ξ分别为置信度项C(p)和数据项D(p)的权重,根据具体的图像进行调整。

3自适应纹理块大小

在图像修复中仅用一阶微分量——梯度来表征图像局部特征是不够的,二阶微分量中含有更丰富的信息。根据文献 [16-17]可知,图像中物体的形状信息取决于等照度线的形态学特征,而等照度线的曲率作为一个二阶微分量是等照度线形态学特征的最重要描述,曲率的倒数为曲率半径,曲率半径在一定程度上可以反映纹理基元的大小。本文通过推导等照度线的曲率半径来自适应调整合成纹理块大小。

这里设图像w(x,y)在任一点处有一条灰度值为h(h为常数)的等照度线,表示为w(x,y)=h。该等照度线上像素点的纵坐标y可以看成是关于横坐标x的函数。w(x,y)=h两边同时对x求导可得:

wx+wyy′=0

(20)

因此,在等照度线处有:

(21)

对式(21)求二阶导数可得:

(22)

(23)

设置纹理合成模板块的尺寸size(block)为:

(24)

式中:η为可调参数。

4修复实验与结果分析

本文利用不同的图像进行修复实验,并将本算法、Criminisi算法、文献[8]和文献[14]中修复算法的修复效果进行对比分析。

图2为对草地填充标记图的修复效果。由图2可见,采用不同算法对同一幅去除人物图像后的填充标记图进行修复时,图2(c)中出现了一小块深色区域(见此图中矩形框处),图2(e)中也出现了深色区域,虽然文献[8]算法对于此区域的修复效果不错,但是在上部阴影部分出现了不连贯的地方(见图2(d)中的小矩形框处),而本文修复算法对该区域的处理相对较为柔和平滑,与周围草坪的大环境相近,视觉效果较为自然。

(a)原图(b)填充标记图(c)Criminisi算法修复效果

(d)文献[8]算法修复效果(e)文献[14]算法修复效果(f)本文算法修复效果

图2草地图像修复效果

Fig.2 Inpainting effect of grassland image

大理石的纹路复杂,局部颜色变化较为尖锐,采用以上几种算法对有缺损的大理石图像进行修复,效果如图3所示。

由图3可以看出,采用Criminisi算法对缺损大理石图像进行修复时,图像纹理结构出现紊乱(见图3(c)中矩形框处),改变了原有图像的纹路,文献[8]和文献[14]中的算法在修复过程中也出现了一定的纹路紊乱现象(见图3(d)和图3(e)中矩形框处),而本文算法在一定程度上保持了原图像的纹路脉络,对纹理结构的处理更好,处理效果与原图较为接近。

(a)原图(b)填充标记图(c)Criminisi算法修复效果

(d)文献[8]算法修复效果(e)文献[14]算法修复效果(f)本文算法修复效果

图3大理石图像修复效果

Fig.3 Inpainting effect of marble image

对损坏严重的眼睛图像进行修复的效果如图4所示。由图4可见,Criminisi算法对单一大小的修复块不能保持纹理的连续性,使得修复图像的纹理失真较为严重(见图4(c)中矩形框处),文献[8]算法的修复效果有所改善,但眼睛和眉毛的纹理失真还是较明显的,文献[14]算法相对于前两种算法有较大的改进,而采用本文算法进行修复时,根据图像特点选择相对合适大小的纹理模板块,同时优化了合成顺序,合成效果有了较为显著的改善,虽然修复图像中有点小瑕疵,但可以利用滤波等方法进行后续完善。

(a)原图(b)填充标记图(c)Criminisi算法修复效果

(d)文献[8]算法修复效果(e)文献[14]算法修复效果(f)本文算法修复效果

图4眼睛图像修复效果

Fig.4 Inpainting effect of eye image

图5所示为几种算法对江岸图像填充标记图的修复效果。由图5可见,Criminisi算法、文献[8]和文献[14]中的算法在修复受损图像时或多或少造成了图像结构的紊乱,修复的填充标记区被无关的信息填充,修复效果不是很理想;本文算法在修复过程中没有干扰图像的整体结构性,而是利用路面对填充标记区进行了延展填充,基本保持了路面的顺畅和平滑,有较好的视觉效果。

(a)原图(b)填充标记图(c)Criminisi算法修复效果

(d)文献[8]算法修复效果(e)文献[14]算法修复效果(f)本文算法修复效果

图5江岸图像修复效果

Fig.5 Inpainting effect of river bank image

以上对图像修复效果的评价是通过肉眼观察来比较修复后图像与原图像(未被破坏的标准图像)的差别,这种方法带有主观色彩。更为科学的方法是利用峰值信噪比(PSNR)作为标准进行评判。PSNR的值越大说明修复后的图像与原标准图像间的误差越小,修复效果就越好。表1列出了几种算法对图2~图5中填充标记图的修复时间和修复图像的峰值信噪比。由表1可见,无论是从修复效率还是从修复质量来看,本文算法都占有优势。

表1 各算法所需修复时间以及修复图像的峰值信噪比

5结语

本文采用纹理合成的思想来解决大面积缺损图像的修复问题。在 Criminisi算法的基础上提出了一种纹理结构引导的自适应图像修复算法,不仅采用结构张量对优先级数据项进行改进,还根据图像结构信息在合成过程中自适应地改变单元块的大小,解决了以块为单位进行拼接的纹理合成过程中块大小对合成效果的影响问题。本文的改进算法不仅能优先保证修复图像结构信息的合理填充,还较好地保持了修复边界的完整性,在一定程度上解决了图像修复的纹理断层现象,因此获得比较好的视觉效果。

参考文献

[1]Bertalmío M, Sapiro G, Caselles V, et al. Image inpainting [C]//Proceedings of SIGGRAPH 2000. New Orleans, USA, July 2000:417-424.

[2]Chan T F, Shen J. Mathematical models for local nontexture inpaintings[J]. SIAM Journal on Applied Mathematics, 2002, 62(3):1019-1043.

[3]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.

[4]Tsai A, Yezzi Jr A, Willsky A S. Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation and magnification[J]. IEEE Transactions on Image Processing,2001,10(8):1169-1186.

[5]Chan T F, Kang S H, Shen J. Euler’s elastica and curvature based inpaintings[J].SIAM Journal on Applied Mathematics, 2002, 63(2): 564-592.

[6]Esedoglu S, Shen J. Digital inpainiting based on the Mumford-Shah-Euler image model[J].European Journal of Applied Mathematics,2002,13(4):353-370.

[7]Criminisi A,Pérez P,Toyama K. Region filling and object removal by exemplar-based image inpainting[J]. IEEE Transactions on Image Processing,2004,13(9):1200-1212.

[8]翟东海,肖杰,鱼江,等.基于自适应模板的图像修复算法[J].计算机应用,2013,33(10): 2891-2894.

[9]任澍,唐向宏,康佳伦.利用纹理和边缘特征的Criminisi改进算法[J].中国图象图形学报,2012,17(9): 1085-1091.

[10]李尊,吴谨,刘劲.基于边缘结构的Criminisi图像修复[J].液晶与显示, 2014,29(5):756-759.

[11]张申华,王克刚,祝轩.局部特征信息约束的改进Criminisi算法[J].计算机工程与应用, 2014,50(8):127-130.

[12]李爱菊,钮文良.基于改进Criminisi算法的图像修复[J].计算机工程与应用, 2014,50 (18):167-170.

[13]侯玉婷,彭进业,韩东辰.改进的Criminisi图像修复算法研究[J].计算机工程与应用, 2015,51(11):135-138.

[14]朱园珠,朱晓临,陈嫚,等.基于改进优先级的自适应图像修复算法[J].合肥工业大学学报:自然科学版, 2014,37(6):683-689.

[15]聂俊岚,王艳芬. 块纹理合成中纹理块尺寸自适应算法[J].计算机辅助设计与图形学学报,2008,20(10):1353-1357.

[16]Sapiro G, Caselles V. Histogram modification via differential equations[J]. Journal of Differential Equations, 1997,135(2):238-268.

[17]Caselles V, Lisani J L, Morel J-M, et al.Shape preserving local contrast enhancement[C]∥Proceedings of the 1997 International Conference on Image Processing(ICIP’97). Washington: IEEE Computer Society,1997:314-317.

[责任编辑尚晶]

Improved Criminisi algorithm based on texture structure guided self-adaptation

WangFangzheng1,2,WuJianxin2

(1.Yancheng Vocational Institute of Health Science, Yancheng 224005, China;2. Department of Computer Science and Technology, Nanjing University, Nanjing 210023, China)

Abstract:For the problems of texture disorder and boundary defect in restored images, this paper proposes a texture structure guided self-adaptive image inpainting approach based on Criminisi algorithm. Firstly, the priority which determines the synthetic sequence is improved by adding structure tensor in data items, so the demaged image is filled from the structural region to the nonstructural ones. Secondly, according to texture information in the original image, the size of each template block is self-adaptively changed, which avoids the disadvantage of improper texture patches to a certain extent, and makes the synthetic effect more natural. Experimental results show that the improved algorithm not only guarantees the reasonable filling of the structural information in the images but also maintains the integrity of the repaired boundaries, and the restored images have better visual effect.

Key words:image inpainting; Criminisi algorithm; texture synthesis; structure tensor; texture patch; self-adaptation

收稿日期:2015-12-18

基金项目:国家自然科学基金优秀青年科学基金资助项目(61422203).

作者简介:汪方正(1981-),男,盐城卫生职业技术学院讲师,南京大学博士生.E-mail:wangfangzheng_81@sina.com通讯作者:吴建鑫(1978-),男,南京大学教授,博士生导师.E-mail:jianxinwu_78@sina.com

中图分类号:TP301.6

文献标志码:A

文章编号:1674-3644(2016)02-0150-06

猜你喜欢
自适应
散乱点云的自适应α—shape曲面重建
浅谈网络教育领域的自适应推送系统
以数据为中心的分布式系统自适应集成方法
自适应的智能搬运路径规划算法
Ka频段卫星通信自适应抗雨衰控制系统设计
电子节气门非线性控制策略
多天线波束成形的MIMO-OFDM跨层自适应资源分配
适应性学习系统的参考模型对比研究
分析,自适应控制一个有乘积项的混沌系统
基于参数自适应蚁群算法对多目标问题的优化