基于動態(tài)搜索策略的快速圖像修復(fù)算法

南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　趙政康

?

基于動態(tài)搜索策略的快速圖像修復(fù)算法

南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院趙政康

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

【關(guān)鍵詞】圖像修復(fù)；相似性衡量；動態(tài)搜索

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

1　Criminisi算法

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

第一步：明確標(biāo)記出待修復(fù)區(qū)域的邊緣；

第二步：對于每一個破損區(qū)域邊緣上的點(diǎn)p為中心的待修復(fù)塊，計(jì)算修復(fù)優(yōu)先權(quán)P(p)；

第三步：根據(jù)每一個待修復(fù)點(diǎn)的優(yōu)先權(quán)值找到具有最高修復(fù)優(yōu)先權(quán)的待修復(fù)塊；

第四步：當(dāng)確定本次迭代所要修復(fù)的塊后，通過樣本塊相似性計(jì)算公式在整個先驗(yàn)區(qū)域內(nèi)匹配最佳樣本塊。通常算法使用歐幾里得距離作為相似性衡量準(zhǔn)則。

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

2　本文改進(jìn)算法的提出

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

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

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

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

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

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

表1　修復(fù)質(zhì)量指標(biāo)與修復(fù)時間對比

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

參考文獻(xiàn)

[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－），男，南京航空航天大學(xué)碩士研究生，研究方向：數(shù)字圖像處理。

作者簡介：