《多媒体数据压缩与编码.ppt》由会员分享，可在线阅读，更多相关《多媒体数据压缩与编码.ppt（155页珍藏版）》请在三一办公上搜索。
1、1,第10章 多媒体数据压缩与编码,多媒体计算机要处理的信息主要有文字、声音、图形、图像等。其中需要处理的图形与图像信息约占总信息量的85。对多媒体信息进行压缩的目的是减小存储容量和降低数据传输率，使得现有的PC机的指标与性能达到能够处理声音与图像信息的要求，这是多媒体计算机硬件支撑平台所必须具备的功能。在这个过程中，声音与图像信息都需要进行压缩处理。但其中矛盾最突出和最困难的是图像信息压缩，这是因为数字化后图像信息数据量非常大，使得存储与处理都十分困难。数据压缩技术的重要作用在图像信息的压缩方面表现得尤为明显。,2,10.1 数据压缩编码技术概述10.1.1 信息的度量 讨论数据压缩，就要涉
2、及现代科学领域的一个重要分支信息论。信息论有关信息熵的概念对数据压缩有着重要的指导意义，它一方面给出了数据压缩的理论极限，另一方面又指明了数据压缩的技术途径。信息论的创始人香农(C.E Shannon)在他的著名论文通信的数学理论中，从研究通信系统传输的实质出发，对信息作了科学定义，进行了定性和定量的描述。香农认为：信息是有秩序的量度，是人们对事物了解的不确定性的消除或减少。信息是对组织程度的一种测度，信息能使物质系统有序性增强，减少破坏、混乱和噪音。,3,香农提出：信息的传播过程是“信源”(信息的发送者)把要提供的信息经过“信道”传递给“信宿”(信息的接收者)，信宿接收这些经过“译码”(即解
3、释符号)的信息符号的过程。并由此建立了通信系统模型。我们从一则消息中获得了信息，但获得的信息有多少呢？量度信息多少的测度就是信息量。信息的度量反映了人们对于信息的定量认识。根据香农有关信息的定义，信息如何测度呢？显然，信息量与不确定性消除程度有关。消除多少不确定性，就获得多少信息量。用数学语言来讲，不确定就是随机性。不确定性的大小可以直观地看成是事先猜测某随机事件是否发生的难易程度。,4,按照香农的定义，信息量的度量公式可描述为：,它实际上就是后验概率和先验概率之比。在信道无干扰情况下，由信源传来的消息告诉信宿某事件已经发生，则某事件必然发生了。按照概率的定义，对于确定发生的必然事件，其概率为
4、1。这时公式的后验概率为1。,(10.1),5,假设Pi是第i个消息出现的先验概率，则第i个消息的信息量为：,(10.2),6,第i个消息可能有n种状态，那么输出这个消息的总信息量的期望值（即平均信息量）为：,借用热力学的名词，把H叫做熵。它代表接收一个符号所获得的平均信息量。熵是在平均意义上表征信源总体特性的一个物理量。公式(10.3)中，对数的底数理论上可取任何数。当底数为2时，信息的计量单位为比特(bit)，即二进制单位。以上就是香农关于信息的度量。通常也称为概率信息。它是一个科学的定义，有明确的数学模型和定量计算。,(10.3),7,香农公式与日常用语中信息的含义一致。如，设某一事件是
5、在预料中一定会发生的必然事件，若该事件果然发生了，收信者将不会得到任何信息。因为根据公式(10.2)，Pi=1，得:,反之，若某一事件发生的概率很小，即猜测它是否发生的不确定性很大，一旦这个事件发生了，收信者会觉得很意外，感到获得信息量很大。根据公式(10.2)，因为Pi1(表示概率远小于1)，故得：,(10.4),(10.5),8,只有当事件发生与不发生的概率相同时，其信息量才达到最大。香农的信息度量公式排除了对信息的主观含意。根据上述公式，同样一个消息对任何一个收信者来说，所得到的信息量都是一样的。,9,10.1.2 信息的压缩 压缩编码的理论基础是信息论。香农把信息定义为熵的减少。即，信
6、息可定义为用来消除不确定性的东西。从信息论的角度来看，压缩就是去掉信息中的冗余，即保留不确定的信息，去除确定的信息，也就是用一种更接近信息本质的描述来代替原有冗余的描述。所以，将香农的信息论观点运用到图像信息的压缩，所要解决的问题就是如何将图像信息压缩到最小，但仍携有足够信息以保证能复制出与原图近似的图像。,10,图像信息之所以能进行压缩是因为其本身通常存在很大冗余，以视频连续画面为例，每一帧画面由若干个像素组成，因为动态图像通常反映一个连续的过程，相邻帧之间存在很大相关性，从一幅画面到下一幅画面，背景与前景可以没有太多的变化。这些相似的信息为数据压缩提供了基础。另一原因是人的视觉和听觉对某些
7、信号(如颜色，声音)不敏感，致使信息被压缩之后还不知不觉，也不致对压缩后的信息产生误解。正因如此，可在允许保真度的条件下压缩待存储的图像数据，以节省存储空间，图像传输时也大大减少信道的容量，光盘技术和数据压缩技术的发展为各种形式数据的存储和传输提供了技术保证。CPU性能不断提高也为数据压缩提供了有利条件。,11,10.1.3 有损压缩与无损压缩 多媒体数据压缩分为有损压缩和无损压缩。无损压缩算法是为保留原始多媒体对象(包括图像、语音和视频)而设计的。无损压缩中，数据在压缩过程中不会改变或损失，解压缩产生的数据是对原始对象的完整复制。当图像冗余度很少(同类像素重复性很小)时，无损压缩技术得不到可
8、接受的结果。有损压缩会造成一些信息的损失，关键问题是看这种损失对图像质量带来的影响。只要这种损失被限制在允许范围内，有损压缩就是可接受的。有损压缩技术主要应用领域是在影像节目、可视电话会议和多媒体网络这样的由音频、彩色图像和视频组成的多媒体应用中。,12,10.1.4 对称压缩和不对称压缩 压缩技术的基本方式有两种：即对称压缩和不对称压缩。在对称压缩中，压缩算法和解压缩算法是一样的。是一种可逆操作。对称压缩的优点在于双方都以同一种速度进行操作，例如视频会议这种实时传递的系统便采用对称压缩技术。发送方将实况视频信号用某种算法加以压缩，然后通过通信介质进行传输。接收端收到信号后，再使用同样的算法按
9、逆运算解压缩，使图像解码后重现。不对称压缩，是指压缩和解压缩的运算速率是不相同的。例如VCD的制作与播放便是典型的不对称压缩。在制作VCD时，将一部电影压缩到VCD盘片上可能需要花费十几个小时或更多时间，而播放VCD时，为保证视频的流畅，其解压缩的速度却很快。,13,10.1.5 影响数据压缩的几个要素 一个好的压缩方法对多媒体信息的存储和传输是至关重要的，影响压缩性能的主要指标有：压缩比 对压缩前后的文件大小和数据量进行比较，作为压缩率的衡量指标。人们普遍希望压缩的倍数越高越好，压缩的速度越快越好。但同时人们又希望确保数据压缩的精度，即解压缩的数据和原来的数据最好没有差别，没有数据损失。然而
10、追求压缩比率和追求精度往往是矛盾的，因此就需要在这两者之间权衡取舍。,14,图像质量 图像的清晰程度反映出图像的质量。有损压缩可获得较大压缩比，但压缩比过高，还原后的图像质量可能降低。图像质量的评估常采用客观和主观评估两种方法。客观评估是通过一种具体算法来统计多媒体数据压缩结果的损失。如采用纯误差测度，即原始图像与恢复图像之间的简单数学统计。尽管这种方法将误差量化表达，但并不能反映观察者对误差的视觉感知。主观评估基于人的视觉感知，因为观察者作为最终视觉信宿，他们能对恢复图像的质量作出直观的判断。方法之一是进行主观测试，让观察者通过观测一系列恢复图像，并与原图像进行比较，再根据损伤的可见程度进行
11、评级，以判断哪种压缩方法的失真少。,15,传统的客观评价方法由于只对恢复图像和原始图像的纯误差做数学统计，难以反映图像的视觉差别。如果能在客观评估中引入简单的视觉模型，或者误差的结构特性，便能导致与主观测试更符合的结果。主观评估的好处就是使人一目了然，但是主观评判的结果往往和客观评判并不是一一对应的，有的结果相差很大。然而这种方法容易受观察者背景知识、观测动机、观测环境等等因素的限制和影响。所以，在图像处理技术和压缩编码技术飞速发展的今天，能够准确地对图像质量进行主观评估的客观评估（即数学算法）是亟待解决的难题。,16,压缩与解压缩的速度 压缩和解压缩的速度是压缩系统的两项单独的性能度量。在有
12、些应用中，压缩和解压缩都需要实时进行，如电视会议的图像传输。在有些应用中，压缩可以用非实时压缩，而只要解压缩是实时的，如多媒体CD-ROM的节目制作。从目前开发的压缩技术来看，一般压缩的计算量比解压缩要大。压缩速度不仅与采用的压缩方法有关，而且与快速算法的计算量有关，若在算法上有较大突破，无疑将对多媒体的开发与应用产生很大影响。,17,执行的硬件与软件 采用什么样的硬件与软件去执行压缩/解压缩，与采用压缩方案和算法的复杂程度有着密切的关系。设计精巧的简单算法可以在简单的硬件上执行，且执行速度很快。而设计复杂的算法需要在功能强大的软硬件支持下才能运行。但仅靠算法来提高压缩/解压缩的速度还是有限的
13、。在多数情况下，不得不依靠硬件本身提供的功能去完成，例如采用专用多媒体处理芯片。因此在压缩/解压缩系统中，速度和硬件之间的选择显得十分重要。,18,10.1.6 图像编码技术的发展经典编码技术 1948年，Oliver提出了第一个编码理论脉冲编码调制PCM(Pulse Coding Modulation)；同年，Shannon的经典论文“通信的数学原理”首次提出并建立了信息率失真函数概念；1959年，Shannon进一步确立了码率失真理论，奠定了信息编码的理论基础。编码方法主要有预测编码、变换编码和统计编码，也称为三大经典编码方法。经典编码技术又称为“第一代”编码技术。,19,“第一代”视频（
14、图像）编码技术是非常优秀的纹理编码方案，它们能够在中等压缩率的情况下，提供非常好的图像质量，但在非常低的位率情况下，无法为一般的序列提供令人满意的质量。20世纪80年代初，“第一代”编码技术达到了顶峰，这类技术去除客观和视觉冗余信息的能力已接近极限。究其原因是由于这些技术都没有利用图像的结构特点，因此它们也就只能以像素或块作为编码对象，另外，这些技术在设计编码器时也没有考虑人类视觉系统的特性。,20,“第二代”编码方法“第一代”编码技术以信息论和数字信号处理技术为理论基础，旨在去除图像数据中的线性相关性。其压缩比不高，大约在101左右。为了克服“第一代”视频（图像）编码技术的局限性，Kunt等
15、人于1985年提出“第二代”视频（图像）编码技术。“第二代”编码技术不局限于信息论的框架，而是充分利用人的视觉生理、心理和图像信源的各种特征，实现从“波形”编码到“模型”编码的转变，以便获得更高压缩比。其压缩比在30:1至70:1之间。“第二代”编码方法主要有：基于分形的编码、基于模型的编码、基于区域分割的编码和基于神经网络的编码等。,21,“第二代”编码方法充分利用了计算机图形学、计算机视觉、人工智能与模式识别等相关学科的研究成果，为视频压缩编码开拓出了广阔前景。但由于“第二代”编码方法增加了分析的难度，所以大大增加了实现的复杂性。从当前发展情况看，“第二代”编码方法仍处于深入研究阶段。如，
16、分形法由于图像分割、迭代函数系统代码的获得非常困难，因而实现起来时间长，算法非常复杂。模型法则仅限于人头肩像等基本的视频上，进一步的发展有赖于新的数学方法和其他相关学科的发展。神经网络的工作机理至今仍不清楚，硬件研制不成功，所以在视频编码中的应用研究进展缓慢，目前多与其他方法结合使用。但由于巨大压缩性能潜力，人们正致力于这些新方法研究之中。,22,近来，出现了充分利用人类视觉特性的“多分辨率编码”方法，如子带编码和基于小波变换的编码。这类方法使用不同类型的一维或二维线性数字滤波器，对视频进行整体分解，然后根据人类视觉特性对不同频段的数据进行粗细不同的量化处理，以达到更好的压缩效果。这类方法原理
17、上仍属于线性处理，属于“波形”编码，可归入经典编码方法，但它们又充分利用了人类视觉系统特性，因此可被看作是“第一代”编码技术向“第二代”编码技术的过渡。用信息熵H来评价压缩编码在压缩编码中，信息熵H可用于用熵衡量压缩方法的效果，如果信号序列经压缩后，熵H不变，则表明信息量没有下降，这种压缩方法是无损的编码方法，所以无损编码又称为熵(不变)编码。,23,用熵衡量压缩是否为最佳码 如以N表示编码器输出码字的平均码长，则当：NH(X)时，有冗余，不是最佳，有进一步压缩的潜力；NH(X)不可能；N稍大于H(X)时是最佳码。熵值是平均码长N的下限。10.1.7 图像编码技术的标准化 图像编码的研究内容是
18、图像数据压缩，其主要应用领域是图像信息通信和存储。当需要对所传输或存储的图像信息进行高比率压缩时，必须采取复杂的图像编码技术。但是，如果没有一个共同的标准，不同系统间不能兼容。除非每一编码方法的各个细节完全相同，否则各系统间的联结十分困难。,24,鉴于这一情况，20世纪90年代后，国际电信联盟ITU、国际标准化组织ISO和国际电工委员会IEC在全世界范围内积极工作，制定了一系列静止和活动图像编码的国际标准，现已批准的主要有：JPEG标准、MPEG标准、H.261标准等。这些标准和建议是在相应领域工作的各国专家合作研究的成果和经验总结。由于这些国际标准的出现，图像编码尤其是视频图像编码压缩技术得
19、到了飞速发展。目前，按照这些标准做的硬件、软件产品和专用集成电路在市场上大量涌现，对现代图像通信的迅速发展及开拓图像编码新应用领域(如多媒体通信、数字高清晰度电视传输等)发挥了重要作用。随着研究不断深入，还将有新的数据压缩编码标准不断推出。,25,图10.1 是图像压缩编码分类的一般方法,图10.1 图像压缩编码分类的一般方法,26,10.2 预测编码 10.2.1 预测编码的基本概念 预测编码是数据压缩理论的一个重要分支，它是根据离散信号之间存在着一定的相关性，利用前面的一个或多个信号对下一信号进行预测，然后对实际值和预测值的差进行编码。就图像压缩而言，预测编码可分为帧内预测和帧间预测两种类
20、型。,27,帧内预测编码反映了同一帧图像内，相邻像素点之间的空间相关性较强，因而任何一个像素点的亮度值，均可由它相邻的已被编码的像素点的编码值来进行预测。如果能够准确地预测作为时间函数的数据源的下一个输出将是什么，或者数据源可以准确地被一个数据模型表示，则可以准确地预测数据，然而，实际信号源是不可能满足这两个条件的，因此，只能用一个预测器，预测下一个样值，允许它有些误差。通常使用的误差函数是均方误差（mse）：,28,其中：E是数学期望；So是下一样值的实际值；So是下一样值的预测值。若预测根据某一预测模型进行，且模型表达足够好，则只需存储或传输某些起始像素点和模型参数就可以代表整个一幅图像了
21、。这时只要编码很少的数据量，这是极端理想的情况。实际上预测不会百分之百准确，此时可将预测的误差值(实际值与预测值之差值)存储或传输，一般来讲，误差值要比实际值小得多，这样在同等条件下，就可减少数据编码的比特数，从而也减少了存储和传输的数据量，实现了数据的压缩。,29,帧内预测编码典型的压缩方法有差分脉冲编码调制DPCM和自适应差分脉冲编码调制ADPCM等，它们比较适合图像与声音数据的压缩。因为这些媒体的数据均由采样得到，相邻采样值之间的差值都不太大，可用较少的比特数表示差值。预测器是DPCM的核心，预测器越好，能使差值越小，数据压缩就越多，预测器可采用线性预测或非线性预测，通常采用线性预测作为
22、预测器的设计。,30,在MPEG压缩标准中还采用了帧间预测编码。这是由于运动图像各帧之间有很强的时间相关性。例如，在电视图像传送中，相邻帧的时间间隔只有1/30秒，大多数像素的亮度信号在帧间的变化是不大的，利用帧间预测编码技术就可减少帧序列内图像信号的冗余度。此外，电视图像的相邻帧间的内容在一般情况下（除场景切换外）实际上没有太大变化，所以相邻帧间有较大相关性，这种相关性称为时域相关性。运动补偿的目地就是要将这种时域相关性尽可能地去除。,31,10.2.2 差分脉冲编码-DPCM 差分脉冲编码调制DPCM与PCM不同，它编码的不是采样样本值，而是样本值及其预测值的差分，即量化的是已知的样本值与
23、预测值之间的差值。DPCM是从过去的几个采样值的线性组合来预测推断现在的采样值，进而用实际采样值与预测采样值之差（称作预测误差）及线性预测系数进行编码，从而达到信息压缩的一种方法。,32,差分脉冲编码调制的概念如图10.2。差分信号 是离散输入信号 和预测器输出的估算值 之差。注意 是对是 预测值，而不是过去样本的实际值。DPCM系统实际上就是对这个差值 进行量化编码，用来补偿过去编码中产生的量化误差。它实际上是一个负反馈系统，采用这种结构可以避免量化误差的积累。,33,图10.2 DPCM工作原理方框图,34,重构信号 是由逆量化器产生的量化差分信号，与对过去样本信号的估算值 求和得到。以作
24、为预测器确定下一个信号估算值的输入信号。由于在发送端和接收端都使用相同的逆量化器和预测器，所以收发两端可从同一个传送信号 获得相同的量化差分信号 和重构信号。,35,若预测误差不经量化精确地传到接收端，可无失真地复原原始PCM信号。但主观实验表明，对于人眼观看的电视图像来讲，预测误差没必要绝对精确地传到接收方，可以对它再经过一次量化，适当降低精确度，从而获得进一步的码率压缩。这样，虽然由于量化误差的引入造成图像一定程度失真，但若把量化误差限制到主观视觉不能察觉的程度，并不影响图像主观质量。所以，量化器是利用主观视觉特点，挖掘压缩潜力的工具。,36,10.2.3 自适应差分脉冲编码-ADPCM
25、ADPCM是自适应量化和自适应预测方法的总称。ADPCM是在DPCM方法上的进一步改进，通过调整量化步长，对不同频段所设置的量化字长不同，使数据得到进一步的压缩。,37,自适应量化是使量化间隔大小的变化自动地适应输入信号大小变化。它根据信号分布不均匀的特点，使系统具有随输入信号变化而改变量化区间大小，以保持输入量化器的信号基本均匀的能力。自适应量化必须具有对输入信号的幅值进行估计的能力，有了估值才能确定相应的改变量。若估值在信号的输入端进行，称前馈自适应；若在量化输出端进行，称反馈自适应。预测参数的最佳化依赖于信源的统计特性，而按DPCM采用固定的预测参数往往得不到好的性能。自适应预测不是对输
26、入信号幅度绝对值进行编码，而是对样本之间的差值进行编码。差值不是简单地用样本的绝对值之差，而是通过预测技术使求出的预测值与实际值的均方差尽可能地小(如图10.3)。,38,图10.3 ADPCM编码框图,39,10.3 变换编码10.3.1 变换编码的基本方法 变换编码先对信号进行某种函数变换，从信号的一种表示空间变换到信号的另一种表示空间，然后在变换后的域上，对变换后的信号进行编码，其过程如图10.4所示。,图10.4 变换编码的工作过程,40,变换编码的基本方法是将数字图像分成一定大小的子图像块，用某种正交变换对子像块进行变换，得到变换域中的系数矩阵，然后选用其中的主要系数进行量化编码，由
27、于在变换域中信号的能量比较集中，例如图像信号的能量主要集中在低频部分，若只对主要的低频分量进行编码并作合理的比特分配，则可大大压缩数据量。,41,变换编码不是直接对原图像信号压缩编码，而是首先将图像信号进行某种函数变换，从一种信号(空间)映射(变换)到另一个域中，产生一组变换系数，然后对这些系数量化、编码、传输。在空间上具有强相关性的信号、反映在频域上，是某些特定的区域内能量常常被集中在一起，或是变换系数矩阵的分布具有规律性。我们可利用这些规律，在不同的频域上分配不同的量化比特数，从而达到压缩数据的目的。,42,我们知道,模拟图像经采样后,成为离散化的亮度值。假如把整幅图像一次进行变换,则运算
28、比较复杂,所需时间较长。通常把图像在水平方向和垂直方向上分为若干子区,以子区为单位进行变换。每个子区通常有88个像素点，每个子区的全部像素值构成一个空间域矩阵。,43,变换编码是一种有损编码方法，采用不同的变换方式，压缩的数据量和压缩速度都不一样。典型的变换编码有离散余弦变换、KL变换以及近来流行的小波变换等。实践证明，无论对单色图像、彩色图像、静态图像还是运动图像，变换编码都是非常有效的方法，变换编码抗干扰性较好，有比预测编码更高的压缩比，其缺点是易于产生方块效应。,44,10.3.2 变换编码的数学表示 离散变换可以用矩阵表示，设信源序列是一个n行k列的矩阵X，例如，对一幅图像进行扫描，从
29、上到下共n行,从左到右取k个样值。这样形成n个k维的采样向量序列(x1,x2,xn)，其中，xi=(xi1,xi2,xik)是一个k维向量。,45,这n个向量构成n行k列的矩阵X，xij表示第i行第j个样值。假设采用一维变换，设变换后输出序列为Y，变换矩阵为A，则它们之间的关系是：Y=AX 如果所采取的变换为正交变换，变换矩阵为正交变换矩阵，即ATA=A-1A=I，其中AT为A的转置矩阵，T-1为T的逆矩阵，I为单位矩阵，那么：X=ATY 在接收端用变换矩阵的转置矩阵AT与接收序列Y相乘便可恢复源序列X。公式的意义在于：在变换中，空间域中能量全部转移到变换域中。在反变换中，变换域的能量又能全部
30、转移到空间域中。,46,经过变换之后，变换域中总能量不变，但能量将会重新分布。在空间域中，能量分布具有一定的随机性。由于图像有一定的相关性，变换域中能量在大部分情况下，集中于零空间频率或低空间频率对应的变换系数，从而使具有相关性图像的相关性减少。同时由于能量集中于零空间频率和低空间频率所对应的变换域矩阵元素中，我们对这些元素分配较多的比特数，而对能量较少的元素分配较少的比特数或不分配比特数，由于相关性的减少，变换域中分配的总比特数可以比原图像的总比特数少，这样就可以使图像所需传送的比特数减少，达到压缩的目的。,47,10.3.3 离散余弦变换 离散余弦变换DCT(Discrete Cosine
31、 Transformation)具有运算速度快、易于实现等优点，它的快速算法已可由专用芯片来实现，因而被广泛采用。离散余弦变换方法研究较早，技术成熟，图像压缩实践证明DCT是许多图像的最佳变换，它允许将88图像的空间表达式转换为频率域，只需要少量的数据点来表示图像。另外，DCT算法的性能很好，可以进行高效的运算，因此使它在硬件和软件中都容易实现。目前国际上已经制订了基于离散余弦变换的静止图像压缩标准JPEG和运动图像压缩标准MPEG。,48,DCT压缩过程中最关键的步骤是一个称为DCT的数学变换。DCT和著名的快速傅立叶变换(FFT)属于同一类数学运算，这类变换的基本运算是将信号从一种表达形式
32、变成另一种表达形式，并且这种变换过程是可逆的，即在两个变换过程中除开舍入误差和截断误差，本质是无损失的。DCT变换过程相当复杂，对其原理的理解很大程度上取决于对数学理论知识的了解。这里我们不讨论深奥的数学概念，只通过举例说明这个问题。源图像在进行DCT变换之前，首先把源图像划分为若干个88像素的子块，然后对88像素块逐一进行DCT(如图10.5)变换。例如，如果源图像为640480的分辨率(即由640480像素组成),则划分后的图像将包含8060这样多的子块。,49,图10.5 JPEG将源图像划分为若干个子块，每个子块包含88个像素,50,现在我们来理解在DCT处理前后数据发生了哪些变化。图
33、像一般可以用灰度(或彩色)来表示，为讨论问题方便，我们取图像中一个被放大了的88个像素的子块作为示例，如图10.6所示。假设每个像素的灰度值(或颜色值)用8比特来表示，那么共有256个灰度等级(或256种颜色)。这样，我们可以定义一个8行8列的二维数组来表示图像子块中各像素的灰度值和颜色值。于是可得到二维数组矩阵。不失一般性，如果图像是真彩色图像，即每个像素的颜色值需用24比特表示，需要用3个8行8列的数组来表示这个子块。每一个数组表示其中一个8比特组合的像素值。离散余弦变换作用于每一个数组。,51,一个被放大的88个像素的子块,表示图像灰度(或颜色)的矩阵,经过离散余弦变换后的频率系数矩阵T
34、,图10.6 一个88个像素的子块的DCT变换,52,进行离散余弦变换，要用到如下公式：,其中，,否则，,53,公式表明：DCT对一个88的矩阵进行处理，得到一个88的频率系数矩阵。不解释这个公式是怎么来的，它的物理意义是：这个变换的基本运算是将信号从一种表达形式(空间域，即图像的像素值)变成另一种等同的表达形式(频率域，即频率系数)，并且这种变换过程是可逆的。数组T中每个元素称为变换系数，这些系数都有明确的物理意义：如当i=0,j=0时，P00的值称为DC系数，它与数组P的平均值有关。T矩阵的其余的值称为AC系数。随着i和j值的增加，相应系数分别代表逐步增加的水平空间频率分量和垂直空间频率分
35、量的大小。,54,从矩阵中可以看出有一个倾向：随着元素离DC系数越来越远，它的值就越来越小。这意味着通过DCT来处理数据，已将图像的表示集结到输出矩阵的左上角的系数，这个系数就比其他系数携带了更多关于图像的有用信息，同时DCT矩阵的右下部分系数几乎不包含有用信息。由于计算机屏幕上的大多数图像都由低频信息构成，因此这一点是很有意义的。这样，系数越来越小，而且对描述图像越来越不重要。所以说DCT确定了图像的一部分信息，这些信息可被“扔掉”并且不会对图像的质量带来严重影响。在图像未进行变换前要实现这一点是难以想象的，当图像在空间域描述时要找出哪些像素对图像的全貌是重要的，而哪些是不重要的则相当困难。
36、,55,如果离散余弦变换是不可逆运算(即从DCT系数中恢复原始像素信息)，那么这种变换是毫无意义的，事实上，有一个逆离散余弦变换(IDCT)公式能够将频率域的数据重新转换为像素值：,56,DCT(IDCT)算法的计算量比较大(从程序中可以看出，是一个循环的嵌套结构)。如对一幅较高精度的真彩色图像使用JPEG压缩时，大约要进行上亿次运算操作，这对实现JPEG压缩、编码的软件、硬件设备产品提出了较高的要求。早期的JPEG压缩多数做成专用的压缩卡，以专用的高速CPU芯片实现压缩处理，现在通用的计算机CPU速度不断提高的情况下，JPEG压缩也可以用软件来实现。,57,DCT的优点很多，主要表现为：已证
37、明DCT是许多图像的最佳变换;DCT可以将NN图像的空间域转换为频率域，只需少量的数据点表示图像；DCT产生的系数很容易被量化，以获得好的块压缩；DCT算法的性能很好，可以进行高效的运算，因此它在硬件和软件中都容易实现；DCT算法是对称的，逆DCT算法可用来解压缩图像。,58,10.3.4 K-L变换 K-L变换(Karhunen-Loeve)亦称主要成份变换，是一个离散变换。K-L变换从图像统计特性出发，用一组不相关的系数来表示连续信号，实现正交变换。K-L使矢量信号的各个分量互不相关，因而在均方误差准则下，它是失真最小的一种变换，故称作最佳变换。如果图像信号是一个平稳随机过程，K-L变换的
38、效率最高。通过K-L变换之后，所有的系数都是不相关的，并且数值较大的方差仅存于少数系数中，这样就有可能在允许的失真度下，把图像数据压缩到最小。,59,虽然K-L变换是最佳正交变换方法，但是由于它没有通用的变换矩阵，因此对于每一个图像数据都要计算相应的变换矩阵，其计算量相当大，很难满足实时处理的要求。所以实际中较少用K-L变换对图像数据进行压缩。,60,10.3.5 小波变换 今天的影像压缩中，动态影像压缩一般采用MPEG算法，静止影像压缩多采用JPEG算法。MPEG和JPEG均基于DCT。使用DCT进行影像压缩的缺陷在于影像的细节、精细信息损失较多，人工处理的痕迹较明显。一种名叫小波压缩的压缩
39、算法引起了人们的注意。,61,小波分析方法最早是1910年Harr提出的小“波”规范正交基的概念。到20世纪80年代，Stromberg证明了小波函数的存在性，1984年法国地球物理学家Morlet在分析地震波的局部性质时，发现传统的付立叶(Fourier)变换难以达到要求，因而引入小波概念于信号分析中。1987年，Mallat将计算机视觉领域内的多尺度分析的思路引入到小波分析中，小波函数的构造以及信号按小波变换的分解与重构，其相应的算法(称为Mallat算法)有效地应用于图像分析与重构。,62,近年来，小波变换(Wavelet Transformation)倍受科学技术界的重视，它不仅在数学
40、上已形成一个新的分支，而且在应用上(如信号处理、图像压缩、模式识别以及众多的非线性科学领域)被认为是继离散余弦变换之后的一种最具潜力的变换编码技术。由于小波变换具有Fourier变换所没有的时频特性及多分辨率分析，以及它的快速算法(Mallat算法)并不逊色于快速Fourier变换，因而小波变换一经出现，立即引起了人们的关注，成为当前最为热门的一个研究方向。,63,小波变换对图像的压缩类似于离散余弦变换，即都是对图像进行变换，由时域变换到频域，然后再量化，编码，输出。不同之处在于小波变换是对整幅图像进行变换，而不是先对图像进行小区域分割。另外在量化技术上也是采用不同的方法。离散余弦变换是采用一
41、种与人类视觉相匹配的矢量量化表，而小波变换则没有这样的量化表，它主要依据变换后各级分辨率之间的自相似的特点，采用逐级逼近技术实现减少数据存储的目的。,64,利用小波变换技术实现对图像、视频及声音的压缩可以取得极好压缩效果。小波压缩的速度很快，而且其还原的影像质量也更为精细(如图10.7)。MPEG最高压缩比率约为2001，对比之下，小波压缩算法对动态影像的压缩比率为4801，而对静止影像画面的压缩比率也高达3001以上。小波压缩算法的出现，促进了包括Internet上的视频点播、更高容量和更高画质的CDROM影视节目的创作、交互式电视、图书检索和异地远程视讯会议的发展。,65,源图像,小波压缩
42、后重构的图像（压缩比:22:1）,图10.7 小波变换的压缩效果,66,基于小波压缩技术的良好性能，美国生产DSP的著名厂商Analog Devices公司，已开始提供支持小波压缩的编码/解码芯片。Intel公司更是利用小波压缩算法重新设计了它的Indeo视频交互系统。在新的Indeo视频交互系统中，舍弃了原来的压缩技术，而采用了更加复杂的基于小波压缩的算法。,67,综上所述，由于小波变换继承了Fourier分析的优点，同时又克服它的许多缺点，所以它在静态和动态图像压缩领域得到广泛的应用，并且已经成为某些图像压缩国际标准(如MPEG-4)的重要环节。当然，像其他变换编码一样，在压缩比特别高的时
43、候，小波变换压缩量化后的重建图像也会产生几何畸变。由于小波分析克服了Fourier分析的许多弱点，因此它不仅可以用于图像压缩，还可以用于许多其他领域，如信号分析、静态图像识别、计算机视觉、声音压缩与合成、视频图像分析、CT成像、地震勘探和分形力学等领域。总之，可以说凡能用Fourier分析的地方，都可以进行小波分析。小波分析应用前景十分广阔。,68,当前，关于小波变换图像压缩算法的研究和应用都十分活跃。国外一些公司将这种技术用于Internet环境中的图像数据传输，提供商业化的服务，对于缓解网络带宽不足、加快图像信息传播速度起到了很好的推进作用。图文资料数字化必然会产生大量的图像数据,对于高比
44、率图像压缩算法的需求尤为迫切。作为一种优秀的图像压缩算法，小波变换在这一领域具有非常好的应用前景，也应该能够发挥关键性的作用.,69,10.4 统计编码 预测编码和变换编码是根据去除相关性的原理达到压缩数据的目的。数据之所以能够压缩，主要是由于信源发出的信息序列是有记忆的，元素之间存在相关性，去掉它们之间的相关性之后，数据才被压缩的。那么，相互独立的、无相关性的消息序列构成的无记忆信源能否进行压缩呢？我们知道，信源的熵H(X)只有在信源符号出现的概率相等时，才达到它的最大值，即使信源符号之间无相关性，只要它们出现的概率不等，那么其熵H(x)必然小于最大值，即有冗余信息的存在。既然有冗余度存在，
45、当然对这样的信源也能够采用一定的方法进行压缩。,70,统计编码就是根据消息出现概率的分布特性而进行的压缩编码，它有别于预测编码和变换编码。这种编码的宗旨在于，在消息和码字之间找到明确的一一对应关系，以便在恢复时能够准确无误地再现出来，或者至少是极相似地找到相当的对应关系，并把这种失真或不对应概率限制到可容忍的范围内。但不管什么途径，它们总是要使平均码长或码率压低到最低限度。,71,统计编码主要针对无记忆信源（是指信源在不同时刻发出的符号之间是无依赖的，彼此统计独立的），根据信息码字出现概率的分布特征而进行压缩编码，寻找概率与码字长度间的最优匹配。统计编码又可分为定长码和变长码。给单个符号或者定
46、长符号组赋相同长度的码字，这就是所谓的定长编码。如果根据符号出现概率的不同赋予长短不一的码字，这是变长编码(VLC)方案。常用的统计编码有huffman编码、算术编码和行程编码三种。,72,10.4.1 哈夫曼(Huffman)编码 大多数存储数字的信息编码系统都采用位数固定的定长码，即使用相同位数对数据进行编码。如常用的ASCII码，用8位二进制数表示一个英文字符。正象一篇文章中，每个字符出现的频度是不同的。有些字符出现的频率高，有些字符出现的频率低。同样，在一幅图像中，有些图像数据出现的频率高，有些图像数据出现的频率低。如果对出现频率高的数据用较少的比特数来表示，出现频率低的数据用较多的比
47、特数来表示，这样从总的效果看还是节省了存储空间。采用这种办法对数据进行编码时，代码的位数不固定，这种码称为变长码。这种编码思想首先由香农提出，哈夫曼对它提出了改进，用这种方法得到的编码称为哈夫曼码。,73,哈夫曼压缩算法的编码思想如下：将信源符号按概率递减顺序排列；把两个最小的概率加起来，作为新符号的概率；重复步骤与，直到概率和等于1为止；完成上述步骤后，再沿路径返回进行编码。寻找从每一信源符号到概率为1处的路径，每层有两个分支，分别赋予0和1(对概率大的赋予编码0，概率小的赋予编码1，反之亦可，但同一过程中赋值的方法必须一致)，从而得到每个符号的编码。哈夫曼编码示例如图10.8所示,74,信
48、源 概率 哈夫曼码a1 0.25 01 a2 0.20 11a3 0.18 000a4 0.13 100a5 0.10 101a6 0.09 0010a7 0.05 0011,1,图10.8 哈夫曼编码过程,75,对信源进行编码后，形成了一个哈夫曼编码表。在信源的存储与传输过程中必须首先存储或传输哈夫曼编码表。解码时，必须参照这个表才能正确译码。使用哈夫曼编码方法，要精确地统计出每个信源出现的概率，如果没有这个精确统计最终的编码文件就不会太小。所以哈夫曼方法通常要进行两次扫描：第一遍扫描产生统计结果，第二遍扫描完成编码。,76,10.4.2 行程编码 现实中有许多这样的图像，在一幅图像中具有许
49、多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的像素都具有相同的颜色值。在这种情况下就不需要存储每一个像素的颜色值，而仅仅存储一个像素的颜色值，以及具有相同颜色的像素数目即可，或者存储一个像素的颜色值，以及具有相同颜色值的行数。这种压缩编码称为行程长度编码，用RLE(Run Length Encoding)表示，具有相同颜色并且是连续的像素数目称为行程长度。,77,RLE所能获得的压缩比有多大，主要取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，则获得的压缩比就越高。反之，压缩比就越小。译码时按照与编码时采用的相同规则进行，还原后得到
50、的数据与压缩前的数据完全相同，由此可见，RLE是一种无损压缩技术。,78,RLE编码方法特别适用于由计算机生成的图像，对于减少图像文件的存储空间非常有效。许多图形文件和视频文件，如.BMP，.TIF等都使用了这种压缩。然而，RLE对颜色丰富的自然图像就显得力不从心。因为在彩色图像中，同一行上具有相同颜色的连续像素往往很少，而连续几行都具有相同颜色值的情况就更少。如果仍用RLE编码方法，不仅不能压缩图像，反而使原来的图像数据变得更大。但这并不是说RLE编码方案不能用于自然图像的压缩，而是不能单纯使用RLE一种编码方法，需要和其他的压缩编码技术联合使用。,79,10.4.3 算术编码 算术编码是R
