王辛悅，周德全

(浙江農(nóng)林大學(xué)信息工程學(xué)院，杭州 臨安 311300)

1 引言

從外界獲得的信息中，視覺(jué)信息占據(jù)了主導(dǎo)地位。而圖像以其生動(dòng)直觀的特點(diǎn)以及包含的豐富信息，成為人們獲得信息的主要工具。然而巨大的數(shù)據(jù)量給圖像的傳輸和存儲(chǔ)帶來(lái)了極大不便，圖像壓縮技術(shù)顯得尤為重要［1］。然而，在傳統(tǒng)的壓縮技術(shù)中采樣遵循奈奎斯特定律，采樣速率要高于原信號(hào)頻率的兩倍，這個(gè)過(guò)程浪費(fèi)了大量的采樣資源，加大了計(jì)算復(fù)雜度，也造成了不必要的內(nèi)存浪費(fèi)。而相較之下，近年來(lái)信號(hào)處理領(lǐng)域誕生的一種新的信號(hào)處理理論—壓縮感知理論［2-4］，針對(duì)可稀疏表示的信號(hào)，能夠?qū)?shù)據(jù)采集和數(shù)據(jù)壓縮合二為一，降低了計(jì)算復(fù)雜度，避免了不必要的空間浪費(fèi)，這使其在信號(hào)處理領(lǐng)域有著突出的優(yōu)點(diǎn)和廣闊的應(yīng)用前景。

壓縮感知采用非自適應(yīng)性投影來(lái)保持信號(hào)的原始結(jié)構(gòu)，能夠通過(guò)數(shù)值最優(yōu)化問(wèn)題準(zhǔn)確重構(gòu)原始信號(hào)。壓縮感知理論主要包括信號(hào)的稀疏表示、隨機(jī)測(cè)量和重構(gòu)算法等三個(gè)方面。稀疏表示是應(yīng)用壓縮感知的先驗(yàn)條件，隨機(jī)測(cè)量是壓縮感知的關(guān)鍵過(guò)程，重構(gòu)算法是獲取最終結(jié)果的必要手段。

2 壓縮感知理論

2.1 稀疏性

一般的自然信號(hào)X∈RN本身并不是稀疏信號(hào)，但一般可以在某種稀疏基上進(jìn)行稀疏表示，即:

其中，S為信號(hào)的稀疏系數(shù)。信號(hào)的稀疏表示就是將信號(hào)x投影到正交變換基Ψ時(shí)，大部分變換系數(shù)的絕對(duì)值近似為0，所得到的變換向量S是稀疏的或者近似稀疏的［2］。則壓縮感知方程為:y=?×x=?×Ψ×s=Θ×s。通過(guò)該變換可將原來(lái)的測(cè)量矩陣Φ變換為傳感矩陣Θ=?×Ψ，解出s的逼近值?，則原信號(hào)x^=Ψ×?，從而實(shí)現(xiàn)了信號(hào)x的稀疏表示。

2.2 測(cè)量矩陣設(shè)計(jì)

根據(jù)壓縮感知理論，通過(guò)變換得到信號(hào)的稀疏系數(shù)后，需要設(shè)計(jì)壓縮采樣系統(tǒng)的觀測(cè)部分，它圍繞觀測(cè)矩陣Φ展開(kāi)。測(cè)量過(guò)程可以表示為

其中，Y為M維觀測(cè)向量，Φ為M×N維的觀測(cè)矩陣。但要想使信號(hào)完全重構(gòu)，必須保證觀測(cè)矩陣不會(huì)把兩個(gè)不同的K項(xiàng)稀疏信號(hào)映射到同一個(gè)采樣集合中，這就要求從觀測(cè)矩陣中抽取的每M個(gè)列向量構(gòu)成的矩陣是非奇異的。測(cè)量矩陣要滿足三個(gè)特征:①由測(cè)量矩陣的列向量組成的子矩陣的最小奇異值必須大于一定的常數(shù);②測(cè)量矩陣的列向量體現(xiàn)某種類似噪聲的獨(dú)立隨機(jī)性;③滿足稀疏度的解是滿足1范數(shù)最小的向量。獨(dú)立同分布的高斯隨機(jī)測(cè)量矩陣可以成為普適的壓縮感知測(cè)量矩陣。但是，它在硬件實(shí)現(xiàn)和重建算法構(gòu)造上卻難以實(shí)用。相對(duì)高斯矩陣等硬件上較難實(shí)現(xiàn)的其他隨機(jī)矩陣形式，伯努利分布的±1矩陣成為構(gòu)建硬件可實(shí)現(xiàn)的壓縮感知方式的首選。

2.3 重構(gòu)算法

設(shè)X∈RN的稀疏度為K，Φ為M×N的二維矩陣(K＜M?N)，Y=Φ×X為長(zhǎng)度M的一維測(cè)量值。壓縮感知重構(gòu)問(wèn)題就是在已知測(cè)量值Y和測(cè)量矩陣Φ的基礎(chǔ)上，求解方程組Y=Φ×X，得到原信號(hào)X。需要求解如下最優(yōu)化問(wèn)題［5-6］:

這個(gè)過(guò)程稱之為重構(gòu)，式中‖X‖0為0范數(shù)。該優(yōu)化問(wèn)題屬于NP難題，一般轉(zhuǎn)化為，

求解。常用的優(yōu)化方法有線性規(guī)劃(BP)算法和匹配追蹤算法［7］或正交匹配追蹤算法(OMP)［8］等貪婪算法。要精確重構(gòu)K稀疏信號(hào)X，測(cè)量次數(shù)M(即Y的維數(shù))必須滿足采樣點(diǎn)數(shù)M=O(KlogN)的條件，并且矩陣Φ必須滿足約束等距性條件。

3 正交匹配追蹤算法

(3)令 Λt=Λt-1∪{λt};

(4)計(jì)算{λt:λ∈Λt}張成空間的正交投影Pt;

(5)計(jì)算新的近似a和冗余r:

(6)t=t+1，如果 t＜mt，則返回第(2)步;

(7)獲得的估計(jì)?λ在索引Λm位置的非零元，且在該位置的測(cè)量向量逼近為:

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

目前基于CS理論的重建算法主要分成四類:凸優(yōu)化方法、組合算法、統(tǒng)計(jì)優(yōu)化方法和貪婪算法。貪婪算法是4類算法中重建速度最快的算法。另外，在CS理論中，由于圖像重建過(guò)程可以看作已知信號(hào)在給定冗余字典上獲得最稀疏分解的過(guò)程，而貪婪算法在信號(hào)稀疏化中的應(yīng)用較為成熟。現(xiàn)準(zhǔn)備利用OMP算法重構(gòu)圖像。OMP算法通過(guò)遞歸的對(duì)已選原子集合正交化求出正交投影Pt，利用rt=y-Pty的殘差更新方式，克服了MP算法的次最優(yōu)性。OMP算法為:

(1)初始化冗余向量r0=y，索引集合Λ0=Φ，迭代計(jì)數(shù)t=1;

(2)找到索引λ0，使得:

以256×256大小的8bit灰度lena圖像做為原信號(hào)，首先利用式(2)對(duì)圖像進(jìn)行測(cè)量壓縮，式(2)中的觀測(cè)矩陣采用高斯隨機(jī)矩陣，然后利用介紹的OMP算法重構(gòu)圖像。在測(cè)量率(測(cè)量值個(gè)數(shù)與原圖像像素個(gè)數(shù)之比)分別為0.7、0.5、0.3 時(shí)，效果如圖1所示。

圖2給出了在不同測(cè)量率下重建圖像的峰值信噪比(PSNR)值。由圖2可知，當(dāng)測(cè)量率過(guò)低時(shí)，PSNR的值相對(duì)較低，表明重建圖像效果一般。仿真實(shí)驗(yàn)的結(jié)果表明，壓縮感知理論應(yīng)用于圖像壓縮領(lǐng)域是一項(xiàng)可行的技術(shù)。實(shí)際應(yīng)用中，采用壓縮感知理論進(jìn)行抽樣時(shí)，可直接對(duì)圖像進(jìn)行隨機(jī)抽樣，只需要得到少量的抽樣值，并對(duì)抽樣值進(jìn)行量化編碼就可以進(jìn)行傳輸或存儲(chǔ)。不必記錄每個(gè)有效值的位置信息并對(duì)其進(jìn)行編碼，這大大降低了計(jì)算復(fù)雜度，也避免了不必要的空間浪費(fèi)，最重要的是實(shí)現(xiàn)了低速采樣。

圖1 原圖與重構(gòu)圖像

圖2 psnr值與測(cè)量率的關(guān)系

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

主要介紹了cs理論用于信號(hào)壓縮及重構(gòu)時(shí)所涉及的信號(hào)稀疏表示、隨機(jī)測(cè)量矩陣設(shè)計(jì)、信號(hào)重構(gòu)算法三大核心問(wèn)題。并給出了CS理論框架下的圖像壓縮與基于OMP算法的圖像重構(gòu)結(jié)果。通過(guò)對(duì)二維圖像信號(hào)lean的實(shí)驗(yàn)證明壓縮感知理論是一種測(cè)量值少而信號(hào)恢復(fù)準(zhǔn)確的數(shù)據(jù)采集壓縮理論，表明壓縮感知理論在圖像壓縮方面具有重大意義。作為新興理論，壓縮感知理論的研究方興未艾，將具有更加廣泛的應(yīng)用前景。

［1］覃風(fēng)清.數(shù)字圖像壓縮綜述［J］.宜賓學(xué)院學(xué)報(bào)，2006(6):88-90.

［2］Donoho D L.Compressed Sensing［J］.IEEE Transactions on Information Theory，2006，52(4):1289-1306.

［3］石光明，劉丹華，高大化，等.壓縮感知理論及其研究進(jìn)展［J］.電子學(xué)報(bào)，2009，37(5):1070-1081.

［4］Cands E.Compressive Sampling［C］.Proceedings of International Congress of Mathematicians， Madrid，Spain，European Mathematic Society，2006:1433-1452.

［5］Baraniuk R G.Compressive sensing［J］.IEEE Signal Processing Magazine，2007，24(4):118-121.

［6］RaVel C Gonzalez.Richard E Woods，數(shù)字圖像處理［M］.北京:電子工業(yè)出版社，2010.

［7］Mallat S，Zhang Z.Matching pursuit with time-frequency dictionaries［J］.IEEE Transactions on Signal Processing，1993，41(12):3397-3415.

［8］Tropp J， GilbertA. Signalrecovery from random measurements via orthogonal matching pursuit［J］.IEEE Transactions on Information Theory，2007，53(12):4655-4666.