LZ数据压缩算法分析及其在印章系统中的应用

论文摘要

随着网络与多媒体技术的发展,人们对数字图像的在质量、大小、应用方面的要求越来越高。然而,图像数据的数据量是非常庞大的,因此,如何利用有限的空间和带宽资源来存储和传输图像数据成为人们迫切需要解决的问题。图像压缩也因而成为了越来越多的科研工作者的研究热点。本文以图像压缩技术为基础,首先介绍了图像压缩的基本概念和压缩领域比较经典的压缩编码方式,包括变换编码、游程编码、Huffman编码和预测编码等。接下来,本文具体讨论了图像压缩领域的算法—LZ77无失真压缩算法,讨论了算法的基本原理、压缩和解压缩的步骤,并对算法中数据输出部分的编码方案进行了具体的描述。与其他算法相比,LZ77算法实时性好,易于实现、具有较高的压缩和解压缩速度,适合实际应用。但是通过对LZ77算法编码方案的分析,我们发现算法在搜索匹配字符串和对单个字符的输出方面还存在一定不足。因此,对算法做出了以下两点改进。1)原算法在搜索匹配字符串时采用的是顺序查找,改进算法将文本窗口的数据进行了重新的组织,以二叉排序树的结构保存字典文本窗口的短语,从而在一定程度上缩短了算法的执行时间。2)原算法在输出单个字符的时可能会导致三元组编码长度大于本身的字长。基于这种情况,改进算法对数据输出部分做出一些修改,即为每个输出的短语添加一位后缀,用来表示输出的是单字符还是多字符匹配的短语。这样处理后,算法就不必再为单个字符编码,从而在一定程度上改善了压缩效果。除此之外,本文还给出了利用该算法进行压缩的几个实例。实验结果表明,改进后的算法能对数据进行有效的压缩处理,在一定程度上提高了压缩比,特别是对于颜色稀疏的图片,算法可以达到更好的压缩效果。最后,本文将LZ77算法用在了实际的项目—四川国盾印章治安管理系统中,通过对图片的压缩处理,将处理后的字符串保存到数据库中,然后进行传输和通信,并在客户端将图片进行完美解压显示。LZ77算法有效解决了存储设备容量有限和图像数据量大之间的矛盾,提高了数据库的运行效率,收到了良好的效果。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 数据压缩简介
• 1.2 图像压缩的理论基础
• 1.2.1 图像压缩的相关理论
• 1.2.2 图像质量的评价标准
• 1.3 图像压缩的发展和意义
• 1.3.1 图像压缩的发展历程
• 1.3.2 图像压缩的意义
• 1.4 本文章节安排
• 第二章 压缩算法
• 2.1 图像压缩的分类
• 2.2 常见的有失真压缩算法
• 2.2.1 变换编码
• 2.2.2 矢量量化编码
• 2.2.3 模型基编码
• 2.3 常见无失真压缩算法
• 2.3.1 Huffman 编码
• 2.3.2 游程编码
• 2.3.3 预测编码
• 2.3.4 字典编码
• 2.4 本章小节
• 第三章 LZ77 无失真压缩算法及其改进
• 3.1 LZ77 算法
• 3.1.1 LZ77 算法提出的背景
• 3.1.2 LZ77 算法的基本原理
• 3.1.3 LZ77 算法的压缩和解压缩步骤
• 3.2 算法存在的缺陷
• 3.3 算法的改进
• 3.3.1 查找算法的改进
• 3.3.2 输出数据编码方案的改进
• 3.4 改进后的算法流程
• 3.5 算法实现中的一些问题
• 3.5.1 算法中所使用的数据结构
• 3.5.2 先行缓冲区和树初始化
• 3.5.3 增加字符串 InsertString（）
• 3.5.4 删除字符串DeleteString（）
• 3.6 算法中输出数据的编码方案
• 3.6.1 字典内偏移offset
• 3.6.2 字符串长度length
• 3.6.3 标志位sign
• 3.7 实验结果比较
• 3.8 算法的特点
• 3.9 本章小节
• 第四章 LZ77 算法在印章管理系统中的应用
• 4.1 四川国盾印章治安管理信息系统
• 4.1.1 系统简介
• 4.1.2 系统结构
• 4.1.3 系统功能
• 4.2 算法应用思想
• 4.3 压缩保存
• 4.3.1 对彩色电子印文的处理
• 4.3.2 对扫描灰度图的处理
• 4.3.3 基本全局门限算法介绍
• 4.4 解压显示
• 4.5 效果
• 4.6 工程中LZ77 的主要编码
• 4.7 本章小节
• 第五章 结论
• 致谢
• 参考文献
• 附录
• 攻读硕士期间的成果