1、 西北大学学报(自然科学网络版) 2004 年 1 月，第 2 卷，第 1 期Science Journal of Northwest University Online Jan. 2004，Vol.2，No. 1 _收稿日期：2003-09-28基金项目：陕西省自然科学基金资助项目（2001SL03 ）审 稿 人：程正兴，男，西安交通大学理学院教授基于小波变换和分类矢量量化的图像压缩算法黄 晴，张书玲（西北大学 数学系，陕西 西安 710069）摘 要：提出一种用于图像压缩的分类矢量量化算法， 该 算法在对图像进行多级小波变换后，利用 3 个方向上各自小波系数之间的相关性，构造符合 图像特征
2、的跨 频带矢量，依据矢量能量和零树矢量综合判定进行矢量分类，并采用了基于人眼 视觉特性的加 权均方误差准则和基于成对最近邻算法(PNN)的 LBG 算法进行矢量量化，提高了 图像的编码效率和重构质量。仿真结果表明，该算法实现简单，在较低的编码 率下，可达到 较好的压缩效果。关 键 词：小波变换，跨频带 矢量构造，矢量分 类，矢量量化中图分类号：TN911.73 文献标识码：A 文章编号： 1000-274X(2003)0041-06图像压缩在图像的传输和存储中起着至关重要的作用。小波变换 1,2由于具有良好的时-频局部化性能，有效地克服了傅立叶变换在处理非平稳的复杂图像信号时所存在的局限性，因
3、而在图像压缩领域受到了广泛的重视，已出现了许多较为成熟的算法，如 EZW 编码 3，SPIHT 编码 4等。Shapiro 利用零树处理图像小波系数，有效地利用了带间相关性和带内相关性，获得了较高的编码效率。由 Shannon 信息论理论知道，对于无记忆信源，矢量量化总是优于标量量化。给定码率时，维数任意大的矢量量化可以任意接近率失真下界。由于小波逆变换具有一定的平滑作用，小波变换域内作矢量量化不会出现明显的方块效应，所以具有较好的图像压缩效果。近年来，也出现了一些将小波变换与矢量量化相结合的编码方案 5-7，文献8研究表明，使用分类矢量量化可以获得高质量图像。基于以上零树编码和矢量量化的思想
4、，本文提出一种新的图像压缩算法。此算法先对图像进行四级小波变换，得到 3 个方向上的四级高频子带，再根据 3 个方向不同频带系数之间的同构特征来构造跨频带矢量，通过对矢量能量和 3 个方向零树矢量的综合判定将矢量分类，然后再采用基于人眼视觉特性的WMSE 准则和基于成对最近邻算法(PNN)的 LBG 算法对重要类矢量进行加权矢量量化，以实现图像的数据压缩。1 算法原理1.1 图像小波分解的特点和跨频带矢量的构造小波变换是一种非平稳信号的分析方法，其基本思想是用一族函数 来表示或逼近一个函数)(,tba,这族函数称为小波函数。实际小波变换中，为了方便，多采用二进小波变换。对 空间中的任)t(f
5、)(2RL意函数 ，它的二进小波变换为2(1)+, d)(=ttfCnmnm其中， ，而 满足 。2,)(nt(0=d)(+t将小波变换一维推广到二维就可用于图像处理。通过水平和垂直滤波，可分离二维小波变换将原始图像分解为水平垂直对角和低频 4 个子带，其中低频部分可继续进一步分解。图像经小波变换后所得到的系数有特殊性质。在不同尺度的高频子带图像之间存在同构特性，而且 3 个方向上不同尺度下的小波系数能量大小不同，各方向的侧重不同。在同一方向上，有更强的同构性和相似性，事实上，各方向不同尺度下对应频带的相关性是最强的。为提高矢量量化的编码效率，在构造矢量时，必须充分利用这些相关性。此外，图像的
6、能量主要集中在低频子带，高频子带所占能量较少，且不同分辨率不同高频子带中的分布非常相似，接近 Gamma 分布或 Laplace 分布。各高频子带系数大部分分布在零值附近，概率密度分布曲线的中心点和最大值为零。这样，对带内及带间相关性的充分利用和对零值附近小波系数的有效处理，就成为提高图像压缩效率的关键。高性能的矢量量化器必须依照图像小波系数的特性来构造矢量。使用不同子带的系数构成矢量来压缩小波系数，就可以利用不同尺度同方向小波系数的相关性。根据以上分析，本文采用三方向跨频带矢量构造方法 9。小波变换将图像分解为 4 层共 13 个子带的塔形结构，各方向以树形关系从各子图中取大小为 的系数块，
7、按图 1 所示的方法构成 85 维矢量。这样构造出来的跨频带矢量能够充)4,321(4m分利用小波系数的带间和带内相关性，但同时也带来计算量过大的问题。又在图像的多分辨分解中，分辨率越低的频带，小波系数所包含的图像信息越多，对图像重构更为重要，而分辨率越高的频带所包含的图像信息越少。因此，为降低矢量量化编码的复杂度，对每个 85 矢量的后 64 维矢量取均值，使矢量维数大幅度减小为 22 维。这样就构造出了 3 个方向小波系数的跨频带矢量。1x52216x852xx图 1 3 个方向跨频带矢量的构造Fig.1 Band-cross vector construction of wavelet
8、parameters1.2 小波零树和 3 个方向跨频带矢量的分类由小波图像的多分辨率解析特点，大量的小波系数分布在零值附近，并且具有明显的方向性，构造出的跨频带矢量也就具有不同的能量和方向特征，通过对矢量进行分类后，用各自独立的码书分别进行量化，可以更有效的利用各子带间的相关性。矢量的能量大小决定了其对于恢复图像质量的贡献程度，矢量能量越大，对恢复图像质量的贡献程度越高，所以能量可以作为矢量重要与否的一个判定准则。其次，本文按四叉树规则构造矢量，与零树3编码的思想是一致的。零树 3是基于小波系数相关性的一种假设：如果在低分辨率高频子带上的小波系数相对于阈值 是无意义的或是不重要的，那么位于同
9、方向同空间位置高分辨率子带上的小波系数相对于T在统计意义下也是无意义的，把满足这种假设的系数用树状结构表示出来就是零树。零树矢量对恢复图像质量的贡献很小。若一个零树矢量同时能量满足小于给定的能量阈值，就可以看作非重要类，不再进行量化编码，把其中的每一个分量置为 0，并且用一个比特作标记，记为 0；而其他矢量均看作重要类，标记为 1，进行较大码书尺寸的矢量量化，以减小量化误差。采用能量阈值和零树矢量的双重判断，既充分利用了子带相关性，又有效的保护了图像的重要信息。1.3 重要类矢量量化的加权均方误差准则在图像的塔式小波分解算法中，大尺度下数据在恢复图像时经过滤波的次数要多，因而量化误差对恢复图像
10、的质量将产生较大影响，且影响的空间范围比较小尺度下的数据要大，因此适合于采用基于人眼视觉特性的 WMSE 准则进行最佳矢量的匹配，以提高量化增益。（2）1=2)(),(iiKiyxyxd其中： 为矢量维数； 为加权系数。Ki文献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.59
11、6 0.584 0.584 0.411 0.355 0.355 0.230 0.189 0.189 0.1191.4 初始码书生成的 PNN10算法在矢量量化中用 LBG 算法 11训练码书时，初始码书的设计一般采用分裂算法。在分裂法中，对中间码书的每个码字都要一分为二，然后利用 LBG 算法形成码字数目是原码书的二倍的新码书。这样设计出的码书其码字均匀或近似均匀地分布在样本空间，而实际信源是非均匀的，容易使得有些码字利用率很低。为此本文采用成对最近邻算法(PNN) 10来生成初始码书。PNN 算法的步骤为：1）令码字数 ,将全部训练矢量作为码字，即 ,构成 个胞腔，第 个胞腔Mn=Mixyi
12、i 1ni的质心为 ，所含矢量个数为 。iRiy1iR2） 计算各对码字 与 间的失真 lmy nmldml 1),(3）设 ，则合并胞腔 和 ，更新码字 为jidlnlji ),(i),(1 iRj iy，更新 为 ，若 ，则从码书中去掉码字 ；否则令jijii Ryy+=iRjiiR+=nj=j4，从码书中去掉码字 。令 。njnjR,y=ny1=4）若 ，则终止；否则转 2） ，继续合并两个最近的胞腔。N2 算法实现小波变换编码中，滤波器的选择是个有待研究的问题。为便于在 Matlab 环境下的处理，本文采用最为简单的 Haar 小波来作为滤波器，实际上，滤波器的选择对编码效果并没有明显
13、的影响。另外，图像的小波变换级数应根据所期望的压缩比来确定，一般用 34 级，例如，若用 4 级小波分解，则 是原图4L像大小的 ，一般对它作有限的无损压缩，再加上其他信息，估计压缩比不会高于 。文中对输入图41像使用对称延拓方式作 4 级小波分解。最低分辨率级的 低频子带对图像恢复质量影响很大，但数据量又小，所以不进行矢量量化，对L其单独处理。利用 子带系数之间的相关性，一般采用差分脉冲编码调制(DPCM)加算术编码对其进行4压缩，大约能压缩两倍左右。为了能够自适应地确定各阈值，首先对矢量能量和最低分辨率级各高频子带系数作统计分析，依据矢量平均能量确定能量阈值，依据最低分辨率级各方向高频子带
14、系数的幅度均值，确定各方向零树矢量的判定阈值。这样每个方向的矢量均可分为重要类和不重要类两类，再对重要类进行大码书的加权矢量量化。3 仿真结果及结论采用 4 幅 的标准图像对系统性能进行模拟实验仿真。实验中所用码书大小为 ，bit8256 3128训练序列大小为 ，码字 22 维。3 个方向上的重要类矢量分别使用 算法进行训练生成码书。LBG表 2 列出了测试图像的小波系数矢量及最低分辨率子带系数的统计结果，表中矢量平均能量定义为，其中 为矢量个数， 为矢量维数。仿真结果表明（见表 3） ，本算法在未对量化结12NiKk,ivE=K果进行熵编码时，对测试图像的编码效率已达到 0.101 8 b
15、pp（每个像素所使用的比特数）每个像素所使用的比特数，且恢复图像视觉效果良好。若再进行熵编码，可进一步提高压缩比。为进一步说明重构图像的主观质量，图 3 给出测试图像和相应的重建图像。本文基于零树编码和分类矢量量化的思想，通过构造3 个方向的跨频带矢量，充分利用了各级子带系数的带间相关性和带内相关性，又通过能量阈值和零树矢量的综表 2 测试图像的统计结果Tab.2 Statistics of test images图 像 矢量平均能量 LH4 幅值平均 HL4 幅值平均 HH4 幅值平均Lena 0.339 4 0.002 9 -0.063 3 -0.010 2Oldhouse 0.270 2
16、 0.018 7 0.034 9 -0.014 7Goldhill 0.211 7 0.049 4 -0.023 5 -0.009 4Camera 0.405 4 0.039 4 -0.026 2 -0.009 45表 3 算法性能统计Tab.3 Statistics of the algorithm performanceLena 原图 Lena 恢复图像 Oldhouse 原图 Oldhouse 恢复图像Goldhill 原图 Goldhill 恢复图像 Camera 原图 Camera 恢复图像图 2 仿真结果Fig.2 Simulation result合判定对各个方向上的矢量进行分类
17、，再采用基于人眼视觉特性的 WMSE 准则对重要类矢量进行加权矢量量化。仿真结果表明，该算法实现简单，在较低码率下，可达到较好的压缩效果。参考文献：1 MALLAT S G. Multifrequency channel decomposition of images and wavelet modelsJ. IEEE Trans on ASSP, 1989, 37(12): 2 091-2 110.2 ATONINI M, BARLAUD M, MATHIEU P. Image coding using wavelet transformJ. IEEE Trans on ImageProce
18、ssing, 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 SAID A, PEARLMAN W. A new fast and efficient image code based on set partitioning in hierarchical treesJ. IEEE Trans on Circuits and S
19、ystem Video Tech, 1996, 6(3): 243-249.原始图像 量化结果 / bpp 压缩比 / 倍 峰值信噪比 / dBLena 0.099 1 80.709 4 27.651 0Oldhouse 0.084 0 95.290 4 30.265 6Goldhill 0.101 8 78.592 1 27.916 8Camera 0.091 5 87.395 9 25.572 665 王 磊, 戚飞虎. 基于双正交小波的快速矢量量化算法 J. 上海交通大学学报, 1998, 6(32), 4-8.6 郑 勇,胡小川 ,朱维乐.采用空间矢量组合的小波图像分类矢量量化J. 电
20、子与信息学报, 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 codingJ. IEEE Trans on Information Theory, 1992, 38(2): 897-904.9 PAMELA C, ROBERT M G, MARTIN V. Vector quantizatio
21、n of image subbards: a surveyM. 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 designJ. IEEE Trans on Comm, 1980, 28(1): 84-95.（编辑：曹大刚） Image compression based on wavelet transform and classified
22、 vector quantizationHUANG Qing, ZHANG 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 th
23、e 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
24、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 月毕业于西北大学数学系计算数学与应用软件专业，同年免 试进入西北大学数学系，攻 读计 算数学硕士学位，主要从事小波分析及其应用数字图像处理图像数据压缩方面的研究。目前已在西北大学学报（自然科学版）、 纺织高校基础学报 等刊物上发表有“ 一种基于多级矢量量化的图像渐进传输方法”、 “基于小波变换和矢量量化的指纹图像压缩方法”等论文。
