基于改進Criminisi算法的圖像修復

李愛菊，鈕文良

北京聯合大學，北京 102200

基于改進Criminisi算法的圖像修復

李愛菊，鈕文良

北京聯合大學，北京 102200

1 引言

隨著計算機圖像技術的迅速發展，其在生物醫學、工業生產、遙感測繪等領域得到了成功的應用。但是在圖像拍攝和采集過程中，由于受到外界因素的干擾，不可避免會丟失部分信息，一些區域缺失，影響圖像質量[1]。圖像修復技術是指根據已知信息，對修復區域內丟失信息進行補充，提高圖像在視覺上的真實性，已經成為圖像處理領域的研究熱點和重點[2]。

針對圖像修復問題，學者們投入了大量的時間和精力進行相關研究，提出了一些圖像修復算法，當前主要分為兩類方法：基于非紋理圖像修復和基于紋理修復方法[3]。基于非紋理的圖像修復方法主要是利用待修復區域附近的已知信息，按一定的規則向待修復區域蔓延，如文獻[4]提出的基于高階偏微分的圖像修復算法，文獻[5]提出的基于整體變分（TV）模型的圖像修復算法等，它們適合于小區域的圖像修復，但如果待修復的區域比較大，難以獲得比較理想的修復效果。文獻[6]提出基于先驗模型的圖像修復算法，對于結構信息的圖像，可以得到較好的修復效果，但是對于含有豐富紋理圖像，修復效果較差。基于紋理綜合的修復方法指利用塊匹配選取合適的紋理塊來修復，其中Criminisi算法是最為經典的紋理圖像修復算法[7]，其首先從圖像完好區域中尋找與待修復區域最匹配的像素塊，然后將其填充到受損區域，修復效果較好。然而在實際應用過程，Criminisi算法存在一些不足，如出現馬賽克效應和紋理混亂現象。為了克服Criminisi算法的不足，國內外一些學者在該算法的基礎上，提出了一些改進Criminisi圖像修復算法[8-11]，但是這些算法都存在各自的缺陷，如何提高圖像修復效果，值得進一步研究。

為了獲得理想的修復效果，針對Criminisi算法存在的不足，提出一種改進Criminisi算法的圖像修復算法，并通過仿真實驗測試算法的可行性和優越性。首先改進優先權計算方式找到最優待修復塊，然后完善最優匹配塊搜索策略，并找到最優匹配塊，最后采用新的置信值更新方式以獲得更為理想的修復效果，并通過仿真實驗測試算法性能。結果表明，相對于Criminisi算法，改進Criminisi算法不僅得到了理想的圖像修復效果，而且大幅度減少了修復時間，提高了圖像的修復效率。

2 Criminisi算法

2.1 基本工作原理

Criminisi算法的工作原理如圖1所示，其中，Ω表示破損區域，I是待修復圖像，?Ω表示破損區域的邊界，點p為目標像素點，Φ表示樣本區域，▽Ip是等照度線的切線方向，np是受損邊界切線的法向量，φp是以p中心的目標塊[12]。

圖1 Criminisi算法原理

2.2 Criminisi算法的工作步驟

（1）計算優先權。先標記出待修復區域Ω，那么Φ=I-Ω，取以受損邊緣上像素點p為中心的模版φp，計算受損邊緣每個像素點的優先權，并按優先權排序，則優先權P(p)計算為：

其中，D(p)為數據項，C(p)為置信度，它們定義為：

（2）尋找最佳匹配塊。計算當前邊緣所有像素塊的優先權，找出優先權最大的塊φp作為當前的目標塊，采用全局搜索的方法，將SSD作為匹配準則在未破損區域內搜索與待修補塊相似度最高的匹配塊。SSD匹配準則定義如下：

式中，d(φp，φq)是φp，φq對應已知像素點顏色RGB。

（3）更新置信度。每次修復的塊都在待修復區域邊緣上，修復區域邊緣總是處在不斷的變化中，因此有必要每完成一個紋理塊的修復就對邊緣進行更新。最高優先級的目標塊被填充后，剛剛填充的像素點由受損區域變為樣本區，置信度發生了變化，因此需要更新像素點的置信度，置信度更新為：

更新置信度得到一個新的邊緣，圖像的待修復區域發生了變化，邊緣像素點的置信度也就發生了變化。重復上述三個步驟直到待修復區域Ω為空，則修復完畢。

綜合上述可知，基于Criminisi算法的圖像修復流程圖具體如圖2所示。

圖2 Criminisi算法流程圖

3 改進Criminisi算法

3.1 優先權的改進

作為Criminisi算法的第一步，待修復塊優先權的判定至關重要，根據文獻[13]中的實驗結果，對式（1）改進，具體做法如下：

3.2 最佳匹配塊搜索算法完善

在Criminisi算法中，由上至下、左到右的最優匹配塊的搜索順序，最終找到最優匹配塊，然而在圖像修復塊的匹配過程中，會產生大量候選塊，若找到最優匹配塊與相差較遠待修復塊，那么對待修復塊的已知像素點進行較好修復，其他部分修復效果差。為此，提出一種改進最優匹配塊搜索策略，具體為：

（1）根據優先權值確定的當前待修復點。

（2）以當前待修復點為中心，順序搜索到與其距離為n的匹配點。

（3）以這些匹配點為中心，生成候選塊與待修復塊做SSD計算。

（4）不斷重復上述步驟，直到搜索完匹配區域為止。

3.3 置信值更新的改進

在Criminisi算法修改過程中，同等對待修補后的像素點和非破損區域的像素點，這與實際情況不相符，這樣可能會破壞圖像模板，對圖像的修復結果產生不利影響。為了解決該難題，先設定一顏色閾值th，該閾值根據圖像修復模板對應的SSD的值確定，具體改進方式為：

4 仿真實驗

4.1 仿真環境

為了測試改進Criminisi算法的圖像修復性能，在Intel酷睿i5 4570 CPU，RAM 4 GB，Windows XP的計算機上，采用VC++編程實現，為了使改進Criminisi算法結果具有可比性，采用標準Criminisi算法對比算法的性能，仿真對象為：Girl、Bungee和Grass圖像[14]，原圖和待修復圖像具體如圖3和圖4所示。

圖3 原圖

圖4 待修復圖像

4.2 結果與分析

4.2.1 主觀評價結果對比

分別采用改進Criminisi算法和Criminisi算法對圖3的圖像進行修復，結果如圖5～7所示。

圖5 Girl修復效果對比

圖6 Bungee修復效果對比圖

圖7 Grass修復效果對比圖

從圖5～7可知，從標記方框可以明顯看出，標準Criminisi算法修復后的圖像中出現了嚴重的結構斷裂以及不連續現象，但是改進Criminisi算法的視覺效果得到明顯改善，這主要由于改進Criminisi算法在圖像修復過程中，對優先權值進行改進，可以有效地保證結構信息較強的待修復塊，并完善最優匹配塊搜索策略以及置信值更新方式，提高了圖像修復后的視覺效果。

4.2.2 客觀評價結果對比

對圖像修復算法性能的評價，除了采用主觀評價外，通常還采用客觀評價標準進行衡量。為了更進一步評價圖像的修復質量，采用峰值信噪比（Peak Signal to Noise Ratios，PSNR）和計算時間對圖像修復質量進行客觀評價，它們結果分別如圖8，9所示。對圖8，9進行分析，可以得到如下結論：

（1）相對于Criminisi算法，改進Criminisi算法的計算時間相對減少，計算復雜度較低，提高了圖像修復的效率，對比結果表明，改進Criminisi算法更加適合于圖像的在線修復，應用范圍更廣，實用價值更高。

（2）相對于Criminisi算法，改進Criminisi算法修復后圖像的信噪比大，修復效果更佳，這說明通過對Criminisi算法進行改進和完善，較好地克服了其不足，可以確保確修復后圖像的視覺效果，改進Criminisi算法是一種性能優異、效率高的圖像修復算法。

圖8 修復后圖像信噪比的對比

圖9 圖像修復時間的對比

5 結束語

針對Criminisi算法存在的缺陷，提出了一種改進Criminisi的圖像修復算法，從優先權計算、最優匹配塊搜索策略以及置信值更新等方面進行改進和完善，并進行了仿真對比實驗。結果表明，改進Criminisi算法不僅能有效確保修復后圖像的視覺效果，而且能有效地節約對應的修復時間，是一種性能更為優異的圖像修復算法。

[1]Minh N，Martin V.The contourlet transform：an efficient directional multiresolution image representation[J].IEEE Transactions on Image Processing，2005，14（12）：2091-2106.

[2]林云莉，趙俊紅，朱學峰，等.改進的紋理合成圖像修復算法[J].計算機應用與軟件，2010，27（10）：11-12.

[3]屈磊，韋穗，梁棟，等.快速自適應模板圖像修復算法[J].中國圖象圖形學報，2008，13（1）：24-28.

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

[5]Anamandra S H，Chandrasekaran V.Exemplar-based color image inpainting using a simple and effective gradient function[C]//Sargolzaei S.International Conference on Image Processing and Computer Vision，2010：140-145.

[6]Zhou Y T，Li L，Xia K W.Research on weighted priority of exemplar-based image inpainting[J].Journal of Electronics，2012，29（1）：166-170.

[7]代仕梅，張紅英，曾超.一種基于樣例的快速圖像修復算法[J].圖形、圖像與多媒體，2010，29（22）：34-39.

[8]付紹春，樓順天.基于區域紋理合成的圖像修補算法[J].電子與信息學報，2009，31（6）：1319-1322.

[9]林勝華，汪繼文，沈玉峰，等.利用鄰域相似度的圖像修復[J].計算機工程與應用，2010，46（7）：190-191.

[10]吳曉軍，李功清.基于樣本和線性結構信息的大范圍圖像修復算法[J].電子學報，2012，40（8）：1509-1514.

[11]張偉彬.基于修復順序的圖像修復算法[J].計算機工程與應用，2008，44（22）：195-196.

[12]陳卿，王慧琴，吳萌.基于紋理特征的自適應圖像修復算法[J].計算機應用，2011，6（6）：1572-1574.

[13]Kwok T H，Sheung H，Charlie C.Fast query for exemplar-basedimagecompletion[J].IEEE Transactionson Image Processing，2010，19（12）：3106-3115.

[14]任澍，唐向宏，康佳倫.利用紋理和邊緣特征的Criminisi改進算法[J].中國圖象圖形學報，2012，17（9）：1086-1091.

[15]Xu Z B，Sun J.Image inpainting by patch propagation using patch sparsity[J].IEEE Transactions on Image Processing，2010，19（5）：1153-1165.

LI Aiju,NIU Wenliang

Beijing Union University,Beijing 102200,China

A novel image inpainting method based on improved Criminisi algorithm to solve the defects of Criminisi algorithm which hardly yields unfavorable results and costs much inpainting time is proposed.The priority levels of the blocks are obtained and the optimal inpainted block is selected,and then the optimum matching block in the image is found by improving search method,and the confidence value is updated to obtain good inpainting results.The simulation experiments are carried out to test the performance.The experimental results show that compared with Criminisi algorithm,the proposed algorithm is effective in both guaranteeing the quality of repaired images and saving much more repairing time.

image inpainting;Criminisi algorithm;priority levels;image texture

針對Criminisi算法難以獲得理想的修復效果，且存在修復時間過長等缺陷，提出一種改進Criminisi算法的圖像修復算法。改進優先權計算方式找到最優待修復塊，完善最優匹配塊搜索策略，找到最優匹配塊，采用新的置信值更新方式以獲得更為理想修復效果，通過仿真實驗測試算法性能，結果表明，相較于Criminisi算法，改進Criminisi算法不僅獲得了較理想的圖像修復效果，而且大幅度減少了修復時間，提高了圖像修復的效果。

圖像修復；Criminisi算法；優先級；圖像紋理

A

TP919

10.3778/j.issn.1002-8331.1401-0419

LI Aiju,NIU Wenliang.Image inpainting based on improved Criminisi algorithm.Computer Engineering and Applications,2014,50（18）：167-170.

北京高等學校青年英才計劃項目（No.YETP1766）。

李愛菊（1980—），女，講師，主要研究領域：高效計算、大數據、并行處理、圖形圖像等；鈕文良（1958—），男，教授，主要研究領域：網絡通信、無線傳感網等。E-mail：50310646@qq.com

2014-01-26

2014-03-21

1002-8331（2014）18-0167-04