基于CS的灰度圖像壓縮

張習(xí)民，卓東風(fēng)，劉國洋，李秋果

(1.河南教育學(xué)院物理系，河南鄭州450046;2.太原科技大學(xué)電子信息工程學(xué)院，山西太原 030024)

基于CS的灰度圖像壓縮

張習(xí)民1，2，卓東風(fēng)2，劉國洋2，李秋果2

(1.河南教育學(xué)院物理系，河南鄭州450046;2.太原科技大學(xué)電子信息工程學(xué)院，山西太原 030024)

采用較新的壓縮感知理論，通過Harr正交稀疏變換和伯努利采樣矩陣，實現(xiàn)了對灰度圖像的低速壓縮采樣，并利用正交匹配追蹤算法實現(xiàn)壓縮數(shù)據(jù)的恢復(fù).實驗結(jié)果表明，此算法能較好地實現(xiàn)圖像的感知壓縮.

Harr小波;壓縮感知;稀疏;非自適應(yīng);正交匹配追蹤

0 引言

在傳統(tǒng)的圖像壓縮采樣過程中，為了避免信號失真，采樣頻率不得低于信號最高頻率的2倍.這種高速采樣再壓縮的過程浪費(fèi)了大量的采樣資源，能否采用一種新的方法，使得在保證信息不損失的情況下，用遠(yuǎn)低于奈奎斯特采樣定理要求的速率采樣信號，同時又能實現(xiàn)信號的恢復(fù)，成為研究的熱點(diǎn).近年來，一種新興的壓縮感知理論為數(shù)據(jù)采集恢復(fù)技術(shù)帶來了革命性的突破.該理論指出如果信號本身是可壓縮的，那么可以用遠(yuǎn)低于奈奎斯特頻率進(jìn)行采樣，并恢復(fù)原圖像［1］.本文在介紹壓縮傳感理論知識的基礎(chǔ)上，首先采用Harr正交變換，實現(xiàn)對圖像的稀疏處理，運(yùn)用伯努利采樣矩陣實現(xiàn)圖像的投影采樣，由正交匹配追蹤(Orthogonal Math Persuit，OMP)實現(xiàn)對圖像的復(fù)原.

1 壓縮傳感基本原理

斯坦福大學(xué)的統(tǒng)計學(xué)家DAVID DONOHO(美國科學(xué)院院士)［2］、CANDES［3］及華裔數(shù)學(xué)家陶哲軒(TAO T)等人于2004年提出了一種新的信息獲取指導(dǎo)理論［4］，即壓縮感知(Compressive Sensing，或Compressed Sensing、Compressed Sampling，CS).文獻(xiàn)直到2006年才發(fā)表.CANDES證明了只要信號在某一個正交空間具有稀疏性，就能以較低的頻率采樣，而且可以以高概率重構(gòu)該信號.

運(yùn)用壓縮感知原理對信號進(jìn)行壓縮采樣的前提是信號必須稀疏，因為并不是所用的信號都能滿足該條件，但大多信號經(jīng)過適當(dāng)?shù)淖儞Q條件可以滿足.所以壓縮感知的第一步工作就是對原始的信號進(jìn)行某種正交變換，使信號在變換域中稀疏.如，我們考慮一維空間RN中一個有限長度的數(shù)字信號x，可以把它看做一個N×1的列向量.對該信號可以用一組正交基進(jìn)行稀疏變換，

這里，ψ是一個正交基矩陣［ψ1ψ2…ψN］，s是N×1的列向量，權(quán)值系數(shù)si=＜x，ψi＞=ψx，顯然，x和s都能代表信號，只不過x為時域(或空間域)，而s為ψ域.如果變換后的信號s含有k個較大的非零值，就可以說信號x是k稀疏的.

其次，用一個觀測矩陣φ對信號x進(jìn)行測量，得到觀測值y，

其中φ是一個M×N的矩陣，經(jīng)過變換后的信號由RN壓縮到RM空間(M＜N)，實現(xiàn)了對原始信號的降維處理，在這個過程中采樣和壓縮是同時進(jìn)行的.

關(guān)鍵是觀測矩陣φ的選擇，它應(yīng)該是非自適應(yīng)的，也就是說φ的選擇是固定不變的，獨(dú)立于信號x，并且觀測矩陣的設(shè)計要保障信號變換前后重要的信息不會被破壞，即保證能從M個觀測值y中恢復(fù)x［5］.

為此，觀測矩陣應(yīng)滿足約束等容條件(Restricted Isometry Property，RIP)，如式(3)

即變換要保證k個重要分量的長度.Baraniuk給出約束等容性的等價條件是:測量矩陣φ和稀疏化正交矩陣ψ的基不相關(guān)，能滿足約束等容條件的測量矩陣可以是獨(dú)立同分布的高斯矩陣，也可以是伯努利分布的矩陣，且滿足M＞cklog(N/k)能重構(gòu)原信號.本文采用的是后者.

2 信號的重構(gòu)算法

若已知的條件為測量矢量y，觀測矩陣φ及稀疏化正交矩陣ψ，希望重構(gòu)出k稀疏的信號s，信號的重構(gòu)可求解如下的欠定方程組完成

該問題的求解可轉(zhuǎn)化為l0范數(shù)的問題

但是解決方程(5)需要窮舉出s中所有的k個非零位置值，至少需要ckN種可能，因而l0范數(shù)下的優(yōu)化方法是一個NP問題.可以把問題轉(zhuǎn)化為求l1范數(shù)以簡化運(yùn)算［6］，

該優(yōu)化算法是一個凸優(yōu)化的過程，可以簡化為線性規(guī)劃的問題.可以通過BP(Basic Pursuit)算法、MP(Match Pursuit)算法來完成.本文對圖像的重構(gòu)采用正交匹配追蹤(OMP算法)來完成.

3 圖像壓縮感知及復(fù)原的步驟

本文實現(xiàn)的是二維灰度圖形的感知壓縮，所用的圖像為256×256的Cameraman灰度圖像，圖像為bmp格式，8位位深.為便于表示，原圖像用矩陣的形式記為X.

3.1 由Harr小波實現(xiàn)對原始圖像的稀疏變換.

為了更好地實現(xiàn)壓縮，對原圖進(jìn)行四級Harr正交變換，以增加其稀疏性，同時應(yīng)用結(jié)構(gòu)簡單的Harr小波基也能簡化運(yùn)算.本文使用Matlab編制了子函數(shù)HarrMatrix()實現(xiàn)對原圖像的四級Harr變換.變換后的矩陣記為Z，原圖及變換后的結(jié)果見圖1.

圖1 Cameraman原圖及Harr變換圖Fig.1Original image of Cameraman and its Harr transforming images

3.2 測量矩陣的選擇

在滿足約束等容條件時，采用伯努利對稱分布形式的測量矩陣C以簡化運(yùn)算.生成該矩陣的Matlab語句為“C=binornd(1，.5，M，b);”，M，b分別為測量矩陣的大小，M代表行，b代表列.因為變換域圖像一列的較大系數(shù)值(k值)處于30～40(相對于256)之間，根據(jù)公式M＞cklog(N/k)，為3～4倍的k值，所以M取為192.這樣，便能生成滿足條件的測量矩陣，其大小為192×256.

3.3 利用正交匹配追蹤算法恢復(fù)Harr變換后圖像

利用測量矩陣同時完成對變換域圖像(四級Harr變換后的圖像)的采樣和壓縮，若采樣后的數(shù)據(jù)用矩陣Y表示，則

該過程對大小為256×256圖像實現(xiàn)了192×256的低速采樣.

利用OMP算法［7］對信號進(jìn)行恢復(fù)時，已知的條件為:采樣觀測值Y，觀測矩陣C，需要恢復(fù)的信號為Z.數(shù)據(jù)恢復(fù)采用的方法是逐列形式，即用Y中的第n列，通過觀測矩陣用OMP算法恢復(fù)出Z中對應(yīng)的第n列.

對于Z中第n列的恢復(fù)方法如下:

(1)令殘差向量r=Yn，Yn代表觀測值中的第n列;

(2)用觀測矩陣C各行與r進(jìn)行內(nèi)積運(yùn)算＜r，Ci＞，i=1，…，256，找出內(nèi)積最大一列(相似度與r最強(qiáng))Cl，列號為l;

(3)用最小二乘法獲得Z中第n列第l位置上的元素值

(4)修正殘差值

在觀測矩陣C中剔除掉Cl列，返回第2步確定Z的第n列中下一個待定元素值及位置，直到待定出該列全部的k個元素，該列其余位置置0.

此時，即完成Z矩陣一列數(shù)據(jù)的恢復(fù).其他各列的恢復(fù)亦如此.待Z矩陣成功恢復(fù)后，可以通過Harr逆變換恢復(fù)出原圖像矩陣X.

4 實驗結(jié)果對比

我們利用上面所說的方法實現(xiàn)對Cameraman的壓縮采樣，復(fù)原后的結(jié)果見圖2.圖2(b)是用本文方法得到的恢復(fù)圖像，可以看出恢復(fù)質(zhì)量已較好，雖然低速采用中存在一定的噪聲.復(fù)原后圖像的峰值信噪比為30.9，和同等條件下用sym8小波、高斯觀測矩陣下復(fù)原圖(圖2(c))相比，復(fù)原圖像的質(zhì)量明顯優(yōu)于后者，而后者的峰值信噪比為27.8.

圖2 壓縮感知前后圖像對比Fig.2Comparisons of images before and after CS

5 總結(jié)

壓縮感知理論以一種非自適應(yīng)實現(xiàn)對圖像的低速采樣，打破了Nyquist香濃采樣定理的極限，并能較好地實現(xiàn)信號的恢復(fù).但壓縮感知理論在降低采樣率的同時，卻是以較高的運(yùn)算復(fù)雜度為代價的.作為一種較新的理論，壓縮感知理論正被廣泛地關(guān)注著，新的思路、新的算法不斷出現(xiàn)，正以旺盛的生命力向前發(fā)展.

［1］RICHARD G.B Compressive sensing［J］.IEEE Signal Processing Magazine，2007，24(4):118－121.

［2］DONOHO D L.Compressed sensing［J］.IEEE Transactions on Information Theory，2006，52(4):1289－1306.

［3］CAND E'S E.Compressive sampling［C］//EMAMNUEL J C.Proceedings of International Congress of Mathematicians.Switzerland:European Mathematical Society Publishing House，2006:1433－1452.

［4］CAND E'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.

［5］MARCO F D，MARK A D，DHARMPAL T，et al.Single-pixel imaging via compressive sampling［J］.IEEE Signal Processing Magazine，2008: 83－91.

［6］李樹濤，魏丹.壓縮傳感綜述［J］.自動化學(xué)報:2009，35(11):1369－1375.

［7］MALLAT S，ZHANG Z.Matching pursuit with time-frequency dictionaries［J］.IEEE Trans On Signal Processing，1993，41(12):3397－3415.

Gray Image Compression Based on CS

ZHANG Xi-min1，2，ZHUO Dong-Feng2，LIU Guo-yang2，LI Qiu-guo2

(1.Department of Physics，Henan Institute of Education，Zhengzhou 450046，China; 2.School of Electronic Information Engineering，Taiyuan University of Science and Technology，Taiyuan 030024，China)

By new theory of compression sensing，realizes compressing gray image at a lower sampling rate through Harr sparse orthogonal transformation and Bonuli observation matrix，and restores compressed data by algorithm of orthogonal match pursuit.The experiments show that this method realizes compression sensing quite well.

Harr wavelet;compression sensing;sparse;non-adaptive;orthogonal match pursuit

TP391.41

A

1007－0834(2011)03－0037－03

10.3969/j.issn.1007－0834.2011.03.013

2011－04－27

河南省教育廳自然科學(xué)研究計劃項目(2009B510007)

張習(xí)民(1972—)，男，河南寶豐人，河南教育學(xué)院物理系講師、太原科技大學(xué)電子信息工程學(xué)院在讀碩士研究生.