鄭秋梅，閔利田

0 引言

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

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

1 算法原理

1.1 小波變換

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

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

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

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

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

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

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

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

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

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

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

1.2 矢量的構(gòu)成

圖1 圖像3級(jí)小波分解示意圖

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

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

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

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

1.3 分類(lèi)矢量量化

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

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

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

與文獻(xiàn)[4] 的方法對(duì)比，利用分類(lèi)矢量量化以后，可以對(duì)不重要的矢量分配較小的碼書(shū)，可以進(jìn)一步的提高壓縮比，同時(shí)碼書(shū)變小，還可以提高算法的時(shí)間效率。

1.4 非線性插值方法

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

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

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

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

從而碼書(shū)C*的第i個(gè)碼字ci可由下式計(jì)算：

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

1.5 最低頻子帶的處理

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

1.6 算法流程

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

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

(2) 對(duì)提取得矢量按照能量進(jìn)行分類(lèi)，對(duì)重要矢量和非重要矢量分別編碼。

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

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

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

本文利用256個(gè)灰度等級(jí)(即8位量化)的512×512標(biāo)準(zhǔn)Lena圖像進(jìn)行實(shí)驗(yàn)，選取haar小波對(duì)圖像進(jìn)行3級(jí)小波分解，這主要是因?yàn)閔aar小波能同時(shí)滿(mǎn)足正交和對(duì)稱(chēng)性[7]。

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

表2 不同策略性能對(duì)比

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

圖3

4 結(jié)束語(yǔ)

本文提出了一種新的矢量組成方式和分類(lèi)矢量量化結(jié)合的方法，借助零數(shù)思想組成一個(gè)84維矢量，然后對(duì)矢量進(jìn)行相應(yīng)的分類(lèi)，分為水平，垂直和對(duì)角3個(gè)方向。然后根據(jù)矢量的能量進(jìn)行重要度分類(lèi)，對(duì)重要類(lèi)矢量分配大的碼書(shū)，對(duì)非重要類(lèi)矢量分配較小的碼書(shū)，同時(shí)結(jié)合非線性插值方法進(jìn)行矢量量化。試驗(yàn)結(jié)果表明，本算法能夠在保證較高峰值信噪比的情況下，獲得較低的編碼率，取得了令人滿(mǎn)意的結(jié)果。但是由于提取得矢量維數(shù)較大，雖然使用了非線性插值方法進(jìn)行了相應(yīng)處理，相對(duì)于20維左右的矢量提取算法，本算法運(yùn)行時(shí)間還是比較慢。而且使用非線性插值方法也增加了額外的開(kāi)銷(xiāo)。因此本算法比較適用于對(duì)圖像質(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] . 計(jì)算機(jī)應(yīng)用,2004,24:379-381.

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

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

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