王 林,宋 星

(西安理工大學(xué) 自動化與信息工程學(xué)院,西安 710048)

圖像壓縮主要解決的問題是盡量減少用來表示圖像信息的數(shù)據(jù)量,通常使用某種變換去掉圖像中的冗余信息來達到壓縮的目的.針對圖像壓縮的圖像變換,使圖像在變換域能量集中地表示,大量的信息集中于少數(shù)的系數(shù)上,而其他的數(shù)據(jù)很小或幾乎為零,數(shù)據(jù)進行壓縮編碼處理時就能更加有效地壓縮數(shù)據(jù),這對圖像的高效存儲與傳輸具有十分重要的意義.

目前,常見的用于圖像壓縮的變換主要有K-L交換、Fourier變換、離散余弦變換(DCT)、小波變換以及近幾年出現(xiàn)的以幾何多尺度分析[1]為主要工具的新型變換等.多年來,小波變換在圖像壓縮中已得到了成功的應(yīng)用,但是圖像的不連續(xù)處的變換系數(shù)存在顯著誤差導(dǎo)致重建圖像質(zhì)量較差.圖可對復(fù)雜的、不規(guī)則區(qū)域中定義的信號[2,3]進行有效表示.因此,2011 年Hammond等人提出了譜圖小波變換(Spectral Graph Wavelet Transform,SGWT)[4],它是一種多尺度幾何分析理論,基于譜圖理論[5]和小波變換理論,具有很好的尺度不變性和局部自適應(yīng)性,能對不規(guī)則區(qū)域圖像進行很好的稀疏表示,并具備完備的理論體系從稀疏系數(shù)中恢復(fù)原始圖像,在圖像處理領(lǐng)域得到了迅速的發(fā)展.2013年,Ortega等人提出了基于圖的小波圖像編碼方法[6],通過設(shè)計濾波器,然后利用SPIHT算法對濾波器系數(shù)進行壓縮編碼.

為了改善小波壓縮圖像重構(gòu)質(zhì)量較差的缺點,本文利用譜圖小波變換對圖像進行分解,提出一種針對譜圖小波系數(shù)的集合分裂嵌入式塊編碼(Set Partitioned Embedded Block,SPECK)算法,具有較高的編碼速度,是嵌入式圖像編碼算法中性能較好的一種.實驗結(jié)果表明,該算法對經(jīng)典圖像壓縮編碼后均取得了不錯的壓縮效果,具有較高的壓縮比和峰值信噪比.

1 譜圖小波

1.1 經(jīng)典小波變換

連續(xù)小波的產(chǎn)生與母小波的選擇有關(guān),引入尺度因子s,這里令s>0,位置因子a,則小波在不同的位置和尺度下對應(yīng)的母小波可表示為:

則函數(shù)f(t)在尺度s和位置a處的連續(xù)小波變換定義為:

從傅里葉域角度出發(fā),假設(shè)尺度參數(shù)s是離散的,將位置參數(shù)a作為函數(shù)獨立的變量,連續(xù)小波在傅里葉域表示為:

1.2 譜圖理論

加權(quán)圖可用G=(V,E,W)表示,其中V表示節(jié)點集,E表示邊集,w為邊對應(yīng)的權(quán)值.討論有限無向圖,其中N為圖中節(jié)點數(shù),表示圖G的鄰接矩陣,該矩陣元素am,n可表示如下:

度d(m)定義為稱為圖G的度矩陣.

圖拉普拉斯[7]矩陣L定義為:

L為實對稱矩陣該矩陣具有一組完備的正交向量集,并且L對應(yīng)的特征值均為非負值.對應(yīng)的特征向量相互正交,特征值滿足:

拉普拉斯矩陣的特征空間類似于傅里葉域.因此,定義圖上傅里葉變換[8]:

相應(yīng)的,圖上傅里葉逆變換定義為:

1.3 譜圖小波變換

類似于圖的傅里葉變換,為了定義圖上的小波變換,選擇滿足的小波核函數(shù)g,使對應(yīng)于在尺度t和節(jié)點n,圖的拉普拉斯矩陣的特征空間L,定義譜圖小波

選擇滿足的低通濾波核函數(shù)h,定義圖上的尺度函數(shù)

小波系數(shù)和尺度系數(shù)如式(10)和式(11)所示:

因為對于大圖不能明確的計算拉普拉斯矩陣的特征空間,文獻[6]提出一種快速譜圖小波變換算法,它用切比雪夫多項式逼近[9]小波核函數(shù)g和h.

cj,k表示切比雪夫系數(shù),Mj是多項式逼近的階數(shù),表示階數(shù)是k的移位切比雪夫多項式.給出快速的近似譜圖小波變換:

根據(jù)公式(13)和(14)給出的快速小波系數(shù)和尺度系數(shù)計算公式,當(dāng)尺度 Nscales=4,256×256 的 lena.bmp譜圖小波變換得到一個低頻系數(shù)和4個高頻系數(shù),如圖1所示.

圖1 譜圖小波分解示意圖

尺度系數(shù)也稱為低頻系數(shù),如圖1(a)所示,可以看出它集中了原始圖像的主要能量.小波系數(shù)也稱為高頻系數(shù),如圖1(b～f)所示,顯示了圖像邊緣、輪廓的紋理特征,其數(shù)值遠小于尺度系數(shù)值.所以說在譜圖小波系數(shù)中存在許多不重要的系數(shù),具有能量聚集性以及能量隨尺度增加而衰減的特性.

從一組給定的譜圖小波系數(shù)c=wf中恢復(fù)一個圖信號,合并所有的小波變換,框架算子將信號f映射成框架系數(shù),即其中c0=Thf是尺度系數(shù),是尺度為sj的小波系數(shù)使用偽逆算子從逼近系數(shù)和小波系數(shù)重構(gòu)信號的計算本文采用共軛梯度方法,而W*W和W*的計算采用快速切比雪夫多項式逼近方法.

2 基于譜圖小波系數(shù)的 SPECK 算法

在完成圖像的譜圖小波變換后,得到多個一維的小波系數(shù)向量.由于小波系數(shù)中存在許多不重要的系數(shù),具有能量聚集性以及能量隨尺度增加而衰減的特性,而基于塊集合劃分思想的SPECK(集合分裂嵌入式塊編碼)算法[10]是一種針對小波系數(shù)的編碼算法,該算法是近期嵌入式分級圖像編碼算法中性能較好的一種.

為了消除分量系數(shù)之間的冗余性,本文使用改進后的SPECK編碼算法[11,12]進行位平面編碼,具體算法為編碼時將所有分量系數(shù)視為一個整體,對各個分量進行交叉位平面編碼,生成一個混合的位流.

設(shè)cj,n表示在尺度下sj的第n個譜小波變換系數(shù).算法的實現(xiàn)過程中,采用逐次逼近量化,定義了非重要集合鏈表(LIS)和重要系數(shù)鏈表(LSC)兩個鏈表.具體的算法流程如下所示.

算法.基于改進的SPECK算法的譜圖小波系數(shù)編碼1)算法初始化計算 將變換系數(shù)c分成根集合S=c0和剩余集合 置 LSC 為空表,并將 S放入LIS中.2)分類掃描過程按|S|大小升序排列集合S,對每個 執(zhí)行子過程如果 執(zhí)行子過程3)精細掃描過程對上次分類掃描過程中己是顯著的系數(shù),輸出該系數(shù)的第k個顯著位.4)量化步長更新如果位平面索引 k>0,k=k–1,返回第 2)步;否則停止.其中,各個子過程描述如下:輸出集合S的第k個顯著位如果如果S是單個系數(shù),輸出系數(shù)的符號位,然后放入LSC中;否則執(zhí)行子過程如果 從LIS中刪除S如果如果把 S 放入 LIS 中對集合將 S 分裂成 S1,S2,其中輸出集合Si的第k個顯著位如果

如果Si是單個系數(shù),輸出系數(shù)的符號位,然后放入LIS中否則執(zhí)行子過程如果,把 S 放入 LIS 中:輸出集合I的第k個顯著位如果執(zhí)行子過程:將 I分裂成 S*和 I*,其中,對集合S*,執(zhí)行子過程對集合I*,執(zhí)行子過程

3 實驗結(jié)果與分析

對該算法整體分析可知,算法中全部可變參數(shù)有尺度參數(shù)Nscales,切比雪夫多項式階數(shù)m,設(shè)計參數(shù)k=200以及掃描次數(shù)sm.由于切比雪夫多項式階數(shù)m影響重構(gòu)圖像的質(zhì)量,因此實驗中以m值作為變量,得到不同質(zhì)量的重構(gòu)圖像.

3.1 圖像數(shù)據(jù)壓縮

對圖像壓縮性能的評價則可以用壓縮比Cr來表示如下:

由于不同碼率下恢復(fù)圖像的質(zhì)量不同,因此壓縮率并不是一個獨立的指標,必須與圖像恢復(fù)質(zhì)量統(tǒng)一進行比較.

在進行算法測試時,選取512×512像素的經(jīng)典圖像,利用文中提出的算法,設(shè)置Nscales=5,在保證圖像重構(gòu)質(zhì)量良好的情況下,得到壓縮后數(shù)據(jù)量與原數(shù)據(jù)的壓縮比(Cr)及峰值信噪比(PSNR),壓縮結(jié)果如表1所示.

表1 512×512 像素圖像壓縮結(jié)果

分析表1中的數(shù)據(jù),將譜圖小波壓縮后得到的圖像與原圖像進行對比,可以看出文中提出的壓縮算法在一定程度上減少了數(shù)據(jù)量,總體得到了不錯的壓縮效果,證明了本文提出的譜小波壓縮方案的可行性.這是由于選取了合適的參數(shù),突出了圖像重構(gòu)中較大小波系數(shù)的重要性,而且基于塊編碼的算法較大程度地減少了較小的小波系數(shù),從而提高了壓縮比.

3.2 重構(gòu)誤差衡量

峰值信噪比(PSNR)表示峰值信號與噪聲的比值,它是表征圖像重構(gòu)效果的重要指標[13],PSNR評價模型定義如下:

式中,MES為均方誤差,是原始圖像與重構(gòu)圖像之間的灰度差,M和N為圖像矩陣維度數(shù)(圖像像素),l為圖像最大灰度值,通常 8 bit的圖像l為 255.PSNR值越大,表示重構(gòu)誤差越小,兩幅圖像相似度越高.

為驗證算法的有效性,設(shè)置不同的切比雪夫多項式階數(shù)m,得到圖像重構(gòu)結(jié)果如表2所示,在相同條件下m越小,相應(yīng)的圖像的PSNR也越高,重構(gòu)誤差就相對較小.

表2 不同 m 下的圖像重構(gòu)結(jié)果

分別以256×256和512×512像素的lena圖像為例進行相關(guān)實驗.選取掃描次數(shù)sm=6,尺度參數(shù)Nscales=5,切比雪夫多項式階數(shù)m分別取3和5,得到結(jié)果如圖2所示.對比不同m下的重構(gòu)圖像,可以看出,圖2(b)的重構(gòu)圖像與圖2(c)相比更接近原始圖像,也就是說,重構(gòu)誤差就相對較小.

圖2 256×256 像素的 lena 重構(gòu)圖像

圖3 512×512 像素的 lena 重構(gòu)圖像

3.3 相關(guān)算法的分析比較

選取256×256的lena和template圖像,利用上述壓縮比Cr和峰值信噪比PSNR的定義式,我們可以在相同條件下,利用本文的算法與基于小波變換的SPECK編碼算法計算得到不同尺度下的Cr值和PSNR值,結(jié)果如表3所示.

表3 基于不同變換的編碼算法的圖像壓縮重構(gòu)結(jié)果

表3中的數(shù)據(jù)顯示,本文提出的壓縮算法與基于小波變換的壓縮算法相比較,有更大的壓縮比,這說明譜圖小波壓縮的壓縮效果更為明顯.并且隨著尺度的改變壓縮比變化很小,圖像重構(gòu)質(zhì)量也相對穩(wěn)定.

綜上所述,本文提出的壓縮算法在對幾個經(jīng)典圖像進行壓縮編碼后,均取得了較好的壓縮比.且與基于小波變換的編碼算法進行對比,在減少占用內(nèi)存空間和重構(gòu)誤差方面都有了一定的改進.

4 結(jié)論與展望

本文采用基于譜圖理論和經(jīng)典小波變換理論的譜圖小波變換,提出了一種針對譜小波系數(shù)利用SPECK編碼進行壓縮編碼的新方法.文中對幾個經(jīng)典的圖像進行了性能測試,均取得了不錯的壓縮效果,并從壓縮比和峰值信噪比兩個方面討論了圖像壓縮及重構(gòu)的質(zhì)量,該算法在減少數(shù)據(jù)存儲空間和重構(gòu)誤差方面都有了一定的改進.但是對于大圖來講,編解碼的速度相對較慢,這也是未來繼續(xù)研究的方向.

參考文獻

1Jansen M,Nason GP,on,Silverman BW,et al.Multiscale methods for data on graphs and irregular multidimensional situations.Journal of the Royal Statistical Society,2009,71(1): 97–125.[doi: 10.1111/rssb.2008.71.issue-1]

2Shuman DI,Narang SK,Frossard P,et al.The emerging field of signal processing on graphs: Extending highdimensional data analysis to networks and other irregular domains.IEEE Signal Processing Magazine,2013,30(3):83–98.[doi: 10.1109/MSP.2012.2235192]

3Narang SK,Gadde A,Ortega A.Signal processing techniques for interpolation of graph structured data.Proceedings of 2013 IEEE International Conference on Acoustics,Speech and Signal Processing.Vancouver,BC,Canada.2013.5445–5449.

4Hammond DK,Vandergheynst P,Gribonval R.Wavelets on graphs via spectral graph theory.Applied and Computational Harmonic Analysis,2011,30(2): 129 –150.[doi: 10.1016/j.acha.2010.04.005]

5Narang SK,Ortega A.Downsampling graphs using spectral theory.Proceedings of 2011 IEEE International Conference on Acoustics,Speech and Signal Processing (ICASSP).Prague,Czech Republic.2011.4208–4211.

6Narang SK,Chao YH,Ortega A.Critically sampled graphbased wavelet transforms for image coding.Proceedings of 2013 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference.Kaohsiung,China.2013.1–4.

7Sakiyama A,Tanaka Y.Edge-aware image graph expansion methods for oversampled graph Laplacian matrix.Proceedings of 2014 IEEE International Conference on Image Processing (ICIP).Paris,France.2014.2958–2962.

8Sandryhaila A,Moura JMF.Discrete signal processing on graphs: Graph fourier transform.Proceedings of 2013 IEEE International Conference on Acoustics,Speech and Signal Processing.Vancouver,BC,Canada.2013.6167–6170.

9Sakiyama A,Watanabe K,Tanaka Y.Spectral graph wavelets and filter banks with low approximation error.IEEE Transactions on Signal and Information Processing over Networks,2016,2(3): 230–245.[doi: 10.1109/TSIPN.2016.2581303]

10Pearlman WA,Islam A,Nagaraj N,et al.Efficient,lowcomplexity image coding with a set-partitioning embedded block coder.IEEE Transactions on Circuits and Systems for Video Technology,2004,14(11): 1219–1235.[doi: 10.1109/TCSVT.2004.835150]

11張紅萍.SPECK圖像編碼算法的研究與改進[碩士學(xué)位論文].西安: 西安電子科技大學(xué),2008.

12陳思佳.一種改進的嵌入式小波圖像編碼算法.現(xiàn)代計算機,2013,(8): 20–24.

13佟雨兵,張其善,祁云平.基于PSNR與SSIM聯(lián)合的圖像質(zhì)量評價模型.中國圖象圖形學(xué)報 ,2006,11(12):1758–1763.[doi: 10.11834/jig.2006012307]