基于小波變換和分類矢量量化的圖像壓縮算法

1、基于小波變換和分類矢量量化的圖像壓縮算法黃晴，張書玲（西北大學 數(shù)學系，陜西 西安 710069）摘要：提出一種用于圖像壓縮的分類矢量量化算法，該算法在對圖像進行多級小波變換后，利用3個方向上各自小波系數(shù)之間的相關(guān)性，構(gòu)造符合圖像特征的跨頻帶矢量，依據(jù)矢量能量和零樹矢量綜合判定進行矢量分類，并采用了基于人眼視覺特性的加權(quán)均方誤差準則和基于成對最近鄰算法(PNN)的LBG算法進行矢量量化，提高了圖像的編碼效率和重構(gòu)質(zhì)量。仿真結(jié)果表明，該算法實現(xiàn)簡單，在較低的編碼率下，可達到較好的壓縮效果。關(guān)鍵詞：小波變換，跨頻帶矢量構(gòu)造，矢量分類，矢量量化中圖分類號：TN911.73 文獻標識碼：A 文章編號：

2、1000-274X(2003)0041-06圖像壓縮在圖像的傳輸和存儲中起著至關(guān)重要的作用。小波變換1,2由于具有良好的時-頻局部化性能，有效地克服了傅立葉變換在處理非平穩(wěn)的復(fù)雜圖像信號時所存在的局限性，因而在圖像壓縮領(lǐng)域受到了廣泛的重視，已出現(xiàn)了許多較為成熟的算法，如EZW編碼3，SPIHT編碼4等。Shapiro利用零樹處理圖像小波系數(shù)，有效地利用了帶間相關(guān)性和帶內(nèi)相關(guān)性，獲得了較高的編碼效率。由Shannon信息論理論知道，對于無記憶信源，矢量量化總是優(yōu)于標量量化。給定碼率時，維數(shù)任意大的矢量量化可以任意接近率失真下界。由于小波逆變換具有一定的平滑作用，小波變換域內(nèi)作矢量量化不會出現(xiàn)明顯

3、的方塊效應(yīng)，所以具有較好的圖像壓縮效果。近年來，也出現(xiàn)了一些將小波變換與矢量量化相結(jié)合的編碼方案5-7，文獻8研究表明，使用分類矢量量化可以獲得高質(zhì)量圖像。基于以上零樹編碼和矢量量化的思想，本文提出一種新的圖像壓縮算法。此算法先對圖像進行四級小波變換，得到3個方向上的四級高頻子帶，再根據(jù)3個方向不同頻帶系數(shù)之間的同構(gòu)特征來構(gòu)造跨頻帶矢量，通過對矢量能量和3個方向零樹矢量的綜合判定將矢量分類，然后再采用基于人眼視覺特性的WMSE準則和基于成對最近鄰算法(PNN)的LBG算法對重要類矢量進行加權(quán)矢量量化，以實現(xiàn)圖像的數(shù)據(jù)壓縮。1算法原理1.1圖像小波分解的特點和跨頻帶矢量的構(gòu)造小波變換是一種非平穩(wěn)

4、信號的分析方法，其基本思想是用一族函數(shù)來表示或逼近一個函數(shù),這族函數(shù)稱為小波函數(shù)。實際小波變換中，為了方便，多采用二進小波變換。對空間中的任意函數(shù)，它的二進小波變換為(1)其中，而滿足。將小波變換一維推廣到二維就可用于圖像處理。通過水平和垂直濾波，可分離二維小波變換將原始圖像分解為水平垂直對角和低頻4個子帶，其中低頻部分可繼續(xù)進一步分解。圖像經(jīng)小波變換后所得到的系數(shù)有特殊性質(zhì)。在不同尺度的高頻子帶圖像之間存在同構(gòu)特性，而且3個方向上不同尺度下的小波系數(shù)能量大小不同，各方向的側(cè)重不同。在同一方向上，有更強的同構(gòu)性和相似性，事實上，各方向不同尺度下對應(yīng)頻帶的相關(guān)性是最強的。為提高矢量量化的編碼效率

5、，在構(gòu)造矢量時，必須充分利用這些相關(guān)性。此外，圖像的能量主要集中在低頻子帶，高頻子帶所占能量較少，且不同分辨率不同高頻子帶中的分布非常相似，接近Gamma分布或Laplace分布。各高頻子帶系數(shù)大部分分布在零值附近，概率密度分布曲線的中心點和最大值為零。這樣，對帶內(nèi)及帶間相關(guān)性的充分利用和對零值附近小波系數(shù)的有效處理，就成為提高圖像壓縮效率的關(guān)鍵。高性能的矢量量化器必須依照圖像小波系數(shù)的特性來構(gòu)造矢量。使用不同子帶的系數(shù)構(gòu)成矢量來壓縮小波系數(shù)，就可以利用不同尺度同方向小波系數(shù)的相關(guān)性。根據(jù)以上分析，本文采用三方向跨頻帶矢量構(gòu)造方法9。小波變換將圖像分解為4層共13個子帶的塔形結(jié)構(gòu)，各方向以樹形

6、關(guān)系從各子圖中取大小為的系數(shù)塊，按圖1所示的方法構(gòu)成85維矢量。這樣構(gòu)造出來的跨頻帶矢量能夠充分利用小波系數(shù)的帶間和帶內(nèi)相關(guān)性，但同時也帶來計算量過大的問題。又在圖像的多分辨分解中，分辨率越低的頻帶，小波系數(shù)所包含的圖像信息越多，對圖像重構(gòu)更為重要，而分辨率越高的頻帶所包含的圖像信息越少。因此，為降低矢量量化編碼的復(fù)雜度，對每個85矢量的后64維矢量取均值，使矢量維數(shù)大幅度減小為22維。這樣就構(gòu)造出了3個方向小波系數(shù)的跨頻帶矢量。圖13個方向跨頻帶矢量的構(gòu)造Fig.1 Band-cross vector construction of wavelet parameters1.2小波零樹和3個方

7、向跨頻帶矢量的分類由小波圖像的多分辨率解析特點，大量的小波系數(shù)分布在零值附近，并且具有明顯的方向性，構(gòu)造出的跨頻帶矢量也就具有不同的能量和方向特征，通過對矢量進行分類后，用各自獨立的碼書分別進行量化，可以更有效的利用各子帶間的相關(guān)性。矢量的能量大小決定了其對于恢復(fù)圖像質(zhì)量的貢獻程度，矢量能量越大，對恢復(fù)圖像質(zhì)量的貢獻程度越高，所以能量可以作為矢量重要與否的一個判定準則。其次，本文按四叉樹規(guī)則構(gòu)造矢量，與零樹編碼的思想是一致的。零樹3是基于小波系數(shù)相關(guān)性的一種假設(shè)：如果在低分辨率高頻子帶上的小波系數(shù)相對于閾值是無意義的或是不重要的，那么位于同方向同空間位置高分辨率子帶上的小波系數(shù)相對于在統(tǒng)計意義

8、下也是無意義的，把滿足這種假設(shè)的系數(shù)用樹狀結(jié)構(gòu)表示出來就是零樹。零樹矢量對恢復(fù)圖像質(zhì)量的貢獻很小。若一個零樹矢量同時能量滿足小于給定的能量閾值，就可以看作非重要類，不再進行量化編碼，把其中的每一個分量置為0，并且用一個比特作標記，記為0；而其他矢量均看作重要類，標記為1，進行較大碼書尺寸的矢量量化，以減小量化誤差。采用能量閾值和零樹矢量的雙重判斷，既充分利用了子帶相關(guān)性，又有效的保護了圖像的重要信息。1.3重要類矢量量化的加權(quán)均方誤差準則在圖像的塔式小波分解算法中，大尺度下數(shù)據(jù)在恢復(fù)圖像時經(jīng)過濾波的次數(shù)要多，因而量化誤差對恢復(fù)圖像的質(zhì)量將產(chǎn)生較大影響，且影響的空間范圍比較小尺度下的數(shù)據(jù)要大，因

9、此適合于采用基于人眼視覺特性的WMSE準則進行最佳矢量的匹配，以提高量化增益。（2）其中：為矢量維數(shù)；為加權(quán)系數(shù)。文獻8利用人眼的視覺特性對灰度圖像設(shè)計了一種加權(quán)量化方案，以減小量化噪聲，本文采用文獻8中給出的各級子帶對應(yīng)加權(quán)系數(shù)，如表1所示。表1各級子帶加權(quán)系數(shù)Tab.1 Weight coefficients of subbands子帶名HL4LH4HH4HL3LH3HH3HL2LH2HH2HL1LH1HH1加權(quán)系數(shù)0.7380.7380.5960.5840.5840.4110.3550.3550.2300.1890.1890.1191.4初始碼書生成的PNN10算法在矢量量化中用LBG算

10、法11訓練碼書時，初始碼書的設(shè)計一般采用分裂算法。在分裂法中，對中間碼書的每個碼字都要一分為二，然后利用LBG算法形成碼字數(shù)目是原碼書的二倍的新碼書。這樣設(shè)計出的碼書其碼字均勻或近似均勻地分布在樣本空間，而實際信源是非均勻的，容易使得有些碼字利用率很低。為此本文采用成對最近鄰算法(PNN)10來生成初始碼書。PNN算法的步驟為：1）令碼字數(shù),將全部訓練矢量作為碼字，即,構(gòu)成個胞腔，第個胞腔的質(zhì)心為，所含矢量個數(shù)為。2） 計算各對碼字與間的失真 3）設(shè)，則合并胞腔和，更新碼字為，更新為，若，則從碼書中去掉碼字；否則令，從碼書中去掉碼字。令。4）若，則終止；否則轉(zhuǎn)2），繼續(xù)合并兩個最近的胞腔。2算

11、法實現(xiàn)小波變換編碼中，濾波器的選擇是個有待研究的問題。為便于在Matlab環(huán)境下的處理，本文采用最為簡單的Haar小波來作為濾波器，實際上，濾波器的選擇對編碼效果并沒有明顯的影響。另外，圖像的小波變換級數(shù)應(yīng)根據(jù)所期望的壓縮比來確定，一般用34級，例如，若用4級小波分解，則是原圖像大小的，一般對它作有限的無損壓縮，再加上其他信息，估計壓縮比不會高于。文中對輸入圖像使用對稱延拓方式作4級小波分解。最低分辨率級的低頻子帶對圖像恢復(fù)質(zhì)量影響很大，但數(shù)據(jù)量又小，所以不進行矢量量化，對其單獨處理。利用子帶系數(shù)之間的相關(guān)性，一般采用差分脈沖編碼調(diào)制(DPCM)加算術(shù)編碼對其進行壓縮，大約能壓縮兩倍左右。為了

12、能夠自適應(yīng)地確定各閾值，首先對矢量能量和最低分辨率級各高頻子帶系數(shù)作統(tǒng)計分析，依據(jù)矢量平均能量確定能量閾值，依據(jù)最低分辨率級各方向高頻子帶系數(shù)的幅度均值，確定各方向零樹矢量的判定閾值。這樣每個方向的矢量均可分為重要類和不重要類兩類，再對重要類進行大碼書的加權(quán)矢量量化。3仿真結(jié)果及結(jié)論采用4幅的標準圖像對系統(tǒng)性能進行模擬實驗仿真。實驗中所用碼書大小為，訓練序列大小為，碼字22維。3個方向上的重要類矢量分別使用算法進行訓練生成碼書。表2列出了測試圖像的小波系數(shù)矢量及最低分辨率子帶系數(shù)的統(tǒng)計結(jié)果，表中矢量平均能量定義為，其中為矢量個數(shù)，為矢量維數(shù)。仿真結(jié)果表明（見表3），本算法在未對量化結(jié)果進行熵編

13、碼時，對測試圖像的編碼效率已達到0.101 8 bpp（每個像素所使用的比特數(shù)）每個像素所使用的比特數(shù)，且恢復(fù)圖像視覺效果良好。若再進行熵編碼，可進一步提高壓縮比。為進一步說明重構(gòu)圖像的主觀質(zhì)量，圖3給出測試圖像和相應(yīng)的重建圖像。本文基于零樹編碼和分類矢量量化的思想，通過構(gòu)造3個方向的跨頻帶矢量，充分利用了各級子帶系數(shù)的帶間相關(guān)性和帶內(nèi)相關(guān)性，又通過能量閾值和零樹矢量的綜表2 測試圖像的統(tǒng)計結(jié)果圖 像矢量平均能量LH4幅值平均HL4幅值平均HH4幅值平均Lena0.339 40.002 9-0.063 3-0.010 2Oldhouse0.270 20.018 70.034 9-0.014 7

14、Goldhill0.211 70.049 4-0.023 5-0.009 4Camera0.405 40.039 4-0.026 2-0.009 4Tab.2 Statistics of test images表3算法性能統(tǒng)計Tab.3 Statistics of the algorithm performance原始圖像量化結(jié)果 / bpp壓縮比 / 倍峰值信噪比 / dBLena0.099 180.709 427.651 0Oldhouse0.084 095.290 430.265 6Goldhill0.101 878.592 127.916 8Camera0.091 587.395 92

15、5.572 6 Lena原圖 Lena恢復(fù)圖像 Oldhouse原圖 Oldhouse恢復(fù)圖像 Goldhill原圖 Goldhill恢復(fù)圖像 Camera原圖 Camera恢復(fù)圖像圖2仿真結(jié)果Fig.2 Simulation result合判定對各個方向上的矢量進行分類，再采用基于人眼視覺特性的WMSE準則對重要類矢量進行加權(quán)矢量量化。仿真結(jié)果表明，該算法實現(xiàn)簡單，在較低碼率下，可達到較好的壓縮效果。參考文獻：1 MALLAT S G. Multifrequency channel decomposition of images and wavelet modelsJ. IEEE Trans

16、 on ASSP, 1989, 37(12): 2 091-2 110.2 ATONINI M, BARLAUD M, MATHIEU P. Image coding using wavelet transformJ. IEEE Trans on Image Processing, 1992, 1(2): 205-220.3 SHAPIRO J M. Embedded image coding using zerotrees of wavelet coefficientJ. IEEE Trans on Signal Processing, 1993, 41(12): 3 445-3 462.4

17、 SAID A, PEARLMAN W. A new fast and efficient image code based on set partitioning in hierarchical treesJ. IEEE Trans on Circuits and System Video Tech, 1996, 6(3): 243-249.5 王 磊, 戚飛虎. 基于雙正交小波的快速矢量量化算法J. 上海交通大學學報, 1998, 6(32), 4-8.6 鄭 勇,胡小川,朱維樂.采用空間矢量組合的小波圖像分類矢量量化J. 電子與信息學報, 2002, 12(24): 1 892-1 89

18、8.7 潘建壽, 孫宏偉. 基于9/7雙正交小波的一種高效矢量量化算法J. 電子與信息學報, 2002, 7(24): 900-904.8 DESARTE P, MACQ B, SLOCK D. Signal-adapted multiresolution transform for image codingJ. IEEE Trans on Information Theory, 1992, 38(2): 897-904.9 PAMELA C, ROBERT M G, MARTIN V. Vector quantization of image subbards: a surveyM. IEE

19、E Trans on Image Processing, 1996,5(2):202-225.10 孫圣和, 路哲明. 矢量量化技術(shù)及應(yīng)用M. 北京: 科學出版社,2002.11 LINDE Y, BNZO A, GRAY R. An algorithm for vector quantizer designJ. IEEE Trans on Comm, 1980, 28(1): 84-95.（編輯：曹大剛） Image compression based on wavelet transform and classified vector quantizationHUANG Qing, ZHA

20、NG Shu-ling(Department of Mathematics, Northwest University, Xian 710069, China)Abstract: A new image compression algorithm, based on wavelet transform and classified vector quantization, is presented. First, wavelet transform decomposes the original image, then the correlation of the three directions wavelet coefficients is used to construct the band-cross vec