一种改进LZW图像压缩技术研究与实现.docVIP

一种改进LZW图像压缩技术研究与实现 　　摘要：针对原始的LZW算法在进行数据压缩的时候给不同的代码字分配固定长度整数，并在查询字典时耗时随字符串长度增加，成几何增长的不足等情况，提出了一种改进的LZW压缩算法，改进的算法采用了给不同的代码字段分配变长长度整数的方法。测试结果显示，在色深较小的图片压缩中，压缩率总体小于50%。比原始的LZW算法有明显的改进。结果表明，NIC算法适用于低色深的非自然图或有大量色块的图片中。 　　关键词：图像压缩；定长编码；压缩率 　　Abstract: During the time of data compression for the original LZW algorithm assigned to a different code word fixed-length integer, and time-consuming with increasing length of the string in the query dictionary, as the lack of geometric growth, an improved the LZW compression algorithm, the improved algorithm uses a variable length integer assigned to a different code field. The test results show a smaller color depth image compression, the compression ratio is less than 50% overall. The results show that the NIC algorithm is suitable for low color depth of unnatural map or a large number of color images.Keywords: Image compression; fixed-length encoding; compression ratio 　　 　　中图分类号：TP301.6文献标识码： A文章编号 　　 　　近年来，图像压缩领域变得越来越为人们所重视，因为图像文件不仅需要占据大量的内容空间，同时随着互联网络技术的发展，在网络上，图像文件也占据了大量的传输带宽，所以在图像进行存储之前，或者在对图像进行网络传输之前，首先要对图像进行压缩。目前的图像压缩算法分为两类：有损压缩和无损压缩，其中LZW是一种流行的无损图像压缩算法。它是一种基于字典的压缩算法，通过对一个字典的应用对数据进行编码，在图像压缩领域，它通过定长编码技术，消除图像像素间冗余，性能良好。 　　1 LZW算法 　　LZW压缩算法思想主要是通过用简单的代码来替换复杂的字符串，在压缩的过程中，动态生成串表，通过串表来记录字符串与代码之间的对应关系[1]。压缩开始时，初始化串表使其包括所有的单字（代码从0到255），LZW压缩算法规定清串表代码为256，结束代码为257，由此串表中增加第一个表项时，对应的代码是258。为限制串表的大小，LZW压缩算法规定串表不能超过4096项，即当代码位数超过12位时，放弃这个串表，重新初始化串表，同时输出一个清位码，并按新的串表继续进行压缩[2][3]。 　　2 改进后的LZW算法 　　改进的LZW算法（New Image Compress：以下简称为NIC）首先对偏移量中的数据进行读取，得到原始图像像素的位数，然后对数据块进行RLE算法压缩，接着以文件读取方式，逐个字节读取，读取的字节赋值到后缀变量中，前缀变量记录为上一次读取的字节。读取完一个字节后，便对字典数组中前缀变量和后缀变量的值做判断，为空则赋值为当前编码号，段号自动增长；不为空则把值赋给前缀变量。当段号大于4095时，输出清字典代码（257），并清空字典所有数据。如此循环，直到数据处理到最后一个字节，输出前缀变量和后缀变量，最后输出结束符（256），把所有输出保存成NIC文件。 　　以标准码长为12bit的LZW压缩算法为例，该算法编码表可以容纳4096个码字。整个编码表分成5个部分，其中1～256，257～512，513～1024，1025～2048，2049～4096分别为第1部分，第2部分，第3部分，第4部分，第5部分，每一部分输出的代码字长度分别为8bit，9bit，10bit，11bit，12bit。在算法中设置257为变长标示，每出现一次代码字长度的变化便输出一个变长标示，以提示解码程序代码字长度的变化。在压缩的过程中，根据LZW的编码规则，每次读入一个字节，都要和之前