多媒体压缩编码

第四章多媒体数据压缩编码技术计算机系李知菲本章要点•多媒体数据压缩编码的重要性及分类•常用压缩编码的基本原理及实现技术，预测编码，变换编码（K-L变换，DCT变换），统计编码（Huffman编码，算术编码）。•量化的基本原理及量化器的设计思想•静态图像压缩编码的国际标准（JPEG）原理，实现技术，以及动态图像压缩编码国际标准（MPEG）的基本原理。进入信息时代，人们将越来越依靠计算机获取和利用信息，而数字化后的视频和音频等媒体信息具有数据海量性，与当前硬件技术所提供的计算机存储资源和网络带宽之间具有很大的差距性。这样，就对多媒体信息的存储和传输造成很大的困难。成为阻碍人们有效获取和利用信息的障碍。一段时间内，数字化的媒体信息数据的压缩形式存储和传输仍然是唯一的选择。4．1多媒体数据压缩编码的重要性和分类•4.1.1多媒体数据压缩编码的重要性信息时代的重要特征是信息的数字化，数字化的信息带来了“信息爆炸”。多媒体计算机系统技术是面向三维图形，立体声和彩色全屏幕运动画面的处理技术。数字计算机面临的是数值，文字，语言，音乐，图形，动画，静图像，电视视频图像等多种媒体承载的用模拟量转化成数字量信息的吞吐，存储和传输的问题。数字化了的视频和音频信号数据量之大是非常惊人的，下面列举两例未经压缩的数字化信息的例子：•一页印在B5（约18*25。5cm）纸上的文件，若以中等分辨率（300d/I约12像素点/mm）的扫描仪进行采样，其数据量约6。61MB/页。一片650MB的CD-ROM可存98页。•一个陆地卫星（LandSat-3）的例子（其水平。垂直分辨率分别为2340和3240，4波段，采样精度7位），它的一幅图像的数据量为2340*3240*7*4=212M，按每天30幅计，每天数据量为212*30=6。36GB，每年的数据量高达2300GB。从以上列举的数据例子，可以看出数字化信息的数据量是何等庞大，这样大的数据量，无疑给存储器的存储容量，通信干线的信道传输率以及计算机的速度都增加了极大的压力。彩色视频数据量分析对于电视画面的分辨率640*480的彩色图像，每秒30帧，则一秒钟的数据量为：640*480*24*30=221.12M播放时，需要221Mbps的通信回路。彩色视频数据量分析实时传输：在10M带宽网上实时传输的话，需要压缩到原来数据量的0.045，即0.36bit/pixel。存储：（按1张光盘可存640M计算）如果不进行压缩，1张CD则仅可以存放2.89秒的数据。存2小时的信息则需要压缩到原来数据量的0.0004，即：0.003bit/pixel。传真数据量分析如果只传送2值图像，以200dpi的分辨率传输，一张A4稿纸的数据量为：1654*2337*1=3888768bit=390K按目前14.4K的电话线传输速率，需要传送的时间是：270秒（4.5分）这个问题是多媒体技术发展中的一个非常棘手的瓶颈问题。解决这一问题，数据压缩是行之有效的方法。通过数据压缩手段把信息数据压下来，以压缩形式存储和传输，即紧缩了存储空间，又提高了通信干线的传输效率，同时也使计算机实时处理音频，视频信息，以保证播放出高质量的视频，音频节目成为可能。•数据压缩技术经历了漫长的50余年的发展过程。•早在1948年，Oliver提出了PCM编码理论（PCM编码全名是PulseCodeModulation“脉冲码调制”编码）。该编码理论的提出，标志着数据压缩技术的诞生。•1948年香农（Shannon）在他的经典论文“通信的数学原理”中首次提出并建立了信息率失真函数概念，1959年他又进一步确立了码率失真理论，从而奠定了信息编码的理论基础(第一代)。此后，图像压缩编码理论和方法都有很大发展。4.1.2数据压缩技术的历史及理论基础•主要的编码方法有预测编码、变换编码和统计编码，也称为三大经典编码方法。•D.A.Huffman：1952年第一次发表了(AMethodfortheConstructionofMinimumRedundancyCodes)论文。从此，数据压缩在商业程序中实现并被应用在许多技术领域。•UNIX系统上一个压缩程序COMPACT就是采用的Huffman0阶自适应编码。•80年代初，Huffman编码又在CP/M和DOS系统中实现，其代表程序叫SQ。在数据压缩领域，Huffman的这一论文事实上开创了数据压缩技术新纪元。•60年代、70年代乃至80年代的早期，数据压缩领域几乎一直被Huffman编码及其分支所垄断。如果不是后面将要提到的那两个以色列人，也许我们今天还要在Huffman编码的0和1的组合中流连忘返。•80年代，数学家们不满足于Huffman编码中的某些致命弱点，他们从新的角度入手，遵循Huffman编码的主导思想，设计出另一种更为精确，更能接近信息论中“熵”极限的编码方法——算术编码。可以证明，算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确表达原始信息内容。当然，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，但却要消耗也许几十倍的计算时间。所以算术编码没有使用的软件。•1984年，TerryWelch发表了名为“高性能数据压缩技术”(ATechniqueforHigh-PerformanceDataCompression)的论文，描述了他在SperryResearchCenter(现在是Unisys的一部分)的研究成果。他实现了LZ78算法的一个变种——LZW。LZW继承了LZ77和LZ78压缩效果好、速度快的优点，而且在算法描述上更容易被人们接受,实现也比较简单。•“第一代”图像编码技术是指以信息论和数字信号处理技术为理论基础，旨在去除图像数据中的线性相关性的一类编码技术。这类技术去除客观和视觉冗余信息的能力已接近极限，其压缩比不高，大约在10:1左右。•80年代中期以后，人们对LZ77进行了改进，随之诞生了一批我们今天还在大量使用的压缩程序。HaruyasuYoshizaki(Yoshi)的LHarc和RobertJung的ARJ是其中两个著名的例子。LZ77得以和LZ78、LZW一起垄断当今的通用数据压缩领域。•目前，基于字典方式的压缩已经有了一个被广泛认可的标准，从古老的PKZip到现在的WinZip，特别是随着Internet上文件传输的流行，ZIP格式成为了事实上的标准，没有哪一种通用的文件压缩、归档系统敢于不支持ZIP格式。•70年代末80年代初，人们逐渐意识到，对多数灰度或是彩色图像乃至声音文件，没有必要忠实地保留其所有信息，在允许一定的精度损失的情况下，可以实现更为有效的压缩方法。到80年代末，设计出了一批在压缩效果上让人惊讶不已的声音和图像压缩算法。•第二代”图像编码技术是Kunt等人于1985年提出的。“第二代”并不局限于信息论的框架，要求充分利用人的视觉、生理、心理和图像信源的各种特征，能获得高压缩比的一类编码技术，其压缩比多在30∶1～70∶1之间，有的甚至高达100∶1。第二代编码技术代表性的方法有子带图像编码等。•“第三代”编码技术是指标准化的编码压缩技术在此基础上，国际标准化组织(ISO)和CCITT联合组成了两个委员会：静态图像联合专家小组(JPEG)和动态图像联合专家小组(MPEG)。JPEG的压缩目标是静止图像（灰度的和彩色的），MPEG的目标则是声音和视频。但他们的基本思路是完全一样的，即保留媒体信息中最有规律、最能体现信息主要特征的数据，而略去其他不重要的数据。•对声音、图像、视频等多媒体信息的压缩有两条思路，要么采用成熟的通用数据压缩技术进行压缩，要么根据媒体信息的特性设计新的压缩方法。•GIF压缩比非常高，可以在同一个文件中存储多幅图像从而实现动画效果。知GIF中的图像使用的是LZW!。GIF大概是使用通用压缩技术压缩图像信息的最成功的例子，当然，GIF文件中除了经过LZW压缩的像素信息以外，还保存有图像的各种属性信息以及图像所使用的调色板信息等。GIF精确地保留了原始图像的每一个像素信息，是无损图像压缩的代表。压缩编码的理论基础是信息论。信息论的主要奠基人香农(C．E．Shannon)曾在他的论文中给出了信息的度量的公式，他把信息定义为熵的减少。从信息论的角度来看，压缩就是去掉信息中的冗余，即保留不确定的信息，去除确定的信息（可推知的），也就是用一种更接近信息本质的描述来代替原有冗余的描述。所以，将香农的信息论观点运用到图像信息的压缩，所要解决的问题就是如何将图像信息压缩到最小，但仍携有足够信息以保证能复制出与原图近似的图像。1、信息量和熵压缩编码的理论基础是信息论。从信息论的角度看,压缩就是去掉信息中的冗余,即保留不确定的信息,去除确定的信息(可推知的),也就是用一种更接近信息本质的描述来代替原有冗余的描述。这个本质的东西就是信息量(即不确定因素)。（1）信息量信息量的大小和消息有一定的关系、在数学上，消息是其出现概率的单调下降函数。信息量越大．消息的可能性越小，反之亦然.信息量是指：为了从N个相等的可能事件中挑选出一个事件所需的信息度量和含量，所提问“是或否”的次数.也就是说，在N个事件中辨识特定的一个事件要询间“是或否”多少次．•例如要从256个数中选定某一个数可以先提问“是否大于128？’，不论回答是与否，则半数的可能事件被取消。如果继续询问下去，每次询问将对应一个lbit的信息量。随着每次询问，都将有半数的可能事件被取消，这个过程由下列公式表示：log2256＝8bit•从公式看出，对于256个数的询问只要进行8次，即可确定一个具体的数。设从N个数中选定任意一个数x的概率为产p（x）．假定选定任意一个数的概率都相等，即p（x）=1/N，则信息量为：)]([)(/1)(logloglog222xpIxpNNxI（2）熵的概念•数据压缩不仅起源于40年代由ClaudeShannon首创的信息论，而且其基本原理即信息究竟能被压缩到多小，至今依然遵循信息论中的一条定理，这条定理借用了热力学中的名词“熵”(Entropy)来表示一条信息中真正需要编码的信息量。En=-log2(Pn)（2）熵的概念•信息（熵）、热力学熵和复杂程度是互相成正比例的物理量。一个通讯讯号的复杂程度就是信息（熵）、物质微观状态的复杂程度就是热力学熵。•影子不是物质，但它是物质的一种映射；信息不是物质，但它是物质的复杂程度的映射。•考虑用0和1组成的二进制数码为含有n个符号的某条信息编码，假设符号Fn在整条信息中重复出现的概率为Pn，则该符号的熵也即表示该符号所需的位数位为：•En=-log2(Pn)举个例子，对下面这条只出现了abc三个字符的字符串：aabbaccbaa字符串长度为10，字符a,b,c分别出现了5,3,2次，则abc在信息中出现的概率分别为0.5,0.3,0.2，他们的熵分别为：•Ea=-log2(0.5)=1•Eb=-log2(0.3)=1.737•Ec=-log2(0.2)=2.322整条信息的熵也即表达整个字符串需要的位数为：E=Ea*5+Eb*3+Ec*2=14.855位（2）熵的概念•如果用计算机中常用的ASCII编码，表示上面的字符串我们需要整整80位呢！现在知道信息为什么能被压缩而不丢失原有的信息内容了吧。简单地讲，用较少的位数表示较频繁出现的符号，这就是数据压缩的基本准则。信源的概率分布与熵的关系当信源中各事件是等概率分布时，熵具有极大值。信源的相关性与序列熵的关系若序列中各符号具有相同的概率分布，该序列是平稳的。若序列中各符号间是统计独立的，即前一个符号的出现不影响以后任何一个符号出现的概率，则该序列是无记忆的。信源的相关性与序列熵的关系•显然两个事件的相关性越小，残剩的不肯定性便越大，当两事件相互独立时，X的出现，丝毫不能解除Y的不肯定性。在这种情况下，联合熵变为2个独立熵之和，从而达到它的最大值。•结论：信源的冗余度越小，即每个符号所独立携带的信息量越大，那么传送相同的信息量所需要的序列越