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

葉坤濤，楊國珂，賀文熙

（江西理工大學理學院，江西贛州341000）

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

葉坤濤，楊國珂，賀文熙

（江西理工大學理學院，江西贛州341000）

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

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

0 引言

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

壓縮傳感理論應用于圖像壓縮重構的研究，是圍繞三個方面來開展的，分別是信號稀疏基和稀疏方法的改進、降采樣矩陣的改進、以及重構算法的改進.

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

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

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

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

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

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

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

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

實際中存在誤差問題時，式（1）被轉換為式（2）：

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

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

1.1 OMP算法

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

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

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

初始化：r＝y，重構稀疏解x0，索引集合I＝Φ，迭代次數iter=0.

2）計算相關系數u=ΦTr，求出u中所得值的最大值，并將其對應的索引值存入索引集J中；

3）對J中索引值對應的原子存入集合I中，同時將Φ中該索引值對應的原子置0；

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

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

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

1.2 最速下降法

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

其中，

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

1.3 算法的改進

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

對式（7）求導得式（9）:

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

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

這樣，新算法的流程為.

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

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

初始化：r=y，重構稀疏解x0，索引集合I=?，迭代次數iter=0；

2）計算相關系數u=ΦTr，求出u中所得值得最大值，并將其對應的索引值存入索引集J中；

3）對J中索引值對應的原子存入集合I中，同時將Φ中該索引值對應的原子置0；

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

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

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

2 仿真結果

2.1 一維信號

對改進的算法進行了仿真測試.實驗平臺搭建在內存為2G的臺式機上，使用的軟件工具為Matlab2012.首先構造一個N=512，K=50的一維信號，降采樣矩陣采用隨機高斯矩陣.每個實驗結果都是采用100次實驗的平均值.實驗結果如圖1、圖2、圖3所示.

圖1 殘差隨迭代次數變化

圖1 反映的是殘差范數‖rk‖2隨迭代次數變化的關系圖，殘差范數隨迭代次數增加，呈指數減小的趨勢，即算法的收斂速度較快.隨殘差范數的減小，信號的重構質量提高，當殘差范數減小到設定的閾值時，跳出算法的迭代，最后得到的結果即為重構信號.

圖2為重構概率隨采樣個數的變化關系圖.由圖2可知，圖像的重構概率隨著采樣個數的增加而增加，采樣個數增加到120，重構概率達到100%，即原始信號可視為被精確重構.

圖2 信號重構概率隨采樣個數變化

圖3 給出的是取采樣個數為120時的重構信號與原始信號的對比圖.可以看出，此時重構信號的包絡與原始信號的包絡完全重合，表示信號被精確重構.

圖3 原始信號與恢復信號對比

2.2 圖像實驗

同樣的改進算法被應用于圖像的壓縮重構.圖像實驗中的稀疏基采用離散小波基，原始圖像采用256×256的Lena圖像，降采樣矩陣分別采用高斯隨機矩陣，置亂哈達瑪矩陣及局部傅里葉矩陣，并進行對比分析.

將新算法與原始OMP算法從運行時間及信噪比兩方面進行對比分析.重構圖像的方法采用文獻[7]按列重構思想.利用常用的峰值信噪比作為重構質量的評斷標準，若x為原始圖像，x?為重構圖像，峰值信噪比的定義公式為：

在壓縮比為0.5的情況下，實驗結果如表1所示.表1中的實驗結果均為算法運行100次的平均值.

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

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

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

圖4 隨機高斯矩陣時重構信噪比和時間隨壓縮比變化

圖5 置亂哈達瑪矩陣時重構信噪比和時間隨壓縮比變化

圖6 局部傅里葉矩陣時重構信噪比和時間隨壓縮比變化

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

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

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

圖7 三幅圖像的重構效果對比（壓縮比=0.5）

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

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

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

3 總結

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

[1]李樹濤,魏丹.壓縮傳感綜述[J].自動化學報,2009,35（11）: 1369-1376.

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

[3]練秋生,陳書貞.基于混合基稀疏圖像表示的壓縮傳感圖像重構[J].自動化學報,2010,36（3）:385-391.

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

[5]張成,楊海蓉,韋穗，等.基于隨機間距稀疏Toeplitz測量矩陣的壓縮傳感[J].自動化學報,2012,38（8）:1362-1369.

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

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

[8]李珅,馬彩文,李艷，等.壓縮感知重構算法綜述[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].湖南大學學報（自然科學版）,2008,38（4）:85-88.

[12]周燦梅．基于壓縮感知的信號重構算法研究[D]．北京:北京交通大學,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年高層次留學人才回國資助項目（2011481）；江西省教育廳科技資助項目（GJJ11468）

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

2095-3046（2014）05-0073-06

10.13265/j.cnki.jxlgdxxb.2014.05.014