基于波浪式矩陣置換的稀疏度均衡分塊壓縮感知算法

杜秀麗，張 薇，陳 波

(遼寧省通信網絡與信息處理重點實驗室(大連大學 信息工程學院 ), 遼寧 大連 116622)(*通信作者電子郵箱dxlxts@126.com)

0 引言

壓縮感知(Compressed Sensing, CS)[1-3]是一種新興的信號處理技術，對傳統的采樣編碼技術提出了挑戰，是信息領域的一次重要變革。它以觀測矩陣為手段，可以以低于奈奎斯特采樣定理規定的采樣率采樣，突破了傳統圖像采樣定理的限制。

分塊CS(Block CS, BCS)[4-6]解決了壓縮感知中存儲資源浪費且重構時間長的難題。長期以來，分塊壓縮感知技術是圖像壓縮感知技術中的熱點問題，得到了國內外專家和學者的廣泛重視。為了消除塊效應，各專家學者做了大量的研究[7-11]。

Guicquero等[7]利用圖像邊緣信息進行自適應壓縮感知，算法復雜度較高，且對于復雜圖像的重構效果不理想。Li等[8]提出一種基于全變分 (Total Variation, TV)范數的圖像分塊壓縮感知算法，通過全變差分測量稀疏度[9]結構，但全變差分在稀疏度結構的估量上準確度不高。張淑芳等[10]利用離散余弦變換(Discrete Cosine Transform, DCT)后各圖像塊的DCT系數作為稀疏度判斷準則，提出粗糙自適應壓縮采樣方法，但其采樣率及稀疏度閾值的確定具有很強的主觀性，不能充分體現自適應壓縮采樣的優勢。王玥等[11]提出了一種基于灰度熵的自適應全變分濾波的壓縮感知算法，通過圖像的灰度熵自適應分配塊采樣率提高重構質量，但灰度熵的使用沒有考慮圖像元素間的相關關系，有一定局限。王蓉芳等[12]提出一種基于視覺顯著性的分塊自適應壓縮感知算法，在采樣階段，每個子塊的采樣率依據顯著信息自適應地變化；在重建階段，根據不同圖像顯著信息的差異，自適應地濾波。

圖像分塊后各子塊的稀疏度是不一樣的，稀疏度小的子塊重構效果差，稀疏度大的子塊重構質量好，不同重構效果的子塊合成一幅圖像時便會出現塊效應。而上述研究都是從自適應采樣的角度出發，通過為不同稀疏度的子塊分配不同的采樣率來消除塊效應[13]。Zhang等[14]為減小采樣率分配不精確帶來的誤差，同時消除自適應采樣中存儲多個測量矩陣的缺陷，對圖像塊本身做處理，提出一種基于矩陣置換的BCS(BCS with Mmatrix Permutation, BCS-MP)算法，通過重新排列所有子塊的列向量來改變子塊的稀疏度，使各個圖像子塊的稀疏度均衡，這樣可以采用相同的測量矩陣進行采樣，同時減小采樣的難度和重構時的塊效應；但算法中采用順序的排序方法，使得子塊間稀疏度均衡效果較差。

針對上述子塊間稀疏度均衡效果較差的問題，為提高圖像重構質量，從均衡子塊稀疏度的角度出發，本文提出了一種基于波浪式矩陣置換的稀疏度均衡BCS(Ripple Matrix Permutation-based sparsity balanced BCS, BCS-RMP)算法。該算法計算各子塊的稀疏度之后，采用波浪式排序方法產生置換矩陣，在采樣之前對圖像子塊進行矩陣置換來均衡各子塊的稀疏度。仿真結果表明，當選擇合適的子塊大小和采樣率時，BCS-RMP算法可有效提高圖像的重構質量，且能更準確地體現細節信息

1 基于矩陣置換的分塊壓縮感知

在分塊壓縮感知中，圖像子塊的紋理分布不均勻會使重構圖像存在塊效應，降低圖像的重構質量。采用不同采樣率的測量矩陣Φ對子塊進行采樣，可以消除塊效應，但存儲多個測量矩陣又增加了編、解碼側計算的復雜度?；诰仃囍脫Q的分塊壓縮感知算法，在采樣之前對圖像進行矩陣置換處理，使置換之后的圖像子塊稀疏度得到均衡，原則上對稀疏度完全均衡的子塊進行采樣是不會出現塊效應的，這樣可以采用相同的測量矩陣Φ對子塊進行采樣，降低了編、解碼側計算的復雜度，提高了圖像重構質量，同時可以達到消除塊效應的效果。

1.1 矩陣置換原理

矩陣置換作為消除塊效應的一種新方法，其基本原理如圖1所示，先對圖像子塊的每一列列向量進行排列，以此得到置換矩陣進行置換處理，然后對排列后的信號進行采樣、重構，最后通過逆矩陣置換得到重構圖像。

圖1 矩陣置換模型的整體框架Fig. 1 Overall framework of matrix permutation model

X=X?P

(1)

(2)

X?=XPT

(3)

1.2 置換矩陣P

置換矩陣P∈RnL×nL是一個nL×nL的方陣，P矩陣的每行和每列中只有一個元素是1，其他元素為0。元素1的位置由排列向量J決定，令J=(J1,J2,…,JnL)是向量(k1,k2,…,knL)的排列，向量(k1,k2,…,knL)的排列對應于唯一的置換矩陣[16]。那么,可以使用J來生成置換矩陣P=[eJ1,eJ2,…,eJnL]，這里eJi表示在第Ji位置為1、其他位置為0的列向量。如nL=5時，排列向量J和置換矩陣P分別如式(4)和式(5)所示：

J=(J1,J2,J3,J4,J5)=(5,1,3,4,2)

(4)

P=[eJ1,eJ2,eJ3,eJ4,eJ5]=[e5,e1,e3,e4,e2]=

(5)

由線性代數知識可知，當矩陣M∈RnL×nL從左邊與置換矩陣P相乘時，排列的是M的行；當矩陣M從右邊與置換矩陣P相乘時，排列的是M的列。本文的置換策略意在對原始信號X?的列進行重新排列，為了方便詳細闡述，本文將基于置換矩陣的置換策略稱為矩陣置換。

前面提到，每個排列向量J對應于唯一的置換矩陣P，排列向量J實際上是對圖像X?的列向量索引進行排列。因此，求解最優置換矩陣P相當于找到一個最優的排列向量J，使置換后的圖像X的稀疏度能夠均勻分布。X?的列數為nL，因此可以將X?的nL列向量分配給X的L個塊，每個塊為n列。為了使X的列向量均勻分布在塊中，首先初始化X的每個塊為空矩陣，然后對X?的列進行由大到小的排列，以迭代方式分配X?的列給X，在每次迭代時，從X?提取L列，并將這些列分配給X的每個塊，分配方式要使X的子塊間稀疏度復雜度趨于均衡。通過對X?列向量的分配便可得到排列向量J。

2 現有矩陣置換算法

要獲得一個最優的置換矩陣P，就要找到一個最優的排列向量J來均衡子塊間的稀疏度。通過灰度共生矩陣的熵測得各子塊列向量的稀疏度，以列向量的稀疏度k?和子塊數量L為輸入，通過對圖像信號列向量的索引進行排列獲得最優的排列向量J，從而得到最優的置換矩陣P。具體算法描述如下。

輸出 優化的置換矩陣P。

4)增加j，如果j≤L返回3)。

5)增加T，如果T≤n返回4)。

7)使用置換J生成最優排列矩陣P=PJ。

其中PJ即為由排列向量J得到的置換矩陣。得到排列向量J最關鍵的就是對列向量索引進行排列，現有矩陣置換采用的是順序的排序方法，第一次迭代時，將k1～kL列按第一個塊到第L個塊的順序進行分配；第二次迭代時，同樣，將kL+1～k2L列按第一個塊到第L個塊的順序進行分配；依此類推。順序的排序方法會使得首尾子塊間稀疏度相差較大，在用相同的測量矩陣采樣時，首尾子塊的重構效果也會有比較明顯的差別，導致逆矩陣置換后的重構圖像效果不盡理想。

3 BCS-RMP算法

對原始信號進行矩陣置換，省去了自適應采樣中存儲多個不同測量矩陣的環節，減小了計算的復雜度。但現有算法中迭代的過程一直按從大到小的排序方法進行排列，使得子塊間稀疏度均衡效果較差，所以本文采用波浪排序(Ripple Sort)的方法對列向量進行分配，使置換后子塊間的稀疏度[9]得到更好的均衡。

波浪排序的基本原理如圖2所示，第一次迭代時，將k1～kL個塊按第一個塊到第L個塊的順序分配；第二次迭代時，將kL+1～k2L個塊按第L個塊到第一個塊的順序分配；依此類推。

圖2 波浪排序的原理

Fig. 2 Principle of ripple sorting

顯然采用波浪式排序得到的排列向量J對子塊間稀疏度均衡效果更好，這樣通過相同的測量矩陣對子塊進行采樣后得到的測量信號稀疏度也是均衡的，重構效果較好，所以在編碼端和解碼端都只需存儲一個子塊的測量矩陣就可以完成采樣和重構，降低了采樣和OMP重構過程中計算的復雜度。雖然現有算法也是存儲一個測量矩陣用于采樣和重構，但其對子塊稀疏度的均衡效果較差，采樣后測量信號會存在子塊邊界處不連續的現象，塊效應相對較明顯，重構質量較差。

因此，基于波浪式矩陣置換的稀疏度均衡分塊壓縮感知(BCS-RMP)算法在第2章現有矩陣置換算法的基礎上，將第3)步中的迭代過程更改為：

4 仿真結果及分析

4.1 圖像的重構效果

為了直觀地測試圖像處理算法在自然圖像上的效果，在圖像處理領域有許多常用的測試圖像，本文選用5幅典型的512×512圖像進行仿真實驗，其中：peppers是一幅辣椒的圖像；lena是一幅模特圖像；boat是一幅船只的圖像；barbara是一幅名為芭芭拉的女子圖像；CT2是一幅計算機斷層掃描圖像。當子塊大小為128×128時，子塊數量L為16。首先，將圖像變換到小波域，小波類型為“dB7”，小波層數為4層。然后，對小波域圖像進行分塊，本文采用波浪式置換矩陣對分塊后的子塊進行列向量的重新排列，得到子塊間稀疏度均衡的圖像信號，并對其進行壓縮感知處理。

4.1.1 細節子塊的重構效果

因為是通過分塊對圖像進行壓縮感知處理，所以先分別從每幅圖像中選取了一個能體現細節信息的子塊，對細節子塊的提高效果進行初步的分析。如圖3所示，原圖上所標注的塊即細節子塊，選取依據是所選塊的稀疏度在各圖像子塊中最大。通過表1中的峰值信噪比(Peak Signal to Noise Ratio, PSNR)可以看出，與BCS-MP算法對比，本文的BCS-RMP算法對細節子塊的重構效果有一定的提高，如:當采樣率為0.1時，peppers圖像提高約1.6 dB，barbara圖像提高約1.4 dB；當采樣率為0.3時，lena圖像提高約0.8 dB，CT2圖像提高約0.5 dB。所以在對細節信息的體現上，本文算法相比BCS-MP算法有一定的優勢。

表1 128×128的細節子塊PSNR對比 dBTab. 1 PSNR comparison of 128×128 detail sub-block dB

從細節子塊的特點來分析，細節子塊是稀疏度較大的子塊，蘊含的紋理信息比較多，列向量間差異也就比較大，在進行列向量的排列時，細節子塊的列向量比較分散地分布，由于子塊間稀疏度并不是完全均衡的，用相同的測量矩陣采樣后，子塊間的重構效果也就存在略微的差異，子塊間的均衡效果越差的話，這種差異也就體現得越明顯，而細節子塊由這些分布在不同塊中的列向量組成，子塊間的重構效果差異越明顯，細節子塊的重構效果越差。對小波域圖像進行矩陣置換后， BCS-RMP算法與BCS-MP算法對子塊間稀疏度均衡效果的對比如表2所示。

表2 圖像子塊稀疏度對比Tab. 2 Sparsity comparison of image sub-block

由表2可知，BCS-RMP算法對應的方差更小一些，表明應用BCS-RMP算法后，子塊間的稀疏度相差更小，均衡效果更好，適用于子塊的采樣率差距更小，子塊更適合采用相同的測量矩陣進行采樣；且子塊的測量矩陣維數小，占用資源少，使得OMP重構時算法計算更簡單，所以BCS-RMP算法對細節信息的恢復更好一些。

4.1.2 整幅圖像的重構效果

BCS-RMP算法與BCS-MP算法對整幅圖像的重構效果對比如表3所示。由表3可知，相比BCS-MP算法，BCS-RMP算法對整幅圖像的重構效果也有一定的提高。其中:peppers圖像提高效果最好，當采樣率為0.1時，提高約1 dB；boat圖像提高相對較差，當采樣率為0.1時，提高約0.3 dB。且從表2可以看出，本文算法對子塊稀疏度的均衡效果更好一些，所以用相同的測量矩陣對子塊進行采樣后，子塊間的重構差異越小，逆矩陣置換后得到的圖像恢復效果越好。

從表3還可以看出，整幅圖像的重構效果劣于細節子塊的重構效果。因為在整幅圖像中，存在一些稀疏度較小的子塊，如圖3中lena圖像的帽子部分、boat圖像中的藍天區域和海域，這些子塊的列向量稀疏度比較小，分配到不同的塊中，在用相同的測量矩陣對子塊進行采樣時，這些稀疏度小的列向量的采樣點數也比較少，雖然波浪式置換矩陣比傳統置換矩陣的均衡效果更好，但因為細節信息比較少，提高效果不是很明顯。因為整幅圖像是細節子塊和這些較小稀疏度子塊的共同體現，所以從整體來看，整幅圖像的重構效果沒有細節子塊的重構效果好。

4.1.3 圖像的重構效果對比

分塊大小為128×128，采樣率為0.3時，BCS-RMP算法和BCS-MP算法的圖像重構效果對比如圖3所示。從圖3可以看出，兩種算法得到的圖像均不存在塊效應。從圖3中的一些細節還可以看出，BCS-RMP算法得到的圖像重構效果更好，如：peppers圖像的整幅圖像，BCS-MP(整幅)圖中，甜椒右側多了本沒有的黑色斑塊，BCS-RMP(整幅)中恢復得到的甜椒幾乎和原圖一樣，BCS-MP(細節)圖中也有明顯的黑色斑塊，而BCS-RMP(細節)圖中明顯要好一些，表明BCS-RMP算法在對細節信息體現上具有優勢；barbara整幅圖像中，BCS-RMP(整幅)圖中的人物面部輪廓更清晰，地面上光線和陰影部分的對比也比較明顯， BCS-RMP(細節)圖中的褲子和圍巾的條紋也比BCS-MP(細節)圖中更明亮、更清晰一些，表明BCS-RMP算法能得到更好的重構效果。

4.2 采樣率對重構效果影響

從表1、表3中還可以看出：當采樣率為0.1時，各幅圖像的提高效果最好；采樣率越高，提高越少，尤其當采樣率為0.4、0.5時，細節子塊的提高大概在0.02～0.80 dB，整幅圖像提高大概在0.02～0.30 dB。

圖3 不同算法圖像重構效果對比Fig. 3 Comparison of image reconstruction effects of different algorithms

分析上述結果的原因，BCS-RMP算法和BCS-MP算法的結果都是使圖像子塊間的稀疏度均衡，只是BCS-RMP算法得到的圖像子塊均衡效果更好一些。當采樣率較大時，對圖像塊采樣得到的紋理信息也較多，考慮一個極端的情況，采樣點是圖像子塊的所有點數，那紋理信息的對比就是兩個圖像子塊的對比。由表2可以看出，雖然BCS-RMP算法得到的子塊間稀疏度的方差較小，但并不是極大的差距，所以采樣率越高時，均衡效果的對比越不明顯；而當采樣率較小時，對圖像塊采樣得到的紋理信息也較少，紋理信息體現的均衡效果差距越明顯，最后的圖像是根據采樣的紋理信息重構的，因此采樣率越小，BCS-RMP算法對重構圖像的提高效果越好。

從圖4中曲線的變化趨勢來看，當采樣率為0.4、0.5時，peppers、lena和boat圖像還有比較明顯的提高效果，而barbara和CT2圖像的提高幾乎為零；當采樣率為0.1～0.3時，五幅圖像都有比較明顯的提高，且細節子塊的提高更明顯。所以BCS-RMP算法更適用于0.1～0.3采樣率下對圖像信號的恢復。

4.3 分塊大小對重構效果的影響

用512×512的圖像進行仿真驗證，子塊大小分別為64×64、32×32時，BCS平滑投影Landweber(BCS-Smoothed Projected Landweber, BCS-SPL)算法、BCS-MP算法和BCS-RMP算法三種分塊壓縮感知方法得到圖像的PSNR對比如表4、表5所示。其中，BCS-SPL算法沒有進行矩陣置換的處理，BCS-MP算法采用現有矩陣置換對圖像進行處理，本文的BCS-RMP算法采用波浪式矩陣置換對圖像進行處理。

由表4、表5可以看出，當分塊大小為64×64、32×32時，相比于BCS-SPL算法，BCS-MP和BCS-RMP算法得到的圖像效果都有明顯的提高，表明矩陣置換策略應用在壓縮感知中對重構效果有比較明顯的改善作用，但本文算法BCS-RMP相對BCS-MP幾乎沒有提高。

圖4 細節子塊和整幅圖像的PSNR增量對比Fig. 4 Comparison of PSNR increments between detail sub-blocks and entire image表4 子塊大小為64×64的整幅圖像的PSNR對比dB

Tab. 4 PSNR comparison of entire image with sub-block of 64×64 dB

表5 子塊大小為32×32的整幅圖像的PSNR對比 dBTab. 5 PSNR comparison of entire image with sub-block of 32×32 dB

采樣率為0.1，子塊大小分別為32×32、64×34、128×128時本文算法BCS-RMP相對BCS-MP的PSNR增量曲線如圖5所示。從圖5中可以看出，當分塊大小為128×128時，BCS-RMP算法對圖像質量的提高效果更好。

圖5 不同子塊大小時整幅圖像的PSNR增量Fig. 5 PSNR increment of entire image with different sub-block sizes

分析上述結果的原因，列向量的稀疏度差別較大，稀疏度大的列向量占據了主導地位。對小波域圖像所有列向量進行從大到小排列后的曲線圖如圖6所示，分析發現大部分列向量的稀疏度都偏小，只有很少一部分列向量的稀疏度比較大。從圖6截取的前35列列向量稀疏度的曲線如圖7所示。

圖6 所有列向量的稀疏度Fig. 6 Sparsities of all column vectors

圖7 前35列列向量的稀疏度Fig. 7 Sparsities of the first 35 column vectors

從圖7中可以看出，稀疏度大的列向量主要集中在前32列，從32列之后列向量的稀疏度開始低于1×105。當子塊大小為32×32時，子塊數量為256，在第一次迭代中，稀疏度最大的32列被分配給其中的32個塊，其余的224個塊被分配的列向量稀疏度水平都相對較小，而在第二次及之后的迭代中被分配的列向量稀疏度更小，不管是順序的排序方法還是波浪排序方法，都無法改變第一次迭代時稀疏度大的列向量對整個子塊稀疏度的主導作用，這也是分塊大小為32×32時，BCS-RMP算法提高并不明顯的原因。

同樣的原因，當子塊大小為64×64時，子塊數量為64，也只有其中的32個塊稀疏度水平較大，但整體來說，相比子塊大小為32×32時，稀疏度均衡效果有所提高。

而當選用128×128的子塊進行實驗，此時子塊數量為16，正好在前兩次迭代中對前32列稀疏度較大的列向量進行分配，從圖7還可以看出，雖然前32列在所有列向量中是稀疏度較大的，但這32列之間也有一個下降的趨勢，如第1列和第32列相差大概6×105，所以采用波浪排序的方法可以減小第一個塊和最后一個塊之間稀疏度的差距，得到更好的均衡效果。

5 結語

分塊壓縮感知中的塊效應問題是近幾年來的熱點問題，自適應采樣的方法無論是從采樣率分配上的改進還是重構算法上的改進都無法做到徹底的改善；矩陣置換通過均衡子塊稀疏度來消除塊效應，但又存在稀疏度均衡效果較差的缺陷。本文改進了矩陣置換中的排序方法，采用波浪排序的方法對列向量進行分配，選擇合適的子塊大小，將波浪排序的應用體現得更明顯，使子塊間稀疏度更均衡。仿真結果表明，當選擇合適的子塊大小時，本文的BCS-RMP算法的重構效果相比于BCS-MP算法有一定的提高，尤其當采樣率為0.1～0.3時，BCS-RMP算法能得到更好的效果，且能更準確地表達圖像的細節。