基于遺傳匹配追蹤的圖像修復算法

辛晚霞，楊 明

(中北大學理學院，山西太原030051)

近幾年，圖像修復是圖像處理領域的研究熱點，目前常用的算法有基于馬爾科夫隨機場的方法(FOE)［1］、基于整體變分的方法(TV)［2］、基于曲率擴散的模型(CDD)［3］和基于壓縮感知(CS)的方法［4－6］等。基于 CS［7］的圖像修復算法需要對圖像進行稀疏表示，匹配追蹤算法(MP)［8－9］是一種常用的稀疏表示方法，它以貪婪算法為核心，較其他稀疏算法更容易理解，并且逼近效果好，計算復雜度小。而MP在冗余字典庫中的遍歷式搜索使得計算量很大，需要巨大的存儲空間。為了解決這個問題，人們提出了遺傳匹配追蹤算法(GMP)［10－14］，GMP 模擬生物進化現象尋找最佳原子。為了得到更理想的效果，文獻［10－12］分別對編碼方式、選擇算子和搜索方式進行了改進。

本文結合GMP提出一種采用混合選擇算子的圖像修復算法，該算法在使用GMP對圖像進行稀疏表示的過程中，使用精英保留策略、競標賽選擇方法和輪盤賭方法［15］相結合的選擇算子，在變異過程中采用動態變異的方式，通過仿真實驗驗證算法的可行性。

1 基于GMP的圖像修復算法

1.1 GMP 算法原理

Mallat和Zhang引入的MP是一個通過選取字典向量來優化逼近的貪婪算法。信號f的最佳逼近原子φp0∈D(D是過完備字典庫)為

逼近殘差為

通過從字典里選取另一最優原子φp1，進一步用MP逼近誤差R，繼續這一過程，得到l階誤差Rl(l=1，2，…，K)，最后得到信號的分解式

GMP將MP中的參數空間投影到編碼空間進行編碼，編碼采用實數編碼，設定初始種群規模Size、種群代數G、參數編碼長度n，并形成初始種群pm，解碼并計算種群中個體的適應值，得到本代最優個體，但不是全局最優的個體，判斷m是否小于G，小于則進行遺傳操作，在保留上一代優良基因的同時又加入了新的基因，大于G則跳出遺傳算法，并帶回最優個體的原子、殘差及投影系數，判斷原子個數是否小于K(稀疏度)，小于則繼續進行迭代，否則停止，得到最終的原子及投影系數。

1.2 基于GMP的圖像修復算法

圖像修復是利用損壞圖像的未被損壞信息，按照一定規則對損壞區域進行填補，利用壓縮感知理論對損壞區域進行修復是一種新穎的方法。設圖像的完整信息為f，未被損壞區域為yobs，則yobs=M f，M是掩模算子，損壞區域為y=f－yobs，圖像具有稀疏性，所以f在字典D中可以稀疏表示

根據圖像的全局稀疏性，未被損壞區域yobs和損壞區域y共用稀疏系數α，則圖像修復問題可定義為

基于GMP的圖像修復算法就是通過GMP求解式(5)得到系數α，然后利用式(6)恢復損壞區域y的過程。

2 改進的GMP圖像修復算法

2.1 改進的選擇算子

選擇算子具有降低種群多樣性和保護種群收斂性的雙重作用，使用單一的選擇算子會導致早熟并且降低種群的多樣性。為了解決這個問題，在進化的前后階段分別使用不同的選擇算子來達到選擇壓力的改變，并且保留精英個體，將每代中最優的個體直接復制到下一代，而不經過交叉和變異操作，把最差的個體替換為最優的個體，在進化初期為了保護種群的多樣性使用錦標賽選擇方式來降低選擇壓力，而在后期為了加快收斂使用輪盤賭方法來提高選擇壓力。

2.2 基于改進的GMP圖像修復算法

基于改進的GMP圖像修復算法的具體實現步驟如下:

1)給定待修復圖像的未被破損區域yobs和掩模算子M，選擇合適的字典D，設置種群規模Size，種群代數G，參數編碼長度n，稀疏度K，交叉率pc，變異率pm，迭代次數l=0，隨機產生初始種群。

2)計算種群中每個個體的適應值eval(vi)，i=1，2，…，Size，即個體所對應字典D中的原子與殘差R或yobs的內積，最高的適應值即為原子與殘差內積的最大值。

3)選擇運算:采用改進的選擇算子對種群進行選擇，即保留適應值最高的個體，直接復制到下一代，把適應值最低的個體替換為最高的個體，前G1代選擇錦標賽方式進行選擇操作，后G－G1代選擇輪盤賭方式進行選擇操作。錦標賽方式為隨機兩兩一組進行競賽，選擇適應值最大的個體。輪盤賭方式為先計算選擇概率pi及累計概率qi，即

然后在［0，1］區間產生一個均勻分布的偽隨機數r，若r＜q1，則選第一個個體v1;若qi－1＜r≤qi，則選第i個個體，依次進行下去。

4)交叉運算:采用算術交叉的方式，根據交叉率pc選出交叉個體，將交叉個體兩兩隨機配對，根據以下方式產生后代。設雙親為v1和v2，交叉產生的后代為

5)變異運算:根據變異率pm選出變異個體，設變異個體為v，則變異后的個體vm按如下方式產生

式中:vU為字典D變量的上界;r是［0，1］間的隨機數;G是最大代數;g為代數;b為確定不均勻度的參數，取2。

6)判斷種群是否收斂，若收斂轉至步驟7)，否則，轉至步驟3)。

7)通過解碼得到最優個體對應的原子參數，并由參數計算出最優原子φpl，再將原子與殘差作內積運算得到原子的系數αl。判斷l是否小于K，是則轉至步驟2)，否則轉至步驟8)。

8)最后得到式(6)的稀疏系數 α ={αl，l=1，2，…，K}，對應的原子 D={φpl，l=1，2，…，K}，通過式(6)計算出損壞區域y。

3 實驗結果及分析

3.1 圖像修復的評價

本文對圖像修復效果采用客觀評價法進行評價，評價指標為信噪比，計算方法為

式中:I0，I1分別表示原圖與修復后的圖像，信噪比越高，修復的效果越好。

3.2 仿真結果

本節在小區域修復和文字去除等方面做實驗驗證算法的可行性，并與FOE方法、TV方法、CDD方法進行比較。表1給出了基于本文GMP圖像修復算法的參數設置，字典D采用文獻［16］中的2D幾何字典。表2給出了3種算法修復3幅圖像的信噪比。

表1 GMP參數設置

表2 實驗結果

圖1為對Lena圖字母掩模后的修復，圖1a為掩模后的圖像，圖1b為字母掩模，掩模率為22.75%，從圖1c、圖1d、圖1e和圖1f中可以看出:FOE方法在肩膀部位出現鋸齒，帽子和圖像左邊界有陰影;TV方法在邊緣部分的修復效果不是很理想;CDD方法有個別像素在修復時出現錯誤，邊緣部分有些模糊;而本文方法無論在平滑還是邊緣區域修復效果都很好，并且信噪比高。

圖1 Lena修復

圖2為對Peppers圖隨機掩模50%的修復，即有一半的信息丟失，從圖2c、圖2d、圖2e和圖2f中可以看出:FOE方法在某些邊緣部分出現了鋸齒;CDD方法對于邊緣部分基本發生了模糊;TV和本文方法修復效果都很好，但是本文方法的信噪比更高一些。

圖3為對Boat圖用棋子格掩模后修復的圖像，圖3a和圖3b中黑色區域為寬度2個像素的掩模區域，掩模率為11.38%，從圖 2c、圖 2d、圖 2e和圖 2f中可以看出:FOE，TV和CDD方法對船上的桅桿和船身修復時有陰影出現，而本文方法修復后的陰影很少，且信噪比高。

4 結論

本文提出一種基于GMP的圖像修復算法，它將GMP與修復算法相結合，并改進了GMP的選擇算子，采用精英保留策略、錦標賽選擇方法及輪盤賭方法相結合的混合選擇算子。該算法充分考慮了圖像的全局稀疏信息，并使用適合細節描寫的2D幾何字典，采用GMP算法減少了計算復雜度。通過仿真結果可以看出:本文提出的算法有一定的應用價值，并且修復后的圖像更接近真實圖像。

圖2 Peppers修復

圖3 Boat修復

［1］陳佩.基于馬爾科夫隨機場圖像恢復算法研究［D］.南京:南京師范大學，2008.

［2］ CHAN T，SHEN J.Mathematical models for local nontexture inpainting［J］.SIAN Journal on Applied Mathematics，2002，62(3):1019－1043.

［3］ CHAN T，SHEN J.Non－texture inpainting by curvature－driven diffusions(CDD)［J］.Journal of Visual Communcation and Image Representation，2001，12(4):436－449.

［4］ SHEN B，HUW，ZHANG Y，etal.Image inpainting via sparse representation［C］//Proc.ICASSP 2009 .［S.l.］:IEEE Press，2009:697－700.

［5］ FADILI M，STARCK J，MURTAGH F.Inpainting and zooming using sparse representation［J］.Comput.J.，2007，52(1):64－79.

［6］ GULERYUZLO.Nonlinear approximation based image recovery using adaptive sparse reconstructions and iterated de－noising－part II:adaptiveal gorithms［J］.IEEE Trans.Image Process，2006，15(3):555－571.

［7］宋允東.基于 JND的壓縮感知圖像編碼［J］.電視技術，2012，36(14):15－18.

［8］ MALLAT S，ZHANG Z.Matching pursuit with time－frequency dictionaries［J］.IEEE Trans.Signal Processing，1993，41(12):3397－3415.

［9］ MCCLUREM，CARIN L，Matching pursuits with a wavebased dictionary［J］.IEEE Trans.Signal Process，1997，45(12):2912－2927.

［10］范虹，孟慶豐，張優云.用混合編碼遺傳算法實現匹配追蹤算法［J］.西安交通大學學報，2005，39(3):295－299.

［11］李亞文，于鳳芹.一種改進選擇算子的遺傳匹配追蹤算法［J］.數據采集與處理，2011，26(2):177－180.

［12］高瑞.基于GA和過完備原子庫劃分的MP信號稀疏分解算法［J］.科學技術與工程，2008，8(4):914－918.

［13］高強.遺傳算法降低匹配追蹤算法計算量的研究［J］.振動、測試與診斷，2003，23(3):165－167.

［14］李亞文.遺傳匹配追蹤算法的研究與改進［D］.無錫:江南大學，2011.

［15］玄光男，程潤偉.遺傳算法與工程設計［M］.北京:科學出版社，2000.

［16］ OSCAR D，GIANLUCA M，ROSA M，et al.Geometric video approximation using weighted matching pursuit［J］.IEEE Trans.Signal Processing，2009，18(8):1703－1716.