《多媒体信息与通信》课件第3章

第三章多媒体信息的压缩编码技术及标准任务3.1基于预测方法的音频信号压缩任务3.2基于DCT的音频信号压缩任务3.3图像/视频信息的霍夫曼编码任务3.4多媒体信息的游程编码

任务3.1基于预测方法的音频信号压缩

学习目标（1）掌握音频信号的定义和分类。（2）理解音频信号数字化实现过程以及压缩的必要性和依据。（3）了解常用的音频信号格式以及压缩标准。（4）掌握基于预测方法的音频压缩的算法流程，并能利用MATLAB进行仿真，及利用Rice编码实现音频信号的压缩。任务分析多媒体信号的压缩是当前许多学者研究的热点。音频信号作为多媒体的重要组成部分，其压缩问题备受研究人员的关注。如何尽可能地在保证信号质量的前提下提高信号压缩比，降低信号的比特率，以节省存储空间，提高信号的传输速率，是信号压缩的主要任务。对于音频信号压缩，需要清楚以下几个问题：（1）“预测”是针对哪些物理量进行的？（2）压缩中采用何种编码方法？（3）如何评价压缩的质量？3.1.1音频信号的定义和分类音频信号作为多媒体的一种表现形式，是自然界声音中的部分体现，可以通过音频采集设备得到。声音是通过空气传播的一种连续的波，在传输过程中引起耳膜的振动，由人耳所感知。对声音的质量评价主要体现在音调、音强和音色三个方面：音调（Pitch）指声音的频率，频率高则音调高，频率低则音调低。同时，声音质量的高低还与频率范围紧密相关。一般来说，频率范围越宽，声音的质量越高。音强（Volume）即音量，与声波的振动幅度有关，反映了声音的大小和强弱。振幅越大，音量越高。音色体现了声音提起来的优美程度。自然界中的声音大多是由不同频率和不同振幅的声波组合形成的复音。复音中的最低频率称为基音（或基频），其他频率成分称为泛音（或谐音）。基音和泛音决定了特色声音的音色或音质。对于次声波（频率低于20Hz的声波）和超声波（频率高于20kHz的声波），人类是不能感知的，但对于频率分布在20Hz～20kHz之间的声波信号，则可以感知到，这部分信号即为“音频信号（Audio）”。人类发音器官发出的声音频率约在80～3400Hz之间，说话的信号频率通常在300～3400Hz之间，这种信号称为“语音信号（SpeechVoice）”。3.1.2音频信号的数字化为了更好地存储和处理音频信号，需要将采集到的自然界的模拟信号转化为数字信号。在模数转化的过程中，需要遵循奈奎斯特抽样定理，才能保证采样之后的数字信号完整地保留原始信号中的信息。音频信号频率分布范围与人的听觉范围相一致（20Hz~20kHz），因此对模拟音频采样的频率应该不小于40kHz。在CD中采用了44.1kHz的采样频率。根据模数转换的过程，对模拟音频信号进行采样以后，还要对离散采样值在幅度上进行量化。在CD中，采样样值的幅度用16位的二进制数来表示，亦即在幅度上把模拟音频信号分为216=65536个区间，依次记录为0~65535。对照每一个采样值的大小，四舍五入后查看当前值属于哪一个量化区间，将区间号划分给当前的采样值。最后得到一系列的“0”“1”字符串。这种直接对模拟音频信号进行数字化的方法称作PCM（PulseCodeModulation，脉冲编码调制）编码。3.1.3音频信号压缩的必要性及依据采用PCM编码时，数字音频的存储量计算公式为为了保证多媒体系统的正常工作与普及，针对数字音频压缩的技术研究显得尤为重要。而音频信号在时间和频域上存在的冗余性，以及人耳的听觉特性使得音频信号的压缩变得可行。音频信号的时间冗余主要表现为幅度分布的非均匀性、样值间的相关性、周期之间的相关性以及静止系数。幅度分布的非均匀性是指音频信号幅度较小的样值分布概率高于大幅度样值分布概率；样值间的相关性随着采样频率的提高呈现上升趋势；周期之间的相关性是指音频信号在特定一段时间内可以由少数频率成分作用，也就会存在周期与周期之间的相关性；静止系数是语音信号的一种停顿，是可以去除的冗余时间段。音频信号的频域冗余主要是指长时功率谱密度的非均匀性和语音特有的短时功率谱密度。音频信号的最终用户是人，因此，应充分利用人类听觉的生理-心理感知特性的影响，对音频信号进行压缩。人耳对信号幅度、频率的分辨能力是有限的，凡是人耳感觉不到的成分，都称为与听觉无关的“不相关”部分，都可视为是冗余的，可以将其压缩掉。3.1.4音频压缩技术的分类一般来讲，根据压缩后的音频能否完全重构出原始声音可以将音频压缩技术分为无损压缩及有损压缩两大类。对于不同的压缩编码方法，其算法的评定可以从以下四方面进行：（1）算法复杂度：包括运算复杂度和内存要求。运算复杂度用MIPS衡量，内存用B或KB来衡量。（2）重构音频信号的质量：信噪比。（3）编码效率：压缩比。（4）编解码时延。1.无损压缩使用无损压缩方案可以在解压缩后逐位恢复原始数据信息。它通过预测过去样本中的值，消除存在于音频信号中的统计冗余。无损压缩可以实现小压缩比，最好可使压缩比达到大约为2:1，具体取决于原始音频信号的复杂性。时域预测编码技术使无损压缩成为可行。2.有损压缩有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不会使人对原始信号表达的信息造成误解；有损压缩适用于重构信号与原始信号无需完全相同的场合。有损压缩的压缩比具体取决于编码/解码过程的复杂性和音频质量要求。有损压缩又有以下几种编码方法。1）波形编码波形编码是指直接对音频信号的时域波形采样值或其频域变换系数进行编码，主要利用音频样值的幅度分布规律和相邻样值间的相关性进行压缩，编码系统源于信号原始样值，波形与原始声音波形尽可能地一致，保留了信号的细节变化和各种过渡特征。差分编码调制（DPCM）源于PCM，它根据声音信号相邻采样值之间呈现明显的相关性，利用前一个采样样本估算下一个样本信号的幅度大小，形成预测值，对预测的样本值与原始的样本值之差进行量化。子带编码（SBC）属于依据感知特性的频域编码。该方法将音频信号进行时间足够短的分段，通过将分段块由时间域转变为频率域，利用带通滤波器（BPF）组把原始信号的频带分割为若干子频带。自适应变换编码（ATC）是先对信号进行某种函数变换，从一种信号（空间）变换到另一种（空间），然后再对信号进行编码。变换编码与子带变换都是根据人对声音信号的感知模型（心理声学模型），通过对信号频谱的分析来决定子带样值或频域样值的量化阶数和其他参数选择的，因此又可称为感知型压缩编码。2）参数编码参数编码首先根据不同的信号源，如语言信号、自然声音等形式建立特征模型，通过提取特征参数和编码处理，使重建的声音信号尽可能高地保持原声音的语意，但重建信号的波形同原声音信号的波形可能会有相当大的差别。3）混合编码混合编码是将波形编码和参数编码组合起来的编码形式，克服了原有波形编码和参数编码的弱点，力图保持波形编码的高质量和参数编码的低速率，在4～16kb/s速率上能够得到高质量的合成声音信号。3.1.5音频压缩技术的标准1.MPEG系列MPEG是世界著名的数字视频和音频压缩的标准化组织。该组织自1988年以来，制定了一系列国际标准，其中MPEG-1、MPEG-2已为人们所熟知，这两个标准为VCD、DVD及数字电视等产业的发展奠定了基础。1997年，MPEG制定了新的音频标准AAC。从1999年开始，他们陆续又制定了新的MPEG标准：MPEG-4、MPEG-7和MPEG-21，这些标准对音频技术的发展产生了深远的影响。2.杜比系列杜比数码又称作杜比环绕影音，是由美国杜比实验室开发的性能卓越的数字音频编码系统，其中，AC-1用于卫星通信和数码有线广播，AC-2用于专业音频的传输和存储，AC-3是杜比最闻名的数字技术。AC-3采用第三代ATC技术，被称为感觉编码系统，它将特殊的心理音响知识、人耳效应的最新研究成果与先进的数码信号处理技术很好地结合起来，形成了“数字多声道音频处理技术”。该技术可以传输和存储多达5个全频带声道，以及一个低频效果声道（LFE），而所占用的存储空间比CD上一路线性PCM编码的声道所占用的空间还要少。3.未来音频压缩技术的发展和标准化其他优秀的音频编码技术，如索尼的ATARC、贝尔实验室的PAC和微软的WMA等，也都获得了相当广泛的应用。3.1.6常用音频文件格式常用音频文件可分为声音文件和MIDI文件。声音文件直接记录了真实声音的二进制采样数据，通常较大。WAV是微软和IBM共同开发的PC标准声音格式，文件后缀名.wav是一种通用的音频数据文件。通常使用WAV格式来保存一些没有压缩的音频，也就是经过PCM编码后的音频，因此也称为波形文件，它依照声音的波形进行存储，因此要占用较大的存储空间。MPEG中的MP3格式是一种音频压缩技术，它被设计用来大幅度地降低音频数据量，MP3这种格式将音乐以1∶10甚至1∶12的压缩率，压缩成容量较小的文件，而对于大多数用户来说重放的音质与最初的不压缩音频相比没有明显的下降，适用于移动设备的存储和使用。WMA（WindowsMediaAudio）是微软公司推出的与MP3格式齐名的一种新的音频格式。WMA在压缩比和音质方面都超过了MP3，更是远胜于RA（RealAudio），即使在较低的采样频率下，WMA也能产生较好的音质。RA（RealAudio）采用的是有损压缩技术，由于它的压缩比相当高，因此音质相对较差，但是文件也是最小的，因此在高压缩比条件下表现好，但若在中、低压缩比条件下时，表现却反而不及其他同类型文件格式了。APE是目前流行的数字音乐文件格式之一。APE是一种无损压缩音频技术，也就是说将从音频CD上读取的音频数据文件压缩成APE格式后，还可以再将APE格式的文件还原，而还原后的音频文件与压缩前的一模一样，没有任何损失。3.1.7音频信号的分帧分帧是大多数音频压缩算法的共同特点，它可以提供快速且便捷处理音频信息流的能力。分帧操作的实际内容是把待压缩的音频信号均分为等时间间隔的一帧一帧的数据。要选取一个合适的帧长。音频工程师协会/欧洲广播联合会(AES/EBU)信号协议规定每192个音频帧构成一个数据块，每一个音频帧分成2个子帧，每一个子帧为32bit，对应一个声道的语音信号采样值。有实验表明，音频编码分帧长度为192的倍数时可取得较好的压缩效果。对于采样频率为44.1kHz，量化长度为16bit的音频数据，分帧长度为1152时较为合适。3.1.8预测编码音频压缩的目的是除去数据中的冗余，完美重构原始音频信号。预测编码是数据压缩三大经典技术之一。预测编码建立在信号数据的相关性之上，是较早用于信源编码的一种技术。该编码方法对具有平稳特性的信号特别有效。一般来讲，调和的声音信号信息冗余较大，而一个不协调（类似噪音）的信号信息冗余较小。一个特定取样值的概率与其邻近的取样值有关。大部分预测编码器的结构、模型及其实现都相对简单，采用各阶的预测系数全部为整数的预测器。对于有记忆信源，信源输出的各个分量之间是有统计关联的，这种统计关联性可充分利用，预测编码就是基于这一思想。预测编码器的基本原理是利用信源输入信号的相关性，在预测编码中并不采用直接编码的机制，即不直接对信源输出来的信号进行编码，而是先将信源信号通过预测器进行预测，然后再对预测误差信号进行编码，即利用过去的样值x（n-1）、x（n-2）等来预测当前的样值x［n］。利用过去的样值越多则预测精度越高。由于差值的动态范围要远小于信号的动态范围，这时即使仍采用原信号量化时采用的量化级，也可降低码位进行编码，进而实现比特率压缩。若想真正实现预测编码还要进一步考虑以下三个方面的问题：（1）预测误差准则的选取。它是指预测误差所依据的标准，目的是使预测误差最小。目前大致可采用下列四种类型的准则：①最小均方误差（MMSE）准则。②功率包络匹配（PSEM）准则。③预测系数不变性（PCIV）准则。④最大误差（ME）准则——主要用于遥控数据压缩。（2）预测函数的选取。一般采用工程上比较容易实现的线性预测，预测精度与K值大小有直接关系，K越大，精度越高，但设备越复杂。所以要根据设计要求及实际效果来确定。（3）预测输入数据的选取。即，选取何处的原始数据作为预测器的依据。一般可分为以下三类:①直接从信源输出选取待测时刻l的前K位，作为预测器的依据。②误差函数的输出端反馈到预测器中的待测时刻l位以前的K位。③将①、②相结合的噪声反馈型编码。线性预测器是一种特殊的预测器，已成为语音及音频压缩编码所要用到的一个重要的技术。3.1.9熵编码熵编码的特点是在编码时不会丢失数据的任何信息熵。通常来说，熵编码是根据统计学的原理来进行编码的（如概率）。利用熵编码可在不减少消息的信息熵的基础上对信号进行有效的编码，以实现对数据的无损压缩。常见的信息熵编码有：霍夫曼编码、香农编码、游程编码、算术编码、Rice编码。Rice编码虽在一般的数据压缩场合不太常见，但却在音频无损压缩领域经常使用。下面简述一下Rice编码的编码原理。Rice编码是一种特殊的霍夫曼编码，它的信源概率密度分布服从Laplace（拉普拉斯）分布。Rice编码只有一个单独的参数k，而不像普通的霍夫曼编码有一个很长的数据字典。经过研究数据表明，在音频的预测编码中，经过线性预测技术进行相关操作后的误差信号的概率分布即近似于Laplace分布。Rice编码码字由以下部分组成：符号位、若干连续的0、分隔位、k位二进制码。其中，符号位表示预测误差e［n］的正负号（1表示e［n］为正，0表示e［n］为负），紧接着是若干位连续的零（这要通过计算得出），随后要加一位分隔位分隔开前后的编码（因为分隔位前后的码字表示意义不同），最后是|e［n］|的低k位二进制码。3.1.10音频信号预测编码的MATLAB实现采用MATLAB软件对以上的算法进行仿真。1.音频信号的读入MATLAB提供了读取音频文件的函数：［x，fs，bits］=wavread（′filename.wav′，［N1，N2］）;值得注意的是，MATLAB提供的wavread函数只能读取WAV格式的音频文件。在wavread函数中，x为一个矩阵（一般为两列），矩阵中各个元素值的取值范围均为［+1，-1］；fs是WAV格式音频文件在采样时的频率；bits是对采样后的样值进行量化时所采用的量化位数。在wavread函数内的文件名后必须要加.wav后缀，并写在′′内。［N1，N2］表示读取WAV中的两个通道。在本任务采用的设计中，使用的音频文件为CD音质的WAV文件。2.分帧如前文所述，对音频文件进行分帧是非常重要的一个操作，它可以提供快速且便捷处理音频信息流的能力。这里采用enframe（）对数据进行分帧。enframe函数位于VoiceBox工具箱中。VoiceBox工具箱是一个MATLAB的语音处理工具箱。在这个工具箱中包含了许多语音处理的样例。3.求取预测误差4.对预测误差进行Rice编码1）Rice编码中余数位k的选择2）预测误差的Rice编码3.1.11单声道预测编码方法及其改进1.单声道线性预测编码在单声道线性预测编码方法里，将音频数据读入之后只对其左声道的数据进行预测编码。考虑到若音频数据过长，MATLAB需要运行比较长的时间才能对整个音频数据完成编码，所以在实际编码时取单声道音频数据中间的1000帧作为代表进行编码。2.左右声道联合差分编码对音频信号进行线性预测编码来实现数据压缩，主要是靠去除数据的相关性来实现的。在上述的预测编码中未考虑到声道间的相关性，而只对单独一个声道进行预测、熵编码，因此压缩比不高。考虑到立体声的左右声道数据之间是有一定的相关性的，因此可以利用左右声道数据的相关性来对数据进行进一步的压缩。在单声道预测编码的基础上进行一些改进，采用左右声道联合差分编码的方法来提高压缩比。

任务3.2基于DCT的音频信号压缩

学习目标（1）理解DCT与MDCT的实现过程，可以利用MATLAB实现变换过程。（2）理解MDCT的提升格式。（3）掌握基于MDCT的音频信号压缩流程。任务分析DCT/MDCT属于变换编码。变换编码主要由映射变换、量化及编码几部分操作组成。映射变换的方法很多，一般是指函数变换法，而常用的又是正交变换法。如傅里叶变换就是利用复数域正交变换将一个函数从时域描写变为频域描写。这有时会使函数的某些特性变得明显，从而使问题处理简化。DCT技术在图像编码中获得了广泛的应用，但用于音频，特别是用于宽带音频编码时却存在着边界效应，会产生很大的噪声，采用MDCT可以克服这些不足。本任务是研究MDCT技术音频压缩的应用。编码部分采用和任务3.1相同的Rice编码实现。那么基于DCT的音频压缩编码到底是如何实现的？MDCT在处理数据时如何消除边界噪声？3.2.1离散余弦变换（DCT）离散余弦变换（DiscreteCosineTransform，DCT）是N.Ahmed等人在1974年提出的正交变换方法。为了工程上实现的需要，国内外许多学者花费了很大精力去寻找或改进离散余弦变换的快速算法。由于近年来数字信号处理芯片（DSP）的发展，加上专用集成电路设计上的优势，离散余弦变换在目前图像编码中有了重要的地位，成为H.261、JPEG、MPEG、H.264等国际上公用编码标准的重要环节。在视频压缩中，最常用的变换方法就是DCT。它被认为是性能接近K-L变换的最佳变换。3.2.2改进的离散余弦变换（MDCT）正交变换采用分组的方式进行，并且对每组系数进行单独的编码，所以产生的量化误差对于其他分块的影响也是不一样的。正交变换边界有它自己的固定非连续性，并且每种类型的正交变换，其不连续情况也不尽相同。因此会在分组边界处产生很大的噪声。为了减少这些噪声，可以采用时域混叠抵消（TimeDomainAliasingCancellation，TDAC）消除边界影响。对于DCT，首先用本组的N个取样和两个相邻组的各K/2个取样叠加，得到M+K个独立的变换系数；为了减少各组间失真，必须把这K个样本重叠；由于这K个重叠点变换了两次，因而导致了DCT编码效率降低。图（b）给出了频谱变换中的DCT窗。采用MDCT的优点：在用MDCT时，为了求由M个采样构成的第一组数据频谱，如图（a）所示那样，首先把这M个采样和与其相邻两个组的各一半叠加，取出2M个采样，再加上窗口，变换成频谱数据。这样就得到了2M个频谱系数，不过其中有一半是由剩下一半的频谱系数符号反转得到的。故独立的频谱系数只得到M个。即对于由M个采样构成的每一组，可以将M个实数值数据进行编码。基于TDAC的MDCT可以降低“边界效应”。长度为N的音频块的x（n），其MDCT与IMDCT定义为IMDCT的输出可以用来重构原输入信号：MDCT由于其性能优于DCT，被广泛应用于音频压缩编码中。例如MPEG-1音频第3层编码（MP3）采用12点和36点的MDCT；MPEG-4高级音频编码（AAC）采用256点和2048点的MDCT。根据上述原理，若变换矩阵可以分解成主对角线都是1的几个三角矩阵的乘积，则找出这几个三角矩阵相对应的可逆整型变换，再根据它们的分解顺序分别进行变换，即可创建出这个变换的整数变换。这个过程即为提升的基本原理。将三角矩阵与输入信号相乘称为提升运算。所有这些主对角线元素都是1的矩阵叫作提升矩阵。提升结构的整数近似是可逆的，且逆运算无误差。因此通过散步提升方法实现的Givens旋转变换的整数近似是完全可逆的。这种整数变换既确保了变换对整数信号达到真正可逆，也能够更有效地降低信号之间的相关性，而且运算结果与浮点数运算结果相差无几，为音频无损压缩提供了良好的基础。对时域重叠抵消的一个充分条件是窗函数必须满足对称性。为了将MDCT完全分解为Givens旋转，可将这一变换过程分成三个步骤：加窗、时域重叠抵消和长度为M的离散余弦变换。这样，加窗和时域重叠抵消就能利用Givens旋转实现。3.2.4无损压缩实现流程利用MDCT实现音频信号的压缩编码时，为了便于比较，采用与任务3.1相同的编码方式——Rice编码。基于MDCT的音频编码流程图如图所示。3.2.5仿真结果根据以上流程利用MATLAB进行仿真。熵编码采用Rice编码，实验对象是用Wavsplit软件进行截取的5组WAV音频文件。表给出了5个音频片段利用MDCT压缩后的仿真结果。根据仿真结果，将压缩比求和取平均值，结果约为1.39。

任务3.3图像/视频信息的霍夫曼编码

学习目标（1）掌握最佳变长编码的原理。（2）掌握霍夫曼二叉树的建立过程。（3）掌握霍夫曼编解码的流程，并能够利用MATLAB实现基于2DDCT的静止图像压缩。任务分析（1）霍夫曼编码是熵编码的一种，理解霍夫曼编码的理论基础。（2）根据霍夫曼编码的理论基础分析其过程。（3）分析利用DCT和霍夫曼编码对静止图像进行压缩的过程。3.3.1图像/视频信息的压缩依据图像/视频信息的压缩主要是依靠削弱甚至消除组成图像像素点、视频连续帧之间的相关性，从而减少图像的像素比特。这种相关性被称为图像/视频的冗余。冗余主要分为以下六类：（1）空间冗余。空间冗余是静态图像中存在的最主要的一种数据冗余。所谓空间冗余，就是在观察某一处的景物时，看到的景物可能会包含很多种颜色，其中必然会有某种颜色是带有连贯性的，但是用设备来取景时，得到的图像是用离散的像素来表示的，也就忽略了这种连贯性。比如说：图像上是一块黑板，黑板上的颜色是一致的，所以图像上用于表现这块黑板所用的颜色就是相同的，空间冗余也就产生了。（2）时间冗余。时间冗余是序列图像中经常包含的冗余。一组连续的画面之间往往存在着时间和空间的相关性，但是用基于离散时间采样来表示运动图像的方式通常没有利用这种连贯性。比如武侠电影中，两个武林高手在一片树林里生死决斗，假设在一定的时间内两个人打斗的地点未发生改变，那么，在这个打斗的过程中，两人打斗的背景（树林和地面）一直都是相同的且没有发生移动，同样的两个人打斗也是如此，只有他们的动作和位置发生了一定的变换。（3）结构冗余。结构冗余是在某些场景中，存在着明显的图像分布模式，这种分布模式称作结构。在很多图像中会重复出现同一纹理或相近的纹理结构，比如说：大理石地砖、蜂窝等。（4）视觉冗余。视觉冗余是因为人类的视觉系统对图像的敏感度不同而产生的一种冗余。人眼对不同的色彩敏感度不同，对亮色敏感度强，对暗色的敏感度就稍弱。而相对于亮度和色度，人们对亮度变化的敏感度就强于色度，对事物的边缘比较敏感，对结构敏感等，因此，可以根据这些视觉特性对图像信息进行取舍，达到图像压缩的目的。（5）符号冗余。符号冗余也称为编码表示冗余。在编码过程中，如果采用定长编码，即利用固定码长表示每个像素，而没有体现出高概率出现的像素与低概率出现的像素的区别，则其势必是冗余的。如果采用可变码长进行编码，对高概率出现的像素采用短码字表示，低概率出现的像素使用长码字表示，则可以消除这种冗余。（6）知识冗余。在某些特定的应用场合里，编码对象中包含的信息与某些先验的基本知识有关。例如，在一副人脸图像中，五官的位置是大致固定的，或者高速公路视频中车辆出现的相对位置也是固定的。在实际编码中，即可以利用这些先验知识，通过模型训练，为待编码的图像建立模型，直接对参数进行编码。3.3.2最佳变长编码1.关于编码的基础物理量（1）熵。（2）平均码长。（3）编码效率。编码效率为熵和平均码长的比值。（4）压缩比。压缩比是未压缩编码前存储位数与压缩后的比值。2.最佳变长编码的方法凡是能载荷一定的信息量，且平均码长最短，可分离的变字长编码的码字称为最佳变长码。为此必须将概率大的信息符号编以短的码字，概率小的信息符号编以长的码字，使得平均码长最短。能获得最佳编码的方法主要有：香农（Shannon）编码、费诺（Fano）编码、霍夫曼（Huffman）编码等。1）香农编码香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值。香农编码法冗余度稍大，实用性不大，但有重要的理论意义。其编码步骤如下：2）费诺编码费诺编码得到的费诺码要比香农编码得到的香农码的平均码长小，且消息传输速率大，编码效率高，属于概率匹配编码。编码步骤如下：（1）将信源消息符号按其出现的概率大小依次排列：p1≥p2≥…≥pn。（2）将依次排列的信源消息符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。（3）将每一大组的信源消息符号再分为两组，同样使这两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。（4）如此重复，直至每个组只剩下一个信源符号为止。3）霍夫曼编码霍夫曼编码（HuffmanCoding）是一种基于统计的无损压缩方法，这种方法是目前压缩方法中应用最普遍的方法。该方法完全依据字符出现概率来构造字符编码，概率小的码字长度长，概率大的码字长度短。霍夫曼编码的具体方法：先按不同字符出现的概率大小排队，把两个最小的概率相加，作为新的概率，并与剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成两个概率相加和为1。每次相加时都将“0”和“1”赋予相加的两个概率，读出时由该符号开始一直走到最后的“1”，将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码。其中，相加的过程可以利用霍夫曼树来表示。3.3.3霍夫曼二叉树的建立普通的编码都是定长的，比如常用的ASCII编码，每个字符都是8bit。表给出了部分字母符号的ASCII编码。这样，计算机就能很方便地把由0和1组成的数据流解析成原始信息，但在很多情况下，数据文件中的字符出现的概率是不均匀的，比如在一篇英语文章中，字母“E”出现的频率最高，“Z”最低，如果使用不定长的bit编码，频率高的字母用比较短的编码表示，频率低的字母用长的编码表示，就可以大大缩小文件的空间。但这要求编码要符合“前缀编码”的要求，即较短的编码不能是任何较长的编码前缀，这样解析的时候才不会混淆，比如表中的编码方法就符合前缀原则。根据表，下面的数据就可以唯一地解析成原始信息了：1110010101110110111100010→DABBDCEAAB要生成前缀编码，最方便的方法就是建立二叉树。图所示为一个二叉树例图。把要编码的字符放在二叉树的叶子上，所有的左节点是0，右节点是1，从根浏览到叶子上，因为字符只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径，符合前缀原则编码就可以得到编码结果。二叉树例图的编码结果如表所示。现在开始考虑压缩的问题，如果有一篇只包含这五个字符的文章，而这几个字符的出现的次数如下：A:6次B:15次C:2次D:9次E:1次操作码采用定长的编码，每个字符3bit，则这篇文章的总长度为3×6+3×15+3×2+3×9+3×1=99而用二叉树生成的编码的总长度为2×6+3×15+3×2+2×9+2×1=83显然，这棵树还可以进一步优化，使得编码更短，如图所示。构造更优的二叉树，其原则是权重越大的叶子，距离根应该越近。而终级目标是生成“最优”的二叉树，最优二叉树必须符合下面两个条件：（1）所有上层节点都大于等于下层节点；（2）对于某节点，设其较大的子节点为m，较小的子节点为n，m下任一层的所有节点都应大于等于n下该层的所有节点。3.3.4霍夫曼编码和解码过程1.霍夫曼编码过程1）建立霍夫曼树完成霍夫曼的编码需要首先建立霍夫曼树，之后对所有字符根据权重进行编码，最后再对文件内容进行编码。建立霍夫曼树的思想：首先定义适合霍夫曼树的节点类型，需要定义的有当前节点的字符，当前节点的左子、右子和父亲指针。在建立霍夫曼树之前还需要对出现的字符和权重进行统计和记录，并且定义一个可以筛选出最小权重的函数。建立霍夫曼树的过程：初始化树节点之后开始建立霍夫曼树。先在所有可能出现的字符中筛选出当前权重最小的两个字符，将这两个字符分别作为新节点的左子和右子建立一个小的二叉树，并将两个字符的权重之和赋值给新节点，将新二叉树放入筛选字符中，再将筛选过的两个字符从筛选列表中淘汰掉。依次对列表中剩下的字符进行权重最小的筛选，直到根节点（如果编码表共有N个字符，则2×N-1就为最终根节点）为止，也就是当筛选列表为空的时候，霍夫曼树即建立完成。对于霍夫曼编码树来说，由于霍夫曼编码是前缀码，所以所有要编码的字符最终都将是这棵树的叶子节点，而其他节点并没有真正的字符意义。即当霍夫曼编码树建立之后，对树的所有叶子节点进行打印可知道是否有字符遗漏或多余。美国品牌专家Davidson曾提出过一个“品牌冰山”的理论，意思是说品牌就像大海中的一座冰山，消费者只能看到浮在海面上的部分，海面下的部分只能去感受和体会。这其中，海面下的部分是隐性的品牌内涵，如品牌理念、品牌的核心价值、品牌个性、品牌文化等。海面上的部分就是显性的品牌符号，如品牌名称、品牌标识、品牌形象代表、品牌口号、品牌音乐、品牌包装等。3.1品牌理念1.品牌理念定义品牌理念应该包括核心概念和延伸概念，必须保持品牌理念与概念的统一和完整，具体包括企业业务领域、企业形象、企业文化、产品定位、产品风格等的一致。品牌理念是得到社会普遍认同的、体现企业自身个性特征的、促使并保持企业正常运作以及长足发展而构建的并且反映整个企业明确经营意识的价值体系。2.品牌理念构成品牌理念由企业使命、经营思想和行为准则三个部分内容构成：(1)企业使命。企业使命是指企业依据什么样的使命开展各种经营活动，是品牌理念最基本的出发点，也是企业行动的原动力。(2)经营思想。经营思想是指导企业经营活动的观念、态度和思想。经营思想直接影响着企业对外的经营姿态和服务姿态。不同的企业经营思想会产生不同的经营姿态，会给人以不同的企业形象的印象。2）建立霍夫曼码表构建完霍夫曼树后，根据霍夫曼树建立霍夫曼码表。建立编码表时要根据每个出现的字符的权重对建立的霍夫曼树的每个叶子节点进行编码。编码时要从叶子节点出发向根节点进行逆向编码。判断如果当前节点为左子则对其编码“0”，如果当前节点为右子则对其编码“1”。以此类推进行编码直到根节点为止。此时的编码是逆向的，所以需要将码值逆向存储。依次对每一个叶子节点进行编码操作，即可得到当前霍夫曼树的编码表。3）进行编码有了码表就可以进行编码了。首先需要建立一个原始文件，在文件中输入需要编码的内容。之后将文件打开，把其中的内容存储到字符串中以便程序编码调用。然后，对需要编码的字符进行编码，将字符逐一读取与刚刚建立的编码表中的每个叶子节点代表的字符进行比较，找出相同的对象，并将当前节点的编码打印到屏幕，再将编码存入到新建的密码文件当中。2.霍夫曼解码过程首先打开密码文件，将之前编码后得到的密文内容存储到字符串中以便解码调用。然后对密文的字符串进行解码，树索引从根节点开始走，当密文中的当前字符是“0”的时候，则索引走向左子节点；当是“1”的时候，则走向右子节点。以此类推，一直走到叶子节点为止，则当前叶子节点所代表的字符即为前一段密文的解码结果。最后对下一个字符依次从根节点开始解码，如此循环对每一段密文进行解码直到解码结束，将解码结果存入到新的解码文件当中。3.3.5霍夫曼编码的特点（1）霍夫曼编码的构造方法是确定的，但得出来的编码结果却是不确定的。一是在编码过程中对于两个概率值赋予“1”，和“0”的关系不确定（可以大概率赋“1”，小概率赋“0”，反之也可行）；二是在编码过程中若是存在相同概率的两个值，两个概率的排序也是随机的。因此，霍夫曼编码的结果并不确定。此外，霍夫曼编码是依据信源符号的概率分布，其编码效率取决于信源的统计特性，当信源符号的概率相等时，其编码效率最低。因而只有在符号概率分布不均匀时，霍夫曼编码才可以展现出明显的优势。（2）由于霍夫曼编码采用的是变长编码，码字不等长，就导致硬件实现很困难（尤其是译码部分），而且在抗误码方面能力也比较弱。（3）霍夫曼编码后，会形成一个霍夫曼编码表，解码时需要参照这一编码表才可以正确解码。因而要求在传输过程中必须传输此表，也就需要考虑此编码表在实际传输中占据的比特数。在实时性要求较强的场合，可以采用霍夫曼编码表缺省的方式，按照其遵循的统计特性直接在接收端预置固定的编码表，节省了传输时间。该方法需要统计和编码两遍扫描源数据流。后来Gallager在1978年进行了改进，取消了统计过程，一边压缩数据，一边动态地调整霍夫曼树，提高了压缩速度，人们称之为自适应霍夫曼编码（AdaptiveHuffman）或动态霍夫曼算法（DynamicHuffman）。3.3.6霍夫曼编码实例——基于DCT的静止图像压缩1.二维离散余弦变换（2DDCT）基于DCT的顺序型编码是JPEG算法的核心内容，是基于变换的有损压缩。图3-3-13给出了基于变换的静止图像的压缩算法框图。3.3.7算术编码Huffman编码保持整数比特的码字分配，在这种约束下，它是一种最优编码。如果信源中符号出现的概率是1/2的各次幂，则Huffman编码可以达到信源的熵，但这在实际中一般是不可能实现的。Huffman编码的另一个限制对二元信源是无效的，即如果一个信源由两个符号组成，就只能分配0和1两个码字给两个符号，平均码长是1，如果两个符号的出现概率相差很大，编码效率将会很低。算术编码的产生解决了这一难题，该算法由Elias提出，这种思想和霍夫曼方法相似，也是根据字符出现几率的统计结果进行重新编码的。霍夫曼方法必须用整数个位来表示每个字符，算术编码方法打破了这一限制，它通常把一个较长的码字分配给整个输入流，而不是给信源的各个符号分别分配码字。算术编码是20世纪80年代发展起来的一种熵编码方法，它按照符号序列的出现概率对概率数直线进行区间分割，并把表示已分割区间内的二进制小数作为相应序列代码。由于它是通过算术运算逐步形成码字的，因而称之为算术编码，它的主要步骤如下：（1）定义当前区间为［0，1）。（2）对输入流的每个符号s，重复下面的两步：①把当前区间分割为长度正比于符号概率的子区间。②为s选择一个子区间，并将其定义为新的当前区间。（3）按照以上步骤把整个输入流处理完后，输出位于当前区间中的任何数字，并且该数字能够唯一确定当前区间。3.3.8Huffman编码和算术编码的比较Huffman编码和算术编码各有优劣。两者都是变长码，符号出现概率越高，码字越短。不同之处在于，Huffman编码每个符号对应的码字是确定的，每个码字的bit数为整数。算术编码的基本思想是用一个精度足够高的实数来表示整个输入序列，输入序列中每个符号对应的码字是不确定的，总体上每个符号对应的码字长度等于其信息熵（均以bit计），码字平均长度可能是小数。表3-3-6所示为Huffman编码与算术编码的比较。

任务3.4多媒体信息的游程编码

学习目标（1）掌握游程的概念。（2）能够对简单的序列进行游程编码。（3）掌握游程编码的流程和具体实现过程。（4）理解LZW的编码过程。任务分析（1）根据游程的概念分析游程编码的实现过程。（2）比较游程编码和霍夫曼编码的编码过程，分析其特点及应用范围。（3）根据游程编码的流程，利用MATLAB具体实现二值图像的压缩。3.4.1游程的概念在一些待编码的信源序列中，有些符号经常连续出现。例如，传真图像如果按行扫描，则经常出现连续的0或1；另外，在有失真编码时，信号经过变换和量化后的系数集中，也会经常出现连续的0。针对这些情况，可以采用游程编码进行压缩编码。游程编码又称行程编码或游程（行程）长度编码（RunLengthEncoding，RLE），是一种利用空间冗余度压缩图像的方法，属于熵编码。“游程长度”指的是由字符（或信号取样值）构成的数据流中各个字符重复出现而形成的字符的长度，简称游程。以灰度图像编码为例，灰度值相同的相邻像素的延续长度（像素数目）即为游程。游程编码是一种非常简单的数据压缩编码形式。这种编码方法建立在数据相关性的基础上。重复的数据值序列（或称为“流”）用一个重复次数和单个数据值来代替。这里，重复的次数称为“游程”。实际应用时，一般采用多种形式的RLE编码。一种常用的格式是由一个控制符、一个重复次数字节和一个被重复的字符构成的3字节码字。游程编码是针对一些文本数据的特点而设计的，主要是去除文本中的冗余字符或字节中的冗余位，从而达到减少数据文件所占用存储空间的目的。为了数据压缩的通用性，一般很少单独采用该方法，而是与其他编码技术配合使用。例如游程编码结合霍夫曼编码形成了一种有效的编码方法——有效值映射。在JPEG中，就综合使用了游程编码、DCT、量化编码以及霍夫曼编码。游程编码对传输误差很敏感，一旦有1位符号出错就会改变游程编码的长度，从而使整个图像发生偏差，因此一般要用行同步、列同步的方法把差错控制在一行一列之内。游程编码具有以下特点：（1）游程编码仍是变长码，需要大量的缓冲和优质的信道。（2）游程长度可以从1一直到无限，这在码字的选择和码表的建立方面都有困难，尚需采用某些措施来改进。（3）游程长度越长，其概率越小。对于小概率的码字，其长度为达到概率匹配或较长时，损失不会太大。（4）游程编码对平均码字长度影响较小。游程编码算法存在以下缺点：（1）游程算法一般不直接应用于灰度图像，比较适合于二值图像的编码。（2）游程编码要想达到较好的压缩效果，图像中就必须出现连续的0或者连续的1，假如一旦用于编码的数组不出现这种连续的0或者连续的1时，游程编码就难以实现压缩效果。（3）游程编码算法一般不单独使用，与霍夫曼编码混合使用的时候较多。3.4.2游程编解码实现流程用游程编码压缩数据时，首先要计算每次