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

第七章多媒体数据压缩技术多媒体数据压缩技术已成为当今数字通信、广播、存储和多媒体娱乐中的一项关键的共性技术。4.1多媒体数据压缩概述4.2数据压缩的技术基础4.3常用的无损数据压缩方法4.4常用的有损数据压缩方法4.5数据压缩国际标准第七章多媒体数据压缩技术4.1多媒体数据压缩概述4.1.1多媒体数据压缩的必要性⑴原始采样的媒体数据量巨大⑵有效利用存储器存储容量⑶提高通信线路的传输效率⑷消除计算机系统处理视频I/O瓶颈第七章多媒体数据压缩技术4.1.2多媒体数据压缩的可能性常见的图像数据冗余种类：•⑴空间冗余：静态图像中存在的最主要的一种数据冗余。•⑵时间冗余：运动图像中经常包含的冗余。•⑶结构冗余：在某些场景中，存在着明显的图像分布模式，称作结构。图像中重复出现或相近的纹理结构，结构可以通过特定的过程来生成。第七章多媒体数据压缩技术•⑷知识冗余：这类规律性的结构可以由经验知识和背景知识得到。•⑸视觉冗余：人眼对亮度变化敏感，对色度的变化相对不敏感；在高亮度区，人眼对亮度变化敏感度下降；对物体边缘敏感，内部区域相对不敏感；对整体结构敏感，而对内部细节相对不敏感。第七章多媒体数据压缩技术•⑹图像区域的相同性冗余：图像中的两个或者多个区域所对应的所有像素值相同或者相近，从而产生数据重复性存储。•⑺纹理的统计冗余：有些图像纹理尽管不严格服从某个分布规律，但是在统计意义上服从这种规律。利用这种性质可以减少表示图像的数据量，所以被称为纹理的统计冗余。第七章多媒体数据压缩技术•4.1.3多媒体数据压缩的原理•1.图像压缩系统的组成•由三部分组成：变换器、量化器和编码器。第七章多媒体数据压缩技术•2.图像压缩说明•视频压缩与语音相比，语音的数据量较小，且基本压缩方法已经成熟，目前的数据压缩研究主要集中于图像和视频信号的压缩方面。•压缩处理过程有两个过程，编码过程是将原始数据经过编码进行压缩，以便存储与传输；解码过程是对编码数据进行解码，还原为可以使用的数据。第七章多媒体数据压缩技术•3.与压缩相关的指标•衡量一种数据压缩技术的好坏有四个重要的指标：•⑴压缩比大：即压缩前后所需要的信息存储量之比要大。•⑵算法简单：实现压缩的算法简单，压缩、解压速度快，尽可能地做到实时压缩解压。•⑶恢复效果好：恢复效果好，要尽可能地恢复原始数据。•⑷压缩能否用硬件实现。第七章多媒体数据压缩技术•4.1.4数据压缩方法的分类第七章多媒体数据压缩技术•⑴冗余压缩法•也称无损压缩法，是指使用压缩后的数据可以解压缩，且解压之后的数据与原来的数据完全相同。它利用数据的统计冗余进行压缩，可完全恢复原始数据而不引入任何失真，但压缩率受到数据统计冗余度的理论限制，一般为2:1到5:1。第七章多媒体数据压缩技术•⑵熵压缩法•也称有损压缩法，有失真压缩，是指使用压缩后的数据进行解压缩，解压之后的数据与原来的数据有所不同，但不会让人对原始资料表达的信息造成误解。第七章多媒体数据压缩技术•⑶熵压缩法与冗余压缩法的比较•在图像压缩系统组成中，变换和编码是无损耗的，而量化是有损耗的。无损压缩方法仅利用了统计冗余，而没有利用量化器。有损压缩方法既利用了统计冗余又采用了量化器，利用了心理视觉冗余。第七章多媒体数据压缩技术•根据压缩方法的原理，可将其具体划分为以下几种：•⑴量化与向量量化编码•⑵预测编码•⑶变换编码•⑷信息熵编码•⑸混合编码第七章多媒体数据压缩技术4.2数据压缩的技术基础•4.2.1熵的概念•表示一条信息中真正需要编码的信息量，即数据压缩的理论极限。对于任何一种无损数据压缩，最终的数据量一定大于信息熵，数据量越接近于熵值，说明其压缩效果越好。第七章多媒体数据压缩技术•信息熵如何计算：在计算机内部是用二进制来表示数据的，现在要用0和1组成的二进制数码来为含有n个符号的某条信息编码，假设符号Fn在整条信息中重复出现的概率为Pn，则该符号的熵En也即表示该符号所需的位数为：•En=log2(1/Pn)=-log2(Pn)•整条信息的熵E也即表示整条信息所需的位数为：E=∑En第七章多媒体数据压缩技术•4.2.2数据压缩模型——主要有：•静态统计模型：预先扫描文件中的所有字符，统计出每个字符出现的概率。•自适应模型；在信息被输入之前对信息内容一无所知并假定每个字符的出现概率均等，随着字符不断被输入和编码，统计并纪录已经出现过的字符的概率并将这些概率应用于对后续字符的编码。•字典模型：第七章多媒体数据压缩技术•4.2.3数据压缩编码•压缩=模型+编码第七章多媒体数据压缩技术•4.3常用的无损数据压缩方法•4.3.1香农-范诺与哈夫曼编码•1.香农-范诺编码——算法步骤：•⑴将待编码的符号按符号出现概率从大到小进行排序。•⑵将排好序的符号分成两组，使这两组符号概率和相等或尽可能的相近。•⑶将第一组赋值为0，第二组赋值为1。•⑷对每一组，只要不是一个符号，就重复步骤2的操作，否则操作完毕。第七章多媒体数据压缩技术•例4-1有一串由6个字母组成的长度为50的字符串，字母分别A、B、C、D、E和F，其中A出现3次，B出现5次，C出现15次，D出现11次，E出现12次，F出现4次，请使用香农-范诺对其进行编码。第七章多媒体数据压缩技术•解题步骤：•⑴使用下表列出字母在字符串中的概率统计•⑵首先对符号按出现次数的多少进行排序，得下表所示。第七章多媒体数据压缩技术•⑶然后对符号进行分组，将其分为概率和最接近的两组即为（C、E）和（D、B、F、A），其中（C、E）赋值为0，（D、B、F、A）赋值为1，依次递归下去。使用二叉树左支为0，右支为1来进行编码，其最终实现如图所示。•⑷使用香农-范诺编码算法得到的编码表，如下表所示。第七章多媒体数据压缩技术•⑸总共需要4×3+3×5+2×15+2×11+2×12+4×4=119位，而如果用ASCII来进行表示的话，至少要用到50×8=400位；如果用等长码3位二进制来表示六个字母的话，这样需用到50×3=150位，从这两方面都实现数据压缩。•⑹再来看一看压缩效果如何，这时就需来计算数据压缩的极限—熵的值：第七章多媒体数据压缩技术•2.Huffman编码——算法步骤：•⑴初始化，根据符号出现的次数按由大到小顺序对符号进行排序。•⑵把概率最小的两个符号组成一个节点，节点为两符号次数之和，去掉已取出的两个节点，加入这两节点之和，重新排序，直至只有一个数据且该数据的值所有符号出现的总次数相同为止，跳向(4)步骤。第七章多媒体数据压缩技术•⑶重复步骤2，得到新节点，形成一棵“树”。•⑷从根节点开始到相应于每个符号的“树叶”，从上到下标上“0”或“1”。通常左支标为0，右支标为1。•⑸从根节点开始顺着树枝到每个叶子分别写出每个符号的代码。第七章多媒体数据压缩技术•例4-2就上面关于Shannon-Fano编码的例子，现对其使用Huffman进行编码。•解题步骤：•⑴首先按照符号出现的概率有大到小排序，如表下所示。•⑵然后选择其中最小的两个符号，组成一个节点，如图所示。第七章多媒体数据压缩技术•⑶去掉刚才的两个符号，加入它们的和，重新排序如下表所示。•⑷继续选择其中最小的两个符号，组成一个新节点，如图所示。•⑸依次类推，进行递归，排序如下表所示。•生成的二叉树如图所示。第七章多媒体数据压缩技术•⑹依次类推，进行递归，排序如下表所示。•生成的二叉树如图所示。•⑺依次类推，进行递归，排序如下表所示。•生成的二叉树如图所示。第七章多媒体数据压缩技术•⑻对其进行编码，左为0，右为1，如图所示。•⑼使用Huffman编码算法得到的编码表，如下表所示。•⑽总共需要4×3+3×5+2×15+2×11+2×12+4×4=119位，与香农-范诺编码算法得到的最后数据相同，也同样实现了压缩，但通常情况下哈夫曼编码比香农-范诺编码的效率要高一些。第七章多媒体数据压缩技术•3.香农-范诺编码和huffman编码•⑴平均码长=熵，但都是接近熵，而且越接近熵，说明压缩效率越高。•⑵保证解码的唯一性，短字码不构成长字码的前缀。•⑶在接收端需要一个与发送端相同的代码表。第七章多媒体数据压缩技术•4.3.2算术编码•算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔，取间隔中的一个数来进行表示消息，消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。第七章多媒体数据压缩技术•1.自适应统计模型的算术编码与解码•例7-3假设某条信息中可能出现的字符只有a、b、c三种，要压缩保存的信息为abba。•解题步骤：第七章多媒体数据压缩技术•2.静态统计模型的算术编码与解码•例4-4：假设信源符号为{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]，其中[x，y]表示半开放间隔，即包含x不包含y。上面的信息表示在下表中统计了每个符号的概率和初始编码间隔。第七章多媒体数据压缩技术•如果二进制消息序列的输入为：cadacdb。编码时首先输入的符号是c，找到它的编码范围是[0.5，0.7]。由于消息中第二个符号a的编码范围是[0，0.1]，因此它的间隔就取[0.5，0.7]的第一个十分之一作为新间隔[0.5，0.52]。依此类推，编码第3个符号d时取新间隔为[0.514，0.52]，…。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图所示。第七章多媒体数据压缩技术•这个例子的编码过程表示在下表中。第七章多媒体数据压缩技术•这个例子的译码过程表示在下表中。第七章多媒体数据压缩技术•3.算术编码的特点•算术编码的模式选择直接影响编码效率，有固定模式，也有自适应模式。•算术编码的自适应模式无需先定义概率模型，对无法进行概率统计的信源合适，在这点上优越于哈夫曼编码。•在信源符号概率接近时，算术编码比哈夫曼编码效率高。•算术编码的硬件实现比哈夫曼编码要复杂些。算术编码在JPEG的扩展系统中被推荐代替哈夫曼编码。第七章多媒体数据压缩技术•4.在算术编码中有几个问题需要注意•由于实际的计算机精度不可能无限长，运算中出现溢出是一个明显的问题，可使用比例缩放方法解决。•算术编码器对整个消息只产生一个码字，这个码字是在间隔[0，1]中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。•算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。第七章多媒体数据压缩技术•4.3.3行程RLE编码•行程编码是一种统计编码，该编码属于无损压缩编码。对于二值图有效。•它的基本原理是：用一个符号值或串长代替具有相同值的连续符号，使符号长度少于原始数据的长度。•行程编码可以分为定长和变长行程编码两种方式。•行程编码一般不直接用于多灰度图像(彩色图像)中，比较适用于二值图像的编码，如传真图像的编码。第七章多媒体数据压缩技术•4.3.4词典编码•LZW是词典编码的一种。•基本原理是首先建立一个字符串表，把每一个第一次出现的字符串放入串表中，并用一个数字来表示，这个数字与此字符串在串表中的位置有关，将这个数字存入压缩文件中，如果这个字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中。压缩完成后将串表丢弃。第七章多媒体数据压缩技术•4.4常用的有损数据压缩方法•4.4.1预测编码•预测编码是根据离散信号之间存在着一定关联性的特点，利用前面一个或多个信号对下一个信号进行预测，然后对实际值和预测值的差（预测误差）进行编码。第七章多媒体数据压缩技术•1.脉冲编码调制PCM第七章多媒体数据压缩技术•均匀量化：采用相等的量化间隔处理采样得到的信号值。第七章多媒体数据压缩技术•非均匀量化：对输入信号进行量化时，大的输入信号采用大的量化间隔，小的输入信号采用小的量化间隔，这样就可以在满足精度要求的情况下用较少的位数来表示。第七章多媒体数据压缩技术•2.差分脉冲编码调制DPCM•不对每一样值都进行量化，而是预测下一样值，并量化实际