基于壓縮感知理論的圖像壓縮技術(shù)研究

王辛悅，周德全

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

1 引言

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

壓縮感知采用非自適應(yīng)性投影來保持信號(hào)的原始結(jié)構(gòu)，能夠通過數(shù)值最優(yōu)化問題準(zhǔn)確重構(gòu)原始信號(hào)。壓縮感知理論主要包括信號(hào)的稀疏表示、隨機(jī)測量和重構(gòu)算法等三個(gè)方面。稀疏表示是應(yīng)用壓縮感知的先驗(yàn)條件，隨機(jī)測量是壓縮感知的關(guān)鍵過程，重構(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ù)的絕對值近似為0，所得到的變換向量S是稀疏的或者近似稀疏的［2］。則壓縮感知方程為:y=?×x=?×Ψ×s=Θ×s。通過該變換可將原來的測量矩陣Φ變換為傳感矩陣Θ=?×Ψ，解出s的逼近值?，則原信號(hào)x^=Ψ×?，從而實(shí)現(xiàn)了信號(hào)x的稀疏表示。

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

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

其中，Y為M維觀測向量，Φ為M×N維的觀測矩陣。但要想使信號(hào)完全重構(gòu)，必須保證觀測矩陣不會(huì)把兩個(gè)不同的K項(xiàng)稀疏信號(hào)映射到同一個(gè)采樣集合中，這就要求從觀測矩陣中抽取的每M個(gè)列向量構(gòu)成的矩陣是非奇異的。測量矩陣要滿足三個(gè)特征:①由測量矩陣的列向量組成的子矩陣的最小奇異值必須大于一定的常數(shù);②測量矩陣的列向量體現(xiàn)某種類似噪聲的獨(dú)立隨機(jī)性;③滿足稀疏度的解是滿足1范數(shù)最小的向量。獨(dú)立同分布的高斯隨機(jī)測量矩陣可以成為普適的壓縮感知測量矩陣。但是，它在硬件實(shí)現(xiàn)和重建算法構(gòu)造上卻難以實(shí)用。相對高斯矩陣等硬件上較難實(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為長度M的一維測量值。壓縮感知重構(gòu)問題就是在已知測量值Y和測量矩陣Φ的基礎(chǔ)上，求解方程組Y=Φ×X，得到原信號(hào)X。需要求解如下最優(yōu)化問題［5-6］:

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

求解。常用的優(yōu)化方法有線性規(guī)劃(BP)算法和匹配追蹤算法［7］或正交匹配追蹤算法(OMP)［8］等貪婪算法。要精確重構(gòu)K稀疏信號(hào)X，測量次數(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位置的非零元，且在該位置的測量向量逼近為:

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

目前基于CS理論的重建算法主要分成四類:凸優(yōu)化方法、組合算法、統(tǒng)計(jì)優(yōu)化方法和貪婪算法。貪婪算法是4類算法中重建速度最快的算法。另外，在CS理論中，由于圖像重建過程可以看作已知信號(hào)在給定冗余字典上獲得最稀疏分解的過程，而貪婪算法在信號(hào)稀疏化中的應(yīng)用較為成熟。現(xiàn)準(zhǔn)備利用OMP算法重構(gòu)圖像。OMP算法通過遞歸的對已選原子集合正交化求出正交投影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)對圖像進(jìn)行測量壓縮，式(2)中的觀測矩陣采用高斯隨機(jī)矩陣，然后利用介紹的OMP算法重構(gòu)圖像。在測量率(測量值個(gè)數(shù)與原圖像像素個(gè)數(shù)之比)分別為0.7、0.5、0.3 時(shí)，效果如圖1所示。

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

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

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

5 結(jié) 束 語

主要介紹了cs理論用于信號(hào)壓縮及重構(gòu)時(shí)所涉及的信號(hào)稀疏表示、隨機(jī)測量矩陣設(shè)計(jì)、信號(hào)重構(gòu)算法三大核心問題。并給出了CS理論框架下的圖像壓縮與基于OMP算法的圖像重構(gòu)結(jié)果。通過對二維圖像信號(hào)lean的實(shí)驗(yàn)證明壓縮感知理論是一種測量值少而信號(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.