ch6数据压缩.ppt

计算机科学与技术系计算机科学与技术系董华松董华松多媒体技术基础多媒体技术基础第五章：第五章：数据压缩数据压缩主要内容主要内容数据压缩概述数据压缩概述经典数据压缩理论经典数据压缩理论香农范诺与霍夫曼编码香农范诺与霍夫曼编码算术编码算术编码行程编码行程编码词典编码词典编码压缩的必要性压缩的必要性音频、视频的数据量很大，如果不进行处理，计算机系统几乎无法对它进行存取和交换。例如，一幅具有中等分辨率（640480）的真彩色图像（24b/像素），它的数据量约为7.37Mb/帧，一个100MB（Byte）的硬盘只能存放约100帧图像。若要达到每秒25帧的全动态显示要求，每秒所需的数据量为184Mb，而且要求系统的数据传输率必须达到184Mb/s。对于声音也是如此，若采用16b样值的PCM编码，采样速率选为44.1kHZ，则双声道立体声声音每秒将有176KB的数据量。视频、视频、图像、声音有很大的压缩潜力图像、声音有很大的压缩潜力p信息论认为：若信源编码的熵大于信源的实际熵，该信源中一定存在冗余度。p原始信源的数据存在着很多冗余度：空间冗余、时间冗余、视觉冗余、听觉冗余等。什么是数据压缩什么是数据压缩 数据压缩就是在一定的精度损失条件下，以最少的数码表示信源所发出的信号信源编码信道编码信道信道译码信源译码信源信宿分钟数字音频信号需要的存储空间1 1分钟数字视频信号需要的存储空间1 1时间域压缩迅速传输媒体信源频率域压缩并行开通更多业务空间域压缩降低存储费用能量域压缩降低发射功率数据压缩的好处数据压缩的好处l压缩比要大l恢复后的失真小l压缩算法要简单、速度快l压缩能否用硬件实现数据压缩技术实现的衡量标准数据压缩技术实现的衡量标准数据压缩技术的性能指标l压缩比压缩比l图象质量图象质量l压缩和解压的速度压缩和解压的速度 另外也必须考虑每个压缩算法所需的硬件和软件。1压缩比压缩比u压缩性能常常用压缩比定义（输入数据和输出数据比）例：512480，24bit/pixel(bmp)输出15000byte输入737280byte压缩比737280/15000492图象质量图象质量u取决于压缩方法：有损压缩的失真情况很难量化，只能对测试的图象进行估计u模拟图象质量的指标：信噪比、分辨率、颜色深度，但必须在观察了实际图象以后。3压缩解压速度压缩解压速度p在许多应用中，压缩和解压可能不同时用，在不同的位置不同的系统中。所以，压缩、解压速度分别估计。p静态图象中，压缩速度没有解压速度严格；动态图象中，压缩、解压速度都有要求，因为需实时地从摄像机或VCR中抓取动态视频。4硬软件系统硬软件系统有些压缩解压工作可用软件实现。设计系统时必须充分考虑：算法复杂压缩解压过程长算法简单压缩效果差目前有些特殊硬件可用于加速压缩/解压。硬接线系统速度快，但各种选择在初始设计时已确定，一般不能更改。因此在设计硬接线压缩/解压系统时必须先将算法标准化。无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。数据压缩技术的分类数据压缩技术的分类经典数据压缩理论经典数据压缩理论信息论中的信源编码理论解决的主要问题：（1）数据压缩的理论极限（2）数据压缩的基本途径数据冗余数据冗余的的类型类型u一一幅幅图图象象中中同同一一种种颜颜色色不不止止一一个个象象素素点点，若若相相邻邻的的象象素素点点的的值值相相同同，象象素素点点间间（水水平平、垂垂直直）有有冗冗余余。（空间冗余）（空间冗余）u当当图图象象的的一一部部分分包包含含占占主主要要地地位位的的垂垂直直的的源源对对象象时时，相相邻邻线间存在冗余。线间存在冗余。（空间冗余）（空间冗余）u若若 图图 象象 稳稳 定定 或或 只只 有有 轻轻 微微 的的 改改 变变，运运 动动 序序 列列 帧帧 间间 存存 在在 冗冗 余余。（时间冗余）（时间冗余）数据冗余数据冗余的的类型类型l空间冗余：在同一幅图像中，规则物体和规则背景的表空间冗余：在同一幅图像中，规则物体和规则背景的表面物理特性具有相关性，这些相关性的光成像结果在数面物理特性具有相关性，这些相关性的光成像结果在数字化图像中就表现为数据冗余字化图像中就表现为数据冗余。l时间冗余：时间冗余反映在图像序列中就是相邻帧图像时间冗余：时间冗余反映在图像序列中就是相邻帧图像之间有较大的相关性，一帧图像中的某物体或场景可以之间有较大的相关性，一帧图像中的某物体或场景可以由其它帧图像中的物体或场景重构出来。音频的前后样由其它帧图像中的物体或场景重构出来。音频的前后样值之间也同样有时间冗余。值之间也同样有时间冗余。数据冗余数据冗余的的类型类型l信息熵冗余：信源编码时，当分配给第信息熵冗余：信源编码时，当分配给第i个码元类的比特个码元类的比特数数b（yi）=-logpi，才能使编码后单位数据量等于其信才能使编码后单位数据量等于其信源熵，即达到其压缩极限。但实际中各码元类的先验概源熵，即达到其压缩极限。但实际中各码元类的先验概率很难预知，比特分配不能达到最佳。实际单位数据量率很难预知，比特分配不能达到最佳。实际单位数据量dH（S），），即存在信息冗余熵。即存在信息冗余熵。l视觉冗余：人眼对于图像场的注意是非均匀的，人眼并视觉冗余：人眼对于图像场的注意是非均匀的，人眼并不能察觉图像场的所有变化。事实上人类视觉的一般分不能察觉图像场的所有变化。事实上人类视觉的一般分辨能力为辨能力为26灰度等级，而一般图像的量化采用的是灰度等级，而一般图像的量化采用的是28灰灰度等级，即存在着视觉冗余。度等级，即存在着视觉冗余。数据冗余数据冗余的的类型类型l听觉冗余：人耳对不同频率的声音的敏感性是不听觉冗余：人耳对不同频率的声音的敏感性是不同的，并不能察觉所有频率的变化，对某些频率同的，并不能察觉所有频率的变化，对某些频率不必特别关注，因此存在听觉冗余。不必特别关注，因此存在听觉冗余。l其它冗余：包括结构冗余、知识冗余等其它冗余：包括结构冗余、知识冗余等。数据冗余数据冗余的的类型类型 从信息语义角度分为从信息语义角度分为“熵熵(平均信息量平均信息量)编码编码”和和“源编码源编码”两种：两种：熵熵(平均信息量平均信息量)编码编码(Entropy Coding)熵编码是一种泛指那些不考虑被压缩信息的熵编码是一种泛指那些不考虑被压缩信息的性质的编码和压缩技术。它是基于平均信息量的性质的编码和压缩技术。它是基于平均信息量的技术把所有的数据当作比特序列，而不根据压缩技术把所有的数据当作比特序列，而不根据压缩信息的类型优化压缩。也就是说，平均信息量编信息的类型优化压缩。也就是说，平均信息量编码忽略被压缩信息的语义内容。码忽略被压缩信息的语义内容。熵编码分为：重复序列消除编码熵编码分为：重复序列消除编码(含：消零、含：消零、行程编码行程编码)、统计编码等。、统计编码等。数据冗余数据冗余的的类型类型源编码(SourceCoding)源编码的冗余压缩取决于初始信号的类型、前后的相关性、信号的语义内容等。源编码比严格的平均信息量编码的压缩率更高。当然压缩的程度主要取决于数据的语义内容，比起平均信息量编码，它的压缩比更大。源编码主要分为：预测编码、变换编码、向量量化等。数据冗余数据冗余的类型与压缩方法分类的类型与压缩方法分类Source CodingPrediction:DPCM and DMTransformation:FFT、DCTLayered:Sub-band、Sub-sampling and Bit PositionVector QuantizationHybrid CodingJPEG、MPEG、H.261、DVI、Intel-IndeoEntropy CodingRun Length CodingStatistical CodingHuffmanArithmetic熵（熵（Entropy）事件集合（样本空间）X中每个事件的自信息量I(x)是定义在这个样本空间上的一个随机变量，所以我们要研究它的统计特性。其数学期望为：H(X)表明了集合X中随机事件的平均不确定性，或者说平均信息量。称H(X)为一阶信息熵或者简称为熵(Entropy)熵（熵（Entropy）在符号出现之前，熵表示符号集中的符号出现的平均不确定性；在符号出现之后，熵代表接收一个符号所获得的平均信息量。根据直觉，信源编码的数据输出速率（平均码长）与信源熵之间应该有某种对应关系。平均码长与熵平均码长与熵如果采用单字符二进制编码方式，设字符aj的编码长度为Lj，则信源字母表的平均码长为：根据前面对二进制信源的分析，有：在Lj log2pj时，平均码长取得极小值H(X)例例 有一幅有一幅4040个象素组成的灰度图像，灰度共有个象素组成的灰度图像，灰度共有5 5级，分别级，分别用符号用符号A A、B B、C C、D D和和E E表示，表示，4040个象素中出现灰度个象素中出现灰度A A的象素数的象素数有有1515个，出现灰度个，出现灰度B B的象素数有的象素数有7 7个，出现灰度个，出现灰度C C的象素数有的象素数有7 7个等等，如表个等等，如表4-014-01所示。如果用所示。如果用3 3个位表示个位表示5 5个等级的灰度值，个等级的灰度值，也就是每个象素用也就是每个象素用3 3位表示，编码这幅图像总共需要位表示，编码这幅图像总共需要120120位。位。符 号 出现的次数157765按照仙农理论，这幅图像的熵为H(S)=(15/40)(40/15)+(7/40)(40/7)+(5/40)(40/5)=2.196这就是说每个符号用2.196位表示，40个象素需用87.84位。熵编码熵编码熵编码包括香农范诺编码、霍夫曼编码和算术编码，其宗旨在于找到一种编码使得平均码长到达熵极限，基本思想就是对出现概率较大的符号取较短的码长，而对出现概率较小的符号取较大的码长。霍夫曼编码霍夫曼编码初始化，根据符号概率的大小按由大到小顺序对符号进行排序，初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如表如表4-03和图和图4-02所示。所示。把概率最小的两个符号组成一个节点，如图把概率最小的两个符号组成一个节点，如图4-02中的中的D和和E组成组成节点节点P1。重复步骤重复步骤2，得到节点，得到节点P2、P3和和P4，形成一棵，形成一棵“树树”，其中的，其中的P4称为根节点。称为根节点。从根节点从根节点P4开始到相应于每个符号的开始到相应于每个符号的“树叶树叶”，从上到下标上，从上到下标上“0”(上枝上枝)或者或者“1”(下枝下枝)，至于哪个为，至于哪个为“1”哪个为哪个为“0”则则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。度是相同的。从根节点从根节点P4开始顺着树枝到每个叶子分别写出每个符号的代码，开始顺着树枝到每个叶子分别写出每个符号的代码，如表如表4-03所示。所示。按照仙农理论，这幅图像的熵为按照仙农理论，这幅图像的熵为符号出现的次数log2(1/pi)分配的代码需要的位数A15(0.3846)1.38015B7(0.1795)2.4810021C6(0.1538)2.7010118D6(0.1538)2.7011018E5(0.1282)2.9611115A(0.12),E(0.42),I(0.09),O(0.30),U(0.07),A-100E-0I-1011O-11U-1010霍夫曼编码的局限性霍夫曼编码的局限性利用霍夫曼编码，每个符号的编码长度只能为整数，所以如果源符号集的概率分布不是2负n次方的形式，则无法达到熵极限。输入符号数受限于可实现的码表尺寸译码复杂需要实现知道输入符号集的概率分布没有错误保护功能香农范诺编码香农范诺编码香农范诺编码与Huffman编码相反，采用从上到下的方法。具体步骤为：（1）首先将编码字符集中的字符按照出现频度和概率进行排序。（2）用递归的方法分成两部分，使两个部分的概率和接近于相等。直至不可再分，即每一个叶子对应一个字符。（3）编码。香农范诺编码举例香农范诺编码举例A BC D EABCD EDE符号ABCDE次数15776501010011算术编码算术编码Huffman编码的局限性：Huffman编码使用整数个二进制位对符号进行编码，这种方法在许多情况下无法得到最优的压缩效果。假设某个字符的出现概率为80%，该字符事实上只需要-log2(0.8)=0.322位编码，但Huffman编码一定会为其分配一位0或一位1的编码。可以想象，整个信息的80%在压缩后都几乎相当于理想长度的3倍左右。，算术编码算术编码基本思想：算术编码不是将单个信源符号映射成一个码字，而是把真个信源表示为实数线上的0到1之间的一个区间，其长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。消息序列中的每个元素都要用来缩短这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。采用算术编码每个符号的平均编码长度可以为小数。算术编码举例（一）算术编码举例（一）符号符号00011011概率概率0.10.40.20.3初始区间初始区间0,0.1)0.1,0.5)0.5,0.7)0.7,1)算术编码的具体实现算术编码的具体实现因为实际只能用有限长的寄存器，这就要求将已编码的高位码字及时输出，但又不能输出过早，以免后续运算还要调整已输出的码位。算术编码每次递推都要做乘法，所以效率比较低。二进制算术编码是一种实用的编码算法，用移位代替了乘法，使效率大大提高。自适应算术编码可以在编码过程中根据符号出现的频繁程度动态的修改分布概率，这样可以避免在编码之前必须精确求出信源概率的难题。自适应算术编码举例自适应算术编码举例cba1.00000.66670.33330.00000.66670.58340.41670.33330.66670.63340.60010.58340.66670.65010.63900.6334c1/31/42/53/6b1/32/42/52/6a1/31/41/51/6输入序列为：输入序列为：bcc.行程编码（行程编码（RLE）行程编码（Run-LengthEncoding）：它通过将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。例如：RTTTTTTTTABBCDG被转换为：R#8TABBCDG，其中“”作为转义字符，表明其后所跟的字符表示长度。用RLE编码方法得到的代码为：80315084180。代码中用。代码中用黑体表示的数字是行程长度，黑体字后面的数字代表象素黑体表示的数字是行程长度，黑体字后面的数字代表象素的颜色值。例如黑体字的颜色值。例如黑体字50代表有连续代表有连续50个象素具有相同个象素具有相同的颜色值，它的颜色值是的颜色值，它的颜色值是8。词典编码词典编码词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。第一类词典编码第一类词典编码第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。LZ77算法算法LZ77算法又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。LZ77编码的基本流程编码的基本流程1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤2，否则进行步骤3。2、输出三元符号组(off,len,c)。其中off为窗口中匹配字符串相对窗口边界的偏移，len为可匹配的长度，c为下一个字符，即不匹配的第一个字符。然后将窗口向后滑动len+1个字符，继续步骤1。3、输出三元符号组(0,0,c)。其中c为下一个字符。然后将窗口向后滑动1个字符，继续步骤1。LZ77算法算法LZ77编码举例编码举例AABCBBABCA步骤位置匹配串输出110,0,A22A1,1,B340,0,C45B2,1,B57ABC5,3,ALZSS算法算法LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。LZSS算法的思想是如果匹配串的长度比指针本身的长度长就输出指针（匹配串长度大于等于MIN_LENGTH），否则就输出真实字符。另外要输出额外的标志位区分是指针还是字符。LZSS编码的基本流程编码的基本流程1、从当前压缩位置开始，考察未编码的字符，并试图在滑动窗口中找出最长的匹配字符串，如果匹配串长度len大于等于最小匹配串长度（len=MIN_LENGTH），则进行步骤2，否则进行步骤3。2、输出指针二元组(off,len)。其中off为窗口中匹配字符串相对窗口边界的偏移，len为匹配串的长度，然后将窗口向后滑动len个字符，继续步骤1。3、输出当前字符c，然后将窗口向后滑动1个字符，继续步骤1。LZSS编码举例编码举例位置1234567891011字符AABBCBBAABC步骤位置匹配串输出11A22AA33B44BB55C66BB（3，2）78AAB（7，3）811CC输入数据流：输入数据流：编码过程编码过程MIN_LEN=2LZSS算法算法在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip,GZip,ARJ,LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。第二类词典编码第二类词典编码第二类算法的想法是企图从输入的数据中创建一个“短语词典(dictionaryofthephrases)”，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。LZ78算法算法LZ78的编码思想是不断地从字符流中提取新的字符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Codeword)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Codeword)去替换字符流(Charstream)，生成码字流(Codestream)，从而达到压缩数据的目的。LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的字符串(String)用字符C进行扩展生成新的字符串(String)，然后添加到词典中。LZ78编码算法编码算法步骤1：将词典和当前前缀P都初始化为空。步骤2：当前字符C:=字符流中的下一个字符。步骤3：判断PC是否在词典中（1）如果“是”，则用C扩展P，即让P:=PC，返回到步骤2。（2）如果“否”，则输出与当前前缀P相对应的码字W和当前字符C，即（W，C）；将PC添加到词典中；令P:=空值，并返回到步骤2LZ78编码举例编码举例位置123456789字符ABBCBCABA步骤位置词典输出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)输入数据流：输入数据流：编码过程：编码过程：LZW算法算法 J.Ziv和A.Lempel在1978年首次发表了介绍第二类词典编码算法的文章。在他们的研究基础上，Terry A.Welch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW(Lempel-Ziv Walch)压缩编码。在编码原理上，LZW与LZ78相比有如下差别：LZW只输出代表词典中的字符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符。即在编码匹配时，至少可以在词典中找到长度为1的匹配串。LZW编码是围绕称为词典的转换表来完成的。LZW算法的词典算法的词典 LZW编码器(软件编码器或硬件编码器)就是通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流(Char stream)，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流(Code stream)，码字代表单个字符或多个字符组成的字符串(String)。LZW编码算法编码算法步骤步骤1：将词典初始化为包含所有可能的单字符，当前前：将词典初始化为包含所有可能的单字符，当前前缀缀P初始化为空。初始化为空。步骤步骤2：当前字符：当前字符C:=字符流中的下一个字符。字符流中的下一个字符。步骤步骤3：判断：判断PC是否在词典中是否在词典中 （1）如果）如果“是是”，则用，则用C扩展扩展P，即让，即让P:=PC，返回，返回到步骤到步骤2。（2）如果）如果“否否”，则，则 输出与当前前缀输出与当前前缀P相对应的码字相对应的码字W；将将PC添加到词典中；添加到词典中；令令P:=C，并返回到步骤，并返回到步骤2LZW编码举例编码举例位置123456789字符ABBABABAC步骤位置码字词典输出1A2B3C114AB1225BB2336BA2447ABA4558ABAC763输入数据流：输入数据流：LZW算法算法 LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司Unisys(优利系统公司)，除了商业软件生产公司之外，可以免费使用LZW算法。预测编码预测编码(Prediction Coding)预测编码是指利用前面的一个或多个信号对预测编码是指利用前面的一个或多个信号对下一个信号进行预测，然后对实际值和预测值的下一个信号进行预测，然后对实际值和预测值的差进行编码。差进行编码。DPCM与与ADPCM是两种典型的预测是两种典型的预测编码。编码。(1)差分脉码调制差分脉码调制(DPCM)PCM(Pulse Code Modulation)，原始的模原始的模拟信号经过时间采样，然后对每一样值进行量化，拟信号经过时间采样，然后对每一样值进行量化，作为数字信号传输。作为数字信号传输。DPCM不对每一样值都进行量化，而是预测不对每一样值都进行量化，而是预测下一样值，并量化实际值和预测值之间的差。下一样值，并量化实际值和预测值之间的差。DPCM是是基基本本的的编编码码方方法法之之一一，在在大大量量的的压压缩缩算算法法中中被被采采用用，比比如如JPEG的的DC分分量量就就是是采采用用DPCM编码的。编码的。举例说明举例说明DPCM编码原理：编码原理：设DPCM系统预测器的预测值为前一个样值，假设输入信号已经量化，差值不再进行量化。若系统的输入为0121123344，则预测值为0012112334，差值为0111011010，差值的范围比输入样值的范围有所减小，可以用较少的位数进行编码。(2)自适应差分脉码调制自适应差分脉码调制(ADPCM)为了进一步改善量化性能或压缩数据率，可采用自适应量化或自适应预测的方法。只要采用了其中的任一种自适应方法，均称为ADPCM。自适应预测预测参数的最佳化依赖于信源的统计特性，要得到最佳的预测参数是一件繁琐的工作，而采用固定的预测参数往往又得不到好的性能。为了既能使性能较佳，又不致于有太大的工作量，可以将上述两种方法折衷考虑，采用自适应预测具体方法是：预测参数仍采用固定的；但此时有多组预测参数可供选择。这些预测参数根据常见的信源特征求得。编码时具体采用哪组预测参数根据信源的特征来自适应的确定。为了自适应的选择最佳参数，通常将信源数据分区间编码，编码时自动地选择一组预测参数，使该区间实际值与预测值的均方误差最小。随着编码区间的不同，预测参数自适应的变化，以达到准最佳预测。例如，Microsoft的ADPCM采用二预测参数，提供7组预测系数，如右表所示。编码时，根据选定的准则(如最小均方误差准则)，每个编码区间自动地选取一组最佳的参数。系数集系数集 系数系数1 1 系数系数2 20 256 01 512 -2562 0 03 192 644 240 05 460 -2086 392 -232 根据信号分布不均匀的特点，系统具有随输入信号的变化而改变量化区间大小,以保持输入给量化器的信号基本均匀的能力，这种能力称为自适应量化。自适应量化自适应量化变换编码变换编码(Transformation Coding)在变换编码时，初始数据要从初始空间或时间域进行数学变换，变换为一个更适于压缩的抽象域。该过程是可逆的；即使用反变换可恢复原始数据。如将时域信号变换到频域，因为声音、图像大部分信号都是低频信号，在频域中信号的能量较集中，再进行采样、编码就可以压缩数据变换本身是可逆的，因而其也是一种无损技术。然而为了取得更满意的结果，某些重要系数的编码位数比其他的要多，某些系数干脆就被忽略了。这样，该过程就成为有损的了。数学家们已经构造了多种数学变换。除了傅里叶变换外，还有余弦、Hadamard、Haar、Karhunen Loeve变换。最实用最常用的数学变换是离散余弦变换(DCT)。典型的变换编码系统框图：典型的变换编码系统框图：信源信源序列序列变换变换变变 换换 域域采采 样样量化量化编码编码存存 储储 或或传传 输输译码译码填零填零反反 变变换换再现再现序列序列变换编码系统压缩数据的三个步骤变换编码系统压缩数据的三个步骤(1)最佳变换（最佳变换（KL变换）变换）数据压缩主要是去除信源的相关性。若考虑到信号存在于无限区间上，而变换区域又是有限的，那么表征相关性的统计特性就是协方差矩阵。当协方差矩阵中除对角线上元素之外的各元素都为零时，就等效于相关性为零。所以，为了有效地进行数据压缩，常常希望变换后的协方差矩阵为一对角矩阵，同时也希望主对角线上各元素随，的增加很快衰减。因此，变换编码的关键在于：在已知的条件下，根据它的协方差矩阵去寻找一种正交变换，使变换后的协方差矩阵满足或接近为一对角矩阵。当经过正交变换后的协方差矩阵为一对角矩阵，且具有最小均方误差时，该变换称最佳变换，也称Karhunen-Loeve变换。可以证明，以矢量信号的协方差矩阵的归一化正交特征向量所构成的正交矩阵，对该矢量信号所作的正交变换能使变换后的协方差矩阵达到对角矩阵。(2)离散余弦变换（离散余弦变换（DCT变换）变换）如果变换后的协方差矩阵接近对角矩阵，该类变换称准最佳变换，典型的有DCT、DFT、WHT、HrT等。其中最常用的变换是离散余弦变换DCT。DCT是从DFT引出的。DFT可以得到近似于最佳变换的性能，但DFT的运算次数太多，且需要复数运算。DCT从DFT中取实部，并可用快速余弦变换算法，因此大大加快了运算。同时其压缩性能十分逼近最佳变换的压缩性能。所以，DCT在图像压缩中得到了广泛的应用。分析合成分析合成 编码编码通过对原始数据的分析，将其分解为一系列更适合于表示的基元或者从中提取出更有本质意义的参数，编码仅对这些基本单元或者特征参数进行，而解码时则借助于一定的规则或者模型，按照一定的算法将这些基元或者参数再综合成原始数据的一个逼近。矢量量化矢量量化量化编码按照一次量化的码元个数，可分为标量量化和矢量量化两种。对数字化后的数据或PCM数据（样本值）一个一个地进行量化，称为标量量化。而将这些数据分组，每组K维矢量，再以矢量为单元逐个进行量化，称其为矢量量化。矢量量化是标量量化的多维扩展。标量量化中可在随机变量X出现概率比较高的间隔内，选择较小的判决间隔，而在其他区域内选择较大的间隔，这样可以以较小的量化均方误差进行量化。矢量量化基于语义编码，其基本思想是采用非线性量化器，即对空间频率及能量分布较大的系数分配较多比特数；反之分配较少的比特数，从而达到压缩的目的。小波变换编码小波变换编码小波变换是一个线性变换，能够将一个信号分解成对空间和时间、频率的独立贡献，同时又不失原信号所包含的信息。经过小波变换后的图像能量很集中，便于对不同的分量作不同的处理，达到较高的压缩比。分形编码分形编码分形编码是一种模型编码，它利用模型的方法，对需要传输的图像进行参数估测。分形的方法是把一幅数字图像，通过一些图像处理技术，如颜色分割、边缘检测、频谱分析、纹理变化分析等等，将原始图像分成一些子图像。子图像可以是简单的物体，也可以是一些复杂的景物。然后在分形集中查找这样的子图像。分形集实际上并不是存储所有可能的子图像，而是存储许多迭代函数，通过迭代函数的反复迭代，恢复出原来的子图像。子带编码利用带通滤波器组把信号频带分割成若干子频带，然后分别处理。通过等效于单边带调幅的调制过程，将各子带搬移到零频率附近以得到低通表示后，再以奈奎斯特速率对各子带输出取样，并对取样值进行通常的数字编码。恢复时，将各子带信号解码并重新调制回其原始位置，再将所有子带输出相加就可得到接近于原始信号的恢复波形。它的复杂度与变换编码差不多，但客观质量高、主观效果好。计算机科学与技术系计算机科学与技术系董华松董华松音频音频音频音频的压缩的压缩的压缩的压缩音频的压缩音频频率范围 低频声音(Infra-sound)：0Hz20Hz 人类听觉频率范围的声音：20Hz20kHz 高频(Ultrasound)：20kHz1GHz 超声波(Hypersound)：1GHz10THz不同音频的带宽 电话语音：200Hz3.4kHz 调幅广播：50Hz7kHz 调频广播：20Hz15kHz 宽带音响:20Hz20kHz音频压缩编码的基本方法无失真压缩无失真压缩音频压缩方法音频压缩方法有失真压缩有失真压缩HuffmanHuffman编码编码行程编码行程编码波形编码波形编码参数编码参数编码混合编码混合编码全频带编码全频带编码PCMPCMDPCMDPCMADPCMADPCM子带编码子带编码 自适应变换编码自适应变换编码ATCATC 心理学模型心理学模型矢量量化矢量量化线性预测线性预测LPCLPC矢矢量量和和激激励励线线性预测性预测VSELPVSELP多多脉脉冲冲线线性性预测预测MP-LPCMP-LPC码码本本激激励励线线性预测性预测CELPCELP电话质量的语音压缩标准ITUTS建议的语音压缩的标准 G.711：采用PCM编码，采样速率为8kHz，量化位数为8bit，对应的比特流速率为64kbit/s。G.721：ITU建议的 G.721将64Kbps的比特流转换为32Kbps的流，它是基于 ADPCM技术。每个数值差分用4位编码，其采样率为8kHz。电话质量的语音压缩标准G.723：G.723是一种以24Kbps运行的基于 ADPCM 的有损耗压缩标准。其音质不如非压缩的 G.711PCM 标准以及基于 SBADPCM 的 G.722标准。G.723.1和G.723.2用于H.324标准。G.728：它的 比特率为16Kbps，带宽限于3.4kHz。其音质比 G.711或 G.722差得多。它基于一种称为低延迟代码激励线性预测(LDCELP)的向量量化技术。电话质量的语音压缩标准CELP是一种常用的语音压缩技术。它用于美国联邦标准1016，可将语音压缩至4.8Kbps。美国联邦标准1015使用 CELP的一个简本，称为线性预测编码(LPC)。LPC一10E标准可以运行于2.4Kbps。采用了一种向量量化方法。声音听起来有点象机器在说话，但4.8Kbps与电话差不多。调幅广播质量的音频压缩标准 调幅广播质量：调幅广播质量：50Hz7kHz，称称“7kHz音频信号音频信号”。G.722：G.722基于子带 ADPCM技术(SBADPCM)，它是将现有的带宽分成两个独立的子带信道分别采用差分脉码调制算法。G.722压缩信号的带宽范围为50Hz到7kHz，而 G.711 仅限于3.4kHz。其比特率为48、56、64Kbps，在标准模式下，采样速率是16KHz，幅度深度为14比特。高保真立体声音频压缩标准 高质量的声音信号频率范围：高质量的声音信号频率范围：50Hz20kHz 目前国际上比较成熟的高质量声音压缩标准为MPEG音频。MPEGl的音频信号在ISO 111723文档中的描述。MPEG音频不是单个一种压缩算法，而是3种音频编码和压缩方案的一个系列。MPEG 声音编码分为：层l、层2、层3。随着层数的增加算法的复杂度也增大。高保真立体声音频压缩标准 所有3层都分级兼容。最复杂的译码器(即在层3工作的译码器)也可对层2或层l的码流进行译码。所有3层都运用同一原理：变换编码和子带编码。v频谱被分为32个子带。v应用快速博里叶变换来表示高频域中的信号。v应用心理声学模式来变换信号以估计刚能引起注意的噪音级。层l、2和3主要在最后一个阶段-即量化阶段的方式上有所区别，但不是唯一的差别。计算机科学与技术系计算机科学与技术系董华松董华松图像图像图像图像和视频的压缩和视频的压缩和视频的压缩和视频的压缩图像图像和视频压缩编码的基本方法和视频压缩编码的基本方法图像和视频压缩方法图像和视频压缩方法无失真压缩无失真压缩有失真压缩有失真压缩HuffmanHuffman编码编码行程编码行程编码算术编码算术编码LZWLZW编码编码预测编码预测编码运动补偿运动补偿变换编码变换编码DCTDCT变换变换小波变换小波变换子带编码子带编码模型编码模型编码分形编码分形编码基于重要性基于重要性滤波滤波子采样子采样矢量量化矢量量化混合编码混合编码JPEGJPEGMPEGMPEGH.261H.261图像图像和视频压缩编码的基本方法和视频压缩编码的基本方法原始的彩色图像，一般由红、绿、蓝三种基色的图像组成（R、G、B）。然而人的视觉系统对彩色色度的感觉和亮度的敏感性是不同的，因此产生了不同的彩色空间表示。H、S、I彩色空间：H为色调、S为饱和度、I表示光的强度或亮度。Y、I、Q方式和Y、U、V方式：这两种表示方式的一个共同点是用其中一个分量Y表示象素的亮度，用其余两个分量表示象素的色度。静止静止图像压缩标准图像压缩标准 静止图像压缩，已有多个国际标准，如ISO制订的JPEG标准（Joint Photographic Experts Group）、JBIG标准（Joint Bilevel Image Group）、ITUT的G3、G4标准等。特别是JPEG标准，适用黑白及彩色照片、彩色传真和印刷图片，可以支持很高的图像分辨率和量化精度。1.JPEG压缩标准压缩标准l 压缩比高，图像质量保真程度好；l算法能适应不同的数字图像参数、大小、图像内容、彩色空间、统计特性等，但不包括二值图像；l用户可以对压缩比、质量效果进行选择；l应该满足硬软件实现的计算需求；l支持多种操作方式。(1)JPEG的无损预测编码算法的无损预测编码算法 无损压缩不使用无损压缩不使用DCTDCT方法，而是采用一个简单的预测器。方法，而