第四章多媒体数据压缩编码技术

2020/2/161第四章多媒体数据压缩编码技术考核目的：考核学生对多媒体数据压缩编码的基本原理和算法、数据压缩编码的分类和方法、多媒体数据压缩编码的国际标准等内容的理解和掌握。考核的知识点：什么是多媒体数据压缩、为什么信息能被压缩、常用的压缩编码和算法（统计编码、预测编码、变换编码）、多媒体数据压缩编码的国际标准JPEG、MPEG-1等内容。2020/2/162•考核要求：•掌握：数据压缩编码的方法、常用的压缩编码和算法、JPEG的原理和实现技术。•理解：量化的原理和量化器的设计、MPEG-1的原理和实现技术。•了解：其它的国际标准等。2020/2/1634.1多媒体数据压缩编码的重要性和分类•你想通过可视通信系统与亲朋好友进行“面对面”的通信吗？•你想通过利用多媒体教学手段在家上学吗？•你想在计算机上亲自体念“海湾战争”吗？•你进入过国家图书馆的Internet多媒体阅览室吗？•你有过在Internet上看美国“9.11”事件的实时新闻报道吗？•你有利用多媒体计算机来控制家中的所有电器的计划吗？•无论你是否有这些想法、或经历，它们赖以实现的技术基础是多媒体数据的压缩技术。2020/2/164一．多媒体数据压缩编码的重要性•压缩的必要性——海量数据的存储与传输的必然要求存储量(Byte)=(采样频率×采样精度×声道数×时间)／8如未经压缩的1分钟立体CD音乐所需的存储量为：(44.1×1000×16)×2×60/8=10584000(B)≈10.1(M)•在多媒体系统中图像和动态视频信息数据量非常之巨大，所需要的存储空间是十分巨大和惊人的。如1GB≈1分钟的彩色电视信号数据。•另外在通信网络上，大多数远程通信网络的速率都在几兆位每秒以下，显然，这样大的数据量不仅超出了计算机的存储和处理能力，更是当前通信信道的传输速率所不及的。••因此，为了存储、处理和传输这些数据，为了使多媒体达到实用水平，除采用新技术手段增加存储空间和通信宽带外，对数据进行有效压缩将是多媒体发展中必须要解决的最关键的技术之一。2020/2/165多媒体信息传送面临的最大难题是海量数据存储与传送电视信号数字化后的数据量问题，数据压缩是解决问题的重要途径。数据的压缩一般由两个过程:一是编码过程（原始数据经过编码进行压缩，存储与传输）;二是解码过程（还原成可用原始数据）2020/2/166二．多媒体数据压缩的可能性1.空间冗余；2.时间冗余；3.信息熵冗余：（1）信息量：指从N个相等的可能事件中选出一个事件所需要的信息度量和含量。（2）信息熵：指一团数据所带的信息量，平均信息量就是信息熵（entropy）。2020/2/167•4.结构冗余•图象有非常强的纹理结构。•5.知识冗余•图像的理解与某些基础知识有关。•6.视觉冗余•视觉冗余是非均匀、非线性的。2020/2/168三．多媒体数据压缩方法的分类1．按压缩方法分:(1)有失真压缩（压缩和解压过程中允许一定的信息损失）(2)无失真压缩2020/2/1692.按编码算法原理分:•（1）预测编码：PCM、DPCM、ADPCM等•（2）变换编码：傅里叶（DFT）、离散余弦（DCT）、离散正弦（DST）等•（3）统计编码：哈夫曼、算术、香农等•（4）静图像编码：方块、逐渐浮现等•(5)电视编码：幀内预测、幀间编码等•(6)其他编码：矢量量化、子带编码等2020/2/16104.2量化量化是指模拟信号到数字信号的映射。量化操作实际上是用有限的离散量代替无限的模拟量的多对一的映射操作。2020/2/1611一．量化原理量化处理是使数据比特率下降的一个强有力的措施。•数据压缩编码中的量化处理，不是指A/D变换后的量化，而是指以PCM码作为输入，经正交变换、差分、或预测处理后，熵编码之前，对正交变换系数、差值或预测误差的量化处理。•量化输入值的动态范围很大，需要以多的比特数表示一个数值，量化输出只能取有限个整数，称作量化级，希望量化后的数值用较少的比特数便可表示。每个量化输入被强行归一到与其接近的某个输出，即量化到某个级。•量化处理总是把一批输入，量化到一个输出级上，所以量化处理是一个多对一的处理过程，是个不可逆过程，量化处理中有信息丢失，或者说，会引起量化误差（量化噪声）。2020/2/1612二．标量量化器的设计1．量化器的设计要求•给定量化分层级数，满足量化误差最小。•限定量化误差，确定分层级数，满足以尽量小的平均比特数，表示量化输出。2．量化方法：•标量量化：•对于PCM数据，一个数一个数地进行量化叫标量量化。•分为：均匀量化、非均匀量化和自适应量化。2020/2/1613三．矢量量化1．矢量量化概念：对PCM数据分组，每组K个数构成一个K维矢量，然后以矢量为单元，逐个矢量进行量化，称矢量量化。2.矢量量化编码方法：有失真编码方法。2020/2/16144.3统计编码•一．统计编码原理——信息量和信息熵基本概念:•（1）信息:是用不确定性的量度定义的。•（2）信息量:从N个相等可能事件中选出一个事件所需要的信息度量或含量。•（3）熵:如果将信源所有可能事件信息量进行平均就得到信息的熵(熵就是平均信息量)。•（4）信源均含有的平均信息量(熵),就是进行无失真编码的理论极限。•（5）信源中或多或少的含有自然冗余。•（6）信息源X的熵为H（X）:式（4.2）2020/2/1615二．哈夫曼编码(Huffman)•1．变字长编码定理:最佳编码定理•在变字长编码中，对于出现概率大的信息符号，编以短字长的码,对于出现•概率小的信息符号编以长字长的码，如果码字长度严格按照符号概率的大小的•相反顺序排列，则平均码字长一定小于按任何其他符号顺序排列方式得到的码•字长度。•证明:（P123）2020/2/1616•2．Huffman编码方法用变字长最佳编码定理•(1)把信源符号按概率大小顺序排列，设法按逆次序分配码字的长度。•(2)在分配码字长度时，将出现概率最小的两个符号的概率相加合成一个概率。•(3)把这个合成概率看成是一个新组合符号地概率，重复上述做法直到最后只剩下•两个符号概率为止。•(4)完成以上概率顺序排列后，再反过来逐步向前进行编码，每一次有三个分支各赋予•一个二进制码，对概率大的赋为零，概率小的赋为1。2020/2/16173.Huffman编码步骤•（1）信源符号按概率大小顺序排列，按逆次序分配码字的长度。•(2）出现概率最小的两个符号概率相加合成一个新概率。•(3）将合成概率看成一个新组合符号概率，重复上述做法，直到最后只剩下两个符号概率为止。•(4)反过来逐步向前编码，每层有两个分支，分别赋予0和1，构成Huffman码字。2020/2/1618•总结：•Huffman编码构造出的码不唯一；•Huffman编码字长参差不齐；•Huffman编码在信源编码概率分布不均匀时效率高，效率比较均匀时，效率低，不用Huffman编码；•对出现频率较高的码分配短码字；•对出现频率较低的码分配长码字。2020/2/1619•三．算术编码•1．原理：•算术编码方法是将被编码的信息表示成实数0和1之间的一个间隔。（图4.9）•信息越长编码表示它的间隙就越小，表示这一间隙所须二进位就越多，•大概率符号出现的概率越大对应于区间愈宽，可用长度较短的码字表示；•小概率符号出现的概率越小对应于层间愈窄，需要长度较长的码字表示。•信息源中连续的符号根据某一模式生成概率的大小来减少间隔。可能出现的符号要比不太可能出现的符号减少范围少，因此只增加了较少的比特位。2020/2/16202.自适应二进制算术编码（1）编码算法举例设编码初始化子区间为[0，1]设大概率MPS，Pe小概率LPSQePe=1-Qe编码时，设置两个专用寄存器（C，A）初始时：令C寄存器的值为子区域的起始位置A寄存器的值为子区域的宽度(该宽度恰好是已输入符号串的概率)初始化时：C=0A=1随着被编码数据源输入，C和A的内容按以下规律修正：当低概率符号LPS到来时：C=CA=AQe当高概率符号MPS到来时：C=C+AQeA=APe=A（1-Qe）（算术编码图4.11）2020/2/1621（2）解码算法举例解码：•按QePe分成两个子区间，判断被解码的码字落在哪个区间，并赋予对应符号：•设c’=（0.0101）b是被解码的值•初始值：A=1Qe=0.001•当c’落在0-QeA之间，解码符号为D=0；C’=C’A=QeA；•当c’落在QeA-A之间，解码符号为D=1；C’=C’-QeA；A=A（1-Qe）(算术解码原理图4.12)2020/2/1622算术编码的特点：(1)不需要码表；(2)当信源概率比较接近时，建议使用算术编码。(3)JPEG成员对多幅图进行算术编码效率可以提高5%。JPEG扩展系统用算术编码代替Huffman。2020/2/16234.4预测编码一．预测编码的基本概念预测编码是统计冗余数据压缩理论的三个重要分支之一，用预测编码减少数据时间和空间的相关性。1.预测编码基本原理2.预测编码方法分类2020/2/1624•线性预测编码(DPCM)•非线性预测编码•1．DPCM差分脉冲编码调制法•DPCM编、解码原理图图4.13•2.ADPCM自适应预测编码•这种编码方法中，量化器的步长和预测器的参数均能根据图象的局部特征作自适应的调整。•ADPCM分成两类•1）线性自适应预测器•2）非线性自适应预测器•引进几个和临近象素有关的值，入i和di非线性改变预测的数。所以，叫非线性的自•适应预测。•采用四点预测2020/2/1625•二．帧间预测编码•对于序列图象，把几帧的图象存起来(大规模集成电路技术的发展)使用帧•间相关性进一步消除图象信号的冗余度，提高压缩比。•帧间压缩方法：•条件补充法•条件次取样法。•运动补偿•帧间预测2020/2/1626•1.条件补充法•条件象素补充法规定：•若帧间各对应象素的亮度差超过阈值，则把这些象素存到缓存区中，•并以恒定传输速度传输，而阈值以下的象素则不传送，在接收端中用上一帧相应的象素代替。•在可视电话中用条件补充法传送的象素只占全部象素的6%左右。•2.条件次取样法•条件补充法和内插法相结合叫条件次取样法。•具体做法：在时间轴采用次取样(两个取一个就是次取样)对于未取样的当前场的•某点可以采用隔场的四邻点亮度的均值，作为该点亮度的预测值。•条件补充：S0=1/4(SA+SB+SC+SD)内•插预测值与实际值之差小于阈值后就不传。2020/2/16273.运动补偿•运动估计有下述三种方法：•(1)块匹配法:以象素块为准进行运动估计。将图象分成M*N个矩形块。在（M+2Wx）*（N+2Wy）范围内进行搜索以求得最优匹配，从而求得运动矢量估值（dx，dy）•(2)象素递归法:以象素为准进行递归的运动估计。•(3)傅立叶变换法•块匹配法2020/2/1628A.匹配算法归一化相关函数NCCF均方误差MSE帧间绝对差MADB.搜索方法：穷尽搜索法二维对数法(TDL)三步搜索法(TTS)交叉搜索法（CSA）2020/2/1629•4.帧间预测，采用DPCM•(Ymn)N和(Ymn)N-1变化很小。•统计结果表明：广播电视节目只有10%以内的象素有变化。•Y有2%的变化；UV有千分之十以内的变化。•Xmn-Xmn=emn只传差值2020/2/16304.5变换编码一.变换编码的特点利用预测编码可以去除图象数据的时间和空间的冗余。它的优点是直观、简捷、易于实现，特别是用于硬件实现。但压缩能力有限，DPCM一般只能压缩到2~4bit/像素。变换编码是进行一种函数变换，映射变换从信号域变换到另一个信号域。例：有两个相邻采样值X1和X2，每一采样值用3bit编码，因此有8个幅度等级，两个为：8*8=64种。变换编码的系统构成：2020/2/1631•二．变换种类K-L变换、离散傅立叶变换、离余弦变换、WALSH变换、Har……4.5.2K-L变换•它是以统计特性为基础的，也称为特征向量变换。•最优的正交变换：特征向量矩阵向量指向数据变化最