小波变换及应用(图像压缩)

小波变换及应用（图像压缩）小波分析因为同时具有好的空间分辨率和好的频率分辨率，特别适于分析非稳态信号。自然图像正具有这种非稳态特性，可以看作是能量空间集中（图像边沿和细节）和频率集中（图像的平缓变化部分）信号的线性组合[8]。因此，使用小波分析进行图像压缩可以取得很好的效果。基于小波的图像压缩思想来源小波分析因为同时具有好的空间分辨率和好的频率分辨率，特别适于分析非稳态信号。自然图像正具有这种非稳态特性，可以看作是能量空间集中（图像边沿和细节）和频率集中（图像的平缓变化部分）信号的线性组合。小波图像压缩就是利用小波变换同时具有好的空间分辨率和好的频率分辨率的特性，使变换系数的能量同时在频率上和空间上集中，达到去除像素冗余度的作用。1.图像的小波分解若2-D滤波器可分解为，则可分的2-DDWT，将分解近似图象为一个近似图象和3个细节图象，即：),(21nn)()(),(221121nnnn),(21nnai101022112121311010221121212110102211212111101022112121112121212)2,2()()(),()2,2()()(),()2,2()()(),()2,2()()(),(LkLkiiLkLkiiLkLkiiLkLkiiknknakgkgnndknknakhkgnndknknakgkhnndknknakhkhnna其中H(Z)和G(Z)为1-D小波滤波器，信号是在低分辨率上的近似，从籍低通滤波器和沿行及列2倍下取样计算此近似信号，信号和包含的细节。信号包含垂直高频（水平边沿）。计算此信号是由水平方向低通和垂直方向高通滤波，信号包含水平高频（垂直边沿），信号包含两个方向的高频（角）。),(211nnai),(21nnai),(21nnai),(),,(21212111nndnndii),(2131nndi),(21nnai),(2111nndi),(21nnai),(2121nndi),(2131nndi2级2-DDWT的上式计算，可由下框图实现：)(ZH2)(ZG2)(ZH2)(ZG2)(ZH2)(ZG2)(ZH2)(ZG2)(ZH2)(ZG2)(ZH2)(ZG2),(210nnaNNN2N2N2N4N4N行列行列),(211nna),(212nna),(2112nnd),(2122nnd),(2132nnd),(2111nnd),(2121nnd),(2131nnd3HL3LH3HH2LH2HH2HL1HL1HH1LH3LL图像的多分辨率表示图像经过小波分解后，绝大部分能量集中在逼近信号子带，该子带的图像可看作原始图像的一种低分辨率的抽样。而细节子带则反映了图像在各个尺度的细节，如边缘、纹理等。因为自然图像的边缘、纹理通常之存在于小部分区域，所以细节子带的大部分系数很小，平均能量很低。下图是Lena图像经过小波分解得到的多分辨率表示。Lena图像的多分辨率表示上述的分解过程通常采用滤波器组的形式实现，滤波器组由一个低通滤波器和一个高通滤波器构成。首先在行的方向上对图像进行分解，然后再在列方向上对图像进行分解，这样就得到一个逼近信号和三个不同方向上的细节信号。逼近信号又可作为输入进行下一级分解。由小波系数重构原始图像是上述过程的逆过程。2.EZW算法EZW算法是Shaprio等人在1993年发表的，它是小波图像压缩历史上具有里程碑意义的一个算法。到目前为止，许多最新的算法仍然还是基于EZW的核心思想。该算法的核心是对小波分解后的子带系数定义一种零树结构，这种零树结构是基于频率衰减的假设，即在同一方向上粗糙尺度子带的系数要比相应位置精细尺度子带的系数大，然后采用连续逼近量化和熵编码生成嵌入式码流。Embeddedzero-treewaveletalgorithmEmbedded意即编码器可以在任一希望速率上停止编码。同样，解码器可在码流的任一点截断码流，停止解码。优点：不需要图像预先知识，不用存储其码表，和不用训练。EZW算法利用DWT分解，在每一层i的最低带(band)分解为四个子带：1iLL，1iLH，1iHL，1iHHEZW算法根据小波分解后得到的图像的多分辨率表示的特点，定义了一种树形结构。对于最低分辨率子带，每一个系数都可与同一空间位置的水平、垂直、对角线方向的3个小波系数相关联；对于非最高分辨率的其它子带，每个系数都可与精细尺度的相同方向、同一空间位置的4个小波系数相关联。称粗糙尺度的系数是其关联的下一级精细尺度系数的父亲，称精细尺度的系数是与其关联的上一级粗糙尺度系数的孩子，这样就形成一系列的子带系数间的父子关系。小波系数的树形结构3HL3LH3HH2LH2HH2HL1HL1HH1LH3LLa13d33d23d4?422d21d32d12d31d11d展开的小波树aa1a2a3a11a12a13a14a21a32a31a24a23a22a34a33a111a132a131a124a123a122a121a114a113a112a144a143a142a141a134a133)(13d)(23d)(33d2d1d注意到每一级的树形节点都对应图像相同空间位置的区域。也即a与1a、2a、3a表示的是同样的空间位置，1a与11a、12a、13a、14a表示同样的空间位置，其它以此类推。这是由于小波变换的空间局域性特点决定的。这种由同一空间位置小波系数构成的树形结构是零树编码的基础。由于小波变换后能量向低分辨率子带集中，因此对于自然图像而言，靠近小波树根的小波系数其幅度值大于远离树根的小波系数幅值的概率很大。这就意味着，如果一个小波系数的幅度低于一个给定的门限，则它的后代的幅度也很有可能低于该门限。这就构成了零树编码的理论基础。能量分布零树编码的一些概念重要系数(significantcoefficient）：如果小波系数的幅度大于一给定门限T，就称该小波系数相对门限T是重要的。反之则称该系数是不重要的。零树的根(zerotreeroot)：如果一个小波系数和它所有的后代都是不重要的，则称该小波系数是零树的根孤立零（isolatedzero）：如果一个小波系数是不重要的，但是其后代中存在重要系数，则称该小波系数是孤立零。SPSNZRIZ量化小波嵌入式编码的重要图存储在0树中集合nS的带符号重要图与小波系数陈列有相同构造)3,2,1(kotherwiseqpdqpdqpbnkjnnkjnkj02],[212,21),(11若若最大尺度J2有重要图],[0qpbj由尺度系数],[qpaJ计算。),(qpbkjT5.1T5.1TT),(qpdkjEZW算法是一个多遍扫描算法，每次扫描都包含两个步骤：重要图编码和细化。如果记maxc是最大的小波系数的幅值，则最初的门限0T由下式给出。max2log02cT它保证了最大的小波系数的幅值落在区间)2,[00TT。每一遍扫描，门限减少一半，即121iiTT算法：最大门限找重要图量化区间)2,(TT量化及其细化对给定的门限iT，我们赋予系数四种节点类型之一：重要正系数（significantpositive）、重要负系数(significantnegative)，零树的根(zerotreeroot)、孤立零(isolatezero)。如果使用定长编码，每种节点类型需要2比特表示。需要注意的是，如果一个系数被分配了零树的根的节点类型，则在这一遍扫描中不需对其后代进行节点类型的编码。重要图编码可部分地看作使用一3级的中平量化器，见下图重要系数即那些落在最外层的量化等级的小波系数，T的选择保证了它们的幅度属于区间[T,2T)，因此重建值为1.5T或-1.5T。T-T1.5T-1.5T一旦一个小波系数被判定为重要的，该小波系数就被加入到重要小波系数列表中去，以进行后面的细化。在细化步骤需要决定小波系数是落在[T,2T)区间的上半部分或是下半部分。通过连续的细化，重要小波系数属于的区间就逐渐缩小了。进行细化的一种方便的方法是取小波系数与当前重建值的差，使用一2级中升量化器进行量化，相应的重建值为T/4或-T/4。最终的重建值是各次扫描重建值的和。4/T4/T差值重要图编码过程中，小波系数的扫描顺序如下所示。需要注意的是，只有以前扫描时被认为是不重要的小波系数才需要进行重要图编码。03b13b23b22b21b12b11b31bEZW编码的例子我们一个例子来说明EZW算法，图像经小波变换后得到多分辨率表示如下，266-771310644-42-24–3-20最大系数幅度为26，所以初始门限为162226loglog02max2cT求初始门限将小波系数的幅度和门限16进行比较。发现26大于16，所以传送significantpositive(sp)；下一个扫描的系数为6，其幅度低于16，并且它的后代的幅度也低于16，因此6是零树的根，所以整个集合编码为zerotreeroot（zr），下一个扫描的系数是–7以及最后扫描的系数7，都是零树的根。因此不需要编码后面的系数，它们的值已经由零树的根的节点类型表示了。所以传输的节点类型为spzrzrzr扫描系数并与门限比较?Tx传输主表-表符号的坐标主表如果每个节点类型用2比特表示(使用定长编码时)，到目前为止重要图编码使用了8比特的开销。在这一遍扫描中，唯一的重要小波系数是26。将该系数包括在准备细化处理的列表中，记列表为Ls，有Ls={26}系数的重建值为1.5T0=24，重建子带如下24000000000000000附表附表-原重要系数不传送下一步是进行细化，使我们获得重要重要系数幅值的修正项。现在列表Ls中只包含有一个元素。这个元素与重建值的差值为26-24=2。对差值用重建值为T0/4的2级量化器量化，得到修正项4。于是，重建值成为了24+4=28。传送修正项的开销是1比特。因此，仅需使用9比特，就可得到如下的重建子带28000000000000000原值重建值4/T4/T差值修正值量化细化接着我们将门限减小2倍并重复上面的过程。T1=T0/2=8再次扫描仍未标记为重要系数的小波系数，为了强调不扫描前面已经列为重要的小波系数，我们使用*来替代它们。*6-771310644-42-24-3-20改变门限T，重复前面步骤第一个扫描的系数是6。它低于门限值8，但是其后代有大于门限的系数，于是被编码为iz。接着扫描的系数是-7和7，它们的值都比门限值8低，而且其后代也低于门限，于是都被编码为zr。接着扫描13和10，编码为sp。最后两个系数是6和4，编码为iz。于是，这一遍扫描编码的节点类型序列为izzrzrspspiziz共需14比特，使总比特数达到23比特。：主表将新的重要系数加入附表，得到Ls={26,13,10}重要系数的重建值为1.5T1=12。于是这时得到的重建子带为280001212000000000015.1T15.1T1T1T重建值系数•细量化细化过程使用系数与其重建值的差来获得修正项。修正项可能的值为±T1/4=±2：26-28=-2修正项=-213-12=1修正项=210-12=-2修正项=-2每个修正项需要1个比特，总编码开销上升至26比特。并得到下面的重建子带260001410000000000024/1T4/21T差值修正值原值-量化值•校正如果再进行一次扫描，门限减小为2412TT，需要扫描的系数如下*6-77**644-42-24-3-20节点类型的编码序列为spsnspspspspsnizizspiziziz需要26比特。-主表重建的子带如下266-661410666-6006000附表为Ls={26,13,10,6,-7,7,6,4,4,-4,4}总的编码开销为52比特160T81T2T3.SPIHT算法SPIHT（SetPartition