Criminisi圖像修復算法的優化

王文豪++周靜波++高尚兵++嚴云洋

摘 要： 針對Criminisi算法在修復時會出現結構斷裂和誤匹配問題，在原有算法基礎上提出一些新的改進思想，改進優先級函數的計算方法，將優先級函數表示為數據項、置信度項和鄰域相關性項的加權和，以保證圖像結構信息的連續性。設計一種樣本塊大小可變的算法，以增強局部協調性和邊界的平滑性。改進模板間相似性度量方法，融入顏色直方圖，以提高模板匹配的準確性。實驗結果表明，該方法能夠彌補Criminisi算法的不足，獲得較好的視覺效果，提高圖像的修復質量。

關鍵詞： Criminisi算法； 圖像修復； 可變大小樣本塊； 模塊相似性度量； 顏色直方圖

中圖分類號： TN911.73?34； TP391 文獻標識碼： A 文章編號： 1004?373X（2017）11?0053?05

Optimization of Criminisi algorithm for image inpainting

WANG Wenhao， ZHOU Jingbo， GAO Shangbing， YAN Yunyang

（Huaiyin Institute of Technology， Huaian 223001， China）

Abstract： Since the Criminisi algorithm has the problems of structure fracture and wrong matching while making image inpainting， some new improvement thoughts are proposed on the basis of the original algorithm， with which the calculation method of the priority function is improved， and the priority function is represented as the weighted sum of the data item， confidence coefficient item and neighborhood correlation term to ensure the information continuity of the image structure. An algorithm of variable?size exemplar block was designed to enhance the local harmony and boundary smoothness. The similarity measure method for templates was improved， and integrated with color histogram to improve the accuracy of template matching. The experimental results show that the method can make up the deficiencies of Criminisi algorithm， obtain better visual effect， and improve the quality of image inpainting.

Keywords： Criminisi algorithm； image inpainting； variable?size exemplar block； module similarity measure； color histogram

0 引 言

圖像修復技術主要利用圖像受損區域的鄰域信息對受損區域按照一定的規則進行填充，使修復后的圖像盡可能地與原圖保持一致，具有較好的視覺效果。其在文物保護、藝術品修補、影視特技、多余物體消除和虛擬現實等領域中具有廣泛的實際應用價值，現已成為圖像處理和計算機視覺領域的研究熱點[1?2]。

目前圖像修復算法可以分為兩類：一類是基于結構的方法[3]，這類方法主要是通過計算等照度的方向，將受損區域周圍已知信息平滑地傳進受損區域內部完成圖像的修復，其較為經典的模型有BSCB[4]，TV（Total Variation）[5]，CDD（Curvature?Driven Diffusions）[6]三個模型，這類算法對修復局部狹長的區域有較好的效果，但對大面積破損和紋理豐富的圖像，修復效果較差；另一類是基于紋理合成的方法[7]，這類算法主要通過在受損區域選擇合適的紋理塊，然后從完好區域尋找與之最相似的塊代替該塊，這類算法中最具有代表性的是Criminisi等人提出的基于樣本塊修復算法[8]，在修復大面積受損區域時可以獲得較好的修復效果，但該算法在搜索最優修復塊和最優匹配塊時存在一些不足[9]。于是研究者們提出了一些改進算法：文獻[10]提出一種基于樣本塊大小的自適應圖像修復算法，根據圖像的梯度信息自適應地調整樣本塊的大小，但極易出現結構不連續現象。文獻[11]將優先級函數中的置信度修改成指數函數形式，以避免其隨著修復過程的進行而迅速下降為零，從而影響修復順序，但該方法修復的圖像存在邊界效應。文獻[12]將優先級函數表示為數據項和置信度的加權和，改善修復順序，但在修復邊緣處有錯層現象。文獻[13]采用局部搜索策略，縮小樣本塊的搜索范圍，提高算法運行速度，但匹配不夠準確。文獻[14]提出一種基于結構傳播的圖像修復算法，取得了較好的修復效果，但算法時間復雜度較高。

上述文獻沒有很好地解決結構連續性和誤匹配問題。本文在Criminisi算法的基礎上加入一些有意義的改進，通過增加鄰域相關性項改進優先級計算方法，使得修復順序更加可靠；利用鄰域相關信息自動調整樣本塊大小，以適應不同紋理和結構的修復；在模塊相似性計算中融入顏色直方圖，提高匹配的準確性。實驗表明該方法能取得較好的修復效果。

3 修復算法

綜合第2節講述的改進方法，最終的改進算法流程如下：

（1） 讀入受損圖像并進行預處理，確定修復邊界

（2） 采用9×9的模板，利用本文改進的優先級計算方法計算邊界上像素的優先級，找到優先級最高的像素點；

（3） 利用本文提出的樣本塊大小可變算法確定以點為中心的樣本塊的最大尺寸，若該尺寸大于13，記錄其邊界；

（4） 按照本文改進的模板相似性度量準則搜索最優匹配塊；

（5） 將最優模塊的像素信息復制到相應的待修復模塊中的未知部分，并更新置信度和優先權等信息；

（6） 若邊界不為空，轉到第（2）步繼續執行；否則，轉到下一步；

（7） 根據第（3）步記錄的較大模塊的邊界，對其采用FMM算法再進行一次快速修復，以消除邊界效應。

4 仿真實驗結果與分析

為了驗證算法的有效性，本文在內存2 GB、主頻2.93 GHz的雙核奔騰處理器上，使用VC++和OpenCV編程進行仿真實驗，并與Criminisi，文獻[12，14]修復結果比較，實驗中，文中的一些參數由實驗經驗得出，其取值分別為：。

實驗1： 修復效果比較

圖8和圖9是兩組實驗結果比較圖。圖8為“十”字型的待修復區域，結構信息較為復雜。圖8（c）為Criminisi算法修復結果，可以看出，有明顯的裂縫和錯誤匹配情形，這主要是由修復順序出現偏差和匹配方式單一導致的。圖8（d）為文獻[12]的修復結果，該算法雖然改進了優先級的計算方式，但由于沒有考慮待修復區域周邊的信息和圖像特征信息，以致于還出現了斷裂和錯誤匹配；圖8（e）為文獻[14]修復結果，效果較好，但時間復雜度較高。圖8（f）為本文方法的修復效果，可以看出，雖然存在少許錯誤匹配，豎著的窗框上也存在修復痕跡，但總體效果而言比圖8（c）、圖8（d）的修復效果要好，與圖8（f）相差無幾。這主要是因為該算法能夠根據待修復區域周邊的信息，自動調整樣本塊的大小、改變修復順序，在模板匹配時，考慮了更多的因素。

圖9是去除較大物體之后的背景修復，該圖的紋理和非結構都較復雜，本文的修復效果如圖9（f）所示，沒有出現紋理不和諧的地方，而Criminisi算法修復的結果在草地上出現欄桿的一部分，文獻[12]修復的結果有明顯的修復痕跡，文獻[14]修復的結果與本文相當。

實驗2： 算法運行時間比較

表1是各個算法在上述實驗結果耗費的時間對比。從表1中可以看出，文獻[12]與Criminisi算法運行時間相差無幾，這是因為文獻[12]只是將Criminisi算法的優先權的計算方式由乘法改為加法。本文方法由于在確定樣本塊大小、優先極計算和樣本塊匹配時需要花費額外的時間，因此時間復雜度比Criminisi算法高一些，然而修復質量卻有較大提高。文獻[14]雖然修復效果較好，然而其時間復雜度太高。

從以上兩組實驗比較結果可以看出，不論是修復受損區域，還是去除較大的多余目標，改進算法比Criminisi算法具有更好的修復效果，但算法耗費的時間比Criminisi算法多。

5 結 語

本文在分析Criminisi算法的基礎上，針對其存在的缺陷，通過引入待修復塊周邊像素的信息和顏色直方圖，對Criminisi算法的優先級計算方式、樣本塊大小和相似性度量等方面進行了一些有意義的改進，實驗結果表明，本文的方法比Criminisi算法可以獲得更好的視覺效果，但對于具有曲線邊界的物體，修復效果還有待提高。

參考文獻

[1] 韓明珠，郭樹旭，臧玲玲，等.基于樣本塊的圖像修復改進算法[J].計算機工程與應用，2015，51（16）：192?194.

[2] 翟東海，肖杰，魚江，等.基于自適應模板的圖像修復算法[J].計算機應用，2013，33（10）：2891?2894.

[3] CHAN T， SHEN J. Mathematical models for local non?texture inpaintings [J]. SIAM journal on applied mathematics， 2001， 62（3）： 1019?1043.

[4] BERTALMIO M， SAPIRO G， CASELLES V， et al. Image inpainting [C]// Proceedings of 2000 ACM Computer Graphics， Annual Conference Series. New Orleans： ACM， 2000： 417?424.

[5] CHAN T F， SHEN J H. Mathematical models for local non?texture inpainting [J]. Journal of applied mathematics， 2001， 62（3）： 1019?1043.

[6] CHAN T F， SHEN J H. Non?texture inpainting by curvature?driven diffusions （CDD） [J]. Journal of visual communication and image representation， 2001， 12（4）： 436?449.

[7] 任澍，唐向宏，康佳倫.紋理和邊緣特征相結合的圖像修復算法[J].計算機輔助設計與圖形學學報，2013，25（11）：1682?1693.

[8] CRIMINISI A， PEREZ P， TOYAMA K. Region filling and object removal by exemplar?based image inpainting [J]. IEEE transactions on image processing， 2004， 13（9）： 1200?1212.

[9] 李愛菊，鈕文良.基于改進Criminisi算法的圖像修復[J].計算機工程與應用，2014，50（18）：167?170.

[10] 孟春芝，何凱，焦青蘭.自適應樣本塊大小的圖像修復方法[J].中國圖象圖形學報，2012，17（3）：237?241.

[11] 劉業妃，王福龍，奚祥艷，等.改進的Criminisi圖像修復算法[J].小型微型計算機系統，2014，35（12）：2754?2758.

[12] 李俊栢，黃文清，黃牧，等.改進的Criminisi圖像修復算法[J].工業控制計算機，2014，27（7）：127?129.

[13] ZHOU H， ZHANG J. Adaptive patch size determination for patch?based image completion [C]// Proceedings of 2010 IEEE 17th International Conference on Image Processing. [S.l.]： IEEE， 2010： 421?424.

[14] SUN Jian， YUAN Lu， JIA Jiaya， et al. Image completion with structure propagation [J]. ACM transactions on graphics， 2005， 24（3）： 861?868.

[15] TELA A. An image inpainting technique based on the fast marching method [J]. Journal of graphics tools， 2004， 9（1）： 23?33.