《多媒体数据压缩编码》由会员分享，可在线阅读，更多相关《多媒体数据压缩编码（76页珍藏版）》请在金锄头文库上搜索。
1、第2章多媒体数据压缩基础,2.1 数据压缩编码简介 2.2 统计编码 2.3 词典编码 2.4 预测编码 2.5 变换编码,2.1 数据压缩编码简介,2.1.1,数据压缩的必要性,文本: 若1024768显示分辨率、1616点阵文字、4 Byte/字，则一屏汉字的总数据量为: (1024/16)(768/16)4 = 12288 Byte (12KB) 图片：若采用1024768显示分辨率，则满屏图像的总数据量为: 1024768248 = 2359296Byte (2304 KB) 音频： 若采样频率为44100Hz，16bit (2Byte)，立体声 (2声道)， 则1分钟的总数据量为:
2、441002 Byte2 (STEREO) 60s = 10336 KB (10MB) 视频：若图像分辨率为352240，24位色彩，帧率为25帧/秒， 则1分钟的总数据量为: 352240 3 Byte2560s = 371250 KB (362.55MB), ,分钟数字音频信号需要的存储空间,1,分钟数字视频信号需要的存储空间,1,2.1.2 数据压缩的可能性, 数据存在冗余 (重复数据、可忽略数据), 不敏感因素 (颜色、亮度、频率、细节),24 位颜色 (16,777,216色) 8位颜色 (256色),数据冗余,基本概念： 冗余 信息所具有的各种性质中多余的无用内容 冗余度 多余的无
3、用内容的程度,信息量与冗余的关系,I = D du,I 信息量 D 数据量 du 冗余量，包含在D中,数据冗余类型,常见的冗余类型： 1、空间冗余 2、时间冗余 3、结构冗余 4、视觉冗余 5、知识冗余 6、信息熵冗余,1.空间冗余 规则物体的物理相关性,2.时间冗余 视频、动画前后画面间的相关性,3.结构冗余 规则纹理、相互重叠的结构表面,4. 视觉冗余 视觉敏感度非均匀、非线性,5. 知识冗余 凭借经验识别,6. 信息熵冗余,也称编码冗余： 如果表示多媒体内容使用的平均比特数大于该消息的信息熵，则信源中存在冗余，即信息熵冗余。 例如：图像中平均每个像素使用的比特数大于该图像的信息熵，则图像
4、中存在冗余，这种冗余即为信息熵冗余。,2.1.3 数据压缩技术的重要指标, 压缩比: 压缩过程中输入数据量与输出数据量之比, 恢复质量（失真度）: 解压后的恢复效果要好, 算法的复杂性和运算速度,2.1.4 数据压缩编码方法分类,分类方法一：根据解码后是否能够完全无失真地恢复进行分类,1）无损压缩（可逆压缩）冗余压缩 其原理是在压缩时去除或减少冗余值，而在解压缩时重新将这些值插入到数据中，恢复原始数据。 压缩比较低，一般在2：15：1，多用于文本数据的压缩。 典型的编码方法有：香农-范诺码、Huffman编码、算术编码、行程编码、 LZW 编码,2.1.4 数据压缩编码方法分类,分类方法一：根
5、据解码后是否能够完全无失真地恢复进行分类,2）有损压缩 指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。 图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。 典型的编码方法有：PCM 编码、预测编码、变换编码、子带编码等。,2.1.4 数据压缩编码方法分类,分类方法二：压缩编码方法的原理进行分类,1）统计编码: Huffman，Shannon，REL,词典编码 2）预测编码: PCM，DPCM，DM，LPC 变换编
6、码: DCT 子带（sub-band)编码 模型编码,压缩技术分类,通用数据压缩（均为无损压缩）,多媒体数据压缩（无损和有损压缩）,基于统计模型 的压缩技术,基于字典模型 的压缩技术,Huffman 编码,算术编码,LZ77,LZ78,LZW,图像压缩,音频和视频压缩 MPEG等,二值图像 CCITT JBIG等,灰度图像 FELICS JPEG等,彩色图像 RLE编码 JPEG等,矢量图像 PostScript WMF CAD等,压缩技术的应用,电报、传真(CCITT),通讯(Modem/网络协议),存储(压缩池),文件系统(压缩扇区),图像(GIF/TIFF/JPEG),音频(MP3),视
7、频(MPEG/RM),数据库(B+树),归档(TAR/ZIP),密码学(消除数据的原始特征),全文索引(倒排索引表),编译(JAVA),程序设计(算法/空间和时间效率),人工智能(专家系统/知识树),2.2.1 信息熵及基本概念,1信息量 信息量是指从N个相等的可能事件中选出一个事件所需要的信息度量或含量，也就是在辨识N个事件中特定的一个事件的过程中所需要提问“是或否”的最少次数。 设从N个数中选定任一个数xj的概率为p（xj），假定选定任意一个数的概率都相等，即p（ xj ）1/N，因此定义其信息量为:,式中，P(xj)是信源X发出xj的概率。I(xj)的含义是，信源X发出xj这个消息（随机
8、事件）后，接收端收到的信息的量度。,2.2 统计编码,信息熵,熵来源于40年代由Claude Shannon创立的信息论中的一条定理，这一定理借用了热力学中的名词“熵”( Entropy )来表示一条信息中真正需要编码的信息量。 信源S发出的xj（j=1,2,n）共n个随机事件的自信息统计平均，即,H(X)称为信源X的“熵”，即信源X发出任意一个随机变量的平均信息量。 其中：等概率事件信源的熵最大，为：,当P(x1)1时，P(x2)P(x3)P(xj)0，由（4-6）式得此时熵为,由上可得熵的范围为：,在编码中用熵值来衡量是否为最佳编码。若以Lc表示编码器输出码字的平均码长，则当 LcH(S)
9、 有冗余，不是最佳。 LcH(S) 不可能。 LcH(S) 最佳编码（Lc稍大于H(S)）。 熵值为平均码长Lc的下限。,平均码长Lc的计算公式为：,（j=1,2,n）,其中：P(xj) 是信源X发出xj的概率，L(xj)为xj的编码长度。,平均码长与熵关系,熵的计算范例,例：对信息aabbaccbaa，字符串长度为 10，字符a、b、c分别出现了5、3、2次，则,Ia=-log2(0.5)=1比特 Ib=-log2(0.3)=1.737 比特 Ic=-log2(0.2)=2.322 比特,H（S）= 0.5Ia +0. 3Ib +0. 2Ic =1.4855比特/符号,如采用等长编码，则每个
10、字符需要位； 总的码长: L=5*+3* +2* = 位,对比一下，我们用ASCII编码表示该信息需要80位。,基本思想：主要针对无记忆信源，根据信息（符号）出现概率的分布特征进行压缩编码，寻找概率与码字长度之间的最佳匹配: 主要方法：包括哈夫曼编码、算术编码、行程编码等,统计编码原理,2.2.1 哈夫曼编码,哈夫曼1952年提出 主要思想：在变字长编码中，对于出现概率大的信息符号编以短字长的码，对于概率小的符号编以长字长的码。 最佳性：如果码字长度严格按所对应符号出现概率大小逆序排列，则平均码字长度一定小于其他以任何符号顺序排列方式得到的平均码字长度。,1.将符号按出现概率由大到小排列，给最
11、后两个符号赋予一个二进制码，概率大的赋1，小的赋0（反之亦可） 2.把最后两个符号的概率合成一个概率，重复上一步 3.重复步骤2，直到最后只剩下两个概率为止 4.将每个符号所对应的分支的0,1反序排出即可,哈夫曼编码步骤,0.23 0.21 0.18 0.15 0.13 0.07 0.03,概率,0.10,0.23,0.33,0.44,0.56,1,可以看出，概率大的符号其编码短，概率小的符号其 编码长，符号使用其编码来表示，达到数据压缩目的,A1 A2 A3 A4 A5 A6 A7,符号,哈夫曼编码举例,码字的平均长度：,可见，哈夫曼编码结果，其平均长度接近于信息符号的熵值，但是仍有冗余,哈
12、夫曼编码性能分析,信源的信息熵：,哈夫曼编码练习,哈夫曼编码特点,优点：当信源符号概率是2的负幂次方时， Huffman 编码法编码效率达到100%。一般情况下，它的编码效率要比其它编码方法的效率高，是最佳变长码。 缺点：Huffman 码依赖于信源的统计特性，必须先统计得到信源的概率特性才能编码，这就限制了实际的应用。通常可在经验基础上预先提供Huffman码表，此时性能有所下降。,2.2.2 行程编码,最简单的编码方法之一。 主要思想：检测重复出现的比特或字符序列，并用一个单独的值和一个计数值来取代。,行程编码原理,如图所示，假定一幅灰度图像，第n行的像素值为：,用RLE编码方法得到的代码
13、为：3150841160。 代码斜体表示的数字是行程长度，斜体字后面的数字代表像素的颜色值。例如斜体字50代表有连续50个像素具有相同的颜色值，它的颜色值是8。,对比RLE编码前后的代码数可以发现，在编码前要用73个代码表示这一行的数据，而编码后只要用10个代码表示代表原来的73个代码，压缩前后的数据量之比约为7:1，即压缩比为7:1。这说明RLE确实是一种压缩技术，而且编码技术实用。,消零(或消空白)法 将数字中连续的“0”或文本中连续的空白用一个标识符(或特殊字符)后跟数字N(连续“0”的个数)来代替。 如数字序列： 742300000000000000000055 编码为： 7423Z1
14、855,行程编码示例,RLE的性能好坏主要取决于图像本身的特点。RLE压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。 然而，由于颜色丰富的自然图像在同一行上具有相同颜色的连续像素往往很少，而连续几行都具有相同颜色值的连续行数就更少，如果仍然使用RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。 译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。因此，RLE属于无损压缩技术。,行程编码的应用,2.2.3 算术编码（arithmetic coding AC）,20世纪60年代初，Elias提出了算术编码概念；1976年， R
15、issanen和Pasco首次介绍了它的实用技术。 基本原理：将编码的信息序列表示成实数0和1之间的一个间隔(Interval)，信息序列越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。,假设某个字符的出现概率为 80%，该字符事实上只需要 -log2(0.8) = 0.322 个二进制位进行编码。,难道真的能只输出 0.322 个 0 或 0.322 个 1 吗？,算术编码的输出是：一个小数,算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于0和1之间的二进制小数。 例如算术编码对某条信息的输出为1010001111，那么它表示小数0.10100011
16、11，也即十进制数0.64,算术编码,例：假设信源符号为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，如表2-1所示。,表2-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），。,算术编码过程,消息的编码输出可以是最后一个间隔中的任意数，整个编码过程如图4-3所示。最后在0.5
