基于分塊的壓縮重建方法

肖 馳，田小霞,2

(1.韓山師范學(xué)院計算機和信息工程學(xué)院,廣東潮州 521041；2.汕頭大學(xué)工學(xué)院，廣東汕頭 515063)

?

基于分塊的壓縮重建方法

肖 馳1，田小霞1,2

(1.韓山師范學(xué)院計算機和信息工程學(xué)院,廣東潮州 521041；2.汕頭大學(xué)工學(xué)院，廣東汕頭 515063)

圖像的壓縮重建是當(dāng)前圖像處理中的研究熱點，本文提出了一種基于分塊壓縮的重建方法，該方法首先將圖像分成尺寸相同的圖像塊，在一定的壓縮比下各塊獨自完成SL0重建，最后將各圖像塊的重建結(jié)果拼接成整幅圖像.圖像塊的尺寸與整幅圖像的重建時間和質(zhì)量有密切關(guān)系.塊尺寸大，重建時間長；塊尺寸小，塊效應(yīng)影響圖像質(zhì)量.文中對由尺寸較小圖像塊組成的重建圖像進(jìn)行維納濾波，消弱了塊效應(yīng)并提高了圖像視覺效果.仿真實驗結(jié)果顯示該方法具有重建時間短和壓縮質(zhì)量高的優(yōu)勢.

SL0壓縮；塊壓縮；維納濾波；

最近，Donoho[1]和Candès等[2]提出了壓縮感知理論(Compression Sensing，CS ).它將采集少量的信號用一個與變換基不相關(guān)的觀測矩陣投影到一個低維空間，再通過相應(yīng)重建算法實現(xiàn)了少量投影的精確重建[1-3].它突破了香農(nóng)采樣定理的瓶頸，使得采樣數(shù)據(jù)量小，采樣時間短，避免數(shù)據(jù)存儲空間資源浪費.

近年來壓縮感知在圖像領(lǐng)域上獲得了迅猛發(fā)展[4-5]，但是圖像尺寸的大小影響其應(yīng)用.對尺寸較大的圖像進(jìn)行觀測和重建時，其觀測矩陣也大，這導(dǎo)致其時間和空間復(fù)雜度增大[6].Candes等[7]提出了結(jié)構(gòu)化隨機矩陣，但實現(xiàn)過程比較復(fù)雜，也不易實現(xiàn).Lu[8]提出了分塊壓縮感知算法(Base-block CS，BCS)， BCS是把原始圖像分為尺寸相同的小圖像塊，這些圖像塊采用相同的觀測矩陣采樣，同時，在信號接收端分別對這些圖像塊進(jìn)行重建，組合成整幅圖像.由于觀測矩陣變小，時間和空間復(fù)雜度大大降低.對應(yīng)用系統(tǒng)來說，瘦身成功，易于傳輸.故這種技術(shù)在圖像應(yīng)用方面具有廣闊前景.

本文算法在SL0和BCS的基礎(chǔ)上提出，以BCS為框架，壓縮重建為優(yōu)化的SL0算法.

1 壓縮感知理論基礎(chǔ)

如果信號X是可以壓縮的或者在某個變換域上是高維稀疏的，那么可以用一個跟變換基Ψ不相干的測量矩陣φ對信號進(jìn)行非自適應(yīng)的、線性的和非相關(guān)的投影，得到測量值y，然后根據(jù)信號是稀疏的這個先驗信息，求解一個帶稀疏度約束的欠定方程組[9]

(1)

其中,x=ψα;ψ為稀疏變換基;α為稀疏系數(shù).如果矩陣A=ψα滿足URP(UniqueRepresentationProperty)，那么(1)式有唯一解.

L0范數(shù)的優(yōu)化是一個NP-Hard[10]，上述公式不能直接求解.但它的間接優(yōu)化算法卻很多，主要分為三類：貪婪迭代法，L1凸優(yōu)化和平滑SL0算法.

MP算法就是不斷地從冗余字典中選取與殘差最匹配的原子，同時在迭代過程中保證信號的殘差最小，再更新信號的擬合值，直到找到所有的原子.信號在選擇的原子上的投影不能確保是否正交，故MP算法不能保證一定可以收斂到全局的最優(yōu)解.Tropp和Gilbert提出了OMP算法[11]，OMP算法會在迭代的過程中對所選擇的原子做Schmidt正交化，這改善了重建性能.

基追蹤算法(BasisPursuit，BP)是用L1范數(shù)代替L0范數(shù)[12]，而L1范數(shù)的最優(yōu)化是一個凸優(yōu)化問題，因此必然有唯一解.(1)式就可以寫為：

(2)

將上述的凸優(yōu)化問題轉(zhuǎn)化成線性規(guī)劃問題(Linear Program，LP)加以求解.在重建過程中，該算法需要的測量值個數(shù)少，抗噪性能好，有比較高的重建精度.但 BP 算法的高計算復(fù)雜度會影響到該算法的大規(guī)模應(yīng)用.梯度投影算法(Gradient Projection for Sparse Reconstruction，GPSR)以梯度下降法作為基礎(chǔ)，每次迭代時，沿負(fù)梯度方向搜索，同時加入隱變量將原本不可微分的目標(biāo)函數(shù)變成帶邊界約束的凸二次規(guī)劃問題[13].GPSR 算法對信號的稀疏度沒有要求，但它的計算復(fù)雜度也相對較高.

另一種是SL0優(yōu)化算法， Mohimani 等提出了用平滑范數(shù)重建算法(Smoothed Norm，簡稱 SL0)來最小化范數(shù)[14].SL0算法主要利用連續(xù)的高斯函數(shù)族來擬合不連續(xù)的L0范數(shù)，然后利用最速下降法來對其最小化，最后對最小化的解進(jìn)行梯度投影使其符合約束條件.SL0 算法的計算復(fù)雜度為O(mn)，跟MP算法相當(dāng)，計算量小.不僅如此，SL0 算法還支持在盲稀疏度的情況下重建原信號.該算法既有貪婪算法的計算復(fù)雜度低的優(yōu)點，又具有凸優(yōu)化算法的準(zhǔn)確性.

2 塊壓縮

在現(xiàn)有的壓縮理論研究中，這些算法通常是將圖像的二維信號轉(zhuǎn)換成一維信號來處理，比如將N×N圖像的每一列首尾相接組成一個N2×1的列向量，這樣一維信號長度很大，導(dǎo)致需要壓縮感知的測量矩陣尺寸很大，使得重建過程占用巨大內(nèi)存，重建速度緩慢.Lu等[8]提出了分塊壓縮感知算法(Base-block CS，BCS),BCS利用分塊的思想解決圖像信號占用內(nèi)存巨大重建效果緩慢的問題.李蘊華[15]和李然等[16]也提出了分塊壓縮感知模型，前者是對不同塊的測量矩陣加權(quán)，后者引入排序算子對解碼端的隨機矩陣重新構(gòu)建.Abolghasemi等[17]提出測量矩陣尺寸變化的分塊法，在運行時間和重建質(zhì)量獲得了很好的效果.BCS提高了存儲和傳輸?shù)男剩诒ＷC重建質(zhì)量的情況下，縮短了重建時間.

2.1 BCS-SL0算法

該算法是基于BCS和SL0算法基礎(chǔ)上的壓縮感知優(yōu)化算法.它是將圖像劃分為i個n×n塊xi(i=2N/n，對各個子塊應(yīng)用相同的測量矩陣φ，得到觀測值向量yi，記為yi=φxi.其中φ為m×n，且m

(3)

將所得到各個塊的測量值在接收端重建該圖像.由于各塊采用相同重建算法，只需將得到的重建圖像簡單組合就得到整個重建圖像.

該算法的系統(tǒng)框架如圖1所示.

圖1 算法的系統(tǒng)框架圖

2.2 優(yōu)化SL0算法

(4)

(4)式是一個有約束條件的最優(yōu)化問題，通過拉格朗日乘子法將其轉(zhuǎn)化成不帶約束條件的最優(yōu)化問題

(5)

從而將離散函數(shù)的最優(yōu)化問題轉(zhuǎn)化成連續(xù)函數(shù)的最優(yōu)化問題，通過凸優(yōu)化的方法對其求解，在迭代過程中采用最速下降法和梯度投影原理，經(jīng)過多次迭代逐步逼近最優(yōu)解α′=AT(AAT)-1y.

3 仿真結(jié)果分析

圖2 Lena、Barbara和Baboon在不同壓縮比下峰值信噪比和運行時間對比

從圖2中可以看到,壓縮比低時，峰值信噪比隨塊尺寸變小而變差.在壓縮比高時，四種算法峰值信噪比沒有顯著差異，這是因為圖像分塊中有一些塊的重建信噪比高從而提高了整幅圖像的信噪比.四種算法的運行時間隨壓縮比增高而迅速增加.但在同一壓縮比下，四種算法的重建時間差異較大.從數(shù)值上看，(1×1)BCSSL0的重建時間幾乎是(2×2)BCSSL0的10倍，是(4×4)BCSSL0的100倍，是(8×8)BCSSL0的1000倍.其中(1×1)BCSSL0表示尺寸為512×512原圖整體壓縮重建；(2×2)BCSSL0表示將尺寸為512×512原圖分為4個256×256圖像塊的壓縮重建；(4×4)BCSSL0表示將尺寸為512×512原圖分為16個128×128圖像塊的壓縮重建；(8×8)BCSSL0表示將尺寸為512×512原圖分為64個64×64圖像塊的壓縮重建.本算法時間復(fù)雜度的優(yōu)勢得到充分的體現(xiàn).圖3給出了在0.5壓縮比下不同尺寸塊的重建效果.

圖3 在0.5壓縮比下不同尺寸塊的重建效果

從這些圖像對比中可以看出，視覺的差異不是很顯著，(1×1)BCSSL0重建圖像的峰值信噪比與(8×8)BCSSL0重建圖像的峰值信噪比多1 dB左右.

由于圖像分塊壓縮重建，重建圖像中會有塊效應(yīng).如Baboon圖像中眼睛下方的區(qū)域.圖像分塊重建產(chǎn)生塊效應(yīng)主要有三個原因：塊稀疏度不均勻、頻譜泄露和塊尺寸受限[16].為了減小塊效應(yīng)，本文對重建的圖像進(jìn)行維納濾波，得到的圖像視覺效果較好，但峰值信噪比略有降低.圖4為維納濾波后的重建圖像.

圖4 在0.5壓縮比和(8×8)BCSSL0下重建圖像的維納濾波效果

三個各有特點的圖像在分為不同尺寸的塊和不同壓縮比下，經(jīng)過維納濾波的重建圖像和未經(jīng)過維納濾波重建圖像的峰值信噪比對比見圖5所示.

圖5 在(8×8)BCSSL0下不同壓縮比的重建圖像和經(jīng)過維納濾波重建圖像的信噪比對比

4 結(jié)束語

本文提出的BCS-SL0方法集聚了BCS和SL0的優(yōu)點，不僅不需要預(yù)先設(shè)置信號的稀疏度，而且速度提高一個數(shù)量級.重建圖像的質(zhì)量雖略有下降，但對壓縮感知實時系統(tǒng)來說，這點可以接受；另一個問題是重建圖像的塊效應(yīng)，采用維納濾波對重建圖像過濾，雖視覺效果提升，但峰值信噪比略有下降了.在保證重建時間的情況下，提高重建質(zhì)量和視覺效果是下一步的研究目標(biāo).

[1] DONOHO D L.Compressed sensing[J].IEEETransactionsonInformationTheory,2006,52(4):1289.

[3] 閆敬文,劉蕾,屈小波.壓縮感知及應(yīng)用[M].北京：國防工業(yè)出版社，2015.

[4] 詹旭,馬將,付克蘭.基于壓縮傳感的灰度圖像水印算法[J].西北師范大學(xué)學(xué)報(自然科學(xué)版),2016,52(1):47.

[5] 李錦瓏,張維昭,馬宏鋒,等.基于 HA LCON 的車牌識別技術(shù)研究[J].西北師范大學(xué)學(xué)報(自然科學(xué)版),2015，51(6):54.

[6] CANDES E,ROMBERG J.Sparsity and incoherence in compressive sampling[J].InverseProblems,2007,23(3):969.

[7] CANDES E J,ROMBERG J,TAO T.Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information[J].IEEETransactionsonInformationTheory,2006,52(2):489.

[8] LU G.Block compressed sensing of natural images[C]//InternationalConferenceonDigitalSignalProcessing.Cardiff UK：IEEE,2007:403.

[9] FOWLER J E,MUN S,TRAMEL E W.Block-based compressed sensing of images and video[J].FoundationsandTrendsinSignalProcessing,2012,4(4):297.

[10] CANDES E J,TAO T.Decoding by linear programming[J].InformationTheory,IEEETransactions,2005,51(12):4203.

[11] TROPP J A,GILBERT A C.Signal recovery from random measurements via orthogonal matching pursuit[J].IEEETransactionsonInformationTheory,2007,53(12):4655.

[12] CHEN S S,DONOHO D L,SAUNDERS M A.Atomic decomposition by basis pursuit[J].SIAMJournalonScientificComputing,1998,20(1):33.

[13] FIGUEIREDO M A T,NOWAK R D,WRIGHT S J.Gradient projection for sparse reconstruction:application to compressed sensing and other inverse problems[J].SelectedTopicsinSignalProcessing,IEEE Journal of,2007,1(4):586.

[14] MOHIMANI H,BABAIE-ZADEH M,JUTTEN C.A fast approach for overcomplete sparse decomposition based on smoothed norm[J].SignalProcessing,IEEETransactionsonInformationTheory,2009,57(1):289.

[15] 李蘊華.一種改進(jìn)的圖像分塊壓縮感知模型[J].計算機工程與應(yīng)用，2011,47(25)：186.

[16] 李然,干宗良,朱秀昌.基于分塊壓縮感知的圖像全局重建模型[J].信號處理,2012,28(10):1416.

[17] ABOLGHASEMI V,FERDOWSI S,SANEI S.A block-wise random sampling approach:compressed sensing problem[J].JournalofAIandDataMining,2015，3(1)：93.

(責(zé)任編輯 孫對兄)

Compression reconstruction methods based on block

XIAO Chi1,TIAN Xiao-xia2

(1.College of Computer and Information Engineering,Hanshan Normal University,Chaozhou 521041,Guangdong,China;2.College of Engineering,Shantou University,Shantou 515063,Guangdong,China)

Image compression and reconstruction are a hot Copic in image processing.This paper presents a new reconstruction method based on block.The new method firstly divides the image into the same blocks according to a certain rule.Then it applies the SL0 algorithm to every block,which is reconstructed successively.Finally,we scrape up the whole from blocks.The size of the block can affect the time and quality of the reconstruction image.If the size of the block is too small that blocking artifacts do harm to the quality of the reconstruction image.In this paper,the Wiener filtering is employed to improve the quality of the reconstruction image which has many small blocks.The simulation results show that the method has the advantages of the reconstruction time and the compression quality.

SL0 compression method;block compressed sensing;Wiener filtering

10.16783/j.cnki.nwnuz.2016.06.011

2015-12-24;修改稿收到日期:2016-07-06

韓山師范學(xué)院學(xué)科建設(shè)專項基金(2013LYM0055);潮州市科技引導(dǎo)計劃項目(2012S13)

肖馳(1971—)，男，湖南邵陽人，講師.主要研究方向為圖像處理及軟件測試.

E-mail:553293364@qq.com

TP 391.4

A

1001-988Ⅹ(2016)06-0051-05