劉國(guó)慶， 林 京

（合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院，安徽 合肥 230009）

0 引 言

在傳統(tǒng)的信號(hào)采集過(guò)程中，為了避免信號(hào)失真及碼間干擾，一般都會(huì)遵循Nyquist采樣定理（又稱香農(nóng)采樣定理），它要求針對(duì)信號(hào)的采樣率不得低于信號(hào)帶寬的2倍。這無(wú)疑對(duì)信號(hào)處理的能力提出了較高的要求，也給相應(yīng)的硬件設(shè)備帶來(lái)了極大的挑戰(zhàn)，尋找新的數(shù)據(jù)采集和處理方法成為一種必然。文獻(xiàn)［1］提出的壓縮感知（Compressed Sensing，簡(jiǎn)稱CS）理論是一種充分利用信號(hào)稀疏性或者可壓縮性的全新信號(hào)獲取和處理理論，利用其他變換空間描述信號(hào)，使得在保證信息不損失的情況下，用遠(yuǎn)低于采樣定理要求的速率采樣信號(hào)的同時(shí)，又可完全恢復(fù)信號(hào)，即將對(duì)信號(hào)的采樣率轉(zhuǎn)變?yōu)閷?duì)信息的采樣，較大地降低了信號(hào)采樣頻率、信號(hào)處理時(shí)間和計(jì)算成本以及數(shù)據(jù)存儲(chǔ)和傳輸?shù)拇鷥r(jià)。

目前，基于小波的圖像處理技術(shù)，例如圖像壓縮及圖像融合［2－3］等已日臻成熟，而壓縮感知在圖像處理方面的應(yīng)用正在開展中。

文獻(xiàn)［4］根據(jù)圖像小波變換系數(shù)層的特點(diǎn)，提出了基于單層小波變換的壓縮感知算法，處理二維圖像。然而在許多實(shí)際應(yīng)用中，信號(hào)的稀疏度往往未知，本文對(duì)文獻(xiàn)［4］其算法進(jìn)行了改進(jìn)，提出了適應(yīng)稀疏度未知情況的基于單層小波變換的自適應(yīng)壓縮感知算法，并進(jìn)行了實(shí)驗(yàn)仿真。

1 壓縮感知與自適應(yīng)重建算法

設(shè)x∈RN×1為一維信號(hào)，則其可以由一組規(guī)范正交基Ψ＝｛ψ1，…，ψN｝展開（例如小波基）Ψ＝｛ψ1，…，ψN｝，即

其中，yk＝〈x，ψk〉，逆變換為y＝ΨHx，此處，ΨΨH＝ΨHΨ＝I，Ψ∈CN×N，I為單位矩陣。x和y是相同信號(hào)的等價(jià)表示，x是信號(hào)在時(shí)域的表示，y是信號(hào)x在Ψ域的表示。如果向量y的非零元素個(gè)數(shù)為K，則稱信號(hào)x在基Ψ 下是K－稀疏（K－Sparse）的；若在基Ψ下，y按照大小排序，以近似于冪律衰減，則稱信號(hào)x是可壓縮的。

對(duì)于信號(hào)x，可將其投影到一組測(cè)量向量Φ＝｛φ1，…，φM｝上，得到x的M 個(gè)線性測(cè)量，即

其中，Φ∈RM×N，Φ的每一行可以看做一個(gè)傳感器，它與信號(hào)相乘，拾取了信號(hào)的一部分信息，根據(jù)這M個(gè)測(cè)量和Φ，就可以重構(gòu)原始信號(hào)，將（1）式代入（2）式，得

其中，Θ＝ΦΨ為M×N矩陣。由此可知，壓縮感知將信號(hào)x從N 維降為M 維觀測(cè)信號(hào)s，由于（2）式中未知數(shù)個(gè)數(shù)N大于方程個(gè)數(shù)M，若直接求解（2）式來(lái)重構(gòu)信號(hào)不能得到確切解。而（3）式中的y是K－稀疏的，即僅有K 個(gè)非零系數(shù)，且K＜M≤N，則可通過(guò)已有的稀疏分解算法求解（3）式的逆問(wèn)題得到稀疏系數(shù)y，再通過(guò)（1）式得到重構(gòu)信號(hào)x。為保證算法的收斂性，（3）式的Φ必須滿足有限等距準(zhǔn)則［5］（Restricted Isometry Property，簡(jiǎn)稱RIP），即對(duì)于任意具有嚴(yán)格K－稀疏的向量v，Φ滿足：

其中，δ＞0。RIP準(zhǔn)則的一種等價(jià)情況是測(cè)量矩陣Φ和稀疏矩陣Ψ滿足不相關(guān)性的要求。對(duì)于CS理論，其逆變換重構(gòu)過(guò)程為求解l0范數(shù)下的最優(yōu)化（Optimization）問(wèn)題，即

而l0范數(shù)的求解是個(gè)NP－Hard問(wèn)題，因此可將問(wèn)題轉(zhuǎn)化為：

對(duì)于（6）式中l(wèi)1最小范數(shù)下的最優(yōu)化問(wèn)題，目前的求解算法有梯度投影法（GP）［6］、基追蹤法（BP）［7］、匹配類追蹤法［8］等，而應(yīng)用最廣的則屬匹配追蹤類方法，具有代表性的有正交匹配追蹤法（OMP）［9］、正則化正交匹配追蹤法［10］等，但上述算法都要求已知信號(hào)的稀疏度，給實(shí)際應(yīng)用帶來(lái)很大不便。文獻(xiàn)［11］提出了一種稀疏自適應(yīng)追蹤算法（SAMP），很好地解決了稀疏度未知的問(wèn)題。該算法描述如下。

輸入：傳感矩陣Φ，采樣向量y，步長(zhǎng)s。

輸出：未知輸入信號(hào)x的K－稀疏的逼近＾x。

初始化：＾x＝0，殘差r0＝y(tǒng)，支撐集F0＝?，支撐集大小l＝s，迭代次數(shù)k＝1，索引值j＝1；

循環(huán)執(zhí)行如下步驟：

（1）初測(cè)試Sk＝max（｜Φ＊rk－1｜，l）。

（2）計(jì)算候選集Ck＝Fk－1∪Sk。

（4）計(jì)算殘差r＝y(tǒng)－ΦFy。

（5）判斷是否滿足停止迭代條件，若滿足，則停止迭代，若不滿足，執(zhí)行步驟（5）。

（6）判斷是否滿足‖r‖2≥‖rk－1‖2，若滿足，執(zhí)行步驟（6）；若不滿足，執(zhí)行步驟（7）。

（7）進(jìn)入下一階段j＝j(luò)＋1，支撐集F的大小增加為l＝j(luò)×s。

（8）更新支撐集Fk＝F，殘差rk＝r，k＝k＋1。

2 基于單層小波變換的壓縮感知算法

在原有CS算法的圖像處理中，將N×N的圖像首先進(jìn)行某種變換，如DCT變換、小波變換等，然后構(gòu)造測(cè)量矩陣Φ，利用Φ對(duì)全部的小波變換系數(shù)進(jìn)行測(cè)量，得到M×N大小的測(cè)量系數(shù)。恢復(fù)圖像的時(shí)候，根據(jù)Φ和M×N大小的測(cè)量系數(shù)，通過(guò)OMP等算法恢復(fù)出原圖像。

由于小波分解將原圖像分為高頻子帶和低頻子帶，高頻子帶可以認(rèn)為是稀疏的，但低頻子帶是原圖像在不同尺度下的逼近信號(hào)，不能認(rèn)為是稀疏的，而將低頻與高頻系數(shù)一起與測(cè)量矩陣Φ相乘則會(huì)破壞低頻逼近分量系數(shù)之間的相關(guān)性，導(dǎo)致重構(gòu)效果變差。當(dāng)小波分解層次只有1層時(shí)，重構(gòu)的圖像已經(jīng)看不出原貌。因此，小波變換層次應(yīng)該盡可能大，一般對(duì)256×256的圖像分解層次應(yīng)該在4層以上。

文獻(xiàn)［4］提出了基于單層小波變換的CS改進(jìn)算法，首先只對(duì)原圖像進(jìn)行單層小波變換，然后只對(duì)第1層高頻子帶進(jìn)行測(cè)量，對(duì)低頻逼近子帶則保留小波分解的系數(shù)，最后對(duì)高頻系數(shù)測(cè)量值利用OMP算法進(jìn)行重構(gòu)，并與低頻子帶一起進(jìn)行小波反變換得到恢復(fù)的圖像。

3 單層小波變換的自適應(yīng)壓縮感知算法

在許多實(shí)際應(yīng)用中，圖像的稀疏度往往是未知的，因此本文在此基礎(chǔ)上提出了一種改進(jìn)算法，適應(yīng)稀疏度未知的情況。由于單層小波變換后高頻子帶具有如下特點(diǎn)：低高塊（垂直方向高頻子帶）具有行稀疏性，高低塊（水平方向高頻子帶）具有列稀疏性，因此本文在圖像恢復(fù)的過(guò)程中對(duì)低高塊逐行、高低塊逐列及高高塊（對(duì)角方向高頻子帶）整體處理，利用SAMP算法進(jìn)行自適應(yīng)重構(gòu)圖像。

（1）對(duì)N×N的圖像進(jìn)行一層小波分解，得到｛LL1，LH1，HL1，HH1｝4個(gè)小波子帶系數(shù)，其大小記為×。

（3）利用SAMP算法對(duì)LH′1逐列進(jìn)行重構(gòu)得，對(duì) HL′1逐行進(jìn)行重構(gòu)得，對(duì) HH′1整體進(jìn)行重構(gòu)得，將L、、與LL1一起進(jìn)行小波逆變換得到恢復(fù)的圖像。

4 仿真結(jié)果

對(duì)256×256的Lena圖像進(jìn)行試驗(yàn)，選取小波函數(shù)bior4.4對(duì)圖像進(jìn)行一層小波分解，則＝128，分別取 M／＝0.1、0.2、0.3、0.4、0.5進(jìn)行仿真。這里為簡(jiǎn)便起見，采用的測(cè)量矩陣為隨機(jī)矩陣（在實(shí)際應(yīng)用中，可以采用結(jié)構(gòu)化測(cè)量矩陣［12］來(lái)代替隨機(jī)矩陣），因此在仿真實(shí)驗(yàn)時(shí)，每次生成的測(cè)量矩陣均不相同，為更真實(shí)地重構(gòu)圖像，均運(yùn)行多次取均值，峰值信噪比見表1所列。其中，I＿OMP代表基于單層小波變換的壓縮感知算法，I＿SAMP代表本文的改進(jìn)算法。

表1 算法性能比較 dB

圖1 256×256圖像在M／＝20%時(shí)的恢復(fù)圖像

5 結(jié)束語(yǔ)

本文首先簡(jiǎn)要介紹了壓縮感知理論和稀疏自適應(yīng)追蹤算法，在單層小波變換壓縮感知的基礎(chǔ)上，根據(jù)圖像小波分解系數(shù)中低頻子帶的特點(diǎn)和高頻子帶的排列特征，提出了基于單層小波變換的自適應(yīng)壓縮感知改進(jìn)算法，很好地解決了稀疏度未知的問(wèn)題，仿真結(jié)果表明，本文算法取得了較好的效果，與單層小波變換的非自適應(yīng)壓縮感知算法相比，保證了重構(gòu)圖像效果，圖像質(zhì)量也得到很好的保證，PSNR相差不過(guò)2dB。

［1］ Donoho D.Compressed sensing［J］.IEEE Transactions on Information Theory，2006，52（4）：1289－1306.

［2］ Candès E.Compressive samplingg［C］／／Proceedings of the International Congress of Mathmaticians，Madrid，Panin，2006：1433－1452.

［3］ 張晶晶，方勇華，陳曉寧.基于小波的偏振圖像融合算法及性能評(píng)價(jià)［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，32（7）：1101－1105.

［4］ 岑翼剛，陳曉方，岑麗輝，等.基于單層小波變換的壓縮感知圖像處理［J］.通信學(xué)報(bào)，2010，31（8A）：52－55.

［5］ Candès E，Romberg J，Tao T.Robust uncertainty principles：exact signal reconstruction from highly incomplete frequency information［J］.IEEE Transactions on Information Theory，2006，52（2）：489－509.

［6］ Figueiredo M，Nowak R，Wright S.Gradient projection for sparse reconstruction：application to compressed sensing and other inverse problems［J］.IEEE Journal of Selected Topics in Signal Processing，2007，1（4）：586－597.

［7］ Chen S B，Donoho D L，Saunders M A.Atomic decomposition by basic pursuit［J］.SIAM Journal on Scientific Computing，1998，20（1）：33－61.

［8］ Mallat S，Zhang Z.Matching pursuits with time－frequency dictionaries［J］.IEEE Transactions on Signal Processing，1993，41（12）：3397－3415.

［9］ Tropp J，Gilbert A.Signal recovery from random measurements via orthogonal matching pursuit［J］.IEEE Transactions on Information Theory，2008，53（12）：4655－4666.

［10］ Needell D，Vershynin R.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit［J］.Foundations of Computational Mathematics，2009，9（3）：317－334.

［11］ Do T T，Lu Gan，Nguyen N，et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing［C］／／Asilomar Conference on Signals，Systems，and Computers，Pacific Grove，California，2008：581－587.