MPEG 教程04.ppt

《MPEG 教程04.ppt》由会员分享，可在线阅读，更多相关《MPEG 教程04.ppt（67页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、MTIMTIXIDIANXIDIAN数据压缩基础数据压缩基础多媒体技术第四讲第四讲1主要内容数据压缩概述经典数据压缩理论香农范诺与霍夫曼编码算术编码行程编码词典编码预测编码变换编码分析综合编码2什么是数据压缩 数据压缩就是在一定的精度损失条件下，以最少的数码表示信源所发出的信号信源编码信道编码信道信道译码信源译码信源信宿3多媒体信源引起了“数据爆炸”如果不进行数据压缩 传输和存储都难以实用化。多媒体数据数据压缩的必要性4分钟数字音频信号需要的存储空间1 15分钟数字视频信号需要的存储空间1 16时间域压缩时间域压缩迅速传输媒体信源迅速传输媒体信源频率域压缩频率域压缩并行开通更多业务并行开通更多

2、业务空间域压缩空间域压缩降低存储费用降低存储费用能量域压缩能量域压缩降低发射功率降低发射功率数据压缩的好处7l压缩比要大压缩比要大l恢复后的失真小恢复后的失真小l压缩算法要简单、速度快压缩算法要简单、速度快l压缩能否用硬件实现压缩能否用硬件实现数据压缩技术实现的衡量标准8 无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。数据压缩

3、技术的分类9经典数据压缩理论信息论中的信源编码理论解决的主要问题：（1）数据压缩的理论极限（2）数据压缩的基本途径10信源信源被抽象为一个随机变量序列（随机过程）。如果信源输出的随机变量取值于某一连续区间，就叫做连续信源。比如语音信号X(t)。如果信源输出的随机变量取值于某一离散符号集合，就叫做离散信源。比如平面图像X(x，y)和电报。信源 X1,X2,X3,X411离散信源如果随机序列中各个变量具有相同的概率分布，则称为离散平稳信源。如果离散平稳信源的输出序列中各个变量是相互独立的，即前一个符号的出现不影响以后任何一个符号出现的概率，则称为离散无记忆平稳信源，否则称为离散有记忆平稳信源。信源

4、 X1,X2,X3,X4 a1,a2,a3,am12信息量和熵仙农信息论把一个事件（字符a1）所携带的信息量定义为：I(a1)=log2(1/p)=-log2 p (bit)其中p为事件发生（字符出现）的概率I(a1)即随机变量X取值为a1时所携带的信息量因为X的信息量也是一个随机变量，所以我们要研究它的统计特性。其数学期望为：称H(X)为一阶信息熵或者简称为熵(Entropy)13熵（Entropy）在符号出现之前，熵表示符号集中的符号出现的平均不确定性；在符号出现之后，熵代表接收一个符号所获得的平均信息量。根据直觉，信源编码的数据输出速率（平均码长）与信源熵之间应该有某种对应关系。14信源

5、的概率分布与熵的关系熵的大小与信源的概率模型有着密切的关系。最大离散熵定理：当与信源对应的字符集中的各个字符为等概率分布时，熵具有极大值log2m。m为字符集中字符个数。15二进制信源的熵二进制信源输出一个二进制数码所携带的平均信息量最大为1bit。pH10.50116最大离散熵定理的应用对于同一个信源其总的信息量是不变的，如果能够通过某种变换（编码），使信源尽量等概率分布，则每个输出符号所独立携带的信息量增大，那么传送相同信息量所需要的序列长度就越短。离散无记忆信源的冗余度隐含在信源符号的非等概率 分布之中。只要H（X）小于log2m，就存在数据压缩的可能。17编码信源 X1,X2,X3,X

6、4 a1,a2,a3,am信源 X1,X2,X3,X4 b1,b2,b3,bn0,118平均码长与熵如果对字符aj的编码长度为Lj，则X的平均码长为：根据前面对二进制信源的分析，有：在Lj log2pj时，平均码长取得极小值H(X)19关于离散无记忆平稳信源的结论一阶熵即为离散无记忆平稳信源的压缩极限。（基本极限）只要信源不是等概率分布，就存在着数据压缩的可能性。数据压缩的基本途径之一：使各字符的编码长度尽量等于字符的信息量。20联合熵与条件熵设随机变量X和Y分别取值于符号表a1,a2,am和b1,b2,b3,bn定义X与Y的联合熵为：定义X关于Y的条件熵为：21离散有记忆信源的冗余联合熵与其

7、可能达到的最大值之间的差值反映了该有记忆信源所含的冗余度，这种冗余是由于随机变量序列之间的相关性造成的。22关于离散有记忆平稳信源的结论离散有记忆平稳信源的压缩极限为：压缩的基本途径之二：尽量去除各分量之间的相关性，再对各分量进行独立编码。压缩的基本途径之三：可利用条件概率进行编码，阶越高越有利。压缩的基本途径之四：可将多个分量合并成向量，利用其联合概率进行编码，联合的分量越多越有利。23熵编码熵编码包括香农范诺编码、霍夫曼编码和算术编码，其宗旨在于找到一种编码使得平均码长到达熵极限，基本思想就是对出现概率较大的符号取较短的码长，而对出现概率较小的符号取较大的码长。24霍夫曼编码具体步骤：（1

8、）初始化（2）合并概率最小的两个事件（3）排序（4）如果事件个数大于2则重复（2）和（3）（5）赋值（6）编码25霍夫曼编码举例符号S1S2S3S4出现概率1/21/41/81/8等长编码00011011霍夫曼010110111H(X)=1.75 L1=2 L2=1.75源S1S2S1S3S2S1S1S4等0001001001000011霍0100110100011126霍夫曼编码的局限性利用霍夫曼编码，每个符号的编码长度只能为整数，所以如果源符号集的概率分布不是2负n次方的形式，则无法达到熵极限。输入符号数受限于可实现的码表尺寸译码复杂需要实现知道输入符号集的概率分布没有错误保护功能27香农

9、范诺编码香农范诺编码与Huffman编码相反，采用从上到下的方法。具体步骤为：（1）首先将编码字符集中的字符按照出现频度和概率进行排序。（2）用递归的方法分成两部分，使两个部分的概率和接近于相等。直至不可再分，即每一个叶子对应一个字符。（3）编码。28香农范诺编码举例A BC D EABCD EDE符号符号ABCDE次数次数1577650101001129算术编码Huffman 编码的局限性：Huffman 编码使用整数个二进制位对符号进行编码，这种方法在许多情况下无法得到最优的压缩效果。假设某个字符的出现概率为 80%，该字符事实上只需要-log2(0.8)=0.322 位编码，但 Huff

10、man 编码一定会为其分配一位 0 或一位 1 的编码。可以想象，整个信息的 80%在压缩后都几乎相当于理想长度的 3 倍左右。30算术编码基本思想：算术编码不是将单个信源符号映射成一个码字，而是把真个信源表示为实数线上的0到1之间的一个区间，其长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。消息序列中的每个元素都要用来缩短这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。采用算术编码每个符号的平均编码长度可以为小数。31算术编码举例（一）符号00011011概率0.10.40.20.3初始区间0,0.1)0

11、.1,0.5)0.5,0.7)0.7,1)32算术编码举例（二）最后的子区间起始位置 85/256=0.01010101 子区间长度 27/256=0.00011011 子区间尾 7/16 =0.0111取编码区间中的一个值，最后编码为：011符号01频度1/43/4消息序列1011区间起始1/41/419/6485/256区间长度3/43/169/6427/256信源分布：信源分布：33算术编码的具体实现因为实际只能用有限长的寄存器，这就要求将已编码的高位码字及时输出，但又不能输出过早，以免后续运算还要调整已输出的码位。（请看参考书上给出的算法）算术编码每次递推都要做乘法，所以效率比较低。二

12、进制算术编码是一种实用的编码算法，用移位代替了乘法，使效率大大提高。自适应算术编码可以在编码过程中根据符号出现的频繁程度动态的修改分布概率，这样可以避免在编码之前必须精确求出信源概率的难题。34自适应算术编码举例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.35行程编码（RLE）行程编码（Run-Length Encoding）：它通过

13、将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。例如：RTTTTTTTTABBCDG被转换为：R#8TABBCDG，其中“”作为转义字符，表明其后所跟的字符表示长度。行程编码多用于黑白二值图像的压缩中。例如00000000111111111111000001111111被转化为一系列黑串和白串长度的编码：81257。因为串长度并非等概率分布，所以一般要配合以统计编码（Huffman编码）。36词典编码词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符

14、号之间的相关性。字符串与代号的对应表就是词典。实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。37第一类词典编码第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。38LZ77算法LZ77 算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词

15、典的大小才能保证算法的效率；随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。39LZ77编码的基本流程1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。2、输出三元符号组(off,len,c)。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符，即不匹配的第一个字符。然后将窗口向后滑动 len+1 个字符，继续步骤 1。3、输出三元符号组(0,0,c)。其中 c 为下一个字符。然后将窗口向后滑

16、动 1 个字符，继续步骤 1。40LZ77算法41LZ77编码举例AABCBBABCA步骤步骤位置位置匹配串匹配串输出输出110,0,A22A1,1,B340,0,C45B2,1,B57ABC5,3,A42LZSS算法LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。LZSS算法的思想是如果匹配串的长度比指针本身的长度长就输出指针（匹配串长度大于等于MIN_LENGTH），否则就输出真实字符。另外要输出额外的标志位区分是指针还是字符。43LZSS

17、编码的基本流程1、从当前压缩位置开始，考察未编码的字符，并试图在滑动窗口中找出最长的匹配字符串，如果匹配串长度len大于等于最小匹配串长度（len=MIN_LENGTH），则进行步骤 2，否则进行步骤 3。2、输出指针二元组(off,len)。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为匹配串的长度，然后将窗口向后滑动 len 个字符，继续步骤 1。3、输出当前字符c，然后将窗口向后滑动 1 个字符，继续步骤 1。44LZSS编码举例位置位置1234567891011字符字符AABBCBBAABC步骤步骤位置位置匹配串匹配串输出输出11A22AA33B44BB55C66BB（

18、3，2）78AAB（7，3）811CC输入数据流：输入数据流：编码过程编码过程MIN_LEN=245LZSS算法在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip,GZip,ARJ,LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。46第二类词典编码第二类算法的想法是企图从输入的数据中创建一个“短

19、语词典(dictionary of the phrases)”，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。47LZ78算法LZ78的编码思想是不断地从字符流中提取新的字符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流(Char stream)，生成码字流(Code stream)，从而达到压缩数据的目的。LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字

20、流中，与码字W相对应的字符串(String)用字符C进行扩展生成新的字符串(String)，然后添加到词典中。48LZ78编码算法步骤1：将词典和当前前缀P都初始化为空。步骤2：当前字符C:=字符流中的下一个字符。步骤3：判断PC是否在词典中 （1）如果“是”，则用C扩展P，即让P:=PC，返回到步骤2。（2）如果“否”，则 输出与当前前缀P相对应的码字W和当前字符C，即（W，C）；将PC添加到词典中；令P:=空值，并返回到步骤249LZ78编码举例位置位置123456789字符字符ABBCBCABA步骤步骤位置位置词典词典输出输出11A(0,A)22B(0,B)33BC(2,C)45BCA(

21、3,A)58BA(2,A)输入数据流：输入数据流：编码过程：编码过程：50LZW算法 J.Ziv和A.Lempel在1978年首次发表了介绍第二类词典编码算法的文章。在他们的研究基础上，Terry A.Welch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW(Lempel-Ziv Walch)压缩编码。在编码原理上，LZW与LZ78相比有如下差别：LZW只输出代表词典中的字符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符。即在编码匹配时，至少可以在词典中找到长度为1的匹配串。LZW编码是围绕称为

22、词典的转换表来完成的。51LZW算法的词典 LZW编码器(软件编码器或硬件编码器)就是通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流(Char stream)，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流(Code stream)，码字代表单个字符或多个字符组成的字符串(String)。52LZW编码算法步骤1：将词典初始化为包含所有可能的单字符，当前前缀P初始化为空。步骤2：当前字符C:=字符流中的下一个字符。步骤3：判断PC是否在词典中 （1）如果“是”，则用C扩展P，即让P:=PC，返回到步骤2。（2）如果“否”，则 输出与

23、当前前缀P相对应的码字W；将PC添加到词典中；令P:=C，并返回到步骤253LZW编码举例位置位置123456789字符字符ABBABABAC步骤步骤位置位置码字码字词典词典输出输出1A2B3C114AB1225BB2336BA2447ABA4568ABAC7输入数据流：输入数据流：编码过程：编码过程：54LZW算法 LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。LZW算法取得了专利，专

24、利权的所有者是美国的一个大型计算机公司Unisys(优利系统公司)，除了商业软件生产公司之外，可以免费使用LZW算法。55预测编码预测编码是数据压缩理论的一个重要分支。它根据离散信号之间存在一定相关性的特点，利用前面的一个或多个信号对下一个信号进行预测，然后对实际值和预测值的差（预测误差）进行编码。如果预测比较准确，那么误差信号就会很小，就可以用较少的码位进行编码，以达到数据压缩的目的。第n个符号Xn的熵满足：所以参与预测的符号越多，预测就越准确，该信源的不确定性就越小，数码率就可以降低。56DPCM编码预测器xkekxkxk-ekDPCM是有损型还是无损型关键看对预测误差是有损型还是无损型关

25、键看对预测误差ek如何编码。57预测方程式 线性预测：如果ai是常数，则为时不变线性预测，否则为自适应线性预测（ADPCM）最简单的预测方程：58最佳线性预测使误差函数达到最小值的预测方程式叫做最佳线性预测。求最佳线性预测的各个参数ai，列方程组：代入得到联立方程组：如果为一阶线性预测，则可求得：59图像信号的预测编码一副数字图像可以看成一个空间点阵，图像信号不仅在水平方向是相关的，在垂直方向也是相关的。根据已知样值与待预测样值间的位置关系，可以分为：（1）一维预测（行内预测）：利用同一行上相邻的样值进行预测。（2）二维预测（帧内预测）：利用同一行和前面几行的数据进行预测。（3）三维预测（帧间

26、预测）：利用相邻几帧（或不同波段）上的取样值进行预测60静止图像的二维预测编码这种压缩算法被应用到JPEG标准的无损压缩模式之中，中等复杂程度的图像压缩比可达到2:1。cabx选择值预测值0非预测1a2b3c4a+b-c5a+(b-c)/26b+(a-c)/27(a+b)/2d三邻域预测法三邻域预测法61活动图像的帧间预测编码视频信号的冗余度主要体现在空间相关性（帧内）、时间相关性（帧间）和色度空间表示上的相关性。对于每秒25帧（30）的电视信号，其相继帧之间存在极强的相关性。据统计256级灰度的黑白图像序列，帧间差值超过3的象素数不超过4。所以在活动图像序列中可以利用前面的帧来预测后面的帧，

27、以实现数据压缩。帧间预测编码技术被广泛应用到H.261、H.263、MPEG-1和MPEG-2等视频压缩标准之中。62具有运动补偿的帧间预测活动图像序列中的一个画面可以大致划分为3个区域：（1）背景区：相邻两个画面的背景区基本相同。（2）运动物体区：可以视为由前一个画面的某一区域的像素平移而成。（位移矢量）（3）暴露区：指物体运动后而显露出来的曾被遮盖的背景区域。运动补偿预测就是将前一个画面的背景区平移后的运动物体区作为后一个画面的预测值。63运动补偿帧间预测编码运动补偿帧间预测从原理上包括如下几个基本步骤：（1）图像分割：把图像划分为静止的背景和若干运动的物体，各个物体可能有不同的位移，但构成同一物体的所有像素的位移相同。（2）运动矢量估值：考察前后两个画面，利用运动估值算法得到每个物体的位移矢量。（3）运动补偿：用运动矢量补偿物体的运动效果再进行预测。（4）编码：除了对实测值与预测值之间的差值进行编码传送外，还要传送位移矢量以及区域分割信息。64运动补偿帧间预测编码编码器运动补偿图像输入图像输入运动矢量输出运动矢量输出-译码器帧缓存运动估值预测误差输出预测误差输出65变换编码预测编码希望通过对信源建模来尽可能的预测源数据；而变换编码则考虑将原始数据变换到另一个表示空间，使数据在新的空间上尽可能相互独立，而能量更集中。XYXY66MTIMTIXIDIANXIDIAN结束67