音频处理技术二.ppt

第2章 音频处理技术（二）,西安交通大学计算机教学实验中心2007,多媒体技术及应用基础,第2|82页,问题的提出,数字音频信息如何处理？用什么工具可以处理？有哪些处理？我能处理吗？,第3|82页,二、数字音频,数字音频原理回顾,第4|82页,声音的数字化,声音的数字化 数字化就是将连续信号变成离散信号。对音频信号，首先在时间上离散，取有限个时间点，称为采样。然后在幅度上离散，取有限个幅度值，称为量化。再将得到的数据表示成计算机容易识别的格式，称为编码。,第5|82页,声音的A/D与D/A转换,模拟信号很容易受到电子干扰，因此用数字信息代替声音信号成为音频信息处理的一种方法。A/D转换和D/A转换技术便应运而生。A表示Analog”（类比、模拟），D代表“Digital”（数字），A/D转换就是把模拟电信号转换成由“0”和“1”组成数字信号的过程。这样做的好处是显而易见的，声音存储质量得到了加强，数字化的声音信息使计算机能够进行识别、处理和压缩，这也就是为什么如今磁带逐渐被淘汰，CD唱片却趋于流行的原因。A/D转换的一个关键步骤是声音的采样和量化，得到数字音频信号，它在时间上是不连续的离散信号。,第6|82页,PCM编码,1939年法国工程师Alec Reeves发明了将连续的模拟信号变换成时间和幅度都离散的二进制码代表的脉冲编码调制信号（Pulse Code Modulation-PCM），并申请了专利。P首先开始应用于电话系统，但一直到年美国Bell实验室才为制成了国际上第一套商用电话系统（系统），这标志了通信开始步入数字化。PCM 编码是对连续语音信号进行空间采样、幅度值量化及用适当码字将其编码的总称。,第7|82页,PCM编码主要优点,抗干扰能力强；失真小；传输特性稳定，尤其是远距离信号再生中继时噪声不累积，而且可以采用压缩编码、纠错编码和保密编码等来提高系统的有效性、可靠性和保密性。,第8|82页,A/D 和D/A转换示意图,8位可编程A/D转换芯片,示意图,第9|82页,模拟声音信号的采样和量化过程示意,模拟声音信号的波形,采样得到的离散时间信号,再量化得到的数字信号,第10|82页,数字音频的技术指标,采样频率采样精度声道数音频数据传输率编码算法与音频数据压缩比,第11|82页,采样频率,采样频率是指一秒钟采样的次数。采样频率越高，单位时间内采集的样本数越多，得到波形越接近于原始波形，音质就越好。根据奈奎斯特(Harry Nyquist)采样理论：如果采样频率高于输入信号最高频率的两倍，重放时就能从采样信号序列无失真地重构原始信号。,第12|82页,采样的3个常用频率,分别为：11.025kHzAM(调幅)广播22.05kHz FM(调频)广播44.1kHz CD高保真音质声音现在声卡的采样频率一般为48kHz甚至96kHz。,第13|82页,采样精度,采样精度用每个声音样本的位数表示，也叫样本精度或量化位数，反映度量声音波形幅度的精度。例如，每个声音样本用16位表示，则量化样本值在065535之间，它的精度是输入信号的1/65536。采样精度决定了模拟信号数字化以后的动态范围。采样精度影响到声音的质量位数越多，声音的质量越高，而需要的存储空间也越多；位数越少，声音的质量越低，需要的存储空间越少。,第14|82页,声道数,单声道(mono)信号一次产生一组声波数据。双声道或立体声(stereo)一次产生两组声波数据。双声道在硬件中占两条线路，一条是左声道，一条是右声道。立体声不仅音质、音色好，而且能产生逼真的空间感。但立体声数字化后所占空间比单声道多一倍。,第15|82页,其他因素,除采样频率、采样精度、声道数影响声音质量外，声音录制时环境噪声、声卡内部噪声以及采样数据丢失等都会造成声音质量的下降。实际收听时，音响（功率放大器、扬声器等）的质量对音质的表现也起很大作用。,第16|82页,音频数据传输率,音频信号数字化后，产生大量数据。产生数据的速度或播放声音时需要传输数据的速度影响声音的播放质量。数据传输率用每秒钟传输的数据位数表示，记为bps（bit per second）。未经压缩的数字音频数据传输率为：数据传输率(bits)=采样频率(Hz)量化位数(bit)声道数,第17|82页,声音质量和数字化指标,第18|82页,编码算法与音频数据压缩比,未压缩的音频数据量非常大，因此在编码的时候常采用压缩的方式。实际上，编码的作用一是记录数字数据，二是采用一定的算法来压缩数据以减少存储空间和提高传输效率。压缩编码的基本指标之一就是压缩比，一般为数据压缩前后的数据量之比：,第19|82页,数据压缩说明,采用不同的数字化指标实际上也是进行了不同比例的数据压缩。如果PCM编码采用4bit量化对CD音质信号压缩，其压缩比为4:1。压缩算法包括有损压缩和无损压缩；有损压缩解压后数据不能完全复原，要丢失一部分信息。无损压缩不丢失任何信息，能较好地复原原始信号。,第20|82页,数字音频文件格式,数字声音文件格式是数字音频在磁盘文件中的存放形式，相同的数据可以有不同的文件格式，而不同的数据也可以有相同的文件格式。WAVE 格式MP3 格式RA 格式,第21|82页,WAVE文件格式,WAVE文件是一种通用的音频数据文件，文件扩展名为“WAV”，Windows系统和一般的音频卡都支持这种格式文件的生成、编辑和播放。CD激光唱盘中包含的就是WAVE格式的波形数据。一般说来，声音质量与其WAVE格式的文件大小成正比。WAVE文件的特点是易于生成和编辑，但在保证一定音质的前提下压缩比不够，不适合在网络上播放。,第22|82页,MP3文件,MP3文件是采用MP3算法压缩生成的数字音频数据文件，以“.MP3”为文件后缀。MP3利用MPEG制定的MPEG-1 Audio layer 3的压缩标准，将音频信息用10:1甚至12:1压缩率变成容量较小的数据文件。虽然MP3是一种利用了人类心理声学特性的有损压缩，人耳基本不能分辨出失真，音质几乎达到了CD音质标准。按照这种算法，10张CD-DA的内容可以压缩到l张CD-ROM中，而且视听效果相当好。,第23|82页,RA文件,Real Audio是Real networks推出的一种音乐压缩格式，它的压缩比可达到96:1，因此在网上比较流行。经过压缩的音乐文件可以在通过速率为14.4kb/s的MODEM上网的计算机中流畅回放。其最大特点是可以采用流媒体的方式实现网上实时播放，即边下载边播放。,第24|82页,五、多媒体数据的编码技术,自然现象：我们了解的东西，描述它用的信息量少，不了解的东西，描述它用的信息量大。在信息论中，可以说：信息是用不确定的度量来定义的；一个消息的可能性越小，其信息含量越大；消息的可能性越大，则信息含量越小。,第25|82页,(1)信息和熵,香农（C.E.Shannon）信息论应用概率来描述不确定性。事件出现的概率小，不确定性越多，信息量就大，反之则少。在数学上，所传输的消息是其出现概率的单调下降函数。所谓信息是指从N个相等可能事件中选出一个事件，所需要的信息度量或含量，也就是在辨识N个事件中某个特定事件过程中所需提问“是”或“否”的最少次数。如从64个数中选定某一个数，提问：“是否大于32?”，则不论回答是与否，都消去了半数的可能事件，如此下去，只要问6次这类问题，就可以从64个数中选定一个数。因此，可以用二进制的6个位来记录这一过程，就可以得到这条信息。,第26|82页,信息源x的熵,第27|82页,例2-10,第28|82页,例2-11,第29|82页,香侬理论的要点,信源中含有自然冗余度，这些冗余度既来自于信源本身的相关性，又来自于信源概率分布的不均匀性，只要找到去除相关性或改变概率分布不均匀性的手段和方法，也就找到了信息熵编码的方法。但信源所含有的平均信息量（熵）是进行无失真编码的理论的极限，只要不低于此极限，就能找到某种适宜的编码方法，去逼近信息熵，实现数据压缩。,第30|82页,(2)信息冗余,多媒体数据中大的数据量并不完全等于它们所携带的信息量。在信息论中，称为冗余。冗余是指信息存在的各种性质的多余度。减少数据冗余可以节省存储空间，有效利用网络带宽。,第31|82页,数据冗余的类型,空间冗余 物理特性具有相关性。,时间冗余 相邻帧图像之间有较大的相关性。,信息熵冗余 自然编码的比特分配不能达到最佳。,视觉冗余 人眼不能察觉图像中的所有变化。,知识冗余 数据的理解与先验知识有很大的关系。例如，当接收到一个成语的前三个字“大惊小”时，就知道下一个字肯定是“怪”。,听觉冗余 人耳不能察觉所有频率的变化。,第32|82页,数据压缩的基本原理,数据压缩的对象是数据。数据是信息的载体，用来记录和传送信息。真正有用的不是数据本身，而是数据所携带的信息。大的数据量并不代表含有大的信息量。而对于去掉冗余的数据对信息没有本质的影响称为压缩。,第33|82页,(3)压缩算法的分类,从信息量有无损失划分：可逆编码和不可逆编码。可逆编码也叫无失真编码、冗余度压缩、熵编码等。其原理是减少数据中的冗余度，而不损失任何信息。解压时可以完全恢复出原来的数据，亦称无损压缩。典型的无损压缩有Huffman编码、算术编码和行程编码等。可逆编码由于不会产生失真，因此在多媒体技术中常用于文本、数据的压缩，它能保证完全地恢复原始数据。但这种方法的压缩比较低，一般在2:15:1之间。,第34|82页,不可逆编码,不可逆编码是有失真压缩，信息论中叫熵压缩。由于压缩了熵，会减少信息而不能再恢复。因此这种压缩又称有损压缩。在语音和图像中，由于存在视觉冗余和听觉冗余，减少这种信息并不影响人们的听觉效果和视觉效果，所以经常采用这种方法，有损压缩常用于数字化存储的模拟数据，并且主要应用于图像、声音、动态视频等数据的压缩。如果用混合编码的JPEG标准，对自然景物的彩色图像，压缩比可达到几十倍甚至上百倍。,第35|82页,压缩算法分类,根据压缩原理划分有预测编码、变换编码、矢量编码、子带编码、熵编码等。,第36|82页,1）预测编码,对于语音，就是通过预测去除语音信号时间上的相关性。而对于图像，帧内预测去除了空间上的冗余，帧间预测则可以去除时间上冗余。目前大多数语音、图像编码中都采用了预测技术。例如语音中的LPC(linear Predictive Coding，线性预测)、CELP(码激励线性预测)、图像中的ADPCM(自适应差分脉冲编码调制)等。,第37|82页,2）变换编码,变换编码首先把要压缩的数据变换到某个变换域中，然后再进行编码。变换域中表现为能量集中在某些区域，就可以利用这一特点在不同区域间有效地分配量化比特数，或者去掉这些能量很小的区域，从而达到数据压缩的目的。例如声音中的频谱分析实际上是对语音波形进行了快速傅里叶变换（FFT），将时域信号变到了频域中，可以清楚地看到能量集中在哪些频率范围内。,第38|82页,3）矢量量化,矢量量化是利用相邻数据间的相关性，将数据序列分组进行量化的一种压缩方法。和预测编码一样，矢量量化本质也是利用数据序列的统计相关性进行压缩的。,第39|82页,4）子带编码,子带编码首先让原始数据分别通过若干个具有不同通频带的滤波器，将信号分成多个子带信号输出，然后分别对各个滤波器的输出进行编码。当滤波器选取得合适时，它们的输出将各自具有不同的分布特性，对各频段进行不同的量化处理，可以有效地进行数据压缩。,第40|82页,5）熵编码,根据信息墒的原理，用短码表示出现概率大的数据，用长码表示出现概率小的数据。这是一种无损数据压缩技术，在语音和图像编码中常常和其它有损压缩编码方法结合使用。,第41|82页,2.基本压缩编码方法,哈夫曼(Huffman)编码在1952年为文本文件而建立。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。,第42|82页,例2-12,设信号源为X=、a、e、I、m、t、c、h、r。对应的概率为p=O.22、0.22、0.14、O.07、0.07、0.07、0.07、0.07、0.07,试给出该信源的霍夫曼编码方案。若传送一个串字符串“I am a teacher”，共14个字符。若用ASCII传送，每个字符8位，共需112位。该字符串中有9个不同的符号，至少需要4位二进制才能表示，这样传送该字符串也要56位。若用刚计算的Huffman编码，只需要42位。,第43|82页,霍夫曼编码过程,第44|82页,(2)行程编码原理,由字符(或信号采样值)构成的数据流中相同的字符(或字符串)会连续重复出现，重复出现的字符长度称为游程长度RL（Run Length）。如果给出了形成串的字符，串的长度及串的位置，就能复出原来的数据流。行程编码RLC(Run Length Coding)就是用二进制码字给出上述信息的一类方法。行程编码又称“运行长度编码”或“游程编码”,第45|82页,例2-13,设有数据流“AAABBBBCCCCCDAAAAAA”，试计算该数据的行程编码。解：A重复3次，B重复4次，C重复5次，D不重复，A重复6次，RLC数据流为：“SA3SB4SC5DSA6”，其中S为指示符。总共占用13个字节，而源数据占用19个字节。有时行程编码不用指示符，重复与否相同对待，则相应的RLC为“A3B4C5D1A6”占用10个字节。,第46|82页,3.数字音频压缩标准,1.电话质量的语音压缩标准。,电视会议的语音编码、为提高线路利用率的多媒体多路复用装置、数字录音电活的数字记录部件以及高质量的语音合成器;数字移动通信、无绳电话。ITU 国际电信联盟 International Telecommunication Union,第47|82页,(2)调幅广播质量的音频压缩标准,调幅广播质量音频信号的频率范围是50Hz7kHz，又称“7kHz音频信号”，当使用16kHz的采样频率和14bit的量化位数时，信号速率为224kbs。1988年ITU制定了G.722标准，它可把信号速率压缩成64kbs。G.722标准基于子带ADPCM技术(SBADPCM)，将现有的带宽分成两个独立的子带信道，使输入信号进入滤波器组分成高子带信号和低子带信号，然后分别进行ADPCM编码，最后进入混合器形成输出码流。这种压缩方法能够在每秒8kB的存储量下给出相当好的音乐信号，也很适合于需要存储大量高质量音频信号的多媒体系统使用。,第48|82页,(3)高保真立体声音频压缩标准,高保真立体声音频信号的频率范围50Hz20kHz，在44.1 kHz采样频率下用16bit量化，信号速率为每声道1410kbs。目前国际上比较成熟的高保真立体声音频压缩标准为MPEG音频。MPEG Audio是一个子带编码系统，声音数据压缩算法的根据是心理声学模型。心理声学模型中一个最基本的概念是听觉系统中存在一个听觉阈值电平，低于这个电平的声音信号就听不到。听觉阈值的大小随声音频率的改变而改变，各个人的听觉阈值也不同。大多数人的听觉系统对2kHz5kHz之间的声音最敏感。一个人是否能听到声音取决于声音的频率，以及声音的幅度是否高于这种频率下的听觉阈值。,第49|82页,MPEG,MPEG声音(ISO/IEC 11172-3)压缩算法是世界上第一个高保真声音数据压缩国际标准，并且得到了极其广泛的应用。MPEG声音标准是MPEG标准的一部分，但它也完全可以独立应用。MPEG声音标准提供三个独立的压缩层次：层1(Layer 1)、层2(Layer 2)和层3(Layer 3)，用户对层次的选择可在复杂性和声音质量之间进行权衡。,第50|82页,四、数字音频处理,本节介绍数字音频的应用技术，包括声音的采集、编辑以及音效处理。编辑工具：Windows下的录音机Sound ForgeGoldWave,第51|82页,1、基本操作,通过下例学习文件的打开、声道的转换、数字化指标的转换、提高音量和文件格式转换 例2.4 example_0220.wav文件是一个双声道立体声语音文件，采样频率44.1kHz，采样精度32位，请对其做以下处理：将双声道声音转换成单声道声音；采样频率转换为8kHz，样本精度转换成16位；将其音量提高20%;将文件格式转换为mp3格式，话音质量。,第52|82页,操作步骤,打开文件。使用“FileOpen”命令打开声音文件example_0220.wav 声道转换。执行“ProcessChannel Converter”命令 修改技术指标。执行“processResample”命令，输入新的采样频率“8,000”；设置位深。执行“ProcessBit-depth Converter”命令，在打开的对话框中设置“Bit depth”为“16”位。提高音量。执行“ProcessVolume”菜单命令 保存文件为mp3文件。执行“FileSave As”命令，保存类型选择“MP3 Audio(*.mp3)”，单击“Template”右边的“Custom”按钮，打开“Custom Setting”（自定义设置），选择“Bit Rate”为“8kbps 8,000Hz”，单击“OK”，并保存文件。,第53|82页,2、声音的录制与格式转换,在使用计算机进行录音时，话筒的插头应插入声卡的MIC(话筒)输入插座内。声卡有两个输入插座，一个用于话筒，一个用于线路输入。用于话筒的插座灵敏度高，一般为O.53mv，适于输入微弱的信号；用于线路输入的插座灵敏度低，主要与音响设备的线路输出端连接，适于输入强度较大的信号，一般为5001000mv。上述两个插座不要混淆。如果把话筒插在线路输入插座内，将录不到声音。,第54|82页,(1)质量选择,录制声音时应根据不同的要求选择不同的质量参数，包括采样频率、样本位数、声道数、编码格式等。录音时，应注意调整输入信号的强度，使其不超过录音设备的动态范围，否则将产生削顶失真，音感阻塞，严重时无法辨别声音的内容。信号强度过低，也不能获得满意的声音，原因是信号与噪声的比值小，噪声相对比较明显，影响了音质。正式录音前，最好先试录一次，以调整音响效果。,第55|82页,(2)声音格式的转换,一般的声音处理软件兼容多种格式的声音文件，使得声音格式的转换非常简单，只要在保存文件时使用“另存为”，然后选择不同的文件格式、质量级别、压缩算法或不同的性能指标。例2.5 以22.1kHz的采样频率、16位位深度录制以下唐诗。去除录制过程中过长的停顿、喀喀声，调整音量，分别将其保存为WAV文件、FM音质的MP3文件和rm文件。,第56|82页,3、朗读并录音,为人进出的门紧锁着 为狗爬出的洞敞开着 一个声音高叫着“爬出来吧，给你自由”我，渴望自由 但我深深地知道：人的身躯怎能从狗洞里爬出 我希望有一天 地下的烈火将我和这口活棺材一起烧掉 我，愿在烈火中永生！,第57|82页,录音操作步骤,环境准备启动Sound Forge创建新文件选择音频格式参数录音按指定文件格式保存,第58|82页,环境准备,连接话筒，在Windows控制面板中双击“声音和多媒体”图标，打开“声音和多媒体”对话框（图2-19a），选择“音频”选项卡，单击“录音”选框中的“音量”按钮，打开“Recording Control”（录音控制）对话框。如果使用话筒录音，则在“Microphone”下的小方框中打“”，音量滑块调到90%左右。,第59|82页,启动Sound Forge,第60|82页,创建新文件,选择“File”“New”，创建一个新文件。,第61|82页,选择格式参数,选择采样频率,选择位深度,选择声道数,第62|82页,录音,单击工具栏中录音按钮，打开“Recording”对话框，单击“录音”按钮。,第63|82页,编辑调整,在编辑窗口中没有波形的区域是没有声音的区域。不做任何选择，执行“ProcessVolume”菜单命令调整整体音量的大小，也可选择某个区域调整音量。,第64|82页,保存文件,执行“FileSave As”保存声音文件。保存WAV文件选择文件类型“Wave(Microsoft)(*.wav)”；保存MP3 文件选择文件类型“MP3 Audio(*.mp3)”，模板选择“64kbps,FM Radio Quality Audio”；保存RM文件选择文件类型“RealMedia(*.rm)”，模板选择“56kbps Audio”，适合使用56k MODEM以上线路上网的用户，也可选其他模板。保存的3个文件的大小分别为545kB、101kB和56kB，时间长度为12秒。,第65|82页,4、声音的剪辑,声音文件可以进行剪辑操作：删除就是去掉声音文件中的一段数据。两段数据排列顺序的不同就改变了声音播放的先后顺序。将两个文件中的声音数据连接起来保存在一个文件中就实现了声音的连接。当然也可以将原来的声音文件分成两个声音文件存放，就实现了声音的分割。,第66|82页,剪辑操作步骤,确定编辑区域；选定起点（Mark In）和终点（Mark Out）声音编辑，编辑操作可以使用“Edit”菜单中的命令，也可以使用与Word相同快捷键。去除噪声；去除噪声使用“EffectNoise Gate”菜单命令。静音处理,“Process Mute”例2.6 笨狼上学,第67|82页,5、声音的效果处理,淡入淡出频率均衡控制混响合唱效果声音的混合声道摇动,第68|82页,(1)淡入淡出,“淡入（Fade In）”和“淡出（Fade Out）”指声音的渐强和渐弱，通常用于声音的开始、结束，两个声音素材的交替切换，产生渐近渐远的音响效果等场合。淡入效果使声音从无到有、由弱到强。而淡出效果则正好相反，声音逐渐消失。淡入与淡出的过渡时间长度由编辑区域的宽窄决定。淡入淡出常用于节目的开始、结尾和两段声音之间的过渡，使声音的出现和消失不太突然。,第69|82页,实现方法,在SoundForge中选择一段声音，执行：“ProcessFadeIn”（淡入）“ProcessFadeOut”（淡出）产生淡入或淡出效果，也可以使用：“ProcessFadeGraphics”命令在打开的对话框中拖动增益曲线随意地编辑淡入和淡出效果。,第70|82页,淡入淡出效果声音波形,淡入淡出声音,第71|82页,(2)频率均衡控制,频率均衡（EQ）控制指对声音素材的低音区、中音区、高音区各个频段进行提升和衰减等控制，使声音的层次和频段分布更符合要求。这一技术从根本上改变了音频文件的固有频率均衡值。频率均衡使用“ProcessEQ”命令,第72|82页,均衡效果示意图,源音,滤掉部分低频的均衡效果,均衡控制指对不同频段的声音音量的调整，可以使声音产生清脆、低沉、柔和等效果。,第73|82页,(3)混响,声音在传播过程中遇到障碍物，会产生反射、绕射及散射。因此形成直达声、反射次数较少的早期反射声和多次反射形成的混响声。混响是乐器或话音及从物体表面反射回来的声音的混合，用软件模拟混响的原理是将滞后一段的声音提前加到原声音上播放。混响时间的长短可以改变音色，混响时间短，声音干涩；混响时间长，声音圆润，具有空旷感。,第74|82页,数字混响的基本原理,把指定编辑区域内的声音滞后一小段时间再叠加到原来的声音上。影响混响效果的参数是叠加声音的音量和滞后时间长度。根据延迟信号的延迟时间和幅度的不同，可以调制出任何大小房间、音乐厅、礼堂、教堂、山谷等环境的音响效果。混响时间短，声音干涩，声音就像在近前发出的一般；混响时间长，声音圆润，具有空旷感。命令：EffectsReverb,第75|82页,混响效果,混响源音,混响效果,第76|82页,(4)合唱效果,合唱效果可以把一个人的声音变成两个的声音，把两个人的声音变成4个人等，从而产生合唱效果或把小乐队的演奏变成大乐队的合奏效果 影响合唱效果的参数主要有三个：合唱程度（Chorus Size）、调制速率（Modulation Rate）和合唱输出（Chorus Out）。它们的值越大，效果越明显。命令：EffectsChorus,第77|82页,(5)声音的混合,声音混合将两段声音混合在一起，可以为自己的歌曲或语音配上音乐。将两段声音混和在一起，首先要保证两段声音的采样频率相同。为保证质量，应将低的采样频率改为高的采样频率。命令序列：ProcessResample EditCopy EditPaste SpecialMix（注）,第78|82页,声道摇动,可以让声音交替地从左右声道上发出，产生声的立体效果，称为摇动（Pan,平底锅）。命令：ProcessPan,第79|82页,摇动编辑对话框,第80|82页,添加摇动效果的声音波形,摇动效果,第81|82页,5.声音的频谱分析,频谱分析（Spectrum Analysis）是分析数字音频频率分布情况的强有利工具，使用它可以很清楚地看到所处理的声音文件中各种频率的声音的分布情况。命令:ToolsSpectrum Analysis,该声音频率范围在20-3.3kHz内,量化只要8kHz的采样频率即可。,第82|82页,作业,第2章2,5,7,11,实验制作音频作品,第83|82页,Huffman(哈夫曼）编码,Huffman树的定义构造Huffman树Huffman编码Huffman编码的译码,第84|82页,Huffman树的定义,Huffman树也称为最优树，是一类带权路径最短的二叉树。树的带权路径长度定义为：,其中：n 是树中叶结点的个数 wi 是第i个结点的权值 li 是第i个结点的路径长度,第85|82页,Huffman树举例,以下有三棵树：,（a）,（b）,（c）,a,b,c,d,a,b,c,d,a,c,b,d,7,7,7,5,5,5,2,2,2,4,4,4,WPLa=7x2+5x2+2x2+4x2=36,WPLb=7x3+5x3+2x1+4x2=46,WPLc=7x1+5x2+2x3+4x3=35,事实证明按哈夫曼树构造二叉树，可得到很好的特性，应用于实际问题，可提高处理效率。,第86|82页,应用举例,由统计规律可知，考试成绩的分布符合正态分布：,-1,1,0,分数 059 60 69 70 79 80 89 90 100,比例数 0.05 0.15 0.40 0.3 0.10,根据正态分布规律，在6090之间的分数占85%，而不及格和优秀是少数。,第87|82页,将百分制转换成五分制,判定树比较：,a60?,a70?,a80?,a90?,不及格,及格,中等,良好,优秀,Y,Y,Y,Y,N,N,N,N,a80?,a70?,a90?,a60?,不及格,优秀,良好,中等,中等,及格,不及格,Y,Y,Y,N,N,N,N,Y,Y,(A),(B),若输入1万个数据，按A的判定过程进行操作，约需比较3.2万次，而按B比较,则仅需2.2万次。,第88|82页,构造Huffman树,构造Huffman树算法步骤：Step1 将n个带权值wi（in）的结点构成n棵二叉树的集合T=T1，T2，Tn，每棵二叉树只有一个根结点。Step2 在T中选取两个权值最小的结点作为左右子树，构成一个新的二叉树，其根结点的权值取左右子树权值之和；Step3 在T中删除这两棵树，将新构成的树加入到T中；Step4 重复2）、3）步的操作，直到T中只含一棵树为止，该树就是Huffman树。,第89|82页,构造Huffman树举例,以权值分别为7，5，2，4的结点a、b、c、d构造Huffman树。T=a b c d,（d）T=T1,（c）T=a T2,（b）T=a b T3,（a）T=a b c d,示例,第90|82页,Huffman编码,编码：用二进制数的不同组合来表示字符的方法。前缀编码：一种非等长度的编码(任一个字符的编码都不是另一个字符编码的前缀)。,a,0,b,0,1,c,d,0,1,1,编码：a（0）b（01）c（011）d（111）,方法约定：1）左分支为02）右分支为13）由叶到根路径上字符组成的二进制串就是该叶结点的编码。,Huffman编码：一种非等长度的编码。以给定权值的结点构造Huffman树，按二进制前缀编码的方式构成的编码为Huffman编码。,第91|82页,Huffman编码举例,在某系统的通信联络中可能出现8种字符，其频率分别为0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，设权值分别为5，29，7，8，14，23，3，11，n=8，其Huffman树为：,第92|82页,Huffman编码的译码,从Huffman编码树上不难看出，代码全部在叶结点上，根据Huffman编码，就能求出相应的字符。该过程称为“译码”。译码是根据从根到叶的Huffman编码求相应的字符。因此要知道每个结点的左右子结点。例如，根据“1111”，就能求出对应的字符是“8”。,0,0,0,0,0,0,0,1,1,1,1,1,1,1,5,3,7,8,14,29,11,23,42,58,100,返回,第93|82页,空间冗余,规则物体的物理相关性冗余分类。规则物体和规则背景表面的物理特性具有相关性。,返回,第94|82页,时间冗余,视频与动画画面间的相关性。相邻帧图像间有较大的相关性。,返回,第95|82页,结构冗余,规则纹理、相互重叠的结构表面。,第96|82页,视觉冗余,视觉、听觉敏感度和非线性感觉。人的视觉对图像的注意是非均匀的。一般分辨率能力为26灰度等级，而一般图像采用的是28灰度等级。,返回,第97|82页,信息熵冗余,编码冗余。数据所携带的信息量少于数据本身而反映出来的数据冗余。,返回,