多媒体数据压缩算法研究与实现

多媒体数据压缩算法研究与实现摘要：多媒体数据压缩技术是实现实时有效地处理、传输和存储庞大的多媒体数据的关键技术。许多应用领域对多媒体信息的实时压缩提出了更高的要求，快速、高效的压缩算法是解决这一问题的关键。针对多媒体数据在空间、时间、结构、视觉、知识等方面所产生的冗余,利用有损压缩和无损压缩等方法,对图像、音频、视频等多媒体数据进行压缩,以保留尽可能少的有用信息。本文主要是把所学的数据结构和算法设计的知识应用于实践，对目前普遍采用的多媒体数据及其压缩算法加以研究，同时介绍了数据压缩所采用的分类、方法及其标准，并分析每种算法的优缺点，并据此选择设计一种多媒体数据的无损压缩算法。并以实例加以说明。关键词：多媒体;压缩;哈夫曼编码.1.多媒体数据类型1.1文字在现实世界中，文字是人与计算机之间进行信息交换的主要媒体。文字主要包括西文与中文。在计算机中，文字用二进制编码表示，即使用不同的二进制编码来代表不同的文字。1.2音频音频（Audio）指的是20HZ～20kHz的频率范围，但实际上“音频”常常被作为“音频信号”或“声音”的同义语，是属于听觉类媒体，主要分为波形声音、语音和音乐。1.3视频媒体能够利用视觉传递信息的媒体都是视频媒体。位图图像、矢量图像等都是视频媒体。1.4动画动画是指运动的画面，动画在多媒体中是一种非常有用的信息交换工具。动画之所以成为可能，是因为人类的“视觉暂留”的生理现象。用计算机实现的动画有两种，一种是帧动画，另一种是造型动画。2.数据压缩基本原理2.1信息、数据和编码数据是用来记录和传送信息，或者说数据是信息的载体。真正有用的不是数据本身，而是数据所携带的信息。数据压缩的理论基础是信息论。数据压缩技术是建立在信息论的基础之上的。数据压缩的理论极限是信息熵。而信息熵有两个基本概念作铺垫，这两个基本概念就是信息、信息量。首先第一个概念“信息”。1．信息信息是用不确定的量度定义的，也就是说信息被假设为由一系列的随机变量所代表，它们往往用随机出现的符号来表示。我们称输出这些符号的源为“信源”。也就是要进行研究与压缩的对象。应该理解这个概念中的“不确定性”、“随机”性、“度量”性，也就是说当你收到一条消息之前，某一事件处于不确定的状态中，当你收到消息后，去除不确定性，从而获得信息，因此去除不确定性的多少就成为信息的度量。比如：你在考试过后，没收到考试成绩（考试成绩通知为消息）之前，你不知道你的考试成绩是否及格，那么你就处于一个不确定的状态；当你收到成绩通知（消息）是“及格”，此时，你就去除了“不及格”（不确定状态，占50%），你得到了消息——“及格”。一个消息的可能性愈小，其信息含量愈大；反之，消息的可能性愈大，其信息含量愈小。2．信息量指从N个相等的可能事件中选出一个事件所需要的信息度量和含量。也可以说是辨别N个事件中特定事件所需提问“是”或“否”的最小次数。例如：从64个数（1~64的整数）中选定某一个数（采用折半查找算法），提问：“是否大于32？”，则不论回答是与否，都消去半数的可能事件，如此下去，只要问6次这类问题，就可以从64个数中选定一个数，则所需的信息量是6（bit）我们现在可以换一种方式定义信息量，也就是信息论中信息量的定义。设从N中选定任一个数X的概率为P(x)，假定任选一个数的概率都相等，即P(x)=1/N，则信息量I(x)可定义为：2221()logloglog()NIxNPx上式可随对数所用“底”的不同而取不同的值，因而其单位也就不同。设底取大于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个随机事件的自信息统计平均，即求数学期望11()()()()()()log()jnnjajjjIxHxEPxIxPxPx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比特：8111()log2388jHxbits香农信息论认为：信源所含有的平均信息量（熵），就是进行无失真编码的理论极限。信息中或多或少的含有自然冗余。4．编码的概念编码是把代表特定量化等级的比较器的输出状态组合，变换成一个n位表示的二进制数码，即每一组二进制码代表一个取样值的量化电平等级。由于每个样值的量化电平等级由一组n位的二进制数码表示，所以，取样频率f与n位数的乘积nf就是每秒需处理和发送的位数，通常称为比特率或数码率。例如，CD音响的采样频率选用44.1kHz，量化位数n＝16，采用立体声，相应的比特率为：44.11628176.4/kHzkBs5．熵编码的概念如果要求在编码过程中不丢失信息量，即要求保存信息熵，这种信息保持编码又叫做熵保存编码，或者叫熵编码。熵编码是无失真数据压缩，用这种编码结果经解码后可无失真地恢复出原数据。2.2数据压缩的条件在多媒体信息中包含大量冗余的信息，把这些冗余的信息去掉，就实现了压缩。数据压缩技术有3个重要指标：一是压缩前后所需的信息存储量之比要大；二是实现压缩的算法要简单，压缩、解压缩速度快，尽可能地做到实时压缩和解压缩；三是恢复效果要好，要尽可能完全恢复原始数据。2.3数据冗余1．冗余的基本概念多媒体技术最大难题是海量数据存储与电视信号数字化后的数据量传送。数字化后的数据量与信息量的关系为：IDdu其中：I——信息量,D——数据量,du——冗余量由上式可以知道，传送的数据量中有一定的冗余数据信息，即信息量不等于数据量，并且信息量要小于传送的数据量，因此这使得数据压缩能够实现。2．冗余的分类一般而言，图像、音频数据中存在的数据冗余类型主要有如下几种。(1)空间冗余。这是图像数据经常存在的一种冗余。在同一幅图像中，规则物体和规则背景的表面特性具有相关性，这些相关性的光成像结构在数字化图像中就表现为数据冗余。(2)时间冗余。时间冗余在图像序列中就是相邻帧图像之间有较大相关性，一帧图像中的某物体或场景可以由其他帧图像中的物体或场景重构出来，音频的一个连续的渐变过程中，也存在同样的时间冗余。(3)信息熵冗余。信源编码时，当分配给某个码元素的比特数使编码后单位数据量等于其信源熵，即达到其压缩极限。但实际中各码元素的先验概率很难预知，比特分配不能达到最佳，实际的单位数据量大于信源熵时，便存在信息熵冗余。(4)视觉冗余。人眼对于图像场的注意是非均匀的，人眼并不能觉察图像场的所有变化。事实上人类视觉的一般分辨率为26灰度等级，而一般图像的量化采用的是28灰度等级，即存在着视觉冗余。(5)听觉冗余。人耳对不同频率的声音的敏感性是不同的，并不能察觉所有频率的变化，对某些频率不必特别关注，因此存在听觉冗余。(6)结构冗余。图像一般都有非常强的纹理结构。如草席图像，纹理一般都是比较有规律的结构，因此在结构上存在冗余。(7)知识冗余。图像的理解与某些基础知识有很大的相关性。例如，人脸的图像有同样的结构：嘴的上方有鼻子，鼻子上方有眼睛，鼻子在正脸图像的中线上等。这些规律性可由某些基础知识得到，此类冗余为知识冗余。(8)其他冗余。多媒体数据除了上述冗余类型外，还存在其他一些冗余类型，如由图像非定常特性所产生的冗余等。3.数据压缩标准数据压缩是多媒体通信中的核心技术之一,数据压缩研究中应注意的问题是，首先，编码方法必须能用计算机或硬件电路高速实现；其次，要符合当前的国际标准。为此,国际上制定了很多与之相关的数据压缩标准,主要可分为三类:音频压缩标准,二值和静止图像压缩标准,以及视频压缩标准。3.1音频数据的压缩标准音频信号是多媒体信息的重要组成部分。音频信号可以分为电话音频信号、调幅广播音频信号和高保真的立体声音信号。前两种单频信号的压缩技术比较成熟,例如,ADPCM、CELP和子带编码等。国际电报电话咨询委员会（CCITT）和国际标准化组织（ISO）先后提出一系列有关音频编码的建议，CCITT(现更名为ITU2T)已为这两种音频信号的压缩编码制定了一些国际标准。1.G.711标准1972年CCITT(现更名为ITU2T)为电话质量和语音压缩制定了PCM标准G.711。其速率为64kbit/s,使用非线性量化技术,其质量相当于12比特线性量化。2.G.721标准1984年CCITT制定了G.721标准,使用自适应差分PCM编码(ADPCM),其速率32kbit/s。ADPCM是一种对中等质量音频信号进行高效编码的有效算法之一,它不仅适用于语音压缩,而且也适用于调幅广播质量的音频压缩和CD2I音频压缩等应用。3.G.722标准1988年CCITT为调幅广播质量的音频信号压缩制定了G.722标准,它使用子带编码方案,用滤波器将输入信号分成高低两个子带信号,然后分别使用ADPCM进行编码,经复用后形成输出码流。G.722标准也提供数据插入功能,这样音频码流与所插入的数据一起形成比特流。G.722能将224kbit/s的调幅广播质量的音频信号压缩为64kbit/s,主要用于视听多媒体和会议电视等。4.G.728标准为了进一步降低语音压缩的速率,1991年CCITT制定了G.728标准,使用基于短延时码本激励线性预测编码(LD2CELP)算法,其速率为16kbit/s,其质量与32kbit/s的G.721标准相当。5.MPEG21音频编码MPEG21音频编码是国际上制定的第一个高保真立体声音频编码标准(ISO1117223)。通过对14种音频编码方案的比较测试,最后选定了以MUSICAM(MaskingPatternUniversalSubbandIntegratedCodingAndMultiplexing)为基础的三层编码结构。根据不同的应用要求,使用不同的层来构成其音频编码器。在MPEG21中音频编码的1、2层称之为MUSICAM。MUSICAM使用了以下技术:子带滤波器先将输入的数字音频信号分成32个子带。在每个子带中,确定一段信号中的最大电平,由此得到比例因子这一编码参数。由于比例因子的相对变化很小,因此采用差分熵编码方法。根据人耳的掩蔽效应确定掩蔽门限,据此自适应地分配比特,以达到高效压缩音频数据。最后,将音频压缩数据、比例因子和比特分配信息按帧结构组合在一起,形成音频比特流。6.MPEG22音频编码在MPEG21音频编码中,MUSICAM只能传送左右两个声道。为此,MPEG扩展了低码率多声道编码,将多声道扩展信息加到MPEG21音频数据帧结构的辅助数据段(其长度没有限制)中。这样可将声道数扩展至5.1,即3个前声道(左L、中C和右R)、2个环绕声(左LS、右RS)和1个超低音声道LFE(常称之为0.1)。由此,形成了MPEG22音频编码标准SO