《毕业设计：多媒体数据压缩算法研究与实现》.doc

多媒体数据压缩算法研究与实现 摘要：多媒体数据压缩技术是实现实时有效地处理、传输和存储庞大的多媒体数据的关键技术。许多应用领域对多媒体信息的实时压缩提出了更高的要求，快速、高效的压缩算法是解决这一问题的关键。针对多媒体数据在空间、时间、结构、视觉、知识等方面所产生的冗余,利用有损压缩和无损压缩等方法,对图像、音频、视频等多媒体数据进行压缩,以保留尽可能少的有用信息。本文主要是把所学的数据结构和算法设计的知识应用于实践，对目前普遍采用的多媒体数据及其压缩算法加以研究，同时介绍了数据压缩所采用的分类、方法及其标准，并分析每种算法的优缺点，并据此选择设计一种多媒体数据的无损压缩算法。并以实例加以说明。 关键词：多媒体;压缩; 哈夫曼编码数据用来记录和传送信息，或者说数据是信息的载体。真正有用的不是数据本身，而是数据所携带的信息。 信息是用不确定的量度定义的，也就是说信息被假设为由一系列的随机变量所代表，它们往往用随机出现的符号来表示。我们称输出这些符号的源为“信源”。也就是要进行研究与压缩的对象。 应该理解这个概念中的“不确定性”、“随机”性、“度量”性，也就是说当你收到一条消息之前，某一事件处于不确定的状态中，当你收到消息后，去除不确定性，从而获得信息，因此去除不确定性的多少就成为信息的度量。比如：你在考试过后，没收到考试成绩（考试成绩通知为消息）之前，你不知道你的考试成绩是否及格，那么你就处于一个不确定的状态；当你收到成绩通知（消息）是 “及格”，此时，你就去除了“不及格”（不确定状态，占50%），你得到了消息——“及格”。一个消息的可能性愈小，其信息含量愈大；反之，消息的可能性愈大，其信息含量愈小。 2．信息量 指从N个相等的可能事件中选出一个事件所需要的信息度量和含量。也可以说是辨别N个事件中特定事件所需提问“是”或“否”的最小次数。 例如：从64个数（1~64的整数）中选定某一个数（采用折半查找算法），提问：“是否大于32？”，则不论回答是与否，都消去半数的可能事件，如此下去，只要问6次这类问题，就可以从64个数中选定一个数，则所需的信息量是6（bit） 我们现在可以换一种方式定义信息量，也就是信息论中信息量的定义。 设从N中选定任一个数X的概率为P(x)，假定任选一个数的概率都相等，即P(x)=1/N，则信息量I(x)可定义为： 上式可随对数所用“底”的不同而取不同的值，因而其单位也就不同。 设底取大于1的整数α，考虑一般物理器件的二态性，通常α取2，相应的信息量单位为比特（bit）；当α=e，相应的信息量单位为奈特（Nat）；当α=10，相应的信息量单位为哈特（Hart）； 显然，当随机事件x发生的先验概率P(x)大时，算出的I(x)小，那么这个事件发生的可能性大，不确定性小，事件一旦发生后提供的信息量也少。必然事件的P(x)等于1， I(x)等于0，所以必然事件的消息报导，不含任何信息量；但是一件人们都没有估计到的事件（P(x)极小），一旦发生后，I(x)大，包含的信息量很大。所以随机事件的先验概率，与事件发生后所产生的信息量，有密切关系。I(x)称x发生后的自信息量，它也是一个随机变量。 现在可以给“熵”下个定义了。信息量计算的是一个信源的某一个事件（X）的自信息量，而一个信源若由n个随机事件组成，n个随机事件的平均信息量就定义为熵(Entropy)。 3．信息熵 信源X发出的xj(j=1,2,……n), 共n个随机事件的自信息统计平均，即求数学期望 H(X)在信息论中称为信源X的“熵”(Entropy) ，它的含义是信源X发出任意一个随机变量的平均信息量。更详细的说，一般在解释和理解信息熵时，有4种样式： （1）当处于事件发生之前，H(X)是不确定性的度量； （2）当处于事件发生之时，是一种惊奇性的度量； （3）当处于事件发生之后，是获得信息的度量； （4）还可以理解为是事件随机性的度量。 例如：以信源X中有8个随机事件，即n=8。每一个随机事件的概率都相等，即P(x1)=P(x2)=P(x3)……P(x8)=1/8，计算信源X的熵。 应用“熵”的定义可得其平均信息量为3比特： 香农信息论认为：信源所含有的平均信息量（熵），就是进行无失真编码的理论极限。 信息中或多或少的含有自然冗余。 4．编码的概念 编码是把代表特定量化等级的比较器的输出状态组合，变换成一个n位表示的二进制数码，即每一组二进制码代表一个取样值的量化电平等级。由于每个样值的量化电平等级由一组n位的二进制数码表示，所以，取样频率f与n位数的乘积nf就是每秒需处理和发送的位数，通常称为比特率或数码率。例如，CD音响的采样频率选用44.1kHz，量化位数n＝16，采用立体声，相应的比特率为： 5．熵编码的概念 如果要求在编码过程中