葉坤濤，楊國珂，賀文熙

（江西理工大學(xué)理學(xué)院，江西贛州341000）

一種最速下降的貪婪迭代算法

葉坤濤，楊國珂，賀文熙

（江西理工大學(xué)理學(xué)院，江西贛州341000）

壓縮傳感應(yīng)用于圖像壓縮重構(gòu)的算法通常有凸優(yōu)化算法和貪婪迭代算法兩大類.一般而言，凸優(yōu)化算法重構(gòu)概率高、速度較慢，貪婪迭代算法具有較快的重構(gòu)速度，但損失了重構(gòu)質(zhì)量.結(jié)合凸優(yōu)化算法中的最速下降法及貪婪迭代算法中的正交匹配算法（OMP），提出了一種新的算法，并應(yīng)用于一維信號(hào)和二維圖像信號(hào)的壓縮重構(gòu)實(shí)驗(yàn)，且深入對比分析了不同降采樣矩陣對新算法的影響.結(jié)果發(fā)現(xiàn)，對同一降采樣矩陣，即使圖像的紋理不同，新算法在重構(gòu)質(zhì)量及重構(gòu)時(shí)間上都優(yōu)于原始的OMP算法.

壓縮傳感；凸優(yōu)化算法；貪婪迭代算法；最速下降法；正交匹配算法

0 引言

在圖像壓縮重構(gòu)方面，人們都希望找到更好的壓縮重構(gòu)方法，使得圖像的重構(gòu)效果提高，即相同壓縮比的情況下，重構(gòu)圖像的信噪比提高、重構(gòu)速度加快.近年來，壓縮傳感理論在圖像領(lǐng)域的應(yīng)用研究逐漸深入，取得了較好的進(jìn)展[1].

壓縮傳感理論應(yīng)用于圖像壓縮重構(gòu)的研究，是圍繞三個(gè)方面來開展的，分別是信號(hào)稀疏基和稀疏方法的改進(jìn)、降采樣矩陣的改進(jìn)、以及重構(gòu)算法的改進(jìn).

對圖像使用不同的稀疏基和稀疏方法，可以得到不同的重構(gòu)效果.例如，2010年，岑翼剛等[2]提出

了基于單層小波變換的圖像稀疏方法，對圖像進(jìn)行一層小波稀疏后，分別對三個(gè)高頻進(jìn)行壓縮重構(gòu)，再和低頻部分結(jié)合重構(gòu)圖像，得到了更好的重構(gòu)信噪比.2010年，練秋生等[3]按照圖像可分成卡通部分和紋理部分，卡通部分又分為平滑成分和邊緣結(jié)構(gòu)的理論，對這三個(gè)部分，分別運(yùn)用不同的稀疏基重構(gòu)，得到更好的重構(gòu)信噪比.2012年，尹曉慧等[4]對DCT層式壓縮重構(gòu)進(jìn)行改進(jìn)，即保留層式DCT變換的最高層系數(shù)，只對其余層高頻子帶系數(shù)進(jìn)行壓縮重構(gòu)，提高了重構(gòu)信噪比.

傳統(tǒng)的降采樣矩陣有隨機(jī)高斯矩陣、局部傅里葉矩陣等，而選取不同的降采樣矩陣，也將獲得不同的重構(gòu)速度和重構(gòu)質(zhì)量[5].例如：2013年，汪博峰等[6]根據(jù)圖像進(jìn)行小波變換后低頻成分集中在左上角的特點(diǎn)，提出了一種優(yōu)化降采樣矩陣的方法，可以提高重構(gòu)質(zhì)量和重構(gòu)速度.2013年，楊海蓉[7]提出了稀疏帶狀測量矩陣的概念，并按列對圖像重構(gòu)，解決了圖像轉(zhuǎn)換成一列時(shí)生成降采樣矩陣較大的問題，在保證重構(gòu)質(zhì)量的情況下，計(jì)算速度大大提升.

壓縮傳感的重構(gòu)算法，同樣也對圖像的重構(gòu)效果有深刻影響.最速下降法、牛頓迭代法等凸優(yōu)化算法，以及正交匹配追蹤算法（OMP）、正則化正交匹配追蹤算法（ROMP）等貪婪算法的應(yīng)用，都對圖像等信號(hào)的重構(gòu)效果產(chǎn)生了不同影響.一般來說，凸優(yōu)化算法的重構(gòu)值更精確，耗時(shí)更長，而貪婪算法在損失一定的精確度的前提下使得重構(gòu)速度相對較快，易于實(shí)現(xiàn)[8].

研究工作是圍繞重構(gòu)算法的改進(jìn)來開展的.結(jié)合凸優(yōu)化算法中的最速下降法和貪婪算法中的OMP算法的優(yōu)點(diǎn)而得到了一種新的算法.對改進(jìn)算法和原始OMP算法，在不同降采樣矩陣的情況下，進(jìn)行了深入的對比分析.仿真實(shí)驗(yàn)結(jié)果表明，在重構(gòu)質(zhì)量提高的同時(shí)，新算法還可以提高重構(gòu)速度，且保留了貪婪算法易于實(shí)現(xiàn)的優(yōu)點(diǎn).

研究首先對算法的重構(gòu)流程和思想給出詳細(xì)論述，然后將其應(yīng)用于一維信號(hào)及二維圖像的壓縮重構(gòu)，且對重構(gòu)效果進(jìn)行分析，得到新算法具有更快的執(zhí)行速度及得到更好的信噪比的結(jié)論.

1 最速下降的貪婪迭代算法

由壓縮傳感理論，已知測量值y，測量矩陣（降采樣矩陣）為R，稀疏基為φ，可以通過求解式（1）來近似的重構(gòu)出原信號(hào)的稀疏表示x，將φ乘以x就能得到重構(gòu)的信號(hào)[9]:

實(shí)際中存在誤差問題時(shí)，式（1）被轉(zhuǎn)換為式（2）：

式（2）同樣又可以轉(zhuǎn)換為無約束的最優(yōu)化問題式（3）：

式（3）中，λ是一個(gè)正則化的參數(shù)，控制模型的收斂速度.

1.1 OMP算法

采用OMP的算法求解式（2）的流程如下[10].

輸入：傳感矩陣Φ，觀測向量y，稀疏度K

輸出：稀疏解x，殘差r，迭代次數(shù)iter

初始化：r＝y(tǒng)，重構(gòu)稀疏解x0，索引集合I＝Φ，迭代次數(shù)iter=0.

2）計(jì)算相關(guān)系數(shù)u=ΦTr，求出u中所得值的最大值，并將其對應(yīng)的索引值存入索引集J中；

3）對J中索引值對應(yīng)的原子存入集合I中，同時(shí)將Φ中該索引值對應(yīng)的原子置0；

4）I=J∪I，得到支撐集ΦI；

5）利用最小二乘得到近似解x=（ΦTIΦI）-1ΦTIy；

6）更新迭代殘差r=y-ΦIx，轉(zhuǎn)步驟1.

1.2 最速下降法

若式（3）看成是一個(gè)多元函數(shù)f（x）的無約束優(yōu)化問題，其尋優(yōu)表達(dá)式可以用式（4）表示[11]：

其中，

每次的最優(yōu)迭代步長tk通過求解式（6）獲得.

1.3 算法的改進(jìn)

文獻(xiàn)[12]指出，用以上最速下降法求解問題（3）時(shí)，本質(zhì)上和OMP 算法一樣，都是致力于使得每次迭代的重建誤差‖y－Φx‖22最小. 且可證明迭代誤差函數(shù)最小，可以等價(jià)為正定二次型函數(shù)的優(yōu)化問題，即式（7）[12]:

對式（7）求導(dǎo)得式（9）:

針對如上正定二次型函數(shù)，同樣能夠得到最速迭代步長tk的表達(dá)形式：

因?yàn)閠k和pk都能用傳感矩陣及殘差表示，所以結(jié)合2.1節(jié)的OMP算法和2.2節(jié)的最速下降法，可以得到一新算法.新算法中使用式（4）對x進(jìn)行更新，殘差的更新公式為：

這樣，新算法的流程為.

輸入：傳感矩陣Φ，觀測向量y，稀疏度K

輸出：稀疏解x，殘差r，迭代次數(shù)iter

初始化：r=y，重構(gòu)稀疏解x0，索引集合I=?，迭代次數(shù)iter=0；

2）計(jì)算相關(guān)系數(shù)u=ΦTr，求出u中所得值得最大值，并將其對應(yīng)的索引值存入索引集J中；

3）對J中索引值對應(yīng)的原子存入集合I中，同時(shí)將Φ中該索引值對應(yīng)的原子置0；

4）I=J∪I，得到支撐集ΦI；

5）利用式（4）更新x，xk+1=xk+tkpk；

6）更新迭代殘差rk+1=rk-ΦItkpk，轉(zhuǎn)步驟1.

2 仿真結(jié)果

2.1 一維信號(hào)

對改進(jìn)的算法進(jìn)行了仿真測試.實(shí)驗(yàn)平臺(tái)搭建在內(nèi)存為2G的臺(tái)式機(jī)上，使用的軟件工具為Matlab2012.首先構(gòu)造一個(gè)N=512，K=50的一維信號(hào)，降采樣矩陣采用隨機(jī)高斯矩陣.每個(gè)實(shí)驗(yàn)結(jié)果都是采用100次實(shí)驗(yàn)的平均值.實(shí)驗(yàn)結(jié)果如圖1、圖2、圖3所示.

圖1 殘差隨迭代次數(shù)變化

圖1 反映的是殘差范數(shù)‖rk‖2隨迭代次數(shù)變化的關(guān)系圖，殘差范數(shù)隨迭代次數(shù)增加，呈指數(shù)減小的趨勢，即算法的收斂速度較快.隨殘差范數(shù)的減小，信號(hào)的重構(gòu)質(zhì)量提高，當(dāng)殘差范數(shù)減小到設(shè)定的閾值時(shí)，跳出算法的迭代，最后得到的結(jié)果即為重構(gòu)信號(hào).

圖2為重構(gòu)概率隨采樣個(gè)數(shù)的變化關(guān)系圖.由圖2可知，圖像的重構(gòu)概率隨著采樣個(gè)數(shù)的增加而增加，采樣個(gè)數(shù)增加到120，重構(gòu)概率達(dá)到100%，即原始信號(hào)可視為被精確重構(gòu).

圖2 信號(hào)重構(gòu)概率隨采樣個(gè)數(shù)變化

圖3 給出的是取采樣個(gè)數(shù)為120時(shí)的重構(gòu)信號(hào)與原始信號(hào)的對比圖.可以看出，此時(shí)重構(gòu)信號(hào)的包絡(luò)與原始信號(hào)的包絡(luò)完全重合，表示信號(hào)被精確重構(gòu).

圖3 原始信號(hào)與恢復(fù)信號(hào)對比

2.2 圖像實(shí)驗(yàn)

同樣的改進(jìn)算法被應(yīng)用于圖像的壓縮重構(gòu).圖像實(shí)驗(yàn)中的稀疏基采用離散小波基，原始圖像采用256×256的Lena圖像，降采樣矩陣分別采用高斯隨機(jī)矩陣，置亂哈達(dá)瑪矩陣及局部傅里葉矩陣，并進(jìn)行對比分析.

將新算法與原始OMP算法從運(yùn)行時(shí)間及信噪比兩方面進(jìn)行對比分析.重構(gòu)圖像的方法采用文獻(xiàn)[7]按列重構(gòu)思想.利用常用的峰值信噪比作為重構(gòu)質(zhì)量的評斷標(biāo)準(zhǔn)，若x為原始圖像，x?為重構(gòu)圖像，峰值信噪比的定義公式為：

在壓縮比為0.5的情況下，實(shí)驗(yàn)結(jié)果如表1所示.表1中的實(shí)驗(yàn)結(jié)果均為算法運(yùn)行100次的平均值.

表1 各測量矩陣時(shí)的新算法與OMP的對比

由表1可知，在壓縮比為0.5的情況下，降采樣矩陣無論采用高斯隨機(jī)矩陣、置亂哈達(dá)瑪矩陣還是局部傅里葉矩陣，新算法不僅在信噪比上都優(yōu)于OMP算法，而且重構(gòu)時(shí)間也縮減.另外，表1還反映出采用不同的降采樣矩陣，同一算法有不同的重構(gòu)效果.

為了全面比較不同情況的重構(gòu)效果，圖4、圖5、圖6給出了在不同的壓縮比時(shí)，降采樣矩陣分別為隨機(jī)高斯矩陣、置亂哈達(dá)瑪矩陣和局部傅里葉矩陣時(shí)，新算法的重構(gòu)質(zhì)量、重構(gòu)時(shí)間，與原OMP算法的比較.

圖4 隨機(jī)高斯矩陣時(shí)重構(gòu)信噪比和時(shí)間隨壓縮比變化

圖5 置亂哈達(dá)瑪矩陣時(shí)重構(gòu)信噪比和時(shí)間隨壓縮比變化

圖6 局部傅里葉矩陣時(shí)重構(gòu)信噪比和時(shí)間隨壓縮比變化

從圖4、圖5、圖6看出隨壓縮比增加，不同降采樣矩陣下，新算法與OMP算法的重構(gòu)時(shí)間都變

大，信噪比也都提高.特別是，對同一降采樣矩陣，新提出的算法無論在重構(gòu)信號(hào)的信噪比和重構(gòu)時(shí)間上，都優(yōu)于OMP算法.其中采用隨機(jī)高斯矩陣與置亂哈達(dá)瑪矩陣時(shí)，相比于局部傅里葉矩陣，具有較快的重構(gòu)速度，但采用局部傅里葉矩陣可得到更好的重構(gòu)質(zhì)量.

為了驗(yàn)證新算法對不同紋理圖像的重構(gòu)效果都優(yōu)于OMP算法，分別對Cameraman、Peppers、Boat這三幅紋理細(xì)節(jié)越來越復(fù)雜的256×256的圖像進(jìn)行壓縮重構(gòu)實(shí)驗(yàn)，重構(gòu)效果如圖7所示.

圖7 三幅圖像的重構(gòu)效果對比（壓縮比=0.5）

圖7 中的重構(gòu)實(shí)驗(yàn)，采用的壓縮比為0.5，使用的降采樣矩陣為局部傅里葉矩陣，圖像所得重構(gòu)時(shí)間T及信噪比P都是重構(gòu)該圖像所得的值.

顯然，對于Cameraman圖像，新算法重構(gòu)的圖像得到了更小的人眼可分辨的噪聲區(qū)域.對于Boat圖像，新算法重構(gòu)的圖像比OMP算法重構(gòu)的

圖像具有更少的模糊紋理.對于Peppers圖像，雖然人眼很難區(qū)分出不同的重構(gòu)效果，但PNSR與重構(gòu)時(shí)間的數(shù)據(jù)仍表明新算法更優(yōu)越.

3 總結(jié)

結(jié)合凸優(yōu)化算法中的最速下降法及貪婪迭代算法中的OMP算法得出一種新的算法，通過實(shí)驗(yàn)分析得出針對不同的降采樣矩陣和不同圖像，新算法在重構(gòu)效果及重構(gòu)時(shí)間上都優(yōu)于OMP算法.新算法的不足之處在于，雖然相比于OMP算法，信噪比有提高，但提高的幅度較小.類似的，結(jié)合正則化正交匹配算法（ROMP）與凸優(yōu)化算法，還可以進(jìn)一步的提高重構(gòu)速度及質(zhì)量.

[1]李樹濤,魏丹.壓縮傳感綜述[J].自動(dòng)化學(xué)報(bào),2009,35（11）: 1369-1376.

[2]岑翼剛,陳曉方,岑麗輝，等.基于單層小波變換的壓縮感知圖像處理[J].通信學(xué)報(bào),2010,31（8）:51-55.

[3]練秋生,陳書貞.基于混合基稀疏圖像表示的壓縮傳感圖像重構(gòu)[J].自動(dòng)化學(xué)報(bào),2010,36（3）:385-391.

[4]尹曉慧,張寶菊,王為，等.基于改進(jìn)層式DCT的壓縮感知圖像處理[J].計(jì)算機(jī)工程,2012,38（9）:226-227.

[5]張成,楊海蓉,韋穗，等.基于隨機(jī)間距稀疏Toeplitz測量矩陣的壓縮傳感[J].自動(dòng)化學(xué)報(bào),2012,38（8）:1362-1369.

[6]汪博峰,曹漢強(qiáng).一種基于離散小波基的壓縮傳感測量矩陣優(yōu)化方法[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34（9）:2193-2196.

[7]楊海蓉,方紅,張成，等.基于稀疏帶狀矩陣的二維圖像重構(gòu)[J].計(jì)算機(jī)工程與應(yīng)用,2013,49（10）:184-187.

[8]李珅,馬彩文,李艷，等.壓縮感知重構(gòu)算法綜述[J].紅外激光工程,2013,42（1）:225-232.

[9]Donoho D L．Compressedsensing[J].IEEETransactionson Information Theory，2006,52（4）:1289-1306.

[10]Tropp J A，Gilbert A C.Signal recovery from random measurementsviaorthogonalmatchingpursuit[J].IEEE Transactions on Information Theory，2007,53（12）:4655-4666.

[11]龍建輝,胡錫炎,張磊.最速下降法解二次矩陣方程[J].湖南大學(xué)學(xué)報(bào)（自然科學(xué)版）,2008,38（4）:85-88.

[12]周燦梅．基于壓縮感知的信號(hào)重構(gòu)算法研究[D]．北京:北京交通大學(xué),2010.

Greedy iterative algorithm of the steepest descent

YE Kuntao,YANG Guoke,HE Wenxi
(School of Science,Jiangxi University of Science and Technology,Ganzhou 341000,China)

When Compressed Sensing(CS)model is applied to the compression-reconstruction of the image, the solving algorithm usually can be categorized as convex optimization algorithm and greedy iterative algorithm.In general,the convex optimization algorithm has a higher reconstruction rate but a slower speed, while the greedy iterative algorithm has a faster speed with a loss of the reconstruction quality.Based on one of convex optimization algorithm,the Orthogonal Matching Algorithm(OMP),and one of greedy iterative algorithm,the steepest descent method,a new algorithm is proposed in this paper.And the new algorithm is applied to one dimensional signal and two-dimensional image signal for compression-reconstruction experiments.The different downsampling matrix effect of this algorithm is also analyzed.Results show that for the same downsampling matrix,the new algorithm is better than the original OMP algorithm both in terms of the reconstruction quality and the reconstruction time when applied for images with different textures.

compressed sensing;convex optimization algorithm;greedy iterative algorithm;the steepest descent method;orthogonal matching algorithm

TP391

A

2014-07-07

國家人社部2011年高層次留學(xué)人才回國資助項(xiàng)目（2011481）；江西省教育廳科技資助項(xiàng)目（GJJ11468）

葉坤濤（1972-），男，博士，副教授，主要從事MEMS、光譜測量與儀器等方面的研究，E-mail:kuntaoye@126.com.

2095-3046（2014）05-0073-06

10.13265/j.cnki.jxlgdxxb.2014.05.014