基于光滑0 范數的圖像分塊壓縮感知恢復算法

王宏志，王賢龍，周婷婷

(長春工業大學 計算機科學與工程學院，長春130012)

0 引 言

最近幾年壓縮感知信號處理問題得到了廣泛的發展。壓縮感知(Compressive sensing，CS)打破傳統信號處理領域奈奎斯特采樣定率［1－3］。壓縮感知理論表明，如果信號是稀疏的或者是可壓縮的，則信號能在低于奈奎斯特采樣頻率采樣的條件下以高概率恢復出原信號。同時，壓縮感知理論框架下，將信號采樣和信號壓縮兩個步驟結合起來，即信號采樣之后就是壓縮的信號。壓縮感知算法主要包括三個方面，信號稀疏變換、觀測矩陣設計和恢復重構算法［4］。其中恢復重構算法直接關系到重構精度的大小，運算時間的長短，決定著CS 理論是否切實可行。

傳統圖像壓縮感知算法往往是將圖像轉換成一維信號，但是圖像信號轉換成一維信號往往長度很大，導致需要壓縮感知的測量矩陣尺寸很大，使得恢復過程占用巨大內存，恢復速度緩慢。為了解決壓縮感知在圖像處理上的應用，L Gan［5］提出了分塊壓縮感知算法(Base－block CS，BCS)。BCS 利用分塊的思想解決圖像信號占用內存巨大、恢復效果緩慢的問題。為了解決BCS算法分塊帶來的塊效應，Fowler 等［6－7］提出一種BCS－SPL 算法，引入維納濾波器的PL(Projected landweber，PL)算法作為信號恢復算法，減少分塊效應。但是BCS－SPL 中采用的恢復算法是PL算法，收斂速度慢，特別是在低采樣率條件下，PL算法迭代時間長，迭代次數多，使得維納濾波器作用的次數多，造成恢復圖像容易模糊。為了解決BCS－SPL 算法低采樣率條件下恢復時間長的問題，本文提出了一種結合光滑0 范數(Smoothed L0，SL0)壓縮感知恢復算法的加速分塊壓縮感知算法，加快了信號收斂速度，減少了迭代次數，實現了算法加速。

1 分塊壓縮感知算法

1.1 壓縮感知理論

假設原信號x，x ∈RN在變換域Ψ 是K－項稀疏的，對信號x 的變換域進行采樣

式中:Φ ∈RM×N是采樣矩陣，M ＜N。

如果從奈奎斯特采樣定理來看，要想從采樣信號y 中精確恢復原信號x 是不可能的。但是壓縮感知理論指出，如果信號x 是稀疏的，在遠遠低于乃奎斯特采樣頻率的采樣條件下，能夠以高概率從采樣信號中精確恢復原信號。

原信號的稀疏性是壓縮感知對信號的唯一要求。壓縮感知信號恢復問題轉換成尋找信號的一個最稀疏解問題［3］。，則壓縮感知信號恢復問題轉化成:

但是求解最小0 范數是一個NP－hard 問題，經過幾年的研究，學者提出了許多恢復算法。最著名的是基追蹤算法(Basis pursuit，BP)［1］。BP 算法將0 范數凸優化的問題放寬到1 范數，通過1 范數的凸優化問題的解代替0 范數優化問題的解:

雖然BP 算法恢復效果很好，但是算法計算復雜度高，信號恢復時間長，因此之后又提出了許多以貪婪算法為基礎的迭代算法。

1.2 BCS－SPL 算法

圖像壓縮感知中，Gan［5］首先提出圖像分塊壓縮感知BCS(Block－Base CS)。BCS 主要思想是將原始圖像分為較多尺寸相同的小圖像塊，對這些圖像塊采用相同的觀測矩陣，同時，在信號恢復端分別對這些圖像塊進行恢復，組合成整幅圖像。

圖像x，像素N=Ir×Ic的圖像分為若干個B×B 大小的圖像塊。用xi表示第i 個圖像塊，i=1，2，…，n，n=N/B2。對分塊之后的圖像采用相同的感知矩陣ΦB對各個子塊xi進行測量，得到測量值:

式中:ΦB∈RMB×B2，MB是各個子圖像塊的采樣數。這種分塊處理，對整個圖像相當于等價的采樣矩陣:

整個圖像觀測值y:

BCS 算法雖然解決了圖像壓縮感知信號恢復占用內存巨大、恢復速度緩慢的問題，但是由于分塊操作時的恢復圖像有明顯的塊效應。針對圖像塊效應，Fowler 等［6］基于維納濾波器的PL 算法提出了BCS－SPL 算法。

圖像信號的恢復采用PL 算法結合維納濾波器對信號進行恢復，同時去除因為分塊產生的塊效應。SPL 算法處理過程如下［6］:

Fowler 等［7］之后還結合近幾年的壓縮感知算法對BCS－SPL 算法做了進一步的改進，并將BCS－SPL 算法推廣到圖像編碼器的設計［8］以及視頻壓縮感知［9－10］。

2 BCS－SSL0PL 算法

2.1 SL0 壓縮感知恢復算法

光滑0 范數(Smoothed L0，SL0)［11－12］是針對欠定系統y=Ax 尋找最稀疏解的一種信號恢復算法，主要應用于壓縮感知信號恢復領域。SL0算法通過高斯函數近似表示L0 范數

所以求信號最稀疏解轉換成求解有約束最小化問題:

SL0 算法采用最速下降法迭代求解最小化問題:

同時σ 每次循環之后衰減一次，保證0 范數估計函數光滑，避免局部極值點。

2.2 BCS－SSL0SPL 算法

傳統BCS－SPL 算法雖然采用了結合維納濾波器的PL 算法作為圖像重建算法。但是，由于低采樣率條件下PL 算法收斂速度慢，導致圖像重建迭代次數過多，維納濾波器作用于圖像的次數多，使得重建的圖像容易變得模糊。而SL0 算法本身采用最速下降法逼近全局解，收斂速度非常快，重建時間短。為了減少低采樣率條件下圖像重建算法迭代次數，本文結合SL0 算法的優點對BCS－SPL 壓縮感知恢復算法進行改進。

從SPL 處理過程可以看出，PL 算法是對圖像變換域直接做閾值收縮，發現SL0 算法也是對圖像變換域進行處理，因此先采用SL0 算法的最速下降法對圖像變換域進行一次最小值逼近:

對用最速下降法逼近的最小值做閾值收縮處理:

同時，由于增加了一次最速下降法的逼近過程，在做閾值收縮時收縮系數需要做適當的變化。SL0算法是獲取圖像變換域中的最稀疏解，因此每次閾值收縮系數λ(i)由經過最速下降法最小逼近的值計算得到的近似0 范數決定，取每次迭代系數:

由式(12)可以看出，當迭代獲得的近似0 范數逼近圖像在變換域的稀疏度為K 時，BCS－SSL0PL收縮系數是SPL 算法中的1－K/(Lc×Lr)倍。

BCS－SSL0PL 算法步驟如下:

從上面的介紹可以看出，BCS－SSL0PL 算法相對于BCS－SPL 算法在于每次迭代增加一次最速下降法的最小值逼近步驟加速，同時用逼近的近似0 范數去控制收縮系數，減少重建算法迭代次數，加快了分塊壓縮感知算法重建速度。迭代次數的減少可以一定程度避免維納濾波器的多次作用而使得圖像變得模糊的問題。

3 實驗結果與分析

選取不同的圖像分別用BCS－SSL0PL 算法和BCS－SPL 算法對圖像進行恢復。每幅圖片的采樣率為0.1 ～0.9，每個采樣率重復試驗10 次，取平均值作為試驗結果。圖像稀疏變換選擇DCT 變換。試驗中兩種算法采用同一個采樣矩陣和變換矩陣，具體參數設置如上述BCSSL0PL算法所描述。

試驗選取Lenna、Man、Peppers、Bridge 四幅圖像作為試驗圖像，圖像大小為512×512。恢復圖像信噪比如表1、表2 所示。從恢復圖像的信噪比可以看出，BCS－SSL0PL 相對于BCS－SPL 算法并沒有多少提升，效果相當。選取0.2 采樣率的Lenna 和Peppers 恢復圖片對比兩種算法恢復圖像的局部細節，如圖1 所示。可以看出，對于Peppers 圖像，BCS－SSL0PL 算法信噪比高于BCS－SPL 算法，且BCS－SPL 算法可以明顯看出塊效應，而BCS－SSL0PL 算法則沒有。而在Lenna圖像，BCS－SSL0PL 算法雖然信噪比沒有BCSSPL 算法高，但是恢復的視覺效果并不比BCSSPL 差，同時也沒有BCS－SPL 算法恢復圖像的塊效應。

兩種恢復算法計算時間如圖2 所示。從恢復的時間可以看出，BCS－SPL 算法對于不同采樣率圖像恢復時間有很大的變化，但是BCSSSL0PL 算法對于不同采樣率的恢復時間比較平穩，變化不大。而且在0.1 ～0.5 采樣率條件下，BCS－SPL 恢復算法都是比較長的，基本上都在30 ～50 s 左右，無法應用于實時性要求高的場合。但是BCS－SSL0PL 恢復算法的恢復時間遠遠小于BCS－SPL 算法，所有恢復時間都在12 ～18 s左右。

表1 BCS－SPL 對應采樣率恢復信噪比Table 1 BCS－SPL recover image psnr for different meshement ration

表2 BCS－SSL0PL 對應采樣率恢復信噪比Table 2 BCS－SSL0PL recover image psnr for different meshement ration

圖1 BCS－SPL 與BCS－SSL0PL 算法恢復細節比較Fig.1 Details comparison of recover images between BCS－SPL and BCS－SSL0PL

圖2 BCS－SPL 與BCS－SSL0PL 算法恢復時間比較Fig.2 Recover time comparison between BCS－SPL and BCS－SSL0PL

BCS－SPL 算法中涉及對圖像分塊，圖像分塊尺寸的大小對算法恢復精度、恢復速度都有影響。為了比較不同分塊尺寸下兩種算法的性能，對512×512 的Lenna 圖像分別采用8×8、16×16、32×32 分塊對兩種算法進行測試。測試結果見表3。

從表3 可以看出，對于不同的分塊尺寸，BCS－SSL0PL 算法的恢復時間都比BCS－SPL 算法減少30%以上。

表3 不同分塊尺寸BCS－SPL 與BCS－SSL0PL 算法比較Table 3 BCS－SPL and BCS－SSL0PL comparison with on different block size

4 結束語

通過對基于光滑0 范數的圖像分塊壓縮感知算法的研究，建立了BCS－SSL0PL 的算法模型，實現了分塊壓縮感知算法的加速，同時避免了分塊壓縮感知算法在低采樣速率情況下恢復圖像的塊效應，且仍然能保證與原有BCS－SPL 算法同等的恢復效果。試驗過程中，當采樣率為0.1 時，BCS－SSL0PL 算法恢復效果不理想，這是因為采樣率過低，計算得到的近似0 范數和真實0 范數有很大的誤差，最速下降法的最小值逼近陷入局部最小值。這個問題需要對不同的圖像選取不同參數加以解決，這些參數的選擇也是下一步研究的問題。同時，由于并不是所有的圖像恢復效果都優于BCS－SPL 算法，所以對于BCS－SSL0PL算法的恢復精度也是下一步研究的重點。

［1］Candes E J，Tao T.Near－optimal signal recovery from random projections:universal encoding strategies?［J］.IEEE Transactions on Information Theory，2006，52(12):5406－5425.

［2］Donoho D L.Compressed sensing［J］.IEEE Transactions on Information Theory，2006，52(4):1289－1306.

［3］Candès E J，Wakin M B.An introduction to compressive sampling［J］.Signal Processing Magazine，2008，25(2):21－30.

［4］Haupt J，Nowak R.Signal reconstruction from noisy random projections［J］.IEEE Transactions on Information Theory，2006，52(9):4036－4048.

［5］Gan L.Block compressed sensing of natural images［C］∥IEEE 15th International Conference on Digital Signal Processing，2007:403－406.

［6］Mun S，Fowler J E.Block compressed sensing of images using directional transforms［C］∥IEEE 16th International Conference on Image Processing (ICIP)，2009:3021－3024.

［7］Fowler J E，Mun S，Tramel E W.Multiscale block compressed sensing with smoother projected Landweber reconstruction［C］∥Proceedings of the European Signal Processing Conference，2011:564－568.

［8］Mun S，Fowler J E.DPCM for quantized block－based compressed sensing of images［C］∥Proceedings of the 20th European on Signal Processing Conference，2012:1424－1428.

［9］Mun S，Fowler J E.Residual reconstruction for blockbased compressed sensing of video［C］∥IEEE Data Compression Conference(DCC)，2011:183－192.

［10］Chen C，Tramel E W，Fowler J E.Compressed－sensing recovery of images and video using multihypothesis predictions［C］∥IEEE Conference Record of the Forty Fifth Asilomar Conference on Signals，Systems and Computers(ASILOMAR)，2011:1193－1198.

［11］Mohimani G H，Babaie－Zadeh M，Jutten C.Fast sparse representation based on smoothed l0 norm［C］∥Independent Component Analysis and Signal Separation，Berlin:Springer，2007:389－396.

［12］Cui Z，Zhang H，Lu W.An improved smoothed l0－norm algorithm based on multiparameter approximation function［C］∥IEEE 12th International Conference on Communication Technology(ICCT)，2010:942－945.