多媒体技术好资源第03讲多媒体数据压缩基础

第3章多媒体数据压缩基础3.1

媒体元素的特点3.2数据压缩编码简介3.3统计编码3.4预测编码

3.5变换编码

第一页，共六十页。

媒体元素的特点3.11.文本——是以文字和各种专用符号表达的信息形式，它是现实生活中使用得最多的一种信息存储和传递方式。用文本表达信息给人充分的想象空间，它主要用于对知识的描述性表示，如阐述概念、定义、原理和问题以及显示标题、菜单等内容。2.图形——是指由外部轮廓线条构成的矢量图。即由计算机绘制的直线、圆、矩形、曲线、图表等。3.图像——是多媒体中最重要的信息表现形式之一，它是决定一个多媒体软件视觉效果的关键因素。

4.视频——指将一系列的静态影像以电信号方式加以捕捉，纪录，处理，储存，传送，与重现的各种技术。5.音频——按表达形式，声音分为讲解、音乐、效果三类。

6.动画——动画是利用人的视觉暂留特性，快速播放一系列连续运动变化的图形图像，也包括画面的缩放、旋转、变换、淡入淡出等特殊效果。

第二页，共六十页。数据压缩编码简介（1）数据压缩的必要性

图像信号：黑白480×360，8bit； 大小是480×360÷1024=168.45KB 彩色大小是480×360×3÷1024=506.25KB 视频：PAL制每秒数据量506.25KB×25帧/秒=12.36MB/s（2）数据压缩的可能性

空间冗余 时间冗余结构冗余视觉冗余知识冗余信息熵冗余3.2第三页，共六十页。数据压缩的可能性P16●[1]空间冗余——规则物体的物理相关性[2]时间冗余——视频与动画画面间的相关性[3]统计冗余——具有空间冗余和时间冗余[6]视觉冗余——视觉、听觉敏感度和非线性感觉[7]知识冗余——凭借经验识别[4]结构冗余——规则纹理、相互重叠的结构表面[5]信息熵冗余——编码冗余，数据与携带的信息10110001110010110001110001011010101010111100010111111010224色28色声音频率文字组句色彩渐变主观意识::教学进程第四页，共六十页。（1）空间冗余静态图像中存在的最主要的一种数据冗余在同一幅图像中，规则物体和规则背景的表面物理特性具有相关性即对同一景物表面上采样点的颜色之间存在着空间连贯性例如：图像中一片连续的区域，其像素为相同的颜色—空间冗余数据压缩的可能性P16●第五页，共六十页。（2）时间冗余序列图像(电视图像、动画)和语音数据中所经常包含的冗余一组连续的画面之间往往存在着时间和空间的相关性例如：唱歌的歌手、两人谈话时背景一致等数据压缩的可能性P16●第六页，共六十页。（3）统计冗余是空间冗余和时间冗余的总称。在数据处理时，往往采用统计事件出现概率的办法来鉴别空间冗余和时间冗余，因此空间冗余和时间冗余具有统计特性。数据压缩的可能性P16●第七页，共六十页。（4）结构冗余在某些场景中，存在着明显的分布模式——结构结构可以通过特定的过程来生成例如：方格状的地板，蜂窝，砖墙等数据压缩的可能性P16●第八页，共六十页。（5）信息熵冗余信息熵：一组数据所携带的信息量。冗余的产生是因为：在信源符号的表示过程中未遵循信息论下最优编码而造成。通过熵编码进行压缩数据压缩的可能性P16●第九页，共六十页。（6）视觉冗余可以根据这些视觉特性来对图象信息进行取舍人类的视觉系统对图像场的敏感性：非均匀和非线性的对亮度变化敏感，而对色度的变化相对不敏感在高亮度区，人眼对亮度变化敏感度下降对物体边缘敏感，内部区域相对不敏感对整体结构敏感，而对内部细节相对不敏感数据压缩的可能性P16●第十页，共六十页。（7）知识冗余有许多图像的理解与某些基础知识有相当大的相关性这类规律性的结构可以由先验知识和背景知识得到例如：人脸的图像知识冗余是模型编码的基础数据压缩的可能性P16●第十一页，共六十页。●多媒体数据压缩的性能指标●压缩比●压缩性能常常用压缩比定义(输入数据和输出数据比)例：512×480，24bit/pixel(bpp)输出15000byte输入＝737280byte压缩比＝737280/15000＝49教学进程节省图象或视频的存储容量，增加访问速度，使数字视频能在PC机上实现，需要进行视频和图象的压缩。有三个关键参数评价一个压缩系统：压缩比、图象质量、压缩和解压的速度，第十二页，共六十页。●压缩质量●压缩方法分为无损压缩和有损压缩，对于有损压缩：失真情况很难量化，只能对测试的图象进行估计。模拟图象质量的指标：信噪比、分辨率、颜色错，但必须在观察了实际图象以后。教学进程●压缩和解压缩速度●在许多应用中，压缩和解压可能不同时用，在不同的位置不同的系统中。所以，压缩、解压速度分别估计。静态图象中，压缩速度没有解压速度严格；动态图象中，压缩、解压速度都有要求，因为需实时地从摄像机或VCR中抓取动态视频。●多媒体数据压缩的性能指标第十三页，共六十页。（3）数据压缩编码分类无损压缩指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同。无损压缩算法一般压缩比2～4。常用的无损压缩算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv&Welch)压缩算法。有损压缩指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。3.2数据压缩编码简介第十四页，共六十页。压缩技术分类通用数据压缩（均为无损压缩）多媒体数据压缩（无损和有损压缩）基于统计模型的压缩技术基于字典模型的压缩技术Huffman编码算术编码LZ77LZ78LZW图像压缩音频和视频压缩MPEG等二值图像CCITTJBIG等灰度图像FELICSJPEG等彩色图像RLE编码JPEG等矢量图像PostScriptWMFCAD等第十五页，共六十页。压缩技术的应用电报、传真(CCITT)通讯(Modem/网络协议)存储(压缩池)文件系统(压缩扇区)图像(GIF/TIFF/JPEG)音频(MP3)视频(MPEG/RM)数据库(B+树)归档(TAR/ZIP)密码学(消除数据的原始特征)全文索引(倒排索引表)编译(JAVA)程序设计(算法/空间和时间效率)人工智能(专家系统/知识树)第十六页，共六十页。压缩编码分类（按长度）等长编码ASCII编码 不等长编码编码长度是不等长的常见编码如Huffman编码第十七页，共六十页。等长与不等长编码例如：符号序列x=“aa

bb

cccc

dddd

eeeeeeee”采用ASCII编码：a=01100001b=01100010c=01100011d=01100100e=01100101空=00100000等长编码：24*8=192bit如用后3位进行编码只需要3*24=72bit压缩比为：72/192=第十八页，共六十页。等长与不等长编码不等长编码方法字符次数概率码字 字长E 8 1/3 0 1D 4 1/6 100 3C 4 1/6 101 3空 4 1/6 110 3a 2 1/12 1110 4B 2 1/12 1111 4需要空间：1*8+3*4+3*4+3*4+2*4+2*4=60平均码长=总位数/字符出现次数=60/24=2.5第十九页，共六十页。不等长码唯一性问题字符 码1 码2 码3 A 0 0 0B 10 10 01C 110 11 011D 1110 01 111对序列010110译码码1 abc码2 daca或ddb或abca码3 bca第二十页，共六十页。3.3统计编码

（1）信息熵与信息量 信息量是指从N个相等的可能事件中选出一个事件所需要的信息度量或含量，也就是在辨识N个事件中特定的一个事件的过程中所需要提问“是或否”的最少次数。 设从N个数中选定任一个数xj的概率为p（xj），假定选定任意一个数的概率都相等，即p（xj）＝1/N，因此定义其信息量为:

P(xj)是信源X发出xj的概率。I(xj)的含义是，信源X发出xj这个消息（随机事件）后，接收端收到信息量的量度。第二十一页，共六十页。（1）信息熵与信息量 来源于40年代由ClaudeShannon创立的信息论中的一条定理，这一定理借用了热力学中的名词“熵”(Entropy)来表示一条信息中真正需要编码的信息量。信源S发出的xj（j=1,2,…,n）共n个随机事件的自信息统计平均，即

H(X)称为信源X的“熵”，即信源X发出任意一个随机变量的平均信息量。其中：等概率事件的熵最大，为：当P(x1)＝1时，P(x2)＝P(x3)＝…＝P(xj)＝0，由（4-6）式得此时熵为由上可得熵的范围为：3.3统计编码

第二十二页，共六十页。平均码长与熵关系 在编码中用熵值来衡量是否为最佳编码。若以Lc表示编码器输出码字的平均码长，则当 Lc≥H(S)有冗余，不是最佳。 Lc＜H(S)不可能。 Lc＝H(S)最佳编码（Lc稍大于H(S)）。 熵值为平均码长Lc的下限。平均码长Lc的计算公式为其中：P(xj)是信源X发出xj的概率，L(xj)为xj的编码长。（j=1,2,…,n）3.3统计编码

第二十三页，共六十页。熵的计算范例例：对信息aabbaccbaa，字符串长度为10，字符a、b、c分别出现了5、3、2次，则Ia=-log2(0.5)=1Ib=-log2(0.3)=1.737Ic=-log2(0.2)=2.322H（S）=0.5Ia+0.3Ib+0.2Ic=1.4855如采用等长编码，则每个字符需要２位；总的码长:L=5*２+3*２+2*２

=２０位对比一下，我们用ASCII编码表示该信息需要80位第二十四页，共六十页。统计编码（熵）统计编码是根据消息出现概率的分布特性而进行的压缩编码在消息和码字间找到明确的一一对应关系，以便恢复时能准确无误再现出来第二十五页，共六十页。技术准备：编码通过模型，我们可以确定对某一个符号该用多少位二进制数进行编码。现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。前缀编码规则：任何一个符号的编码都不是另一个符号编码的前缀。最简单的前缀编码字符编码A0B10C110D1110E1111011110111100010DABBDCEAAB第二十六页，共六十页。Shannon-Fano编码采用从上到下的方法进行编码。仙农-范诺(Shannon-Fano)算法：首先按照符号出现的频度或概率排序，使用递归方法分成两个部分，每一部分具有近似相同的次数（概率）当概率和为1，进行编码第二十七页，共六十页。Shannon-Fano编码例１有一幅40个象素组成的灰度图像，灰度共有5级，分别用符号A、B、C、D和E表示，40个象素中出现灰度A的象素数有15个，出现灰度B的象素数有7个，出现灰度C的象素数有7个等等。如果用3个位表示5个等级的灰度值，也就是每个象素用3位表示，编码这幅图像总共需要120位。符号ABCD

E出现的次数157765H(S)=(15/40)*

(40/15)+(7/40)*

(40/7)+…

+(5/40)*

(40/5)=2.196

这就是说每个符号用2.196位表示，40个象素需用87.84位第二十八页，共六十页。Shannon-Fano编码例１符号出现的次数(

)

分配的代码需要的位数A15(0.375)1.41500030B7(0.175)2.51450114C7(0.175)2.51451014D6(0.150)2.736911018E5(0.125)3.000011115第二十九页，共六十页。Shannon-Fano编码例２例题：cabcedeacacdeddaaabaababaaabbacdebaceada例子中的信息编码为：1000011011111011100100010......码长共91位，而使用ASCII编码表示上述信息共需要320位a–16b–7c–6d–6e-5a–16b–7---------c–6-----d–6e-5a–00b–01c–10d–110e–111root0010111abcde0第三十页，共六十页。3.3统计编码-霍夫曼编码 依据信源字符出现的概率大小来构造代码，对出现概率较大的信源字符，给予较短码长，而对于出现概率较小的信源字符，给予较长的码长，最后使得编码的平均码字最短。第三十一页，共六十页。3.3统计编码-霍夫曼编码（2） 编码过程——出现频率高的数据编码长度短，反之亦然[1]信号源的数据按照出现概率递减的顺序排列[2]合并两个最小出现概率，作为新数据出现概率[3]重复进行[1][2]，直至概率相加为1为止[4]合并运算时，概率大者取0，概率小者取1[5]记录概率为1处到信号源的0、1序列编码特点[1]编码长度可变，压缩与解压缩较慢[2]硬件实现困难[3]编码效率取决于信号源的数据出现概率第三十二页，共六十页。例4-1：设输入图像的灰度级{a1,a2,a3,a4,a5,a6}出现的概率分别是0.4、0.2、0.12、0.15、0.1、0.03。试进行哈夫曼编码，并计算编码效率、压缩比、冗余度。

编码步骤：（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如图4-2所示。（2）把概率小的两个符号组成一个节点，如图4-2中的a5、a6组成节点P1。（3）重复步骤2，得到节点P2、P3、P4、P5，形成一棵“树”，其中P5为根节点。（4）从根节点P5开始到相应于每个符号的“树叶”，从上到下标上1（上枝）或者0（下枝），至于哪个为1哪个为0则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。最终编码结果为：a1=1,a2=000, a3=011,a4=001,a5=0100, a6=0101

第三十三页，共六十页。由公式可求得图像信源熵是：H(X)=

=-（0.4×log20.4+0.2×log20.2+0.12×log20.12+ 0.15×log20.15+0.1×log20.1+0.03×log20.03） =2.25bit根据哈夫曼编码过程图给出的结果，由公式（4-7）可求出它的平均码字长度：Lc=0.4×1+0.2×3+0.15×3+0.12×3+0.1×4+0.03×4=2.33压缩之前8个符号需要3个比特量化，经过压缩之后的平均码字长度为2.33，由公式（4-10）得其压缩比为：第三十四页，共六十页。Huffman编码例题2：cabcedeacacdeddaaabaababaaabbacdebaceada

例子中的信息编码为：101010010111111011101010101......码长88位，比Shannon-Fano编码略短一些a–16b–7c–6d–6e-5a–0b–100c–101d–110e–111root00111abcde001第三十五页，共六十页。整数位编码与信息熵cabcedeacacdeddaaabaababaaabbacdebaceada该信息的熵经计算可知为86.601位符号理想位数（熵）S-F编码需要位数Huffman编码需要位数a1.32221b2.51523c2.73723d2.73733e3.00033总计86.6019188第三十六页，共六十页。3.3统计编码-算术编码 假设某个字符的出现概率为80%，该字符事实上只需要-log2(0.8)=0.322个二进制位进行编码 难道真的能只输出0.322个0或0.322个1吗？算术编码的输出是：一个小数 算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于0和1之间的二进制小数。 例如算术编码对某条信息的输出为1010001111，那么它表示小数0.1010001111，也即十进制数0.64第三十七页，共六十页。算术编码（arithmeticcodingAC）是利用0和1之间的间隔来表示信源编码的一种方法，其编码值是间隔的上、下限包含的相同二进制。编码过程中的间隔决定了符号压缩后的输出。算术编码用到两个基本的参数：符号的概率和它的编码间隔。

信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。3.3统计编码-算术编码第三十八页，共六十页。算术编码计算方法Low=low+range*range_low(symbol)high=low+range*range_high(symbol)其中：Low是前一个符号的最低值；range是之前所有符号的概率积；range_low和range_high分别是当前符号的上下值；一般编码取最小值，采用乘2取整得到二进制编码。第三十九页，共六十页。例假设信源符号为{A,B,C,D}，这些符号的概率分别为{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]，如表符号ABCD概率0.10.40.20.3初始编码间隔[0,0.1][0.1,0.5][0.5,0.7][0.7,1]表信源符号、概率和初始编码间隔如果消息序列的输入为：CADACDB，其编码过程如下：首先输入的符号是C，找到它的编码范围是[0.5,0.7]；由于消息中第2个符号A的编码范围是[0,0.1]，因此它的间隔就取[0.5,0.7]的第一个1/10作为新间隔[0.5,0.52]；编码第3个符号D时取新间隔为[0.514,0.52]；编码第4个符号A时，取新间隔为[0.514,0.5146]，…。第四十页，共六十页。消息的编码输出可以是最后一个间隔中的任意数，整个编码过程如图。最后在[0.5143876,0.514402]中选择一个数作为编码输出值：0.5143876解码时，解码器由编码输出值：0.5143876，可马上解得一个字符为C，然后依次得到唯一解A,D,A,C,D,B。第四十一页，共六十页。3.3统计编码

-行程编码是一个针对包含有顺序排列的多次重复的数据的压缩方案。其原理就是把一系列的重复值用一个单独的值再加上一个计数值来取代，行程长度就是连续且重复的单元数目。如果想得到原始数据，只需展开这个编码就可以了。例如，计算机制作图像中，常常具有许多颜色相同的图块，而且在行上都具有相同的颜色，或者在一行上有许多连续的像素都具有相同的颜色值。这时，就不需要存储每一个像素的颜色值，而仅存储一个像素的颜色值以及具有相同颜色的像素数目就可以，或者存储一个像素的颜色值，以及具有相同颜色值的行数，这种压缩编码称为行程编码。具有相同颜色的连续的像素数目称为行程长度。第四十二页，共六十页。十进制小数0.6875转换为二进制小数是？方法是？答案是？0.1011第四十三页，共六十页。假定一幅灰度图像，第n行的像素值为：用RLE编码方法得到的代码为：3150841160。代码斜黑体表示的数字是行程长度，黑体字后面的数字代表像素的颜色值。例如黑体字50代表有连续50个像素具有相同的颜色值，它的颜色值是8。对比RLE编码前后的代码数可以发现，在编码前要用73个代码表示这一行的数据，而编码后只要用10个代码表示代表原来的73个代码，压缩前后的数据量之比约为7:1，即压缩比为7:1。这说明RLE确实是一种压缩技术，而且编码技术实用。3.3统计编码

-行程编码第四十四页，共六十页。RLE的性能好坏主要取决于图像本身的特点。RLE压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。然而，由于颜色丰富的自然图像在同一行上具有相同颜色的连续像素往往很少，而连续几行都具有相同颜色值的连续行数就更少，如果仍然使用RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。因此，RLE属于无损压缩技术。3.3统计编码

-行程编码第四十五页，共六十页。词典编码属于无损压缩技术，其根据是数据本身包含有重复代码序列这个特性。词典编码的种类较多，归纳起来有两类：第一类词典编码的基本思想是查找正在压缩的字符序列是否在前面输入的数据中出现过，如果是，则用指向早期出现过的字符串的“指针”替代重复的字符串。3.3统计编码

–词典编码第四十六页，共六十页。3.3LZW词典编码例：待编码数据流ABBCABBBC第四十七页，共六十页。源码键输出字典字符串1A2B3CNILAAB14ABBB25BBBC26BCCA37CAAB(A)BB48ABBBB(B)BC59BBCCEOF3第四十八页，共六十页。源码后码输出字典字符串1A2B3CAB14ABBC25BCCA36CAAB(A)BA47ABAABBA(AB)AA78ABAAAEOF1ABCABABAA第四十九页，共六十页。3.4

预测编码-脉冲编码调制3.23.92.83.41.24.2343314011100011011001100原始信号PAM脉冲（采样）PCM脉冲（量化）有量化差错1001100PCM输出（编码）第五十页，共六十页。

3.4

预测编码-脉冲编码调制第五十一页，共六十页。3.4

预测编码-量化（1）均匀量化如果采用相等的量化间隔对采样得到的信号作量化，那么这种量化称为均匀量化。均匀量化就是采用相同的“等分尺”来度量采样得到的幅度，也称为线性量化，如图3-08所示。量化后的样本值Y和原始值X的差E=Y-X称为量化误差或量化噪声。第五十二页，共六十页。（2）非均匀量化

无论对大的输入信号还是小的输入信号一律都采用相同的量化间隔。但是，对话音信号来说，大信号出现的机会并不多，增加的样本位数就没有充分利用。为了克服这个不足，就出现了非均匀量化的方法，这种方法也叫做非线性量化。非线性量化的基本想法是，对输入信号进行量化时，大的输入