无损数据压缩

第二章无损压缩技术主要内容数据压缩的基本原理和方法数据压缩技术的性能指标数据冗余的类型与压缩方法分类常用数据压缩方法1．信息的含义在信息理论中，经常用到消息和信息的概念。1)消息消息是由符号、文字、数字或语音组成的表达一定含义的一个序列，如一份电报和报纸上的一段文字。消息是信息的载体，是表达信息的工具。2)信息信息是消息的内涵，是消息中的不确定性内容。2.1数据压缩的基本原理和方法消息中事件发生的不确定性小，即可能性大，则事件的信息量就小；反之，一个发生可能性很小的事件，携带的信息量就很大。2.1数据压缩的基本原理和方法2.信息的量度1)信息量及熵

(1)信息量定义设信源x由属于集合Am＝{a1,a2,…,am}的m个可能的符号产生，若信源事件aj的概率为P(aj)，则定义事件aj的信息量I(aj) I(aj)＝-logP(aj)(2.1)作为事件aj所包含的信息量的量度，称为自信息。 单位：取2为底的对数，则单位为比特(bit)； 取e为底的对数，则单位为奈特。2.1数据压缩的基本原理和方法 从信息量的定义可以看出，信息是事件aj的不确定因素的度量。事件发生的概率越大，事件的信息量越小；反之，一个发生可能性很小的事件，携带的信息量就很大，甚至使人们“震惊”。 例如：在32个数码中任选1个数码时，设每个数码选中的概率是相等的，则

那么，任一数码的信息量为

2.1数据压缩的基本原理和方法

(2)信源的熵一个通信系统并非只传送1个符号，而是多个符号，这就需要定义整个信源符号的平均信息量的大小。 我们把自信息的统计平均值——数学期望

(2.2)

即信源x中每个符号的平均信息量，称为信源x的熵。 当信源x中的每个符号是等概率的且是独立的时候，平均信息量最大，此时，j=1，2，…，m

代入式(2.2)得(2.3)2.1数据压缩的基本原理和方法 例如：若信号x{a1,a2}的概率分别为P(a1)＝0.9，P(a2)＝0.1，则符号的平均信息量，即信源x的熵为

H(x)=-(0.9×lb0.9+0.1×lb0.1)=0.467bit

若a1,a2等概率，P(a1)=P(a2)=0.5，则信源x的平均信息量达到最大，即

所以二进制1位数据(0/1)的每1位的信息量即为1比特。数据无损压缩的理论——信息论(InformationTheory)1948年创建的数学理论的一个分支学科，研究信息的编码、传输和存储；该术语源于ClaudeShannon(香农)发表的“AMathematicalTheoryofCommunication”论文题目，提议用二进制数据对信息进行编码；最初只应用于通信工程领域，后来扩展到包括计算在内的其他多个领域，如信息的存储、信息的检索等。在通信方面，主要研究数据量、传输速率、信道容量、传输正确率等问题。2.1数据压缩的基本原理和方法TheFatherofInformationTheory——

ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA/news/2001/february/26/1.html信息论之父2.1数据压缩的基本原理和方法返回2.2数据压缩技术的性能指标

1）压缩的必要性音频、视频的数据量很大，如果不进行处理，计算机系统几乎无法对它进行存取和交换。例如：一幅中等分辨率（640*480）的真彩色图像（24b/像素），它的数据量约为0.9MB/帧，若要达到每秒25帧的全动态显示要求，每秒所需的数据量约为22MB。对于声音也是如此，CD音质的声音每秒将有约为172KB的数据量。2）数据可被压缩的依据数据本身存在冗余听觉系统的敏感度有限视觉系统的敏感度有限2.2数据压缩技术的性能指标

3）从哪些方面评价一个压缩系统2.2数据压缩技术的性能指标●压缩比●图像质量●压缩解压速度●硬件和软件压缩比

输入数据和输出数据之比。例如：图像512×480，24位输入＝(512×480×24)/8=737280B若输出＝15000B

则压缩比＝737280/15000＝492.2数据压缩技术的性能指标图像质量压缩方法：无损压缩有损压缩有损压缩：失真情况很难量化，只能对测试的图像进行估计。

2.2数据压缩技术的性能指标压缩解压速度在许多应用中，压缩和解压可能不同时用，在不同的位置不同的系统中。所以，压缩、解压速度分别估计。静态图像中，压缩速度没有解压速度严格；动态图像中，压缩、解压速度都有要求，因为需实时地从摄像机或其他设备中抓取动态视频。2.2数据压缩技术的性能指标硬软件系统

有些压缩解压工作可用软件实现。设计系统时必须充分考虑：算法复杂——压缩解压过程长算法简单——压缩效果差目前有些特殊硬件可用于加速压缩/解压。硬件系统速度快，但各种选择在初始设计时已确定，一般不能更改。因此在设计硬接线压缩/解压系统时必须先将算法标准化。2.2数据压缩技术的性能指标冗余的基本概念

指信息存在的各种性质的多余度。举例：（1）广播员读文稿时每分钟约读180字，一个汉字占两个字节；文本数据量为360B；（2）如果对语音录音，由于人说话的音频范围为20Hz到4kHz，即语音的带宽为4kHz，若设量化位数为8bits,则一秒钟的数据量为：4k×8×2=64kbit/s=8KB/s则一分钟的数据是480KB。

2.3数据冗余的类型与压缩方法分类360B

480KB 设一幅图片有4个灰度级S={A，B，C，D}，这4个灰度级所出现的概率分别为P(aj)={0.6，0.2，0.06，0.14}，则

H(x)=-(0.6×lb0.6+0.2×lb0.2+0.06×lb0.06+0.14×lb0.14)=1.547bit

即其平均信息熵为1.547bit。这说明表示这4个灰度级所使用的最少平均位数为1.547bit。 平均信息熵是一种理论上的最佳编码的平均码长。我们平常使用的一般为自然码编码，表示每一事件的位数是相同的。如果对A、B、C、D4个灰度级采用自然码进行编码，即2.3数据冗余的类型与压缩方法分类A 00B 01C 10D 11

每一个灰度级用两位二进制表示，则4个灰度级的平均码长为2，而平均信息熵是理论上的最佳编码的平均码长，为1.547位。显然，自然码编码和理论上的最佳编码存在一定的差距，这一差距常用冗余度

来表示。2.3数据冗余的类型与压缩方法分类 冗余度表示原始图像编码中所包含冗余信息的多少，应越小越好。在本例中，灰度级的自然码编码长度为2bit，平均信息熵是理论上的最佳编码码长，为1.547bit，显然，在自然码编码中包含有冗余信息。如何找出一种编码方法，使其平均码长尽量接近信息熵，是图像编码所追求的目标。 另外，如果4个灰度级是等概率出现的，均为0.25，则信源的平均信息熵为

即在等概率的情况下，自然码编码的冗余度为0。2.3数据冗余的类型与压缩方法分类数据冗余的类别空间冗余时间冗余统计冗余信息熵冗余结构冗余知识冗余视觉冗余听觉冗余2.3数据冗余的类型与压缩方法分类●空间冗余2.3数据冗余的类型与压缩方法分类同一景物表面上采样点的颜色之间往往存在着空间连贯性，但是基于离散像素采样来表示物体颜色的方式通常没有利用这种连贯性。例如：图像中有一片连续的区域，其像素为相同的颜色，空间冗余产生。●时间冗余序列图像（如电视图像和运动图像）和语音数据的前后有着很强的相关性，经常包含着冗余。在播出该序列图像时，时间发生了推移，但若干幅画面的同一部位没有变化，变化的只是其中某些地方，这就形成了时间冗余。空间冗余和时间冗余是把图像信号看作概率信号时反应出的统计特性，因此，这两种冗余也被称为统计冗余。2.3数据冗余的类型与压缩方法分类●统计冗余●结构冗余在某些场景中，存在着明显的图像分布模式，这种分布模式称作结构。图像中重复出现或相近的纹理结构，结构可以通过特定的过程来生成。例如：方格状的地板，蜂窝，砖墙，草席等图结构上存在冗余。已知分布模式，可以通过某一过程生成图像。2.3数据冗余的类型与压缩方法分类●信息熵冗余信息熵实际情况又称编码冗余。信息熵是指一组数所携带的信息量。由图像的记录方式与人对图像的知识差异所产生的冗余称为知识冗余。●知识冗余

人类的视觉系统对于图像场的注意在非均匀和非线性的，视觉系统并不是对图像的任何变化都能感知。●视觉冗余●听觉冗余人耳对不同频率的声音的敏感性是不同的，并不能察觉所有频率的变化，对某些频率不必特别关注，因此存在听觉冗余。2.3数据冗余的类型与压缩方法分类数据压缩技术分类指使压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。

典型的算法有：Huffman编码，算术编码，行程编码等。特点：压缩比较低，为2:1——5:1，一般用来压缩文本，数据。2.3数据冗余的类型与压缩方法分类●无损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。典型的算法有：混合编码的JPEG标准，预测编码，变换编码等。特点：压缩比高，为几十到几百倍一般用于图像，声音，视频压缩。2.3数据冗余的类型与压缩方法分类●有损压缩数据压缩的方法统计编码预测编码变换编码混合编码

分析合成编码2.4常用数据压缩方法的基本原理

根据消息出现概率的分布特性而进行的压缩编码。

Huffman编码

算术编码

行程编码

词典编码2.4常用数据压缩方法的基本原理●统计编码Huffman编码统计独立信源，能达到最小平均码长的编码方法。编码效率高。霍夫曼(D.A.Huffman)在1952年提出和描述的“从下到上”的熵编码方法。根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少。广泛用在JPEG,MPEG,H.26X等各种信息编码标准中。统计编码一Huffman编码编码步骤：

(1)初始化，根据符号概率的大小按由大到小顺序对符号进行排序。

(2)把概率最小的两个符号组成一个节点。

(3)重复步骤（2）。

(4)从根节点开始到相应于每个符号的“树叶”，从上到下标上“0”(上枝)或者“1”(下枝)，至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。

(5)从根节点开始顺着树枝到每个叶子分别写出每个符号的代码。统计编码一霍夫曼编码举例现有一个由5个不同符号组成的30个符号的字符串：BABACACADADABBCBABEBEDDABEEEBB计算(1)该字符串的霍夫曼码(2)该字符串的熵(3)该字符串的平均码长(4)编码前后的压缩比统计编码一符号出现的次数log2(1/pi)分配的代码需要的位数B101.585?A81.907?C33.322?D42.907?E52.585?合计30符号出现的概率统计编码一(1)计算该字符串的霍夫曼码步骤①：按照符号出现概率大小的顺序对符号进行排序步骤②：把概率最小的两个符号组成一个节点P1步骤③：重复步骤②，得到节点P2，P3，P4，……，

PN，形成一棵树，其中的PN称为根节点步骤④：从根节点PN开始到每个符号的树叶，从上到下

标上0(上枝)和1(下枝)，至于哪个为1哪个为0则

无关紧要，但通常把概率大的标成1，概率小的

标成0步骤⑤：从根节点PN开始顺着树枝到每个叶子分别写出

每个符号的代码统计编码一符号B(10)A(8)E(5)D(4)C(3)P1(7)P2(12)P3(18)P4(30)01101010编码B(11)A(10)E(00)D(011)C(010)统计编码一符号出现的次数lb(1/pi）分配的代码需要的位数B101.5851120A81.9071016C33.3220109D42.90701112E52.5850010合计301.0675个符号的代码统计编码一

(2)计算该字符串的熵

其中，是事件的集合，并满足H(S)=(8/30)×log2(30/8)+(10/30)×log2(30/10)+

(3/30)×log2(30/3)+(4/30)×log2(30/4)+

(5/30)×log2(30/5)

=[30lg30–(8×lg8＋10×lg10＋3×lg3＋4

×lg4＋5lg5)]/(30×log22)

=(44.3136－24.5592)/9.0308＝2.1874(Sh)统计编码一(3)计算该字符串的平均码长平均码长：

＝(2×8＋2×10＋3×3＋3×4＋2×5)/30

＝67/30=2.233位/符号(4)计算编码前后的压缩比编码前（等长）：5个符号需3位，30个字符，90位编码后：共67位 压缩比:90/67=1.34:1统计编码一霍夫曼编码举例2编码前N=8symbols:{a,b,c,d,e,f,g,h},3bitspersymbol(N=23=8)P(a)=0.01,P(b)=0.02,P(c)=0.05,P(d)=0.09,P(e)=0.18,P(f)=0.2,P(g)=0.2,

P(h)=0.25计算(1)该字符串的霍夫曼码(2)该字符串的熵(3)该字符串的平均码长(4)编码效率统计编码一该字符串的霍夫曼码(2)该字符串的熵(3)该字符串的平均码长(4)编码效率统计编码一Huffman编码的注意点Huffman编码没有错误保护功能，如果码中有错误，则可能引起接下来的一连串译码错误。Huffman编码是可变长编码，因此很难随意查找或调用中的文件内容。Huffman依赖于信源的统计特性。Huffman编码的每个码字都是整数，因此实际上平均码长很难达到信息熵的大小。Huffman编码解码必须要有码表，如果消息数目很多，那么所需要存储的码表也很大，这将影响系统的存储量及编、译码速度。统计编码一010.11010.2600.3510.611101000.391.00码字码长01200233344平均码长：2.72Huffman编码过程a10.20a20.19a30.18a40.17a50.15a60.10a70.01算术编码算术编码把一个信源集合表示为实数线上的0到1之间的一个区间。这个集合中的每个元素都要用来缩短这个区间。信源集合的元素越多，所得到的区间就越小，当区间变小时，就需要一些更多的数位来表示这个区间，这就是区间作为代码的原理。算术编码首先假设一个信源的概率模型，然后用这些概率来缩小表示信源集的区间。统计编码二算术编码新子区间的起始位置＝前子区间的起始位置＋当前符号的区间左端×前子区间长度新子区间的长度＝前子区间的长度×当前符号的概率（等价于范围长度）

最后得到的子区间的长度决定了表示该区域内的某一个数所需的位数。统计编码二算术编码[例]假设信源符号为{00,01,10,11}，这些符号的概率分别为{0.1,0.4,0.2,0.3}，根据这些概率可把间隔[0,1)分成4个子间隔：[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1)，其中[x,y)表示半开放间隔，即包含x不包含y。上面的信息可综合在下表中。符号00011011概率0.3初始编码间隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)统计编码二算术编码统计编码二算术编码要注意的几个问题：由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。算术编码器对整个消息只产生一个码字，这个码字是在间隔[0,1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。统计编码二行程编码是最简单、最古老的压缩技术之一，主要技术是检测重复的比特或字符序列，并用它们的出现次数取而代之。该方法有两大模式：一是消零(消空白)，二是行(游)程(runlength)编码。

消零(或消空白)法

将数字中连续的“0”或文本中连续的空白用一个标识符(或特殊字符)后跟数字N(连续“0”的个数)来代替。

如数字序列：742300000000000000000055编码为：7423Z1855统计编码三行程编码法

任何重复的字符序列可被一个短格式取代。该算法适合于任何重复的字符。一组n个连续的字符c将被

c和一个特殊的字符取代。当然，若给定字符仅重复两次就不要用此方法。 任何重复的字符由“该字符＋记号(M)＋重复次数”代替。例如字符序列：Name:..........CR

编码为：Name:

.M10CR统计编码三词典编码词典编码(dictionaryencoding)根据数据本身包含有重复代码这个特性。例如文本文件和光栅图像。两类统计编码四第一类: 查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。

统计编码四第二类:从输入的数据中创建一个“短语词典(dictionaryofthephrases)”，编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。统计编码四统计编码四LZW编码简介LZW通过建立一个字符串表,用较短的代码来表示较长的字符串来实现压缩（第二类）。字符串和编码的对应关系是在压缩过程中动态生成的,并且隐含在压缩数据中,解压的时候根据表来进行恢复,是一种无损压缩。全称Lempel-Ziv-WelchEncoding，简称LZW的压缩算法。统计编码四LZW压缩有三个重要的对象数据流(CharStream)编码流(CodeStream)编译表(StringTable)。在编码时，数据流是输入对象（文本文件的数据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都须要用借助的对象。统计编码四LZW编码基本原理提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大