張習(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正交稀疏變換和伯努利采樣矩陣，實(shí)現(xiàn)了對(duì)灰度圖像的低速壓縮采樣，并利用正交匹配追蹤算法實(shí)現(xiàn)壓縮數(shù)據(jù)的恢復(fù).實(shí)驗(yàn)結(jié)果表明，此算法能較好地實(shí)現(xiàn)圖像的感知壓縮.

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

0 引言

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

1 壓縮傳感基本原理

斯坦福大學(xué)的統(tǒng)計(jì)學(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證明了只要信號(hào)在某一個(gè)正交空間具有稀疏性，就能以較低的頻率采樣，而且可以以高概率重構(gòu)該信號(hào).

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

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

其次，用一個(gè)觀測(cè)矩陣φ對(duì)信號(hào)x進(jìn)行測(cè)量，得到觀測(cè)值y，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 測(cè)量矩陣的選擇

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

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

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

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

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

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

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

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

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

(4)修正殘差值

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

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

4 實(shí)驗(yàn)結(jié)果對(duì)比

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

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

5 總結(jié)

壓縮感知理論以一種非自適應(yīng)實(shí)現(xiàn)對(duì)圖像的低速采樣，打破了Nyquist香濃采樣定理的極限，并能較好地實(shí)現(xiàn)信號(hào)的恢復(fù).但壓縮感知理論在降低采樣率的同時(shí)，卻是以較高的運(yùn)算復(fù)雜度為代價(jià)的.作為一種較新的理論，壓縮感知理論正被廣泛地關(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］.自動(dòng)化學(xué)報(bào):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é)研究計(jì)劃項(xiàng)目(2009B510007)

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