《一种基于改进ＥＺＷ算法的图像压缩方法.doc》由会员分享，可在线阅读，更多相关《一种基于改进ＥＺＷ算法的图像压缩方法.doc（11页珍藏版）》请在三一文库上搜索。
1、一种基于改进算法的图像压缩方法 (1.中国科学院 遥感应用研究所 遥感信息国家重点实验室, 北京 100101； 2.北京交通大学 交通运输学院， 北京 100044） 中图法分类号： TP391文献标识码： A Improved EZW Algorithm for Image Compression LI Jin ping1, RUI Xiao ping2, YANG Chong jun1 (1.The State Key Laboratory of Remote Sensing Information Sciences, Institute of Remote Sensing Applic
2、ations,Chinese Academy of Sciences, Beijing 100101, China; 2.School of Traffic & Transportation, Beijing Jiaotong University, Beijing 100044, China) Abstract: This paper presents an improved EZW algorithm for massive image compression. This method divides the massive image into some sub blocks. Base
3、d on the wavelet transformation for these sub blocks, it first uses EZW coding for them and then uses Huffman coding for them. This method can ensure that makes the best use of the hiberarchy relationship of wavelet coefficients and also can improve the compress rate. The authors brings out an adapt
4、ive reading/writing method according to the size of image, which is composed of two parts strip reading/writing and block reading/writing, the cache mechanisms of these two parts are also introduced in this paper. The authors apply this method into browsing massive image on Web and get a good effect
5、. Key words: Wavelet; EZW ; Image Compression; Adaptive Reading/Writing 随着现代信息社会对通信业务要求的不断增长，图像通信与通信网容量的矛盾日益突出，特 别是具有庞大数据量的数字图像通信，更是难以在网络上实时传输与浏览。这样就使图像信息在网络上进行数据共享变得非常困难，成为了图像通信发展中的“瓶颈”问题。因此对于高比率图像压缩算法的需求尤为迫切，图像压缩问题成了越来越多的科研工作者的研究热点。这些年来关于小波变换图像压缩算法的研究和应用都十分活跃。国外一些公司将这种技术用于Internet环境中的图像数据传输，提供商业化的
6、服务，对于缓解网络带宽不足、加快图像信息传播速度起到了很好的推进作用。作为一种优秀的图像压缩算法，小波变换在这一领域具有非常好的应用前景，也应该能够发挥关键性的作用，同时也必将对这种技术在我国的推广和应用起到有力的推动作用1，2。 1 EZW算法简介 图像通过小波变换后产生大量不重要的数据，通常需要经过量化处理和编码处理，抛弃不重要的数据才能实现图像的压缩。零树编码是当前小波图像压缩算法中最常用的编码技术。基于零树编码的规则，Shapiro等人首先提出了嵌入式零树编码（Embedded image coding using Zerotree of Wavelets coefficients，E
7、ZW）算法3，该算法是第一个使用零树编码的小波图像压缩算法，它利用小波图像中各级子带间的相似性，对系数按重要性进行排序，然后对系数进行逐级量化，最终得到按系数重要性排序的比特流。EZW算法的这种内嵌编码方式使得图像在网络上累进传输成为可能，并且用户可以根据需要任意确定图像压缩的比率，因此，EZW算法一经提出就受到了广泛的关注。 EZW算法的基本流程是：图像经过小波变换后，首先对其系数进行量化处理，按照2的整数幂从高到低排列量化阈值（通过量化阈值，对小波变换后的所有系数进行调整，将重要的系数保留，将不重要的系数忽略，从而让图像得到任意比例的压缩），结合低尺度系数与高尺度系数分布关系，生成四种符号
8、，即正重要系数(POS)、负重要系数(NEG)、孤立零点(IZ)和零树根(ZTR)；逐级递减量化阈值，按扫描顺序搜索重要系数，根据搜索结果形成重要系数坐标序列，输出索引；小波系数幅值逐级细化，在每一级量化阈值上，根据重要系数坐标序列输出这些坐标在该阈值上的1比特值4。 这种EZW编码算法对图像的压缩比例非常大，图像还原的效果比较满意，但该算法也存在一些缺陷,如必须开辟与图像比例为 1 1 的内存块，然后对图像进行多次扫描，进而还原整个图像的小波系数代码，不方便进行分块等。本文在分析嵌入式零树编码的基础上，提出了一种EZW的改进算法，下面将详细描述本算法的实现过程。 2 改进的EZW算法 为了能
9、够保证大型图像在网络上的实时传输，通常需要将图像进行分块处理，用户操作的图像只是整个图像中的一小块。也就是说，在对图像进行操作时，只要对用户关心的区域进行小波压缩即可，而没有必要将整个图块全部读入内存并进行压缩运算。因此作者提出分块EZW算法对图像进行处理，该算法将图像分割为一定大小的块，对每一块分别进行小波变换和EZW编码，这样就突破了EZW不能进行的图像漫游（分级浏览）局限。 2.1 EZW和Huffman双重编码机制 通过实验，作者发现EZW的编码结果依然存在冗余数据，还可以进一步进行压缩。可见，EZW并非是最优编码，还可以进一步进行优化。针对EZW算法的特点，笔者在EZW编码后，继续使
10、用Huffman编码，进一步对图像数据进行压缩。 这种双重编码的方式一方面能够保证EZW算法利用小波系数之间的层次关系，另一方面可以更大地提高图像压缩比率。这里重点介绍在EZW编码基础上再进行Huffman编码的实现过程。 Huffman编码的基本思想是：先统计出有多少像素，每一个像素出现的概率。然后按照概率的大小，进行排序，大概率在前，小概率在后。接着将最小的两个概率变成一个单元二叉树，较大概率的放在左叶节点，较小的放在右叶节点，同时新生成一个节点，该节点的概率为两个叶节点的概率和，将该节点按大小插入到原代码列中并删除那两个节点，如此反复，最终生成Huffman树。按照生成的Huffman树
11、对代码进行编码，规则为左0右1。本文将像素出现的概率分为八类，则进行Huffman编码的步骤可以叙述如下： (1)将像素值按其概率分布，由大到小排列，像素分类如表1所示。 (2)最小的两个概率变成一个单元二叉树，较大概率的放在左叶节点，较小的放在右叶节点，同时新生成一个节点，该节点的概率为两个叶节点的概率和。 (3)将新节点插入到原代码列中，并删除最小的两个概率。 (4)如此反复，直到原代码列中只剩下一个节点，并且概率等于1，到此生成Huffman树，如 图1所示。 (5)按照Huffman树的结构对代码进行编码，如表2所示。规则为左0右1，如图2所示。 对文件的代码进行编码时，生成代码表，然
12、后进行编码，压缩后的Huffman树必须保存，以供后面使用。Huffman编码是无损压缩编码，对于离散性较小的信息压缩效果比较好，是所有无损压缩编码中编码最优的。在压缩阶段，由于需要对所有代码进行扫描，所以将会稍稍影响速度，但在解压过程中，不会出现此类问题。 2.2 图像的自适应读写 本文中的EZW算法是针对任意图像块的，因此必须设计一个适合任意大小图像的自适应读写模块，以供图像的压缩编码使用。对于一幅图像，首先要判断其大小，如果给定图像子块大小，则可以对整个图像作如下判断： (1)如果图像不是大型图像（大型图像的长宽定义可以自己设置），则采用“带读写”方法，按照子块的高度和宽度直接按照特定的
13、顺序读或写。读写顺序按照光栅扫描的顺序从上至下，从左至右进行扫描。一次从左到右读入一个条带，并将条带数据存放到内存中，再分别输出每一块的数据信息。(2)如果图像是大型图像，则将该图像分成若干个子块，根据用户需求（比如用户拉框选择确定的图像范围）对每一块数据进行精确的定位，读一块，输出一块。对于块，要求为正方形，且边长必须被2i整除，i 为小波变换的级数，一般设定块的大小为800800或1 6001 600。对于边界上的块，将其大小调整至符合要求，如在五级小波变换的情况下，如果边界的长为27，就将其 调整为32，如果边界的宽为34，就将其调整为64，本文将两者之差称为拓展宽度。调整时调大不调小，
14、在调整过程中，拓展的数据设置其颜色为白色（0xFF）。 在图像子块无缝压缩时，输出的矩阵保证能被2i整除，i 为小波变换的级数，其边界数据将用相邻的块对应位置的数据进行填充。每一次写数据时，将拓展的数据抛弃。 2.3 图像读写的存储分配和缓冲机制 由于颜色由RGB三种分量组成，为了提高速度，将三种分量同时读入内存，为了节省内存，将三种分量分别进行小波压缩处理。带读写时，为了能够以最佳的速度读取数据，所以将读写文件的缓冲内存均设为一维数组，尽可能地一次读满缓冲区。一次将条带数据读入到一维数组中，输出信息矩阵时，在该数组中寻找需要的数据；块读写时，分 N 次将块数据读入到二维数组中，然后再将数据输
15、出。由于无缝压缩读取数据需要相邻的行与列的边沿数据，所以有必要开辟内存，将边沿数据保存。在带读中，相邻的列之间数据已经读到内存中，所以无须再进行另外的保存；但相邻的行之间需要进行数据保存，为此将建立一个宽度为图像宽度，高为边沿重叠宽度（取边沿拓展宽度的两倍）的缓冲区。 建立缓冲机制的总体思想是，在进行图像数据读写时，已经读入的数据不能完全抛弃，等到需要时能够在内存中找到，而且占用内存必须尽可能地少。下面以边沿拓展宽度为7为例说明读写图像的缓冲机制。 针对带读方式，子块两侧边沿像素在带读的同时，数据已经在内存中将其找到，填充到要输出的信息矩阵中就可以了。而对于相邻之间的数据则需要建立条带缓冲区。
16、 建立条带缓冲区的方法是：首先，先读入7行数据，放在条带缓冲区的714行，其中17行为拓展宽度，用白色表示。以后每读入一个条带的数据就将条带的后14行数据复制到条带缓冲区中，如此循环，如图3所示。这样，在处理条带数据时就可以方便地从缓冲区中获取相邻边界的14行数据，保证在小波运算时边界不出现缝隙。 针对块读方式，与带读方式不同的是，在增加一个条带缓冲区的同时，需要增加一个列边沿缓冲区，宽度为边沿重叠的宽度（边沿拓展宽度的两倍）。为了简化缓冲机制，完全可以将列缓冲区和块缓冲区合并在一起。与带读缓冲机制相似，首先读入长为图像宽度，宽为重叠宽度（7）的数据，存放在条带缓冲区的后半部，然后再建立循环，
17、进行块读，其中每行的首块必须先读入7列数据存放在列缓冲区，也就是块缓冲区的714列，然后从15列开始将读入的数据放入，以后每块在读数据以前，先将后14列数据复制到前14列。存储机制如图4所示。 带读机制和块读机制本身并不复杂，但由于有重叠数据的要求，所以读入的数据有一些不能丢弃，以备后用，并且还要处理边界不规则的块。值得注意的是由于有重叠数据的要求，边界的块处理和生成可能还牵涉到与边界块相邻的块的处理。 在带读机制的条件下，根据图像的宽度（设为 W ），读写文件的所有缓冲区的大小为： W 块的边长，设块的边长为 1 600 ，如果图像的宽度为12 600（图像文件大小为378MB），需要60M
18、B的缓冲空间。对于小波运算来说，需要10MB以上的空间，所以本系统可能需要70MB左右的运行空间，设块的边长为800，则系统需要35MB左右的空间。 保守一点来说，带读的运行机制对海量数据有一定的限制。如果图像的宽度超过在设块的大小为1 600像素，图像宽度超过16 000时，对于内存配置在128MB的计算机来说，可能会出现问题，同时效率下降很大。 理论上来说，块读机制可以处理无上限的海量数据。设块的边长为1 600，如果图像的宽度为12 600（图像文件大小为378MB），缓冲区的大小不到10MB，加上小波运算需要的空间，系统只需要25MB左右的内存就可以了。 3 实例 笔者采用Daubch
19、ies紧支集小波滤波器对图像进行压缩测试，选用图像块为1 6001 600，边界拓展为16像素，占块的1%。分别用Winzip，传统的EZW算法和EZW+Huffman双重编码算法对图像压缩，发现采用本文所述的方法后，压缩比率能够在传统EZW算法压缩的基础上进一步提高20%40%左右。图5和图6是本文用到的两个图片，用这三种方法测试的结果如表3所示。 但是由于采用了两次编码机制，因此程序的效率有所下降，本文所述的分块压缩，将感兴趣的图像大小限制在一定的范围内，对于图像子块来说，采用双重编码后，程序运行效率没有受到很大影响。 4 结论 海量图像在网络上实时传输是近些年图像处理的热点问题。随着互联
20、网的普及和图像应用范围的不断扩大，对图像编码提出的要求也越高，不仅要求算法具有高的压缩比，还要求有许多新的功能，如渐进编解码、从有损压缩到无损压缩等。利用EZW算法进行图像数据的压缩，可以较好地实现数据累进传输和实时压缩的问题。本文在EZW算法的基础上将大型图像分块处理，对每个子块采用EZW编码+Huffman编码的双重编码机制进行压缩，进一步提高了压缩的比率，同时采用了具有缓冲机制的自适应的读写方式读写图像数据，能够满足用户在网络上浏览任意区域图像的要求。 实际上，对于大型图像来说，可以根据用户热点的区域来统计哪些子块经常被访问，对于这些经常被访问的子块，可以预先在用户第一次浏览网页时建立缓冲机制，这样就可以更快地让用户在大型图像中分级漫游，这也是笔者目前正在深入研究的工作。