小波用于编码零树编码方案.doc

小波用于编码 零树编码方案1 小波变换应用于图像压缩编码用小波变换的方法进行图像数据的压缩编码是变换编码的一种，将时域信号变换到小波域后会得到一个多分辨率、能量集中的系数空间。能量越集中，系数被压缩的程度就越大。早在小波分析出现之前，人们就试图用多分辨率分析的思想对信号进行处理，以突破傅立叶变换的局限性，最著名的是Burt和Adelson的Laplace金字塔编码；后来，Mallat11提出了小波多分辨率分析算法；Daubechies用基于离散滤波器迭代的方法构造了紧支集的规范正交小波基，使小波分解可以用信号和离散滤波器的卷积运算来实现，从而使小波分解被广泛应用于图像分解。正交小波对应一个正交镜像滤波器，就是说低通滤波器h和高通滤波器g正交。双正交小波有两个小波，即小波和它的对偶小波，它们对应的滤波器分别为h,g和。其中，h与正交，g与正交，即满足：；进行图像的压缩编码时，用一个小波分解，用另一个重构。母波选择的合适与否直接影响着图像编码的结果，正交小波的变换明显的不如双正交小波。本文采用的均是附录二中介绍的双正交小波。小波变换是变换编码的一种，也要经过变换、量化和压缩三个步骤。将原始图像进行离散小波变换（DWT）后，如果立即进行相应的逆变换，会得到精确的原始图像，当然这要忽略在计算时带来的误差。对于一幅图像所得到的小波系数的能量要比在时域时集中的多，这样就很有利于将其量化为字符流。现代的量化方法有很多：如：标量量化、向量量化和零树编码量化等都是非常有效的。最后要对得到的字符流进行无损压缩，这要用到一些经典的方法，如：Huffman、ADPCM、RLE等。下面将讨论一种零树编码量化的方法。2 嵌入式零树编码方法(EZW)简介零树(Zerotree)可以认为是一种新的数据结构，它最初是由Lewis和Knowles提出的，他们以根系数的预测定义的能量公式来做为零树的判断条件，若树能量小于阈值则判决该树为零树；1993年，Shapiro17利用小波变换后系数在各尺度之间的相似性提出了嵌入式逐次逼近量化的零树编码方法（Embedded Zerotree Wavelet，记为EZW），以逐级递减的量化阈值为基准，找到重要系数进行标识后再精细编码，由重要系数表和重要标记辅助表组成；在这个基础上，1996年，Said和Pearlman18提出了基于内嵌零树的块编码（Set Partitioning In Hierarchical Trees，记为SPIHT）算法，利用S+P变换，生成了不重要块表(List of Insignificant Sets，记为LIS)、不重要像素表(List of Insignificant Pixels，记为LIP) 和重要像素表(List of Significant Pixels，记为LSP)，用这些表对EZW进行改进，他们的思想可以认为是一种自适应方法，即在一个尺度下从大块开始扫描，如果没有高于阈值的数就进行下一个大块的处理，如果有就将这个大块分割成减半的小块再进行处理；1998年，V.N.Ramaswamy19提出了对SPIHT的改进，并将其应用于无损编码；1997年，C.D.Creusere 20等提出了REZW(Robust EZW)算法。所有这些都是基于Shapiro的EZW的改进，为了说明EZW算法，先要搞清楚小波系数图中的“父子（根基衍生）”关系。一幅图像经过二维离散小波变换后，可以得到指定分解尺度下的小波系数，如图1所示。图1小波分解示意图 利用快速算法，将二维的小波变换分解为两个一维的运算，分别用高通与低通滤波器，进行一级分解与重构的示意图分别如图2和图3所示。图2 DWT分解快速算法图3 DWT重构快速算法如果再对LL1进行分解，可以得到LL2、LH2、HL2、HH2。变换系数在高尺度与低尺度之间有一定的相关性，这种相关性如图4所示。Shapiro正是利用了这种相关性将零树引入小波编码中，EZW思想可以表述如下：一个小波系数x，对于一个给定的阈值T，如果|x| T0+ T0/2， 则记为POS1，重构值为T0+T0/2 + T0/4；如果重要值 T0x T0+ T0/2， 则记为POS0 ，重构值为T0+ T0/2 - T0/4，；如果重要值-(T0+ T0/2)x-T0，则记为NEG0 ，重构值为-(T0+ T0/2)+ T0/4，；如果重要值 x-(T0+ T0/2)， 则记为NEG1 ，重构值为-(T0+ T0/2) - T0/4，；将POS1和NEG1记为“1”，POS0和NEG0记为“0”，记在辅助表中。用（x-精细重构值）代替原来的