采用順序修復(fù)的樣本例圖像修復(fù)算法①

李旭峰,王 靜,王國東,劉紅敏,王志衡

1(河南理工大學(xué) 電氣工程與自動化學(xué)院,焦作 454150)2(河南理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,焦作 454150)

采用順序修復(fù)的樣本例圖像修復(fù)算法①

李旭峰1,王 靜2,王國東1,劉紅敏2,王志衡2

1(河南理工大學(xué) 電氣工程與自動化學(xué)院,焦作 454150)2(河南理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,焦作 454150)

本文提出了一種采用順序修復(fù)的樣本例圖像修復(fù)算法,該方法在原Criminisi經(jīng)典圖像修復(fù)算法的基礎(chǔ)上對修復(fù)順序進(jìn)行新的嘗試.原Criminisi經(jīng)典算法的修復(fù)順序通過計算優(yōu)先級得出,隨著修復(fù)的深入優(yōu)先級逐漸趨近于0,導(dǎo)致算法失去作用.為解決該問題,本文采用順序修復(fù)的方法來代替優(yōu)先級決定順序,避免出現(xiàn)算法失去作用的情況;同時本文提出的“倒L”型樣本模板來增強(qiáng)結(jié)構(gòu)的傳播能力、提高匹配的正確率.實(shí)驗(yàn)結(jié)果證明,本文的修復(fù)算法相對Criminisi算法具有優(yōu)勢并取得很好的修復(fù)結(jié)果.

順序修復(fù);圖像修復(fù);樣本塊;匹配

圖像修復(fù)方法主要是結(jié)合退化圖像中待修復(fù)區(qū)域周圍的信息復(fù)原待修復(fù)區(qū)域的未知圖像信息,達(dá)到人的視覺心理要求[1].圖像修復(fù)技術(shù)在恢復(fù)圖片中丟失信息、去除圖片中不需要的部分及隱藏視頻錯誤信息等問題上得到廣泛應(yīng)用[2].Chan T F 等[3]通過計算偏微分方程實(shí)現(xiàn)圖像信息的傳播,在TV模型[4]的基礎(chǔ)上建立曲率驅(qū)動擴(kuò)散(Curvature Driven Diffusions,CDD)模型進(jìn)行修復(fù),Chen Y等[5]利用拉普拉斯變換來修復(fù)線性結(jié)構(gòu)和非線性結(jié)構(gòu)以及它們的混合信息.Florinabel等[6]根據(jù)視覺效果的不同程度進(jìn)行改進(jìn),取得很好的效果.Xu[7]等利用樣本例的稀疏性對圖像信息進(jìn)行導(dǎo)修復(fù).Criminisi等[8]提出的樣本塊圖像修復(fù)算法,其特點(diǎn)是能同時修復(fù)紋理和結(jié)構(gòu)信息.通過計算待修復(fù)區(qū)域邊緣點(diǎn)優(yōu)先級順序,確定邊緣上待修復(fù)塊的修復(fù)順序,然后根據(jù)該順序進(jìn)行匹配修復(fù).在該算法基礎(chǔ)上,王靜等[9]對其進(jìn)行了修改,改善了該方法匹配錯誤率較高的問題;T Ru?i?等[10]利用馬爾科夫隨機(jī)場通過感知待修復(fù)區(qū)域周圍信息進(jìn)行修復(fù).李旭峰等[11]提出了特征優(yōu)先的塊匹配圖像算法,加強(qiáng)了結(jié)構(gòu)傳播能力;任澎等[12]提出利用紋理和邊緣特征的改進(jìn)算法,同時又提出了將紋理和邊緣特征相結(jié)合的圖像修復(fù)方法[13].

1 Criminis算法及其問題

1.1 算法介紹

Criminisi經(jīng)典算法[4]以圖像塊為操作對象將圖像中已知區(qū)域的信息傳遞到未知區(qū)域,如圖1所示,其中I為整個圖像,代表已知區(qū)域,代表未知區(qū)域.其算法分為兩個步驟:1)計算待填充邊緣的優(yōu)先級順序,尋找優(yōu)先級最高的塊作為待填充塊;2)將待填充塊中的已知部分與圖像中已知區(qū)域信息進(jìn)行匹配,找出最合適的塊作為填充塊,并將填充塊填充在待填充位置.

圖1 Criminisi算法修復(fù)原理

1.2 算法問題

由公式(1)可知優(yōu)先級為置信項(xiàng)和數(shù)據(jù)項(xiàng)的乘積,在公式(2)中可以看出,隨著修復(fù)的深入,分子的值會越來越小,而是一個恒定值,因此也會越來越小,逐漸的逼近0值,最終導(dǎo)致優(yōu)先級也趨近為0,使算法逐漸失去應(yīng)有作用.此問題嚴(yán)重影響Criminisi算法的修復(fù)效果.

2 本文算法

2.1 算法基礎(chǔ)

針對上述問題,本文采用順序修復(fù)圖像的方式來避免該問題的出現(xiàn),同時取得較好的修復(fù)結(jié)果.本方法中掃描塊為一個邊長7個像素的正方形塊,當(dāng)掃描塊和修復(fù)區(qū)域重合時,稱為待匹配塊.如圖2所示,為待匹配塊,為最佳匹配塊,為待填充塊,為最佳填充塊,為待匹配塊的基礎(chǔ)匹配區(qū)域,為匹配塊的實(shí)際匹配區(qū)域.待匹配塊的基礎(chǔ)匹配區(qū)域和待修復(fù)區(qū)域不重疊,即?=0,保證修復(fù)過程中基礎(chǔ)匹配區(qū)域能為匹配塊提供足夠的信息支撐.

圖2 本文算法修復(fù)原理

1.2 算法步驟

修復(fù)過程包括以下步驟:

1)建立掃描塊,以掃描塊為基本單位從上往下、從左往右依次對待修復(fù)圖像進(jìn)行掃描,直到掃描塊遇到待修復(fù)區(qū)域;

4)如圖2所示,計算每個候選塊中填充部分和待填充塊兩個相鄰的像素塊的相似度所述相似度同樣由SSD距離公式計算得出,計算出的SSD距離值越大說明相似度越小,值越小相似度越大;

5)由第4步可知,每一個候選塊有兩個相似度值,這里取較小的相似度作為該候選塊的相似度值,同時比較所有候選塊的相似度值,最小的候選塊作為最佳待填充塊填充到待填充位置

6)重復(fù)執(zhí)行以上步驟,直到圖像被修復(fù)完成.

2.3 算法分析

本算法使用掃描塊從左往右從上往下依次對圖像進(jìn)行掃描,找到待填充區(qū)域時依次對其修復(fù).通過該修復(fù)順序,避開優(yōu)先級計算方法,同時避開優(yōu)先級計算時出現(xiàn)的算法失效問題.本算法中采用的基礎(chǔ)匹配區(qū)域總位于已知信息的區(qū)域并參與匹配計算,其形狀為“倒 L”形,如圖.該形狀的優(yōu)點(diǎn)是,匹配時同時計算了待填充位置上方和左方的圖像信息,使匹配信息更全面.在以上基礎(chǔ)上,步驟4)和步驟5)選擇其中一個方向的塊進(jìn)行相似度計算,進(jìn)一步的保證填充的信息在其中一個方向上具有更加平緩自然的過渡,保證了圖像修復(fù)結(jié)果的自然、不突兀.本文通過實(shí)驗(yàn)結(jié)果來證明本文算法的作用及優(yōu)勢.

3 實(shí)驗(yàn)結(jié)果及分析

本章將文獻(xiàn)[8]算法、文獻(xiàn)[9]算法和本文算法修復(fù)結(jié)果進(jìn)行比較,圖4和圖5為本文算法和文獻(xiàn)[8]、文獻(xiàn)[9]算法修復(fù)結(jié)果對比圖,文章同時從定量和觀感兩方面對各個算法修復(fù)結(jié)果進(jìn)行分析和評價.

3.1 定量分析

本文入PSNR(峰值信噪比)對修復(fù)結(jié)果進(jìn)行定量分析.PSNR是最大值信號和背景噪音之間的比率,PSNR的單位為dB,為衡量經(jīng)過處理后的影像品質(zhì),通常會參考PSNR值來認(rèn)定圖像處理程序是否令人滿意.PSNR值越大,就代表失真越少,即圖像修復(fù)修復(fù)效果越好.表1所示為圖4和圖5中各個算法修復(fù)結(jié)果的PSNR.從表中可以看出兩幅圖中三個算法修復(fù)結(jié)果的PSNR 中,本文算法都高于文獻(xiàn)[8]和文獻(xiàn)[9].數(shù)據(jù)顯示本文算法的PSNR最大,說明本文算法修復(fù)結(jié)果圖像質(zhì)量相對更高,即本文算法更好的修復(fù)效果.

圖3 “倒 L”形修復(fù)模板

表1 算法修復(fù)結(jié)果的 PSNR (dB)

3.2 感觀分析

感觀方面,圖 4 中(a)為原圖像,(b)為待處理圖像,(c)為文獻(xiàn)[8]算法處理結(jié)果,(d)為文獻(xiàn)[9]算法處理結(jié)果,(e)為本文算法處理結(jié)果.圖(c)中可以明顯看到屋頂部分沒有被完全修復(fù)成功,屋頂中間缺失一小塊,其原因是該算法在修復(fù)到一定深度之后算法失去作用,無法控制填充的內(nèi)容,導(dǎo)致的修復(fù)結(jié)果不完善;同時,植物向水中延伸的部分也不符合實(shí)際規(guī)律,除算法作用逐漸減小外,直線傳播能力弱也是一個重要的原因.圖(d)中,屋頂結(jié)構(gòu)部分被修復(fù)完整,但水面也出現(xiàn)很多多余的樹木紋理.圖(e)中,山上樹木紋理部分處理結(jié)果和圖(c)中相當(dāng),對房屋屋頂?shù)奶幚硎滞暾?沒有出現(xiàn)屋頂部分缺失的情況,這說明本文算法不會隨著修復(fù)深度而失效;岸邊植物的延伸也被很好的限制住,沒有無規(guī)則的延伸到水中,即本文算法具有很好的直線傳播能力.

圖4 蹦極人物修復(fù)結(jié)果

圖5 反光鏡修復(fù)結(jié)果

如圖 5,(a)為原始圖像,(b)為待修復(fù)圖像,(c)為文獻(xiàn)[8]算法修復(fù)結(jié)果,(d)為文獻(xiàn)[9]算法修復(fù)結(jié)果,(e)為本文算法修復(fù)結(jié)果.該圖像中包含樹葉紋理和欄桿直線結(jié)構(gòu).針對該圖片的修復(fù)結(jié)果除要求樹葉紋理自然,直線結(jié)構(gòu)傳播無差錯之外,還需要保證修復(fù)結(jié)果中沒有不符合常理的多余傳播.在圖(c)中欄桿得到很好的傳播,但是欄桿上面出現(xiàn)多余的欄桿結(jié)構(gòu),這種情況就屬于錯誤傳播,其原因是算法隨修復(fù)深度逐漸失去作用;圖(d)出現(xiàn)了和(c)中同樣的情況;圖(e)中樹葉紋理部分傳播合理,也完成欄桿的直線傳播,但是欄桿的銜接性稍差,這也是順序修復(fù)算法的不足之處.圖(c)和(e)中其余馬路部分都得到很好的修復(fù).本文算法優(yōu)勢得到進(jìn)一步體現(xiàn).

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

本文介紹了Criminisi算法及其問題,同時提出來新的算法來解決該問題.本方法采用的順序修復(fù)方法避免優(yōu)先級計算產(chǎn)生的算法作用逐漸減弱的特性,同時保證待匹配塊基礎(chǔ)匹配區(qū)域的完整,待匹配塊基礎(chǔ)匹配區(qū)域?yàn)椤暗筁”形狀,該形狀的即能配合順序修復(fù)又充分利用填充位置上方和右方的已知信息,使圖像修復(fù)的正確率得到有效的提升.通過對比兩者的實(shí)現(xiàn)過程和實(shí)驗(yàn)結(jié)果可以看出,本文方法在處理圖像紋理方面和Criminisi經(jīng)典算法具有相同的能力,但具有更強(qiáng)的結(jié)構(gòu)傳播能力;本文算法依然存在著修復(fù)范圍小等問題,未來希望針對該問題對本算法進(jìn)行更深入的研究.

1 Guillemot C,Le Meur O.Image inpainting:Overview and recent advances.IEEE Signal Processing Magazine,2014,31(1):127–144.[doi:10.1109/MSP.2013.2273004]

2 張紅英,彭啟琮.數(shù)字圖像修復(fù)技術(shù)綜述.中國圖象圖形學(xué)報,2007,12(1):1–10.[doi:10.11834/jig.20070102]

3 Chan TF,Shen JH.Nontexture inpainting by curvaturedriven diffusions.Journal of Visual Communication and Image Representation,2001,12(4):436–449.[doi:10.1006/jvci.2001.0487]

4 Chan TF,Shen JH.Mathematical models for local nontexture inpaintings.SIAM Journal on Applied Mathematics,2001,62(3):1019–1043.

5 Chen YJ,Ranftl R,Pock T.A bi-level view of inpaintingbased image compression.Computer Vision Winter Workshop.Czech Republic.2014.

6 Florinabel DJ,Juliet SE,Sadasivam V,et al.Combined frequency and spatial domain-based patch propagation for image completion.Computers &Graphics,2011,35(6):1051–1062.

7 Xu ZB,Sun J.Image inpainting by patch propagation using patch sparsity.IEEE Trans.on Image Processing,2010,19(5):1153–1165.[doi:10.1109/TIP.2010.2042098]

8 Criminisi A,Perez P,Toyama K.Region filling and object removal by exemplar-based image inpainting.IEEE Trans.Image Processing,2004,13(9):1200–1212.[doi:10.1109/TIP.2004.833105]

9 Wang J,Lu K,Pan DR,et al.Robust object removal with an exemplar-based Image Inpainting approach.Neurocomputing,2014,123:150–155.[doi:10.1016/j.neucom.2013.06.022]

10 Ru?i? T,Pi?urica A.Context-aware patch-based image inpainting using Markov random field modeling.IEEE Trans.Image Processing,2015,24(1):444–456.[doi:10.1109/TIP.2014.2372479]

11 李旭峰,王靜,劉紅敏,等.特征優(yōu)先塊匹配圖像修復(fù)算法.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2016,28(7):1131–1137.

12 任澍,唐向宏,康佳倫.利用紋理和邊緣特征的 Criminisi改進(jìn)算法.中國圖象圖形學(xué)報,2012,17(9):1085–1091.[doi:10.11834/jig.20120906]

13 任澎,唐向宏,康佳倫.紋理和邊緣特征相結(jié)合的圖像修復(fù)算法.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2013,25(11):1682–1693.

Image Inpainting Algorithm Base on Sequential Repaired Exemplar

LI Xu-Feng1,WANG Jing2,WANG Guo-Dong1,LIU Hong-Min2,WANG Zhi-Heng2

1(College of Electrical Engineering and Automation,Henan Polytechnic University,Jiaozuo 454150,China)2(College of Computer Science and Technology,Henan Polytechnic University,Jiaozuo 454150,China)

This paper proposes a novel image inpainting algorithm based on exemplar repaired in a sequential manner.This method makes a new experiment on inpainting order of Criminisi classical algorithm.The inpainting order of the classical algorithm is obtained by calculating the priority.But the priority is tending to 0 with the sustained inpainting.As a result,the algorithm will fail and produce error inpainting results.In order to solve this problem,we replace the priority determined order with a sequential manner,which can keep the algorithm working all the time.Moreover,we propose a novel exemplar pattern like an inverted L.The pattern in our method can help to enhance the ability of structure propagation and improve correction rate of patch matching.Experimental results prove that the novel algorithm can achieve better visual effects.

sequential;image inpainting;exemplar;match

李旭峰,王靜,王國東,劉紅敏,王志衡.采用順序修復(fù)的樣本例圖像修復(fù)算法.計算機(jī)系統(tǒng)應(yīng)用,2017,26(9):219–223.http://www.c-sa.org.cn/1003-3254/5948.html

①基金項(xiàng)后:國家自然科學(xué)基金(61401150,61472119,61572173);河南理工大學(xué)博士基金(B2013-039);河南理工大學(xué)創(chuàng)新型科研團(tuán)隊(duì)計劃(T2014-3)

2016-12-22;采用時間:2017-01-18