辛晚霞，楊 明

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

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

本文結(jié)合GMP提出一種采用混合選擇算子的圖像修復(fù)算法，該算法在使用GMP對(duì)圖像進(jìn)行稀疏表示的過(guò)程中，使用精英保留策略、競(jìng)標(biāo)賽選擇方法和輪盤(pán)賭方法［15］相結(jié)合的選擇算子，在變異過(guò)程中采用動(dòng)態(tài)變異的方式，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證算法的可行性。

1 基于GMP的圖像修復(fù)算法

1.1 GMP 算法原理

Mallat和Zhang引入的MP是一個(gè)通過(guò)選取字典向量來(lái)優(yōu)化逼近的貪婪算法。信號(hào)f的最佳逼近原子φp0∈D(D是過(guò)完備字典庫(kù))為

逼近殘差為

通過(guò)從字典里選取另一最優(yōu)原子φp1，進(jìn)一步用MP逼近誤差R，繼續(xù)這一過(guò)程，得到l階誤差Rl(l=1，2，…，K)，最后得到信號(hào)的分解式

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

1.2 基于GMP的圖像修復(fù)算法

圖像修復(fù)是利用損壞圖像的未被損壞信息，按照一定規(guī)則對(duì)損壞區(qū)域進(jìn)行填補(bǔ)，利用壓縮感知理論對(duì)損壞區(qū)域進(jìn)行修復(fù)是一種新穎的方法。設(shè)圖像的完整信息為f，未被損壞區(qū)域?yàn)閥obs，則yobs=M f，M是掩模算子，損壞區(qū)域?yàn)閥=f－yobs，圖像具有稀疏性，所以f在字典D中可以稀疏表示

根據(jù)圖像的全局稀疏性，未被損壞區(qū)域yobs和損壞區(qū)域y共用稀疏系數(shù)α，則圖像修復(fù)問(wèn)題可定義為

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

2 改進(jìn)的GMP圖像修復(fù)算法

2.1 改進(jìn)的選擇算子

選擇算子具有降低種群多樣性和保護(hù)種群收斂性的雙重作用，使用單一的選擇算子會(huì)導(dǎo)致早熟并且降低種群的多樣性。為了解決這個(gè)問(wèn)題，在進(jìn)化的前后階段分別使用不同的選擇算子來(lái)達(dá)到選擇壓力的改變，并且保留精英個(gè)體，將每代中最優(yōu)的個(gè)體直接復(fù)制到下一代，而不經(jīng)過(guò)交叉和變異操作，把最差的個(gè)體替換為最優(yōu)的個(gè)體，在進(jìn)化初期為了保護(hù)種群的多樣性使用錦標(biāo)賽選擇方式來(lái)降低選擇壓力，而在后期為了加快收斂使用輪盤(pán)賭方法來(lái)提高選擇壓力。

2.2 基于改進(jìn)的GMP圖像修復(fù)算法

基于改進(jìn)的GMP圖像修復(fù)算法的具體實(shí)現(xiàn)步驟如下:

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

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

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

然后在［0，1］區(qū)間產(chǎn)生一個(gè)均勻分布的偽隨機(jī)數(shù)r，若r＜q1，則選第一個(gè)個(gè)體v1;若qi－1＜r≤qi，則選第i個(gè)個(gè)體，依次進(jìn)行下去。

4)交叉運(yùn)算:采用算術(shù)交叉的方式，根據(jù)交叉率pc選出交叉?zhèn)€體，將交叉?zhèn)€體兩兩隨機(jī)配對(duì)，根據(jù)以下方式產(chǎn)生后代。設(shè)雙親為v1和v2，交叉產(chǎn)生的后代為

5)變異運(yùn)算:根據(jù)變異率pm選出變異個(gè)體，設(shè)變異個(gè)體為v，則變異后的個(gè)體vm按如下方式產(chǎn)生

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

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

7)通過(guò)解碼得到最優(yōu)個(gè)體對(duì)應(yīng)的原子參數(shù)，并由參數(shù)計(jì)算出最優(yōu)原子φpl，再將原子與殘差作內(nèi)積運(yùn)算得到原子的系數(shù)αl。判斷l(xiāng)是否小于K，是則轉(zhuǎn)至步驟2)，否則轉(zhuǎn)至步驟8)。

8)最后得到式(6)的稀疏系數(shù) α ={αl，l=1，2，…，K}，對(duì)應(yīng)的原子 D={φpl，l=1，2，…，K}，通過(guò)式(6)計(jì)算出損壞區(qū)域y。

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

3.1 圖像修復(fù)的評(píng)價(jià)

本文對(duì)圖像修復(fù)效果采用客觀評(píng)價(jià)法進(jìn)行評(píng)價(jià)，評(píng)價(jià)指標(biāo)為信噪比，計(jì)算方法為

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

3.2 仿真結(jié)果

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

表1 GMP參數(shù)設(shè)置

表2 實(shí)驗(yàn)結(jié)果

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

圖1 Lena修復(fù)

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

圖3為對(duì)Boat圖用棋子格掩模后修復(fù)的圖像，圖3a和圖3b中黑色區(qū)域?yàn)閷挾?個(gè)像素的掩模區(qū)域，掩模率為11.38%，從圖 2c、圖 2d、圖 2e和圖 2f中可以看出:FOE，TV和CDD方法對(duì)船上的桅桿和船身修復(fù)時(shí)有陰影出現(xiàn)，而本文方法修復(fù)后的陰影很少，且信噪比高。

4 結(jié)論

本文提出一種基于GMP的圖像修復(fù)算法，它將GMP與修復(fù)算法相結(jié)合，并改進(jìn)了GMP的選擇算子，采用精英保留策略、錦標(biāo)賽選擇方法及輪盤(pán)賭方法相結(jié)合的混合選擇算子。該算法充分考慮了圖像的全局稀疏信息，并使用適合細(xì)節(jié)描寫(xiě)的2D幾何字典，采用GMP算法減少了計(jì)算復(fù)雜度。通過(guò)仿真結(jié)果可以看出:本文提出的算法有一定的應(yīng)用價(jià)值，并且修復(fù)后的圖像更接近真實(shí)圖像。

圖2 Peppers修復(fù)

圖3 Boat修復(fù)

［1］陳佩.基于馬爾科夫隨機(jī)場(chǎng)圖像恢復(fù)算法研究［D］.南京:南京師范大學(xué)，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］.電視技術(shù)，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］范虹，孟慶豐，張優(yōu)云.用混合編碼遺傳算法實(shí)現(xiàn)匹配追蹤算法［J］.西安交通大學(xué)學(xué)報(bào)，2005，39(3):295－299.

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

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

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

［14］李亞文.遺傳匹配追蹤算法的研究與改進(jìn)［D］.無(wú)錫:江南大學(xué)，2011.

［15］玄光男，程潤(rùn)偉.遺傳算法與工程設(shè)計(jì)［M］.北京:科學(xué)出版社，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.