第6章多媒体数据压缩技术

第6章多媒体数据压缩技术第一页，共62页。教学目标

■熟悉多媒体数据压缩的基本概念及原理

■了解压缩方法的分类

■掌握几种常用的压缩方法■掌握数据压缩的国际标准第6章多媒体数据压缩技术第二页，共62页。

■6.1多媒体数据压缩概述1.多媒体信息的数据量巨大●文本若1024×768显示分辨率、16×16点阵文字、4Byte/字，则一屏汉字的总数据量为:到

(1024/16)×(768/16)×4=12288Byte6.1.1数据压缩的必要性●图像若采用640×480显示分辨率，24位真彩色，则满屏图像的总数据量为:640×480×24÷8=？Byte(922KB)●音频若采样频率为44.1KHz16bit(2Byte)，立体声，则1分钟的总数据量为:

●视频若采样频率最低为10M,样本宽度为24bit,扫描速度为25帧/s,则一帧数字化图像所用的最少存储空间为1.2M。44.1×2Byte×2×60s=10584KB10×24/8×1s/25=1.2MB第6章多媒体数据压缩技术第三页，共62页。●视频以PAL制为例，显示有效分辨率为720*576，样本宽度为24bit,扫描速度为25帧/s,则1s的数据量是：720*576*24/8*25*1s=?MB第6章多媒体数据压缩技术

■6.1多媒体数据压缩概述6.1.1数据压缩的必要性第四页，共62页。2.有效利用存储器容量3.提高通信线路的传输效率4.消除计算机系统处理视频I/O瓶颈第6章多媒体数据压缩技术

■6.1多媒体数据压缩概述6.1.1数据压缩的必要性第五页，共62页。●数据存在冗余(重复数据、可忽略数据)●不敏感因素(颜色、亮度、频率、细节)6.1.2数据压缩条件224颜色(16,777,216色)28颜色(256色)第6章多媒体数据压缩技术第六页，共62页。信息量与冗余的关系●冗余——

信息所具有的各种性质中多余的无用空间●冗余度——

多余的无用空间的程度6.1.3数据冗余I=D－du

I—信息量D—数据量du—冗余量例：180个汉字，文本数据量为360B。广播员朗读使用1分钟，数字化时采样频率8KHz，8位量化，则数据量为8×60s=480KB/分

一分钟语音数据有

倍冗余（480KB-360B)/360B=1300第6章多媒体数据压缩技术第七页，共62页。冗余分类[1]空间冗余——

规则物体的物理相关性[2]时间冗余——

运动图像中的相关性[3]统计冗余——

具有空间和时间冗余[5]视觉冗余——

视觉的敏感度和非线性感觉[6]知识冗余——

凭借经验识别[4]结构冗余——

规则纹理、重叠的结构表面[7]其他冗余——图像的非特定性带来的冗余224色28色声音频率文字组句色彩渐变主观意识::第6章多媒体数据压缩技术第八页，共62页。图像压缩系统的组成6.1.4压缩原理变换器量化器编码器输入图像图像压缩的的相关指标

压缩比算法简单恢复效果好压缩能否用硬件实现第6章多媒体数据压缩技术第九页，共62页。

■6.2数据压缩算法6.2.1数据压缩算法分类●

无损压缩编码——压缩数据还原后，与原始数据一致，无损失●

有损压缩编码——

压缩后再还原的数据有损失无损压缩编码(可逆编码)霍夫曼编码行程编码算术编码有损压缩编码(不可逆编码)全频带编码PCM/ADPCM混合编码JPEG/MPEG按是否失真来分第6章多媒体数据压缩技术第十页，共62页。6.2.1数据压缩算法分类●预测编码针对空间冗余和时间冗余利用已被编码的点的值预测邻近的点的值●变换编码针对复杂图像将图像或时域信号变换到频域上，再进行压缩按是压缩原理来分●信息熵编码根据信息熵原理，对概率大符号用短码字表示，反之用长码字表示典型的有哈夫曼编码、行程编码、算术编码●混合编码把变换编码和预测编码结合的编码方法第6章多媒体数据压缩技术第十一页，共62页。几个相关的名词●信息是用不确定性的量度定义的。一个消息的可能性愈小，其信息愈多；而消息的可能性愈大，则其信息愈少。●信息量：指从N个相等的可能事件中选出一个事件所需要的信息度量和含量，也就是在N个事件中辩识特定的一个事件要询问的“是或否”的次数.（假如要从64个数中选定某一个数)第6章多媒体数据压缩技术

■6.2数据压缩算法第十二页，共62页。信息量的计算公式概率I(x)=log2N=-log2=-log2p(xj)1N第6章多媒体数据压缩技术●P(xj)是信源X发出xj的概率;I(xj)是指信源X发出xj这个消息后，接收端收到信息量的量度。

■6.2数据压缩算法第十三页，共62页。●熵：如果将信源所有可能事件的信息量进行平均，就得到了信息熵(entropy)。熵就是平均信息量。H(X)称为信源X的“熵”，即信源X发出任意一个随机变量的平均信息量第6章多媒体数据压缩技术

■6.2数据压缩算法第十四页，共62页。平均码长的算法●

P(Xj)为信源符号出现的概率，L(Xj)是符号的编码长度。（j=1,2,…,n）第6章多媒体数据压缩技术

■6.2数据压缩算法第十五页，共62页。6.2.2常用的无损压缩方法●

香农——范洛编码●编码原理——

[1]信号源的数据按照出现概率递减的顺序排。

[2]将排好序的符号分成两组，使每组的概率之和接近或相等。

[3]将第一组赋值为0，第二组赋值为1。

[4]把每个分组按同样原则划分，重复2，3，直到不能再分。

[5]读数时，从上到下。411141263FEDCBA例：有六个字母组成的字符串长度为50，各个字母出现的次数分别为：ABCDEF第6章多媒体数据压缩技术第十六页，共62页。411141263FEDCBA346111214AFBECDABCDEFDCEBFADCBFAEBFAFA0100001111符号编码ABCDEF11111100100101110概率3/506/5012/5014/5011/504/50第6章多媒体数据压缩技术第十七页，共62页。ABCDEF编码111111001001011101.信息符号的熵值：H(x)=符号概率3/506/5012/5014/5011/504/503/25log2(25/3)+……3/50log2(50/3)+2.符号的平均码长：=3/504

+3/253+(6/25+7/25+11/50+2/25)2+2/254第6章多媒体数据压缩技术

■6.2数据压缩算法第十八页，共62页。6.2.2常用的无损压缩方法●霍夫曼编码——

无损编码编码原理——出现频率高的数据编码长度短，反之亦然

[1]信号源的数据按照出现概率递减的顺序排列

[2]合并两个最小出现概率，作为新数据出现概率

[3]重复进行[1][2]，直至概率相加为1为止

[4]合并运算时，概率大者取1，概率小者取0[5]记录概率为1处到信号源的0、1序列编码特点编码长度可变，压缩与解压缩较慢硬件实现困难编码效率取决于信号源的数据出现概率第6章多媒体数据压缩技术ABCDEFG0.230.070.180.210.130.150.03例：信源符号及其概率如下所示，试求霍夫曼编码、平均码长及熵。第十九页，共62页。ABCDEFG0.230.070.180.210.130.150.03ADCFEBG0.230.210.180.150.130.070.03GB0.1001E0.2301FC0.33DA0.4401010.56011.001A：B：C：D：E：F：G：011001111001011101000第6章多媒体数据压缩技术解法一：第二十页，共62页。ADCFEBG0.230.210.180.150.130.070.03

1

00.101

00.23

1

00.33

1

00.44

1

00.56011.0霍夫曼码

010011111010110011000解法二：第6章多媒体数据压缩技术信源概率第二十一页，共62页。1.信息符号的熵值为：H(x)=-0.23log20.23-0.21log20.21-0.18log20.18-0.15log20.15-0.13log20.13-0.07log20.07-0.03log20.03符号概率2.符号的平均码长为：ADCFEBG霍夫曼码

0100111110101100110000.230.210.180.150.130.070.03=0.23×2+0.21×2+0.18×3+0.15×3+0.13×3+0.07×4+0.03×4=2.66第6章多媒体数据压缩技术第二十二页，共62页。第6章多媒体数据压缩技术x1x2x3x4x5x6x70.200.080.350.050.150.100.07练习题：信源符号及其概率如下所示:⑴求出各信源符号的霍夫曼编码。⑵求出平均码长。⑶求出熵并写出熵的计算公式。第二十三页，共62页。符号ADCFEBG霍夫曼码

0100111110101100110001.写出ABCDEF的霍夫曼的编码。（编码过程）2.霍夫曼编码111101100001100111000（译码过程）01100111100101110CEGABFD第6章多媒体数据压缩技术霍夫曼码的编码与解码过程第二十四页，共62页。6.2.2常用的无损压缩方法●算数编码——

无损编码算术编码方法是将被编码的信息表示成实数0和1之间的一个间隔。信息越长编码表示它的间隙就越小，表示这一间隙所须二进位就越多，大概率符号出现的概率越大对应于区间愈宽，可用长度较短的码字表示。小概率符号出现的概率越小对应于层间愈窄，需要长度较长的码字表示。20世纪60年代初，Elias提出了算术编码概念。1976年Rissanen和Pasco首次介绍该实用技术。第6章多媒体数据压缩技术第二十五页，共62页。符号abcd概率0.10.40.20.3初始间码间隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1]设：low为编码间隔的低端；high为高端；range为编码间隔的长度；rangelow为编码字符分配的间隔低端；rangehigh为编码字符分配的间隔高端。初始high=1,low=0,range＝high-low,初始值计算公式：·low=low＋range×rangelow

·high=low＋range×rangehigh此时分配给初始值的范围为［low,high]例：输入序列为cadacdb第6章多媒体数据压缩技术第二十六页，共62页。[0.7,1][0.5,0.7）[0.1,0.5)[0,0.1)初始编码间隔0.30.20.40.1概率dcba符号设：low为编码间隔的低端；high为高端range为编码间隔的长度；rangelow为编码字符分配间隔低端rangehigh为编码字符分配的间隔高端⑵第二个数值计算公式

以第一值后生成的编码间隔为初始值，再重复（1）（3）以下值的计算以此类推例：输入序列为cadacdb第6章多媒体数据压缩技术第二十七页，共62页。

■6.2数据压缩算法[0.7,1][0.5,0.7)[0.1,0.5)[0,0.1)初始编码间隔0.30.20.40.1概率dcba符号例：输入序列为cadacdb初始high=1,low=0,range＝high-low,初始值计算公式：·low=low＋range×rangelow

·high=low＋range×rangehigh此时分配给初始值的范围为［low,high]

第一个字符c编码时low=0+1×0.5=0.5high=0+1×0.7=0.7range=high-low=0.7-0.5=0.2此时分配给c的范围为［0.5,0.7]第6章多媒体数据压缩技术第二十八页，共62页。[0.7,1][0.5,0.7)[0.1,0.5)[0,0.1)初始编码间隔0.30.20.40.1概率dcba符号例：输入序列为cadacdb⑵第二个数值计算公式以第一值后生成的编码间隔为初始值，再重复（1）（3）以下值的计算以此类推第二个字符a编码时:初始值为［0.5,0.7]range=high-low=0.7-0.5=0.2low=0.5+0.2×0=0.5high=0.5+0.2×0.1=0.52此时分配给e的范围为［0.5,0.52]第6章多媒体数据压缩技术第二十九页，共62页。[0.7,1][0.5,0.7)[0.1,0.5)[0,0.1)初始编码间隔0.30.20.40.1概率dcba符号例：输入序列为cadacdbaabcd第6章多媒体数据压缩技术第三十页，共62页。●

游（行）程编码(RLE):用一个符号值或串长代替具有相同值的连续符号（连续符号构成了一段连续的“行程”），使符号长度少于原始数据的长度。

例：999997777722223334444(9，5)(7,5)(2,4)(3,3)(4,4)0000000111111444444000000（0，7）（1，6）（4，6）（0，6）第6章多媒体数据压缩技术

■6.2数据压缩算法第三十一页，共62页。6.2.3常用的有损压缩方法（熵压缩）预测编码：根据原始的离散信号之间存在关联性的特点，利用前面的一个或多个信号对下一个信号进行预测，然后对实际值和预测值的差进行编码。常用的有PCM（脉冲编码调制），拆分脉冲编码调制（DPCM），自适应拆分脉冲编码调制（ADPCM）.第6章多媒体数据压缩技术第三十二页，共62页。6.2.3常用的有损压缩方法（熵压缩）●

差分脉冲编码调制（DPCM）差值编码●差分脉冲编码调制原理①在发送端:处理或传输的不是图像中当前样值本身，而是该样值与前一个（相邻）样值的差值，则这些差值绝大多数是很小的或为零，可以用短码来表示，而对那些出现几率较少的较大差值，用长码来表示，则可使总体码数下降。②在接收端:将已得到的前一样值与刚收到的差值相加，就可还原出所要的当前样值。对相邻的样值差值进行变字长编码的方式称为差值编码。第6章多媒体数据压缩技术第三十三页，共62页。6.2.3常用的有损压缩方法（熵压缩）1.差值编码(1)视频信号的空间(帧内)相关性的统计分析①视频图的组成:“像块”、“轮廓”和“细节”“像块”--是图像中成片相同像素组成的块，它的空间相关性最强。“轮廓”---是像块间的分界，它的相关性较差。”细节”---是图像中变化最频繁的细节描述，相关性最小。②统计结果:“像块”要占约90％以上；

“轮廓”和“细节”只占不到10％。（2）时间(帧间)相关性的分析①在静止画面中，其帧间相同位置的样值则100％的相同。②在非静止画面中，相邻帧的不同部分也只是运动物体，只占较小的比例第6章多媒体数据压缩技术第三十四页，共62页。差值编码原理图)1()()(--=DnininiVVVΔVi’(n)=ΔVi(n)+ε(n)Vo(n)=Vo(n-1)+ΔVi(n)+ε(n)第6章多媒体数据压缩技术第三十五页，共62页。●2.差分脉冲编码调制（DPCM）预测编码如图所示：设Xn为实际样值，X^n为其预测值

A：本行前一样值

B：上一行前一样值

C：上一行该点样值

D：前一帧该点样值预测值X^n应为：X^n=F（A，B，C，D）三维预测

第6章多媒体数据压缩技术第三十六页，共62页。预测编码

（2）线性预测上式应为：X^n=KaA+KbB+KcC+KdD其中Ka、Kb、Kc、Kd分别为A、B、C、D的权重或系数。一般有：Ka+Kb+Kc+Kd=1

讨论：①当Kb=Kc=Kd=0，Ka=1时，②当Ka+Kb+Kc=1，Kd=0时，

③当Kd≠0为三维预测，为一维差值预测。为二维预测，即帧内预测。即帧间预测。发送端：ΔXn=Xn-X^n第6章多媒体数据压缩技术第三十七页，共62页。●3.变换编码离散余弦变换1.离散余弦变换（DCT）(1)视频图像的频率特征：低频信号的幅值大，高频信号幅值小。图像信号的能量主要集中于信号的低频分量,而高频分量的能量较小。(2)相关性分析：对于变化复杂的图像来说位置空间的相关性并不明显。(3)DCT变换的方法①分块：将每个分量图像分成许多8×8=64个样点组成的像块，并对其采样，得到在空域中的8×8的样值矩阵。②变换：利用FDCT公式，将空域中的8×8样值矩阵，正向变换（FDCT）为频域中的8×8DCT系数矩阵。第6章多媒体数据压缩技术第三十八页，共62页。FDCT变换

如图示：低频高频第6章多媒体数据压缩技术第三十九页，共62页。a:两个空间的同位置系数无对应关系。b:在频域中的右下角对应高频部分，而在左上角对应低频部分c:DC系数的构成：d:DCT系数的取值范围：在视频数字化中，由于采用8位量化，在空域中的样值的最大值应为256，所以

F（0，0）MAX=DCMAX=256×64/8=2048

故：0≤DC≤2047AC的取值范围：

-1024≤AC≤1023DCyxfFyx==ΣΣ==7070),(81)0,0(第6章多媒体数据压缩技术第四十页，共62页。e:DCT系数规律：低频系数值大，高频系数值小f:对比两个数值矩阵观察相关性f=170132185147190215220185130190175195223199163180220202173197170154160170211185190166140172190193150180140164198180177141172135190163140165132160140160200145135170199190129第6章多媒体数据压缩技术第四十一页，共62页。

f(x,y),F(u,v)矩阵

F=136.2340-48.8294-39.24589.8608-22.631011.6491-63.7071-5.381662.2669-77.255416.1615-12.825535.054023.9713-5.6764-41.699117.5839-17.406925.576026.7426-26.4953-12.8395-10.5650-43.593518.621918.167323.2682-26.082817.795821.602510.09396.4744-9.1274-32.19130.341412.5642-10.6278-7.27107.0297-8.1319-9.276810.067812.2530-9.920210.1096-12.997410.025310.542210.7947

2.3326-29.5610-20.2712-7.353512.19529.65590.2945-8.391312.2379-8.4750-6.515315.882613.3316-2.18192.2038第6章多媒体数据压缩技术第四十二页，共62页。2.DCT系数量化

DCT之后其系数矩阵中相关性不够明显，DCT系数量化是基于限失真编码理论进行的，容许有失真，但应在视觉容许的容限内。视觉要求：

a.对亮度信号与色度信号的分辨能力不同;b.对低频图像信号和高频图像信号的分辨能力不同。结论：可以采用不同的量化方案。量化的方法：区域滤波法：是采用式：Q(U,V)=round[F(U,V)/W(U,V)]对DCT系数矩阵中的每一个值逐一量化。第6章多媒体数据压缩技术第四十三页，共62页。Y量化步长（W）第6章多媒体数据压缩技术第四十四页，共62页。-3-200000-4000000001000000000000000000000000000000000000000000000

Q=Q(U,V)=round[F(U,V)/W(U,V)]第6章多媒体数据压缩技术第四十五页，共62页。3.Zig-Zag扫描：一种将二维数组转变为一维数组的Z字形扫描方法。

(1)Zig-Zag扫描的依据：在量化后的DCT系数矩阵中，非0的数据主要都集中于矩阵的左上角。第6章多媒体数据压缩技术(2)Zig-Zag扫描的方法：Zig-Zag扫描采用的是Z字形扫描方式，从直流分量DC开始进行Z字形扫描。

第四十六页，共62页。-3-200000-4000000001000000000000000000000000000000000000000000000

Q=4.游程（行程）编码

：（参照右边的Z形图走，可得出行程编码值）

5.熵编码：霍夫曼编码（8,1）（-3,1）（3,1）（0,1）（-4,1）（-2,1）（0,6)(1,1)(0,51)第6章多媒体数据压缩技术第四十七页，共62页。JPEG压缩是一种针对静止的连续色调的图像压缩方法，1992年正式称为国际标准。是国际上彩色、灰度、静止图像的第一个国际标准。JPEG标准是一个适合范围广泛的通用标准。它不仅适于静图像的压缩，电视图像序列的帧内图像的压缩编码也常采用JPEG压缩标准。它包括DPCM、DCT的有损压缩及无损压缩两个部分6.3.1JPEG—静止图像压缩标准第6章多媒体数据压缩技术第四十八页，共62页。6.3.2基于DCT编码的JPEG压缩过程

1.分块采样(帧改组)⑴JPEG压缩编码对象：为连续色调静止图像各分量信号进行单独采样。⑵4:2:0格式中各分量信号的采样点数：

PAL制：亮度信号(Y)的有效采样点数为720×576

色差信号（U，V）有效采样点数均为360×288⑶帧改组：采样时,当一帧图像信号输入到编码器时，编码器对其进行的分解处理，称为帧改组。⑷帧改组方法：（亮度信号）第6章多媒体数据压缩技术第四十九页，共62页。①分片：将图像分割成许多横向条(或称“片”)，每条的宽度为16个采样点。

16像素36×1645×16宏区块③分像块：将宏区块再分成4个8×8样点组成的像块。②分段：以16个采样点在横向为一段进行切割,得到16×16个采样点构成的块，称为宏区块。12348×8像块第6章多媒体数据压缩技术第五十页，共62页。④宏块的形成：由4个8×8的亮度(Y)像块组成的宏区块和与之重叠

的两个8×8的色差(U，V)像块，这6个像块组成一个宏块。如图：CRCBYCRY8×8像块8×8像块8×88×88×88×8宏块结构图CB第6章多媒体数据压缩技术第五十一页，共62页。2.FDCT变换由f(x，y),变换为8×8=64个FDCT系数F(u,v)。3.量化（区域滤波法）4.差值编码与Zig-Zag扫描后行程编码5.熵编码并输出数据流1.对DC系数进行差值编码传输：DCn+1-DCn2.AC系数进行Z扫描并行程编码DC=DCn+1-DCn=2已知，DCn=22443443333222111111110…….行程编码：（2,1）（4,2）（3,1）（4,2）（3,4）（2,3）（1,8）（0,43）DC第6章多媒体数据压缩技术第五十二页，共62页。44-2311004-430100043010000-21100000-21000000100000001000000000000000已知，DCn-1=2.求出：

⑴霍夫曼编码⑵平均码长⑶熵一个系数矩阵经过区域滤波法量化后，所得的Q矩阵系数如表所示：

解：DC=DCn-DCn-1=2行程编码为：2第6章多媒体数据压缩技术行程编码：（2,1）（4,3）（-4,1）（-2,1）（3,3）（-2,2）（1,1）（0,2）（1,8）（0，42)第五十三页，共62页。000000000000000000000000000000000000000000练习题：根据下面的已知条件，填写出Q矩阵中的空缺系数第6章多媒体数据压缩技术已知：Q矩阵的行程编码为：（2,1