基于馬爾科夫隨機(jī)場(chǎng)匹配準(zhǔn)則的Crim inisi修復(fù)算法*

趙 娜，王慧琴，吳 萌

西安建筑科技大學(xué) 信息與控制工程學(xué)院，西安 710055

基于馬爾科夫隨機(jī)場(chǎng)匹配準(zhǔn)則的Crim inisi修復(fù)算法*

趙 娜，王慧琴+，吳 萌

西安建筑科技大學(xué) 信息與控制工程學(xué)院，西安 710055

+Corresponding author:E-mail:hqwang@xauat.edu.cn

ZHAO Na,WANG Huiqin,WU M eng.Crim inisidigital inpainting algorithm based on M arkov random field matching criterion.Journalof Frontiersof Com puter Science and Technology,2017,11(7)：1150-1158.

傳統(tǒng)的基于樣本的修復(fù)算法在修復(fù)數(shù)字圖像時(shí)精度較低，提出了一種基于馬爾科夫隨機(jī)場(chǎng)（Markov random field，MRF）匹配準(zhǔn)則的Crim inisi數(shù)字圖像修復(fù)算法。該算法以馬爾科夫隨機(jī)場(chǎng)替代歐氏距離匹配準(zhǔn)則，在尋找最佳匹配塊前首先通過(guò)馬爾科夫隨機(jī)場(chǎng)對(duì)圖像紋理建模，然后計(jì)算圖像全局能量對(duì)待修復(fù)像素塊進(jìn)行估值，最后尋找最佳匹配塊以達(dá)到全局最優(yōu)。實(shí)驗(yàn)結(jié)果表明，該算法對(duì)數(shù)字圖像的修復(fù)有了很大改善，紋理誤匹配率下降，修復(fù)精度得到明顯提高。

Criminisi；馬爾科夫隨機(jī)場(chǎng)（MRF）；匹配準(zhǔn)則；圖像修復(fù)

1 引言

數(shù)字圖像修復(fù)是指對(duì)局部區(qū)域內(nèi)丟失的數(shù)據(jù)按照特定規(guī)則進(jìn)行修補(bǔ)，以恢復(fù)其完整性，使人眼無(wú)法觀察到圖像曾經(jīng)缺損或已被修復(fù)，在視覺(jué)上認(rèn)為修復(fù)后的這幅圖像是合理而完整的。目前該技術(shù)主要應(yīng)用于文物字畫(huà)的保護(hù)、破損圖像的修補(bǔ)、影視特技制作以及目標(biāo)物的移除等領(lǐng)域。圖像修復(fù)從其問(wèn)題本身來(lái)講是一個(gè)數(shù)學(xué)上的病態(tài)問(wèn)題，它具有不穩(wěn)定且不唯一的解，也就是說(shuō)人們僅通過(guò)已知信息無(wú)法使圖像恢復(fù)原狀。

Criminisi等人[1]提出了一種基于樣本的圖像修復(fù)算法，它利用了基于結(jié)構(gòu)的修復(fù)方法中的擴(kuò)散方式來(lái)定義修復(fù)塊的優(yōu)先級(jí)，可同時(shí)兼顧圖像紋理信息和結(jié)構(gòu)信息，并通過(guò)全圖搜索設(shè)定匹配準(zhǔn)則以尋找最佳匹配塊。在實(shí)際應(yīng)用中，發(fā)現(xiàn)待修復(fù)像素塊與最佳匹配塊之間匹配準(zhǔn)則的設(shè)定對(duì)修復(fù)結(jié)果影響較大。傳統(tǒng)的Crim inisi算法采用基于歐氏距離的匹配準(zhǔn)則，該準(zhǔn)則在匹配過(guò)程中僅以二者之間的空間距離作為衡量標(biāo)準(zhǔn)，并沒(méi)有考慮圖像的顏色分布、紋理變化等信息。Komodakis等人[2]提出運(yùn)用置信傳播算法解決圖像修復(fù)的全局最優(yōu)化問(wèn)題，該方法對(duì)結(jié)構(gòu)修復(fù)效果較差。Pritch等人[3]根據(jù)圖像已知信息的變化規(guī)律對(duì)圖像破損區(qū)域進(jìn)行修復(fù)。Xue等人[4]利用圖像的顏色梯度值構(gòu)造新的匹配準(zhǔn)則，從而提高了圖像塊的匹配度，但時(shí)間復(fù)雜度高。雷鳴等人[5]根據(jù)顏色比率梯度搜索最佳匹配塊，以減少誤匹配，但該算法時(shí)間復(fù)雜度較高。Wang等人[6]將匹配準(zhǔn)則與偏微分方程結(jié)合，并考慮圖像塊的相似性約束對(duì)修復(fù)造成的影響。彭坤楊等人[7]利用平均灰度值的思路，減少修復(fù)時(shí)間，但修復(fù)效果并不是很理想。Bugeau等人[8]提出以Bhattacharya距離約束歐氏距離，用兩種距離同時(shí)進(jìn)行匹配塊相似度衡量，在匹配準(zhǔn)則改進(jìn)方面取得了一定進(jìn)展。Zhou等人[9]將待修復(fù)塊與選取的多個(gè)匹配塊轉(zhuǎn)化為非負(fù)矩陣，利用非負(fù)矩陣因子化解求得填充信息。劉純[10]將目標(biāo)塊及匹配塊的紋理特征相似性引入匹配過(guò)程中，取得了較好的成果。張晴等人[11]提出以歐式距離為主，巴氏距離為輔的相似性度量方法，對(duì)圖像平滑紋理部分的修復(fù)效果較為明顯。馬爽等人[12]提出利用圖像塊關(guān)聯(lián)匹配修復(fù)算法實(shí)現(xiàn)對(duì)降采樣受損圖像的粗修復(fù)，該方法對(duì)包含漸變特征的自然圖像修復(fù)具有很好的視覺(jué)效果。王新年等人[13]結(jié)合幾何距離關(guān)系，采用多塊同時(shí)修復(fù)的策略，引入幾何距離修正因子確定各塊的最佳匹配塊，該方法提高了修復(fù)效率。Liang等人[14]使用中心像素映射的方法標(biāo)記最大連通成分并進(jìn)行片段檢測(cè)，以此來(lái)加快搜索匹配塊，實(shí)驗(yàn)結(jié)果表明該方法可節(jié)省90%的時(shí)間。李尊等人[15]提出基于蝙蝠算法的Crim inisi圖像修復(fù)算法，采用蝙蝠算法進(jìn)行最佳匹配塊的搜索，蝙蝠算法能將全局搜索和局部搜索高效地融合，且具有很好的適應(yīng)性和魯棒性，能夠降低錯(cuò)誤信息的累積。但是上述文獻(xiàn)都沒(méi)有很好地解決復(fù)雜紋理修復(fù)時(shí)的誤匹配、誤差累計(jì)等問(wèn)題。

本文針對(duì)復(fù)雜紋理的修復(fù)提出了基于馬爾科夫隨機(jī)場(chǎng)（Markov random field，MRF）的匹配塊選取準(zhǔn)則。馬爾科夫隨機(jī)場(chǎng)認(rèn)為待修復(fù)像素塊的信息只與其鄰域像素塊有關(guān)，不僅涵蓋了歐氏距離最小的傳統(tǒng)匹配準(zhǔn)則，而且考慮到了匹配塊的灰度統(tǒng)計(jì)特征，以條件概率描述圖像數(shù)據(jù)分布并用于修復(fù)，具有更高的準(zhǔn)確性，修復(fù)效果更佳。

2 Crim inisi算法及修復(fù)效果分析

2.1 Criminisi算法原理

Crim inisi算法是基于樣本的修復(fù)算法，可同時(shí)兼顧圖像紋理信息和結(jié)構(gòu)信息，并通過(guò)全圖搜索設(shè)定匹配準(zhǔn)則以尋找最佳匹配塊。Crim inisi算法修復(fù)過(guò)程主要由計(jì)算優(yōu)先權(quán)，搜索最佳匹配塊，復(fù)制更新3步組成。

步驟1計(jì)算待修復(fù)區(qū)域邊界上像素點(diǎn)的優(yōu)先權(quán)，由待修復(fù)像素塊的置信度及數(shù)據(jù)項(xiàng)得到。

優(yōu)先權(quán)：

置信度：

式（2）中，待修復(fù)區(qū)域邊界上像素點(diǎn) p的置信度C(p)為待修復(fù)塊中已知像素之和與待修復(fù)塊所含像素總數(shù)的比值；Size(Ψp)是待修復(fù)塊所含像素總數(shù)。數(shù)據(jù)項(xiàng)：

式（3）中，衡量像素點(diǎn) p處邊緣強(qiáng)度的數(shù)據(jù)項(xiàng)D(p)是待修復(fù)區(qū)域邊界上點(diǎn)p處的單位法向量np與等照度線向量的乘積；α是歸一化參數(shù)（一般對(duì)于灰度圖像α=255）；ε為一個(gè)極小的常數(shù)，避免D(p)為0。

選擇優(yōu)先權(quán)最高的像素塊作為待修復(fù)塊首先進(jìn)行修復(fù)。

步驟2根據(jù)待修復(fù)塊的已知信息在圖像已知區(qū)域內(nèi)按一定的匹配準(zhǔn)則尋找最佳匹配塊，經(jīng)典Crim inisi算法采用了基于歐氏距離的匹配準(zhǔn)則，即在已知區(qū)域中進(jìn)行遍歷搜索，計(jì)算灰度距離，與待修復(fù)塊歐氏距離最小的塊視為與其最匹配的塊，其中歐氏距離d(Ψp,Ψq)定義為待修復(fù)塊Ψp與匹配塊Ψq對(duì)應(yīng)像素點(diǎn)的灰度值平方和。

匹配準(zhǔn)則：

步驟3將最佳匹配塊復(fù)制到待修復(fù)塊對(duì)應(yīng)的位置上，更新待修復(fù)邊緣置信度與數(shù)據(jù)項(xiàng)。

復(fù)制更新：

以上3步不停地循環(huán)，直到圖像中所有的受損區(qū)域全部被修復(fù)為止。每次循環(huán)前都要重新計(jì)算新的邊界上各點(diǎn)的優(yōu)先權(quán)以確定下一個(gè)最先需要修復(fù)的目標(biāo)塊。

2.2 Criminisi算法修復(fù)效果分析

Crim inisi算法是基于樣本的修復(fù)算法，它最大的優(yōu)點(diǎn)就是能夠修復(fù)大范圍受損的圖像，這是通過(guò)將像素塊不斷地復(fù)制到待修復(fù)區(qū)域?qū)崿F(xiàn)的。Criminisi算法中對(duì)修復(fù)結(jié)果產(chǎn)生較大影響的是搜索最佳匹配塊這一步驟，修復(fù)時(shí)匹配塊的大小以及匹配準(zhǔn)則的選取都會(huì)對(duì)修復(fù)結(jié)果產(chǎn)生質(zhì)的影響。

修復(fù)時(shí)，修復(fù)塊尺寸越小，修復(fù)的連續(xù)性就越好，邊緣特征保持越好，人眼對(duì)于邊界的不連續(xù)性就越不敏感；修復(fù)塊尺寸越大，塊與塊的誤差就越大，邊界越不連續(xù)，結(jié)構(gòu)信息缺損越嚴(yán)重，人眼就越容易識(shí)別。但是當(dāng)匹配塊選取過(guò)小，如選取2×2大小的匹配塊時(shí)，其修復(fù)時(shí)間明顯增長(zhǎng)，修復(fù)效率大大下降。為同時(shí)兼顧修復(fù)精度與修復(fù)時(shí)間，本文選取3×3的匹配塊進(jìn)行修復(fù)。

修復(fù)時(shí)采用的匹配準(zhǔn)則不同，結(jié)果也大不相同。經(jīng)典Crim inisi算法采用基于歐氏距離的匹配準(zhǔn)則，其計(jì)算兩個(gè)圖像塊的空間距離，歐式距離值越小，圖像塊越相似。因?yàn)榛跉W氏距離的匹配準(zhǔn)則只考慮待修復(fù)塊與匹配塊之間對(duì)應(yīng)像素值的相似性,并沒(méi)有從整體上考慮待修復(fù)塊與周圍已知信息的一致性，所以該準(zhǔn)則易從平坦區(qū)域復(fù)制像素，在衡量位于平滑區(qū)域的圖像塊時(shí)具有優(yōu)勢(shì)，而在衡量位于紋理或含有結(jié)構(gòu)的圖像塊時(shí)存在不足[16]。若在圖像已知區(qū)域搜索到錯(cuò)誤的匹配塊而造成修復(fù)錯(cuò)誤時(shí)，此錯(cuò)誤會(huì)在后續(xù)的修復(fù)過(guò)程中進(jìn)一步擴(kuò)散，從而造成大面積的修復(fù)錯(cuò)誤。

如圖1所示，（a）～（f）均是從原圖中截取的圖像塊。從人類視覺(jué)感知的主觀角度評(píng)價(jià)，與圖（a）P0相似度最高的是圖（f）P5；采用客觀量化評(píng)價(jià)歐式距離方法衡量圖像塊（b）～（f）與圖像塊（a）之間的相似度可知，與圖1（a）P0最相似也即歐式距離最小的圖像塊卻是圖1（c）P2。因此，若在算法中僅采用歐式距離作為相似性評(píng)價(jià)指標(biāo)，必然引起匹配錯(cuò)誤。

Fig.1 Sim ilarity comparison of image blocks圖1 圖像塊的相似性比較

3 基于馬爾科夫隨機(jī)場(chǎng)的匹配塊選取準(zhǔn)則

馬爾科夫隨機(jī)場(chǎng)是一組關(guān)于馬爾科夫性質(zhì)隨機(jī)變量的全概率分布模型。20世紀(jì)70年代，MRF被用于圖像處理領(lǐng)域描述圖像本身所特有的空間相關(guān)性，并在圖像紋理分析、圖像邊緣檢測(cè)、圖像分割以及圖像恢復(fù)與重建等方面發(fā)揮了優(yōu)越性。本文利用MRF在圖像紋理方面的特性，將其作為Crim inisi算法的新匹配準(zhǔn)則，修復(fù)結(jié)果有了較大提高。

3.1 馬爾科夫隨機(jī)場(chǎng)原理

馬爾科夫性指當(dāng)一個(gè)隨機(jī)過(guò)程在給定現(xiàn)在以及過(guò)去所有狀態(tài)的情況下，其未來(lái)狀態(tài)的條件概率分布僅依賴于當(dāng)前狀態(tài)的值，與過(guò)去所有狀態(tài)無(wú)關(guān)[17]。

對(duì)于圖像中一個(gè)特定的點(diǎn)，該點(diǎn)的取值只依賴于該點(diǎn)鄰域像素點(diǎn)的取值，而與其他位置的像素情況無(wú)關(guān)。

如圖2所示，分別為像素X的一階鄰域系統(tǒng)、二階鄰域系統(tǒng)和高階鄰域系統(tǒng)。

Fig.2 Neighborhood system of pixelX圖2 像素X的鄰域系統(tǒng)

一幅圖像由一些區(qū)域組成，每一個(gè)區(qū)域都滿足馬爾科夫隨機(jī)場(chǎng)對(duì)“平穩(wěn)的自回歸過(guò)程”的描述?！捌椒€(wěn)的自回歸過(guò)程”即統(tǒng)計(jì)特性不隨時(shí)間的推移而改變，在圖像中指對(duì)于小區(qū)域圖像如3×3或5×5的像素塊來(lái)說(shuō)，每一塊的灰度值是均勻的。則利用待修復(fù)像素塊的一階鄰域、二階鄰域或高階鄰域信息即可估計(jì)待修復(fù)像素塊的近似值[18]。由于MRF對(duì)于高階鄰域的計(jì)算復(fù)雜度高，本文選取其一階鄰域?qū)Υ迯?fù)像素塊進(jìn)行估值。

3.2 MRF數(shù)學(xué)模型建立及求解

對(duì)待修復(fù)像素塊進(jìn)行估值，即是對(duì)其鄰域的最大后驗(yàn)概率進(jìn)行估計(jì)，待修復(fù)塊與其鄰域系統(tǒng)滿足Bayes條件概率：

式（7）中，X為待修復(fù)像素塊；Y為已知的圖像及X的鄰域系統(tǒng)；P(X=x|Y=y)為已知Y時(shí)關(guān)于X的后驗(yàn)概率；P(X=x)為先驗(yàn)概率。通過(guò)適當(dāng)?shù)剡x擇Y使P(X=x|Y=y)達(dá)到最大，此時(shí)對(duì)應(yīng)的X即為缺損部分的最佳估計(jì)值x?：

利用馬爾科夫隨機(jī)場(chǎng)模型對(duì)整幅數(shù)字圖像進(jìn)行數(shù)學(xué)建模，即：

式（9）中，δ2為圖像灰度方差；M表示圖像由M個(gè)區(qū)域組成；qm為每個(gè)區(qū)域的灰度均值；N1、N2表示圖像的長(zhǎng)寬值。

計(jì)算圖像先驗(yàn)概率：

式（10）中，T是一個(gè)溫度常數(shù)，最初用于模擬退火算法中，算法開(kāi)始賦予T一個(gè)較大的值，隨著算法迭代次數(shù)的增加T逐漸減小，在MRF隨機(jī)場(chǎng)模型中一般取值為1；是一個(gè)歸一化常數(shù)；U(X)稱為Gibbs能量函數(shù)，圖像的全局能量函數(shù)為：

式（11）中，Vp(xp)表示給一個(gè)像素分配一個(gè)標(biāo)號(hào)的似然能量；Vpq(xp,xq)表示兩個(gè)相鄰像素分配兩個(gè)標(biāo)號(hào)的先驗(yàn)?zāi)Ｐ湍芰浚?p,q)表示鄰域像素對(duì)；ε表示系統(tǒng)中的4鄰域像素對(duì)集合。

基于MRF的鄰域最大后驗(yàn)概率估計(jì)實(shí)際上相應(yīng)于最小化全局能量U(X)：

3.3 估計(jì)值與匹配塊相似性度量

因MRF估值得出的3×3像素塊的9個(gè)像素灰度值是相同的，若直接填充會(huì)產(chǎn)生嚴(yán)重的塊效應(yīng)現(xiàn)象，所以在估值完成后，在全局搜索3×3最佳匹配塊。搜索時(shí)以平均灰度值作為衡量標(biāo)準(zhǔn)，計(jì)算匹配塊的平均灰度值，若其值與估值差異越小，則表示它們?cè)狡ヅ?，取差異值最小的匹配塊作為最佳匹配塊，并將最佳匹配塊復(fù)制到待修復(fù)塊對(duì)應(yīng)的位置上。

4 算法步驟及實(shí)驗(yàn)結(jié)果分析

4.1 本文算法步驟

（1）讀入待修復(fù)圖像，二值化圖像以尋找待填充邊緣；

（2）初始化置信度與數(shù)據(jù)項(xiàng)值，計(jì)算優(yōu)先權(quán)，選擇優(yōu)先權(quán)最高的像素塊為待修復(fù)塊；

（3）利用MRF圖像模型對(duì)待修復(fù)塊估值x?；

（4）全局搜索平均灰度值xˉ與估值x?差異最小的匹配塊；

（5）將最佳匹配塊復(fù)制到待修復(fù)像素塊，更新填充邊緣置信度與數(shù)據(jù)項(xiàng)；

（6）不斷循環(huán)以上步驟，直至待修復(fù)像素塊全部收斂修復(fù)。

4.2 實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)在Windows平臺(tái)下利用M icrosoft Visual C++6.0中的開(kāi)源計(jì)算機(jī)視覺(jué)庫(kù)（open source computer vision library，OpenCV 1.0）進(jìn)行仿真實(shí)驗(yàn)。

本文設(shè)計(jì)簡(jiǎn)單紋理與復(fù)雜紋理共4組實(shí)驗(yàn)驗(yàn)證算法性能，采用峰值信噪比（peak signal to noise ratio，PSNR）、均方誤差（mean squared error，MSE）、結(jié)構(gòu)相似性（structural sim ilarity，SSIM）作為修復(fù)結(jié)果客觀評(píng)價(jià)指標(biāo)。PSNR值越大表示圖像質(zhì)量越好，MSE值越小表示修復(fù)圖像與參考圖像越相似，SSIM值越大表示修復(fù)圖像質(zhì)量越高。

對(duì)于簡(jiǎn)單紋理，選取Golf圖像進(jìn)行對(duì)比實(shí)驗(yàn)，復(fù)雜紋理則選取Bungee、Farmer、People等圖像進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果如圖3～圖6和表1～表4所示。

Table1 Objectiveevaluation ofGolf inpainting image表1 Golf圖像修復(fù)結(jié)果客觀評(píng)價(jià)

Table2 Objectiveevaluation of Bungee inpainting image表2 Bungee圖像修復(fù)結(jié)果客觀評(píng)價(jià)

圖3中，（a）與（b）分別為Golf原圖與待修復(fù)圖像；（c）與（d）分別是經(jīng)典Crim inisi修復(fù)結(jié)果與其局部放大圖；（e）與（f）分別是文獻(xiàn)[2]修復(fù)結(jié)果與其局部放大圖；（g）與（h）分別是文獻(xiàn)[8]修復(fù)結(jié)果與其局部放大圖；（i）與（j）分別為本文算法修復(fù)結(jié)果與其局部放大圖。就人眼直接觀察發(fā)現(xiàn)，Crim inisi和文獻(xiàn)[2]修復(fù)結(jié)果均存在著不同程度的錯(cuò)誤紋理堆積，誤匹配率較高。雖然通過(guò)對(duì)算法的改進(jìn)，文獻(xiàn)[8]與本文修復(fù)結(jié)果在人眼看來(lái)紋理均比較自然，但通過(guò)客觀評(píng)價(jià)發(fā)現(xiàn)，本文修復(fù)結(jié)果較文獻(xiàn)[8]修復(fù)結(jié)果MSE降低，PSNR略微提高。

Fig.3 Inpainting resultsofGolf image圖3 Golf圖像修復(fù)結(jié)果

Fig.4 Inpainting resultsof Bungee image圖4 Bungee圖像修復(fù)結(jié)果

Fig.5 Inpainting resultsof Farmer image圖5 Farmer圖像修復(fù)結(jié)果

Table3 Objectiveevaluation of Farmer inpainting image表3 Farm er圖像修復(fù)結(jié)果客觀評(píng)價(jià)

Table4 Objectiveevaluation of People inpainting image表4 Peop le圖像修復(fù)結(jié)果客觀評(píng)價(jià)

Fig.6 Inpainting resultsof People image圖6 Peop le圖像修復(fù)結(jié)果

圖4中，（a）與（b）分別為Bungee原圖與標(biāo)記后的待修復(fù)圖像；（c）是經(jīng)典Crim inisi修復(fù)結(jié)果，結(jié)構(gòu)斷裂，誤匹配嚴(yán)重；（d）為文獻(xiàn)[2]修復(fù)結(jié)果，較經(jīng)典Criminisi有了較大改善；（e）為文獻(xiàn)[13]修復(fù)結(jié)果，結(jié)果斷裂，存在誤匹配；（f）為文獻(xiàn)[8]修復(fù)結(jié)果，結(jié)構(gòu)基本修復(fù)，但仍然產(chǎn)生了匹配錯(cuò)誤；（g）為本文算法修復(fù)結(jié)果，在紋理匹配方面較之前算法有了明顯改善，但結(jié)構(gòu)線存在部分錯(cuò)位現(xiàn)象。

圖5與圖6分別是對(duì)Farmer圖和People圖的修復(fù)。從幾組對(duì)比實(shí)驗(yàn)可知，本文算法較經(jīng)典Crim inisi修復(fù)算法在修復(fù)結(jié)果上有了很大的改善，較文獻(xiàn)[2]與[13]改進(jìn)算法，本文修復(fù)結(jié)果精度更好，PSNR與SSIM值也明顯提高。對(duì)于文獻(xiàn)[8]，其引入Bhattacharya距離與原始SSD相乘，因?yàn)锽hattacharya距離可以衡量離散概率分布的相似性，它可以較好地將位于平滑區(qū)域的圖像塊和位于紋理區(qū)域的圖像塊分開(kāi)，所以對(duì)于簡(jiǎn)單紋理，本文算法與其修復(fù)結(jié)果較為相像。對(duì)于復(fù)雜紋理，由于MRF利用了圖像的先驗(yàn)知識(shí)，修復(fù)結(jié)果更符合圖像的整體分布，且不論從主觀上看還是用PSNR、MSE等客觀分析，本文所采用的MRF匹配準(zhǔn)則以場(chǎng)論來(lái)描述紋理分布都優(yōu)于Bhattacharya距離。

由SSIM值發(fā)現(xiàn)本文算法修復(fù)結(jié)果在結(jié)構(gòu)相似性分析上較文獻(xiàn)[8]略低，由圖可知，當(dāng)圖像中結(jié)構(gòu)信息較為復(fù)雜時(shí)，其修復(fù)出現(xiàn)輕微錯(cuò)位與模糊現(xiàn)象。在圖像修復(fù)中，圖像結(jié)構(gòu)邊緣應(yīng)優(yōu)先得到修復(fù)，但本文算法是對(duì)匹配準(zhǔn)則的進(jìn)一步改進(jìn)，并沒(méi)有對(duì)修復(fù)順序進(jìn)行約束，且MRF自身對(duì)紋理相關(guān)性更為敏感，對(duì)結(jié)構(gòu)信息復(fù)雜區(qū)域易出現(xiàn)誤匹配，故本文算法無(wú)法自動(dòng)識(shí)別和確定多個(gè)邊緣的修復(fù)順序，結(jié)構(gòu)相似性略低于文獻(xiàn)[8]。

分析圖7中數(shù)據(jù)可知，盡管本文算法與文獻(xiàn)[8]算法修復(fù)耗時(shí)相比平均增加了45.82%，但與經(jīng)典Criminisi對(duì)比仍減少了8.96%。綜合而言，雖然基于MRF匹配準(zhǔn)則的修復(fù)算法修復(fù)耗時(shí)有所增加，但其對(duì)復(fù)雜紋理提高了修復(fù)精度，獲得了更好的視覺(jué)效果。

Fig.7 Running time comparison圖7 修復(fù)耗時(shí)對(duì)比結(jié)果

5 總結(jié)

本文提出了一種基于MRF匹配準(zhǔn)則的Crim inisi數(shù)字圖像修復(fù)算法。本文算法以馬爾科夫隨機(jī)場(chǎng)替代歐氏距離匹配準(zhǔn)則，實(shí)驗(yàn)證明了這種方法與經(jīng)典Crim inisi算法的修復(fù)精度相比有很大提高，基本解決了圖像誤匹配現(xiàn)象。但該算法還存在著一些不足，如在提高修復(fù)精度的同時(shí)是以犧牲一定的速度為代價(jià)；且由于馬爾科夫隨機(jī)場(chǎng)本身只對(duì)紋理內(nèi)部信息較為敏感，本文算法僅對(duì)數(shù)字圖像紋理部分修復(fù)效果較好，對(duì)于較為復(fù)雜的圖像結(jié)構(gòu)線仍存在斷裂與錯(cuò)位問(wèn)題。這些不足將是今后研究的重點(diǎn)。

[1]CriminisiA,Perez P,Toyama K.Region filling and object removal by exemplar-based image inpainting[J].IEEE Transaction on Image Processing,2004,13(9):1200-1212.

[2]Komodakis N,Tziritas G.Image completion using efficient belief propagation via priority scheduling and dynam ic pruning[J].IEEE Transactions on Image Processing,2007,16(11):2649-2661.

[3]Pritch Y,Kav-Venaki E,Peleg S.Shift-map image editing[C]//Proceedings of the 12th IEEE International Conference on Computer Vision,Kyoto,Japan,Sep 29-Oct4,2009.Piscataway,USA:IEEE,2009:151-158.

[4]Xue Yanbing,Zhang Hua,Wang Fayu,etal.Exemplar-based image completion using color ratio gradient[C]//Proceedings of the 1st Congress on Image and Signal Processing,Sanya,China,May 27-30,2008.Piscataway,USA:IEEE,2008:569-572.

[5]Lei M ing,Wang Chundong,Xue Yanbing.A new exemplar based image completing method[J].Journal of Optoelectronics·Laser,2009,20(5):677-680.

[6]Wang Yuxiong,Zhang Yujin.Image inpainting viaweighted sparse non-negativematrix factorization[C]//Proceedings of the 18th International Conference on Image Processing,Brussels,Belgium,Sep 11-14,2011.Piscataway,USA:IEEE,2011:3409-3412.

[7]Peng Kunyang,Dong Lanfang.A fast image inpainting algorithm based on average gray value[J].Journal of Image and Graphics,2010,15(1):50-55.

[8]Bugeau A,Bertalmío M,Caselles V,etal.A comprehensive framework for image inpainting[J].IEEE Transactions on Image Processing,2010,19(10):2634-2645.

[9]Zhou Yatong,Li Lin,Xia Kewen.Research onweighted priority of exemplar-based image inpainting[J].Journalof Electronics,2012,29(1):166-170.

[10]Liu Chun.The research on fast image inpainting algorithms[D].Changsha:Hunan University,2012.

[11]Zhang Qing,Lin Jiajun,Liu Yunxiang.Image inpainting algorithm using improved similaritymetrics[J].Journalof Shanghai Instituteof Technology:NaturalScience,2014,14(3):228-232.

[12]Ma Shuang,Tan Yuanpeng,Xu Gang.Image completion based on fusion of patch associatedmatching and low-rank matrix super resolution[J].Journal of Computer-Aided Design&ComputerGraphics,2015,27(2):271-278.

[13]Wang Xinnian,Wang Zhe,Wang Yan.Improved Criminisi algorithm based on geometry distance[J].Computer Engineering and Design,2015,36(7):1835-1839.

[14]Liang Zaoshan,Yang Gaobo,Ding Xiangling,etal.An efficient forgery detection algorithm for object removal by exemplar-based image inpainting[J].Journalof VisualCommunication&Image Representation,2015,30(C):75-85.

[15]Li Zun,Wu Jin,Liu Jin.Crim inisi image restoration algorithm for object removal[J].Infrared Technology,2016,38(1):28-32.

[16]Shen Jianbing，Jin Xiaogang，Zhou Chuan.Gradient based image completion by solving the Poisson equation[J].Computersand Graphics,2007,31(1):119-156.

[17]Ru?i?T,Pi?urica A,PhilipsW.Markov random field based image inpainting w ith context-aware label selection[C]//Proceedings of the 19th International Conference on Image Processing,Lake Buena Vista,USA,Sep 30-Oct 3,2012.Piscataway,USA:IEEE,2012:1733-1736.

[18]Yang Xiaoping,Wang Shuwen.Dunhuangmural inpainting based on Markov random field sampling[J].Journal of ComputerApplications,2010,30(7):1835-1837.

附中文參考文獻(xiàn)：

[5]雷鳴,王春東,薛彥兵.一種新的樣本塊圖像修補(bǔ)方法[J].光電子·激光,2009,20(5):677-680.

[7]彭坤楊,董蘭芳.一種基于圖像平均灰度值的快速圖像修復(fù)算法[J].中國(guó)圖象圖形學(xué)報(bào),2010,15(1):50-55.

[10]劉純.快速圖像修復(fù)算法研究[D].長(zhǎng)沙:湖南大學(xué),2012.

[11]張晴,林家駿,劉云翔.改進(jìn)相似性度量準(zhǔn)則的圖像修復(fù)算法[J].上海應(yīng)用技術(shù)學(xué)院學(xué)報(bào):自然科學(xué)版,2014,14(3):228-232.

[12]馬爽,談元鵬,許剛.塊關(guān)聯(lián)匹配與低秩矩陣超分辨融合的圖像修復(fù)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2015,27(2):271-278.

[13]王新年,王哲,王演.基于幾何距離的Crim inisi圖像修復(fù)算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2015,36(7):1835-1839.

[15]李尊,吳謹(jǐn),劉勁.目標(biāo)移除的Criminisi圖像修復(fù)算法[J].紅外技術(shù),2016,38(1):28-32.

[18]楊筱平,王書(shū)文.基于馬爾可夫采樣的敦煌壁畫(huà)修復(fù)[J].計(jì)算機(jī)應(yīng)用,2010,30(7):1835-1837.

ZHAO Nawas born in 1992.She is an M.S.candidate at School of Information and Control Engineering,Xi'an University of Architecture and Technology.Her research interests include digital image inpainting and digital image processing,etc.

趙娜（1992—），女，陜西延安人，西安建筑科技大學(xué)信息與控制工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)字圖像修復(fù)，數(shù)字圖像處理等。

王慧琴（1970—），女，山西長(zhǎng)治人，2002年于西安交通大學(xué)獲得博士學(xué)位，現(xiàn)為西安建筑科技大學(xué)教授、博士生導(dǎo)師，CCF會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)字圖像處理，多媒體通信，數(shù)字建筑，信息安全等。

WU Mengwas born in 1979.She is a lecturer at School of Information and Control Engineering,Xi'an University of Architecture and Technology.Her research interests include digital image processing andmanagement information systems,etc.

吳萌（1979—），女，陜西韓城人，西安建筑科技大學(xué)信息與控制工程學(xué)院講師，主要研究領(lǐng)域?yàn)閿?shù)字圖像處理，管理信息系統(tǒng)等。

Crim inisi Digital Inpainting Algorithm Based on M arkov Random Field M atching Criterion*

ZHAO Na,WANG Huiqin+,WUMeng
Schoolof Information and Control Engineering,Xi'an University of Architecture and Technology,Xi'an 710055,China

The accuracy of traditional image exemplar-inpainting algorithm is lower.This paper proposesa new Crim inisi digital inpainting algorithm based on Markov random field(MRF)matching criterion.The MRF becomes new matching criterion instead of Euclidean distance.Before searching the bestmatching patch,the image texture model based on MRF is built.Then the global energy of the image is calculated to estimate the value of inpainting patch.Finally,the bestmatching patch is searched in order to achieve the globaloptimum.The experimental results show that the proposed algorithm achieves impressive inpainted results,the texture errormatching rate is decreased,and the inpainting accuracy is improved.

Crim inisi;Markov random field(MRF);matching criterion;image inpainting

in was born in 1970.She

the Ph.D.degree in engineering from Xi'an Jiaotong University in 2002.Now she is a professor and Ph.D.supervisor at Xi'an University of Architecture and Technology,and the member of CCF.Her research interests include digital image processing,multimedia communication,digitalarchitectureand information safety,etc.

A

：TN911.73

*The Scientific Research Foundation for the Returned Overseas Chinese Scholars,State Education M inistry of China under Grant No.K05055(教育部留學(xué)回國(guó)人員科研啟動(dòng)基金);the Natural Science Basic Research Plan of Shaanxi Province under Grant No.2016JM 6079(陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目);the Science and Technology Projectof Beilin District in 2016 under Grant No.GX1605(2016年碑林區(qū)科技計(jì)劃項(xiàng)目).

Received 2016-04,Accepted 2016-09.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-09-08,http://www.cnki.net/kcms/detail/11.5602.TP.20160908.1045.006.htm l