基于改進(jìn)回溯線搜索的二維梯度投影法

潘金鳳，徐芝美，徐秀美

(山東理工大學(xué) 電氣與電子工程學(xué)院，山東 淄博 255049)

0 引 言

近年來(lái)，壓縮感知理論因其低采樣率的特點(diǎn)而備受學(xué)者們的關(guān)注.信號(hào)能夠應(yīng)用壓縮感知理論進(jìn)行處理(被精確或近似精確重構(gòu))的前提是它在時(shí)域或某一變換域是稀疏的.目前該理論的絕大多數(shù)實(shí)現(xiàn)方法都是一維的，例如一維壓縮感知重構(gòu)算法有l(wèi)0范數(shù)最小化方法、l1范數(shù)最小化方法以及全變差(Total Variation, TV)最小化方法[1-3]等.l0范數(shù)最小化方法是根據(jù)信號(hào)稀疏性質(zhì)直接推導(dǎo)出的壓縮感知重構(gòu)方法，但該方法是非確定多項(xiàng)式(Non-deterministic Polynomial，NP)問(wèn)題，求解困難.l1范數(shù)最小化方法是l0范數(shù)最小化方法的最優(yōu)凸近似，在測(cè)量矩陣和稀疏基滿足等距約束性質(zhì)的條件下，二者具有相同的稀疏解[4]，與l0范數(shù)最小化方法相比，其優(yōu)點(diǎn)是求解容易.全變差度量信號(hào)振蕩的整體幅度，在圖像處理中有重要作用[5].但對(duì)于圖像處理，一維壓縮感知算法不利于圖像結(jié)構(gòu)信息的保存與利用，所以學(xué)者提出了二維壓縮感知方法[6].其中二維梯度投影(Two-Dimensional Projected Gradient, 2DPG)法[7]是對(duì)l0范數(shù)最小化方法應(yīng)用全變差正則化而得到的一種二維壓縮感知方法.文獻(xiàn)[7]的實(shí)驗(yàn)結(jié)果表明，在壓縮采樣率相同的前提下，與基于全變差正則化的一維壓縮感知算法NESTA[8]、L1-magic[9]、TVAL3[10]等相比，二維梯度投影方法重構(gòu)圖像的質(zhì)量得到提高.但二維梯度投影方法的缺點(diǎn)是全變差最小化求解時(shí)使用固定步長(zhǎng)的梯度下降法，不利于最優(yōu)步長(zhǎng)的選擇，所以本文應(yīng)用回溯線搜索(Backtracking Line Search, BTLS)[11]改進(jìn)其步長(zhǎng)選擇方法，以提高重構(gòu)圖像的質(zhì)量.實(shí)驗(yàn)結(jié)果表明，使用改進(jìn)方法后，重建圖像的峰值信噪比(Peak Signal-to-Noise Ratio, PSNR)和結(jié)構(gòu)相似度(Structural Similarity, SSIM)[12]都得到提高.同時(shí)，還提出一種改進(jìn)的回溯線搜索方法來(lái)實(shí)現(xiàn)全變差最小化的求解，該方法能進(jìn)一步改善重構(gòu)圖像的質(zhì)量，提高算法的收斂速度.

1 一維壓縮感知方法

若一維信號(hào)x∈RN×1和稀疏基矩陣Ψ∈RN×N滿足x=Ψa，且α∈RN×1是稀疏的，即l0范數(shù)‖α‖0

y=Φx=ΦΨα,

(1)

式中：壓縮測(cè)量值y∈RM×1.

式(1)可應(yīng)用l0范數(shù)最小化方法求解

min‖α‖0s.t.y=ΦΨα.

(2)

式(2)是NP-難問(wèn)題，可用正交匹配追蹤等貪婪類算法求解.

全變差最小化方法也可求解式(1)，

min‖TV(x)‖ s.t.y=ΦΨα,

(3)

式中：TV(x)為x的全變差.全變差最小化方法建立在信號(hào)梯度稀疏的假定之下，不要求信號(hào)本身是稀疏的[13].

2 改進(jìn)的二維梯度投影法

2.1 二維梯度投影法

目前，大多數(shù)圖像的壓縮感知處理方法是將其二維數(shù)據(jù)矩陣轉(zhuǎn)化為一維向量來(lái)處理，其缺點(diǎn)是破壞了圖像的結(jié)構(gòu)信息并導(dǎo)致測(cè)量矩陣等需要非常大的存儲(chǔ)空間.為了克服以上缺點(diǎn)，學(xué)者提出了二維壓縮感知方法.若圖像X∈RN×N在稀疏基Ψ∈RN×N下的稀疏系數(shù)為W=ΨXΨT，測(cè)量矩陣A∈RM×N，B∈RM×N，則二維壓縮感知的觀測(cè)值為Y=AXBT.

二維壓縮感知觀測(cè)值的重構(gòu)同樣可用l0范數(shù)最小化和全變差最小化方法等實(shí)現(xiàn).文獻(xiàn)[7]將二者結(jié)合起來(lái)，提出了基于全變差正則化的二維梯度投影法，

min‖ΨXΨT‖0+ηTV(X) s.t.Y=AXBT,

(4)

式中：

為X的全變差.

應(yīng)用Lagrange乘子法，式(4)變?yōu)?/p>

λ[‖ΨXΨT‖0+ηTV(X)].

(5)

X(k+1)=X(k)-μL1(X(k))-

μλ[L2(X(k))+ηL3(X(k))].

(6)

因?yàn)槭?6)中的3個(gè)導(dǎo)數(shù)難以同時(shí)求解，所以算法采取對(duì)3個(gè)導(dǎo)數(shù)分別按次序求解的方法.

式(6)中L3(X(k))的微分為

L3(X(k))|i,j=

(7)

式中：δ為一小正數(shù).

應(yīng)用梯度下降法可實(shí)現(xiàn)最小全變差的求解

(8)

式中：步長(zhǎng)t的值由人工設(shè)置.

(9)

(10)

式中：A+,B+分別為A,B的偽逆.

2.2 改進(jìn)的二維梯度投影法

在二維梯度投影方法中，式(8)應(yīng)用梯度下降法求解最小全變差的解時(shí)，搜索步長(zhǎng)是人為設(shè)置的固定值，難以取得搜索步長(zhǎng)的最優(yōu)值，不利于最優(yōu)解的估計(jì)與算法的快速收斂.因此本文首先使用回溯線搜索方法自適應(yīng)確定梯度下降法的搜索步長(zhǎng)值，將此改進(jìn)方法稱為基于回溯線搜索的二維梯度投影法(2DPG_BTLS)，該方法的實(shí)現(xiàn)步驟如算法1所示.

算法1：

輸入：稀疏基Ψ∈RN×N，測(cè)量矩陣A∈RM×N，B∈RM×N，迭代步數(shù)k=1，誤差容限ε，最大迭代次數(shù)Iter及α,β,δ的值.

步驟1：計(jì)算壓縮觀測(cè)值Y∈RM×M，與X的初始值X(0)=A+Y(B+)T.

步驟2：設(shè)置初始步長(zhǎng)t=1并計(jì)算優(yōu)化搜索步長(zhǎng)

while (L3(X(k)-L3(X(k)) )>L3(X(k))-αtL3(X(k))TΔX(k))

t=βt

endwhile

步驟6：k=k+1.

步驟7：若k≤Iter且‖X(k)-X(k-1)‖F(xiàn)/‖X(k-1)‖F(xiàn)>ε，返回步驟2，否則，停止迭代.

輸出：X(k+1).

本文進(jìn)一步改進(jìn)了算法1中X的最小全變差的求解方法，改進(jìn)方法對(duì)算法1中步驟2～3用以下步驟代替.

t=βt

endwhile

改進(jìn)方法除以上改變外，其余各步驟保持不變，構(gòu)成了基于新的步長(zhǎng)搜索判斷方法的二維梯度投影法，將此方法簡(jiǎn)稱為改進(jìn)方法.實(shí)驗(yàn)結(jié)果表明，該方法能進(jìn)一步提高重構(gòu)圖像的PSNR值和算法的收斂速度.

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

實(shí)驗(yàn)1比較了2DPG方法、2DPG_BTLS方以及改進(jìn)方法對(duì)各圖像在不同壓縮采樣率下壓縮測(cè)量值的重構(gòu)結(jié)果的PSNR值，結(jié)果如表 1 所示.測(cè)量數(shù)M變化使壓縮采樣率M/N在0.5～0.9之間變化.測(cè)量矩陣A,B都是均值為0，方差為1的高斯矩陣.實(shí)驗(yàn)圖像X∈R256×256，即N=256.在這3種方法中，實(shí)驗(yàn)的稀疏基Ψ都使用DTCWT矩陣，而不是原二維梯度投影法的DDWT矩陣.初始值δ=10-7，β=0.5，ε=10-4，Iter=103.從表 1 中的數(shù)值可見(jiàn)，與2DPG方法比較，2DPG_BTLS方法及改進(jìn)方法的重構(gòu)圖像的PSNR值都有很大提高，且改進(jìn)方法的大部分結(jié)果都優(yōu)于2DPG_BTLS方法的結(jié)果.

表 1 不同測(cè)量數(shù)下各重建圖像的PSNR值

實(shí)驗(yàn)2是3種方法的噪聲魯棒性比較.原圖像為256×256的Lena圖像，即X∈R256×256.測(cè)量矩陣A，B都是高斯矩陣，測(cè)量數(shù)M=154，壓縮采樣率為0.6.設(shè)圖像的壓縮測(cè)量值被加性高斯白噪聲Z污染，則含噪的壓縮測(cè)量值Y=AXBT+Z，高斯白噪聲Z∈R154×154的均值為0，其方差由Y的信噪比(Signal to Noise Ratio，SNR)決定，實(shí)驗(yàn)中Y的SNR的變化范圍為10～50 dB.實(shí)驗(yàn)結(jié)果如表 2 所示，每種方法的重構(gòu)圖像的PSNR值隨壓縮觀測(cè)值的信噪比的變化都很小，且與表 1 中壓縮采樣率為0.6時(shí)，Lena的無(wú)噪壓縮觀測(cè)的重構(gòu)結(jié)果PSNR值的差別也很小，說(shuō)明2DPG方法及兩個(gè)改進(jìn)方法都具有較強(qiáng)的噪聲魯棒性，這是因?yàn)?DPG方法本身就包含了去噪的步驟.在不同的SNR值下，改進(jìn)方法重構(gòu)圖像的PSNR值都是最高的.

表 2 含噪Lena圖像壓縮測(cè)量的重建結(jié)果PSNR值比較

圖 1 是Lena圖像無(wú)噪與含噪壓縮觀測(cè)值的重構(gòu)結(jié)果比較.圖1(a)是256×256的原始圖像，測(cè)量矩陣A，B都是高斯矩陣，M=102，即壓縮采樣率約為0.4.圖 1(b)～(c)是當(dāng)SNR=10 dB 時(shí)用2DPG方法和改進(jìn)方法得到的重構(gòu)圖像的比較.與2DPG方法相比，改進(jìn)方法的PSNR和SSIM值也得到了提高.

圖 1 含噪壓縮觀測(cè)圖像重構(gòu)結(jié)果比較Fig.1 The image recovery results comparison for noisy compressive observations

實(shí)驗(yàn)2中對(duì)算法的收斂性進(jìn)行了比較.實(shí)驗(yàn)圖像是Barbara，X∈R256×256，測(cè)量矩陣A，B都是高斯矩陣，M=128.其余初始值的取值與實(shí)驗(yàn)1相同.算法的收斂性結(jié)果如圖 2 所示.從圖 2 可以看出，改進(jìn)方法的誤差容限需迭代800步左右，而2DPG方法與2DPG_BTLS方法直到迭代步數(shù)達(dá)到程序允許的最大迭代次數(shù)103時(shí)，誤差容限仍大于實(shí)驗(yàn)中設(shè)置ε=10-4.因此改進(jìn)方法能夠提高重建圖像質(zhì)量.

圖 2 算法收斂性比較Fig.2 The convergence comparison of the three methods

4 結(jié) 論

二維梯度投影法是一種結(jié)合了l0范數(shù)最小化和全變差最小化方法的二維壓縮感知重構(gòu)方法，該方法用梯度下降法實(shí)現(xiàn)全變差最小化.本文用回溯線搜索法實(shí)現(xiàn)梯度下降法的優(yōu)化步長(zhǎng)選擇，提高了重建圖像的質(zhì)量.同時(shí)還提出了一種回溯線搜索法的改進(jìn)算法來(lái)實(shí)現(xiàn)最小全變差的求解，應(yīng)用該改進(jìn)算法能進(jìn)一步提高重建圖像的質(zhì)量以及算法的收斂性.但因?yàn)樗惴◤?fù)雜性提高，改進(jìn)算法與2DPG算法相比，需要更多的運(yùn)算時(shí)間，這是本文算法應(yīng)改進(jìn)之處.