展会信息港展会大全

压缩算法,霍夫曼编码,LZW,Rice,LZ77
来源:互联网   发布日期:2011-09-19 11:13:25   浏览:10645次  

导读:压缩算法概述...

一、 行程长度压缩
  原理是将一扫描行中的颜色值相同的相邻像素用一个计数值和那些像素的颜色值来代替。例如:aaabccccccddeee,则可用3a1b6c2d3e来代替。对于拥有大面积,相同颜色区域的图像,用RLE压缩方法非常有效。由RLE原理派生出许多具体行程压缩方法:
  1.PCX行程压缩方法: 该算法实际上是位映射格式到压缩格式的转换算法,该算法对于连续出现1次的字节Ch,若Ch>0xc0则压缩时在该字节前加上0xc1,否则直接输出Ch,对于连续出现N 次的字节Ch,则压缩成0xc0+N,Ch这两个字节,因而N最大只能为ff-c0=3fh(十进制为63),当N大于63时, 则需分多次压缩。
  2.BI_RLE8压缩方法:在WINDOWS的位图文件中采用了这种压缩方法。该压缩方法编码也是以两个字节为基本单位。其中第一个字节规定了用第二个字节指定的颜色重复次数。 如编码 0504表示从当前位置开始连续显示5个颜色值为04的像素。当第二个字节为零时第二个字节有特殊含义:0表示行末;1表示图末;2转义后面2个字节, 这两个字节分别表示下一像素相对于当前位置的水平位移和垂直位移。这种压缩方法所能压缩的图像像素位数最大为8位(256色)图像。
  3.BI_RLE压缩方法: 该方法也用于WINDOWS位图文件中,它与 BI_RLE8编码类似,唯一不同是:BI_RLE4的一个字节包含了两个像素的颜色,因此,它只能压缩的颜色数不超过16的图像。因而这种压缩应用范围有限。
  4.紧缩位压缩方法(Packbits):该方法是用于Apple公司的Macintosh机上的位图数据压缩 方法, TIFF 规范中使用了这种方法, 这种压缩方法与BI_RLE8压缩方法相似,如1c1c1c2132325648 压缩为:83 1c 21 81 32 56 48,显而易见, 这种压缩方法最好情况是每连续128个字节相同,这128个字节可压缩为一个数值7f。这种方法还是非常有效的。

二、霍夫曼编码压缩:
  也是一种常用的压缩方法。是1952年为文本文件建立的,其基本原理是频繁使用的数据用较短的代码代替,很少使用的数据用较长的代码代替,每个数据的代码各不相同。这些代码都是二进制码,且码的长度是可变的。如: 有一个原始数据序列,ABACCDAA则编码为A(0),B(10),C(110),(D111),压缩后为010011011011100。产生霍夫曼编码需要对原始数据扫描两遍,第一遍扫描要精确地统计出原始数据中的每个值出现的频率,第二遍是建立霍夫曼树并进行编码,由于需要建立二叉树并遍历二叉树生成编码,因此数据压缩和还原速度都较慢,但简单有效,因而得到广泛的应用。
哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号,长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示,而不常见的符号需要很多为来表示。
哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而,它并不处理符号的顺序和重复或序号的序列。


三、LZW压缩方法
  LZW压缩技术比其它大多数压缩技术都复杂, 压缩效率也较高。其基本原理是把每一个第一次出现的字符串用一个数值来编码,在还原程序中再将这个数值还成原来的字符 串,如用数值0x100代替字符串"abccddeee"这样每当出现该字符串时,都用0x100代替,起到了压缩的作用。 至于0x100与字符串的对应关系则是在压缩过程中动态生成的,而且这种对应关系是隐含

赞助本站

AiLab云推荐
推荐内容
展开

热门栏目HotCates

Copyright © 2010-2024 AiLab Team. 人工智能实验室 版权所有    关于我们 | 联系我们 | 广告服务 | 公司动态 | 免责声明 | 隐私条款 | 工作机会 | 展会港