《多媒体课程幻灯片5.ppt》由会员分享，可在线阅读，更多相关《多媒体课程幻灯片5.ppt（179页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第 6 章章多媒体数据压缩技术多媒体数据压缩技术6.16.1 数据压缩基本原理数据压缩基本原理数据压缩基本原理数据压缩基本原理 多媒体信息的数据量多媒体信息的数据量多媒体信息的数据量多媒体信息的数据量 数据压缩条件数据压缩条件数据压缩条件数据压缩条件 数据冗余数据冗余数据冗余数据冗余6.26.2 数据压缩算法数据压缩算法数据压缩算法数据压缩算法 数据压缩算法分类数据压缩算法分类数据压缩算法分类数据压缩算法分类 霍夫曼编码霍夫曼编码霍夫曼编码霍夫曼编码 JPEG JPEG 编码编码编码编码6.1.16.1.1多媒体信息的数据量多媒体信息的数据量多媒体信息的数据量多媒体信息的数据量6.1 6.1
2、 数据压缩基本原理数据压缩基本原理数据压缩基本原理数据压缩基本原理 文本文本文本文本 若若若若10247681024768显示分辨率、显示分辨率、显示分辨率、显示分辨率、16161616点阵文字、点阵文字、点阵文字、点阵文字、4 Byte/4 Byte/字，则一屏字，则一屏字，则一屏字，则一屏 汉字的总数据量为汉字的总数据量为汉字的总数据量为汉字的总数据量为:(1024/16)(768/16)4=12288 Byte (12KB)(1024/16)(768/16)4=12288 Byte (12KB)图像图像图像图像 若采用若采用若采用若采用10247681024768显示分辨率，则满屏图像的
3、总数据量为显示分辨率，则满屏图像的总数据量为显示分辨率，则满屏图像的总数据量为显示分辨率，则满屏图像的总数据量为:1024768log 1024768log2 2 256 8=786432 Byte (768 KB)256 8=786432 Byte (768 KB)音频音频音频音频 若采样频率为若采样频率为若采样频率为若采样频率为44100Hz44100Hz，16bit(2Byte)16bit(2Byte)，立体声，立体声，立体声，立体声 (2(2声道声道声道声道)，则则则则1 1分钟的总数据量为分钟的总数据量为分钟的总数据量为分钟的总数据量为:441002 Byte2(STEREO)60s
4、=10336 KB(10MB)441002 Byte2(STEREO)60s=10336 KB(10MB)多媒体信源引起了多媒体信源引起了多媒体信源引起了多媒体信源引起了“数据爆炸数据爆炸数据爆炸数据爆炸”如果不进行数据压缩如果不进行数据压缩如果不进行数据压缩如果不进行数据压缩,传输和存储都难以实用传输和存储都难以实用传输和存储都难以实用传输和存储都难以实用化化化化。压缩的必要性压缩的必要性压缩的好处：压缩的好处：1.数据存储容量数据存储容量空间域的压缩；空间域的压缩；2.提高传输信源速率，解决带宽瓶颈提高传输信源速率，解决带宽瓶颈时间域的压缩；时间域的压缩；3.开通各种并行业务（电视、传真、
5、电开通各种并行业务（电视、传真、电话、可视图文等）话、可视图文等）频率域的压缩；频率域的压缩；4.降低发射机功率降低发射机功率能量域的压缩。能量域的压缩。6.1.26.1.2 数据压缩条件数据压缩条件数据压缩条件数据压缩条件(可能性可能性可能性可能性)数据存在冗余数据存在冗余数据存在冗余数据存在冗余 (重复数据、可忽略数据重复数据、可忽略数据重复数据、可忽略数据重复数据、可忽略数据)数据传输与存储空间的限制数据传输与存储空间的限制数据传输与存储空间的限制数据传输与存储空间的限制 (压缩压缩压缩压缩 传输或存储传输或存储传输或存储传输或存储 解压缩解压缩解压缩解压缩)45.1kHz/Stereo
6、45.1kHz/Stereo 1.3MB 1.3MB 22.0kHz/Nomo22.0kHz/Nomo 0.3MB 0.3MB StopStop重复数据重复数据重复数据重复数据可忽略数据可忽略数据可忽略数据可忽略数据 不敏感因素不敏感因素不敏感因素不敏感因素 (颜色、亮度、频率、细节颜色、亮度、频率、细节颜色、亮度、频率、细节颜色、亮度、频率、细节)2 224 24 颜色颜色颜色颜色 (16,777,216(16,777,216色色色色)2 28 8 颜色颜色颜色颜色 (256(256色色色色)6.1.36.1.3 数据冗余数据冗余数据冗余数据冗余 冗余基本概念冗余基本概念冗余基本概念冗余基本
7、概念 冗余冗余冗余冗余 信息所具有的各种性质中多余的无用空间信息所具有的各种性质中多余的无用空间信息所具有的各种性质中多余的无用空间信息所具有的各种性质中多余的无用空间 冗余度冗余度冗余度冗余度 多余的无用空间的程度多余的无用空间的程度多余的无用空间的程度多余的无用空间的程度I=D I=D duduI I 信息量信息量信息量信息量 D D 数据量数据量数据量数据量 du du 冗余量，包含在冗余量，包含在冗余量，包含在冗余量，包含在D D中中中中 信息量与冗余的关系信息量与冗余的关系信息量与冗余的关系信息量与冗余的关系 冗余举例冗余举例冗余举例冗余举例播音员播音员播音员播音员 180 180字
8、字字字/分钟，分钟，分钟，分钟，2Byte2Byte一个字，一个字，一个字，一个字，360Byte360Byte (合合合合0.35KB0.35KB/分钟分钟分钟分钟)音频数据音频数据音频数据音频数据8kHz8kHz采样采样采样采样8bit608bit60秒秒秒秒 =3840KBit(=3840KBit(合合合合480KB480KB/分钟分钟分钟分钟)冗余分类冗余分类冗余分类冗余分类 1 1 空间冗余空间冗余空间冗余空间冗余（帧内相关）（帧内相关）（帧内相关）（帧内相关）规则物体的物理相关性规则物体的物理相关性规则物体的物理相关性规则物体的物理相关性2 2 时间冗余时间冗余时间冗余时间冗余（帧
9、间相关）（帧间相关）（帧间相关）（帧间相关）视频与动画画面间的相关性。视频与动画画面间的相关性。视频与动画画面间的相关性。视频与动画画面间的相关性。一组连续画面中的相邻帧往往包含相同的背景和移动物体，只不过一组连续画面中的相邻帧往往包含相同的背景和移动物体，只不过一组连续画面中的相邻帧往往包含相同的背景和移动物体，只不过一组连续画面中的相邻帧往往包含相同的背景和移动物体，只不过移动物体所在的空间位置略有不同，把一帧图像中的某物体或场景移动物体所在的空间位置略有不同，把一帧图像中的某物体或场景移动物体所在的空间位置略有不同，把一帧图像中的某物体或场景移动物体所在的空间位置略有不同，把一帧图像中的
10、某物体或场景可以由其他帧图像中的物体或场景进行处理后重构出来，可以大大可以由其他帧图像中的物体或场景进行处理后重构出来，可以大大可以由其他帧图像中的物体或场景进行处理后重构出来，可以大大可以由其他帧图像中的物体或场景进行处理后重构出来，可以大大减少时间冗余。减少时间冗余。减少时间冗余。减少时间冗余。3 3 统计冗余统计冗余统计冗余统计冗余 具有空间冗余和时间冗余具有空间冗余和时间冗余具有空间冗余和时间冗余具有空间冗余和时间冗余4 4 结构冗余结构冗余结构冗余结构冗余 规则纹理、相互重叠的结构表面规则纹理、相互重叠的结构表面规则纹理、相互重叠的结构表面规则纹理、相互重叠的结构表面例如布纹图像和草
11、席图像，方格状的地板图案等例如布纹图像和草席图像，方格状的地板图案等例如布纹图像和草席图像，方格状的地板图案等例如布纹图像和草席图像，方格状的地板图案等5 5 信息熵冗余信息熵冗余信息熵冗余信息熵冗余 消息是其出现概率的单调下降函数，消息是其出现概率的单调下降函数，即消息出现的可能性（概率）越小，信即消息出现的可能性（概率）越小，信息量也就越大。息量也就越大。例：一个例：一个256以内的数，它的信息量以内的数，它的信息量log2256=8bit=1Byte设从设从N个任选一个数个任选一个数x的概率为的概率为p(x)=1/N，则信息量则信息量 I(x)=log2N=-log21/N=-log2
12、p(x)熵：信息源所有可能事件的信息量的平均熵：信息源所有可能事件的信息量的平均值。值。若有信源若有信源X=xi|I=1,2,N，xi的概率为的概率为p(xi)，则，则X的熵为的熵为例：从例：从256个数中选定一个数的熵为：个数中选定一个数的熵为：编码时，给各消息分配的位数编码时，给各消息分配的位数编码时，给各消息分配的位数编码时，给各消息分配的位数bibi，则数据量，则数据量，则数据量，则数据量D=pD=pi i*b*bi i ,而而而而b bi i=-log=-log2 2p pi i由于由于由于由于P Pi i值预先很难估算，所以取值预先很难估算，所以取值预先很难估算，所以取值预先很难估
13、算，所以取 b bi i=aver(b=aver(bj j|j=1,2,N)|j=1,2,N)例：对于信息例：对于信息例：对于信息例：对于信息“AAABCABD”AAABCABD”有有有有p pA A=1/2 p=1/2 pB B=1/4 p=1/4 pC C=1/8 p=1/8 pD D=1/8=1/8则信息熵应为则信息熵应为则信息熵应为则信息熵应为H=-1/2logH=-1/2log2 21/2-1/4log1/2-1/4log2 21/4-1/4-1/8log1/8log2 21/8-1/8log1/8-1/8log2 21/8=1/2+1/2+3/8+3/8=7/41/8=1/2+1/
14、2+3/8+3/8=7/4也即用平均也即用平均也即用平均也即用平均7/47/4位来表示一个码元时无冗余，所以位来表示一个码元时无冗余，所以位来表示一个码元时无冗余，所以位来表示一个码元时无冗余，所以当编码结果为当编码结果为当编码结果为当编码结果为 A A：00 B:01 C:10 D:1100 B:01 C:10 D:11时，就产生了冗余。时，就产生了冗余。时，就产生了冗余。时，就产生了冗余。6 6 视觉冗余视觉冗余视觉冗余视觉冗余 视觉、听觉敏感度和非线性感觉视觉、听觉敏感度和非线性感觉视觉、听觉敏感度和非线性感觉视觉、听觉敏感度和非线性感觉2 22424色色色色2 28 8色色色色7 7
15、知识冗余知识冗余知识冗余知识冗余 凭借经验识别凭借经验识别凭借经验识别凭借经验识别有许多图像的理解与某些基础知识有相当大的相关性，这有许多图像的理解与某些基础知识有相当大的相关性，这有许多图像的理解与某些基础知识有相当大的相关性，这有许多图像的理解与某些基础知识有相当大的相关性，这类规律性的结构可由先验知识和背景知识得到类规律性的结构可由先验知识和背景知识得到类规律性的结构可由先验知识和背景知识得到类规律性的结构可由先验知识和背景知识得到8 8 其他冗余其他冗余其他冗余其他冗余 上述上述上述上述7 7种以外的冗余种以外的冗余种以外的冗余种以外的冗余声音频率声音频率声音频率声音频率文字组句文字组
16、句文字组句文字组句色彩渐变色彩渐变色彩渐变色彩渐变主观意识主观意识主观意识主观意识:6.2.16.2.16.2 6.2 数据压缩算法数据压缩算法数据压缩算法数据压缩算法数据压缩算法分类数据压缩算法分类数据压缩算法分类数据压缩算法分类 无损压缩编码无损压缩编码无损压缩编码无损压缩编码 压缩数据还原后，与原始数据一致，无损失压缩数据还原后，与原始数据一致，无损失压缩数据还原后，与原始数据一致，无损失压缩数据还原后，与原始数据一致，无损失无损压缩编码无损压缩编码无损压缩编码无损压缩编码(可逆编码可逆编码可逆编码可逆编码)霍夫曼编码霍夫曼编码霍夫曼编码霍夫曼编码行行行行 程程程程 编编编编 码码码码算
17、算算算 术术术术 编编编编 码码码码 有损压缩编码有损压缩编码有损压缩编码有损压缩编码 压缩后再还原的数据有损失压缩后再还原的数据有损失压缩后再还原的数据有损失压缩后再还原的数据有损失有损压缩编码有损压缩编码有损压缩编码有损压缩编码(不可逆编码不可逆编码不可逆编码不可逆编码)全频带编码全频带编码全频带编码全频带编码PCM/ADPCMPCM/ADPCM混混混混 合合合合 编编编编 码码码码JPEG/MPEGJPEG/MPEG压缩技术的基本方式：压缩技术的基本方式：压缩技术的基本方式：压缩技术的基本方式：v对称压缩：压缩算法和解压缩算法是一样的。对称压缩：压缩算法和解压缩算法是一样的。对称压缩：压
18、缩算法和解压缩算法是一样的。对称压缩：压缩算法和解压缩算法是一样的。优点：压与解压速度相同。优点：压与解压速度相同。优点：压与解压速度相同。优点：压与解压速度相同。适用于：实时系统，例如视频会议。适用于：实时系统，例如视频会议。适用于：实时系统，例如视频会议。适用于：实时系统，例如视频会议。v不对称压缩：压缩和解压缩速率不同。例如不对称压缩：压缩和解压缩速率不同。例如不对称压缩：压缩和解压缩速率不同。例如不对称压缩：压缩和解压缩速率不同。例如VCD VCD VCD VCD 的的的的制作与播放。制作与播放。制作与播放。制作与播放。影响数据压缩的要素：影响数据压缩的要素：压缩比：压缩比：压缩比：压
19、缩比：(压缩前后文件大小之比，越高越好，但受速度、压缩前后文件大小之比，越高越好，但受速度、压缩前后文件大小之比，越高越好，但受速度、压缩前后文件大小之比，越高越好，但受速度、消耗资源等的影响消耗资源等的影响消耗资源等的影响消耗资源等的影响)图像质量图像质量图像质量图像质量：(还原后与原图像相比，评估的方法有客观评估还原后与原图像相比，评估的方法有客观评估还原后与原图像相比，评估的方法有客观评估还原后与原图像相比，评估的方法有客观评估 和主观评估）和主观评估）和主观评估）和主观评估）压缩与解压缩速度压缩与解压缩速度压缩与解压缩速度压缩与解压缩速度：(与压缩方法和压缩编码的算法有关，一般压与压缩
20、方法和压缩编码的算法有关，一般压与压缩方法和压缩编码的算法有关，一般压与压缩方法和压缩编码的算法有关，一般压 缩比解压缩计算量大，因而压缩比解压缩慢）缩比解压缩计算量大，因而压缩比解压缩慢）缩比解压缩计算量大，因而压缩比解压缩慢）缩比解压缩计算量大，因而压缩比解压缩慢）执行的硬件与软件执行的硬件与软件执行的硬件与软件执行的硬件与软件：（压缩实现需要硬件和软件，硬件速度快，（压缩实现需要硬件和软件，硬件速度快，（压缩实现需要硬件和软件，硬件速度快，（压缩实现需要硬件和软件，硬件速度快，但复杂的算法需要软件的支持）但复杂的算法需要软件的支持）但复杂的算法需要软件的支持）但复杂的算法需要软件的支持）
21、图像压缩编码分类：图像压缩编码分类：预测编码预测编码变换编码变换编码统计编码统计编码其他编码其他编码差分脉冲调制编码（DPCM）自适应差分脉冲调制编码（ADPCM）帧间预测编码离散余弦变换（DCT）K-L变换小波变换哈夫曼编码游程长度编码算术编码LZW编码矢量量化编码子带编码分形编码6.2.2 预测编码预测编码原理原理 根据离散信号之间存在着一定的相关性的根据离散信号之间存在着一定的相关性的特点，利用图像像素的以往样本值（前面一特点，利用图像像素的以往样本值（前面一个或几个点的数据）对于新样本值（下一个个或几个点的数据）对于新样本值（下一个点的数据）进行预测，然后将样本的实际值点的数据）进行预
22、测，然后将样本的实际值与其预测值相减得到一个误差值与其预测值相减得到一个误差值(较小较小)，这样，这样可以用比较少的数码进行编码得到较大的数可以用比较少的数码进行编码得到较大的数据压缩结果，达到压缩数据的目的。据压缩结果，达到压缩数据的目的。利用以往的样本值对新样本值进行预测利用以往的样本值对新样本值进行预测利用以往的样本值对新样本值进行预测利用以往的样本值对新样本值进行预测将新样本值的实际值与其预测值相减，得到误差值将新样本值的实际值与其预测值相减，得到误差值将新样本值的实际值与其预测值相减，得到误差值将新样本值的实际值与其预测值相减，得到误差值对该误差值进行编码，传送此编码即可对该误差值进
23、行编码，传送此编码即可对该误差值进行编码，传送此编码即可对该误差值进行编码，传送此编码即可理论上数据源可以准确地用一个数学模型表示，使其理论上数据源可以准确地用一个数学模型表示，使其理论上数据源可以准确地用一个数学模型表示，使其理论上数据源可以准确地用一个数学模型表示，使其输出数据总是与模型的输出一致，因此可以准确地预输出数据总是与模型的输出一致，因此可以准确地预输出数据总是与模型的输出一致，因此可以准确地预输出数据总是与模型的输出一致，因此可以准确地预测数据，但是实际上预测器不可能找到如此完美的数测数据，但是实际上预测器不可能找到如此完美的数测数据，但是实际上预测器不可能找到如此完美的数测数
24、据，但是实际上预测器不可能找到如此完美的数学模型学模型学模型学模型典型方法典型方法DPCMDPCM：差分脉冲调制预测，：差分脉冲调制预测，：差分脉冲调制预测，：差分脉冲调制预测，Differential Pulse Code Differential Pulse Code ModulationModulationADPCMADPCM：自适应差分脉冲调制预测，：自适应差分脉冲调制预测，：自适应差分脉冲调制预测，：自适应差分脉冲调制预测，Adaptive Adaptive Differential Pulse Code ModulationDifferential Pulse Code Modul
25、ation差分脉冲调制（DPCM）预测原理图量化器量化器量化器量化器预测器预测器预测器预测器译码器译码器译码器译码器预测器预测器预测器预测器编码器编码器编码器编码器发送端发送端发送端发送端接收端接收端接收端接收端X Xn nd dn nX Xn nX Xn n d dn n d dn n X Xn nX Xn n 差分脉冲调制（DPCM）预测是降低每个像素所需平均比特数的最是降低每个像素所需平均比特数的最常常使使用的方法用的方法说明说明发送端预测器带有存储器，把发送端预测器带有存储器，把发送端预测器带有存储器，把发送端预测器带有存储器，把t tn n时刻以前的采时刻以前的采时刻以前的采时刻以前
26、的采样值样值样值样值x x1 1,x,x2 2,x,x3 3,x,xn-1n-1存储起来并据此对存储起来并据此对存储起来并据此对存储起来并据此对x xn n进行预测，进行预测，进行预测，进行预测，得到预测值得到预测值得到预测值得到预测值d dn n为为为为x xn n与与与与 的差值，的差值，的差值，的差值，d dn n 为为为为d dn n经量化器量化的值经量化器量化的值经量化器量化的值经量化器量化的值x xn n 是接收端的输出信号是接收端的输出信号是接收端的输出信号是接收端的输出信号误差误差误差误差q qn n为为为为q qn n=x=xn n-x-xn n=x=xn n-(+d-(+d
27、n n)=(x)=(xn n-)-d-)-dn n=d=dn n-d-dn n 实际上就是发送端的量化器对误差量化的误差实际上就是发送端的量化器对误差量化的误差实际上就是发送端的量化器对误差量化的误差实际上就是发送端的量化器对误差量化的误差对对对对 d dn n 的量化越粗糙，压缩比越高，失真越大的量化越粗糙，压缩比越高，失真越大的量化越粗糙，压缩比越高，失真越大的量化越粗糙，压缩比越高，失真越大X Xn nX Xn nX Xn nX Xn n预测方程式 线性预测：如果ai是常数，则为时不变线性预测，否则为自适应线性预测（ADPCM）最简单的预测方程：最佳线性预测使误差函数达到最小值的预测方程
28、式叫做最佳线性预测。求最佳线性预测的各个参数ai，列方程组：代入得到联立方程组：如果为一阶线性预测，则可求得：图像信号的预测编码一幅数字图像可以看成一个空间点阵，图像信一幅数字图像可以看成一个空间点阵，图像信号不仅在水平方向是相关的，在垂直方向也是号不仅在水平方向是相关的，在垂直方向也是相关的。根据已知样值与待预测样值间的位置相关的。根据已知样值与待预测样值间的位置关系，可以分为：关系，可以分为：（1 1）一维预测（行内预测）：利用同一行上相）一维预测（行内预测）：利用同一行上相邻的样值进行预测。邻的样值进行预测。（2 2）二维预测（帧内预测）：利用同一行和前）二维预测（帧内预测）：利用同一行
29、和前面几行的数据进行预测。面几行的数据进行预测。（3 3）三维预测（帧间预测）：利用相邻几帧）三维预测（帧间预测）：利用相邻几帧（或不同波段）上的取样值进行预测（或不同波段）上的取样值进行预测静止图像的二维预测编码这种压缩算法被应用到JPEG标准的无损压缩模式之中，中等复杂程度的图像压缩比可达到2:1。cabx选择值预测值0非预测1a2b3c4a+b-c5a+(b-c)/26b+(a-c)/27(a+b)/2d三邻域预测法三邻域预测法活动图像的帧间预测编码视频信号的冗余度主要体现在空间相关性（帧内）、时间相关性（帧间）和色度空间表示上的相关性。对于每秒25帧（30）的电视信号，其相继帧之间存在
30、极强的相关性。据统计256级灰度的黑白图像序列，帧间差值超过3的象素数不超过4。所以在活动图像序列中可以利用前面的帧来预测后面的帧，以实现数据压缩。帧间预测编码技术被广泛应用到H.261、H.263、MPEG-1和MPEG-2等视频压缩标准之中。差分脉冲调制（DPCM）预测示例例如，取一序列为10，12，14，16，18，20。（例如亮度变化缓慢的图像的亮度值）由于其中所有数字都不相同，但是是一个等差的数列，所以行程编码和哈夫曼对其不产生压缩效果。先用DPCM方法，其预测器的预测参数为 =Xn-1，则其误差值得到一个新的序列10，2，2，2，2，2。然后再使用行程编码方法对这个新序列进行压缩，
31、压缩结果为10(5,2)。X Xn n差分脉冲调制（DPCM）预测输入数据为平稳的随机过程输入数据为平稳的随机过程预测器的设计是预测编码系统的核心：预测参数预测器的设计是预测编码系统的核心：预测参数无损压缩，对预测误差的量化是造成图像质量下无损压缩，对预测误差的量化是造成图像质量下降的主要原因降的主要原因自适应差分脉冲调制（自适应差分脉冲调制（自适应差分脉冲调制（自适应差分脉冲调制（ADPCMADPCM）预测）预测）预测）预测uu输入数据不是平稳的随机过程输入数据不是平稳的随机过程输入数据不是平稳的随机过程输入数据不是平稳的随机过程uu自适应预测自适应预测自适应预测自适应预测uu定期重新调整预
32、测器的预测参数，使预测器随输入数定期重新调整预测器的预测参数，使预测器随输入数定期重新调整预测器的预测参数，使预测器随输入数定期重新调整预测器的预测参数，使预测器随输入数据的变化而变化据的变化而变化据的变化而变化据的变化而变化uu自适应改变量化器的量化阶数，用小量化阶量化小差自适应改变量化器的量化阶数，用小量化阶量化小差自适应改变量化器的量化阶数，用小量化阶量化小差自适应改变量化器的量化阶数，用小量化阶量化小差值，大量化阶量化大差值值，大量化阶量化大差值值，大量化阶量化大差值值，大量化阶量化大差值uu分为线性自适应预测与非线性自适应预测两种分为线性自适应预测与非线性自适应预测两种分为线性自适应
33、预测与非线性自适应预测两种分为线性自适应预测与非线性自适应预测两种6.2.3 变换编码变换编码 从一种信号（空间）变换到另一种信从一种信号（空间）变换到另一种信号（空间）使信号的某些特征更加明显，号（空间）使信号的某些特征更加明显，再编码，变换域里容易压缩，变换后的信再编码，变换域里容易压缩，变换后的信号值更独立和有序。号值更独立和有序。将信号从时域转换为频域。将信号从时域转换为频域。如：将直角坐标系转变为极坐标系。如：将直角坐标系转变为极坐标系。原理原理原理原理 为达到目的，可以通过不同的路径为达到目的，可以通过不同的路径为达到目的，可以通过不同的路径为达到目的，可以通过不同的路径殊途同归殊
34、途同归殊途同归殊途同归 例如：数学计算机中，经常利用某些数学函数略加转例如：数学计算机中，经常利用某些数学函数略加转例如：数学计算机中，经常利用某些数学函数略加转例如：数学计算机中，经常利用某些数学函数略加转换可以找出一条计算的捷径。换可以找出一条计算的捷径。换可以找出一条计算的捷径。换可以找出一条计算的捷径。乘法：乘法：乘法：乘法：1000000*1000001000000*100000100000000000100000000000运算时，数据很大，可以变成对数进行加法运算时，数据很大，可以变成对数进行加法运算时，数据很大，可以变成对数进行加法运算时，数据很大，可以变成对数进行加法1000
35、000 X 1000001000000 X 100000100000000000100000000000取对数取对数取对数取对数lg10lg106 6取对数取对数取对数取对数lg10lg105 5取指数取指数取指数取指数101011116 65 5 1111算法算法算法算法变换变换变换变换X1X2出现相近幅值的可能性很大，即取值出现相近幅值的可能性很大，即取值点都落入了图中的虚线圈中，如将坐标系点都落入了图中的虚线圈中，如将坐标系旋转旋转45。,为为Y1Y2系，可以看出相关性减小，系，可以看出相关性减小，量化位数，可以进行压缩。量化位数，可以进行压缩。0 0X X1 1X X2 2相邻采样值相
36、邻采样值相邻采样值相邻采样值x x1 1,x,x2 2各用各用各用各用3bit3bit编码，有编码，有编码，有编码，有6464种合成种合成种合成种合成可能，变换后，可能，变换后，可能，变换后，可能，变换后，Y Y1 1,Y,Y2 2合成种类减少合成种类减少合成种类减少合成种类减少Y Y1 1Y Y2 2变换编码原理框图变换变换变换变换量化量化量化量化译码器译码器译码器译码器逆变换逆变换逆变换逆变换编码器编码器编码器编码器发送端发送端发送端发送端接收端接收端接收端接收端G GA AAAGGUU输入输入输入输入U U输出输出输出输出U U为变换矩阵，为变换矩阵，为变换矩阵，为变换矩阵，A,A:A,
37、A:变换系数变换系数变换系数变换系数U:UU:U的逆变换的逆变换的逆变换的逆变换最佳正交变换K-L变换X1X2Y1Y2对相关向量求协方差矩阵，按照特征值的大小排列特征向量。变换域中能量集中到少数几个变换系数上（特征值大的特征向量上的系数），编码效率最高，误差最小。K-L变换图示变换图示小波（Wavelet）变换是一种具有很好局部性的时频分析方法小波基的构造具有平移（时域）和伸缩（频域）特性多分辨率特性，对低频信息的持续分解（Mallat塔式分解）简单的一维哈尔（小波）变换分辨率平均值细节系数89 7 3 5 6 4 3 148 4 5 21-1 1 126 3.52 1.514.751.25离
38、散余弦变换(DCT,Discrete Cosine Transform)准最佳变换，利用三角函数进行的一种变换DCT的基向量由余弦函数构成一维DCT变换和二维DCT变换,变换后输出DCT变换系数，将幅度变成频率广泛应用于图像与视频压缩中，如JPG,MPEG变换编码最新应用JPEG2000 静态图像压缩标准DWT(离散小波变换)MPEG-4 基于内容的音视频编码标准DCT（离散余弦变换）H.264(MPEG4 Part10)整数变换6.2.4 统计编码统计编码(信息熵编码信息熵编码)1.游程长度编码RLE（Run Length Encoding）由于一幅图像中有许多颜色相同的图块，用一整数对存储
39、一个像素的颜色值及相同颜色像素的数目（长度）。例如：（G,L）长度颜色值编码时采用从左到右，从上到下的排列，每当遇到一串相同数据时就用该数据及重复次数代替原来的数据串。000000003333333333222222222226666666111111111111111111111111555555555555888888888888888888555555555555553333222222222222222222(0,8)(3,10)(2,11)(6,7)(1,18)(1,6)(5,12)(8,18)(5,14)(3,4)(2,18)18*7的像素颜色仅用的像素颜色仅用11对数据对数据游程
40、长度编码特点：直观，经济；直观，经济；是一种无损压缩；是一种无损压缩；压缩比取决于图像本身特点，相同颜色图像块越压缩比取决于图像本身特点，相同颜色图像块越大，图像块数目越少，压缩比越高。大，图像块数目越少，压缩比越高。适用于计算机生成的图像，例如。适用于计算机生成的图像，例如。BMPBMP、TIFTIF等，等，不适于颜色丰富的自然图像。不适于颜色丰富的自然图像。但当颜色值出现极端的情况下，即每个相邻像素但当颜色值出现极端的情况下，即每个相邻像素但当颜色值出现极端的情况下，即每个相邻像素但当颜色值出现极端的情况下，即每个相邻像素的颜色值均不相同，则用此方法后，反而会产生的颜色值均不相同，则用此方
41、法后，反而会产生的颜色值均不相同，则用此方法后，反而会产生的颜色值均不相同，则用此方法后，反而会产生长度增加一倍的病态数据（此时应采用标志位的长度增加一倍的病态数据（此时应采用标志位的长度增加一倍的病态数据（此时应采用标志位的长度增加一倍的病态数据（此时应采用标志位的方法来区分实际像素和连续像素）。方法来区分实际像素和连续像素）。方法来区分实际像素和连续像素）。方法来区分实际像素和连续像素）。改进例如：RTTTTTTTTABBCDG被转换为：R#8TABBCDG，其中“”作为转义字符，表明其后所跟的字符表示长度。行程编码多用于黑白二值图像的压缩中。例如000000001111111111110
42、00001111111被转化为一系列黑串和白串长度的编码：8,12,5,7。因为串长度并非等概率分布，所以一般要配合以统计编码（Huffman编码）。2.哈夫曼编码最佳编码定理最佳编码定理 哈夫曼哈夫曼19521952年提出年提出 内容：在变字长编码中，对于出现概率大的信息符号内容：在变字长编码中，对于出现概率大的信息符号编以短字长的码，对于概率小的符号编以长字长的码。编以短字长的码，对于概率小的符号编以长字长的码。如果码字长度严格按所对应符号出现概率大小逆序排如果码字长度严格按所对应符号出现概率大小逆序排列，则平均码字长度一定小于其他以任何符号顺序排列，则平均码字长度一定小于其他以任何符号顺
43、序排列方式得到的平均码字长度。列方式得到的平均码字长度。哈夫曼编码方法哈夫曼编码方法 根据以上定理而得到的一种编码方法根据以上定理而得到的一种编码方法 步骤步骤 1.1.将符号按出现概率由大到小排列，给最后两个符号赋予一将符号按出现概率由大到小排列，给最后两个符号赋予一个二进制码，概率大的赋个二进制码，概率大的赋1 1，小的赋，小的赋0 0（反之亦可）（反之亦可）2.2.把最后两个符号的概率合成一个概率，重复上一步把最后两个符号的概率合成一个概率，重复上一步 3.3.重复步骤重复步骤2 2，直到最后只剩下两个概率为止，直到最后只剩下两个概率为止 4.4.将每个符号所对应的分支的将每个符号所对应
44、的分支的0,10,1反序排出即可反序排出即可哈夫曼编码方法过程演示A1A1A2A2A3A3A4A4A5A5A6A6A7A70.230.230.210.210.180.180.150.150.130.130.070.070.030.03符号符号符号符号 概率概率概率概率 1 1 0 00.100.101 1 0 00.230.23 1 1 0 00.330.33 1 1 0 00.440.44 1 1 0 00.560.560 0 1 11 1编码编码编码编码 01 01 00 00 111 111 110 110 101 1011001100110001000可以看出，概率大的符号其编码短，概
45、率小的符号其可以看出，概率大的符号其编码短，概率小的符号其可以看出，概率大的符号其编码短，概率小的符号其可以看出，概率大的符号其编码短，概率小的符号其编码长，符号使用其编码来表示，达到数据压缩目的编码长，符号使用其编码来表示，达到数据压缩目的编码长，符号使用其编码来表示，达到数据压缩目的编码长，符号使用其编码来表示，达到数据压缩目的哈夫曼编码结果分析码字的平均长度_ 7N=niP(ai)=2.72bit i=1信息符号的熵值 7H(a)=-P(ai)log2P(ai)=2.61bit i=1可见，哈夫曼编码结果，其平均长度接近于信息符号的熵值，但是仍有冗余编码编码编码编码 01 01 00 0
46、0 111 111 110 110 101 1011001100110001000码长码长码长码长 2 2 2 2 3 3 3 3 3 3 4 4 4 4例如例如：信源有四个符号：X a1 a2 a3 a4 1/2 1/4 1/8 1/8信息熵：H(x)=-1/2log2(1/2)-1/4log2(1/4)-(1/8log2(1/8)2=1.75 bit/字符采用哈夫曼编码（二进制编码）a1 a2 a3 a4 0 10 110 111平均码长：L=(1/2)1+(1/4)2+(1/8)6=1.75 bit/字符编码效率：=1.75/1.75=100%a a1 1 a a2 2 a a3 3 a
47、 a4 4 1/21/21/41/41/81/81/81/8符号符号符号符号 概率概率概率概率 0 0 1 11/41/40 0 1 11/21/20 0 1 11 1编码编码编码编码 0 0 10 10 110 110 111 111 4个符号 采用PCM编码：R=log24=2 bit a1 a2 a3 a4 00 01 10 11 L=2 Pi=2 编码效率：=H(x)/L=1.75/2=87.5%哈夫曼编码的特点其实就是数据结构中的二叉树形式无歧义性，能正确地恢复原信号构造出来的码不唯一有两种赋值方式：概率大的赋1，小的赋0，反之亦可两符号概率相等时，其排列顺序随机，造成编码不唯一编码
48、出来的字长不统一，硬件实现困难对不同的信号源，编码效率不同，等概率信源，效率最低编码后形成一个哈夫曼编码表，若正确解码必须有此码表，于是在传送过程中也要传送此码表需两次扫描、译码时间较长、不能实现随机存取。需两次扫描、译码时间较长、不能实现随机存取。需两次扫描、译码时间较长、不能实现随机存取。需两次扫描、译码时间较长、不能实现随机存取。3.3.算术编码算术编码算术编码算术编码将信息表示成实数轴上将信息表示成实数轴上将信息表示成实数轴上将信息表示成实数轴上0 0和和和和1 1之间的间隔，信息越长，之间的间隔，信息越长，之间的间隔，信息越长，之间的间隔，信息越长，编码的间隔越小，表示这一间隔所需的
49、二进制位也编码的间隔越小，表示这一间隔所需的二进制位也编码的间隔越小，表示这一间隔所需的二进制位也编码的间隔越小，表示这一间隔所需的二进制位也就越多。就越多。就越多。就越多。用一个浮点数值代替一个符号序列。用一个浮点数值代替一个符号序列。用一个浮点数值代替一个符号序列。用一个浮点数值代替一个符号序列。当符号概率接近时，效率高于当符号概率接近时，效率高于当符号概率接近时，效率高于当符号概率接近时，效率高于HuffmanHuffman。例：例：例：例：字符：字符：字符：字符：a b c d a b c d 概率：概率：概率：概率：0.1 0.4 0.2 0.30.1 0.4 0.2 0.3范围：范
50、围：范围：范围：00，0.10.1）0.10.1，0.50.5）0.50.5，0.70.7）0.70.7，1 1）bc算法：算法：算法：算法：设设设设High=1,Low=0High=1,Low=0：00，1 1）,每个字符的间隔为每个字符的间隔为每个字符的间隔为每个字符的间隔为LiLi，Hi)Hi)第第第第i i个字符：个字符：个字符：个字符：Low=Low+(High-Low)*Li;Low=Low+(High-Low)*Li;High=Low+(High-Low)*Hi;High=Low+(High-Low)*Hi;Low=Low;High=High;Low=Low;High=High;