基于小波变换和分类矢量量化的图像压缩算法.doc

基于小波变换和分类矢量量化的图像压缩算法
黄　晴，张书玲
（西北大学 数学系，陕西 西安 710069）
摘　要：提出一种用于图像压缩的分类矢量量化算法，该算法在对图像进行多级小波变换后，利用3个方向上各自小波系数之间的相关性，构造符合图像特征的跨频带矢量，依据矢量能量和零树矢量综合判定进行矢量分类，并采用了基于人眼视觉特性的加权均方误差准则和基于成对最近邻算法(PNN)的LBG算法进行矢量量化，提高了图像的编码效率和重构质量。仿真结果表明，该算法实现简单，在较低的编码率下，可达到较好的压缩效果。
关　键　词：小波变换，跨频带矢量构造，矢量分类，矢量量化
中图分类号：TN911.73 文献标识码：A 文章编号：1000-274X(2003)0041-06
图像压缩在图像的传输和存储中起着至关重要的作用。小波变换[1,2]由于具有良好的时-频局部化性能，有效地克服了傅立叶变换在处理非平稳的复杂图像信号时所存在的局限性，因而在图像压缩领域受到了广泛的重视，已出现了许多较为成熟的算法，如EZW编码[3]，SPIHT编码[4]等。Shapiro利用零树处理图像小波系数，有效地利用了带间相关性和带内相关性，获得了较高的编码效率。由Shannon信息论理论知道，对于无记忆信源，矢量量化总是优于标量量化。给定码率时，维数任意大的矢量量化可以任意接近率失真下界。由于小波逆变换具有一定的平滑作用，小波变换域内作矢量量化不会出现明显的方块效应，所以具有较好的图像压缩效果。近年来，也出现了一些将小波变换与矢量量化相结合的编码方案[5-7]，文献[8]研究表明，使用分类矢量量化可以获得高质量图像。
基于以上零树编码和矢量量化的思想，本文提出一种新的图像压缩算法。此算法先对图像进行四级小波变换，得到3个方向上的四级高频子带，再根据3个方向不同频带系数之间的同构特征来构造跨频带矢量，通过对矢量能量和3个方向零树矢量的综合判定将矢量分类，然后再采用基于人眼视觉特性的WMSE准则和基于成对最近邻算法(PNN)的LBG算法对重要类矢量进行加权矢量量化，以实现图像的数据压缩。
1　算法原理
1.1　图像小波分解的特点和跨频带矢量的构造
小波变换是一种非平稳信号的分析方法，其基本思想是用一族函数来表示或逼近一个函数,这族函数称为小波函数。实际小波变换中，为了方便，多采用二进小波变换。对空间中的任意函数，它的二进小波变换为
　　　　　　　　　　　　　　　　　　　　　　　　　(1)
其中，，而满足　。
将小波变换一维推广到二维就可用于图像处理。通过水平和垂直滤波，可分离二维小波变换将原始图像分解为水平﹑垂直﹑对角和低频4个子带，其中低频部分可继续进一步分解。图像经小波变换后所得到的系数有特殊性质。在不同尺度的高频子带图像之间存在同构特性，而且3个方向上不同尺度下的小波系数能量大小不同，各方向的侧重不同。在同一方向上，有更强的同构性和相似性，事实上，各方向不同尺度下对应频带的相关性是最强的。为提高矢量量化的编码效率，在构造矢量时，必须充分利用这些相关性。此外，图像的能量主要集中在低频子带，高频子带所占能量较少，且不同分辨率不同高频子带中的分布非常相似，接近Gamma分布或Laplace分布。各高频子带系数大部分分布在零值附近，概率密度分布曲线的中心点和最大值为零。这样，对带内及带间相关性的充分利用和对零值附近小波系数的有效处理，就成为提高图像压缩效率的关键。
高性能的矢量量化器必须依照图像小波系数的特性来构造矢量。使用不同子带的系数构成矢量来压缩小波系数，就可以利用不同尺度同方向小波系数的相关性。根据以上分析，本文采用三方向跨频带矢量构造方法[9]。小波变换将图像分解为4层共13个子带的塔形结构，各方向以树形关系从各子图中取大小为的系数块，按图1所示的方法构成85维矢量。这样构造出来的跨频带矢量能够充分利用小波系数的带间和带内相关性，但同时也带来计算量过大的问题。又在图像的多分辨分解中，分辨率越低的频带，小波系数所包含的图像信息越多，对图像重构更为重要，而分辨率越高的频带所包含的图像信息越少。因此，为降低矢量量化编码的复杂度，对每个85矢量的后64维矢量取均值，使矢量维数大幅度减小为22维。这样就构造出了3个方向小波系数的跨频带矢量。

图1　3个方向跨频带矢量的构造
Fig.1 Band-cross vector construction of wavelet parameters
1.2　小波零树和3个方向跨频带矢量的分类
由小波图像的多分辨率解析特点，大量的小波系数分布在零值附近，并且具有明显的方向性，构造出的跨频带矢量也就具有不同的能量和方向特征，通过对矢量进行分类后，用各自独立的码书分别进行量化，可以更有效的利用各子带间的相关性。
矢量的能量大小决定了其对于恢复图像质量的贡献程度，矢量能量越大，对恢复图像质量的贡献程度越高，所以能量可以作为矢量重要与否的一个判定准则。其次，本文按四叉树规则构造矢量与零树编码的思想是一致的。零树[3]是基于小波系数相关性的一种假设：如果在低分辨率高频子带上的小波系数相对于阈值是无意义的或是不重要的，那么位于同方向同空间位置高分辨率子带上的小波系数相对于在统计意义下也是无意义的，把满足这种假设的系数用树状结构表示出来就是零树。零树矢量对恢复图像质量的贡献很小。若一个零树矢量同时能量满足小于给定的能量阈值，就可以看作非重要类，不再进行量化编码，把其中的每一个分量置为0，并且用一个比特作标记，记为0；而其他矢量均看作重要类，标记为1，进行较大码书尺寸的矢量量化，以减小量化误差。采用能量阈值和零树矢量的双重判断，既充分利用了子带相关性，又有效的保护了图像的重要信息。
1.3　重要类矢量量化的加权均方误差准则
在图像的塔式小波分解算法中，大尺度下数据在恢复图像时经过滤波的次数要多，因而量化误差对恢复图像的质量将产生较大影响，且影响的空间范围比较小尺度下的数据要大，因此适合于采用基于人眼视觉特性的WMSE准则进行最佳矢量的匹配，以提高量化增益。
　　　　　　　　　　　　　　　　　　　　　　　（2）
其中：为矢量维数；为加权系数。
文献[8]利用人眼的视觉特性对灰度图像设计了一种加权量化方案，以减小量化噪声，本文采用文献[8]中给出的各级子带对应加权系数，如表1所示。
表1　各级子带加权系数
Tab.1 Weight coefficients of subbands
子带名
HL4
LH4
HH4
HL3
LH3
HH3
HL2
LH2
HH2
HL1
LH1
HH1
加权系数
0.738
0.738
0.596
0.584
0.584
0.411
0.355
0.355
0.230
0.189
0.189
0.119
1.4　初始码书生成的PNN[10]算法
在矢量量化中用LBG算法[11]训练码书时，初始码书的设计一般采用分裂算法。在分裂法中，对中间码书的每个码字都要一分为二，然后利用LBG算法形成码字数目是原码书的二倍的新码书。这样设计出的码书其码字均匀或近似均匀地分布在样本空间，而实际信源是非均匀的，容易使得有些码字利用率很低。为此本文采用成对最近邻算法(PNN)[10]来生成初始码书。
PNN算法的步骤为：
1）令码字数,将全部训练矢量作为码字，即,构成个胞腔，第个胞腔的质心为，所含矢量个数为。
2） 计算各对码字与间的失真
3）设，则合并胞腔和，更新码字为，更新为，若，则从码书中去掉码字；否则令，从码书中去掉码字。令。
4）若，则终止；否则转2），继续合并两个最近的胞腔。
2　算法实现
小波变换编码中，滤波器的选择是个有待研究的问题。为便于在Matlab环境下的处理，本文采用最为简单的Haar小波来作为滤波器，实际上，滤波器的选择对编码效果并没有明显的影响。另外，图像的小波变换级数应根据所期望的压缩比来确定，一般用3~4级，例如，若用4级小波分解，则是原图像大小的，一般对它作有限的无损压缩，再加上其他信息，估计压缩比不会高于。文中对输入图像使用对称延拓方式作4级小波分解。
最低分辨率级的低频子带对图像恢复质量影响很大，但数据量又小，所以不进行矢量量化，对其单独处理。利用子带系数之间的相关性，一般采用差分脉冲编码调制(DPCM)加算术编码对其进行压缩，大约能压缩两倍左右。
为了能够自适应地确定各阈值，首先对矢量能量和最低分辨率级各高频子带系数作统计分析，依据矢量平均能量确定能量阈值，依据最低分辨率级各方向高频子带系数的幅度均值，确定各方向零树矢量的判定阈值。这样每个方向的矢量均可分为重要类和不重要类两类，再对重要类进行大码书的加权矢量量化。
3　仿真结果及结论
采用4幅的标准图像对系统性能进行模拟实验仿真。实验中所用码书大小为，训练序列大小为，码字22维。3个方向上的重要类矢量分别使用算法进行训练生成码书。表2列出了测试图像的小波系数矢量及最低分辨率子带系数的统计结果，表中矢量平均能量定义为，其中为矢量个数，为矢量维数。仿真结果表明（见表3），本算法在未对量化结果进行熵编码时，对测试图像的编码效率已达到0.101 8 bpp（每个像素所使用的比特数）每个像素所使用的比特数，且恢复图像视觉效果良好。若再进行熵编码，可进一步提高压缩比。为进一步说明重构图像的主观质量，图3给出测试图像和相应的重建图像。本文基于零树编码和分类矢量量化的思想，通过构造3个方向的跨频带矢量，充分利用了各级子带系数的带间相关性和带内相关性，又通过能量阈值和零树矢量的综
表2 测试图像的统计结果
图 像
矢量平均能量
LH4幅值平均
HL4幅值平均
HH4幅值平均
Lena
0.339 4
0.002 9
-0.063 3
-0.010 2
Oldhouse
0.270 2
0.018 7
0.034 9
-0.014 7
Goldhill
0.211 7
0.049 4
-0.023 5
-0.009 4
Camera
0.405 4
0.039 4
-0.026 2
-0.009 4
Tab.2 Statistics of test images

表3　算法性能统计
Tab.3 Statistics of the algorithm performance
原始图像
量化结果 / bpp
压缩比 / 倍
峰值信噪比 / dB
Lena
0.099 1
80.709 4
27.651 0
Oldhouse
0.084 0
95.290 4
30.265 6
Goldhill
0.101 8
78.592 1
27916 8
Camera
0.091 5
87.395 9
25.572 6

Lena原图 Lena恢复图像 Oldhouse原图 Oldhouse恢复图像

Goldhill原图 Goldhill恢复图像 Camera原图 Camera恢复图像

图2　仿真结果
Fig.2 Simulation result
合判定对各个方向上的矢量进行分类，再采用基于人眼视觉特性的WMSE准则对重要类矢量进行加权矢量量化。仿真结果表明，该算法实现简单，在较低码率下，可达到较好的压缩效果。

参考文献：
[1] MALLAT S G. Multifrequency channel decomposition of images and wavelet models[J]. IEEE Trans on ASSP, 1989, 37(12): 2 091-2 110.
[2] ATONINI M, BARLAUD M, MATHIEU P. Image coding using wavelet transform[J]. IEEE Trans on Image
Processing, 1992, 1(2): 205-220.
[3] SHAPIRO J M. Embedded image coding using zerotrees of wavelet coefficient[J]. IEEE Trans on Signal Processing, 1993, 41(12): 3 445-3 462.
[4] SAID A, PEARLMAN W. A new fast and efficient image code based on set partitioning in hierarchical trees[J]. 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 898.
[7] 潘建寿, 孙宏伟. 基于9/7双正交小波的一种高效矢量量化算法[J]. 电子与信息学报, 2002, 7(24): 900-904.
[8] DESARTE P MACQ B, SLOCK D. Signal-adapted multiresolution transform for image coding[J]. IEEE Trans on Information Theory, 1992, 38(2): 897-904.
[9] PAMELA C, ROBERT M G, MARTIN V. Vector quantization of image subbards: a survey[M]. IEEE Trans on Image Processing, 1996,5(2):202-225.
[10] 孙圣和, 路哲明. 矢量量化技术及应用[M]. 北京: 科学出版社,2002.
[11] LINDE Y, BNZO A, GRAY R. An algorithm for vector quantizer design[J]. IEEE Trans on Comm, 1980, 28(1): 84-95.
（编辑：曹大刚）
Image compression based on wavelet transform and classified vector quantization
HUANG Qing, ZHANG Shu-ling
(Department of Mathematics, Northwest University, Xi’an 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 vector, and then the vector is classified through joint judgement using the vector energy and zerotree vector. Finally, the vector is quantized based on WMSE and PNN. Therefore, the high coding efficiency and reconstructed image quality are both obtained. Simulation shows that this method can be realized easily and compress the wavelet image efficiently under lower coding rate.
Key words: wavelet transform,band-cross vector construction,vector classification,vector quantization
作 者 简 介
黄　晴，女，陕西延安人，生于1978年12月。2001年7月毕业于西北大学数学系计算数学与应用软件专业，同年免试进入西北大学数学系，攻读计算数学硕士学位，主要从事小波分析及其应用﹑数字图像处理﹑图像数据压缩方面的研究。目前已在《西北大学学报》（自然科学版）、《纺织高校基础学报》等刊物上发表有“一种基于多级矢量量化的图像渐进传输方法”、“基于小波变换和矢量量化的指纹图像压缩方法”等论文。