基于交替方向乘子法的圖像復(fù)原問題研究

楊靜雅

(長(zhǎng)治學(xué)院 數(shù)學(xué)系,山西 長(zhǎng)治 046011)

0 引言

圖像處理中的圖像復(fù)原問題早在1960年就被提出[1]．在圖像復(fù)原問題中,原圖像記為x,觀測(cè)到的圖像記為y,觀測(cè)圖像通常會(huì)受到噪聲的影響,建立模型如下:

y=Bx+n,

(1)

其中B為矩陣,表示直接作用的算子,n為噪聲項(xiàng)．通常,將圖像進(jìn)行取樣和量化,得到的結(jié)果是實(shí)數(shù)矩陣．在一般的圖像復(fù)原問題中,B表示線性作用算子．復(fù)原處理有時(shí)也稱為反卷積,則矩陣B表示一個(gè)卷積算子．由于相機(jī)與被攝物體之間可能存在相對(duì)運(yùn)動(dòng),造成運(yùn)動(dòng)模糊、聚焦偏差等,即為模型中的噪聲項(xiàng),會(huì)對(duì)觀測(cè)結(jié)果產(chǎn)生一定的影響．

1 無約束優(yōu)化問題

約束優(yōu)化問題的一般形式:

(2)

其中ε為常數(shù)且ε≥0,φ(x)是光滑或者非光滑的目標(biāo)函數(shù)．當(dāng)φ(x)=‖x‖1,ε=0時(shí),上述問題通常稱為基追蹤問題．

最近幾年,根據(jù)(2)式提出了壓縮感知問題[2,3]．基于矩陣B和原始圖像x的稀疏程度,壓縮感知的相關(guān)理論提供了(2)式解的條件．在大多數(shù)的壓縮感知和圖像復(fù)原問題中,非光滑的正則項(xiàng),例如:全變差、l1范數(shù),是較為常見的形式[2,4]．

針對(duì)無約束優(yōu)化問題,即

(3)

其中,τ稱為正則化參數(shù)．顯然,問題(3)和(2)是等價(jià)的．為了解決問題(3),提出了一些基于迭代收縮的算法,例如:加速方法SpaRSA[5]、迭代方法TwIST[6]和FISTA[7]等．大多數(shù)這些算法的關(guān)鍵因素是收縮、閾值,以及去噪功能．基于以上特點(diǎn),得到函數(shù):

(4)

針對(duì)目標(biāo)函數(shù)是兩個(gè)函數(shù)之和的無約束優(yōu)化問題,形式如下:

(5)

其中g(shù):Rn→Rd．

采用分離變量法,創(chuàng)建一個(gè)新的變量v,滿足v=g(u),作為f2的變量,即

(6)

通過引入二次懲罰項(xiàng)的方法,將問題(6)轉(zhuǎn)化為無約束優(yōu)化問題,即

(7)

通過交替進(jìn)行,化u和v為最小值,當(dāng)α取值很大時(shí),(7)式可逼近(6)式,同時(shí),也與(5)式等價(jià)．

對(duì)于圖像復(fù)原的無約束優(yōu)化問題,如(3)式中的定義．這個(gè)問題可以寫成如下形式:

f2(x)=τφ(x).

(8)

則得到相應(yīng)的約束優(yōu)化問題:

s.t.x=v.

(9)

如果φ(x)=ψ(Dx),利用分離變量法,得到下面的約束優(yōu)化問題:

(10)

2 提出的算法

2.1 采用對(duì)稱形式的交替方向乘子法,原理如下:

minf(x)+g(z) s.t.Ax+Bz=c.

(11)

其對(duì)應(yīng)的拉格朗日表達(dá)式為:

(12)

對(duì)稱形式的交替方向乘子法,包括以下迭代步驟:

yk+1/2=yk+ρ(Axk+1+Bzk-c)

(13)

yk+1=yk+1/2+ρ(Axk+1+Bzk+1-c),

(14)

那么上面的迭代步驟可以變?yōu)橐韵滦问?

uk+1/2=uk+Axk+1+Bzk-c

(15)

uk+1=uk+1/2+Axk+1+Bzk+1-c

這種交替化求最小的方法,與原來的無約束問題(5)相比,每一步的運(yùn)算更容易求解．

2.2 對(duì)稱的交替方向乘子法——SUMAM,算法如下:

算法SUMAM

1)k=0,取μ=0.9,選擇v0和λ0;

2)重復(fù);

4)λk+1/2=λk-(xk+1-vk);

6)λk+1=λk+1/2-(xk+1-vk+1);

7)λ←λ+1;

8)滿足某個(gè)終止規(guī)則,停止．

其中,對(duì)算法中第三步驟的式子求解,得到解的形式如下:

(16)

對(duì)算法中第五步的式子求解,得到的解如下:

(17)

3 數(shù)值實(shí)驗(yàn)

考慮關(guān)于攝影師圖像的修復(fù)問題,攝影師的原始圖像及觀察到的圖像如下圖所示,其中,觀測(cè)圖像(圖2)被高斯噪聲(SNR值為40 dB)破壞,與原始圖像相比,缺失了40%的像素．

圖1 原圖

圖2 噪聲污染的圖像

圖3 修復(fù)后的圖像

算法迭代次數(shù)CPU/sSUMAM7412.9TwIST502143FISTA50088.4

利用SUMAM算法編程,通過Matlab軟件對(duì)圖2進(jìn)行處理,得到結(jié)果如圖3所示,與圖1進(jìn)行對(duì)比,清晰度較高,達(dá)到了非常好的修復(fù)效果．

表1給出了SUMAM算法與TwIST算法、FISTA算法處理上述問題時(shí),在迭代次數(shù)與CPU運(yùn)行時(shí)間的比較．

圖4 三個(gè)算法的比較

圖4表示利用SUMAM算法與TwIST算法、FISTA算法處理上述問題時(shí),三種算法各自的目標(biāo)函數(shù)隨時(shí)間的變化情況．

本文所有實(shí)驗(yàn)均在Matlab R2008a,win7系統(tǒng),處理器AMD Athlon(tm) II×2 215,CPU 2.70 GHz,RAM:2.00GB環(huán)境下運(yùn)行．

4 結(jié)論

本文針對(duì)一類無約束優(yōu)化問題,利用對(duì)稱形式的交替方向乘子法SUMAM進(jìn)行求解．?dāng)?shù)值實(shí)驗(yàn)結(jié)果表明,該算法達(dá)到了較好的修復(fù)效果．特別是,該算法迭代次數(shù)以及CPU均大幅度減少,較大程度上提高了運(yùn)算效率,驗(yàn)證了算法的可行性以及在修復(fù)速度方面的優(yōu)勢(shì)．