基于霍夫曼编码实现的图像数据无损压缩基于霍夫曼编码实现的图像数据无损压缩Based on the Huffman coding Implementation of the image data lossless compression1.1.前言前言 在信息社会高速发展的今天，信息交流占据了我们很大一部分的生活，我们已经习惯于通过各种方式，查询信息，得到信息，了解信息，信息的载体有很多种，例如：文字、图像、语言以及视频等等；我们通过这些信息载体进行通信和交流，在早期的信息社会中，人们大多使用文字和声音进行交流，以及极为少数的图形图像进行交流，而对于形象又简洁的图像信息却尤为缺少，因此往往会与我们的要求有一定的出入。而现在，随着信息的飞速进步，通信技术以及计算机总体性能都大大的提高，如今图像成为计算机系统和通信传递信息的重要处理对象。尽管如今计算机总体性能有很大的提高，如容量和速度都有一定的优势。但大数据量的图像信息会给存储器和存储容量带来压力，同时图像信息会有大量冗余，这意味着它有很大的压缩潜力，因此我们很有必要在容量和数据都一定的状态下，去想办法改变。因而有了图像压缩编码，图像压缩编码技术在计算机图像处理中已经得到了越来越多的应用，相信随着图像压缩技术的发展，图像技术是具有相当大的发展潜力的。2.2.正文正文2.12.1 图像压缩的现状和发展趋势图像压缩的现状和发展趋势近年来图像压缩技术获得了飞速发展。按其信息保持的程度,图像压缩可分为有损压缩和无损压缩两大类。有损压缩允许一定程度的信息丢失,在满足实际应用的条件下能够取得非常高的压缩比,因而在多媒体交互式系统、视频传输业务和家庭娱乐等领域得到了广泛的应用下而言，无损压缩因不允许信息丢失,压缩效率难以提高而发展较慢。然而在遥感图像、医用图像处理等应用领域内,对于高效的无损压缩方法和高保真度压缩方法有着迫切的需要。2.22.2 关于数据图像无损压缩编码关于数据图像无损压缩编码 图像压缩编码的理论和实验研究至今已有 40 多年的历史,许多压缩编码技术从理论到实现都进行了深入的研究。以下仅从压缩原理、发展现状和国际标准三个方面来论述现阶段图像无损压缩的发展状况。经常使用的无损压缩方法有游程编码、霍夫曼编码和算术编码等。我们主要研究霍夫曼编码。2.212.21 关于哈夫曼编码关于哈夫曼编码 哈夫曼编码是一种常用的压缩编码算法,采用变长码编码,属于无损压缩算法的一种,在无损压缩的编码范畴中,哈夫曼(Huffman)编码方法是一种较有效的编码方法,是哈夫曼在 1952 年根据香农在 1948 年和范若在 1949 年阐述的一种编码思想提出的一种不定长(变长)编码的方法,也称霍夫曼编码。哈夫曼编码图像压缩应用中具有非常重要的意义,哈夫曼编码是一种实用的无损压缩技术,经过多年的不断改进,已经形成了系统的理论和方法。目前主要有两种类型的哈曼编码方式,即静态哈夫曼编码和动态哈夫曼编码。图像压缩编码技术可以追溯到1948 年提出的电视信号数字化,到今天已经有 60 多年的历史了。在此期间出现了很多种图像压缩编码方法,本课题主要研究基于哈夫曼编码对图像进行无损压缩,基于哈夫曼编码的图像无损压缩过程通常分为两步,即去除相关和编码。去除相关就是要去除图像数据的冗余部分,降低信源熵,这是对图像数据的压缩过程;编码就是对去除冗余后的图像数据重新用一种新的符号编码代替,这也是对图像数据的重编码进行存储的过程。 2.222.22 哈夫曼编码原理与具体实现哈夫曼编码原理与具体实现为了节省空间,在对数据进行编码时,可以对那些经常出现的数据指定较少的位数表示,而那些不常出现的数据指定较多的位数表示,从而降低冗余,这样从总的效果看就节省了存储空间。基于哈夫曼编码图像压缩的基本原理是频繁使用的数据用较短的代码代替,较少使用的数据用较长的代码代替,每个数据的代码各不相同,这是一种典型的无损编码方式。这些代码都是二进制码,且码字长度是不均匀的、平均码率可以接近信息源熵值的一种编码。编码过程是先对图像数据扫描一遍,计算出各种像素出现的概率,按概率的大小建立最优二叉树(二叉树的叶子节点刚好表示的图像中的某种像素)并给二叉树的每个分支赋特定权值(0 或 1),然后通过遍历二叉树读取从根节点到叶子节点的路径权值字符串,即给每种像素指定了不同长度的唯一编码,由此得到一张该图像所有像素的哈夫曼编码表。编码后的图像数据记录的是每个像素的码字,而码字与实际像素值的对应关系记录在码表中,码表是附在图像文件中的。 由于进行的是无损压缩,所以要扫描图像的所有像素点,压缩过程分为四步:扫描统计像素出现的概率并按大小排列;建立最优二叉树;哈夫曼编码;保存编码。经过哈夫曼编码后的图像中的不同像素分别用不同长度二进制编码表示,接下来的工作就是保存重编码后的像素,由于无损压缩中编码前后一幅图像的像素点数是相同的,如果仍然以像素为单位保存图像数据就无法实现压缩功能,能够实现压缩是因为编码前后表示像素的二进制编码的位数有所变化,所以,应该对重编码后的二进制位按位存储,由于 VB6.0 中没有移位运算,但是可以通过乘 2、除 2 操作实现左移、右移。当编码结束后,各像素的哈夫曼编码存放hufbm(1 to 256)中,在保存时,把所有像素的哈夫曼编码连成一串,然后每 8 位(字节)转换为整型数据,存储的是转换后的整型数据。解压过程： (1)指向 huffman 树的树根。(2)根据当前一位编码为 0 或 1 从而指向左或右儿子节点。(3)判断该节点的左,右儿子是否是空(即为 0)不是则向后扫描一个编码,执行上一步,如是则完成一个解码,该叶子节点的数组下标即为像素值,继续解下一个。在解码过程中需要把按位存储的编码读取出来,这个过程就是按位读取,由于压缩的文件长度大多小于 30K,那么编码部分必将小于30K,VB6.0 中字符型(string)的变量最长可达 65535 个字符,所以可将编码部分一次性读取,构造一个自定义函数 dtoo(sas byte),该函数的功能是将 byte 型的变量转变成 8 位二进制数。至此,关于哈夫曼编码的几个重要模块的实现算法已经介绍完,通过模块测试都能达到预期效果,把这几个模块集成即可形成一个基于哈夫曼编码的图像压缩系统，其中使用了一些用户自定义类型、变量3 3、结论、结论图像压缩技术,是当前很热门和实用的信息技术,图像压缩技术研究了几十年,取得了很大的成绩,但还有许多不足,值得我们进一步研究。Huffman 编码压缩作为一种简单高效的编码方法,在文本,图像,音频等压缩技术中都有着广泛的应用。从整个课题中可以看到,Huffman 编码算法只对图像压缩一次,要想提高压缩比,可以对图像进行两次压缩或多次压缩。另外,还可以与人眼视觉特性相结合实现有损压缩。总之,图像压缩是一个非常有发展前途的研究领域,这一领域的突破对于我们的信息生活和通信事业的发展有着深远的意义。4 4、参考文献、参考文献1、侯阳.迪克数据压缩技术及 C 语言实例.学苑出版社2、精英科普编著。视频压缩与音频编码技术.中国电力出版社3、David F Rogers 计算机图形学的算法基础.机械工业出版社4、田青 图像压缩技术J.警察技术,20025、王新成.高级图像处理技术M.第一版,北京,中国科学技术出版社,2001.6、孙仲康,等.数字图像处理及其应用M.北京,国防工业出版社,1985.7、董士海,等.图像格式编程指南M.北京,清华大学出版社,1994. 8、Ebrahimi T, Kunt M. Visual data compression for multimedia applications Proceedings of IEEE,1998,86(6):110911259、陈延标.数字图像处理.北京:人民邮电出版社,1990.16016310、Guo Junlu. Advances in digital image compression techniques. Computer Communications,1993,16(4):20221411、Hamming R W 著.编码和信息理论.朱雪龙译.北京:科学出版社,198412、高文.多媒体数据压缩技术.北京:北京电子工业出版社,199413、Wong S, Iaremba L. Radiological image compression A review. Proc IEEE,1995,83(2): 19421914、Carreto Castro M F. Comparison of lossless compression techniques In Proceeding of the 36th MidwestSymposium,1993.12681270 15、Denecker K. An experimental comparison of several lossless image coders for medical images. 1997.43545016、Cheng-Chieh Lee. Lossless adaptive differential coding of images. SPIE,1996,2418:2717、Mandyam G. Lossless image compression using the discrete cosine transform. Journal of Visual Communication and Image Representation, 1997,8(1):212618、Komatsu K. Reversible discrete cosine transform. In Proceedings of the 1998 IEEE International Conference,1998,3:1769177219、Jung HoYoul. A unified mathematical form of the WalshHadamard transform for lossless image data compression. Signal Processing, 1997,(63):354320、Said A. An image multiresolution representation for lossless and lossy compression. IEEE Trans Image Processing,1996,5(9):1303131021、Calderbank A R. Lossless image compression using integer to integer wavelet transform. Image Processing Proceedings,1997,1:59659922、Pennebaker W B, Miechell J L 著. JPEG 静止图像数据压缩标准.黎洪松 北京:学苑出版社,199623、徐孟侠.图像编码的进展.通信学报,1993,14(2):404724、Weinberfger M, Seroussi G, Sapiro G. The LOCO-I lossless image compression algorithm: principles and standardization into JPEG-LS. Hewlett-Packard Laboratories Technical Report,No HPL-98-193,199825、JPEG2000 requirements and profiles Version 4. 0. ISO/