基于紋理結(jié)構(gòu)引導(dǎo)自適應(yīng)的改進Criminisi算法

汪方正，吳建鑫

(1.鹽城衛(wèi)生職業(yè)技術(shù)學(xué)院，江蘇 鹽城，224005； 2.南京大學(xué)計算機科學(xué)與技術(shù)系，江蘇 南京，210023)

?

基于紋理結(jié)構(gòu)引導(dǎo)自適應(yīng)的改進Criminisi算法

汪方正1,2，吳建鑫2

(1.鹽城衛(wèi)生職業(yè)技術(shù)學(xué)院，江蘇 鹽城，224005； 2.南京大學(xué)計算機科學(xué)與技術(shù)系，江蘇 南京，210023)

摘要：針對缺損圖像修復(fù)時容易產(chǎn)生紋理紊亂、邊界殘缺等問題，基于Criminisi算法提出一種紋理結(jié)構(gòu)引導(dǎo)的自適應(yīng)圖像修復(fù)算法。首先對決定合成順序的優(yōu)先級進行改進，在數(shù)據(jù)項中加入結(jié)構(gòu)張量，使圖像修復(fù)從結(jié)構(gòu)區(qū)域向無結(jié)構(gòu)區(qū)域填充；其次根據(jù)原圖像區(qū)域紋理結(jié)構(gòu)信息自適應(yīng)地改變模板塊的尺寸，這在一定程度上避免了紋理塊過小或過大帶來的弊端，從而使合成效果更為自然。實驗結(jié)果表明，本文提出的改進算法不僅保證了修復(fù)圖像結(jié)構(gòu)信息的合理填充，還較好地保持了修復(fù)邊界的完整性，圖像修復(fù)后具有較佳視覺效果。

關(guān)鍵詞：圖像修復(fù)；Criminisi算法；紋理合成；結(jié)構(gòu)張量；紋理塊；自適應(yīng)

在數(shù)字圖像的傳輸和使用過程中，由于某些原因其部分信息可能會丟失或損壞，導(dǎo)致數(shù)字圖像殘缺不整，而圖像修復(fù)技術(shù)可以恢復(fù)殘缺圖像的基本信息。圖像修復(fù)的實質(zhì)是利用圖像中的已知信息對缺失信息進行填充或替換，這與紋理合成的原理是相同的。

最早的圖像修復(fù)算法是采用擴散機制的非線性偏微分方程方法。2000年，Bertalmío等[1]借鑒流體擴散的思想提出了一個三階偏微分方程，這是基于非紋理結(jié)構(gòu)圖像修復(fù)的基礎(chǔ)，隨后出現(xiàn)的一些典型算法如全變分模型算法[2]、曲率驅(qū)動擴散模型算法[3]、Mumford-Shah算法[4]、Euler’s elastica模型算法[5]、Mumford-Shah-Euler模型算法[6]等都屬于此類。基于非紋理結(jié)構(gòu)的圖像修復(fù)算法對于小面積圖像缺失的修復(fù)有效果，但用于大尺度破損區(qū)域的修復(fù)則容易產(chǎn)生模糊現(xiàn)象。

基于紋理的圖像修復(fù)方法主要有兩種，一種方法是利用圖像分解的思想，另一種則是運用基于塊操作的紋理合成，實際中多采用后者，其中Criminisi算法[7]得到較為廣泛的使用。然而，Criminisi算法在修復(fù)過程中易將紋理誤認為圖像邊緣，造成修復(fù)順序偏差，最終會影響修復(fù)效果，因此對Criminisi算法的改進就成為一個研究熱點。文獻[8]提出了基于自適應(yīng)模板的圖像修復(fù)算法，即根據(jù)當前模板塊與尺寸擴大后的模板塊之間的灰度均值及方差的變化情況來自適應(yīng)地擴大模板尺寸，以降低誤修復(fù)率,從而有效提高圖像修復(fù)精度;文獻[9]引入差別因子,改進優(yōu)先權(quán)模型，并通過新的搜索方式來克服修復(fù)過程中易產(chǎn)生瑕疵點的不足以完善修復(fù)效果;文獻[10-14]都是采用不同的策略來改進優(yōu)先權(quán)函數(shù)的計算方式，完善最優(yōu)匹配塊搜索策略，提高圖像修復(fù)精度。

本文基于Criminisi算法提出一種紋理結(jié)構(gòu)引導(dǎo)的自適應(yīng)圖像修復(fù)算法，不僅采用結(jié)構(gòu)張量對優(yōu)先級數(shù)據(jù)項進行改進，還根據(jù)圖像結(jié)構(gòu)信息在合成過程中自適應(yīng)地改變單元塊的大小，解決以塊為單位進行拼接的紋理合成過程中塊大小對合成效果的影響問題，以期使圖像修復(fù)質(zhì)量更佳。

1Criminisi算法簡介

Criminisi算法主要是對圖像修復(fù)中的合成順序作了比較大的改進，從而獲得了不錯的修復(fù)效果。該算法主要有以下三個步驟。

1.1計算待修復(fù)塊的優(yōu)先權(quán)

優(yōu)先權(quán)的計算關(guān)系到圖像修復(fù)的順序，是該算法的關(guān)鍵。對于待修復(fù)邊緣上的每一個像素點，都設(shè)定一小塊以該像素為中心的區(qū)域，優(yōu)先權(quán)最大的目標塊最先進行修復(fù)。優(yōu)先權(quán)的大小取決于以下兩個因素：① 目標塊內(nèi)像素的置信度大??；② 目標塊中心點周圍結(jié)構(gòu)信息的強弱。Criminisi算法的示意圖如下。

圖1　Criminisi算法示意圖

圖1中，Ω表示待修復(fù)區(qū)域,?Ω代表其邊界輪廓，Φ表示已知區(qū)域。對于以輪廓上的點p為中心的目標塊，其優(yōu)先權(quán)定義為：

(1)

式中：C(p)為置信度項，表示目標塊所含已知像素的比例；D(p)為數(shù)據(jù)項，表示沿等照度線方向到達邊界點p的信息強度函數(shù)。C(p)和D(p)分別定義為：

(2)

(3)

式中：Ψp代表目標塊；C(q)為目標塊中已知像素點的個數(shù)；np為垂直于邊緣線?Ω上p點的法向量；代表p點等照度線的方向和強度；α為歸一化因子。

1.2搜索最佳匹配塊并填充

(4)

1.3更新待修復(fù)邊緣的優(yōu)先權(quán)

完成以上步驟后，目標塊內(nèi)的未知像素點變?yōu)橐阎袼攸c，需更新待修復(fù)區(qū)域邊緣的優(yōu)先權(quán)。對于新加入到修補區(qū)塊內(nèi)的像素，都要將其與p點像素設(shè)為相同置信度，然后循環(huán)讀取邊界點鏈表中的像素點，計算最佳匹配源塊，修補并更新置信度及鏈表直至鏈表為空，修復(fù)完畢。

1.4Criminisi算法的不足

Criminisi算法對基于紋理合成圖像修復(fù)的合成順序給出了置信度C(p)和數(shù)據(jù)項D(p)的優(yōu)先級公式,但該算法在圖像修復(fù)的過程中易將紋理誤認為邊緣，造成修復(fù)順序偏差，影響修復(fù)效果。另外，在以塊為單位進行拼接的紋理合成過程中，塊的大小對合成效果也有很大的影響。如果單元塊小于紋理單元，可能會破壞結(jié)構(gòu)信息；如果單元塊比紋理單元大太多，又可能會導(dǎo)致合成效果模糊[15]。由于現(xiàn)實中的圖像紋理結(jié)構(gòu)通常是不規(guī)則的，為此本文主要針對上述不足之處加以改進，以完善圖像的修復(fù)效果。

2基于結(jié)構(gòu)張量改進修復(fù)算法合成順序

2.1結(jié)構(gòu)張量的推導(dǎo)

計算各像素點處的梯度向量即可獲得該點的結(jié)構(gòu)強度和方向信息，但是單個像素點處的梯度信息并不能充分體現(xiàn)圖像的局部結(jié)構(gòu)特性。結(jié)構(gòu)張量相比梯度向量能更好地描述出圖像目標的邊緣、形狀、角點等局部特征，可以豐富圖像的局部結(jié)構(gòu)信息。這里定義圖像Q的梯度為：

(5)

式中：Qx、Qy分別為x、y方向上的偏導(dǎo)數(shù)，Qx=?xQσ，Qy=?yQσ，其中Qσ=Gσ*Q，*為卷積算子，可以降低噪聲對求導(dǎo)運算的影響，從而提高邊緣檢測的魯棒性。

定義初始張量內(nèi)積φ0為：

(6)

其中δ12=δ21，·代表笛卡爾內(nèi)積。由上式可知φ0為一個對稱半正定2×2矩陣。下面通過推理來進一步說明初始張量內(nèi)積φ0的特性：

(7)

(8)

通過對φ進行主軸變換就可以提取特征值和特征向量。設(shè)λn為張量內(nèi)積φ的特征值，θn為特征向量：

(9)

(10)

(11)

(12)

另外，張量內(nèi)積φ的跡可以表征結(jié)構(gòu)強度Pt:

(13)

圖像數(shù)據(jù)的相干性C的計算公式如下：

(14)

2.2基于結(jié)構(gòu)張量待修復(fù)塊優(yōu)先權(quán)的改進

根據(jù)上一節(jié)對張量內(nèi)積φ的推導(dǎo)和計算，下面主要闡述利用其分析圖像的局部結(jié)構(gòu)特征，并提取各點局部結(jié)構(gòu)測度。假設(shè)導(dǎo)數(shù)的加權(quán)期望值Ex(Qx)=Ex(Qy)，則有：

(15)

根據(jù)式(15)可以得知，結(jié)構(gòu)張量φ表征了兩個偏導(dǎo)數(shù)的聯(lián)合分布，而協(xié)方差矩陣是對稱正定的，從而說明結(jié)構(gòu)張量φ存在兩個非負特征值λ1和λ2，這里可以將特征值和特征向量理解為橢圓主軸的長度和方向。根據(jù)非負特征值λ1和λ2的取值，本文分三種情況對圖像局部結(jié)構(gòu)特征進行討論。

(1)當λ1≈λ2≈0時，表示圖像在該點附近沿任何方向的灰度變化都很小，結(jié)構(gòu)強度Pt和相干性C也都很小,此時圖像符合平坦區(qū)的特征；

(2)當λ1≥λ2≈0時，表示圖像在該點附近沿某一方向的變化率遠大于沿垂直于此方向的變化率，有較大的結(jié)構(gòu)強度Pt和相干性C，局部的灰度值有很強的相干性，此時圖像表現(xiàn)出明顯的邊緣特征；

(3)當λ1≈λ2?0時，表示圖像在該點附近兩個相互垂直的方向上灰度變化都相當快，有較大的結(jié)構(gòu)強度Pt和較小的相干性C，此時圖像存在拐角的特征。

為了量化局部結(jié)構(gòu)測度，本文以結(jié)構(gòu)張量φ的兩個非負特征值λ1和λ2來進行計算。

方向一致性測度即邊強度的計算公式如下：

(16)

角點測度即角強度的計算公式如下：

(17)

為提升修復(fù)圖像從結(jié)構(gòu)區(qū)域向無結(jié)構(gòu)區(qū)域填充的效果，這里將圖像的局部結(jié)構(gòu)測度加入到?jīng)Q定修復(fù)塊優(yōu)先權(quán)的因素中，從而得到數(shù)據(jù)項D(p)的計算公式：

(18)

最后將優(yōu)先權(quán)P(p)更新為：

(19)

式中：ω、ξ分別為置信度項C(p)和數(shù)據(jù)項D(p)的權(quán)重，根據(jù)具體的圖像進行調(diào)整。

3自適應(yīng)紋理塊大小

在圖像修復(fù)中僅用一階微分量——梯度來表征圖像局部特征是不夠的，二階微分量中含有更豐富的信息。根據(jù)文獻 [16-17]可知，圖像中物體的形狀信息取決于等照度線的形態(tài)學(xué)特征，而等照度線的曲率作為一個二階微分量是等照度線形態(tài)學(xué)特征的最重要描述,曲率的倒數(shù)為曲率半徑，曲率半徑在一定程度上可以反映紋理基元的大小。本文通過推導(dǎo)等照度線的曲率半徑來自適應(yīng)調(diào)整合成紋理塊大小。

這里設(shè)圖像w(x,y)在任一點處有一條灰度值為h(h為常數(shù))的等照度線，表示為w(x,y)=h。該等照度線上像素點的縱坐標y可以看成是關(guān)于橫坐標x的函數(shù)。w(x,y)=h兩邊同時對x求導(dǎo)可得：

wx+wyy′=0

(20)

因此，在等照度線處有：

(21)

對式(21)求二階導(dǎo)數(shù)可得：

(22)

(23)

設(shè)置紋理合成模板塊的尺寸size(block)為：

(24)

式中：η為可調(diào)參數(shù)。

4修復(fù)實驗與結(jié)果分析

本文利用不同的圖像進行修復(fù)實驗，并將本算法、Criminisi算法、文獻[8]和文獻[14]中修復(fù)算法的修復(fù)效果進行對比分析。

圖2為對草地填充標記圖的修復(fù)效果。由圖2可見，采用不同算法對同一幅去除人物圖像后的填充標記圖進行修復(fù)時，圖2(c)中出現(xiàn)了一小塊深色區(qū)域(見此圖中矩形框處)，圖2(e)中也出現(xiàn)了深色區(qū)域，雖然文獻[8]算法對于此區(qū)域的修復(fù)效果不錯，但是在上部陰影部分出現(xiàn)了不連貫的地方(見圖2(d)中的小矩形框處)，而本文修復(fù)算法對該區(qū)域的處理相對較為柔和平滑，與周圍草坪的大環(huán)境相近，視覺效果較為自然。

(a)原圖(b)填充標記圖(c)Criminisi算法修復(fù)效果

(d)文獻[8]算法修復(fù)效果(e)文獻[14]算法修復(fù)效果(f)本文算法修復(fù)效果

圖2草地圖像修復(fù)效果

Fig.2 Inpainting effect of grassland image

大理石的紋路復(fù)雜，局部顏色變化較為尖銳，采用以上幾種算法對有缺損的大理石圖像進行修復(fù)，效果如圖3所示。

由圖3可以看出，采用Criminisi算法對缺損大理石圖像進行修復(fù)時，圖像紋理結(jié)構(gòu)出現(xiàn)紊亂(見圖3(c)中矩形框處)，改變了原有圖像的紋路，文獻[8]和文獻[14]中的算法在修復(fù)過程中也出現(xiàn)了一定的紋路紊亂現(xiàn)象(見圖3(d)和圖3(e)中矩形框處)，而本文算法在一定程度上保持了原圖像的紋路脈絡(luò)，對紋理結(jié)構(gòu)的處理更好，處理效果與原圖較為接近。

(a)原圖(b)填充標記圖(c)Criminisi算法修復(fù)效果

(d)文獻[8]算法修復(fù)效果(e)文獻[14]算法修復(fù)效果(f)本文算法修復(fù)效果

圖3大理石圖像修復(fù)效果

Fig.3 Inpainting effect of marble image

對損壞嚴重的眼睛圖像進行修復(fù)的效果如圖4所示。由圖4可見，Criminisi算法對單一大小的修復(fù)塊不能保持紋理的連續(xù)性，使得修復(fù)圖像的紋理失真較為嚴重(見圖4(c)中矩形框處)，文獻[8]算法的修復(fù)效果有所改善，但眼睛和眉毛的紋理失真還是較明顯的，文獻[14]算法相對于前兩種算法有較大的改進，而采用本文算法進行修復(fù)時，根據(jù)圖像特點選擇相對合適大小的紋理模板塊，同時優(yōu)化了合成順序，合成效果有了較為顯著的改善，雖然修復(fù)圖像中有點小瑕疵，但可以利用濾波等方法進行后續(xù)完善。

(a)原圖(b)填充標記圖(c)Criminisi算法修復(fù)效果

(d)文獻[8]算法修復(fù)效果(e)文獻[14]算法修復(fù)效果(f)本文算法修復(fù)效果

圖4眼睛圖像修復(fù)效果

Fig.4 Inpainting effect of eye image

圖5所示為幾種算法對江岸圖像填充標記圖的修復(fù)效果。由圖5可見，Criminisi算法、文獻[8]和文獻[14]中的算法在修復(fù)受損圖像時或多或少造成了圖像結(jié)構(gòu)的紊亂，修復(fù)的填充標記區(qū)被無關(guān)的信息填充，修復(fù)效果不是很理想；本文算法在修復(fù)過程中沒有干擾圖像的整體結(jié)構(gòu)性，而是利用路面對填充標記區(qū)進行了延展填充，基本保持了路面的順暢和平滑，有較好的視覺效果。

(a)原圖(b)填充標記圖(c)Criminisi算法修復(fù)效果

(d)文獻[8]算法修復(fù)效果(e)文獻[14]算法修復(fù)效果(f)本文算法修復(fù)效果

圖5江岸圖像修復(fù)效果

Fig.5 Inpainting effect of river bank image

以上對圖像修復(fù)效果的評價是通過肉眼觀察來比較修復(fù)后圖像與原圖像(未被破壞的標準圖像)的差別，這種方法帶有主觀色彩。更為科學(xué)的方法是利用峰值信噪比(PSNR)作為標準進行評判。PSNR的值越大說明修復(fù)后的圖像與原標準圖像間的誤差越小，修復(fù)效果就越好。表1列出了幾種算法對圖2～圖5中填充標記圖的修復(fù)時間和修復(fù)圖像的峰值信噪比。由表1可見，無論是從修復(fù)效率還是從修復(fù)質(zhì)量來看，本文算法都占有優(yōu)勢。

表1　各算法所需修復(fù)時間以及修復(fù)圖像的峰值信噪比

5結(jié)語

本文采用紋理合成的思想來解決大面積缺損圖像的修復(fù)問題。在 Criminisi算法的基礎(chǔ)上提出了一種紋理結(jié)構(gòu)引導(dǎo)的自適應(yīng)圖像修復(fù)算法，不僅采用結(jié)構(gòu)張量對優(yōu)先級數(shù)據(jù)項進行改進，還根據(jù)圖像結(jié)構(gòu)信息在合成過程中自適應(yīng)地改變單元塊的大小，解決了以塊為單位進行拼接的紋理合成過程中塊大小對合成效果的影響問題。本文的改進算法不僅能優(yōu)先保證修復(fù)圖像結(jié)構(gòu)信息的合理填充，還較好地保持了修復(fù)邊界的完整性，在一定程度上解決了圖像修復(fù)的紋理斷層現(xiàn)象，因此獲得比較好的視覺效果。

參考文獻

[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]翟東海,肖杰,魚江,等.基于自適應(yīng)模板的圖像修復(fù)算法[J].計算機應(yīng)用,2013,33(10): 2891-2894.

[9]任澍,唐向宏,康佳倫.利用紋理和邊緣特征的Criminisi改進算法[J].中國圖象圖形學(xué)報,2012,17(9): 1085-1091.

[10]李尊,吳謹,劉勁.基于邊緣結(jié)構(gòu)的Criminisi圖像修復(fù)[J].液晶與顯示, 2014,29(5):756-759.

[11]張申華,王克剛,祝軒.局部特征信息約束的改進Criminisi算法[J].計算機工程與應(yīng)用, 2014,50(8):127-130.

[12]李愛菊,鈕文良.基于改進Criminisi算法的圖像修復(fù)[J].計算機工程與應(yīng)用, 2014,50 (18):167-170.

[13]侯玉婷,彭進業(yè),韓東辰.改進的Criminisi圖像修復(fù)算法研究[J].計算機工程與應(yīng)用, 2015,51(11):135-138.

[14]朱園珠,朱曉臨,陳嫚,等.基于改進優(yōu)先級的自適應(yīng)圖像修復(fù)算法[J].合肥工業(yè)大學(xué)學(xué)報:自然科學(xué)版, 2014,37(6):683-689.

[15]聶俊嵐，王艷芬. 塊紋理合成中紋理塊尺寸自適應(yīng)算法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,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

基金項目：國家自然科學(xué)基金優(yōu)秀青年科學(xué)基金資助項目(61422203).

作者簡介：汪方正(1981-)，男，鹽城衛(wèi)生職業(yè)技術(shù)學(xué)院講師，南京大學(xué)博士生.E-mail：wangfangzheng_81@sina.com通訊作者：吳建鑫(1978-),男，南京大學(xué)教授，博士生導(dǎo)師.E-mail：jianxinwu_78@sina.com

中圖分類號：TP301.6

文獻標志碼：A

文章編號：1674-3644(2016)02-0150-06