搜索
基于霍夫曼编码实现的图像数据无损压缩程序设计1.前言现代社会是信息社会，我们无时无刻都在跟信息打交道，如上网查阅图文资料，浏览最新的新闻，QQ聊天或者传送文件等。人类对信息的要求越来越丰富，希望无论何时何地都能够方便、快捷、灵活地通过文字、语音、图像以及视频等多媒体进行通信。在早期的通信领域中，能够处理和传输的主要是文字和声音，因此，早期的计算机和通信设备的处理能力跟人类的需求有相当大的差距。随着通信信道及计算机容量和速度的提高，如今图像信息已成为通信和计算机系统的一种处理对象，成为通信领域市场的热点之一。可是，大数据量的图像信息会给存储器的存储容量、通信干线信道的带宽以及计算机的处理速度增加极大的压力。单纯依靠增加存储器容量、提高通信网络带宽和计算机处理速度来解决问题，在技术和经济上都不太现实。显然，在信道带宽、通信链路容量一定的前提下，采用编码压缩技术，减少传输数据量，是提高通信速度的重要手段。2.正文2.1图像压缩编码的现状和发展趋势1948年提出电视数字化后，就开始对图像压缩编码技术的研究工作，至今已有50多年的历史。图像压缩的基本理论起源于20世纪40年代末香农的信息理论。香农的编码定理告诉我们，在不产生任何失真的前提下，通过合理的编码，对于每一个信源符号分配不等长的码字，平均码长可以任意接近于信源的熵。在五十年代和六十年代，图像压缩技术由于受到电路技术等的制约，仅仅停留在预测编码、亚采样以及内插复原等技术的研究，还很不成熟。1969年在美国召开的第一届“图像编码会议”标志着图像编码作为一门独立的学科诞生了。到了70年代和80年代，图像压缩技术的主要成果体现在变换编码技术上，矢量量化编码技术也有较大发展，有关于图像编码技术的科技成果和科技论文与日俱增，图像编码技术开始走向繁荣。自80年代后期以后，由于小波变换理论，分形理论，人工神经网络理论，视觉仿真理论的建立，人们开始突破传统的信源编码理论，例如不再假设图像是平稳的随机场。图像压缩编码向着更高的压缩比和更好的压缩质量的道路前进，进入了一个崭新的、欣欣向荣的大发展时期。如今图像压缩编码技术广泛地被应用在各个领域。如：电视计算机、多媒体出版物、遥感图像数据库等。它已经为开创新的应用领域提供了良好的技术基础。到目前为止，图像压缩编码技术已经发展到第二代编码技术。1、第一代编码技术包括建立在shannon的码率失真理论基础上的预测编码、变换编码、统计编码及Oliver提出的PCM编码理论。虽然这些编码技术在中等压缩率的情况下，能提供非常好的图像质量，但在码率非常低得情况下，无法提供令人满意的质量。究其原因是由于这些技术没有利用图像的结构特点，同时也没有考虑人类视觉系统的特性，因此它们也就只能以像素或块作为编码的对象。2、第二代编码包括基于分形的编码、基于模型的编码、基于区域分割的编码，以及基于神经网络的编码等。这类编码技术不再局限于信息论的框架，充分利用了人类视觉以及图像信源的各种特征，实现从“波形”编码到“模型”编码的转变，获得了更高的压缩比。2.2关于数据图像无损压缩编码图像编码发展至今已经非常成熟了，但新颖的编码方法仍然层出不穷。不管具体的编码形式如何，它们都是力图消除图像中的一种或者多种冗余。根据由压缩数据恢复的图像与原始图像的差别，图像数据压缩可以简单分为两类：“有损压缩”和“无损压缩”。其中无损压缩在信息论中就称为“熵编码”。无损压缩仅仅是删除图像数据中的冗余信息，在可完全恢复原始数据而不引入任何失真的条件下使比特率最小的压缩方法。由于压缩率受到数据统计冗余度的理论限制，压缩比一般为2:1到5：1.在众多的应用中，无损压缩是仅有的可以接受的数据压缩方法，其中的一种应用是医疗或商业文件的归档。在这些应用场合中，有损压缩通常因为法律原因而被禁止。另一种应用是卫星成像处理。还有一类应用是数字X光照相术，这种应用中信息的丢失会导致损坏诊断的精确性。在这一类的情况下，无损压缩的需要是由与其用户和图像性质所推动的。无损压缩广泛地被应用在各个所需的领域，适应当前多媒体技术发展的需要。可见，这一领域的突破对于通信和多媒体事业的发展将具有深远的影响。经常使用的无损压缩方法有游程编码、霍夫曼编码和算术编码等。2.21游程编码原理游程编码主要用于量化后出现概率大量零系数的情形，利用游程来表示连零码，以降低为表示零码所用的数据量。游程编码往往与其他编码方法结合使用。游程编码通过将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。因此，RLE是无损压缩技术。游程：数字序列中连续出现相同符号的一段。(1)二元序列的游程：只有“0”和“1”两种符号。连0的个数称为0游程；连1的个数称为1游程。(2)游程变换：二元序列000101110010001.、、、、、、可变换成如下游程序列3011103120113011当游程很短，也就是像素的灰度频繁改变时，使用行程码不适宜的。2.22霍夫曼编码原理霍夫曼编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成霍夫曼编码算法基于一种称为“编码树”（codingtree）的技术。算法步骤如下：（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。以下这个简单例子说明了这一过程。1)．字母A,B,C,D,E已被编码，相应的出现概率如下：p(A)=0.16,p(B)=0.51,p(C)=0.09,p(D)=0.13,p(E)=0.112)．C和E概率最小，被排在第一棵二叉树中作为树叶。它们的根节点CE的组合概率为0.20。从CE到C的一边被标记为1，从CE到E的一边被标记为0。这种标记是强制性的。所以，不同的霍夫曼编码可能由相同的数据产生。3)．各节点相应的概率如下：p(A)=0.16,p(B)=0.51,p(CE)=0.20,p(D)=0.13D和A两个节点的概率最小。这两个节点作为叶子组合成一棵新的二叉树。根节点AD的组合概率为0.29。由AD到A的一边标记为0，由AD到D的一边标记为1。如果不同的二叉树的根节点有相同的概率，那么具有从根到节点最短的最大路径的二叉树应先生成。这样能保持编码的长度基本稳定。4)．剩下节点的概率如下：p(AD)=0.29,p(B)=0.51,p(CE)=0.20AD和CE两节点的概率最小。它们生成一棵二叉树。其根节点ADCE的组合概率为0.49。由ADCE到AD一边标记为0，由ADCE到CE的一边标记为1。5)．剩下两个节点相应的概率如下：p(ADCE)=0.49,p(B)=0.51它们生成最后一棵根节点为ADCEB的二叉树。由ADCEB到B的一边记为1，由ADCEB到ADCE的一边记为0。6)．图2-1为霍夫曼树结构。编码结果被存放在一个表中：w(A)=001,w(B)=0,w(C)=111,w(D)=100,w(E)=011P(A)=0.160P(B)=0.510(1.00)（0.29）0P(C)=0.0911（0.2）1(0.49)P(D)=0.131P(E)=0.110图2-1霍夫曼树结构表2-2霍夫曼编码表2.23算术编码原理算术编码是20世纪80年代发展起来的一种熵编码方法，它已渐渐受到人们的注意。它的基本原理是，任何一个数据序列均可表示成0和1之间的一个间隔，该间隔的位置与输入的概率分布有关。可以根据信源的统计特性来设计具体的编码器，也可以针对未知概率的信源设计能够自适应适配其分布的算术编码器，这两种形式的编码器均可以用硬件实现，有关的实验数据表明，在未知信源概率分布的大部分情形下，算术编码优于霍夫曼编码。算术编码的基本规则如下：（1）初始状态：编码起点C0=0，区间宽度A0=1.（2）新编码点：Ci=Ci-1+(Ai-1)*Pi式中：Ci-1是原编码点，Ai-1是原区间宽度，Pi为所编符号对应的积累概率。新区间宽度：符号概率霍夫曼编码A0.16001B0.510C0.09111D0.13100E0.11011Ai=Ai-1*Pi式中：Pi为所编符号对应的概率。3、结论目前，图像压缩技术已经得到了广泛的推广应用，对人们的日常生活产生了重要的影响。VCD、DVD和各种档次的数字点数都是图像压缩技术的应用实例。“图像压缩编码”是图像处理的重要内容，随着通信技术和多媒体技术的发展，图像压缩编码技术已进入实用阶段，图像编码可以看作是一维信号编码或三维的推广。在当前数字图像压缩领域中，无损压缩由于具有高度的保真效果，完全的可复原性，获得了越来越多的关注。在卫星科学探测领域，数据存储和传输必须用无损压缩技术才能保证图像细节不被破坏。企事业单位的数据存档必须是无损的，这样才能完全复原而不至于丢失重要信息。因此，对高效的无损压缩方法有着越来越迫切的需要，除了对压缩比的要求外，还需要压缩的实时性好，可靠性高等。研究高性能的无损压缩算法，具有一定的理论意义和实用价值。4、参考文献1、贾永红，数字图像处理，武汉：武汉大学出版社，2003.92、黄贤武，王佳俊，李家华，数字图像处理与压缩编码技术，四川：电子科技大学出版社，2000年。3、TinkuAcharyaAjoyK.Ray著，田浩等译，ImageProcessingPrinciplesandApplications，北京：清华大学出版社，2007.74、C算法.第一卷。基础、数据结构、排序和搜索，RobertSedgewick著，周良忠译，北京：人民邮电出版社，2004.65、籍俊伟.无损压缩技术的研究与应用【期刊论文】-北京工业大学，20046、田瑞财，殷晓丽.基于哈弗曼编码的图像压缩技术研究【期刊论文】-科技资讯，20097、章毓晋.图像工程（上册）-图像分析，第二版，北京：清华大学出版社，2005,78、章毓晋.图像工程（下册）-图像分析，第二版，北京：清华大学出版社，2005,79、冯希.几种图像无损压缩与编码方法的比较研究【期刊论文】-中国科学院研究生院，（西安光学精密机械研究所）200810、王汇源.数字图像传输原理与技术.北京:国防工业出版社,1995，9