第3章 多媒体数据压缩-2010

1、1第3章 多媒体数据压缩(sh j y su)3.1 数据压缩的基本原理和方法3.2 音频压缩(y su)标准3.3 图像压缩标准3.4 视频压缩标准共一百六十九页23.1 数据压缩(sh j y su)的基本原理和方法所谓“数据”，通常是指信源所发信号的数字化表示或记录所谓数据压缩，就是以最少的数码表示信源所发出的信号，减少(jinsho)容纳给定消息集合或数据采样集合的信息空间。信息空间亦即被压缩对象是指：物理空间：如储存器、磁盘、光盘等数据存储介质时间区间：如传输给定消息集合所需的时间电磁频谱区域：如传输给定消息集合所需的带宽等。压缩的必要性音频、视频的数据量很大，如果不进行处理，计算机

2、系统几乎无法对它进行存取和交换。共一百六十九页33.1 数据压缩(sh j y su)的基本原理和方法1950年在计算机普及之前，世界范围内信息量的增长速度是每150年翻一番；随着计算机的广泛应用，1950-1960年间信息量的增长达到每10年翻一番；1960-1992年间缩短为每5年翻一番。人们预计2020年以后信息量每73天就要翻一番。几个未经压缩的数字化信息的例子：B5（180 x255mm）、300dpi（12像素点/mm）-6.61MB/页-CD-ROM 98页双声道立体声激光(jgung)唱盘（CD-DA）： 44.1x103x16x2=1.41Mb/s，650M ：- 约一小时数

3、字音频磁带（DAT）：48x103x16=768kb/s共一百六十九页43.1 数据压缩(sh j y su)的基本原理和方法SIF（Source Input Format）格式，NTSC制式，4:4:4采样(ci yn)每帧数据：352x240 x3=253KB每秒数据：253x30=7.603MB/sCCIR（International Consultative Committee for Radio）格式，PAL制式，4：4：4采样每帧数据：720 x576x3=1.24MB每秒数据：1.24x25=31.3MB/s实验表明，176144的YUV原始视频在10Mbps的LAN上传送速率是

4、3帧/秒左右。陆地卫星遥感图片的水平和垂直分辨率分别为2340及3240，四 波 段、 采样精度为7bit的一幅图像的数据量为212Mb，按每天30幅计算，其数据量为6.36Gb，而每年的数据量则高达2300Gb。共一百六十九页53.1 数据压缩(sh j y su)的基本原理和方法压缩的可行性信息论认为：若信源编码(bin m)的熵大于信源的实际熵，该信源中一定存在冗余度。空间冗余、时间冗余、视觉冗余、听觉冗余等共一百六十九页63.1.1 数据压缩(sh j y su)技术的性能指标有三个关键参数评价一个(y )压缩系统压缩比压缩性能常常用压缩比定义（输入数据和输出数据比）图象质量无损压缩

5、（图象质量不变）有损压缩，失真情况很难量化，只能对测试的图象进行估计。压缩和解压的速度压缩和解压可能不同时用，压缩、解压速度分别估计。共一百六十九页73.1.2 数据冗余的类型与压缩方法(fngf)分类数据冗余的类型空间冗余时间冗余信息熵冗余视觉冗余听觉(tngju)冗余其它冗余结构冗余知识冗余共一百六十九页83.1.2 数据(shj)冗余的类型与压缩方法分类空间冗余这是图像数据中经常存在的一种冗余。在同一幅图像中，规则物体和规则背景的表面物理特性(txng)具有相关性，这些相关性的光成像结构在数字化图像中就表现为数据冗余。A共一百六十九页93.1.2 数据冗余(rn y)的类型与压缩方法分类

6、时间冗余这是序列(xli)图像（电视图像、运动图像）和语音数据中经常出现的冗余。T共一百六十九页103.1.2 数据冗余的类型(lixng)与压缩方法分类信息熵冗余（编码冗余）信息熵（entropy）是指一组数据所携带的信息量H= - Pilog2Pi (i=0k-1) k为数据类数或码元个数Pi为第i个数据类数或码元发生的概率d=Pib(yi) (i=0k-1)b(yi)是分配(fnpi)给码元yi的比特数，理论上应该是b(yi) -log2Pi ，实际中很难估计出码元的的概率，当选用等概率时，d则大于H共一百六十九页113.1.2 数据冗余的类型与压缩(y su)方法分类视觉冗余人类视觉系

7、统对于图像场的任何变化，并不是都能感知的。人类视觉系统一般的分辨(fnbin)能力约为26灰度级一般图像量化采用28灰度级听觉冗余人耳对不同频率的声音的敏感性是不同的，并不能察觉所有频率的变化，对某些频率不必特别关注，存在听觉冗余。知识冗余有许多图像的理解与某些基础知识有相当大的相关性。例如人脸的图像有固定的结构。共一百六十九页123.1.2 数据(shj)冗余的类型与压缩方法分类结构(jigu)冗余共一百六十九页133.1.2 数据冗余的类型与压缩(y su)方法分类根据解码后数据与原始数据是否完全一致可以分为两大类：一类是熵编码、冗余压缩法，也称无损压缩法、无失真压缩法、可逆编码等多用于文

8、本、数据的压缩，非线性编辑系统为了保证视频质量，有些高档系统采用的是无失真压缩方法。二是熵压缩法，也称有损压缩法、有失真压缩法。图像、声音(shngyn)、动态视频根据编码原理预测编码，变换编码，统计编码，分析合成编码，混合编码等共一百六十九页143.1.3 常用(chn yn)数据压缩方法的基本原理统计编码(bin m)识别一个给定的数据流中出现频率最高的比特或字节模式，并用比原始比特更少的比特数来对其编码。频率越低的模式，其编码的位数越多，频率越高的模式编码位数越少。若码流中所有模式出现的概率相等，则平均信息量最大， 信源就没有冗余。(1)香农-范诺编码(2)行程编码(3)LZW编码(4)

9、霍夫曼编码(5)算术编码共一百六十九页153.1.3 常用数据压缩(sh j y su)方法的基本原理(1)香农-范诺编码香农-范诺编码算法需要用到下面两个基本概念：Entropy(熵)的概念: 熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。某个事件的信息量用:Ii- pi *log2 pi表示，其中pi为第i个事件的概率0 pi 1信源S的熵的定义:按照香农(Shannon)的理论，信源S的熵定义为H(S) = EIi = pi*log2(1/pi) i：1n其中pi是符号(fho)Si在S中出现的概率；log2(1/pi)表示包含在Si中的

10、信息量，也就是编码Si所需要的位数。共一百六十九页163.1.3 常用数据压缩(sh j y su)方法的基本原理例如，一幅用256级灰度表示的图象，如果每一个象素点灰度的概率均为 pi=1/256，编码每一个象素点就需要 比特。有一幅40个象素组成的灰度图象，灰度共有5级，分别用符号A、B、C、D和E表示，40个象素中出现灰度A的象素数有15个，出现灰度B的象素数有7个，出现灰度C的象素数有7个等等(dn dn)，如表3-01所示。如果用3个比特表示5个等级的灰度值，也就是每个象素用3比特表示，编码这幅图象总共需要120比特。按照香农理论，这幅图象的熵为：H(S) = (15/40) * l

11、og2 (40/15) + (7/40) * log2 (40/7) + . + (5/40) * log2 (40/5) =2.196这就是说每个符号用2.196比特表示可以，40个象素需用87.84比特。8表3-01共一百六十九页173.1.3 常用(chn yn)数据压缩方法的基本原理最早阐述和实现这种编码的是香农(1948年)和范诺(1949年）。它采用从上到下的方法进行编码。首先按照符号出现的频度(pn d)或概率排序，例如A、B、C、D、E，如表3-02所示，然后使用递归方法分成两个部分，每一部分具有近似相同的次数，如图3-01所示。按照这种方法进行编码得到的总比特数为91。压缩比

12、约为1.3 : 1。表3-02 Shannon-Fano算法举例表共一百六十九页183.1.3 常用(chn yn)数据压缩方法的基本原理Shannon-Fano算法编码(bin m)过程：符号ABCDE概率15/407/407/406/405/4001000111码字000110110111共一百六十九页193.1.3 常用(chn yn)数据压缩方法的基本原理(2)行程编码基本原理：文字、图象、声音等数据中，会出现大量重复的字符或数值。重复的数据可以用该值以及重复的次数来代替。将一个相同值的连续串用其值和串长来代替。比如在传真通信中，所传的文件多数为二值（黑、白）图像 。连续出现的像素点数

13、称为行程长度，简称长度。适合：如文字输入的二值图像、黑白或彩色图像（它们的分布都属于平稳(pngwn)的随机分布，在同一行或相邻行的像素之间具有较强的相关性）-效果好；纯随机的“沙丘型”图像-效果差共一百六十九页203.1.3 常用数据压缩(sh j y su)方法的基本原理主要技术是检测重复的比特或字符序列，并用它们的出现次数取而代之。该方法(fngf)有两大模式：一是消零(消空白)，将数字中连续的“0”或文本中连续的空白用一个标识符(或特殊字符)后跟数字N(连续“0”的个数)来代替。如数字序列： 742300000000000000000055编码为： 7423Z1855共一百六十九页21

14、3.1.3 常用数据压缩(sh j y su)方法的基本原理二是行(游)程(run length)编码。任何重复的字符序列可被一个短格式取代。任何重复4次或4次以上的字符由“该字符记号(M)重复次数”代替。例如(lr)数字序列： Name: . . . . . . . . . . CR 编码为： Name: . M10 CR 用RLE编码方法得到的代码为：80315084180。共一百六十九页223.1.3 常用数据压缩(sh j y su)方法的基本原理AAAAAAAAAAAAAAA15A压缩率 15 bytes / 2 bytes = 7.5AAAABBBBBCCCCCCCCDEEEE 4

15、A5B8C1D4E 压缩率 22 bytes / 10 bytes = 2.2 MyDogHasFleas 1M1y1D1o1g1H1a1s1F1l1e1a1s压缩率 13 bytes / 26 bytes = 0.5 共一百六十九页23RLE编码方式共一百六十九页24RLE编码流程图共一百六十九页253.1.3 常用(chn yn)数据压缩方法的基本原理RLE编码模式由于所针对的编码类型的不同，RLE算法也有很大的区别对位图图像编码时，根据所编码的元素的类型，RLE编码模式可以分为：位模式对Bit进行编码，而忽略Byte和Word的界限单色图像（monochrome ）字节模式对Byte进行

16、编码，而忽略Bit和Word的界限2字节的数据包，适用于1Byte/Pixel像素(xin s)模式对Pixel进行编码，一个Pixel用多个Byte表示一个Pixel包含多少个Byte的信息保存的图像的Header部分共一百六十九页26RLE编码模式共一百六十九页273.1.3 常用(chn yn)数据压缩方法的基本原理RLE中的负压缩MyDogHasFleas经过RLE编码之后，长度被压缩了0.5倍（即膨胀了1倍）如何解决？随之而来的问题压缩数据的行程由3个字符变成了4个，影响了压缩效率控制字符的引入涉及到了控制字符的选择，并且(bngqi)要把出现在数据中的控制字符编码成3个共一百六十九

17、页283.1.3 常用(chn yn)数据压缩方法的基本原理RLE的三字节编码(bin m)模式共一百六十九页293.1.3 常用(chn yn)数据压缩方法的基本原理RLE图片格式选用RLE作为压缩编码算法(sun f)的图片文件格式有：MacPaintBMPPDFPCXTIFFRLE（CompuServe ，Utah以及 Microsoft）以RLE（CompuServe）格式为例进行说明观看2个RLE图片使用PMView软件共一百六十九页303.1.3 常用(chn yn)数据压缩方法的基本原理RLE（CompuServe）CompuServe RLE文件格式形成于80年代，是为1-bi

18、t图像制定(zhdng)的标准文件头包含3个字符ASCII ESC（HEX 1B）ASCII G（HEX 47）ASCII H（HEX 48）或者M（HEX 4D）表示高分辨率图像模式，分辨率为256192表示中分辨率图像模式，分辨率为12896共一百六十九页313.1.3 常用(chn yn)数据压缩方法的基本原理文件体文件体位于文件头之后由一对ASCII码表示，第一位ASCII码表示背景像素（黑）的值，第二位ASCII码表示前景像素（白）的值。ASCII值 相应的像素个数 32如HEX（20 7E）表示 0 个背景象素，94个前景像素文件尾 再次浏览(li ln)RLE图片用16进制编辑器

19、打开RLE文件，找到其中的文件头，文件体以及文件尾共一百六十九页323.1.3 常用数据压缩(sh j y su)方法的基本原理(3)LZW编码词典编码的思想：数据本身包含有重复代码这个特性。例如文本文件就具有这种特性。词典编码法的种类很多，归纳起来大致有两类。第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。这里所指的“词典”：是指用以前处理过的数据来表示编码过程中遇到(y do)的重复部分。第二类算法的想法是企图从输入的数据中创建一个“短语词典(dictionary of th

20、e phrases)”，短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。共一百六十九页333.1.3 常用数据压缩(sh j y su)方法的基本原理共一百六十九页343.1.3 常用数据压缩(sh j y su)方法的基本原理J.Ziv和A.Lempel在1978年首次发表了介绍这种编码方法的文章。在他们的研究基础(jch)上，Terry A.Weltch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW(Lempel-Ziv Walch)压缩编码。LZW算法得到普遍采用，对LZW算法进

21、一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图象格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。参考多媒体技术基础，林福宗，清华大学出版社共一百六十九页353.1.3 常用数据压缩(sh j y su)方法的基本原理LZW编码LZW编码时，首先将原始的数据分成多个条纹，每个条纹都单独进行压缩。 LZW算法基于一个转换表或字串表，它将输入(shr)字符映象到编码中，使用可变长代码，最大代码长度为12位。LZW算法中的字串表对于每个条纹都不同，并且不必保留给解压缩程序，因为解压缩过程中能自动建立完全相同的字串表。实际上，它是通过查找冗余字符串并将此字符串

22、用较短的符号标记替代的压缩技术。共一百六十九页363.1.3 常用(chn yn)数据压缩方法的基本原理LZW的实现有很多的技巧性，但是算法本身却是非常简单的。 用字符串表中的一个索引代码来替代相应的字符串 在具体(jt)实现时，大多都使用12位的索引代码来代替8位的输入字符。 字符串表有4096个存储空间，正好可以采用12位的代码来定位. 前256个空间用来存储单个字符 (location 0 stores 0, location 1 stores 1, 等). 专门用于清零代码，专门用于信息结束代码当从输入字符串中发现一个新串时，将其添加到字符串表中,其存储空间从258到4095，数据解析

23、器一直解析新输入的字符，只要新生成的字符串位于字符串表中。一旦新的字符产生了一个新的字符串，把这个新的字符串添加到字符串表中，并输出上次已知的字符串的索引代码共一百六十九页373.1.3 常用数据压缩(sh j y su)方法的基本原理LZW压缩算法用单个字符(z f)初始化字符(z f)串表 STRING = 第一个输入字符WHILE 输入流中还有字符CHARACTER = 下一个输入字符IF STRING + CHARACTER 在字符串表中STRING = STRING + CHARACTERELSE 输出 STRING 的索引代码把 STRING + CHARACTER 添加到字符串表

24、中STRING = CHARACTEREND WHILE 输出 string 的索引代码共一百六十九页383.1.3 常用数据压缩(sh j y su)方法的基本原理BABAABAAAENCODEROUTPUTSTRINGTABLEoutput codeRepresentingcodewordstring66B258BA65A259AB258BA260BAA259AB261ABA65A262AA262257AA共一百六十九页393.1.3 常用数据压缩(sh j y su)方法的基本原理LZW解压算法用单个字符(z f)初始化字符(z f)串表OLD_CODE =第一个输入代码输出 OLD_C

25、ODE所代表的字符WHILE 输入流中还有代码NEW_CODE = 下一个输入代码IF NEW_CODE 不在字符串表中STRING = 得到 OLD_CODE所对应的字符（串）STRING = STRING + CHARACTERELSE STRING = 得到 NEW_CODE所对应的字符（串）输出 STRINGCHARACTER = STRING的第一个字符把 OLD_CODE + CHARACTER添加到字符串表中OLD_CODE = NEW_CODEEND WHILE共一百六十九页403.1.3 常用数据压缩(sh j y su)方法的基本原理 OutputOldcodeNewcod

26、eStringcharString TablecodestringB66A6565AA258BABA258258BAB259ABAB259259ABA260BAAA6565AA261ABAAA262262AAA262AAEOL257共一百六十九页413.1.3 常用数据压缩(sh j y su)方法的基本原理(4)霍夫曼编码1952年Huffman提出了对统计独立信源能达到最小平均码长的编码方法，也即最佳码。最佳性可从理论上证明。这种码具有即时性和唯一可译性。原理：对出现概率大的信源符号赋予(fy)短码字，而对于出现概率小的信源符号赋予(fy)长码字。如果码字长度严格按照所对应符号出现概率大小

27、的逆序排列，则编码结果平均码字长度一定小于任何其他排列方式。Morse码：用较少的点和线表示出现频率较大的字母E (.) T (-) Q(-.-)共一百六十九页423.1.3 常用数据压缩(sh j y su)方法的基本原理现仍以一个具体的例子说明它的编码步骤1、初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如表3-03和图3-02所示。2、把概率最小的两个符号组成一个节点，如图3-02中的D和E组成节点P1。3、重复步骤2，得到节点P2、P3和P4，形成一棵“树”，其中的P4称为根节点。4、从根节点P4开始到相应于每个符号的“树叶”，从上到下标上“0”(上枝)或者“1”(下枝)，至

28、于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。5、从根节点P4开始顺着树枝到每个叶子(y zi)分别写出每个符号的代码，如表3-03所示。电信-伍卫国共一百六十九页433.1.3 常用数据压缩(sh j y su)方法的基本原理按照Shannon理论(lln)，这幅图象的熵为H(S) = (15/40) * log2 (40/15) + (7/40) * log2 (40/7) + + (5/40)* log2 (40/5) = 2.196压缩比1.37:1。表3-03共一百六十九页443.1.3 常用数据压缩(sh j y su)方法的基本原

29、理图3-02 霍夫曼编码方法霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。例如，码串中的第1位为0，那末肯定是符号A，因为表示其它符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据(gnj)码簿一个码一个码地依次进行译码。A(15/40)B(7/40)C(7/40)D(6/40)E(5/40)00001111P2(14/40)P1(11/40)P3(25/40)P4(40/40)0100101110111共一百六十九页453.1.3 常用数据压缩(s

30、h j y su)方法的基本原理Huffman编码(bin m)举例共一百六十九页463.1.3 常用数据压缩(sh j y su)方法的基本原理概率分布为2的负数(fsh)幂共一百六十九页473.1.3 常用(chn yn)数据压缩方法的基本原理Huffman-双字长(z chn)编码举例共一百六十九页483.1.3 常用数据压缩(sh j y su)方法的基本原理Huffman编码小结Huffman方法的构造程序是明确的，但构造出来的码字并不是唯一的。为什么？编码码字字长(z chn)参差不齐，硬件实现不方便。码字在存储或传输过程中，如果出现误码时，可能引起误码的连续传播。为什么？变化的码

31、距对不同的信源其编码效率是不同的什么情况下最高？什么情况下最低？解码时必须参照Huffman编码表Huffman编码表的缺省使用：减少了编码时间，便于硬件实现共一百六十九页493.1.3 常用(chn yn)数据压缩方法的基本原理(5)算术编码算术编码把一个信源集合表示(biosh)为实数线上的0到1之间的一个开闭区间。这个集合中的每个元素都要用来缩短这个区间。信源集合的元素越多，所得到的区间间隔就越小，当区间变小时，就需要更多的数位来表示这个区间，这就是区间作为代码的原理。方法：首先假设一个信源的概率模型，然后用这些概率来缩小表示信源集的区间间隔。对二进制编码来说，信源符号只有两个。因此在编

32、码初始阶段可预置一个大概率Pe和一个小概率Qe，然后对被编码比特流符号进行判断。共一百六十九页503.1.3 常用数据压缩(sh j y su)方法的基本原理编码过程描述：初始化子区间为0，1），0的概率：Qe，1的概率：Pe=1-Qe新子区间的起始位置前子区间的起始位置当前符号(fho)的区间左端前子区间长度新子区间的长度 前子区间的长度当前符号的概率最后得到的子区间的长度决定了表示该区域内的某一个数所需的二进制位数。共一百六十九页513.1.3 常用数据压缩(sh j y su)方法的基本原理例1 已知信源 ： ，按以上(yshng)规则，对1011进行算术编码：011/43/4X= 设C

33、表示子区间的起始位置，A表示子区间的长度。Qe=1/4，Pe=3/4，所以符号“0”的区间左端为0，“1”的区间左端为1/4，初始子区间为0，1），初始值为C0，A1。编码过程如下：共一百六十九页523.1.3 常用(chn yn)数据压缩方法的基本原理最后的子区间的起始位置=(85/256)d=0.33203125=(0.01010101)b子区间的长度(chngd)=（27/256 )d =0.10546875（0.00011011 )b 子区间尾=(7/16 )d=0.4375 d=(0.0111 )b编码结果为子区间头尾间的取值，其值为“0.011”,可编码为”011“。解码是编码的逆

34、过程。共一百六十九页533.1.3 常用数据压缩(sh j y su)方法的基本原理例2：假设信源符号为00, 01, 10, 11，这些符号的概率为 0.1, 0.4, 0.2, 0.3 ，根据概率可把间隔(jin g)0, 1)分成4个子间隔：0, 0.1), 0.1, 0.5), 0.5, 0.7), 0.7, 1)，其中x, y)表示半开放间隔，即包含x不包含y。上面的信息可综合在表3-04中。表3-04共一百六十九页543.1.3 常用(chn yn)数据压缩方法的基本原理如果二进制消息序列的输入为：10 00 11 00 10 11 01。编码时首先输入的符号是10，找到它的编码范

35、围是0.5, 0.7)。由于消息中第2个符号00的编码范围是0, 0.1)，因此它的间隔(jin g)就取0.5, 0.7)的第一个十分之一作为新间隔0.5, 0.52)。依此类推，编码第3个符号11时取新间隔为0.514, 0.52)，编码第4个符号00时，取新间隔为0.514, 0.5146)， 。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图3-03所示。共一百六十九页553.1.3 常用数据压缩(sh j y su)方法的基本原理图3-03整个编码(bin m)过程共一百六十九页563.1.3 常用数据压缩(sh j y su)方法的基本原理从0.5143836, 0.5

36、14402中选择一个(y )数作为输出：0.51439共一百六十九页573.1.3 常用(chn yn)数据压缩方法的基本原理译码的消息(xio xi)：10 00 11 00 10 11 01共一百六十九页583.1.3 常用数据压缩(sh j y su)方法的基本原理在算术编码中有几个问题需要注意：由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16-, 32-或者64位的精度，因此这个问题可使用比例缩放的方法来解决。算术编码器对整个消息只产生一个码字，这个码字是在间隔0, 1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。算术编码

37、也是一种(y zhn)对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。共一百六十九页593.1.3 常用数据压缩(sh j y su)方法的基本原理算术编码总结：算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行(jnxng)修改。在编码期间估算信源符号概率的过程叫做建模。需要开发动态算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压

38、缩效率的关键。共一百六十九页603.1.3 常用(chn yn)数据压缩方法的基本原理-有损压缩预测编码是数据压缩理论的一个重要分支预测编码是指利用前面的一个或多个信号对下一个信号进行预测，然后对实际值和预测值的差进行编码。DPCM与ADPCM是两种典型的预测编码。线性预测、非线性预测理论基础：现代统计学和控制论目标：减少数据在时间和空间上的相关性应用：时间序列数据，如语音的分析与合成图像的编码与解码关键技术：预测器的设计(shj)-线性预测函数共一百六十九页613.1.3 常用(chn yn)数据压缩方法的基本原理差分脉冲编码调制(tiozh)DPCM（Differential Pulse

39、Code Modulation）原理 预测器 量化器编码器解码器 预测器信道接收端输出XNXNeNXNeNeNXN+输入XN发送端+-共一百六十九页623.1.3 常用(chn yn)数据压缩方法的基本原理符号说明：XN ：为采样(ci yn)的图像或声音数据XN ：是XN的预测值eN：是实际值与预测值的差值（ XN- XN ）eN ：是eN的量化值XN :是引入了量化误差的XN 。共一百六十九页633.1.3 常用(chn yn)数据压缩方法的基本原理例子：假设预测器的预测值为前一个样值（即预测器为单位延迟），量化器不进行量化，系统(xtng)的输入为：0、1、2、1、1、2、3、3、4、4

40、、 XN ： 0、1、2、1、1、2、3、3、4、4 XN ： 0、0、1、2、1、1、2、3、3、4 eN ： 0、1、1、-1、0、1、1、0、1、 0 量化器预测器输入输出+-XNeNXNeNXN共一百六十九页643.1.3 常用(chn yn)数据压缩方法的基本原理预测器的设计：预测器通常设计成用前面(qin mian)几个样值来预测新样值，而不是利用整个数据信源模型，这是因为模型太复杂，且是时变的，在大多数情况下预测几乎不能够实现。科尔莫戈罗夫（1941年）、维纳（1942年）进行了关于线性预测的开创性工作。最小均方预测误差为最优预测，即：通常采用的误差函数是均方误差（mse）mse

41、=E（S0 S0）2 E：数学期望，S0：实际值，S0：预测值。DPCM的改进ADPCM共一百六十九页653.1.3 常用数据压缩(sh j y su)方法的基本原理预测器的设计（续）：若线性预测器用前面的样值s1、s2、 、sn来预测S0，则预测值为：S0 = a1s1 + a2s2 + + ansn （3.1）令E0 = S0 - S0S0的最佳估计值是能使平方误差(wch)E0的期望值最小的S0。为求出这一最小值，需计算偏导数，并令偏导数为零，并由协方差的定义可等到一组联立方程。预测系数依赖与原始数据的统计特性，这对实际使用是不方便的。共一百六十九页663.1.3 常用数据压缩(sh j

42、 y su)方法的基本原理 预测器的设计（续）：为了简化预测器，使DPCM系统能做到实时压缩，在实际中常常用固定的预测参数来代替最佳系数。如JPEG：选用前一样值作为(zuwi)下一样值的预测值。图像处理中采用四点预测：a1=0.702，a2=-0.200，a3=0.437，a4=0.061a1=0.75，a2=-0.5，a3=0.5，a4=0.25(日本人)考虑到硬件实现方便、人的主观因素共一百六十九页673.1.3 常用数据压缩(sh j y su)方法的基本原理ADPCM ：进一步改善量化性能或压缩数据率的方法分类：线性自适应预测、非线性自适应预测自适应量化根据信号分布不均匀的特点，系统

43、具有随输入信号的变化而改变量化区间大小以保持输入量化器的信号基本均匀的能力。自适应预测预测参数(cnsh)仍采用固定的；但此时有多组预测参数(cnsh)可供选择。编码时具体采用哪组预测参数(cnsh)根据信源的特征来自适应的确定。通常将信源数据分区间编码，编码时自动地选择一组预测参数，使该区间实际值与预测值的均方误差最小。共一百六十九页683.1.3 常用数据压缩(sh j y su)方法的基本原理DPCM 和ADPCM通常把样值压缩到34比特，比PCM用8比特或16比特可减少(jinsho)一半以上空间。MS ADPCM预测系数表共一百六十九页693.1.3 常用(chn yn)数据压缩方法

44、的基本原理变换编码定义：是指先对信号进行某种函数变换(binhun)，从一种信号（空间）变换(binhun)到另一种信号（空间），然后对变换(binhun)后的信号进行编码。例如：将时域信号变换到频域，因为声音、图像大部分信号都是低频信号，在频域中，信号的能量集中，再进行采样、编码可以进一步压缩数据。如傅氏变换：将时间函数变换成频率函数共一百六十九页703.1.3 常用(chn yn)数据压缩方法的基本原理变换编码的原理框图(kungt)：数据压缩三步骤：变换、变换域采样、量化采样量化编码变换解码器反变换信道或存储输入输出-GAUA填零GU共一百六十九页713.1.3 常用(chn yn)数据

45、压缩方法的基本原理离散(lsn)变换：可以用矩阵表示。设信源序列为一个n行k列矩阵X（例如图像扫描结果）；假设采用一维变换，变换后输出序列为Y；变换矩阵为T。则有：Y = TX （信源端）如果取正交变换，则有：X = T-1Y （接收端）T：的寻找，协方差矩阵！共一百六十九页723.1.3 常用(chn yn)数据压缩方法的基本原理最佳的正交变换：当经过正交变换后的协方差矩阵为一对角矩阵，且具有最小均方误差时，该变换称最佳变换，也称Karhunen-Loeve变换。变换编码的关键在于：在已知的条件下，根据它的协方差矩阵去寻找(xnzho)一种正交变换，使变换后的协方差矩阵满足或接近为一对角矩阵

46、。K-L（ Karhunen-Loeve） 变换是最佳变换，在数据压缩技术中占有重要的地位。采用这种变换，对图像信号而言，变换后2b/样值的质量可与7b/样值的质量相比拟。变换矩阵由信源特征确定，不是恒定形式。计算量大、实用性不太高共一百六十九页733.1.3 常用数据压缩(sh j y su)方法的基本原理次最佳的正交变换：DFT变换：变换后的协方差矩阵接近对角矩阵。对不同信源有固定的正交变换矩阵。简便、易于(yy)实现运算次数太多，为了加快速度可使用快速傅立叶变换（FFT），但它需要复数运算。所以使用不方便，速度不理想。DCT：是DFT取实部，有快速算法，对于平稳过度的信源来说，DCT的性

47、能十分接近KLT，所以DCT在图像压缩中得到广泛应用共一百六十九页743.1.3 常用数据压缩(sh j y su)方法的基本原理 分析合成编码通过对原始数据的分析，将其分解为一系列更适合于表示的基元或者从中提取出更有本质意义的参数，编码仅对这些基本单元或者特征参数进行，而解码时则借助于一定的规则或者模型，按照一定的算法将这些基元或者参数再综合成原始数据的一个逼近。(1)矢量(shling)量化(2)小波变换编码(3)分形图像编码(4)子带编码共一百六十九页753.1.3 常用数据压缩(sh j y su)方法的基本原理(1)矢量量化量化编码按照一次量化的码元个数，可分为标量量化和矢量量化两种

48、。对数字化后的数据或PCM数据（样本值）一个一个地进行量化，称为标量量化。标量量化中可在随机变量X出现概率比较高的间隔内，选择较小的判决间隔，而在其他区域内选择较大的间隔，这样可以以较小的量化均方误差进行量化。将这些数据分组，每组K维矢量，再以矢量为单元逐个进行量化，称其为矢量量化。基于(jy)语义编码，其基本思想是采用非线性量化器，即对空间频率及能量分布较大的系数分配较多比特数；反之分配较少的比特数，从而达到压缩的目的。 共一百六十九页763.1.3 常用(chn yn)数据压缩方法的基本原理(2)小波变换编码小波变换是一个线性变换，能够将一个信号分解成对空间和时间、频率的独立贡献，同时又不

49、失原信号所包含的信息。经过小波变换后的图像能量很集中，便于对不同的分量作不同的处理，达到较高的压缩比。(3)分形图像编码分形编码是一种模型编码，它利用模型的方法，对需要传输的图像进行参数估测。(4)子带编码利用带通滤波器组把信号频带分割成若干子频带，然后(rnhu)分别处理。共一百六十九页773.1.4音频压缩编码(bin m)的基本方法通常把已有的话音编译码器分成三种类型：波形编译码器(waveform codecs)，音源编译码器(source codecs)和混合编译码器(hybrid codecs)。一般来说：波形编译码器的话音质量高，但数据率也很高；音源编译码器的数据率很低，产生的合

50、成话音的音质有待(yudi)提高；混合编译码器使用音源编译码技术和波形编译码技术，数据率和音质介于它们之间。共一百六十九页78图 三种(sn zhn)编译码器的话音质量和数据率的关系共一百六十九页793.1.4音频压缩编码的基本(jbn)方法无失真压缩音频压缩方法有失真压缩Huffman编码行程编码波形编码参数编码混合编码全频带编码PCMDPCMADPCM子带编码 自适应变换编码ATC 心理学模型矢量量化线性预测LPC矢量和激励线性预测VSELP多脉冲线性预测MP-LPC码本激励线性预测CELP共一百六十九页803.1.4音频(ynpn)压缩编码的基本方法波形编译码波形编译码的想法是，不利用生

51、成话音信号的任何知识而企图产生一种重构信号，它的波形与原始话音波形尽可能地一致。这种编译码器的复杂程度比较低，数据速率在16 kbps以上，质量相当(xingdng)高。低于这个数据速率时，音质急剧下降。共一百六十九页813.1.4音频压缩编码的基本(jbn)方法声音数字化有两个(lin )步骤：第一步是采样，就是每隔一段时间间隔读一次声音的幅度；第二步是量化，就是把采样得到的声音信号幅度转换成数字值。量化有好几种方法，但可归纳成两类：一类称为均匀量化，另一类称为非均匀量化。采用的量化方法不同，量化后的数据量也就不同。因此，可以说量化也是一种压缩数据的方法。共一百六十九页823.1.4音频(y

52、npn)压缩编码的基本方法均匀量化如果采用相等的量化间隔对采样(ci yn)得到的信号作量化，那么这种量化称为均匀量化。均匀量化就是采用相同的“等分尺”来度量采样得到的幅度，也称为线性量化量化后的样本值Y和原始值X的差E=Y-X称为量化误差或量化噪声。共一百六十九页833.1.4音频压缩编码的基本(jbn)方法非均匀量化对输入信号进行(jnxng)量化时，大的输入信号采用大的量化间隔，小的输入信号采用小的量化间隔。这样就可以在满足精度要求的情况下用较少的位数来表示。声音数据还原时，采用相同的规则。共一百六十九页843.1.4音频压缩编码的基本(jbn)方法子带编码SBC(subband cod

53、ing) ：首先使用一组带通滤波器BPF(band-pass filter)把输入音频信号的频带分成若干个连续的频段，每个频段称为子带。对每个子带中的音频信号采用单独的编码方案编码。在信道上传送时，将每个子带的代码复合起来。在接收端译码时，将每个子带的代码单独译码，然后(rnhu)把它们组合起来，还原成原来的音频信号。共一百六十九页853.1.4音频压缩编码(bin m)的基本方法采用对每个子带分别编码的好处有：第一，对每个子带信号分别进行自适应控制，量化阶的大小(quantization step)可以按照每个子带的能量电平加以调节。具有较高能量电平的子带用大的量化阶去量化，以减少总的量化噪

54、声。第二，可根据每个子带信号在感觉上的重要性，对每个子带分配不同的比特数，用来(yn li)表示每个样本值。例如，在低频子带中，为了保护音调和共振峰的结构，就要求用较小的量化阶、较多的量化级数，即分配较多的比特数来表示样本值。而话音中的摩擦音和类似噪声的声音，通常出现在高频子带中，对它分配较少的比特数。共一百六十九页863.1.4音频压缩编码(bin m)的基本方法音源编译码的思想是：企图从话音(huyn)波形信号中提取生成话音的参数，使用这些参数通过话音生成模型重构出话音。针对话音的音源编译码器叫做声码器(vocoder)。在话音生成模型中，声道被等效成一个时变滤波器(time-varyin

55、g filter)，它由白噪声无声话音段激励，或者由脉冲串有声话音段激励。因此需要传送给解码器的信息就是滤波器的规格、发声或者不发声的标志和有声话音的音节周期，并且每隔1020 ms更新一次。这种声码器的数据率在2.4 kbps左右，产生的语音虽然可以听懂，但其质量远远低于自然话音。增加数据率对提高合成话音的质量无济于事，这是因为受到话音生成模型的限制。尽管它的音质比较低，但它的保密性能好，因此这种编译码器一直用在军事上。共一百六十九页873.1.4音频压缩编码(bin m)的基本方法线性预测编码LPC(linear predictive coding)是一种非常重要的编码方法。从原理上讲，L

56、PC是通过分析话音波形来产生声道激励和转移函数的参数，对声音波形的编码实际就转化为对这些参数的编码，这就使声音的数据量大大减少。在接收端使用(shyng)LPC分析得到的参数，通过话音合成器重构话音。合成器实际上是一个离散的随时间变化的时变线性滤波器，它代表人的话音生成系统模型。时变线性滤波器既当作预测器使用，又当作合成器使用。分析话音波形时，主要是当作预测器使用，合成话音时当作话音生成模型使用。随着话音波形的变化，周期性地使模型的参数和激励条件适合新的要求。共一百六十九页883.1.4音频压缩(y su)编码的基本方法线性预测器是使用过去(guq)的P个样本值来预测当前时刻的采样值x(n)。

57、预测值可以用过去P个样本值的线性组合来表示：线性预测误差为在给定的时间范围里，如n0，n1，使e(n)的平方和即e(n)2为最小，这样可使预测得到的样本值更精确。通过求解偏微分方程，可找到系数ai的值。共一百六十九页89共一百六十九页90共一百六十九页91共一百六十九页923.1.4音频压缩编码(bin m)的基本方法混合编译码企图填补波形编译码和音源编译码之间的间隔。波形编译码器虽然可提供(tgng)高质量的话音，但数据率低于16 kbps的情况下，在技术上还没有很好地解决音质的问题；声码器的数据率虽然可降到2.4 kbps甚至更低，但它的音质根本不能与自然话音相提并论。为了得到音质高而数据

58、率又低的编译码器，历史上出现过很多形式的混合编译码器，但最成功并且普遍使用的编译码器是时域合成-分析器。共一百六十九页933.1.4音频压缩(y su)编码的基本方法思想：这种编译码器使用的声道线性预测滤波器模型与线性预测编码LPC (linear predictive coding)使用的模型相同，不使用两个状态(有声/无声)的模型来寻找滤波器的输入激励信号，而是企图寻找这样一种激励信号，使用这种信号激励产生的波形尽可能接近于原始话音(huyn)的波形。AbS编译码器由Atal和Remde在1982年提出，并命名为多脉冲激励MPE(multi-pulse excited)编译码器，在此基础上

59、随后出现的是等间隔脉冲激励RPE(regular-pulse excited)编译码器、码激励线性预测CELP(code excited linear predictive)编译码器和混合激励线性预测MELP(mixed excitation linear prediction)等编译码器。共一百六十九页94图 Abs编码器（上）和译码器（下）共一百六十九页953.1.4音频压缩编码(bin m)的基本方法AbS编译码器把输入话音信号分成(fn chn)许多帧(frames)，一般来说，每帧的长度为20 ms。合成滤波器的参数按帧计算，然后确定滤波器的激励参数。AbS编码器是一个负反馈系统，通

60、过调节激励信号u(n)可使话音输入信号s(n)与重构的话音信号之差为最小，也就是重构的话音与实际的话音最接近。这就是说，编码器通过“合成”许多不同的近似值来“分析”输入话音信号，这也是“合成-分析编码器”名称的来由。MPE，RPE和CELP编译码器之间的差别在于所使用的激励信号的表示方法。共一百六十九页963.1.4音频压缩(y su)编码的基本方法在MPE中，对每帧话音所用的激励信号u(n)是固定数目的脉冲(michng)，在一帧中脉冲(michng)的位置和幅度必须由编码器来确定，这在理论上可以找到很好的值，但实际上不太可能，因为计算太复杂。因此在实际上就使用次佳方法，一般来说，每5 ms