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,