多媒体技术基础(林福宗)-02数据无损压缩.ppt

第2章 数据无损压缩 第2章 数据无损压缩目录 2.0数据压缩概述(补) 2.1 数据的冗余 2.1.1 冗余概念 2.1.2 决策量 2.1.3 信息量 2.1.4 熵 2.1.5 数据冗余量 2.2 统计编码 2.2.1 香农-范诺编码 2.2.2 霍夫曼编码 2.2.3 算术编码 2.3 RLE编码 2.4 词典编码 2.4.1 词典编码的思想 2.4.2 LZ77算法 2.4.3 LZSS算法 2.4.4 LZ78算法 2.4.5 LZW算法 2.0 多媒体数据压缩概述 2.0 多媒体数据压缩概述 数据压缩的必要性 数据量大 2.0 数据压缩概述 数据压缩必要性 数据量大 2.0 数据压缩概述 数据压缩必要性 数据量大 2.0 数据概述 数据可被压缩的依据 数据本身存在冗余 听觉系统的敏感度有限 视觉系统的敏感度有限 数据压缩类型 无损压缩 有损压缩 2.0 数据压缩概述 数据无损压缩的理论——信息论(information theory) 1948年创建的数学理论的一个分支学科，研究信息的编码、传输和存储 Claude Shannon (香农)发表的“A Mathematical Theory of Communication”论文题目，提议用二进制数据对信息进行编码 最初只应用于通信工程领域，后来扩展到包括计算在内的其他多个领域，如信息的存储、信息的检索等。在通信方面，主要研究数据量、传输速率、信道容量、传输正确率等问题。 2.0 数据压缩概述 数据压缩的可能性 数字化的多媒体数据可以进行数据压缩是基于两种事实 信息的冗余度：多媒体数据中存在大量的冗余，如：300…00(后跟100个0)，可以表示为30(100)，表示3后跟100个0，从而避免大量的重复0。(科学记数法) 2.0 数据压缩概述 数据压缩的可能性 数字化的多媒体数据可以进行数据压缩是基于以下两种事实 人的视觉及听觉等感官特性 视觉特征表现为对亮度信息很敏感而对边缘的急剧变化不敏感 听觉特征表现出对部分音频信号不敏感,如人的听觉具有一个强音能抑制一个同时存在的弱音现象,而且人耳对低频端比较敏感，而对高频端不太敏感 2.1 数据的冗余 冗余概念 人为冗余 在信息处理系统中，使用两台计算机做同样的工作是提高系统可靠性的一种措施 在数据存储和传输中，为了检测和恢复在数据存储或数据传输过程中出现的错误，根据使用的算法的要求，在数据存储或数据传输之前把额外的数据添加到用户数据中，这个额外的数据就是冗余数据 视听冗余 由于人的视觉系统和听觉系统的局限性，在图像数据和声音数据中，有些数据确实是多余的，使用算法将其去掉后并不会丢失实质性的信息或含义，对理解数据表达的信息几乎没有影响 数据冗余 不考虑数据来源时，单纯数据集中也可能存在多余的数据，去掉这些多余数据并不会丢失任何信息，这种冗余称为数据冗余，而且还可定量表达 2.1 数据的冗余 例：信息量、数据量与冗余量 多媒体数据的数据量远远大于其所携带的信息量 例：180个汉字，文本数据量为360B。广播员朗读使用1分钟，数字化时采样频率8000Hz，单声道，8位量化，则数据量为8000×60＝480KB。可见，传递同样信息，语音数据有1300倍冗余 数学描述：I＝D－du I：信息量 D：数据量 du：冗余量 2.1 数据的冗余 信息量(information content) 信源发出的消息是不确定的，与概率有关。 事件发生的概率越小，猜测它有没有发生的困难程度就越大，不确定性就越大，一旦它出现必然使人感到意外，给人的信息量就越大，当消息的概率很小，即几乎不可能的消息出现了，则会给人以巨大的信息量。 对于发生概率等于1的必然事件，就不存在不确定性，不具任何信息量。 例…… 2.1 数据的冗余 信息量 信息论中常用的对数底是2，则信息量的单位是比特(bit)。 如果p(ui)＝0.5, I(ui)=1bit。所以1bit信息量就是两个互不相容的等概率事件之一发生时所提供的信息量。 若取自然对数e为底，则信息量的单位为 (nat)。 若以10为对数底，则信息量的单位为 (hart) 。 2.1 数据的冗余(续2) 信息量(information content) 具有确定概率事件的信息的定量度量 在数学上定义为  其中， 是事件出现的概率 举例：假设X={a,b,c}是由3个事件构成的集合，p(a)=0.5，p(b)=0.25，p(b)=0.25分别是事件a, b和c出现的概率，这些事件的信息量分别为， I(a)=log2(