采用双线性插值收缩的图像修复方法

1、OpticsandPrecisionEngineering2010年5月May2010文章编号10042924X(2010)0521234208第18卷第5期光学精密工程Vol.18No.5采用双线性插值收缩的图像修复方法王昊京1,2,王建立1,王鸣浩1,2,阴玉梅1(1.中国科学院长春光学精密机械与物理研究所,吉林长春130033;2.中国科学院研究生院,北京100039)摘要:针对Criminisi,法收缩待修复的图像,0.20.5倍,并在源区域中搜索最佳匹配修复块。然后,在待,并将其填充到待修复图像的修复区域,。实验结果表明,采用本文提出的算法进行图像修复时,其时效约为Criminisi

2、等人提出的算法的540倍,该方法可以在获得高的修复效率同时保持良好的修复质量。关键词:图像修复;收缩图像;样本匹配;双线性插值;效率中图分类号:TP391.41文献标识码:Adoi:10.3788/OPE.20101805.1234EfficientimageinpaintingbasedonbilinearinterpolationdownscalingWANGHao2jing1,2,WANGJian2li1,WANGMing2hao1,2,YINYu2mei1(1.ChangchunInstituteofOptics,FineMechanicsandPhysics,ChineseAcade

3、myofScience,Changchun130033,China;2.GraduateUniversityofChineseAcademyofScience,Beijing100039,China)Abstract:Toovercometheshortcomingsoflongtime2consumingandlowefficiencyfromtheexem2plar2basedimageinpaintingalgorithmproposedbyCriminisi,animageinpaintingalgorithmwaspres2ented,inwhichthebilinearinterp

4、olationalgorithmwasusedtodownscaletheoriginalimageandtoimproveinpaintingefficiency.Firstly,thedimensionoftheoriginalimagewasdownscaledbyafactor0.220.5,thentheinpaintedpointwiththehighestpriorityfromatargetregionwasevaluatedandabest2exemplarwassearchedfromthesourceregioninthedownscaledimage.Furthermo

5、re,thosecounterpartswereobtainedbytheproposedrulesfromtheoriginalimageandwerefilledintothewholedamagedregionintheoriginimage.Theabovestepswereiterateduntilthetargetregionswerecompletelyfilled.Experimentalresultsdemonstratethattheproposedimageinpaintingalgorithmcan收稿日期:2009207201;修订日期:2009209230.基金项目

6、:国家863高技术研究发展计划资助项目(No.2008AA8080502)© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. 第5期王昊京,等:采用双线性插值收缩的图像修复方法1235inhance5240timestheinpaintingefficiencyoftheCriminisis,whilegoodinpaintingimagesarea2chieved.Thismethodcanobtaingoodinpaintingresultsinefficienc

7、yandquality.Keywords:imageinpainting;imagedownscaling;samplematching;bilinearinterpolation;efficiency1引言图像修复应用广泛,是图像处理领域中一个重要研究分支。它利用图像中目标区域周围的已知信息,按照一定的规则,来修补图像中遗失或损坏的部分,以恢复原图像的完整性,中不需要的元素,实。、余物体、1。Criminisi等人2003年提出一种基于样本的2基于样本的图像修复算法的效率分析1所示。图像修复算法223,对物体的移除和区域的填充效果良好。该算法是基于最佳样本的图像修复方法,它借鉴了纹理生成方法

8、中的思想来寻找样本匹配区域并复制,其重要的贡献是设计出了计算目标修复区域修复块优先级的方法,使得填充顺序仅依据图像自身1。它利用基于结构的修复方法中的扩散方式来定义修复块的优先级,使得边缘附近的修复块具有较高的修复优先级,从而在修复纹理信息的同时对结构信息也有一定的保持3。但在实际应用中,Criminisi等人提出的算法在搜索匹配块时采取全局式搜索方式,并进行其他的相关计算,造成修复过程耗时大、效率低。有不少人针对其算法提出了改进426,但均没有解决其耗时大、效率低的问题,而仅改进了算法的修复效果。本文在分析上述算法的基础上,给出了一种新的图像修复方法,该方法极大地提高了修复时效。首先使用基于

9、双线性插值的图像收缩算法,在给定收缩因子的情况下,收缩原始修复的图像,接着在收缩图像中寻找最佳匹配样本,然后根据收缩图像中得到的最佳匹配样本,在待修复图像中依据一定的规则获得相应最佳匹配样本来修复图像。此方法可以在提高修复时效的同时获得良好的修复质量。图1算法标记图Fig.1NotationdiagramI代表整个待修复图像;图像I中待修复的目标区域为;5表示待修复目标区域的填充前沿;表示像素点已知的源区域,其提供最佳匹配样本,且=I-;p为位于填充前沿5上大+1)×(2+1)的修复块,中心点为p,默小为(2认情况下是大小为9×9的方形窗口模块(实际应用中较最大的可鉴别纹元

10、略大)。2.1Criminisi等人的提出修复算法初始时,手工选定待修复区域或待移除的目标,即目标区域为,算法流程223如下:(1)提取图像中目标区域的初始边界5(2)循环运行下述伪代码直至目标区域填充完毕(a)标识填充前沿5;如果5=<,则退出循环(b)计算优先级P(p),p5.(c)寻找优先级最大的点P处的窗口模板p,即P=argmaxp5tP(p)(d)在中寻找最佳匹配样本,q满足© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. 1236光学精密工程定义

11、如下:第18卷q=argminqd(p,q)(e)将最佳匹配样本q的数据复制到p中,pp(f)更新信度项C(p),pp此算法可以有效地修复图像,但图像修复的过程耗时长、效率低。尤其对大尺寸的图像进行修复时,耗时大的问题十分突出。下面就影响此算法时耗的因素进行分析。2.2Criminisi等人的修复算法的时耗分析假定待修复图像I是大小为SI=M×N的二维数字图像,待修复的目标区域是大小为S的矩形区域,+1)×(2+1)(2),S=(2源区域SSI2.2.1(5),式(5)中np是填充前沿5上p点的法向量, Ip表示与梯度相垂直的向量,其方向与等照度线一致,是一个归一化因子(对

12、于灰度图像=255)。计算每个像素点p的优先级P(p)所需的时间约为一个常量T2。在图像修复中计算填充前沿5P(p)所需的时间t2。在完成第t次图,tSt=S-ttkS为方形,则其周长L5t=D(p)=4t,此项耗时为:SkS算法的每个修复循环都需要搜索填充前沿5t。不妨假设:采用sobel算子检测目标区域t的填充前沿5t,每次检测轮廓线的时间为SIT1,为每个像素执行sobel算子需要的时间,认为是一个常数;每次修复的图像大小为kS,其中k,k(0,1)为每次修复面积系数,也认为是一常数;那么直到目标区域全部被填充,共需要检测的次数为,需要的总时间是:kSt1.kS(1)t2T2t=0L5t

13、<2kS.(6)2.2.3寻找优先级最大像素点P在每个修复循环中都需搜索优先级最大的像素点p,第t次修复循环所需的时间正比于填充前沿5t的周长L5t,比较两个像素优先级大小的耗时约为一个常数T3。完成图像修复时,搜索优先级最大像素点P的耗时为:SkSt3T3t=0L5t<2kS.(7)2.2.4搜索最佳匹配样本q并复制数据到中2.2.2优先级P(p)的计算p在获得优先级最大的像素点p后,可获得最先需填充的修复块p,然后在源区域中搜索与p相匹配的最佳填充块q,并把q中的数据拷贝到p中。q与p满足如下关系:q=argminq(8)d(p,q),式(8)中距离函数d(a,b),定义为SS

14、D(SumofSquaredDifferences),表示图像RGB颜色空间中欧几里德距离。对于待修复图像I中任意像素点p,它计算一次距离函数d(a,b)并且将最佳匹配样本q中的数据复制到p中所需的时间约为一个常数T4,在第t次修复循环中的耗时为(SI-St)T4,那么完成图像修复时此项的耗时为:SkS优先级计算的方法是Criminisi等人提出的算法中关键创新。算法在每个修复循环中都需计算优先级P(p),p5t,定义为:P(p)=C(p)D(p),(2)式(2)中C(p)为表示修复块p的信度项,而D(p)表示修复块p的数据项,定义为:C(p)=qC(p),|p|(3)式(3)中C(p)为修复

15、块p中像素点q的自信度。在修复循环开始前,按照式初始化修复图像中每个像素点的自信度:C(q)=1,q0,q,(4)式(3)中|p|是中心点为P的修复块p的面积,修复块p内的像素点位于源区域内的数目越多,那么像素点p的自信度就越高。D(p)的t4T4t=0(SI-St)<.kS(9)© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. 第5期王昊京,等:采用双线性插值收缩的图像修复方法t(b)计算优先级P(p),p512372.2.5信度项C(q)的更新当具有最高优

16、先级的修复块p被修复后,p中修复点的置信度C(q)需要更新为当前修复块中心点的信度值。每次更新所需的时间与更新的面积大小kS成正比关系,时间系数为T5,完成图像修时信度项C(q)更新所需的总时间为:(10)t5T5S.2.3此图像修复算法的性能分析完成图像修复时所需的总时间记为t,由式(1)、(6)、(7)、(9)、(10)可得:5(c)寻找优先级最大的点P处的窗口模板tp,即()P=argmaxp5Pp(d)据P在中按照一定规则选取p(e)在中寻找最佳匹配样本q,满足:q=argminqd(q)p,(f)据中按照一定的规则选取qq在(g)将最佳匹配样本q的数据复制到pt=i=1ti<T

17、(SI,S,S),(11)在式(11)中定义:22()TSI,S,S=+T5S.kSkS;q的数据复中,pp,p更新信度项C(p),pp(4)对图像I进行全局搜索修复当待修复图像I和目标区域一定时,通过一个收缩因子,(0,1),将图像I的长和宽同时收缩倍,而采用的窗口模板不变。收缩后的图像I和目标区域的大小记为SI和S,22即SI=SI,SS,那么收缩图像修复的耗=)时T(SI,S,S满足如下关系:2)T(SI,ST(SI,S,S),(12),S<假设窗口模板的收缩因子也为,那么耗)时T(SI,S,S满足:)(,S)T(SI,S,S>TSI,S)T(SI,S,S)T(SI,S,S&

18、lt;.(13)下面重点介绍双线性插值的收缩算法、根据选取p在中选取p的规则以及根据q在q的规则。3.1双线性插值的收缩算法收缩图像的方法有最邻近插值和双线性插值等,而双线性插值的方法应用广泛。最邻近插值算法,优点是最邻近插值简单、计算量小,速度快,缺点是图像质量不高,会产生不连续现象7。对于灰度图像,双线性插值算法是利用原始图像上相邻的4个像素点加权平均而获得新像素点的。它比最近邻点法复杂,计算量大,虽然获得的图像有模糊效应,但质量高,连续性好。如图2所示,左边为待修复的图像I,尺寸为:m×n,右边是收缩图像I,收缩因子为,尺寸×n。为:m收缩图像I中的任意像素点为p(x

19、,y),它映射到待修复的图像I中的像素点为p(x,y),通过上述分析可以看到修复收缩图像的耗时远低于原始图像。通过缩放图像可降低时耗,提高速度,是本文的理论基础。3采用双线性插值收缩的修复方法下面给出采用双线性插值收缩的图像修复算法的伪代码。初始时,手工选定待修复区域或待移除的目标区域为,流程如下:(1)使用双线性插值的算法将输入图像的长宽均收缩倍(2)提取待修复目标区域的初始边界5(3)循环运行下述代码直至目标区域被填充完毕tt(a)标识填充前沿5;如果5=<,则退出循环图2双线性插值收缩算法示意图Fig.2Frameworkofbilinearinterpolationdownsca

20、l2ingalgorithm© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. 1238光学精密工程第18卷x,y有可能为浮点数。对于任意点p(x,y)I,双线性插值的收缩算法描述如图2所示。(1)对于任意一个输入点p(x,y)有:x=u=8+1);另一种是设置q的窗口因数是q的-u,y=,v=)-v,x,y0,1,倍,即q=(+1)×(+1)。+1)×(2+1)时,耗时为当q=q=(2)()(T(S,S;当=+1×+1)时,I,Sq),

21、它们的性能有如下关耗时为T(SI,S,S(2)计算与缩放图像中p(x,y)相对于的点p(x,y):p(x,y)=(p(u+1,v)-p(u,v)x+(p(u,v+1)-p(u,v)y+(p(u+1,v+1)+p(u,v)-p(u+1,v)-p(u,v+1)xy+p(u,v)而p(u,v),p(u+1,v),p(u,v+),1,1)I(3)p(x,y(x,系:4)T(SI,ST(SI,S,S),(14),S,较大程度上保持了图像的清晰度。在搜索最佳匹配样本时,采用双线性插值算法较最邻近插值算法搜索的结果更加准确,估计质量更高。3.2据P在选择p的规则t第t次修复循环中P是填充前沿5上优先级最大的

22、像素点。收缩图像I的像素点p(x,y)是由待修复图像I中的四个像素点:p(u,。原因首,其次是它在图像q所,而第一种模板不能。所以在论文中采用第二窗口模板,即q=(+1)×(+1)。使用的窗口模板的面积S越大,修复图像所需的时间就越小,但是窗口尺寸因数不能够太大,否则修复结果会失真。3.4目标区域修复不完全的处理t在本文的方法中若仅依据5=<而退出修复循环会导致修复图像修复不完整。这是因为收缩图像I的目标区域仅仅是对输入图像I的目标区域的一种粗略的估计,由于采用双线性插值算法收缩图像造成了收缩图像I中的像素点是对输入图像I中多点的估计,所以收缩图像I的目标区域修复完毕,但待修复

23、图像I中目标区域却有部分区域仍未被填充完毕。t为完全修复目标区域,在判断5=<后,需对未完全修复的图像I中使用全局搜索的方式进行修复,即本文方法的第4)步。此时所需的总修复时间不会满足式(14),会增加一点,但实验证明它可以满足下式:32T(SI,S,S)<t<T(SI,S,S).(15)v),p(u+1,v),p(u,v+1),p(u+1,v+1)经过双线性插值获得的。P与这四个点的“位置”最为接近,所以p的中心位置点P应该从这四个点中选取。选取的规则如下:t(1)若p(u,v)5,那么p=p(u,v)t(2)假如p(u,v)|5,而p(u+1,v),p(u,上,那v+1)

24、,p(u+1,v+1)至少有一点位于5tt之上的像素点中的任意么p为这三个的位于5一点。(3)假如p(u+1,v)、p(u,v+1)、p(u+1,vt+1)、p(u,v)|5那么p=p(u,v)。通过上述规则可以获得收缩图像I上最先填充像素点P和修复模块p,以及待修复图像I中最先填充的修复块p。3.3据qq的规则在中选取4实验结果分析为了简单、客观地对修复图像的进行评价,这里采用峰值信噪比(PSNR)、均方误差(MSE)、耗时3个指标。峰值信噪比是图像灰度的峰值与噪声方差之比,单位是dB,其评价相对客观9。值越高,传输量和量化误差越小,图像质量越高,代表失真越少5,10。对于图像而言,PSNR

25、定义如下:在收缩图像I中搜索的最佳匹配模板q是对待修复图像I中最佳匹配模板q的一种粗略估计。通过缩放图像中获得的q来寻找待修复图像I中最佳匹配模板q有两种选择:第一种是+1)×(2设置q与q一样,即q=q=(2© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. 第5期王昊京,等:采用双线性插值收缩的图像修复方法1239PSNR=10log10,MSE2(16)式(16)中R是图像数据类型的最大波动值,实验中图像采用24bit的RGB图像,故R=255;输入图

26、像为I,输出图像为K,尺寸均为m×n。均方无误差MSE定义8为:m-1n-1MSE=2()()Ii,j-Ki,jmn,(17)(c)Criminisi的结果(d)本文方法结果c)s)ofproposedmethod对于真彩图像的PSNR有不同的计算方法。这里将图像从RGB空间转换到YCbCr空间中进行计算。敏感,亮度分量Y且G算MSE时,使用Y。MSE越小,证明修复后图像的色差越小,和原始图像的相似性大,质量高。耗时越少,则效率越高。本方法以matlab2008b为平台,在PC机(CPU为Pentium4,3.20GHz,内存为1GB)上图removalfromLena实现。图3是带

27、划痕Lena图像的Criminisi等人算法和本文方法的对比试验。图3(a)是原始Le2na图像。图3(b)是待修复的Lena图像,绿色划痕是待修复区域。如表1所示,在修复中采用收缩因子=0.25,Criminisi等人和本文方法中使用模板的尺寸因子均为=2,lena图像的尺寸为512×512,而划痕的大小为7174pixel。从表1中可以看到本文的方法耗时仅为54.1s,是Criminisi等人的算法的24.7倍;MSE数值较Criminisi等人的算法小,证明本文的方法修复的结果色差小,优于Cri2minisi等人的算法。相应的PSNR的数值也较Criminisi等人的算法小,图

28、像质量高。直观上,图3(c)中Criminisi等人的算法对Lena帽子上划(a)原始图像(b)带划痕图像(a)Originimage(b)Scratchimage痕的修复不是很成功,存在错误的修复块。图3(d)是本文方法的修复图片,看不出明显的错误,修复质量略优于Criminisi等人的算法。表1实验的参数设置及结果Tab.1Resultsandparametersofproposedalgorithm名称LenaPepperGirl算法Criminisi耗时/s1337.054.1787.9113.4912.324.1PSNR/db35.338.439.039.024.724.8MSE/p

29、ixel8.2219.0213.6尺寸/pixel2512×512512×384640×480像素修复数7174696813945窗口尺寸收缩因子223335本文Criminisi本文Criminisi本文图4是图片peppers上文字去除的对比试验。图4a)是原始的peppers图像,图4b)是加入绿色文字的待修复图片。表1中给出了peppers图像中文字去除的数© 1994-2010 China Academic Journal Electronic Publishing House. All rights

30、reserved. 1240光学精密工程第18卷(a)原始图像(b)带文字图像(a)Originimage(b)Imagewithtext(c)Criminisi的结果(d)本文方法结果c)Criminisisresult(d)Resultofproposedmethod图5girlFig.fromgirlimage37.9倍。但MSE和的数值和表1中的Lena和peppers相应的数值有较大的差异,这是因为划痕去除、文字去除所修复的面积远小于物体移除修复的面积。这(c)Criminisi的结果(d)本文方法结果(c)Criminisisresult(d)Resultofproposedmet

31、hod图4Peppers上文字的去除Fig.4Textremovalfrompeppers造成修复结果和原图存在较大的差异,所以MSE数值相对较高,相应的PSNR的数值也低一些。Criminisi的算法和本文方法的MSE和PSNR数值相近,说明修复质量基本一样。直观上,本文方法的修复结果更加合理,原因在于Criminisi的修复结果中出现一根树干,比较突兀。在时效上,Lena图像的耗时3×1370;pepper图像的耗时0×787.9,girl图像的耗时:2×912.3,均满足式(15)和上述分析。

32、据结果。可以看出时效提高到6.9倍,而PSNR和MSE几乎一样。从直观上看,Criminisi等人的修复结果和本文方法的修复质量差异不大。图5是图像中物体移除的对比试验,采用自拍的girl图像。图5(a)是girl原始图像。图5(b)是待修复的girl图像,绿色是待去除的区域。图5(c)是算法的修复结果。而图5(d)是本文方法的结果。对于girl图像,从表1可以看出本文5结论Criminisi等人提出的基于样本的图像修复算法存在修复耗时长、效率低的缺点,本文分析了影响此算法时间性能的因素,提出了采用双线性插值收缩的高效图像修复方法。该方法将原修复图像的长宽同时收缩0.20.5倍,在保持图像修复

33、质量基本不变的情况下,修复时效约为Crimi2nisi等人提出算法的540倍,解决Criminisi等(a)原始图像(b)要去除的物体(a)Originimage(b)Objecttoberemoved人的算法对大尺寸图像进行修复耗时长、效率低的问题。该算法对于其他的图像修复算法也有很好的借鉴意义。都:电子科技大学,2006.ZHANGHY.ResearchandapplicationondigitalimageinpaintingD.Chengdu:ElectronicScience参考文献:1张红英.数字图像修复技术的研究与应用D.成andTechnologyofChina,2006.(i

34、nChinese)© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. 第5期王昊京,等:采用双线性插值收缩的图像修复方法12412CRIMINISIA,PEREZP,TOYAMAK.Objectremovalbyexemplar2basedinpaintingC.Com2puterVisionandPatternRecognition.USA:IEEEComputerSocietyConference,2003:72127陈良,高成敏.快速离散化双线性插值算法J.计算

35、机工程与设计,2007,28(15):378723790.CHENL,GAOCHM.Fastdiscretebilinearinter2polationalgorithmJ.ComputerEngineeringandDesign,2007,28(15):378723790.(inChinese)728.3CRIMINISIA,PEREZP,TOYAMAK.Regionfillingandobjectremovalbyexemplar2basedimageinpaintingJ.IEEETrans.ofImageProcessing,2004,13(9):120021212.4何金海,李薇,屈磊,等.一种改进的基于样本的图8王森,杨克俭.基于双线性插值的图像缩放算法的研究与实现J.自动化技术及应用,2008,27(7):44235.WANGS,YANGKJ.AnimagescalingalgorithmbasedonbilinearinterpolationwithVC+J.TechniquesofAApplication,2008,