基于多小波的彩色圖像分層樹集合分裂算法

陳俊麗, 卿定湖, 李 翔, 萬旺根

(上海大學(xué)通信與信息工程學(xué)院,上海 200072)

基于多小波的彩色圖像分層樹集合分裂算法

陳俊麗, 卿定湖, 李 翔, 萬旺根

(上海大學(xué)通信與信息工程學(xué)院,上海 200072)

提出一種基于多小波變換的改進(jìn)的彩色圖像分層樹集合分裂 (set partitioning in hierarchical trees,SPIHT)算法,將彩色 RGB圖像轉(zhuǎn)換到 YCbCr色彩域,Y通道分配到 2倍于 Cb,Cr的比特,在各色彩通道間構(gòu)造新的方向樹結(jié)構(gòu),重組圖像多小波分解系數(shù),進(jìn)行嵌入式多小波彩色圖像 SPIHT編碼.結(jié)果表明,該算法具有良好的編碼效果,性能優(yōu)于 9/7單小波編碼.

多小波;分層樹集合分裂;嵌入式編碼;空間方向樹;圖像壓縮

本研究利用彩色圖像各分量之間的相關(guān)性,在SPIHT算法的空間方向樹結(jié)構(gòu)基礎(chǔ)上引入新的空間方向樹結(jié)構(gòu),并結(jié)合圖像多小波變換后系數(shù)分布的特點(diǎn),提出改進(jìn)的多小波彩色圖像 SPIHT算法,提高了多小波彩色圖像的編碼效率.

1 圖像的多小波變換

1.1 多小波理論

多小波 (multiwavelet)是指由 2個(gè)或 2個(gè)以上函數(shù)作為尺度函數(shù)生成的小波.與單小波相比,多小波同時(shí)具有對(duì)稱性、短支撐性、正交性以及高階消失矩等良好特性,因此,多小波在信號(hào)和圖像處理方面具有明顯優(yōu)勢(shì).

設(shè)向量函數(shù) Φ (t)=(φ1(t),φ2(t),…,φr(t))T,φi∈L2(R),i=1,2, …,r.對(duì) j∈Z,定義L2(R)空間中的閉子空間 Vj={2j/2φi(2jt-k):1≤i≤r,k∈Z}.若空間序列 Vj滿足下列條件:

(5){φi(2jt-k):1≤i≤r,k∈Z}為 V0空間的Riesz基,則函數(shù)Φ生成 L2(R)空間的多分辨分析(multi-resolution analysis,MRA),且稱Φ為 r重多尺度函數(shù).若 {φi(2jt-k):1≤i≤r,k∈Z}為 V0的正交基,則稱 {Vj}為正交 MRA.對(duì)正交 MRA,定義Vj+1=Vj⊕ Wj,即 Wj為 Vj在 Vj+1中的正交補(bǔ).若存在ψ1,ψ2,…,ψr,使得其整數(shù)平移構(gòu)成 W0的正交基 ,則Ψ (t)=(ψ1(t),ψ2(t),…,ψr(t))T為 r重正交多小波,且Φ(t),Ψ(t)滿足如下雙尺度方程:

式中,hk,gk都為 r×r階的濾波器矩陣.

將單小波中分解與重構(gòu)的Mallat算法推廣至多小波,可以得到如下多小波的分解與重構(gòu)算法:

式中,Cj,k= (c1,j,k,c2,j,k,…,cr,j,k)T,Dj,k= (d1,j,k,d2,j,k,…,dr,j,k)T,j,k∈Z,,為 hm,gm的共軛轉(zhuǎn)置.與單小波不同,在多小波情況下進(jìn)入Mallat算法的初始尺度系數(shù)為矢量,因此,必須先對(duì)信號(hào)進(jìn)行預(yù)處理.相應(yīng)地,重構(gòu)時(shí)還需進(jìn)行后濾波.

1.2 圖像多小波系數(shù)的重組策略

對(duì)圖像進(jìn)行多小波變換時(shí),應(yīng)先對(duì)圖像的行和列進(jìn)行前置濾波,并按一定的規(guī)則將前置濾波圖像的行和列組成向量信號(hào),再進(jìn)行多小波變換.由于有多個(gè) (r)尺度 (小波)函數(shù)的存在,在多小波變換后有 r2個(gè)子塊.若分解級(jí)數(shù)為 L,則 L級(jí)多小波變換將圖像分解為 r2(3L+1)個(gè)子塊,如圖 1所示.

基于小波變換的圖像壓縮算法中,EZW算法和SPIHT算法較好地利用了不同子帶間小波系數(shù)的相似性,使得輸出的比特流具有嵌入式特性,但這 2種方法均是針對(duì)單小波變換.由于經(jīng)過多小波變換后,產(chǎn)生了不同于單小波變換的子帶結(jié)構(gòu),破壞了上述算法所假設(shè)的零樹結(jié)構(gòu),因此,需要根據(jù)圖像多小波變換的特點(diǎn),對(duì)多小波系數(shù)進(jìn)行重新排列,以達(dá)到SPIHT編碼要求 (見圖 2).

對(duì)于 GHM多小波來說,分解后的每個(gè)子帶的2×2個(gè)子塊間存在大量相關(guān)性.為了保持這種相關(guān)性,將每個(gè) 2×2子塊的系數(shù)進(jìn)行重組,將對(duì)應(yīng)于同一空間位置的系數(shù)放在一起,形成 4個(gè)子帶LL,LH,HL和 HH.圖 2(b)為經(jīng)過系數(shù)重組后生成新的子帶.

對(duì)于 CL和 SA4多小波,由于多尺度函數(shù)的第 2個(gè)分量是反對(duì)稱的,相應(yīng)的濾波器組的第 2個(gè)通道是帶通的,所以子塊 L0L1,L1L0和 L1L1具有帶通性,而L0L0子塊具有低通性,存在不相似譜行為,不需要進(jìn)行系數(shù)重組.因此,對(duì)于CL和SA 4多小波 ,只考慮對(duì)每個(gè)高頻子帶的 2×2個(gè)子塊系數(shù)進(jìn)行重組,生成 LH,HL,HH子帶.圖 2(c)給出了 SA 4多小波分解及系數(shù)重組后的子帶結(jié)構(gòu).經(jīng)過系數(shù)重組后,不僅達(dá)到 SPIHT編碼要求,而且充分利用了某個(gè)方向子帶之間的相關(guān)性,得到了更高的壓縮效率.

圖 1 基于多小波變換的圖像分解Fig.1 Image decomposition based on multiwavelet transform

圖 2 多小波系數(shù)重組方法Fig.2 Rearrangement of multiwavelet transform coeff icients

2 多小波彩色圖像 SPIHT算法

2.1 SPIHT算法

SPIHT算法是一種改進(jìn)的 EZW編碼方法,該算法將系數(shù)組織在以下 3個(gè)集合表中:L IP(不重要系數(shù)表)、L IS(不重要集合表)和 LSP(重要系數(shù)表).簡(jiǎn)單的彩色圖像壓縮編碼方法是將彩色圖像的YCbCr 3個(gè)色彩通道分離,各自獨(dú)立地進(jìn)行編碼傳輸.3個(gè)色彩平面就有 3個(gè)空間方向樹 (spatial orientation tree,SOT)結(jié)構(gòu)和 3組 L IP,L IS和 LSP集合.編碼后的碼流不具備嵌入式特性,因此,必須等待 3個(gè)分量的碼流全部到達(dá)解碼端才能進(jìn)行解碼操作,然后恢復(fù)圖像.而本算法依照 SPIHT的定義,使每一個(gè)色彩平面形成各自的 SOT、初始化時(shí),L IP和L IS的值來自于 3個(gè) SOT的根節(jié)點(diǎn),隨著 SPIHT算法的執(zhí)行,比特流在 3個(gè)色彩通道之間自動(dòng)分配,從而解決了碼率的不可嵌入式問題,因此,可稱該算法為 D_SPIHT算法.

彩色圖像轉(zhuǎn)換到 YCbCr色彩域后,同一個(gè)像素點(diǎn)的 Y值通常要比 Cb,Cr值大很多,即亮度通道的小波變換系數(shù)通常大于 2個(gè)色度通道.因此,對(duì)彩色圖像高比特平面 (編碼的系數(shù)來自亮度通道)編碼時(shí),抑制色度通道中不必要的比特輸出,可以有效地提高編碼效率.

2.2 改進(jìn)空間方向樹結(jié)構(gòu)的彩色圖像 SPIHT算法

對(duì)于自然圖像,當(dāng)色度分量存在較大系數(shù)時(shí),相應(yīng)位置的亮度分量也存在相對(duì)較大的系數(shù).彩色嵌入式零樹小波 (color embedded zerotree wavelet,CEZW)算法的零樹結(jié)構(gòu)充分利用了 YCbCr分量之間的相關(guān)性 (見圖 3(a)),每一個(gè)亮度 Y節(jié)點(diǎn)不但在本通道內(nèi)有子節(jié)點(diǎn),在其他 2個(gè)色度通道內(nèi)也有子節(jié)點(diǎn).亮度通道小波系數(shù)的模值通常要比色度通道的模值大很多,因此,在初始階段,編碼的顯著性系數(shù)大多來自于亮度通道.用 wY,wCb和 wCr分別表示 Y,Cb和 Cr通道的小波系數(shù)模極大值,并設(shè):

顯然,有M ＞N.在 L IP列表中色度分量至少要經(jīng)過M-N次排序,重要系數(shù)則放入 LSP列表中.如果圖像尺寸較大,則初始化時(shí)大量 Cr,Cb通道的小波系數(shù)置于 L IP和 L IS列表內(nèi),編碼時(shí)將會(huì)產(chǎn)生過多無效的 0比特,浪費(fèi)了資源,降低了編碼效率.為了更有效地利用 Y,Cb,Cr分量之間的相關(guān)性,提高編碼效率,本研究提出了一種彩色圖像 SPIHT(colour-SPIHT,CSPIHT)零樹結(jié)構(gòu),通道節(jié)點(diǎn)間的父子關(guān)系如圖 3(b)所示.

圖 3 節(jié)點(diǎn)間的父子關(guān)系Fig.3 Parent-children node relation

在 CSPIHT零樹結(jié)構(gòu)中,對(duì)于低頻子帶中沒有子孫節(jié)點(diǎn)的 Y分量節(jié)點(diǎn),存在色度分量 Cb,Cr低頻子帶中相應(yīng)位置的 4個(gè)子節(jié)點(diǎn),通道間和通道內(nèi)的空間方向樹結(jié)構(gòu)如圖 4所示.在初始化 L IS和 L IP列表時(shí),僅僅將 Y分量的低頻子帶節(jié)點(diǎn)添加到 L IS和L IP中.當(dāng)L IS表中的Y通道父節(jié)點(diǎn)被掃描到是重要系數(shù)時(shí),該色度分量節(jié)點(diǎn)才被添加到列表中進(jìn)行處理.這樣就避免了將大量的色度分量添加到L IP和 L IS列表中,節(jié)約了資源.

圖 4 CSPIHT中空間方向樹結(jié)構(gòu)Fig.4 Spatial or ientation tree structure in d ifferent spectral p lanes in the CSPIHT schem e

3 仿真結(jié)果及分析

實(shí)驗(yàn)性能用峰值信噪比 (peak signal to noise ratio,PSNR)來衡量.設(shè)原始圖像 x的大小為 M ×N,重構(gòu)后的圖像為 x^,則峰值信噪比定義為

表1 測(cè)試平臺(tái)Table 1 Test platform

本研究選用 24 bit RGB 512×512 Lena和 512×512 Baboon作為測(cè)試圖像,因?yàn)樗鼈兎謩e表示低頻含量較高的圖像與高頻含量較高的圖像.在多小波分解前,先將圖像轉(zhuǎn)換到 YCbCr色彩域,編碼比特率為 0.1比特 /像素 (壓縮率 240∶1).分別用雙正交 9/7單小波,GHM,CL和 SA 4多小波對(duì)圖像進(jìn)行4層和 5層分解,并進(jìn)行多小波分解系數(shù)重組.表2為各圖像的 PSNR性能比較.

從表2可知,對(duì)于 Lena圖像,當(dāng)分解層次為 4層時(shí),即 LL子帶尺寸相對(duì)較大時(shí),采用雙正交 9/7單小波和 GHM多小波 CSPIHT算法的壓縮結(jié)果要優(yōu)于 D_SPIHT算法;當(dāng)采用 CL和 SA 4多小波時(shí),重建圖像的 PSNR大大提高;當(dāng)分解層次為 5層時(shí),用9/7單小波處理的效果明顯改善,略超過 CL多小波,但是仍然略遜于 SA4多小波的處理效果.研究結(jié)果表明,多小波彩色Lena圖像的壓縮性能已經(jīng)接近雙正交 9/7單小波.

對(duì)于Baboon圖像,由于其包含大量的高頻內(nèi)容,因而較難壓縮.即使在低壓縮比下,重構(gòu)的圖像中也會(huì)出現(xiàn)許多瑕疵.實(shí)驗(yàn)結(jié)果表明,GHM多小波的壓縮性能已經(jīng)接近雙正交 9/7單小波,CL和 SA 4多小波超過了雙正交 9/7單小波.但是,不管分解 4層還是 5層,CSPIHT算法的性能都要優(yōu)于 D_SPIHT算法.

表2 彩色圖像壓縮算法的 PSNR性能比較Table 2 PSNR compar isons of color images SPIHT based on wavelet and multiwavelet dB

4 結(jié) 束 語

本研究利用圖像多小波變換后各個(gè)子塊之間的相關(guān)性,重排系數(shù),保持了多小波系數(shù)的零樹特征.針對(duì)彩色圖像各分量之間的關(guān)系,引入了新的空間方向樹結(jié)構(gòu),提出了改進(jìn)多小波彩色圖像 SPIHT算法.仿真結(jié)果表明,在相同壓縮比的情況下,改進(jìn)的CSPIHT算法可以獲得更高的峰值信噪比.

[1] ATES H F,ORCHARD M T.Spherical coding algorithm for wavelet image compression[J]. IEEE Transactions on Image Processing,2009,18(5):1015-1024.

[2] DONGW S,SH I GM,XU J Z.Adap tive nonseparable interpolation for image compression with directional wavelet transform[J].IEEE Signal Processing Letters,2008,15:233-236.

[3] PAN H,SIU W C,LAW N F.Lossless image compression using binary wavelet transform [J]. IET Image Processing,2007,1(4):353-362.

[4] ADAM IN,SIGNORONIA,LEONARDIR.State-of-the-art and trends in scalable video compression with waveletbased app roaches[J]. IEEE Transactions on Circuits and Systems for Video Technology,2007,17(9):1238-1255.

[5] SHAPRIO JM.Embedded image coding using zerotree of wavelet coefficients[J]. IEEE Transactions on Signal Processing,1993,41(12):3445-3462.

[6] SA ID A,PEARLMAN W.A new fast and efficient image codec based on setpartitioning in hierarchical trees[J].IEEE Transactions on Circuits and Systems for Video Technology,1996,6(3):243-249.

[7] KHAN M A,KHAN E.Error resilient technique for SPIHT coded color images [C]∥ International Multimedia, Signal Processing and Communication Technologies.2009:237-240.

[8] CHEW L W,ANG L M,SENG K P.Low memory stripbased image compression for color images[C]∥International Conference on Intelligent Human-Machine Systems and Cybernetics.2009:363-366.

[9] CHIEN J C,L ICC.3D multiwaveletpacketson low bitrate color video compression [C]∥ International Conference on Wavelet Analysis and Pattern Recognition.2007:280-285.

[10] WANG A L,L IU P G,CHEN Y S.Multiwavelet-based region of interest image coding[C]∥ International Congresson Image and Signal Processing.2009:1-4.

Set Par tition ing in Hierarchical Trees Algor ithm for Color Images Based on M ultiwavelet

CHEN Jun-li, QINGDing-hu, L IXiang, WAN Wang-gen
(School of Communication and Information Engineering,ShanghaiUniversity,Shanghai200072,China)

We proposes an improved color set partitioning in hierarchical trees(SPIHT)algorithm based on multiwavelet.The algorithm convertsa RGB color image into the YCbCr format.Clearly,bitsassigned to luminance Y p lane are twice than that Cb and Cr chrominance p lanes.A new spatial orientation tree structure is developed between channel p lanes based on SPIHT coding.We embed multiwavelet SPIHT codes for color imageswith the re-combined multiwavelet coefficients.The results show that performance of the proposed codingmethod is superior to SPIHT on 9/7 wavelet.

multiwavelet;set partitioning in hierarchical trees(SPIHT);embedded coding;spatial orientation tree;image compression

O 174.2

A

1007-2861(2011)01-0039-05

10.3969/j.issn.1007-2861.2011.01.006

2010-04-02

國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863計(jì)劃)資助項(xiàng)目(2007AA01Z319);上海市教委重點(diǎn)學(xué)科建設(shè)資助項(xiàng)目 (J50104)

陳俊麗 (1972～),女,副教授,博士,研究方向?yàn)樾〔ê投嗝襟w信息處理.E-mail:jlchen@staff.shu.edu.cn

(編輯:趙 宇 )

在數(shù)字圖像和視頻圖像編碼領(lǐng)域,小波變換具有時(shí)頻局部性、正交性等特性,與基于離散余弦變換(discrete cosin transform,DCT)的編碼技術(shù)相比較,可獲得更高的信噪比 (壓縮率相同時(shí))或壓縮率 (信噪比相同時(shí)),因而得到廣泛的關(guān)注,并已應(yīng)用于MPEG-4和 JPEG2000圖像壓縮國(guó)際標(biāo)準(zhǔn)[1-4].

1993年,Shaprio[5]提出了嵌入式零樹小波(embedded zerotree wavelet,EZW)編碼方法,取得了良好的圖像壓縮效果.1996年,Said等[6]基于EZW的基本思想,提出了分層樹集合分裂 (set partitioning in hierarchical trees,SPIHT)算法.該算法采用空間方向樹表示小波系數(shù)的零樹結(jié)構(gòu),提高了編碼效率.對(duì)于彩色圖像,一般采用直接對(duì) 3個(gè)彩色分量分別進(jìn)行零樹編碼的方法.雖然 SPIHT算法直觀簡(jiǎn)單,但是并沒有充分利用彩色圖像各分量之間的相關(guān)性,降低了編碼效率.文獻(xiàn) [7-8]從降低誤差和減少計(jì)算量的角度對(duì)彩色圖像的 SPIHT編碼算法進(jìn)行了詳細(xì)分析.在圖像處理過程中,正交性能夠?qū)崿F(xiàn)圖像的精確重構(gòu).然而在實(shí)數(shù)域中,同時(shí)具有緊支、對(duì)稱、正交的非平凡單小波是不存在的,而多小波由于同時(shí)具有正交性、緊支撐性、對(duì)稱性和高的逼近階等特性,越來越受到人們的重視[9-10].