基于多尺度的自適應采樣圖像分塊壓縮感知算法*

殷長濤，文志強，胡駿飛

(智能信息感知及處理技術湖南省重點實驗室, 湖南 株洲 412007)

基于多尺度的自適應采樣圖像分塊壓縮感知算法*

殷長濤，文志強，胡駿飛

(智能信息感知及處理技術湖南省重點實驗室, 湖南 株洲 412007)

基于分塊的壓縮感知算法適用于圖像信號的處理，通過平滑迭代閾值投影法可以快速重構(gòu)圖像，但存在低采樣率下重構(gòu)圖像質(zhì)量較差的缺點?；谌儾罘值姆謮K壓縮感知算法，在一定程度上能提升重構(gòu)效果，但降低了運算速度。針對以上算法的不足，提出基于多尺度的自適應采樣圖像分塊壓縮感知算法。根據(jù)小波分解后不同層對重構(gòu)結(jié)果影響所占權(quán)重不同的特性，自適應分配給每一層不同的采樣率，并在重構(gòu)時將平滑迭代閾值投影法應用到每一層的每一個子帶的分塊上。實驗結(jié)果表明，與傳統(tǒng)的迭代閾值投影法相比在重構(gòu)質(zhì)量上提高了1～3 dB，在重構(gòu)速度上與迭代閾值投影法相當并優(yōu)于全變差分法。

壓縮感知；多尺度；小波變換；自適應采樣；圖像分塊

0 引言

壓縮感知(Compresssive Sensing,CS)[1]最早是由DONOHO D等人提出的一種新的信號壓縮采樣方法。利用數(shù)據(jù)的冗余性，把原始信號通過觀測矩陣投影到低維空間，如果原始信號稀疏或是可壓縮的，則可以通過觀測值，利用凸優(yōu)化的方法很好地重構(gòu)出原始信號。

目前已有研究者將CS理論運用于圖像數(shù)據(jù)的獲取，但是實踐中發(fā)現(xiàn)，直接針對整幅圖像數(shù)據(jù)進行壓縮感知時所需要的觀測矩陣會占用很大的存儲空間，重構(gòu)時運算量過大，并且效果不理想。針對壓縮感知這個缺點，GAN L等人提出了分塊壓縮感知(Block Compressed Sensing，BCS)[2]理論，該理論首先將圖像分割成相同大小的圖像塊，再對每一小塊分別進行采樣重構(gòu)。MUN S等提出了分塊迭代閾值投影算法(BCS-SPL)[3],該算法通過將BCS理論與Landweber迭代法[4]相結(jié)合，并且加入了維納濾波過程，在加快了重構(gòu)速度的同時，也消除了分塊采樣所帶來的重構(gòu)結(jié)構(gòu)的快效應，很大程度上提高了分塊壓縮感知的可用性。蔡旭等人在文獻[3]的基礎上提出了基于全變差分自適應采樣率分塊壓縮感知算法(TV-BCS-SPL)[5],根據(jù)圖像塊全變差分的值判斷其紋理復雜程度，進而自適應地分配采樣率。該算法在一定程度上提高了在低采樣率下的重構(gòu)精度，但算法比較復雜，需要較長的運算時間。本文提出了一種改進的基于多尺度采樣的分塊壓縮感知算法，并且利用基于光滑Landweber投影法作為重構(gòu)算法，通過實驗證明提出的算法不僅可以保證大多數(shù)圖的重構(gòu)精度優(yōu)于分塊迭代閾值投影算法，而且重構(gòu)速度也優(yōu)于基于全變差分的自適應采樣率分塊壓縮感知算法。

1 相關理論

1.1 分塊壓縮感知(BCS)

GAN L等人在文獻[2]中將基于分塊圖像的測量引入壓縮感知理論，以降低計算量和存儲器的負擔。假設要對一幅Ιρ×Ic大小的圖像進行采樣，圖像的總像素數(shù)用N=Ir×IC來表示。上分塊壓縮感知算法將圖像分成了很多B×B大小的圖像塊，并對這些小塊進行相同的采樣操作。令Xi代表第i個圖像塊像素值所組成的向量，則對應的采樣值為：

yi=ΦBxi

(1)

(2)

由于Φ是一個對角矩陣，因此只需要存儲大小為nB×B2的ΦB，而不是存儲大小為n×N的矩陣，減輕了存儲器的負擔，增加了算法的實時性。

1.2 基于Landweber投影的重構(gòu)方法(SPL)

FOWLER J E等人在2009年提出了基于Landweber投影的塊壓縮感知重構(gòu)算法。算法將解決數(shù)學上反問題的Landweber迭代法[4]應用于圖像重構(gòu)過程中，提高了算法效率和重構(gòu)的精度。算法步驟如下：

(1)如式(1)所示分塊采樣后，分別得到了各個圖像塊的采樣值，將第i個圖像塊的采樣值記為yi，并假設重構(gòu)圖像X(k)=Φ-1Y，令迭代次數(shù)k=0。

(2)對第k次迭代重構(gòu)的圖像進行維納濾波，X(k)=Wienner(X(k))

(3)將第k次迭代得到的第j個圖像塊xj(k)依次執(zhí)行下式：

(3)

(4)

(6)若兩次迭代返回的均方根誤差之差小于0.000 1，則終止迭代，否則返回步驟(2)繼續(xù)迭代。

由于該算法對圖像進行了較多的平滑處理，因此導致圖像細節(jié)變得模糊，這種現(xiàn)象在采樣率低的情況下十分明顯。

1.3 基于全變差分的自適應采樣率分塊壓縮感知(TV-BCS-PL)

針對以上算法的不足，蔡旭等人提出了基于全變差分自適應采樣率分塊壓縮感知[5],該算法根據(jù)圖像塊的全變差分值來度量其紋理的復雜程度，并根據(jù)不同的全變差分值對采樣率進行自適應分配。具體算法如下。

假定原圖像大小為M×N，分塊圖像大小為B×B，則整個圖像中有num=M×N/B2個圖像塊，用I來表示整幅圖像，K表示當前子塊，并用(s,t)坐標表示圖像塊在圖像中的位置，Kij代表圖像塊中的每個像素，初始采樣率為R，則圖像塊K的全差分值為：

(5)

圖1 TV值算法示意圖

式中DhK代表水平方向的前像素與后像素的差值，DvK代表下方像素與本像素的差值，并且將整幅圖像分為四部分，每部分的DhK和DvK的計算方法如圖1所示。

(1)第一部分圖像塊為1≤s

(2)第二部分圖像塊為s=M/B且1≤t

(3)第三部分圖像塊為1≤s

(4)第四部分圖像塊為1≤s

(6)

根據(jù)式(6)計算出每個圖像塊的TV值，并利用下式自適應分配對各塊的采樣率：

(7)

其中μ為采樣率控制因子，文獻[5]中將其設為0.35，代表根據(jù)TV值分配采樣率的權(quán)重占總采樣率的35%。為了防止過采樣或欠采樣，對ri值進行閾值處理：

(8)

2 基于多尺度自適應采樣的塊壓縮感知算法

2.1 多尺度自適應采樣

對于基于平滑投影的多尺度分塊壓縮感知來說，采樣算子A分為兩部分，第一部分是多尺度變換Ω(例如離散小波變換等)和多尺度分塊觀測矩陣Φ′,所以A=Φ′Ω,于是可以通過下式對整幅圖像采樣：

y=Φ′Ωx

(9)

假設Ω對圖像進行了L層小波分解，因此Φ′是L個不同的基于塊的采樣算子分別與L層中每一層小波分解對應。x的小波變換可表示為：

(10)

(11)

其中1≤l≤L。

對圖像采樣過程中的采樣率進行了自適應分配。對低頻部分進行全部采樣，即s0=1,對于其他層的采樣率可用sl表示并可由(12)式求出：

Sl=WlS′

(12)

由此可得圖像總采樣率為：

(13)

通過將總采樣率S和小波分解每層所占比重wl帶入式(13)求出S′,通過S′可以求出每層分配到的采樣率。然而求出的采樣率有可能有一個或多個Sl>1，因此需調(diào)整算法使得對于所有的Sl都必須符合Sl≤1。具體做法是，假設Sl>1，則令Sl=1，相應的(13)式需要調(diào)整為：

(14)

再根據(jù)式(14)求出其他層采樣率，如果求出的結(jié)果中依然有Sl>1則可以重新迭代上述過程，直至所有Sl都小于等于1。通過實驗對比發(fā)現(xiàn)對于每層所占比重采用式(15)得出的結(jié)果最好：

Wl=16L-l+1

(15)

2.2 多尺度重構(gòu)

多尺度重構(gòu)采用的重構(gòu)算法包括對于整幅圖像利用維納濾波器進行平滑的過程和為達到圖像更加稀疏的效果將整幅圖像映射到稀疏域的閾值化處理過程。在這兩個操作之間是Landweber迭代過程，用x←x+ΦT(y-Φx)來表示，其中Φ是觀測矩陣，下面的偽代碼描述了如何將多尺度變換加入基于平滑投影的Landweber算法中。

forl++ (1≤l≤L)

fors++ (s∈{H,V,D})

forj++

endfor

endfor

endfor

k=0

do

forl++ (1≤l≤L)

fors++(s∈{H,V,D})

forj++

endfor

endfor

endfor

forl++ (1≤l≤L)

fors++ (s∈{H,V,D})

forj++

endfor

endfor

endfor

k=k+1

enddo

While(|D(k)-D(k-1)|>10-2)

endwhile

3 實驗結(jié)果與比較

3.1 實驗環(huán)境

實驗平臺是搭載了雙核2.3 GHz CPU和4 GB內(nèi)存的筆記本電腦，實驗環(huán)境為Windows 7操作系統(tǒng)，并在MATLAB 2014a上運行。算法使用了小波工具箱和l1-magic工具箱。

3.2 實驗結(jié)果

采用三張大小為512×512的圖像處理領域常用灰度圖像來驗證所提出算法的性能。實驗將提出的算法分別對比三種算法在不同采樣率下重構(gòu)圖像的質(zhì)量(PSNR)，對比算法包括基于平滑投影迭代分塊壓縮感知算法(BCS-SPL)[6]、基于全變差分的壓縮感知算法(TV)[7]以及一個多尺度變換的衍生算法GPSR[8]。所提出算法與BCS-SPL算法均采用雙樹離散小波變換作為稀疏變換。其中本文算法采用3層離散小波變換，并采用9/7雙正交小波[9]作為采樣域的變換。對于小波變換的第l層，每個大小為B×B的分塊被分別采樣。實驗采用分塊大小為16、32以及64，分別對應層為l=1,2,3。傳統(tǒng)的BCS-SPL算法和TV算法采用分塊大小為32。

表1、表2和表3分別是在三種不同圖像下的重構(gòu)效果比較。通過以上實驗結(jié)果可以看出，在多數(shù)情況下與傳統(tǒng)的BCS-SPL相比，本文提出的算法重構(gòu)結(jié)果的峰值信噪比要高出1～3 dB，并且在低采樣率時提出算法相對于TV算法有1～2 dB的性能提升。

表1 lena圖像上實驗結(jié)果比較 (dB)

表2 peppers圖像上實驗結(jié)果比較 (dB)

表3 goldhill圖像上實驗結(jié)果比較 (dB)

表4是當采樣率為0.3時對lena圖的重構(gòu)時間比較。

表4 0.3采樣率下對lena圖像的重構(gòu)時間比較

根據(jù)表4可知，本文提出的算法比BCS-SPL快了17 s，而MS-GPSR和TV兩種算法則相當耗時。其中TV算法盡管采用了快速SRM采樣算子，依然將近要用2個小時才可以完成對圖像的重建。

4 總結(jié)

本文將多尺度分解應用于平滑投影的Landweber分塊壓縮感知算法并在小波域進行采樣。提出的重構(gòu)算法是將BCS-SPL算法應用到小波分解后對每一層上每個子帶的分塊再分別重構(gòu)每一個分塊。實驗結(jié)果顯示，在重構(gòu)效果的對比上，提出的算法比原始BCS-SLP算法在時域上進行采樣和重構(gòu)時，重構(gòu)質(zhì)量普遍要高1～3 db。由此得出，提出的算法在提高圖像重構(gòu)效果的同時，依舊保持了BCS-SPL算法的運算速度?；诜謮K的壓縮感知算法的優(yōu)點在于降低了采樣和重構(gòu)算法的計算復雜度，同時提高了算法的實時性。提出的算法在小波域?qū)D像進行分塊的采樣和重構(gòu)，雖然保留了BCS算法的優(yōu)點，但是在對小波分解的觀測過程中，A=Φ′Ω，小波變換破壞了觀測矩陣Φ′分塊對角的結(jié)構(gòu)特性，產(chǎn)生了一個稠密的A矩陣，這就給壓縮感知在硬件實現(xiàn)上帶來了很大的挑戰(zhàn)。因此，提出算法在提升重構(gòu)效果的同時，也帶了算法硬件實現(xiàn)上的挑戰(zhàn)，如何解決觀測矩陣結(jié)構(gòu)問題是之后工作的重點。

[1] DONOHO D. Compressed sensing [J] . IEEE Transactions on Information Theory, 2006,52(4):1289-1306.

[2] GAN L. Block compressed sensing of natural images [C]. 2007 15th International Conference on Digital Signal Processing,IEEE,2007:403-406.

[3] MUN S, FOWLER J E . Block compressed sensing of natural images[C]. 2009 16th IEEE International Conference on Image Processing (ICIP),IEEE,2009:3021-3024.

[4] 王兵賢, 胡康秀, 王澤文. 反問題的Landweber迭代法及其應用研究進展[J]. 計算機應用研究, 2013, 30(9):2583-2586.

[5] 蔡旭, 謝正光, 黃宏偉,等. 一種自適應低采樣率圖像分塊壓縮感知算法[J]. 小型微型計算機系統(tǒng), 2016,37(3):612-616.

[6] MUN S, FOWLER J E. Block compressed sensing of images using directional transforms[C]. IEEE International Conference on Image Processing, 2009:3021-3024.

[8] SCHNITER P, POTTER L C, ZINIEL J. Fast Bayesian matching pursuit: model uncertainty and parameter estimation for sparse linear models[J]. IEEE Transactions on Signal Processing, 2009:399-405.

[9] DABHOLE S H, GUNDALE V A, POTGIETER J. An efficient modified structure of CDF 9/7 Wavelet based on adaptive lifting with SPIHT for lossy to lossless image compression[C]. International Conference on Signal Processing Image Processing & Pattern Recognition, IEEE, 2013,17(5):269-274.

Block-based image compressive sensing algorithm with adaptive sampling based on multiscale

Yin Changtao, Wen Zhiqiang, Hu Junfei

(Key Laboratory of Intelligent Information Perception and Processing Technology (Hunan Province), Zhuzhou 412007, China)

The block based compressive sensing algorithm can be applied to the image signal processing, and the image can be reconstructed quickly by using the method of smoothed projected landweber. Due to the algorithm display a poor reconstruction quality under the low sampling rate, someone propose the algorithm based on the total variation, which is called TV algorithm. Despite a certain improvement was made on the reconstruction effect, the algorithm decreased the operation speed on the other hand. In view of the deficiency of the two algorithms, we propose an adaptive sampling block based compressive sensing algorithm based on multiple scales. According to the difference in wavelet decomposition layers on the reconstruction results, we adaptively allocat each layer of different sampling rate, and apply the Smoothed Projected Landweber algorithm to each layer of each sub zone block. Experimental results reveal that the proposed algorithm improves the reconstruction quality by one to three dB, and the method is superior to the total variation method in the reconstruction speed .

compressed sensing; multiscale; wavelet transform; adaptive sampling; image blocking

國家自然科學基金(61170102)

TP391

A

10.19358/j.issn.1674- 7720.2016.24.013

殷長濤，文志強，胡駿飛. 基于多尺度的自適應采樣圖像分塊壓縮感知算法[J].微型機與應用，2016,35(24)：42-45，49.

2016-07-23)

殷長濤(1990-)，男，在讀碩士研究生，主要研究方向：圖像處理。

文志強(1973-)，男，教授，主要研究方向：圖像處理、模式識別。

胡駿飛(1990-)，男，在讀碩士研究生，主要研究方向：圖像處理。