基于小波變換的分類矢量量化編碼

鄭秋梅，閔利田

0 引言

小波分析[1-2]是一種信號的時間－尺度（時間－頻率）分析方法，它具有多分辨分析的特點，而且在時頻兩域都具有表征信號局部特征的能力，是一種窗口大小固定不變但其形狀可以改變的時頻局部化分析方法。有效的克服了傅立葉變換在處理非平穩(wěn)的復(fù)雜圖像信號時所存在的局限性。因而被廣泛應(yīng)用于圖像處理領(lǐng)域。迄今為止,人們已經(jīng)提出了許多基于小波的圖象壓縮方法,如基于小波的零樹編碼方法,基于小波的分形編碼方法,基于小波的矢量量化方法等等。根據(jù)香農(nóng)率失真理論，矢量量化比標(biāo)量量化（矢量量化是標(biāo)量量化的擴展）效果好。只要碼矢數(shù)足夠大, 碼矢維數(shù)足夠高,則矢量的量化誤差能夠得到香農(nóng)所規(guī)定的下限。研究表明，利用小波變化和矢量量化相結(jié)合的方法，能夠取得較好的壓縮效果。

本文提出了一種新的高壓縮比圖像壓縮算法，結(jié)合小波變換和矢量量化的優(yōu)點，圖像經(jīng)過3級小波變換后，同方向各級子帶的小波系數(shù)按照四叉樹規(guī)則構(gòu)成矢量，然后按照矢量的能量進行分類矢量量化，該方法的矢量組成充分考慮了小波系數(shù)帶內(nèi)以及帶間的相關(guān)性，采用分類矢量量化，可以對不同方向的矢量采用不同的量化策略，可以大大減少編碼比特。

1 算法原理

1.1 小波變換

小波是由一個函數(shù) )(xψ經(jīng)伸縮和平移得到的一組函數(shù)

其中(x)ψ就稱為基本小波或母小波，它滿足相容條件：

其中(ωψ是)(x)ψ的傅立葉變換。對于任意的函數(shù)或者信號其小波變換定義為：

對于連續(xù)小波變換，可通過對其尺度參數(shù)a和平移參數(shù)b的采樣而離散化，從而形成離散小波變換。

S.Mallat于1988 年提出了小波多分辨分析算法,十分適合于分析圖像。1989年,Daubechies用基于離散濾波器迭代的方法構(gòu)造了緊支集的規(guī)范正交小波基，從而使小波分析廣泛用于圖像分析,而且從理論上證明,正交小波分解后的信號可以精確地恢復(fù)原始信號。

根據(jù)小波變換理論,一幅圖像經(jīng)過若干級小波分解后,可得到一系列不同方向(分辨率)的多種子帶(子圖像),而且這些子帶具有4個特點：[3]

(1) 不同方向的子帶對應(yīng)的頻率不同；

(2) 圖像的能量主要集中在低頻子帶,高頻子帶所占的能量很少；

(3) 相同方向不同尺度子帶之間具有相關(guān)性(縱向相關(guān))；

(4) 不同方向不同尺度子帶也具有相關(guān)性(橫向相關(guān)) ,即圖像能量在不同方向、不同尺度高頻子帶中的分布非常相似,接近Gamma或Laplacian分布。

小波分析是一種信號的時間－尺度（時間－頻率）分析方法，它具有多分辨分析的特點。即在低頻部分具有較高的頻率分辨率和較低的時間分辨率，在高頻部分具有較高的時間分辨率和較低的頻率分辨率，很適合于探測正常信號中夾帶的瞬變反常信號并分析其成分。圖像經(jīng)過小波變換以后的系數(shù)在不同方向都呈現(xiàn)出各種相關(guān)特性，在進行圖像處理的時候可以充分的利用這些相關(guān)特性，能夠取得較好的效果。

1.2 矢量的構(gòu)成

圖1 圖像3級小波分解示意圖

圖像經(jīng)小波分解后的系數(shù)存在的各種相關(guān)性，如同方向不同子帶之間的零樹性，同一子帶中相鄰系數(shù)之間的相關(guān)性等，如果能充分的考慮小波系數(shù)的各種相關(guān)性，就能夠得到較高的壓縮效率。

常見的矢量構(gòu)成方式有：(1) 在每一個子帶根據(jù)不同的碼率分配和失真度分別在不同子帶形成不同維數(shù)的矢量。(2)跨帶矢量構(gòu)成。這兩種方法只是單獨得利用了小波系數(shù)各種相關(guān)性中的一種，對小波系數(shù)的相關(guān)性沒有充分利用。本文的矢量構(gòu)成充分考慮了同一子帶和同方向不同子帶中小波系數(shù)的相關(guān)性，可以取得較高的壓縮比。具體組成方式如下：

如圖1所示，構(gòu)造矢量時,第三級各子帶(HH3、HL3和LH3)矢量大小為2×2;第二級各子帶(HH2、HL2和LH2) 矢量大小為4×4;第一級各子帶矢量大小為8×8。其中第二級子帶中的系數(shù)為第三級子帶系數(shù)的子節(jié)點，第一級子帶中的系數(shù)為第二級子帶系數(shù)的子節(jié)點，這樣總共構(gòu)成一個84維的矢量[4]。

與文獻[5] 構(gòu)成矢量的方法相比較，本文方法充分考慮了小波系數(shù)的各種相關(guān)性，能夠取得較高的壓縮比。但是由于矢量維數(shù)的提高，也導(dǎo)致算法運行時間過慢。因此可以考慮利用非線性插值方法對矢量進行降維，以提高算法效率。

1.3 分類矢量量化

由于圖像復(fù)雜多樣，形成的矢量也變化多端，因此要建立一個囊括各種變化的碼書不太可能，于是就出現(xiàn)了分類矢量量化，利用分類矢量量化可以對重要的矢量分配較大的碼書，對不重要的碼書分配較小的碼書，這樣就可以在保證一定峰值信噪比的情況下，獲得較高的壓縮比。

本文采用的分類策略如下：首先將矢量分為3類：水平方向，垂直方向和對角方向。對于不同方向的矢量可以采用不同的碼書尺寸進行量化。然后對各方向的矢量按照能量進行分類，設(shè)矢量維數(shù)為K,矢量能量可表示為

相對于一定的能量門限T，若W＞T則為重要矢量，否則則為非重要矢量，對于重要矢量對恢復(fù)圖像的質(zhì)量影響很大可以分配較大碼書，對于非重要矢量可以分配較小的碼書[5] 。

與文獻[4] 的方法對比，利用分類矢量量化以后，可以對不重要的矢量分配較小的碼書，可以進一步的提高壓縮比，同時碼書變小，還可以提高算法的時間效率。

1.4 非線性插值方法

在矢量量化中，一般希望矢量維數(shù)很大，這樣不但可以提高算法的壓縮比而且隨著矢量維數(shù)的增大，量化器的性能也會提高。但是對于給定的比特率，矢量量化的復(fù)雜度與矢量的維數(shù)呈指數(shù)規(guī)律遞增。本文提取84維矢量進行矢量量化，矢量維數(shù)較高，增加了矢量量化的復(fù)雜度。因此可以考慮使用非線性插值方法來降低矢量維數(shù)，同時起到降低算法復(fù)雜度的效果。

圖2 非線性插值矢量量化圖

如圖 2所示，量化器存在兩個碼書，其中編碼碼書C的維數(shù)要小于解碼碼書C*的維數(shù)，k維特征矢量u是從n維矢量x中抽取出來的，即u=g(x),其中k＜n。矢量u經(jīng)過編碼碼書C進行編碼，找出C中與u最近的碼矢，輸出標(biāo)號i，最后，通過解碼器在解碼碼書中搜索對應(yīng)于標(biāo)號i的碼矢X'，把X'作為x的量化估計。

假設(shè)訓(xùn)練矢量集Γ包含M個訓(xùn)練矢量xj，滿足訓(xùn)練率M/N＞＞1。對這些n維訓(xùn)練矢量進行特征提取，形成k維特征矢量集。用LBG算法對這些特征矢量集進行訓(xùn)練，可生成大小為N的碼書C。利用碼書C可將特征矢量集劃分為N個胞腔，相應(yīng)得將訓(xùn)練矢量集也分成了N個胞腔，即

從而碼書C*的第i個碼字ci可由下式計算：

本文在對矢量進行分類矢量量化時，對水平，垂直和對角 3個方向的矢量應(yīng)用非線性插值方法，我們?nèi)∈噶康那?0個分量構(gòu)成特征矢量，采用LBG算法訓(xùn)練產(chǎn)生20維的編碼碼書C，再由（6）式生成84維的解碼碼書C*。

1.5 最低頻子帶的處理

由于最低頻子帶含有圖像的大部分能量，為了保證恢復(fù)圖像的質(zhì)量，可以對該子帶單獨使用Huffman編碼進行壓縮。這樣可進一步提高壓縮圖像的壓縮比。

1.6 算法流程

本文算法的步驟可概括如下：

(1) 對圖像進行3級小波分解，對小波分解后的系數(shù)按照本文算法提取矢量。

(2) 對提取得矢量按照能量進行分類，對重要矢量和非重要矢量分別編碼。

(3) 應(yīng)用非線性插值矢量量化器進行矢量量化。

(4) 對水平，垂直和對角3個方向量化完畢之后，再對最低頻的小波系數(shù)單獨進行Huffman編碼。

2 實驗結(jié)果及分析

本文利用256個灰度等級(即8位量化)的512×512標(biāo)準(zhǔn)Lena圖像進行實驗，選取haar小波對圖像進行3級小波分解，這主要是因為haar小波能同時滿足正交和對稱性[7]。

對小波分解后的系數(shù)，按照本文算法組成矢量。表1列出了3個方向的平均能量。按照平均能量進行分類，利用LBG進行訓(xùn)練生成不同尺寸的碼書。對重要類矢量水平，對角和垂直3個方向的碼書長度取256，256和256，對非重要類矢量3個方向的碼書長度分別取128，128和128。實驗結(jié)果如表2所示。

表2 不同策略性能對比

試驗結(jié)果表明，本文算法在保證一定的PSNR值得情況下，獲得了較高的壓縮比。非線性插值方法的引入也使算法的運行時間相對于文獻[4]大幅度縮減。同時由于采用分類矢量量化，還可以根據(jù)不同的能量門限獲得不同的壓縮效率，能量門限越低，重要類矢量的個數(shù)越少，可以獲得更低的編碼率，實驗表明最低可達到0.048，此時所有矢量都被認為是非重要的矢量。但是相應(yīng)的峰值信噪比也會降低。

圖3

4 結(jié)束語

本文提出了一種新的矢量組成方式和分類矢量量化結(jié)合的方法，借助零數(shù)思想組成一個84維矢量，然后對矢量進行相應(yīng)的分類，分為水平，垂直和對角3個方向。然后根據(jù)矢量的能量進行重要度分類，對重要類矢量分配大的碼書，對非重要類矢量分配較小的碼書，同時結(jié)合非線性插值方法進行矢量量化。試驗結(jié)果表明，本算法能夠在保證較高峰值信噪比的情況下，獲得較低的編碼率，取得了令人滿意的結(jié)果。但是由于提取得矢量維數(shù)較大，雖然使用了非線性插值方法進行了相應(yīng)處理，相對于20維左右的矢量提取算法，本算法運行時間還是比較慢。而且使用非線性插值方法也增加了額外的開銷。因此本算法比較適用于對圖像質(zhì)量要求不高，而又希望圖像壓縮比比較高的情況。

[1] Mallat S. Multifrequency channel decomposition of images and wavelet models[J] . IEEE Trans on ASSP,1989,37(12):2091-2110.

[2] Atonini M, Barlaud M, Mathieu P. Image coding using wavelet transform[J] . IEEE Trans on Image Processing,1992,1(2):205-220.

[3] 張兆禮,趙春暉,梅曉丹. 現(xiàn)代圖像處理技術(shù)[M] . 北京:人民郵電出版社,2002:295-296.

[4] 王茂芝,徐文皙,佘春東. 一種高效的小波變換跨帶矢量量化編碼[J] . 計算機應(yīng)用,2004,24:379-381.

[5] 鄭勇,李德明,朱維樂. 采用方向樹結(jié)構(gòu)矢量組合的小波圖像分類矢量量化[J] . 電子信息學(xué)報，2004,27(12):1959-1963.

[6] 孫圣和,陸哲明. 矢量量化技術(shù)及應(yīng)用[M] . 北京:科學(xué)出版社,2002:104-105.

[7] 馬杜祥,劉貴忠等. 基于小波變換的圖像和視頻壓縮編碼[J] . 工程數(shù)學(xué)學(xué)報,2001,18(5):17-30.