多層離散小波變換系數(shù)的稀疏向量構(gòu)造的改進*

羅文東,田慕陽,張 萌

(東南大學電子工程學院,南京 210096)

多層離散小波變換系數(shù)的稀疏向量構(gòu)造的改進*

羅文東,田慕陽,張 萌*

(東南大學電子工程學院,南京 210096)

融合離散小波變換和壓縮感知的圖像壓縮方案很好避免了采用離散余弦變換和壓縮感知時所帶來的塊效應(yīng),但當前基于單層離散小波變換的算法壓縮比較低,基于多層離散小波變換的算法重構(gòu)質(zhì)量不佳。為了解決這些不足,根據(jù)離散小波變換系數(shù)的特點,對現(xiàn)有基于多層離散小波變換的算法提出了改進。圖像經(jīng)小波變換后,保留圖像最高層低頻系數(shù),高頻系數(shù)的構(gòu)造方式給予適當改進。實驗結(jié)果表明,與現(xiàn)有算法相比,重構(gòu)圖像的峰值信噪比PSNR(Peak Signal to Noise Ratio)值得到2 dB～4 dB提高。

圖像壓縮;壓縮感知;離散小波變換;稀疏向量

根據(jù)奈奎斯特采樣定理,傳統(tǒng)的信號采樣速率必須大于或等于被采樣信號帶寬的2倍,才能無失真地恢復(fù)模擬信號。當前信息需求量急劇增加,這種高速采樣的過程浪費了大量的資源。近年來,壓縮感知CS(Compressed Sensing)的出現(xiàn)突破了這一限制。壓縮感知理論使得信號采集的同時對數(shù)據(jù)進行壓縮,即感知壓縮了的信息。其核心思想是如果信號是可壓縮的或者在某個變換基上是稀疏的,那么就可以利用觀測矩陣將其投影到一個低維空間,獲得遠小于信號維度的測量值,再通過壓縮感知重構(gòu)算法求解出原始信號[1]。壓縮感知的出現(xiàn),給信號處理領(lǐng)域帶來了解決問題的新思路。

壓縮感知理論廣泛應(yīng)用于圖像壓縮處理中,但自然界的大部分信號并不都是稀疏的,使用壓縮感知的前提條件就是圖像是稀疏的,所以稀疏向量的構(gòu)造對整個圖像的壓縮重構(gòu)質(zhì)量起決定性的作用。幸運的是大部分自然信號,例如圖像、視頻和語音信號等,都能在特定的正交變換基上進行稀疏表示。對于圖像和視頻信號而言,典型的稀疏基包括離散余弦變換基、離散小波變換基等。離散余弦變換給圖像帶來明顯的塊效應(yīng)[2],離散小波變換可以克服這個缺點,而且離散小波變換還可以進行多層變換,使用起來更靈活。本文以多層離散小波變換為基礎(chǔ),對稀疏向量構(gòu)造算法存在不足提出了改進,改進后的算法能夠提升圖像的重構(gòu)質(zhì)量。

1 離散小波變換系數(shù)的稀疏向量研究

1.1 壓縮感知簡介

設(shè)x∈RN×1為一維信號,則其可以由一組正交基展開(例如小波基)Ψ={ψ1,ψ2,…,ψN},即

(1)

其中,yk=〈x,ψk〉。當信號x在某個基Ψ上僅有K?N個非零系數(shù)yk時,稱Ψ為信號x的稀疏基。

一般來說,信號經(jīng)過某種變換(如離散小波變換)之后,其系數(shù)可以認為是稀疏的。例如,對信號進行小波變換之后,可以通過保留其系數(shù)中的K個較大的分量,而把其他N-K個分量置零(因為這N-K個變換域系數(shù)對信號重構(gòu)的貢獻很小)。這樣,即可以認為信號x在小波基Ψ下是K稀疏的。對于信號x,可將其投影到一組測量向量Φ={φ1,φ2,…,φN}上,得到x的M個線性測量,即

s=Φx

(2)

式中:Φ為M×N矩陣,由此看到,壓縮感知將信號x從N維降為M維觀測信號s。對于給定的測量值s從式(2)求解是一個線性規(guī)劃問題。因K

(3)

Φ滿足RIP,就可以由s無失真地重構(gòu)出x。CS信號的重構(gòu)問題可以表示成求解0范數(shù)下的最優(yōu)化問題,然而求解0范數(shù)最優(yōu)化是個非確定性多項式難題(NP-hard),可將問題轉(zhuǎn)換為求解1最小范數(shù)下的最優(yōu)化問題:

(4)

1.2 單層離散小波變換稀疏向量的構(gòu)造

岑翼剛等[5]提出了基于單層離散小波變換的壓縮感知算法,保留圖像低頻系數(shù),只對高頻系數(shù)進行測量,重構(gòu)圖像質(zhì)量得到極大提升。Zhang Jin等[6]提出了一種行列平均的算法。單層離散小波變換后,低頻部分不做處理,分別對3個子塊HLl、LHl和HHl的各行測量、重構(gòu);再對3個子塊的各列做測量、重構(gòu),最后求平均,重構(gòu)圖像。該方法克服了只對行或者列進行處理而忽略圖像是二維的缺點。榮雁霞等[7]根據(jù)圖像小波變換系數(shù)的特點,將圖像分塊思想與小波變換相結(jié)合,提出一種基于離散小波變換的分塊壓縮感知算法。每一個圖像塊經(jīng)小波變換后,保留圖像低頻系數(shù),只對高頻系數(shù)進行觀測。實驗結(jié)果表明,與不分塊壓縮感知算法相比,重構(gòu)圖像的PSNR值有2 dB～4 dB的提高,重構(gòu)時間明顯減少。與基于二維離散余弦變換的分塊壓縮感知算法相比,塊效應(yīng)有明顯的改善,重構(gòu)質(zhì)量明顯提高。上述3種算法只做單層離散小波變換,低頻系數(shù)占圖像的比例還是較大,造成圖像的壓縮比低。

1.3 多層離散小波變換稀疏向量的構(gòu)造

Mohit Kalra等[8]提出的多層離散小波變換構(gòu)造稀疏向量的方法。其實是借用了SPIHT算法中的父子關(guān)系。我們知道離散小波變換第1層的3個高頻系數(shù)是最稀疏的,越往上系數(shù)絕對值越大,如圖1所示,這種在水平方向不同層次分別取1個、4個、16個系數(shù)的關(guān)系能很好滿足多層離散小波變換構(gòu)造稀疏向量的要求。

圖1 Kalra稀疏向量構(gòu)造算法

Mohamed Deriche和Muhammad Ali Qureshi等[9]對Mohit Kalra的算法提出了改進,把同一相對位置的水平分量,垂直分量,對角分量依次組合成新的稀疏向量(因為Mohit Kalra首先提出這種組合多層離散小波系數(shù)的算法,為敘述方便,之后我們把如圖1所示的構(gòu)造算法叫做Kalra構(gòu)造算法)。圖1以16×16圖像為例,做了3層離散小波變換,最高層低頻系數(shù)取a1,然后分別是水平方向21(1+4+16)個b1,垂直方向21個c1,對角方向21個d1組成一個長度為64的向量,依次取完共有4個這樣的向量。該方法雖然增加了向量的長度,但是同一相對位置的水平、垂直和對角分量組合在一起容易造成絕對值大的數(shù)據(jù)的集中,構(gòu)造的向量會有較多的不稀疏。

Muhammad Ali Qureshi和Mohamed Deriche等[10]原創(chuàng)性地提出了一種在多層離散小波變換下構(gòu)造稀疏向量的方法。經(jīng)過離散小波變換,該文獻提出的構(gòu)造稀疏矩陣的方法就是先分塊,然后取出每一塊相同位置的元素構(gòu)成列向量(為敘述方便,之后我們把它叫做Qureshi構(gòu)造算法)。如圖2所示,經(jīng)過了兩層變換,分成了相同的16塊。構(gòu)造的稀疏向量也只有16個元素。3層變換的稀疏向量也只有64個元素。但是該方法構(gòu)造的向量所含元素太少,會有較多向量不滿足稀疏性要求。

圖2 Qureshi稀疏向量構(gòu)造算法

2 改進算法

為了驗證我們對稀疏向量構(gòu)造的改進,我們首先給出了圖像壓縮重構(gòu)的流程圖,如圖3所示。

圖3 圖像壓縮重構(gòu)的流程圖

具體步驟如下:

(1)原始圖像經(jīng)多層離散小波變換,除最高層的低頻系數(shù),其他我們可以認為基本稀疏。為了后續(xù)的壓縮感知算法對稀疏性的要求,我們設(shè)定一個閾值,對于絕對值小于閾值的系數(shù),我們直接量化為零。

(2)構(gòu)造一系列的稀疏向量。采用文獻Kalra或Qureshi構(gòu)造算法構(gòu)造一系列稀疏向量。

(3)為了便于后續(xù)的硬件實現(xiàn),測量矩陣選用了滿足RIP的伯努利矩陣,它只含有1和-1兩種元素。稀疏向量與伯努利矩陣相乘得到了維度更小的向量,數(shù)據(jù)得到了壓縮。

(4)通過OMP算法對向量進行重構(gòu),得到測量前的稀疏向量,稀疏向量重新組合后經(jīng)離散小波逆變換,最后得到了重構(gòu)的圖像。

論文的重點放在對稀疏向量構(gòu)造的改進。兩種構(gòu)造算法在相同離散小波變換層數(shù)時,得到的向量個數(shù)相同,每一個稀疏向量的元素個數(shù)相同,所以我們的改進算法適用于兩種構(gòu)造算法。改進的算法如下:

最高層的低頻系數(shù)保留。保留最高層低頻系數(shù)在不太影響壓縮比的情況下,能提升重構(gòu)質(zhì)量。比如經(jīng)過3層變換,最高層低頻系數(shù)占整個圖像的1/64,而且系數(shù)絕對值大,不利于稀疏向量的構(gòu)造。

Kalra和Qureshi構(gòu)造算法構(gòu)造的列向量分成N組,依次提取不同組相同位置的向量組成更長的新向量。如圖4所示,相同顏色的向量為不同組的相同位置。分析發(fā)現(xiàn),按順序每N個組成一個列向量,有時候會連續(xù)好幾個向量的元素絕對值較大,構(gòu)造的向量會不稀疏。所以用該組合的方法能夠最大化打散向量,而且更長的向量有利于稀疏向量的構(gòu)造。

圖4 改進的組合方式

對于256×256圖像,以3層離散小波變換為例,保留最高層低頻系數(shù)后一共有1 024個向量,每個向量含63個元素。下面給出分組數(shù)和向量元素個數(shù)的關(guān)系。

表1 不同分組數(shù)構(gòu)造的元素個數(shù)

3 仿真結(jié)果

為驗證文中改進算法的性能,選取標準測試圖像Lena 256×256。觀測矩陣選取伯努利隨機矩陣,重構(gòu)算法采用OMP算法。在測量比MR(M/N)分別為0.2、0.3、0.4、0.5、0.6、0.7和0.8的情況下取得數(shù)據(jù),畫出曲線圖,形成對比,如圖5所示。

通過折線圖我們可以看到,兩種稀疏向量構(gòu)造算法經(jīng)改進后,PSNR都有明顯的提升,總體而言,Qureshi構(gòu)造算法改進后最優(yōu)。為了形象表示改進后的效果,我們在MR為0.5時得到截圖,如圖6所示。

圖5 不同構(gòu)造算法重構(gòu)質(zhì)量折線圖

圖6 MR為0.5時不同算法重構(gòu)圖像對比 (a)是原始圖像,(b)是Kalra構(gòu)造算法的效果圖,(c)是Kalra構(gòu)造算法改進后的效果圖。(d)是Qureshi構(gòu)造算法的效果圖,(e)是Qureshi構(gòu)造算法改進后的效果圖。

對比圖片可明顯看出改進算法對兩種構(gòu)造算法的提高。

同時我們還對改進后的Qureshi構(gòu)造算法不同向量長度做了探究。我們?nèi)‰x散小波變換為3層條件下,不同向量長度取得的數(shù)據(jù)如表2所示。隨著向量長度的增加,PSNR會不斷增大,這是因為長向量得到稀疏向量的概率更大。

表2 不同向量長度圖像重構(gòu)質(zhì)量

進一步對不同層數(shù)的離散小波變換對重構(gòu)質(zhì)量的影響進行了探究?？刂葡蛄吭貫?52個條件下,不同層數(shù)離散小波變換結(jié)果如表3所示。

表3 不同小波變換層數(shù)圖像重構(gòu)質(zhì)量

可以看出,越高層的小波變換系數(shù)絕對值越大,構(gòu)成的向量也越不稀疏。

4 結(jié)語

與傳統(tǒng)稀疏向量構(gòu)造算法相比,本文通過保留最高層的低頻系數(shù)以及分組提取的方法優(yōu)化了稀疏向量構(gòu)造算法。通過在MATLAB平臺仿真表明,在相同測量比的條件下我們可以得到更清晰的圖像,充分證明了改進的稀疏向量構(gòu)造算法優(yōu)于Kalra和Qureshi構(gòu)造算法。同時我們還對不同長度的向量、不同層數(shù)小波變換對重構(gòu)質(zhì)量的影響進行了探究,得出的數(shù)據(jù)有一定的參考價值。

[1] 任越美,張艷寧,李映. 壓縮感知及其圖像處理應(yīng)用研究進展與展望[J]. 自動化學報,2014,40(8):1563-1575.

[2] Hasan K K,Ngah U K,Salleh M F M. Efficient Hardware-Based Image Compression Schemes for Wireless Sensor Networks:A Survey[J]. Wireless Personal Communications,2014,77(2):1415-1436.

[3] 崔佳鵬. 基于壓縮感知的圖像壓縮技術(shù)研究與實現(xiàn)[D]. 哈爾濱:哈爾濱工業(yè)大學信息與電氣工程學院,2013.

[4] 尹宏鵬,劉兆棟,柴毅,等. 壓縮感知綜述[J]. 控制與決策,2013,28(10):1441-1445.

[5] 岑翼剛,陳曉方,岑麗輝,等. 基于單層小波變換的壓縮感知圖像處理[J]. 通信學報,2010,31(8A):52-55.

[6] Zhang J,Xia L,Huang M,et al. Image Reconstruction in Compressed Sensing Based on Single-Level DWT[C]//Proc of the IEEE Workshop on Electronics,Computer and Applications(IWECA). Ottawa,IEEE,2014:941-944.

[7] 榮雁霞,邱曉暉. 基于小波變換的分塊壓縮感知算法[J]. 計算機技術(shù)與發(fā)展,2015,25(5):29-32.

[8] Kalra M,Ghosh D. Image Compression Using Wavelet Based Compressed Sensing And Vector Quantization[C]//Proc of the 11th International Conference on Signal Processing(ICSP). Beijing,IEEE,2012:640-645.

[9] Deriche M,Qureshi M A,Beghdadi A. An Image Compression Algorithm Using Reordered Wavelet Coefficients with Compressive Sensing[C]//Proc of the 5th International Conference on Image Processing,Theory,Tools and Applications(IPTA). Orleans,IEEE,2015:498-503.

[10] Qureshi M A,Deriche M. A New Wavelet Based Efficient Image Compression Algorithm Using Compressive Sensing[J]. Multimedia Tools and Applications,2016,75(12):6737-6754.

An Improved Reconstruction to Sparse Vector for the Coefficient of Multilayer Discrete Wavelet Transform*

LUOWendong,TIANMuyang,ZHANGMeng*

(Southeast University,Nanjing 210096,China)

The image compression scheme which combines discrete wavelet transform and compressed sensing has overcome the block effect brought by the discrete cosine transform and compressed sensing. But the algorithm based on single layer discrete wavelet transform causes the low compression ratio,and the algorithm based on multilayer discrete wavelet transform causes a poor refactoring quality. In order to solve these problems,employing the characteristics of discrete wavelet transform coefficients,the better algorithm based on multilayer scheme is proposed. After the discrete wavelet transform,reserving the low frequency coefficients at the highest level,the method to reconstruct the high frequency coefficient is appropriately improved. Compared with the existing algorithms,the experimental results of the proposed algorithm show that the PSNR(Peak Signal to Noise Ratio)of reconstructed image was improved about 2 dB～4 dB.

image compression;compressed sensing;discrete wavelet transform;sparse vector

項目來源:江蘇省普通高校研究生科研創(chuàng)新計劃項目(SJLX15_0095,SJLX16_0081);東南大學研究生教改項目(XJGKT14-01);本科教改項目(2013-033);江蘇高校品牌專業(yè)建設(shè)工程項目

2016-07-28 修改日期:2016-09-25

C:6140C

10.3969/j.issn.1005-9490.2017.02.029

TN941

A

1005-9490(2017)02-0405-05