基于小波变换的图像压缩算法研究

1、基于小波变换的图像压缩算法研究袁林 张国峰 戴树岭(北京航空航天大学先进仿真技术实验室 北京 100083摘 要 小波变换是一种对信号的时间 -尺度 (时间 -频率 进行分析的方法,它具有多分辨率分析的特点,而 且在时频两域都具有表征信号局部特征的能力。本文对基于小波变换的图像数据压缩编码方法进行研究, 首先利用小波变换对图像进行多分辨率分解, 然后对分解后的图像数据进行小波零数编码和自适应算术编 码,从而实现图像压缩的目的。关键词 虚拟现实 小波变换 图像压缩 零数编码 算术编码1 引言在分布式虚拟环境中,随着应用的日益广泛和系统结构的日渐复杂,将有大量的图像、语音等 多媒体的数据需要在网络

2、上传输。在带宽资源有限的情况下传输这些多媒体数据时,需要对这些数 据进行有效的压缩和解压,以达到快速传输的效果。因此,在虚拟现实系统中进行有关多媒体数据 压缩的研究是非常有应用价值的。近几年,小波变换作为一种新兴的信息处理方法,已经受到广泛重视。具有“数学显微镜”之 称的小波变换同时在时域和频域具有分辨率。对高频分量用逐渐精细的时域或空域步长,可以聚焦 到分析对象的任意细节,对于剧烈变换的边缘,比常规的傅立叶变换具有更好的适应性。由于小波 变换的优良特性与 Mallat 算法的简便易行,使得小波变换图像编码压缩成为图像压缩领域的一个主 要研究方向。2小波变换 1与多分辨率分析小波变换就是将信号

3、在一个函数族上作分解,该函数族是由一个独立的函数 (小波母函数 (t 经过平移和伸缩而得到的,如式 2-1所: (| (2/1ab t a t = 0, , a R b a (2-1 其中,分别为伸缩和平移尺度, (t 的傅立叶变换必须满足容许性条件 :=C R 2| (| (2-2 此式隐含了 0 (=dt t R ,表明小波具有正负交替的波动性。图像的多分辨率分析 (MultiResolution analysis采用不同分辨率下处理图像中不同信息的方法, 将图像在各种分辨率下的细节提取出来, 得到一个拥有不同分辨率的图像细节序列再进行分析处理。 与 DCT 变换不适合于带宽较宽 (拥有较

4、多边缘轮廓信息 的图像信号不同,小波变换是一种不受带宽 约束的图像处理方法,即小波变换多分辨率的变换特性提供了利用人眼视觉特性的良好机制,从而 使小波变换后图像数据能够保持原图像在各种分辨率下的精细结构。2.1快速小波变换算法 (Mallat算法 2Mallat 首先将多分辨率分析用于图像数据的压缩,他给出了信号分解与合成的快速算法,该算 法在小波分析中的地位相当于 FFT 算法在傅立叶分析中的地位。 Mallat 算法将数学领域的小波方法、 计算机视觉中的多分辨率方法和信号处理中的子带滤波方法完美的统一起来,它的出现使小波分析 方法在信号处理领域真正得以实用化。根据多分辨率分析理论,可得出快

5、速分解算法表达式:(=m mj k j mmj k j c k m g d c k m h c , 1, , 1, 22 (2-3其快速重构算法的表达式为 :+=kk j k k j m j d c c , , , 1 (2-4其中, k j c , 、 k j d , 分别是尺度 j 上的尺度系数和小波系数;而 m j c , , 1,为尺度 j-1上的尺度系数。2.2二维图像的小波变换的分解与重构图像的二维小波变换实质上就是对图像进行离散二维小波变换。其二维小波变换就相当于对二 维图像数据在水平方向和垂直方向各自独立地进行一次一维小波变换。这样,由前面介绍的一维小 波变换的快速算法,相应地

6、就可以推出二维小波变换的快速算法。 Mallat 的图像小波变换塔式算法 如下图 1和图 2所示 3。 其中, 表示每两列中取出一列, 表示每两行中取出一行, LL 表示低通子图像, LH 表示水 平边缘子图像, HL 表示垂直边缘子图像, HH 表示斜方向边缘子图像 图 1 Mallat图像小波变换分解算法原始图像 其中, 表示每两行中插入一行零, 表示每两列中插入一列零图 2 Mallat图像小波变换重建算法从滤波器的角度来看,上述过程可看成是对图像二维数据进行横向和纵向的滤波过程。由于 h 具有低通滤波特性, g 具有高通滤波特性,若将初始输入矩阵 (图像的二维数据 看作一个二维离散信

7、号的话,则一次分解后得到的四部分输出分别经过了不同的滤波器,代表了原始图像不同的信息。 其中, LL 是经过行和列两个方向的低通,对应了原始离散图像在下一尺度上的概貌, LH 经过了行 方向上的低通和列方向上的高通, 对应于水平方向的概貌和垂直方向上的细节信号。 以此类推得出, HL 对应于水平方向的细节信号和垂直方向上的概貌, 而 HH 则表示的是沿对角线方向的细节。 小波 变换后小波系数分布可由图 3表示3 图像的量化编码3.1 基于小波变换的编码技术图像经多次小波分解后形成一系列处于不同空间、不同频率的子图像,然后可对这些子图像进 行某种形式的编码,对系数的编码是小波变换用于图像压缩的核

8、心。在对小波系数进行处理时,应 该充分考虑并利用其统计特性,只有这样才能得到高效而合理的结果。从对图像变换后小波系数的 统计特性的分析中可以发现,小波系数在零值附近高度集中,很好地去除了相关性。小波系数的数 据结构十分有利于进行编码压缩,并能较好的保持原图像的特点。图像经过小波变换后生成的小波图像的数据总量与原始图像的数据量相等,即小波变换本身并 不具有压缩功能。之所以将它用于图象压缩,是因为生成的小波图像具有与原图像不同的特性,表 现在图像上的能量主要集中于低频部分,而水平、垂直和斜线部分的能则较少, LH j 、 HL j 和 HH j , 分别表征了原图像在水平、垂直和斜线方向的边缘信息

9、,具有明显的方向特性。低频部分称作“模 图 3 二维图像分解小波系数糊图像” ,水平、垂直和对角线部分称作“细节图像” 。对分解所得的各个子图,需要根据人类视觉 生理和心理特点分别作不同策略的量化处理。3.2 小波系数的零数编码Shapiro 4提出了零树数据结构来表征各级高频子带系数的自相似性,如下假设在很大概率下成 立:如果低频子带的小波系数小于某一阀值,则同方向上较高频子带的对应相同位置的小波系数也 会小于该阀值。图像的金字塔式分解从低频到高频子带形成一个层次树结构,最低频子带的结点有 3个子结点分别位于 3个方向次低频子带的相同位置,其余子带(除最高频子带的结点都有 4个 子结点位于同

10、方向上高一级子带的相应位置。这里定义 了 POS 、 NEG 、 IZ 、 ZTR 四个符号:一个 小波系数 x ,对于给定阀值 T ,若 T X |,则称 x 不重要,相反称为重要,根据系数符号正负定义 为 POS 和 NEC ;若根结点是不重要的且其所有后代结点也是不重要的,称为零树 ZTR ,若其后代 有重要系数则称为孤立零数,并建立两个列表:主表放不重要系数或以其为根结点的树,辅表存放 重要系数。系数扫描顺序,采用从低频到高频,同一级各子带按 HL 、 LH 、 HH 顺序,子带内按迂回 扫描顺序。利用上述层次树结构、符号和扫描顺序定义,对于给定阀值 T 通过两步实现编码:(1 主扫描

11、按预先定义的顺序扫描所有系数,确立系数的类别并输出相应符号,若是 ZTR 则不必扫描其 后代系数,否则继续扫描其子代,直到分裂出后代中的所有重要系数,扫描结束生成主表和辅表。(2辅扫描采用逐级逼近量化方法细化辅表中重要系数。4 图像的熵编码自适应算术编码根据混合编码的思想,一个典型的静态图像压缩编码必须包括三个基本部分:变换、量化和编 码。首先原始图像经过一些变换产生变换系数,如果不考虑计算机计算精度损失的话,这一过程可 认为是无损的;之后,变换系数被量化产生符号流(实际上,压缩变换编码过程中所有的信息损失 都发生在量化阶段 ;编码阶段处理符号流则尽可能无损地描述数据流。算术编码 5是一种变长

12、编码,它使用长度可变的代码来对以不同概率出现的样本进行编码,用 于消除代码冗余。 算术熵编码是 Rissomen 提出的一种二元码的编码方法。 在不知信源统计的情况下, 通过监视一段时间内码符号出现的频度,不管统计是平稳的还是非平稳的,编成的码率总能趋近于 信源熵值。每次迭代时编码算法只处理一个数据符号,并且只有算术运算。其基本原理是 :将被编码 的信息表示成实数 0和 1之间的一个间隔 (Interval。信息越长,编码表示的间隔就越小,表示这一 间隔所需的二进制位就越多。信息源中连续的符号根据某一模式生成概率的大小来减少间隔,出现 概率大的符号比出现概率小的符号减少的范围小,因此只增加较少

13、的比特位。自适应二值算术编码对一系列的二进制符号进行编码。每个符号代表二进制判定值的一种可能 结果。每个二进制判定值提供两种可能中的一种。递归概率区间划分是二进制算术编码的基础。对 于每个二进制判定值,把当前的概率空间划分为两个子区间,并且在必要时修改码流,以便指向赋 给出现符号的概率子区间的基。自适应算术编码建立了一个统一模型,用于选择每个二进制判定值编码用的条件概率估算值。 当一个给定二进制判定值的概率估算值取决于特定的特征或已编码的特征时,就以特征的性质或值 为条件。 统计模型所要求的每个条件概率估算值被保存在独立的存储位置。 算术编码器是自适应的, 这意味着每个上下文索引处的概率估算值

14、由算术编码系统创建和维护, 它可以根据条件而自行改变。5 结束语图像是人们传递信息的重要媒介,而数据量大又是数字图像的一个显著特点,因此图像压缩对 于信息快速增长的今天来说显得尤为重要。 小波变换是 80年代末发展起来的新兴信号处理工具, 图 像的小波分解非常适合于图像数据的压缩,而且已被 JPEG20006图像压缩标准采用。因此研究基于 小波变换的图像压缩算法具有重要意义。参考文献1 程正兴 小波分析算法与应用,西安交通大学出版社, 1998.52 Mallat, S.G, “A theory for multiresolution signal decomposition: the wavelet representation”. IEEE Trans Pattern Analysis and Machine Intelligence, 1989.11(7: 674-693.3 美 Kenneth R.Castleman著,朱志刚等译,数字图像处理,电子工业出版社, 2002.24 Shapiro, J.M., Embedded image coding using zerotrees of wavelet coefficients, IEEE Trans. Signal Processing. Vol41(12, P3445-3462, 1993.5 I