基于動態搜索策略的快速圖像修復算法

南京航空航天大學計算機科學與技術學院　趙政康

?

基于動態搜索策略的快速圖像修復算法

南京航空航天大學計算機科學與技術學院趙政康

【摘要】本文在樣本全局搜索算法的基礎上，設計了一種新的算法，算法在匹配樣本策略上著手，使用動態的對比算法，在相似性計算結束之前排除掉差異較大的樣本，減少了樣本匹配的平均計算量。實驗結果表明，與對比算法相比較，本文算法在不降低修復質量的前提下有效的提高了算法的修復速度。

【關鍵詞】圖像修復；相似性衡量；動態搜索

圖像修復是數字圖像處理領域的一個重要分支，為了恢復損毀圖像的完整性，利用圖像的已知信息，按照一定的規則，來修補圖像中缺失部分，是圖像修復算法重點關注的問題。圖像修復算法可以分為基于擴散的修復方法和基于樣本紋理合成的修復方法。基于擴散的修復方法典型的算法是Bertalmio于2000年提出的基于偏微分方程的數字圖像修復算法[1]，2003年Criminisi等人另辟蹊徑提出了基于樣本的圖像修復算法[2]，它是基于紋理合成的修復方法，借鑒了紋理生成方法中的思想來尋找樣本區域并匹配復制。Criminisi給出的大量實驗表明，該算法在修復效果和時間上都略勝一籌。接著，大量的科研工作者開始研究Criminisi的算法：文獻3通過分析Criminisi算法的不足之處，提出一種新的算法，該算法采用一種新的最優樣本塊的匹配準則，降低了傳播誤差的幾率。文獻4則提出了基于結構信息擴散的圖像修復算法[4]，獲得了不錯的效果。

1　Criminisi算法

Criminisi修復算法[2]的具體步驟簡述如下：

第一步：明確標記出待修復區域的邊緣；

第二步：對于每一個破損區域邊緣上的點p為中心的待修復塊，計算修復優先權P(p)；

第三步：根據每一個待修復點的優先權值找到具有最高修復優先權的待修復塊；

第四步：當確定本次迭代所要修復的塊后，通過樣本塊相似性計算公式在整個先驗區域內匹配最佳樣本塊。通常算法使用歐幾里得距離作為相似性衡量準則。

第五步：將選定的最佳匹配塊拷貝到待修復區域，完成本次迭代的修復。

2　本文改進算法的提出

分析修復算法復雜度可知，修復過程中最耗時的步驟是迭代過程中樣本塊與待修復塊一一匹配的過程。考慮到歐氏距離的計算是一種累加計算，使用窮舉的方式計算量太大，然而修復算法計算歐式距離是為了找出距離最小的樣本塊，因此本文設計了一種動態對比搜索策略來處理每次迭代過程中的樣本選擇問題，即在累加還沒結束之前就可以排除掉一部分相似性差異很大的樣本。具體的實現方式如下：使用一個變量d來記錄當前迭代過程中產生的最小的距離，修復迭代過程按照以下步驟進行：

第一步：初始化d為樣本空間中第一個樣本與待修復塊之間的距離；

第二步：該次迭代中其余樣本塊與待修復塊之間的距離計算方式為累加一次比較一次，即每累加一次，將臨時結果與d作比較，如果值大于d，則排除當前樣本塊；若d被更新成0，則停止這一次迭代，當前樣本塊為最佳匹配。

第三步：取當前d保持者的樣本塊作為最佳匹配，完成本次迭代。

3　實驗結果與分析

本節主要對所提算法進行功能驗證和性能評估，首先介紹實驗環境及實驗設計，然后通過實驗結果對比算法的修復效果和修復時間。本章實驗在PC機上使用Matlab 2013b編程實現，系統環境為64 位WIN 8系統，PC配置為Intel(R) Core(TM) i5-4210M CPU @ 2.60GHz，8GB內存。實驗設計了兩組實驗，通過對比Criminisi算法與本文所提算法的修復質量和修復速度來驗證本文算法的可行性。表格1記錄了兩組實驗的實驗數據，PSNR為修復質量衡量指標，PSNR值越大，修復結果越接近原圖像。

表1　修復質量指標與修復時間對比

分析表1中數據，本文算法的修復質量與對比算法相比平均下降了0.125分貝，這是一個相對比較小的數量級，可以認為本文算法的修復質量沒有受到搜索策略改變的影響。繼續觀察表中實驗的修復速度數據，本文算法的修復時間平均比對比算法降低了45.08秒，很明顯在修復速度方面本文算法具有明顯的優勢。在此得出結論，本文的改進算法在沒有影響修復質量的前提下有效的提高了修復速度，本文算法是可行的。

參考文獻

[1]Bertalmio M,Sapiro G,Caselles V,et al. Image inpainting[C].Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Technique,2000: 417-424.

[2]Criminisi A,Perez P,Toyama K.Object Removal by Exemplar-based Inpainting[C].Proc.of Conf.on Comp.Vision Pattern Rec.Madison,WI,USA,2003.

[3]Tang Feng,Ying Yiting,Wang Jin,Peng Qunsheng. A Novel Texture Synthesis Based Algorithm for Object Removal in Photographs[C].Ninth Asian Computing Science Conference.Chiang Mai.

[4]Sun Jian,Lu Yuan,Jia Jiaya,et al.Image Completion with Structure Propagation [EB/OL].[2015.7.30].http:// researeh.microsoft.com/asia/dload_files/group/VC/2005/ Imagecompletion/Siggraph05_0265. final.pdf.

趙政康（1990－），男，南京航空航天大學碩士研究生，研究方向：數字圖像處理。

作者簡介：