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

《多媒体数据压缩算法研究与实现..pdf》由会员分享，可在线阅读，更多相关《多媒体数据压缩算法研究与实现..pdf（21页珍藏版）》请在三一文库上搜索。

1、多媒体数据压缩算法研究与实现 摘要：多媒体数据压缩技术是实现实时有效地处理、传输和存储庞大的多媒体数据的 关键技术。 许多应用领域对多媒体信息的实时压缩提出了更高的要求，快速、 高效的压缩算 法是解决这一问题的关键。针对多媒体数据在空间、时间、结构、视觉、知识等方面所产生 的冗余 ,利用有损压缩和无损压缩等方法,对图像、音频、视频等多媒体数据进行压缩,以保留 尽可能少的有用信息。本文主要是 把所学的数据结构和算法设计的知识应用于实践，对目前 普遍采用的多媒体数据及其压缩算法加以研究，同时介绍了数据压缩所采用的分类、方法及 其标准， 并分析每种算法的优缺点，并据此选择设计一种多媒体数据的无损压缩

2、算法。并以 实例加以说明。 关键词 ：多媒体 ; 压缩 ; 哈夫曼编码 . 1. 多媒体数据类型 1.1 文字 在现实世界中， 文字是人与计算机之间进行信息交换的主要媒体。文字主要包括西文与 中文。在计算机中，文字用二进制编码表示，即使用不同的二进制编码来代表不同的文字。 1.2 音频 音频（ Audio ）指的是20HZ20kHz 的频率范围，但实际上“音频”常常被作为“音频 信号”或“声音”的同义语，是属于听觉类媒体，主要分为波形声音、语音和音乐。 1.3 视频媒体 能够利用视觉传递信息的媒体都是视频媒体。位图图像、矢量图像等都是视频媒体。 1.4 动画 动画是指运动的画面，动画在多媒体中

3、是一种非常有用的信息交换工具。动画之所以 成为可能，是因为人类的“视觉暂留”的生理现象。用计算机实现的动画有两种，一种是帧 动画，另一种是造型动画。 2. 数据压缩基本原理 2.1 信息、数据和编码 数据是用来记录和传送信息，或者说数据是信息的载体。真正有用的不是数据本身，而 是数据所携带的信息。数据压缩的理论基础是信息论。数据压缩技术是建立在信息论的基础 之上的。 数据压缩的理论极限是信息熵。而信息熵有两个基本概念作铺垫，这两个基本概念 就是信息、信息量。首先第一个概念“信息”。 1信息 信息是用不确定的量度定义的，也就是说信息被假设为由一系列的随机变量所代表，它 们往往用随机出现的符号来表

4、示。我们称输出这些符号的源为“信源”。也就是要进行研究 与压缩的对象。 应该理解这个概念中的“不确定性”、 “随机”性、 “度量”性，也就是说当你收到一条 消息之前， 某一事件处于不确定的状态中，当你收到消息后， 去除不确定性， 从而获得信息， 因此去除不确定性的多少就成为信息的度量。比如：你在考试过后，没收到考试成绩（考试 成绩通知为消息） 之前，你不知道你的考试成绩是否及格，那么你就处于一个不确定的状态； 当你收到成绩通知 （消息） 是 “及格”，此时，你就去除了 “不及格”（不确定状态， 占 50% ） ， 你得到了消息“及格”。一个消息的可能性愈小，其信息含量愈大；反之，消息的可能 性

5、愈大，其信息含量愈小。 2信息量 指从 N个相等的可能事件中选出一个事件所需要的信息度量和含量。也可以说是辨别N 个事件中特定事件所需提问“是”或“否”的最小次数。 例如： 从 64 个数（ 164 的整数）中选定某一个数（采用折半查找算法），提问：“是否 大于 32？” ，则不论回答是与否，都消去半数的可能事件，如此下去， 只要问 6 次这类问题， 就可以从64 个数中选定一个数，则所需的信息量是6（bit ） 我们现在可以换一种方式定义信息量，也就是信息论中信息量的定义。 设从 N中选定任一个数X的概率为 P(x) ， 假定任选一个数的概率都相等，即 P(x)=1/N ， 则信息量I(x)

6、 可定义为：222 1 ( )logloglog( ) N I xNP x 上式可随对数所用“底”的不同而取不同的值，因而其单位也就不同。 设底取大于1 的整数 ，考虑一般物理器件的二态性，通常 取 2，相应的信息量单 位为比特（ bit ） ；当 =e，相应的信息量单位为奈特（Nat） ；当 =10，相应的信息量单位 为哈特（ Hart ） ； 显然，当随机事件x 发生的先验概率P(x) 大时，算出的I(x)小，那么这个事件发生的 可能性大， 不确定性小， 事件一旦发生后提供的信息量也少。必然事件的P(x) 等于 1， I(x) 等于 0， 所以必然事件的消息报导，不含任何信息量； 但是一件

7、人们都没有估计到的事件（P(x) 极小） ，一旦发生后，I(x)大，包含的信息量很大。所以随机事件的先验概率，与事件发生 后所产生的信息量，有密切关系。I(x) 称 x 发生后的自信息量，它也是一个随机变量。 现在可以给“熵”下个定义了。信息量计算的是一个信源的某一个事件（X）的自信息 量，而一个信源若由n 个随机事件组成，n 个随机事件的平均信息量就定义为熵(Entropy)。 3信息熵 信源 X发出的 xj(j=1,2,n), 共n 个随机事件的自信息统计平均，即求数学期望 11 ()( )()( )( )( ) log( ) j nn jaj jj I xH xEP x I xP xP

8、x 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 比特： 8 1 11 ( )log23 8

9、8j H xbits 香农信息论认为：信源所含有的平均信息量（熵），就是进行无失真编码的理论极限。 信息中或多或少的含有自然冗余。 4编码的概念 编码是把代表特定量化等级的比较器的输出状态组合，变换成一个n 位表示的二进制数 码，即每一组二进制码代表一个取样值的量化电平等级。 由于每个样值的量化电平等级由一组n 位的二进制数码表示，所以，取样频率f 与 n 位数的乘积nf 就是每秒需处理和发送的位数，通常称为比特率或数码率。例如，CD音响的 采样频率选用44.1kHz ，量化位数n16，采用立体声，相应的比特率为： 44.11628176.4/kHzkB s 5熵编码的概念 如果要求在编码过程

10、中不丢失信息量，即要求保存信息熵，这种信息保持编码又叫做 熵保存编码， 或者叫熵编码。 熵编码是无失真数据压缩，用这种编码结果经解码后可无失真 地恢复出原数据。 2.2 数据压缩的条件 在多媒体信息中包含大量冗余的信息，把这些冗余的信息去掉，就实现了压缩。 数据压 缩技术有3 个重要指标： 一是压缩前后所需的信息存储量之比要大；二是实现压缩的算法要 简单，压缩、解压缩速度快，尽可能地做到实时压缩和解压缩；三是恢复效果要好，要尽可 能完全恢复原始数据。 2.3 数据冗余 1冗余的基本概念 多媒体技术最大难题是海量数据存储与电视信号数字化后的数据量传送。数字化后的 数据量与信息量的关系为：IDdu

11、 其中：I信息量 ,D数据量 ,du冗余量 由上式可以知道，传送的数据量中有一定的冗余数据信息，即信息量不等于数据量，并 且信息量要小于传送的数据量，因此这使得数据压缩能够实现。 2冗余的分类 一般而言，图像、音频数据中存在的数据冗余类型主要有如下几种。 (1) 空间冗余。 这是图像数据经常存在的一种冗余。在同一幅图像中，规则物体和规则 背景的表面特性具有相关性，这些相关性的光成像结构在数字化图像中就表现为数据冗余。 (2) 时间冗余。 时间冗余在图像序列中就是相邻帧图像之间有较大相关性，一帧图像中 的某物体或场景可以由其他帧图像中的物体或场景重构出来，音频的一个连续的渐变过程 中，也存在同样

12、的时间冗余。 (3) 信息熵冗余。信源编码时，当分配给某个码元素的比特数使编码后单位数据量等于 其信源熵， 即达到其压缩极限。但实际中各码元素的先验概率很难预知，比特分配不能达到 最佳，实际的单位数据量大于信源熵时，便存在信息熵冗余。 (4) 视觉冗余。 人眼对于图像场的注意是非均匀的，人眼并不能觉察图像场的所有变化。 事实上人类视觉的一般分辨率为2 6 灰度等级，而一般图像的量化采用的是2 8 灰度等级，即 存在着视觉冗余。 (5) 听觉冗余。 人耳对不同频率的声音的敏感性是不同的，并不能察觉所有频率的变化， 对某些频率不必特别关注，因此存在听觉冗余。 (6) 结构冗余。 图像一般都有非常强

13、的纹理结构。如草席图像，纹理一般都是比较有规 律的结构，因此在结构上存在冗余。 (7) 知识冗余。 图像的理解与某些基础知识有很大的相关性。例如，人脸的图像有同样 的结构：嘴的上方有鼻子，鼻子上方有眼睛，鼻子在正脸图像的中线上等。这些规律性可由 某些基础知识得到，此类冗余为知识冗余。 (8) 其他冗余。 多媒体数据除了上述冗余类型外，还存在其他一些冗余类型，如由图像 非定常特性所产生的冗余等。 3. 数据压缩标准 数据压缩是多媒体通信中的核心技术之一, 数据压缩研究中应注意的问题是，首先，编 码方法必须能用计算机或硬件电路高速实现；其次，要符合当前的国际标准。为此, 国际上 制定了很多与之相关

14、的数据压缩标准, 主要可分为三类: 音频压缩标准 , 二值和静止图像压缩 标准 , 以及视频压缩标准。 3.1 音频数据的压缩标准 音频信号是多媒体信息的重要组成部分。音频信号可以分为电话音频信号、调幅广播音 频信号和高保真的立体声音信号。前两种单频信号的压缩技术比较成熟, 例如 ,ADPCM 、CELP 和子带编码等。国际电报电话咨询委员会（CCITT ）和国际标准化组织（ISO）先后提出一 系列有关音频编码的建议，CCITT(现更名为 ITU2T) 已为这两种音频信号的压缩编码制定了一 些国际标准。 1.G. 711标准 1972年CCITT(现更名为 ITU2T) 为电话质量和语音压缩制

15、定了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进行编码

16、, 经复用后形成输 出码流。 G.722标准也提供数据插入功能, 这样音频码流与所插入的数据一起形成比特流。 G.722能将 224kbit/s的调幅广播质量的音频信号压缩为64kbit/s,主要用于视听多媒体和会 议电视等。 4.G. 728标准 为了进一步降低语音压缩的速率,1991 年CCITT制定了 G.728标准 , 使用基于短延时码本 激励线性预测编码(LD2CELP)算法 , 其速率为 16kbit/s,其质量与 32kbit/s的 G.721标准相当。 5.MPEG 21音频编码 MPEG21 音频编码是国际上制定的第一个高保真立体声音频编码标准(ISO1117223) 。 通

17、过 对14 种音频编码方案的比较测试, 最后选定了以 MUSICAM(Masking Pattern Universal Subband Integrated Coding And Multiplexing)为基础的三层编码结构。根据不同的应用 要求 , 使用不同的层来构成其音频编码器。在MPEG21 中音频编码的1、2层称之为 MUSICAM 。 MUSICAM 使用了以下技术: 子带滤波器先将输入的数字音频信号分成32个子带。在每个子带中, 确定一段信号中的最大电平, 由此得到比例因子这一编码参数。由于比例因子的相对变化很 小, 因此采用差分熵编码方法。根据人耳的掩蔽效应确定掩蔽门限, 据

18、此自适应地分配比特, 以达到高效压缩音频数据。最后, 将音频压缩数据、比例因子和比特分配信息按帧结构组合 在一起 , 形成音频比特流。 6.MPEG 22音频编码 在MPEG21 音频编码中 ,MUSICAM 只能传送左右两个声道。为此,MPEG 扩展了低码率多声道 编码 , 将多声道扩展信息加到MPEG21 音频数据帧结构的辅助数据段( 其长度没有限制) 中。这 样可将声道数扩展至5.1, 即3个前声道 ( 左L、中 C和右 R)、2个环绕声 ( 左LS、右RS)和1个超低 音声道 LFE(常称之为 0.1) 。由此 , 形成了 MPEG22 音频编码标准 SO1381823 。MPEG22

19、 音频编码能 传送多路声音 , 并能确保比特流与MPEG21 前向和后向兼容。 7.AC23系统 AC23 系统是 Dolby 公司开发的新一代高保真立体声音频编码系统, 它继承了 AC22系统的 许多优点 (例如 , 变换编码、 自适应量化和比特分配、人耳的听觉特性等), 并采用了一些新的 技术 ( 例如 , 指数编码、 混合前 / 后向自适应比特分配和耦合技术等) 。AC23系统的总体性能要 优于目前的 MPEG22 音频算法 ( 称之为 MUSICAM 环绕声 ) 。 3.2 二值图象压缩标准 二值图像是指只有黑、白两个亮度值的图像, 例如由文字组成的图像、地图、 线路图等。 灰度图像经

20、过比特平面分解或抖动处理后也能变为二值图像。二值图像编码最常用、最典型 的例子是传真。为此,CCITT先后制定了 G3 和G4 标准 , 其中 ,G3使用 MR 编码算法。而G4 是G3 的 改进型 , 使用 MMR 算法。目前 , 这两种二值图像压缩标准广泛地应用于传真通信和文档存储领 域。另一个正在发展的二值图像压缩标准是JBIG,JBIG 是二值图像专家组的缩写。JBIG可望 成为新一代二值图像和低像素精度图像的无失真压缩标准。虽然已有了优秀的MMRG4标准 , 但还是要制定 JBIG, 其主要原因是改进二值中间色调图像的压缩性能。因为二值中间色调图 像与二值文字图像具有非常不同的统计特

21、性。而G3/G4不适应于中间色调图像, 当G3/G4压缩 这类图像时 , 不仅得不到压缩, 反而有可能扩展数据量, 而使用 JBIG标准可获得约 8:1 的压缩。 它使用了与 JPEG 标准相同的算术编码方法, 其压缩效率要比目前的传真标准G3/G4 高得多。值 得指出的是 , JBIG 标准虽然是针对二值图像的, 但它也可以对包括灰度值的黑白图像或彩 色图像进行编码。 3.3 静止图象压缩标准 ISO和CCITT于 1986年底成立了 “联合图片专家组”, 简称为 JPEG,研究连续色调静止图像 压缩的国际标准。从1988年至 1990年, JPEG进行了大量的改进工作后, 于1991年4月

22、形成了 ISOCD10918 号标准草案。JPEG 标准草案 (DIS) 包括两部分 , 一部分为要求和指标, 描述连续色 调静止图像编码和解码过程的要求和要实现的指标, 以及用于应用间交换压缩图像数据的编 码表示 ( 即交换格式 ) 。 这些过程和表示是通用的, 可适用于很广的应用范围, 例如通信和计算 机系统中的彩色和灰度图像编码。另一部分描述如何确定部分1所定义的各种编码和解码过 程的一致性。 3.4 视频压缩标准 视频是多媒体通信中最重要的媒体之一。一方面视频媒体能给人以“百闻不如一见”的 感受 , 与话音相比 ,视频可以说是一种高级媒体, 能给人带来高级的视觉享受; 另一方面由于 视

23、频的信息量非常大( 尤其是数字化后), 按质量划分 , 视频可大致分为以下三类: 低质量视频,画面较小 ,通常为 QCIF 或CIF格式 , 帧速率低 , 通常为 5 10帧/ 秒 , 既可为 黑白视频也可为彩色视频。其典型的应用包括电视电话和会议电视。 中等质量的视频, 中等大小的画面, 通常为 CIF或CCIR 601视频格式。帧速率为2530 帧/ 秒, 多为彩色视频。其典型应用有CD 和数字音频磁带等数字存储媒体。 高质量视频 , 其画面较大 , 通常为 CCIR 601视频格式至高清晰度电视视频格式。帧速率 25 帧/ 秒, 高质量的彩色图像。其典型应用包括广播质量的普通数字电视和高

24、清晰度电视 等。 针对上述三种视频, 国际上制定了相应的视频压缩标准:H.261 、MPEG21 和MPEG22 。值得 一提的是 1992年成立了一个专家组来制定非常低码率( kbit/s级) 的视频标准 MPEG24 。打算 用于未来的电视电话和移动多媒体通信系统, 例如视频蜂窝电话等。 1.H.261 H.261是 CCITT制定的视频压缩标准,它是国际上第一个视频压缩标准, 主要用于电视电 话和会议电视 , 以满足 ISDN日益发展的需要。H.261视频压缩算法的核心是运动估值预测和 DCT 编码。由于它是第一个国际视频压缩标准, 其许多技术 ( 包括视频数据结构, 运动估算与补 偿,

25、DCT变换、量化和熵编码等) 都被后来的 MPEG21 和MPEG22 所借鉴和采用。 2.MPEG21 MPEG 是活动图像专家组的缩写, MPEG21 采用 CIF视频格式 , 帧速率为 25帧/ 秒或 30帧/ 秒, 码率为 1.5Mbit/s(其中 , 视频约 1.2 Mbit/s ,音频约 0.3 Mbit/ s),图像质量略高于家用VHS 录像机 , 音频质量 ( 双声道 ) 接近 CD 质量。由于 MPEG21 采用类似于 H.261的通用编码方法, 因 此,MPEG21 不仅可用于数字存储媒体, 而且可用于通信和广播, 其压缩数据能以文件的形式 传送、管理和接收。 3.MPEG

26、22 MPEG22 是继 MPEG21 后 ,MPEG 制定的又一视频压缩标准(ISO/IEC13818)。由于是 MPEG21 的继承和发展 , 因此 ,MPEG22 能适用于更广的应用领域, 主要包括数字存储媒体, 广播电视和 通信 , 制定 MPEG22 标准的出发点是保持通用性, 适用于广泛的应用领域、比特率、 分辨率、 质 量和服务。为了适应各种不同的应用要求,MPEG22 使用了可分级性(scalability),即能提供 不同的服务等级(level)。为此 , 该标准定义了几种不同的可分级性形式。基本的可分级性形 式有 : 数据划分、信噪比(SNR)、空间和时间的可分级性。进一步

27、也支持这几种基本可分级 性形式的组合 , 称之为混合可分级性。MPEG22 标准是目前为止最重要的视频压缩标准。它对 多媒体通信和广播电视等领域将会产生深远的影响。随着宽带 ISDN、超大规模集成电路和计 算机技术的发展, 其应用前景十分广阔。 4. 数据压缩算法 各种媒体信息( 特别是图像和动态视频) 数据量非常大。这么大的数据量不仅超出了计 算机的存储和处理能力，更是当前通信信道的传输速率所不及的。因此，为了存储、处理和 传输这些数据，必须进行压缩。相比之下，语音的数据量较小，且基本压缩方法己经成熟， 目前的数据压缩研究主要集中于图像和视频信号的压缩方面。 数据压缩的核心是计算方法，不同的

28、计算方法，产生不同形式的压缩编码，以解决不同 数据的存储与传送问题。数据冗余类型和数据压缩的算法是对应的，一般根据不同的冗余类 型采用不同的编码形式，随后是采用特定的技术手段和软硬件，以实现数据压缩。 4.1 算法的分类 数据压缩方法种类繁 多，可以分为无损 （无失真） 压缩和有损（有失真）压缩 两大类， 无损压缩编码采用 统计编码， 而有损压缩则采 用预测或者变换编码等。见 图 4-1 。 图 4-1 数据压缩技术的基本分类 1无损压缩算法 无损压缩是指解码后的数据与压缩之前的原始数据完全一致。无损压缩利用数据的统计 冗余进行压缩， 可完全恢复原始数据而不引起任何失真，但压缩率受到数据统计冗

29、余度的理 论限制，一般为2:1 到 5:1 。这类方法广泛用于文本数据、程序和特殊应用场合的图像数据 的压缩。 由于压缩比的限制，仅使用无损压缩方法不可能解决图像和数字视频的存储和传输 问题 : (1) 无损压缩编码基于信息熵原理，属于可逆编码。其压缩比一般不高。 (2) 所谓“可逆” ，是指压缩的数据可以不折不扣地还原成原始数据。 (3) 典型的可逆编码有：霍夫曼编码、算术编码、行程编码、LZW编码等。 2有损压缩算法 有损压缩是指解码后的数据与原始数据不一致。有损压缩方法利用了人类视觉对图像中 的某些频率成分不敏感的特性，允许压缩过程中损失一定的信息；虽然不能完全恢复原始数 据，但是所损失

30、的部分对理解原始图像的影响较小，却换来了大得多的压缩比。有损压缩广 泛应用于语音、图像和视频数据的压缩。 (1) 该编码在压缩时舍弃部分数据，还原后的数据与原始数据存在差异。有损压缩具有 不可恢复性和不可逆性。 (2) 有损压缩编码类型有：预测编码、变换编码等 4.2 预测编码 预测编码（ Predictive Coding）是一种有失真的编码，是一种专门用作压缩冗余数据 的编码技术。 预测编码主要是减少了数据在时间和空间上的相关性，因而对于时间序列数据 有着广泛的应用价值。预测编码是根据某一模型利用以往的样本值对于新样本值进行预测， 然后将样本的实际值与其预测值相减得到一个误差值，对于这一误

31、差值进行编码。如果模型 足够好且样本序列在时间上相关性较强，那么误差信号的幅度将远远小于原始信号，从而可 以用较少的电平类对其差值量化得到较大的数据压缩结果。 如果能精确预测数据源输出端作为时间函数使用的样本值的话，那就不存在关于数据源 的不确定性， 因而也就不存在要传输的信息。换句话说， 如果我们能得到一个数学模型完全 代表数据源， 那么在接收端就能依据这一数学模型精确地产生出这些数据。然而没有一个实 际的系统能找到其完整的数据模型，我们能找到的最好的预测器是以某种最小化的误差对下 一个采样进行预测的预测器。 预测编码方法分线性预测和非线性预测编码方法。线性预测编码方法，也称差值脉冲编 码调

32、制法，简称DPCM （differential Pulse Code Modulation） 。预测编码方法在图像数据 压缩和语音信号的数据压缩中都得到广泛的应用和研究。 1。差分脉冲编码调制法 差分脉冲编码调制法，简称DPCM(Differention Pulse Code Modulation)。 （1）DPCM 的基本原理 一幅二维静止图像，设空间坐标( , )i j( , )i j像素点的实际灰度为( , )f i j，( , )fi j是根 据以前已出现的像素点的灰度对该点的预测灰度，也称预测值或估计值。 (,)fij空间坐标像素点的实际灰度值。 (,)fij空间坐标像素点的预测灰度

33、值 实际值和预测值之间的差值，以下式表示， ( , )e i j= ( , )f i j -( , )fi j实际值和预测值之差 将差值( , )e i j定义为预测误差， 由于之间有极强的相关性，所以这个预测误差是很小的。 编码时，不是对像素点的实际灰度( ,)f i j进行编码，而是对预测误差信号( , )e i j进行量化、 编码、发送，由此而得名为差值脉冲编码调制法，简写DPCM 。编码和解码过程见图4-2 所 示： 图 4-2 DPCM 编、解码原理图 系统包括，发送、接收和信道传输三个部分。发送端由编码器、量化器、预测器和加 减法器组成；接收端包括解码器和预测器等；信道传送以虚线表

34、示。由图可见DPCM 系统具 有结构简单，容易用硬件实现（接收端的预测器和发送端的预测器完全相同）的优点。图中 输入信号( , )f i j是坐标为( , )i j像素点的实际灰度值，( , )fi j是由已出现先前相邻像素点的 灰度值对该像素点的预测灰度值。( , )e i j是预测误差。 假如发送端不带量化器，直接对预测 误差( , )e i j进行编码、传送，接收端可以无误差地恢复( , )f i j。这是可逆的无失真的DPCM 编码，是信息保持编码；但是，如果包含量化器，这时编码器对( , )e i j编码，量化器导致 了不可逆的信息损失， 这时接收端， 经解码恢复出的灰度信号，不是真

35、正的( , )f i j， 以 ?(, ) f i j 表示这时的输出。可见引入量化器会引起一定程度的信息损失，使图像质量受损。但是，为 了压缩比特数， 利用人眼的视觉特性，对图像信息丢失不易觉察的特点，带有量化器有失真 的 DPCM 编码系统还是普遍被采用。 2自适应差分脉冲调制法 ADPCM（ Adaptive Differential Pulse Code Modulation，自适应差分编码）具有自适 应特性， ADPCM 主要用于对中等质量的音频信号进行高效率压缩。例如语音的压缩、调幅广 播音质的信号压缩等。该编码包括自适应量化和自适应预测两种形式: 自适应量化 - 在一定的量化级数

36、下，减少量化误差或在相同误差情况下压缩数据。自适 应量化必须具有对输入信号幅度值的估算能力，否则无法确定信号改变量的大小。 自适应预测 - 根据常见的信息源求得多组固定的预测参数，将预测参数提供给编码使 用。在实际编码时，根据信息源的特性以实际值与预测值的均方差最小为原则。自适应地 选择其中一组固定的预测参数进行编码。 预测编码的方法能够压缩图像数据的空间和时间冗余性。特点是直观、简捷和易于实 现。 在传输速度要求很高的应用中,大多选用此方法。然而, 预测方法的不足是压缩能力有 限。为了更好地提高压缩能力, 可以采用变换编码方法。 4.3 变换编码 变换编码的基本概念 变换编码是一种有失真的编

37、码，所谓变换是指对原始数据原来的时间或空间域进行数学 变换，使得变换后能够突出原始数据中的重要部分，以便重点处理。广泛应用于单色图像、 彩色图像、 静止图像、 运动图像， 以及多媒体计算机技术中的电视帧内图像压缩和帧间图像 压缩中。变换编码是指将给定的图像变换到另一个数据域（变换域或频域）上，以便用较少 的数据表示大量的信息。也就是说， 它不是直接对空间域图像信号编码，而是首先将当前所 表达的空间域图像信号经过变换映射到另一个正交矢量空间，得到一系列变换系数，然后对 这些变换系数进行编码处理。结果， 重要的系数在变换到其他空间域后，其编码的精确度高 于次重要的系数。变换本身是一种无损且可逆的技

38、术，但为了获得更好的编码效果，忽略了 一些不重要的系数，因而成为有损的技术。常用的变换编码方案有离散余弦变换、离散哈达 玛变换、小波变换等方法。 变换编码的原理为：输入信号经过适当的正交变换到另一个频域空间，相关性就会明显 降低， 能量集中在频域的少数低频系数上，这样就达到了数据压缩的效果。如果保留频域中 系数大的元素，忽略系数小的元素，然后辅以非线形量化来提高压缩程度，最后进行编码， 可获得很高的压缩比。 4.4 统计编码原理 统计编码又称信息熵编码，它通过去除信源信号的冗余达到压缩的目的，属于无损编码。 根据消息出现概率的分布特性而进行的压缩编码 , 它有别于预测编码和变换编码。这种编 码

39、的宗旨在于, 在消息和码字之间找到明确的一一对应关系 , 以便在恢复时能准确无误地 再现出来 , 或者至少是极相似地找到相当的对应关系, 并把这种失真或不对应概率限制到可 容忍的范围内。但不管什么途径, 它们总是要使平均码长或码率压低到最低限度。常用的编 码有： Huffman 码、行程编码、算术编码等。 1哈夫曼（ Huffman ）编码 （1）哈夫曼编码的方法 编码过程如下： 将信源符号按概率递减顺序排列； 把两个最小的概率加起来 , 作为新符号的概率； 重复步骤、 , 直到概率和达到 1 为止； 在每次合并消息时，将被合并的消息赋以1 和 0 或 0 和 1； 寻找从每个信源符号到概率为

40、1 处的路径，记录下路径上的1 和 0； 对每个符号写出“1” 、 “0”序列（从码数的根到终节点）。 （2）哈夫曼编码的特点 哈夫曼方法构造出来的码不是唯一的。原因如下： . 在给两个分支赋值时 , 可以是左支 ( 或上支 ) 为 0, 也可以是右支 ( 或下支 ) 为 0, 造成编码的不唯一。 . 当两个消息的概率相等时 , 谁前谁后也是随机的, 构造出来的码字就不是唯一的。 哈夫曼编码码字字长参差不齐 , 因此硬件实现起来不大方便。 哈夫曼编码对不同的信源的编码效率是不同的。 . 当信源概率是 2 的负幂时 , 哈夫曼码的编码效率达到 100%； . 当信源概率相等时 , 其编码效率最低

41、。 . 只有在概率分布很不均匀时 , 哈夫曼编码才会收到显著的效果，而在信源分布均 匀的情况下 , 一般不使用哈夫曼编码。 对信源进行哈夫曼编码后 , 形成了一个哈夫曼编码表。解码时 , 必须参照这一哈 夫曼编码表才能正确译码。 在信源的存储与传输过程中必须首先存储或传输这一哈夫曼编码表在实际计算压缩效果 时 , 必须考虑哈夫曼编码表占有的比特数。在某些应用场合, 信源概率服从于某一分布或 存在一定规律( 这主要由大量的统计得到) ，这样就可以在发送端和接收端固定哈夫曼编码 表，在传输数据时就省去了传输哈夫曼编码表，这种方法称为哈夫曼编码表缺省使用。使用 缺省的哈夫曼编码表有两点好处： . 降

42、低了编码的时间 , 改变了编码和解码的时间不对称性； . 便于用硬件实现 , 编码和解码电路相对简单。这种方法适用于实时性要求较强的场 合。虽然这种方法对某一个特定应用来说不一定最好，但从总体上说 , 只要哈夫曼编表基 于大量概率统计, 其编码效果是足够好的。 （3）哈夫曼编码举例 假设一个文件中出现了8 种符号 S0,S1,S2,S3,S4,S5,S6,S7，S0 到 S7的出现频率分别 为 4/14 ，3/14 ，2/14 ，1/14 ， 1/14 ，1/14 ，1/14 ，1/14 ，则进行Huffman 编码的过程为图 4-3 所示 :其中圆圈中的数字是新节点产生的顺序。 图 4-3

43、Huffman编码的示意图 哈夫曼提出的这种编码也称为最佳变长码，其优点是编码的效率高，但这种编码依赖 于信源的统计特性。并且，如果消息数很大，需要存储的码表也要很大，因而会影响存储 量、编码以及译码速度等各个方面的性能。 2算术编码 算术编码把一个信源集合表示为实数线上的 0 到 1 之间的一个区间。 这个集合中的每 个元素都要用来缩短这个区间。信源集合的元素越多, 所得到的区间就越小, 当区间变小时, 就需要更多的数位来表示这个区间, 这就是区间作为代码的原理。算术编码首先假设一个信 源的概率模型 , 然后用这些概率来缩小表示信源集的区间。 （1）举例说明算术编码过程 例 设英文元音字母采

44、用固定模式符号概率分配如下： 设编码的数据串为 eai 。令 high为编码间隔的高端，low 为编码间隔的低端，range 为的编码间隔长度，rangelow为编码字符分配的间隔低端，rangehigh 为编码字符分配的 间隔高端。 初始 high=1 ， low=0， range high-low， 一个字符编码后新的low 和 high 按下式计算： low =low range rangelow high =lowrange rangehigh 在第一个字符e 被编码时， e 的 rangelow 0.2 ，rangehigh=0.5，因此： low 0 + 1 0.2 0.2 hig

45、h=0 + 1 0.5 0.5 range=high low=0.5 0.2=0.3 此时分配给 e 的范围为 0.2,0.5 。 第二个字符a 编码时使用新生成范围0.2,0.5， a 的 rangelow=0, rangehigh=0.2, 因此： low=0.2+ 0.3 0=0.2 high=0.2 0.3 0.2=0.26 range=0.06 范围变成 0.2,0.26 。 对下一个字符 i 编号， i 的 rangelow=0.5，rangehigh=0.6，则： low=0.2 0.06 0.5=0.23 high=0.2 0.06 0.6=0.236 即用 0.23,0.23

46、6 表示数据串 eai ，如果解码器知道最后范围是0.23,0.236 这一范围，它马上可解得一个字符为 e ，然后依次得到惟一解 a ，即最终得到 eai 。 （ 2）算术编码的特点 不必预先定义概率模型，自适应模式具有独特的优点； 信源符号概率接近时，建议使用算术编码，这种情况下其效率高于Huffman 编码； 算术编码绕过了用一个特定的代码替代一个输入符号的想法，用一个浮点输出数值代 替一个流的输入符号，较长的复杂的消息输出的数值中就需要更多的位数； 算术编码实现方法复杂一些，但 JPEG 成员对多幅图像的测试结果表明，算术编码比 Huffman 编码提高了5% 左右的效率，因此在 JP

47、EG 扩展系统中用算术编码取代 Huffman 编码。 3。行程编码 行程编码 (Run Length Coding)主要检测信源中重复出现的符号序列，用它们的出现次 数进行编码。通过计算信源符号出现的行程长度，然后将行程长度转换成代码。例如，对于 二值符号序列0000000000000001111111000000000 可以编码为1507190，它代表 15 个 0 后 续 7 个 1 再后续 9 个 0。 如果约定所有的符号序列都以0 开始，其编码可进一步简化为1579。 因为符号0 和 1 交错排列，所以没有必要指出是何种符号的行程长度。 行程编码是一种无损压缩。其压缩效果取决于压缩的

48、内容。例如在黑白二值图像 （传真） 中存在大量的重复像素，采用行程编码可以有效地压缩数据。然而， 对于一些各种像素分布 均匀的特殊的图像，采用行程编码会使数据量不降反增，出现所谓的负压缩。这是行程编码 的局限。 4.5LZW压缩编码 LZW （Lempel Ziv Welch）压缩编码是一种先进的数据压缩技术，属于无损压缩编码， 该编码主要用于图像数据的压缩。对于简单图像和平滑且噪声小的信号源具有较高的压缩 比，并且有较高的压缩和解压缩速度。 1977 年，两位以色列教授Lempel 和 Ziv 提出了查找冗余字符和用较短的符号标记替代 冗余字符的概念。1985 年，由 Welch 加以充实而

49、形成LZW ，简称“ LZW ”技术。 1 LZW压缩基本原理 LZW压缩技术把数据流中复杂的数据用简单的代码来表示，并把代码和数据的对应关系 建立一个转换表，又叫“字符串表”。 转换表是在压缩或解压缩过程中动态生成的表，该表只在进行压缩或解压缩过程中需 要，一旦压缩和解压缩结束，该表将不再起任何作用。 2。LZW算法 LZW算法基于转换串表（字典）T，将输入字符串映射成定长（通常为12 位）的码字。 在 12 位 4096 种可能的代码中，256 个代表单字符， 剩下 3840 给出现的字符串。LZW字典中 的字符串具有前缀性。 3. LZW算法流程： （1）初始化：将所有的单字符串放入串表； （2）读第一个输入字符给前缀串； （3）Step ：读下一个输入字符K； if 没有这样的K( 输入已穷尽 ) ： 码字 ( ) 输出；结束。 if K 已存在于串表中： K:=； repeat Step； else K不在于串表中 : 码字 ( ) 输出； K加进串表； K:= ；repeat Step