何 凱，梁 然，張 濤

(天津大學(xué)電子信息工程學(xué)院，天津 300072)

基于小波系數(shù)相關(guān)性的紋理圖像快速修復(fù)算法

何 凱，梁 然，張 濤

(天津大學(xué)電子信息工程學(xué)院，天津 300072)

為了實(shí)現(xiàn)紋理圖像的快速修復(fù)，在傳統(tǒng)樣本塊修復(fù)算法的基礎(chǔ)上，提出了一種基于小波系數(shù)相關(guān)性的圖像修復(fù)算法．簡(jiǎn)要論述了紋理圖像各小波變換系數(shù)的相關(guān)性特點(diǎn)；根據(jù)圖像分解后小波系數(shù)高頻成分較少、主要信息均集中在低頻分量以及各分量對(duì)應(yīng)位置的信息具有一致性的特點(diǎn)，算法首先對(duì)破損圖像進(jìn)行小波分解，然后利用最優(yōu)樣本塊匹配的方法對(duì)低頻分量進(jìn)行修復(fù)，同時(shí)實(shí)現(xiàn)其他分量對(duì)應(yīng)位置信息的修復(fù)，最終通過(guò)小波合成完成紋理圖像的修復(fù)．仿真實(shí)驗(yàn)結(jié)果表明，在修復(fù)效果無(wú)明顯差異的基礎(chǔ)上，該算法比原方法的處理時(shí)間大為縮短．

圖像修復(fù)；小波變換；紋理合成；小波系數(shù)相關(guān)性

近年來(lái)，圖像修復(fù)已成為圖像處理和計(jì)算機(jī)視覺(jué)等領(lǐng)域的研究熱點(diǎn)．圖像修復(fù)在日常生活中有著廣泛的應(yīng)用，如填補(bǔ)美術(shù)作品或老照片因年久老化而出現(xiàn)的裂痕、去除圖像中不必要的文字或污點(diǎn)、移除圖像中多余的人或物體等，此外，在圖像壓縮和視頻通信中的錯(cuò)誤隱匿領(lǐng)域中也經(jīng)常使用．

根據(jù)修復(fù)區(qū)域的大小，圖像修復(fù)算法可分為2大類(lèi)．一類(lèi)是基于偏微分方程(partial differential equation，PDE)的圖像修復(fù)算法，如Bertalmio等[1]沿等照度線的方向?qū)⑵茡p區(qū)域周?chē)男畔⑾騼?nèi)傳播，也稱(chēng)為BSCB模型，并在此基礎(chǔ)上推出了CDD (curvature driven diffusion)模型等[2]；隨后Chan等[3]又提出了基于全變分(total variation，TV)模型的算法，并在此基礎(chǔ)上提出了一些改進(jìn)的模型(如Euler-Elastic模型、Mumford-Shah模型、Mumford-Shah-Euler模型等)．上述模型算法在處理圖像中的劃痕、文字等小尺度破損區(qū)域時(shí)，取得了較好的效果，但修復(fù)較大區(qū)域時(shí)，修復(fù)效果不夠理想．另一類(lèi)是基于紋理合成的圖像修復(fù)算法，其基本思想是：按照修復(fù)優(yōu)先權(quán)大小依次從圖像有效信息區(qū)域內(nèi)尋找最優(yōu)匹配塊，逐個(gè)填充到破損區(qū)域當(dāng)中，從而實(shí)現(xiàn)圖像的紋理合成．研究表明[4-7]，該方法能夠有效填充圖像中較大的破損區(qū)域，代表了近年來(lái)圖像修復(fù)領(lǐng)域的主要發(fā)展方向，也取得了一些進(jìn)展[8-12]．然而，當(dāng)前紋理合成算法大都采用全局搜索的方法來(lái)尋找最優(yōu)匹配塊，存在搜索速度慢、容易產(chǎn)生錯(cuò)誤匹配等諸多缺點(diǎn)．

為了克服上述不足，筆者在文獻(xiàn)[8]的基礎(chǔ)上，提出了一種基于小波系數(shù)相關(guān)性的紋理合成算法，該算法充分利用小波分解后，紋理圖像的信息主要集中在低頻分量，且低頻分量與高頻分量具有一定位置對(duì)應(yīng)關(guān)系的特點(diǎn)，能夠有效縮小待修復(fù)區(qū)域大小和搜索范圍，從而提高圖像修復(fù)速度，減少誤匹配．

1 基于樣本塊的紋理合成修復(fù)算法

基于樣本塊的紋理合成修復(fù)算法是目前大區(qū)域紋理修復(fù)的經(jīng)典算法，其基本原理如圖1所示．其中，Ω為待修復(fù)區(qū)域，Ω?為待修復(fù)區(qū)域邊界，Φ為源區(qū)域(有效信息區(qū)域)，p為是邊界上的一點(diǎn)，pΨ為待填充的目標(biāo)區(qū)域塊．

圖1 基于樣本塊的修復(fù)算法示意Fig.1 Diagram of examplar-based completion algorithm

圖像修復(fù)的優(yōu)先權(quán)順序至關(guān)重要，它是決定圖像最終修復(fù)效果的關(guān)鍵因素．邊界點(diǎn)p的優(yōu)先權(quán)

式中：()C p表示當(dāng)前塊可靠性的置信度；()D p表征過(guò)p點(diǎn)的等照度線強(qiáng)度．

式中：p⊥?I表示等照度線的切線方向；np為p點(diǎn)處邊界線的單位法向向量；pΨ||是Ψp內(nèi)的像素個(gè)數(shù)；α為歸一化因子．確定最大優(yōu)先權(quán)點(diǎn)p之后，以p點(diǎn)為中心，在原圖有效區(qū)域內(nèi)搜索Ψp的最優(yōu)匹配塊Ψq，使之滿足關(guān)系

式中：Ψq′為圖中匹配塊；對(duì)應(yīng)點(diǎn)顏色RGB值的方差和．將最優(yōu)匹配塊內(nèi)的信息復(fù)制到破損區(qū)域；更新匹配塊Ψp中修復(fù)好的各點(diǎn)的置信度和待修復(fù)區(qū)域的邊界?Ω；重復(fù)以上步驟，直到破損區(qū)域被全部填充為止．

2 本文算法

2.1 圖像小波系數(shù)相關(guān)性分析

小波理論是20世紀(jì)80年代發(fā)展起來(lái)的一種數(shù)學(xué)方法，由于其在時(shí)域和頻域內(nèi)同時(shí)具有良好的分辨能力，一經(jīng)問(wèn)世就得到了廣泛的應(yīng)用．在二維圖像處理中，Matlab最早將多分辨分析的思想引入到小波的分解和重構(gòu)的快速算法當(dāng)中，即

式中：j為變換尺度；f為圖像信號(hào)；φ為尺度函數(shù)；ψ為小波函數(shù)；為2個(gè)函數(shù)fa和fb的內(nèi)積；和分別為第j層和第j+1層的低頻系數(shù)；而則分別為第j+1層的垂直、水平和對(duì)角方向的高頻系數(shù)．

從式(5)中可以看出，2維小波的多分辨分解相當(dāng)于用一組濾波器組對(duì)圖像進(jìn)行濾波．對(duì)于大多數(shù)的紋理圖像來(lái)說(shuō)，信息主要集中在低頻分量，因此經(jīng)過(guò)1尺度小波分解后，圖像的主要信息都集中在低頻分量(aa)當(dāng)中，而其他3個(gè)分量(ad、da、dd)所包含的信息量很少，從圖2中可以很明顯地看出這一點(diǎn)．

盡管小波變換具有一定的去相關(guān)特性，但變換后圖像各小波系數(shù)之間仍然存在著較強(qiáng)的相關(guān)性，這種相關(guān)性不僅表現(xiàn)在幅值上，還表現(xiàn)在相位上．上述相關(guān)性可以分為3類(lèi)，即尺度內(nèi)的相關(guān)性、尺度間的相關(guān)性、以及同時(shí)考慮尺度內(nèi)和尺度間的系數(shù)相關(guān)性．這些相關(guān)性可以利用“互信息”來(lái)進(jìn)行度量，其定義為

圖2 紋理圖像的各小波分量Fig.2 Wavelet components of texture image

式中：X和Y是具有聯(lián)合概率密度函數(shù)p( x, y)的2個(gè)隨機(jī)變量表示2個(gè)隨機(jī)分布的相關(guān)熵，也稱(chēng)為Kullback-Leibler 散度．

本文主要利用圖像經(jīng)小波變換后尺度內(nèi)的相關(guān)性，它表現(xiàn)為同一子帶內(nèi)的小波系數(shù)具有聚集特性，可以用一個(gè)系數(shù)X與其相鄰系數(shù)NX的互信息I( X; NX)來(lái)衡量；研究表明[4]，這種尺度內(nèi)的相關(guān)性較強(qiáng)，其數(shù)值界于另外2種相關(guān)性之間，即滿足關(guān)系

式中：I( X; PX)為層間父節(jié)點(diǎn)和子節(jié)點(diǎn)的互信息；I( X; PX; NX)為同時(shí)考慮尺度內(nèi)和尺度間的互信息．

2.2 基于小波變換的紋理合成算法

從圖2還可以看出，高頻分量(ad，da，dd)與低頻分量(aa)對(duì)應(yīng)位置的信息是相似的，因此可在修復(fù)小波低頻分量的同時(shí)，實(shí)現(xiàn)對(duì)應(yīng)位置高頻分量的修復(fù)．

基于以上分析，提出了一種基于小波系數(shù)相關(guān)性的紋理合成算法．首先利用基于樣本塊的方法對(duì)小波低頻分量進(jìn)行修復(fù)，選擇最高優(yōu)先權(quán)樣本塊，尋找其最優(yōu)匹配塊，得到低頻分量(aa)中該樣本塊的修復(fù)矢量，如圖3(a)所示；再利用低頻分量與高頻分量對(duì)應(yīng)位置信息的一致性，利用相同的修復(fù)矢量對(duì)3個(gè)高頻分量進(jìn)行修復(fù)，而不再計(jì)算高頻分量(ad，da，dd)的優(yōu)先權(quán)和最優(yōu)匹配塊，如圖3(b)～(d)所示；最后通過(guò)小波合成獲得圖像的最終修復(fù)結(jié)果．

圖3 高頻小波分量的修復(fù)原理Fig.3 High-frequency wavelet component completion principle

該算法有如下5個(gè)步驟．

(1) 對(duì)破損紋理圖像進(jìn)行1尺度2維小波分解．

(2) 計(jì)算小波分解后低頻(aa)分量圖像各點(diǎn)的修復(fù)優(yōu)先權(quán)，選取最高優(yōu)先權(quán)樣本塊，在有效信息區(qū)域內(nèi)搜索其最優(yōu)匹配塊．

(3) 根據(jù)低頻(aa)分量最高權(quán)樣本塊與其最優(yōu)匹配塊的位置關(guān)系，將3個(gè)高頻分量對(duì)應(yīng)位置的圖像分別復(fù)制到各自破損區(qū)域當(dāng)中．

(4) 重復(fù)步驟(2)、(3)直至各小波分量破損區(qū)域全部修復(fù)完成為止．

(5) 將修復(fù)后的各個(gè)小波分量進(jìn)行合成，獲得最終的圖像修復(fù)結(jié)果．

3 實(shí)驗(yàn)仿真結(jié)果

筆者在Matlab 7.4軟件環(huán)境下，對(duì)4幅圖像進(jìn)行了仿真實(shí)驗(yàn)．實(shí)驗(yàn)所用計(jì)算機(jī)配置為P4-2.66,Hz，內(nèi)存1,GB．圖3中小波分解后各分量的修復(fù)效果如圖4所示．為了更好地看出紋理圖像各小波分量的對(duì)應(yīng)關(guān)系，對(duì)圖3和圖4進(jìn)行了適當(dāng)?shù)脑鰪?qiáng)處理．

圖4 圖3紋理圖像各小波分量的修復(fù)效果Fig.4 Completion effect of wavelet components of texture image in Fig.3

從圖4中可以看出，本文算法在修復(fù)低頻小波分量的同時(shí)，其他3個(gè)高頻分量也得到了較好的修復(fù)．由于本文算法僅對(duì)小波分解后的低頻分量進(jìn)行修復(fù)，因此破損區(qū)域大小僅為原來(lái)的1/4，并且搜索區(qū)域也變?yōu)樵瓉?lái)的1/4．這帶來(lái)兩方面的好處：一方面本文算法的修復(fù)時(shí)間因待修復(fù)區(qū)域和搜索范圍變小而大幅度縮短；另一方面，在填充過(guò)程中的塊匹配錯(cuò)誤也因誤差積累機(jī)會(huì)的減少而明顯減少．

本文算法和文獻(xiàn)[8]的算法性能比較如表1所示．從表中可以看出，2種算法結(jié)果的PSNR無(wú)明顯差別，最多相差不超過(guò)0.5,dB；對(duì)4幅圖像，本文算法的處理速度分別比原算法快了14.94、7.3、9.02和11.49倍．

2種算法的仿真結(jié)果如圖5～圖8所示．從圖中可以看出，本文算法的紋理修復(fù)效果與原算法修復(fù)效果一樣，獲得了令人滿意的主觀效果．

表1 本文方法與原方法的性能比較Tab.1 Performance comparison between the proposed method and traditional one

圖5 D93圖像修復(fù)結(jié)果Fig.5 Completion effect of image D93

圖6 D20圖像修復(fù)結(jié)果Fig.6 Completion effect of image D20

圖7 Swan圖像修復(fù)結(jié)果Fig.7 Completion effect of image Swan

圖8 Rabbit圖像修復(fù)結(jié)果Fig.8 Completion effect of image Rabbit

4 結(jié) 語(yǔ)

本文提出了一種基于小波系數(shù)相關(guān)性的紋理圖像修復(fù)算法．該算法充分利用小波系數(shù)的相關(guān)性特點(diǎn)，在對(duì)破損圖像的低頻分量進(jìn)行修復(fù)的同時(shí)，實(shí)現(xiàn)了各高頻分量的自動(dòng)修復(fù)，取得了令人滿意的實(shí)際效果．該算法的最大優(yōu)點(diǎn)在于，在修復(fù)效果相差不多的條件下，本文方法的修復(fù)時(shí)間大為縮短．仿真實(shí)驗(yàn)結(jié)果證明了該方法的有效性．

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

［2］ Chan T F，Shen J. Non-texture inpainting by curvaturedriven diffusions(CCD)[J]. Journal of Visual Communication and Image Representation，2001，12(4)：436-449.

［3］ Chan T F，Shen J. Mathematical models for local nontexture inpaintings[J]. SIAM Journal on Applied Mathematics，2001，62(3)：1019-1043.

［4］ Liu J，Moulin P. Information-theoretic analysis of interscale and intrascale dependencies between Image wavelet coefficients[J]. IEEE Transactions on Image Processing，2001，10(11)：1647-1658.

［5］ Shen J B，Zhou X G，Wang C，et al. Gradient based image completion by solving the Poisson equation[J]. Computers & Graphics，2007，31(1)：119-126.

［6］ Wang M Q，Han G Q，Tu Y Q. Edge-based image completing guided by region segmentation[C] //Proceedings of International Colloquium on Computin，Communication，Control，and Management．Guangzhou，China，2008：152-156.

［7］ Wong A，Orchard J. A nonlocal-means approach to exemplar-based inpainting[J]. Image Processing，2008，10：2600-2603.

［8］ Criminisi A，Perez P，Toyama K. Object removal by exemplar-based inpainting[C]//Proc IEEE Computer Vision and Pattern Recognition. Madison，Wisconsin，USA，2003，2：18-20.

［9］ Drori I，Cohen-Or D，Yeshurun H. Fragment-based image completion[J]. ACM Transactions on Graphics，2003，22(3)：303-312.

［10］ Hao G，Nobutaka O，Shiqeki S. A structure-synthesis image inpainting algorithm based on morphological erosion operation[J]. Image and Signal Processing，2008，5：27-30.

［11］ Shen H F，Zhang L P. A MAP-based algorithm for destriping and inpainting of remotely sensed images[J]. Geoscience and Remote Sensing，2009，47(5)：1492-1502.

［12］ Shih T K，Tang N C，Hwang J N. Exemplar-based video inpainting without ghost shadow artifacts by maintaining temporal continuity[J]. Circuits and Systems for Video Technology，2009，19(3)：347-360.

Fast Texture Image Completion Algorithm Based on Dependencies Between Wavelet Coefficients

HE Kai，LIANG Ran，ZHANG Tao
(School of Electronic Information Engineering，Tianjin University，Tianjin 300072，China)

According to the traditional examplar-based method，a fast texture image completion algorithm based on dependencies between wavelet coefficients was presented in this paper to complete texture images quickly. A simple analysis was made of dependencies between wavelet coefficients of texture images. Since most information about texture images focuses on low-frequency component and all components have dependencies in their corresponding place，the damaged image was first decomposed into four components by wavelet transformation，the low-frequency component was then completed by selecting the best matching patch，the other three components with their own information in the corresponding place were simultaneously completed，and the texture image was finally completed by composing all the completed components together. Simulation results indicate that the running time of the proposed algorithm is remarkably reduced，while the texture completion effect is similar to that of the traditional one.

image completion；wavelet transformation；texture synthesis；dependencies between wavelet coefficients

TN911.72

A

0493-2137(2010)12-1093-05

2009-06-12；

2010-01-08.

國(guó)家自然科學(xué)基金資助項(xiàng)目(61002030)．

何 凱（1972— ），男，博士，副教授．

何 凱，hekai626@163.com.