作者:王继林
摘 要 本文介绍了如何把动态Huffman编码用于图像编码和压缩,从而进行加密传输的方法。并编写了具体程序实现读取图片、生成压缩文件、解压缩和重建图像等功能。
关键词 动态Huffman编码,图像压缩 ,解压缩,加密传输
一、 概述
当今,信息数字化在提供诸多优点的同时也提出了新的挑战。其中最主要的问题是信号数字化后数据量太大,直接传输对信道利用很不经济;存储则需要巨大的存储容量,同时也造成处理方面的困难;另外,标准数字化处理以后产生的信息编码规则统一,非常容易被截获、破解。
动态Huffman编码采取了一边扫描数据一边编码(也就是边建树)的方式,扫描完成后编码也完成。在扫描的过程中就可以同时传输数据。这就解决了实时传输的问题。同时,接收端一边接收数据一边建树,与发送方建树方式完全一致,这期间解码也在进行,接收完成解码也就完成。解码时不需要Huffman树,节省了存储空间,减少了信道占用和传输时间。所示掌握Huffman编码这种最重要同时也是最基本的编码方式,对今后在该领域的学习研究都有着深远的意义。
本文通过一个“图像动态Huffman编解码程序”的具体实例讨论如何利用VC++实现图像读取,动态Huffman编码,生成压缩文件,解码,重建图像的功能。具体开发环境:Windows XP, Microsoft Visual C++ 6.0。
二、 程序实现与分析
1.打开图像,将灰度值存入图像数组,并显示。
2.对图像进行动态Huffman编码
一边读取图像数组中的各个灰度值,一边编码,并同时把编码写入压缩文件。文件最开始的4个字节写入图片的长与宽,供解码显示图像时使用。字符串compressor中存放压缩后生成的文件名,要事先定义。例如:#define compressor "D:\\test.dat"。假如开始的几个灰度值为:255,235,60,60,建树并写编码的过程如图所示。具体如下:
(1)读入255,写入编码11111111(255),建树(如图1所示)。(2)读入235,以前未出现,向下扩展新节点(如图2所示)。写入编码011101011(0,235)。(3)读入60,以前未出现,向下扩展新节点(如图3所示)。写入编码0000111100(0,0,60)。(4)调整树(如图4所示)。(5)读入60,以前出现过,写入编码101,调整树(如图5所示)。圆代表普通节点,代码中lGray为-2。方框代表叶子,lGray为灰度值。NYT是以前未出现的灰度值向下扩展的位置,lGray为-1。因为各个节点的初始左右孩子下标为0,如果有下标为0的节点,调整树时会造成混乱,所以图中根节点的下标为514,以避免下标为0的节点的产生。
调整Huffman树时,有一点至关重要:节点权值加一时,即使比当前节点下标大的节点双亲有相等的权值,二者也不能交换位置,实现的核心代码如下:
|