基于壓縮感知的圖像自適應(yīng)編碼算法

張淑芳，李 凱，徐江濤，瞿廣財(cái)

(天津大學(xué)電子信息工程學(xué)院，天津 300072)

目前對(duì)圖像信號(hào)進(jìn)行采集和壓縮普遍采用以香農(nóng)定理為準(zhǔn)則的處理方式，即對(duì)圖像信號(hào)進(jìn)行高速采樣后再壓縮編碼．該采樣方式要求采樣速率達(dá)到信號(hào)帶寬的2倍以上才能精確重構(gòu)信號(hào)，對(duì)采樣設(shè)備提出了巨大挑戰(zhàn)；同時(shí)采用傳統(tǒng)圖像編碼算法對(duì)采樣后的數(shù)據(jù)進(jìn)行壓縮時(shí)，僅對(duì)采樣數(shù)據(jù)變換后少數(shù)絕對(duì)值較大的系數(shù)進(jìn)行壓縮編碼，拋棄大量零或者接近于零的系數(shù)，從而對(duì)采樣資源造成大量浪費(fèi)．近年來，由Candès[1]和 Donoho[2]提出的壓縮感知(compressive sensing，CS)理論為新型圖像采集和壓縮處理提供了理論支持[3]，它首先利用隨機(jī)觀測(cè)矩陣Φ，把在某個(gè)正交基或緊框架上稀疏或可壓縮的高維信號(hào)(x∈RN)投影到M維的低維空間上(得到測(cè)量值y)，然后通過求解優(yōu)化問題從少量的投影中以高概率重構(gòu)原始信號(hào)或圖像．CS理論的核心思想是將壓縮與采樣合并進(jìn)行，它突破了香農(nóng)采樣定理的瓶頸，即只需要通過少量的樣本點(diǎn)就能夠精確地重構(gòu)原始圖像，它將給信號(hào)處理帶來一次新的革命，對(duì)統(tǒng)計(jì)學(xué)、信息論和編碼等領(lǐng)域產(chǎn)生重要的理論影響[4]．

國內(nèi)外學(xué)者對(duì)壓縮傳感在圖像編碼中的應(yīng)用進(jìn)行了大量研究．2006年 Haupt等[5]通過實(shí)驗(yàn)表明如果圖像是高度可壓縮的，測(cè)量過程即使存在噪聲，壓縮感知方法仍可準(zhǔn)確重構(gòu)圖像．2006年Rice大學(xué)成功研制出“單像素相機(jī)”[6]，為低像素相機(jī)拍攝高質(zhì)量圖像提供了可能．2007年，Gan[7]借鑒離散余弦變換(discrete cosine transform，DCT)塊編碼的巨大成功提出了基于塊的壓縮感知方法，每一塊都采用相同的塊觀測(cè)矩陣，可減少觀測(cè)矩陣的存儲(chǔ)量，有效解決高維圖像采集問題．由于在一幅圖像中每個(gè)塊在變換域的稀疏度不一樣，在變換域越稀疏的塊，重構(gòu)圖像所需要的采樣點(diǎn)數(shù)就越少．本文鑒于此，提出了基于壓縮感知的圖像自適應(yīng)編碼算法，在對(duì)圖像進(jìn)行CS壓縮采樣前，首先判斷其在 DCT域的稀疏度，然后根據(jù)每個(gè)塊的稀疏度對(duì)其進(jìn)行自適應(yīng)的壓縮采樣，從而使得在低采樣率的情況下能夠?qū)D像進(jìn)行高質(zhì)量重構(gòu)．

1 壓縮感知理論

壓縮感知理論由 Candès和 Donoho[1-2]在 2006年正式提出．Candès證明了只要信號(hào)在某一正交空間具有稀疏性，就能以較少的采樣點(diǎn)數(shù)完全或者以很高概率重建該原始信號(hào)．

假設(shè) x =[x( 1 ),x( 2),… ,x (N)]T表示一維離散時(shí)間信號(hào)組成的列向量，其可表示為一組標(biāo)準(zhǔn)正交基的線性組合，即

式中：Ψ 為基矩陣，Ψ = [ψ1,ψ2,… ,ψN]，ψi為列向量；N × 1 的列向量s是x的加權(quán)系數(shù)序列，即s = x ,ψ =x ．顯然，x和s是同一個(gè)信號(hào)的等價(jià)ii表示，x是信號(hào)在時(shí)域的表示，s則是信號(hào)在Ψ域的表示．如果s中只有 K個(gè)非零(或絕對(duì)值較大)的系數(shù)，其余 N-K個(gè)系數(shù)都為 0(或絕對(duì)值很小)，則稱s為信號(hào)x的稀疏表示．

假設(shè) y ∈RN為信號(hào)x在測(cè)量矩陣Φ∈RM×N下的線性測(cè)量值，即

式中：=ΘΦΨ是一個(gè)MN×的矩陣．對(duì)于給定的測(cè)量值y從式(2)求解s是一個(gè)線性規(guī)劃問題，但由于KMN?≤，即方程的個(gè)數(shù)少于未知數(shù)的個(gè)數(shù)，這是一個(gè)欠定問題．Candès等[8]證明了信號(hào)重構(gòu)可以通過求解最小l0范數(shù)來求解，如果測(cè)量矩陣Φ和稀疏變換矩陣Ψ滿足約束等距性(restricted isometry property，RIP)條件，最優(yōu)稀疏解?可以由測(cè)量值y∈RN重構(gòu)，即

式中 ·0為向量的 l0范數(shù)，代表向量x中非零元素的個(gè)數(shù)．該式為非凸優(yōu)化問題，是典型的 NP-hard問題，計(jì)算復(fù)雜度高．Candès[1]和 Donoho[2]提出用 l1范數(shù)來代替 l0范數(shù)，把式(3)轉(zhuǎn)化為一個(gè)凸優(yōu)化問題來求解，即

得到信號(hào)x在稀疏域Ψ下的最優(yōu)稀疏解?s后，信號(hào)x的重構(gòu)值?x可表示為

在對(duì)圖像進(jìn)行稀疏變換時(shí)，常用 DCT、小波變換和有限差分來作為變換稀疏基，在用有限差分做稀疏變換時(shí)，常用全變差(total variation，TV)來衡量．Candès等[9]從大量自然圖像的離散梯度都是稀疏的角度出發(fā)，提出了適合二維圖像壓縮重構(gòu)的最小全變分法，重構(gòu)精確而且魯棒性強(qiáng)，但是運(yùn)算速度較慢．2009年Li[10]提出了基于最小全變分法的 TVAL3算法，它將全變分法和增廣拉格朗日函數(shù)相結(jié)合來進(jìn)行圖像壓縮重構(gòu)，有效提高了重構(gòu)速度，并且重構(gòu)圖像的PSNR值也有了很大提高，其重構(gòu)公式為

式中：p＝1或p＝2代表1范數(shù)或2范數(shù)；gradiu表示在位置i處u的離散梯度向量．

因此，本文在對(duì)圖像進(jìn)行自適應(yīng)壓縮編碼后，利用測(cè)量值進(jìn)行圖像重構(gòu)時(shí)選用TVAL3算法．

2 基于壓縮感知的圖像自適應(yīng)編碼算法

本文提出了基于壓縮感知的圖像自適應(yīng)編碼算法，根據(jù)圖像各個(gè)塊的稀疏度對(duì)其進(jìn)行自適應(yīng)的壓縮采樣，從而實(shí)現(xiàn)低采樣率下圖像的高質(zhì)量重構(gòu)．

2.1 圖像壓縮采樣率對(duì)重構(gòu)質(zhì)量的影響

本文對(duì)圖像進(jìn)行基于塊的壓縮采樣，把圖像分為3232×的塊，為了滿足RIP條件，本文使用獨(dú)立同分布的高斯隨機(jī)矩陣作為測(cè)量矩陣Φ，分別對(duì)圖像進(jìn)行 20%、40%、60%和 80%的采樣，并采用 TVAL3算法對(duì)測(cè)量值進(jìn)行重構(gòu)．為了衡量圖像重構(gòu)效果，采用客觀圖像質(zhì)量評(píng)價(jià)指標(biāo) PSNR來表征重構(gòu)圖像塊和相應(yīng)原始圖像塊之間的差別．圖 1(a)和(b)分別為Lena圖像和Cameraman圖像在不同采樣率下每幅圖像各個(gè)塊 PSNR值的分布情況，塊采用從上到下，從左到右的方式進(jìn)行排列，橫坐標(biāo)表示塊的分布，縱坐標(biāo)表示重構(gòu)圖像各個(gè)塊的PSNR值．

圖1 不同采樣率下重構(gòu)圖像PSNR值的分布Fig.1 PSNR distribution of reconstructed images at different sampling rates

從圖 1可以看出，隨著采樣率的升高，各個(gè)塊的PSNR值呈上升趨勢(shì)，但高采樣率會(huì)導(dǎo)致圖像壓縮效率的降低，并且造成解碼端圖像重構(gòu)復(fù)雜度的升高．因此，需要在圖像采樣率和 PSNR之間形成良好的折中．另外，由于圖像中各個(gè)塊的稀疏度不同，使得在相同采樣率下重構(gòu)圖像中各個(gè)塊的 PSNR值有較大起伏，對(duì)圖像整體質(zhì)量造成了很大影響．

圖2為20%和80%采樣率時(shí)的重構(gòu)圖像，其中圖2(a)為采樣率20%的重構(gòu)圖像，由于其PSNR起伏較大，有些塊 PNSR較好，有些塊 PSNR較差，因此其塊效應(yīng)比較明顯，在臉部和帽子區(qū)域可以看出明顯的塊效應(yīng)．圖 2(b)為采樣率 80%的重構(gòu)圖像，雖然PSNR起伏也較大，但由于其 PSNR值都較高，因此看不出明顯的塊效應(yīng)，其重構(gòu)時(shí)間比采樣率20%時(shí)的重構(gòu)時(shí)間大約增加了50%．

因此，需要對(duì)整幅圖像進(jìn)行自適應(yīng)的壓縮采樣，對(duì)稀疏性較好的塊采用較低的采樣率，對(duì)稀疏性較差的塊采用較高的采樣率，從而確保在較低的采樣率下，整幅圖像重構(gòu)質(zhì)量達(dá)到最優(yōu)．如果能找到圖像各個(gè)塊的PSNR和稀疏度之間的關(guān)系，就能對(duì)圖像進(jìn)行自適應(yīng)的壓縮采樣．

圖2 不同采樣率下的重構(gòu)圖像Fig.2 Reconstructed images at different sampling rates

2.2 圖像稀疏度的判斷準(zhǔn)則

由于對(duì)圖像進(jìn)行分塊二維 DCT變換后，低頻系數(shù)分布在 DCT分塊系數(shù)矩陣的左上角，高頻系數(shù)分布在其右下角，并且低頻系數(shù)的絕對(duì)值大于高頻系數(shù)的絕對(duì)值．圖像越稀疏，它的低頻部分占的比重就會(huì)越大．本文利用α作為 DCT系數(shù)絕對(duì)值|Ti,j|大小的判斷閾值，如果|Ti,j|小于α則判定其為較小的系數(shù)，反之則把該系數(shù)作為較大的DCT系數(shù)．利用C表示圖像各個(gè)塊 DCT變換系數(shù)中模值小于α的個(gè)數(shù)．從以上分析可知，C值越大表示該塊越稀疏，其需要較少的壓縮采樣點(diǎn)數(shù)就能得到較好的重構(gòu)圖像[11]．圖3(a)和(b)分別給出了α＝4，采樣率為 40%時(shí)，Lena和Cameraman重構(gòu)圖像中各個(gè)塊C值和PSNR值的關(guān)系．

從圖 3可以看出，圖像各個(gè)塊的 C值和 PSNR值大致服從相同的變化規(guī)律，即塊的 C值越大，其PSNR值越高，因此可通過C值來間接表征圖像塊重構(gòu)時(shí)能夠達(dá)到的PSNR值．

因此，本文以C值作為圖像稀疏度的判斷準(zhǔn)則，依據(jù) C值的大小來對(duì)圖像的采樣率進(jìn)行自適應(yīng)選擇．

2.3 基于壓縮感知的圖像自適應(yīng)編碼算法

圖3 圖像各塊C值和PSNR值之間的關(guān)系Fig.3 Relationship between C and PSNR of each block in the image

為了在較低采樣率下獲得較高的圖像質(zhì)量，本文對(duì)C值較大的塊以較低采樣率進(jìn)行壓縮采樣，反之對(duì)C值較小的塊以較高采樣率進(jìn)行壓縮采樣，從而保證整幅圖像都具有較高的重構(gòu)質(zhì)量．本文選用iT(i＝1，2，3)作為對(duì)原始圖像進(jìn)行壓縮采樣時(shí)采樣率高低判斷的閾值，且 T1＞T2＞T3；用β1、β2、β3和β4分別表示對(duì)圖像進(jìn)行 20%、40%、60%和 80%的采樣壓縮．依據(jù) C和 Ti的大小關(guān)系，對(duì)每個(gè)圖像塊進(jìn)行自適應(yīng)的壓縮采樣，即

Ti取值不同，則會(huì)對(duì)圖像的壓縮效率和重構(gòu)質(zhì)量產(chǎn)生不同影響．當(dāng) Ti取值較小時(shí)，圖像可以較低的采樣率進(jìn)行壓縮采樣，從而可有效提高圖像的編碼效率，降低編碼器的功耗，但重構(gòu)圖像的質(zhì)量要差一些；反之，當(dāng) Ti取值較大時(shí)，圖像編碼效率較低，但重構(gòu)圖像的質(zhì)量較好．大量實(shí)驗(yàn)表明，當(dāng) T1、T2和 T3的取值分別為900、800和700時(shí)，在保證重構(gòu)圖像質(zhì)量較好的前提下，能較大幅度提高圖像的編碼效率．在應(yīng)用本文所提算法對(duì)圖像進(jìn)行自適應(yīng)編碼時(shí)，需要根據(jù)網(wǎng)絡(luò)帶寬、編碼器的功耗和對(duì)圖像重構(gòu)質(zhì)量的要求等實(shí)際因素對(duì) Ti的取值進(jìn)行相應(yīng)調(diào)整．

對(duì)圖像進(jìn)行自適應(yīng)壓縮采樣的流程如圖4所示．

步驟1 將輸入圖像分成m個(gè)n×n的塊，并令i＝1．

步驟 2對(duì)第i塊圖像進(jìn)行DCT變換并計(jì)算該塊的C值．

步驟 3根據(jù)式(7)，判斷 C值和圖像壓縮采樣閾值T1、T2和T3的關(guān)系，如果C＞T1，則對(duì)圖像進(jìn)行1β采樣，轉(zhuǎn)向步驟7，否則執(zhí)行步驟4．

步驟4 如果C≤T1并且C＞T2，則對(duì)圖像進(jìn)行2β采樣，轉(zhuǎn)向步驟7，否則執(zhí)行步驟5．

步驟5 如果C≤T2并且C＞T3，則對(duì)圖像進(jìn)行3β采樣，轉(zhuǎn)向步驟7，否則執(zhí)行步驟6．

步驟6 如果C≤T3，則對(duì)圖像進(jìn)行4β采樣．

步驟 7 如果 i≥m 則結(jié)束整個(gè)壓縮采樣過程，否則，令 i＝i＋1，重新執(zhí)行步驟 2．

圖4 算法流程Fig.4 Flow chart of the proposed algorithm

為了提高壓縮效率，本文在對(duì)圖像塊進(jìn)行壓縮采樣時(shí)，利用相同的種子針對(duì)各個(gè)塊不同的采樣率生成相應(yīng)尺寸的高斯隨機(jī)觀測(cè)矩陣，這就與傳統(tǒng)固定采樣率的壓縮方法一樣，僅需向解碼端傳遞一次產(chǎn)生隨機(jī)觀測(cè)矩陣的種子．同時(shí)，為了向解碼端傳遞各個(gè)塊壓縮時(shí)所使用的采樣率，本文使用標(biāo)志位 1、2、3和 4分別表示 20%、40%、60%和 80%的采樣率，與傳統(tǒng)利用固定采樣率對(duì)圖像進(jìn)行壓縮采樣相比，該自適應(yīng)算法只需在各圖像塊編碼碼流的開始多加入一個(gè)采樣率標(biāo)志位即可．

3 實(shí)驗(yàn)結(jié)果及分析

采用Lena、Cameraman和Columbia具有不同灰度和紋理細(xì)節(jié)的圖像對(duì)所提算法的有效性進(jìn)行驗(yàn)證，其中 Lena圖像包含豐富的細(xì)節(jié)信息和紋理特征；Cameraman圖像前景和背景對(duì)比度較大；Columbia為景物圖像，平滑和細(xì)節(jié)區(qū)域區(qū)分較為明顯.

在實(shí)驗(yàn)中，塊的大小 n取值為 32，α的取值為4，采用 TVAL3恢復(fù)算法，并且閾值 T1、T2和 T3的取值分別為 900、800和 700，實(shí)驗(yàn)結(jié)果如表 1所示．其中λ表示采樣率的增加所帶來的PSNR增益，以20%時(shí)的采樣率1β和PSNR1作為基準(zhǔn)，其余采樣率所帶來的PSNR增益可表示為

表1 實(shí)驗(yàn)結(jié)果Tab.1 Experimental results

從表 1可以看出，固定采樣率下，增加單位采樣率所能提升的PSNR值的增益在20%左右，而本文提出的自適應(yīng)采樣算法增加單位采樣率所能帶來的圖像 PSNR值平均增益達(dá)到了33%．顯然，本算法對(duì)重構(gòu)圖像的質(zhì)量有顯著提高．對(duì)于Lena和 Cameraman圖像，包含的細(xì)節(jié)信息較多，采用本文所提自適應(yīng)算法所需采樣率大約為50%，對(duì)于前景和背景區(qū)域區(qū)分較為明顯的 Columbia圖像，采用自適應(yīng)算法時(shí)所需采樣率僅為 30.22%，這是由于大部分背景區(qū)域塊的稀疏性較好，采用較低的采樣率就能精確重構(gòu)圖像．

圖5給出了Lena原始圖像以及不同采樣率下的重構(gòu)圖像．其中圖 5(e)為原始圖像，圖 5(a)、(b)、(c)和(d)分別為 Lena圖像在采樣率 20%、40%、60%和 80%時(shí)的重構(gòu)圖像，隨著采樣率的增加，重構(gòu)圖像的主觀質(zhì)量越來越好．當(dāng)采樣率為 20%和 40%時(shí)，存在明顯的塊效應(yīng)和模糊現(xiàn)象；當(dāng)采樣率達(dá)到 60%時(shí)，重構(gòu)圖像的 PSNR值為 34.07,dB，從主觀效果上來看，重構(gòu)圖像和原始圖像的差別很小．采用本文自適應(yīng)采樣算法，僅需要 50%的采樣率，重構(gòu)圖像(圖5(f))的PSNR值為35.02,dB，和原始圖像相比，幾乎看不出差異．

圖5 Lena原始圖像以及在不同采樣率下的重構(gòu)圖像Fig.5 Original image and reconstructed images at different sampling rates for Lena

為了更加直觀地說明利用自適應(yīng)算法進(jìn)行壓縮采樣時(shí)圖像各區(qū)域所選用的采樣率，圖 6(a)和(b)分別給出了 Lena圖像和 Cameraman圖像采樣率的分割示意．在圖 6(a)所示的 Lena圖像分割圖中，對(duì)于頭發(fā)、面部和帽子這些包含細(xì)節(jié)信息較多的區(qū)域，圖像塊的稀疏性較差，采用較高采樣率對(duì)此進(jìn)行壓縮采樣，有效保證了重構(gòu)圖像的主客觀質(zhì)量，而對(duì)于周邊比較平滑的區(qū)域，圖像塊的稀疏性較好，則采用 20%的采樣率，可有效提高圖像的壓縮效率．同樣對(duì)于圖6(b)所示的 Cameraman圖像而言，在草坪、人的頭部和相機(jī)等部位，包含的紋理信息較多，采用了 80%的采樣率進(jìn)行壓縮采樣，而對(duì)于天空這些比較平坦的背景區(qū)域，塊的稀疏性較好，采用 20%采樣率進(jìn)行壓縮采樣．

圖6 圖像采樣率的分割示意Fig.6 Partition sketch map of image sampling rates

圖7 給出了Lena圖像在各種固定采樣率和自適應(yīng)算法下各個(gè)塊的PSNR值分布，其中橫坐標(biāo)表示塊的分布，采用和圖 1相同的排列方式；縱坐標(biāo)表示PSNR值的大?。畯膱D 7可以看出，與固定采樣率的PSNR曲線相比，本文所提自適應(yīng)算法的PSNR曲線較平坦，上下起伏較小，從而保證整幅圖像中各個(gè)塊的重構(gòu)質(zhì)量都位于一個(gè)平均水平，顯著提高了重構(gòu)圖像的整體質(zhì)量．

圖7 Lena圖像各個(gè)塊的PSNR分布Fig.7 PSNR distribution of each block in Lena image

4 結(jié) 語

本文提出了一種基于壓縮感知的圖像自適應(yīng)編碼算法，該算法根據(jù)圖像各個(gè)塊在 DCT域的稀疏度，分別對(duì)各個(gè)塊進(jìn)行不同采樣率的壓縮采樣，在確保整體圖像質(zhì)量較優(yōu)的條件下，有效降低了圖像的編碼碼率．實(shí)驗(yàn)結(jié)果表明，本文所提算法實(shí)現(xiàn)復(fù)雜度較低，重構(gòu)圖像主客觀質(zhì)量較好．

［1］ Candès E J. Compressive sampling[C]// Proceedings of the International Congress of Mathematicians. Madrid，Spain，2006：1433-1452．

［2］ Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory，2006，52(4)：1289-1306.

［3］ 李樹濤，魏 丹. 壓縮傳感綜述[J]. 自動(dòng)化學(xué)報(bào)，2009，35(11)：1369-1377.Li Shutao，Wei Dan. A survey on compressive sensing[J]. Acta Automatica Sinica，2009，35(11)：1369-1377(in Chinese).

［4］ 石光明，劉丹華，高大化，等. 壓縮感知理論及其研究進(jìn)展[J]. 電子學(xué)報(bào)，2009，37(5)：1070-1081.Shi Guangming，Liu Danhua，Gao Dahua，et al. Advances in theory and application of compressed sensing[J]. Acta Electronica Sinica，2009，37(5)：1070-1081(in Chinese).

［5］ Haupt J，Nowak R. Compressive sampling vs. conventional imaging[C]// Proceedings of the IEEE International Conference on Image Processing. Atlanta，Georgia，2006：1269-1272.

［6］ Takhar D，Laska J N，Wakin M B，et al. A new compressive imaging camera architecture using opticaldomain compression[C]// Computational Imaging IV at SPIE Electronic Imaging. San Jose，California，2006：43-52.

［7］ Gan L. Block compressed sensing of natural images[C]//Proceedings of the 15th International Conference on Digital Signal Processing. Washington DC，USA，2007：403-406.

［8］ Candès E J，Tao T. Decoding by linear programming[J].IEEE Transactions on Information Theory，2005，51(12)：4203-4215.

［9］ Candès E J，Romberg J，Tao T. Robust uncertainty principles：Exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory，2006，52(2)：489-509.

［10］ Li Chengbo. An Efficient Algorithm for Total Variation Regularization with Applications to the Single Pixel Camera and Compressive Sensing[D]. Houston：Department of Computational and Applied Mathematics，Rice University，2009.

［11］ Stankovi? V， Stankovi? L ， Cheng S. Compressive video sampling[C]// Proceedings of the European Signal Processing Conference. Lausanne，Switzerland，2008.