殷長濤，文志強，胡駿飛
（智能信息感知及處理技術湖南省重點實驗室, 湖南 株洲 412007）
摘要：基于分塊的壓縮感知算法適用于圖像信號的處理，通過平滑迭代閾值投影法可以快速重構圖像，但存在低采樣率下重構圖像質量較差的缺點。基于全變差分的分塊壓縮感知算法，在一定程度上能提升重構效果，但降低了運算速度。針對以上算法的不足，提出基于多尺度的自適應采樣圖像分塊壓縮感知算法。根據小波分解后不同層對重構結果影響所占權重不同的特性，自適應分配給每一層不同的采樣率，并在重構時將平滑迭代閾值投影法應用到每一層的每一個子帶的分塊上。實驗結果表明，與傳統的迭代閾值投影法相比在重構質量上提高了1~3 dB，在重構速度上與迭代閾值投影法相當并優于全變差分法。
關鍵詞：壓縮感知；多尺度；小波變換；自適應采樣；圖像分塊
中圖分類號：TP391文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2016.24.013
引用格式：殷長濤，文志強，胡駿飛. 基于多尺度的自適應采樣圖像分塊壓縮感知算法［J］.微型機與應用，2016,35（24）：42-45，49.
0引言
壓縮感知（Compresssive Sensing,CS）［1］最早是由DONOHO D等人提出的一種新的信號壓縮采樣方法。利用數據的冗余性，把原始信號通過觀測矩陣投影到低維空間，如果原始信號稀疏或是可壓縮的，則可以通過觀測值，利用凸優化的方法很好地重構出原始信號。
目前已有研究者將CS理論運用于圖像數據的獲取，但是實踐中發現，直接針對整幅圖像數據進行壓縮感知時所需要的觀測矩陣會占用很大的存儲空間，重構時運算量過大，并且效果不理想。針對壓縮感知這個缺點，GAN L等人提出了分塊壓縮感知（Block Compressed Sensing，BCS）［2］理論，該理論首先將圖像分割成相同大小的圖像塊，再對每一小塊分別進行采樣重構。MUN S等提出了分塊迭代閾值投影算法（BCSSPL）［3］,該算法通過將BCS理論與Landweber迭代法［4］相結合，并且加入了維納濾波過程，在加快了重構速度的同時，也消除了分塊采樣所帶來的重構結構的快效應，很大程度上提高了分塊壓縮感知的可用性。蔡旭等人在文獻［3］的基礎上提出了基于全變差分自適應采樣率分塊壓縮感知算法（TVBCSSPL）［5］,根據圖像塊全變差分的值判斷其紋理復雜程度，進而自適應地分配采樣率。該算法在一定程度上提高了在低采樣率下的重構精度，但算法比較復雜，需要較長的運算時間。本文提出了一種改進的基于多尺度采樣的分塊壓縮感知算法，并且利用基于光滑Landweber投影法作為重構算法，通過實驗證明提出的算法不僅可以保證大多數圖的重構精度優于分塊迭代閾值投影算法，而且重構速度也優于基于全變差分的自適應采樣率分塊壓縮感知算法。
1相關理論
1.1分塊壓縮感知（BCS）
GAN L等人在文獻［2］中將基于分塊圖像的測量引入壓縮感知理論，以降低計算量和存儲器的負擔。假設要對一幅Ιρ×Ic大小的圖像進行采樣，圖像的總像素數用N=Ir×IC來表示。上分塊壓縮感知算法將圖像分成了很多B×B大小的圖像塊，并對這些小塊進行相同的采樣操作。令Xi代表第i個圖像塊像素值所組成的向量，則對應的采樣值為：
![@}TL]}9DYAS_9TAL7Z20Q4R.png](http://files.chinaaet.com/images/2017/02/16/6362287050389512219766754.png "@}TL]}9DYAS_9TAL7Z20Q4R.png")
由于Φ是一個對角矩陣，因此只需要存儲大小為nB×B2的ΦB，而不是存儲大小為n×N的矩陣，減輕了存儲器的負擔，增加了算法的實時性。
1.2基于Landweber投影的重構方法（SPL）
FOWLER J E等人在2009年提出了基于Landweber投影的塊壓縮感知重構算法。算法將解決數學上反問題的Landweber迭代法［4］應用于圖像重構過程中，提高了算法效率和重構的精度。算法步驟如下：
(1)如式（1）所示分塊采樣后，分別得到了各個圖像塊的采樣值，將第i個圖像塊的采樣值記為yi，并假設重構圖像X(k)=Φ-1Y，令迭代次數k=0。
（2）對第k次迭代重構的圖像進行維納濾波，X(k)=Wienner(X(k))
（3）將第k次迭代得到的第j個圖像塊xj(k)依次執行下式：
(j)(k)=(k)j+ΦTB(y(k)j-ΦBx(k)j)（3）
(4)將第k次迭代得到的重構圖像(k)投影到Ψ域，得到(k)=Ψ(k)，該矩陣為稀疏矩陣，并對(k)做閾值處理。
(5)將(k)作ΨT(k)變換得到時域中重構圖像(k),并對重構圖像塊(k)j執行下式：
X(k+1)j=(k)j+ΦTB(y(k)j-ΦB(k)j)（4）
(6)若兩次迭代返回的均方根誤差之差小于0.000 1，則終止迭代，否則返回步驟（2）繼續迭代。
由于該算法對圖像進行了較多的平滑處理，因此導致圖像細節變得模糊，這種現象在采樣率低的情況下十分明顯。
1.3基于全變差分的自適應采樣率分塊壓縮感知(TV-BCS-PL)
針對以上算法的不足，蔡旭等人提出了基于全變差分自適應采樣率分塊壓縮感知［5］,該算法根據圖像塊的全變差分值來度量其紋理的復雜程度，并根據不同的全變差分值對采樣率進行自適應分配。具體算法如下。
假定原圖像大小為M×N，分塊圖像大小為B×B，則整個圖像中有num=M×N/B2個圖像塊，用I來表示整幅圖像，K表示當前子塊，并用(s,t)坐標表示圖像塊在圖像中的位置，Kij代表圖像塊中的每個像素，初始采樣率為R，則圖像塊K的全差分值為：
TVl1l2=∑DhK2+Dv K2(5)
式中DhK代表水平方向的前像素與后像素的差值，DvK代表下方像素與本像素的差值，并且將整幅圖像分為四部分，每部分的DhK和DvK的計算方法如圖1所示。
(1）第一部分圖像塊為1≤s<M/B且1≤t<N/B的塊:
![N)]W)6%DC@5MD18WL%F5Q]6.png](http://files.chinaaet.com/images/2017/02/16/6362287057697812216868808.png "N)]W)6%DC@5MD18WL%F5Q]6.png")
根據式（6）計算出每個圖像塊的TV值，并利用下式自適應分配對各塊的采樣率：
其中μ為采樣率控制因子，文獻［5］中將其設為0.35，代表根據TV值分配采樣率的權重占總采樣率的35%。為了防止過采樣或欠采樣，對ri值進行閾值處理：
文獻［5］中取γ為1.9用來控制最小采樣率，并且為了保證總采樣數保持不變，令K=R/ri，對采樣率的分配進行多次迭代直到|K－1|<0.001，跳出迭代后得到的ri就是每個子塊對應的采樣率。
2基于多尺度自適應采樣的塊壓縮感知算法
2.1多尺度自適應采樣
對于基于平滑投影的多尺度分塊壓縮感知來說，采樣算子A分為兩部分，第一部分是多尺度變換Ω（例如離散小波變換等）和多尺度分塊觀測矩陣Φ′,所以A=Φ′Ω,于是可以通過下式對整幅圖像采樣：
y=Φ′Ωx（9）
假設Ω對圖像進行了L層小波分解，因此Φ′是L個不同的基于塊的采樣算子分別與L層中每一層小波分解對應。x的小波變換可表示為：
=Ωx（10）
的第l層小波分解中子帶s被分割為Bl×Bl的小塊，并用一個與之大小對應的Φ觀測矩陣對其采樣。假設用l,s,j表示小波分解中第l層的子帶s中的第j個子塊，那么采樣過程可以用下式表示：
yl,s,j=Φll,s,j（11）
其中1≤l≤L。
對圖像采樣過程中的采樣率進行了自適應分配。對低頻部分進行全部采樣，即s0=1,對于其他層的采樣率可用sl表示并可由（12）式求出：
Sl=WlS′（12）
由此可得圖像總采樣率為：
通過將總采樣率S和小波分解每層所占比重wl帶入式（13）求出S′,通過S′可以求出每層分配到的采樣率。然而求出的采樣率有可能有一個或多個Sl>1，因此需調整算法使得對于所有的Sl都必須符合Sl≤1。具體做法是，假設Sl>1，則令Sl=1，相應的（13）式需要調整為：
再根據式(14)求出其他層采樣率，如果求出的結果中依然有Sl>1則可以重新迭代上述過程，直至所有Sl都小于等于1。通過實驗對比發現對于每層所占比重采用式(15)得出的結果最好：
Wl=16L-l+1(15)
2.2多尺度重構
多尺度重構采用的重構算法包括對于整幅圖像利用維納濾波器進行平滑的過程和為達到圖像更加稀疏的效果將整幅圖像映射到稀疏域的閾值化處理過程。在這兩個操作之間是Landweber迭代過程，用x←x+ΦT(y－Φx)來表示，其中Φ是觀測矩陣，下面的偽代碼描述了如何將多尺度變換加入基于平滑投影的Landweber算法中。
function =MultiScale-BCS (y,{Φl,1≤l≤L},Ψ,Ω)
forl++ (1≤l≤L)
fors++ (s∈{H,V,D})
for j++
(0)l,s,j=ΦTlyl,s,j
endfor
endfor
endfor
k=0
do
x(k)=Ω-1(k)
(k)=Wiener(x(k))
^k=Ω(k)
forl++ (1≤l≤L)
fors++(s∈{H,V,D})
for j++
^^(k)l,s,j=^(k)l,s,j+ΦTl(yl,s,j－Φl^(k)l,s,j)
x︶︶(k)=ΨΩ-1^^(k)
x︶(k)=Threshold(x︶︶(k))
(k)=ΩΨ-1x︶(k)
endfor
endfor
endfor
forl++ (1≤l≤L)
fors++ (s∈{H,V,D})
for j++
endfor
endfor
endfor
(k)l,s,j=(k)l,s,j+ΦTl(yl,s,j－Φl(k)l,s,j)
D(k+1)=(k+1)－^^(k)2
k=k+1
enddo
While(|D(k)－D(k-1)|>10－2)
=(k)
endwhile
3實驗結果與比較
3.1實驗環境
實驗平臺是搭載了雙核2.3 GHz CPU和4 GB內存的筆記本電腦，實驗環境為Windows 7操作系統，并在MATLAB 2014a上運行。算法使用了小波工具箱和l1magic工具箱。
3.2實驗結果
采用三張大小為512×512的圖像處理領域常用灰度圖像來驗證所提出算法的性能。實驗將提出的算法分別對比三種算法在不同采樣率下重構圖像的質量（PSNR），對比算法包括基于平滑投影迭代分塊壓縮感知算法（BCSSPL）［6］、基于全變差分的壓縮感知算法（TV）［7］以及一個多尺度變換的衍生算法GPSR［8］。所提出算法與BCSSPL算法均采用雙樹離散小波變換作為稀疏變換。其中本文算法采用3層離散小波變換，并采用9/7雙正交小波［9］作為采樣域的變換。對于小波變換的第l層，每個大小為B×B的分塊被分別采樣。實驗采用分塊大小為16、32以及64，分別對應層為l=1,2,3。傳統的BCSSPL算法和TV算法采用分塊大小為32。
表1、表2和表3分別是在三種不同圖像下的重構效果比較。通過以上實驗結果可以看出，在多數情況下與傳統的BCSSPL相比，本文提出的算法重構結果的峰值信噪比要高出1~3 dB，并且在低采樣率時提出算法相對于TV算法有1~2 dB的性能提升。
表4是當采樣率為0.3時對lena圖的重構時間比較。根據表4可知，本文提出的算法比BCSSPL快了17 s，而MSGPSR和TV兩種算法則相當耗時。其中TV算法盡管采用了快速SRM采樣算子，依然將近要用2個小時才可以完成對圖像的重建。
4總結
本文將多尺度分解應用于平滑投影的Landweber分塊壓縮感知算法并在小波域進行采樣。提出的重構算法是將BCSSPL算法應用到小波分解后對每一層上每個子帶的分塊再分別重構每一個分塊。實驗結果顯示，在重構效果的對比上，提出的算法比原始BCSSLP算法在時域上進行采樣和重構時，重構質量普遍要高1~3 db。由此得出，提出的算法在提高圖像重構效果的同時，依舊保持了BCSSPL算法的運算速度。基于分塊的壓縮感知算法的優點在于降低了采樣和重構算法的計算復雜度，同時提高了算法的實時性。提出的算法在小波域對圖像進行分塊的采樣和重構，雖然保留了BCS算法的優點，但是在對小波分解的觀測過程中，A=Φ′Ω，小波變換破壞了觀測矩陣Φ′分塊對角的結構特性，產生了一個稠密的A矩陣，這就給壓縮感知在硬件實現上帶來了很大的挑戰。因此，提出算法在提升重構效果的同時，也帶了算法硬件實現上的挑戰，如何解決觀測矩陣結構問題是之后工作的重點。
參考文獻
［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:30213024.
［4］ 王兵賢, 胡康秀, 王澤文. 反問題的Landweber迭代法及其應用研究進展［J］. 計算機應用研究, 2013, 30(9):25832586.
［5］ 蔡旭, 謝正光, 黃宏偉,等. 一種自適應低采樣率圖像分塊壓縮感知算法［J］. 小型微型計算機系統, 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.
［7］ CANDS E J, ROMBERG J K, TAO T. Stable signal recovery from incomplete and inaccurate measurements［J］. Communications on Pure & Applied Mathematics, 2005, 19(5):410 412.