第3章多媒体信息编码精选文档.ppt

《第3章多媒体信息编码精选文档.ppt》由会员分享，可在线阅读，更多相关《第3章多媒体信息编码精选文档.ppt（128页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第3章多媒体信息编码1 1本讲稿第一页，共一百二十八页第3章 多媒体信息编码 3.1 引言引言 3.23.2无损数据压缩无损数据压缩无损数据压缩无损数据压缩3.3 3.3 有损压缩编码有损压缩编码2 2本讲稿第二页，共一百二十八页一、什么是数据压缩数据压缩就是在一定的精度损失条件下，以最少的数码表示信源所发出的信号.数据压缩处理一般由两个过程组成:一是编码过程,即对原始数据进行编码压缩,以便存储和传输;二是解码过程,即对压缩的数据进行解压,恢复成可用的数据。信源编码信道编码信道信道译码信源译码信源信宿3.1 引言引言3 3本讲稿第三页，共一百二十八页压缩/解压的过程EncoderDecoder

2、InputMessageOutputMessageCompressedMessageaaaaaaaaaaaaaaaaaaaa20aaaaaaaaaaaaaaaaaaaaaCODEC4 4本讲稿第四页，共一百二十八页二、多媒体数据压缩编码的必要性 压缩编码的必要性和重要性压缩编码的必要性和重要性1.1.多媒体系统技术多媒体系统技术多媒体系统技术多媒体系统技术:面向三维图形、立体声、彩色全屏幕运动画面的面向三维图形、立体声、彩色全屏幕运动画面的面向三维图形、立体声、彩色全屏幕运动画面的面向三维图形、立体声、彩色全屏幕运动画面的处理技术；处理技术；处理技术；处理技术；多种媒体承载的由模拟量转化成数字

3、量信息的获取、表示、多种媒体承载的由模拟量转化成数字量信息的获取、表示、多种媒体承载的由模拟量转化成数字量信息的获取、表示、多种媒体承载的由模拟量转化成数字量信息的获取、表示、存储、传输、表现。存储、传输、表现。存储、传输、表现。存储、传输、表现。2.2.未压缩的数字化信息量未压缩的数字化信息量未压缩的数字化信息量未压缩的数字化信息量 1 1页页页页B5B5文件数据量约为文件数据量约为文件数据量约为文件数据量约为6.61MB/P6.61MB/P180255mm180255mm2 212122 2像素像素像素像素/mm/mm2 28bit1B/8bit=6.61MB/P8bit1B/8bit=6

4、.61MB/P650MB650MB的的的的CDROMCDROM存放存放存放存放98Pages98Pages5 5本讲稿第五页，共一百二十八页二、多媒体数据压缩编码的必要性 CD-ACD-A激光唱盘每秒采样位为激光唱盘每秒采样位为激光唱盘每秒采样位为激光唱盘每秒采样位为1.41Mbps1.41Mbps44kHz16bit/Hz44kHz16bit/Hz 样本样本样本样本2(2(声道声道声道声道)1.41Mbps1.41Mbps650MB650MB的的的的CDROMCDROM存放存放存放存放1 1小时音乐小时音乐小时音乐小时音乐 数字音频磁带数字音频磁带数字音频磁带数字音频磁带(DAT)(DAT)

5、每秒采样位为每秒采样位为每秒采样位为每秒采样位为768kbps768kbps48kHz16bit/Hz48kHz16bit/Hz 样本样本样本样本=768kbps=768kbps650MB650MB的的的的CDROMCDROM存放存放存放存放2 2小时节目小时节目小时节目小时节目 数字电视图像数字电视图像数字电视图像数字电视图像 SIF(Source input format)SIF(Source input format)格式、格式、格式、格式、NFSCNFSC制、彩色、制、彩色、制、彩色、制、彩色、4:4:44:4:4采样采样采样采样每帧每帧每帧每帧:3522403B=253KB:3522

6、403B=253KB每秒每秒每秒每秒:253KB30=7.603MBps:253KB30=7.603MBps每片每片每片每片CDROM:650MB253kB=2569CDROM:650MB253kB=2569帧帧帧帧/片片片片 (650MB7.603MB)60=1.42(650MB7.603MB)60=1.42分分分分/片片片片6 6本讲稿第六页，共一百二十八页二、多媒体数据压缩编码的必要性2.2.未压缩的数字化信息量未压缩的数字化信息量未压缩的数字化信息量未压缩的数字化信息量 数字电视图像数字电视图像数字电视图像数字电视图像 ICCR(International Consultative C

7、ommittee for ICCR(International Consultative Committee for Radio)Radio)格式、格式、格式、格式、PALPAL制、制、制、制、4:4:44:4:4采样采样采样采样每帧每帧每帧每帧:7205763B=1.24MB:7205763B=1.24MB每秒每秒每秒每秒:1.24MB25=31.1MBps:1.24MB25=31.1MBps每片每片每片每片CDROM:650MB1.24MB=524CDROM:650MB1.24MB=524帧帧帧帧/片片片片 650MB31.1MB=20.9650MB31.1MB=20.9秒秒秒秒/片片片片

8、 陆地卫星陆地卫星陆地卫星陆地卫星(LandSat-3)(LandSat-3)分辨率分辨率分辨率分辨率2340324023403240、4 4波段、波段、波段、波段、7 7位采样精度位采样精度位采样精度位采样精度每幅每幅每幅每幅:2340324074=212Mb:2340324074=212Mb每天每天每天每天:212Mb30=6.36Gbit:212Mb30=6.36Gbit每年每年每年每年:6.36Gbit365=2321.4Gbit=290GB:6.36Gbit365=2321.4Gbit=290GB7 7本讲稿第七页，共一百二十八页三、多媒体数据压缩的可能性 多媒体数据压缩的可能性（1

9、 1）图像数据表示中大量冗余）图像数据表示中大量冗余（2 2）图像数据压缩技术）图像数据压缩技术:利用图像数据冗余性减少数据量方法利用图像数据冗余性减少数据量方法1.1.空间冗余空间冗余空间冗余空间冗余 静态图像存在的主要冗余静态图像存在的主要冗余静态图像存在的主要冗余静态图像存在的主要冗余;采样点颜色之间的空间连贯性采样点颜色之间的空间连贯性采样点颜色之间的空间连贯性采样点颜色之间的空间连贯性:区域中各点光强、色彩、饱和度同区域中各点光强、色彩、饱和度同区域中各点光强、色彩、饱和度同区域中各点光强、色彩、饱和度同;离散像素采样表示颜色没有利用这种空间连贯性离散像素采样表示颜色没有利用这种空间

10、连贯性离散像素采样表示颜色没有利用这种空间连贯性离散像素采样表示颜色没有利用这种空间连贯性;改变颜色的像素存储方式改变颜色的像素存储方式改变颜色的像素存储方式改变颜色的像素存储方式,利用空间连贯性利用空间连贯性利用空间连贯性利用空间连贯性,减少数据量减少数据量减少数据量减少数据量.8 8本讲稿第八页，共一百二十八页图图BitmapBitmap颜色相同的块颜色相同的块帧内压缩帧内压缩帧内压缩帧内压缩例如，在静态图像中有一块表面颜色均匀的区域，在此区域中例如，在静态图像中有一块表面颜色均匀的区域，在此区域中所有点的光强和色彩以及饱和度都是相同的，因此数据有很大所有点的光强和色彩以及饱和度都是相同的

11、，因此数据有很大的的空间冗余空间冗余。9 9本讲稿第九页，共一百二十八页2.2.时间冗余时间冗余时间冗余时间冗余序列图像序列图像(电视、运动图像电视、运动图像电视、运动图像电视、运动图像)表示常包含的冗余表示常包含的冗余;相邻帧记录了相邻时刻的同一场景画面相邻帧记录了相邻时刻的同一场景画面,移动物位移动物位置稍不同置稍不同.运动图像一般为位于一时间轴区间的一组连续画运动图像一般为位于一时间轴区间的一组连续画面，其中的相邻帧往往包含相同的背景和移动物体，面，其中的相邻帧往往包含相同的背景和移动物体，只不过移动物体所在的空间位置略有不同，所以后一只不过移动物体所在的空间位置略有不同，所以后一帧的数

12、据与前一帧的数据有许多共同的地方，这种共帧的数据与前一帧的数据有许多共同的地方，这种共同性是由于相邻帧记录了相邻时刻的同一场景画面，同性是由于相邻帧记录了相邻时刻的同一场景画面，所以称为所以称为时间冗余。时间冗余。同理，语音数据中也存在着时间冗余。同理，语音数据中也存在着时间冗余。1010本讲稿第十页，共一百二十八页时间冗余时间冗余1111本讲稿第十一页，共一百二十八页3.视觉冗余视觉冗余人类的视觉系统由于受生理特性的限制，对于图像场的注意人类的视觉系统由于受生理特性的限制，对于图像场的注意人类的视觉系统由于受生理特性的限制，对于图像场的注意人类的视觉系统由于受生理特性的限制，对于图像场的注意

13、是非均匀的，人对细微的颜色差异感觉不明显。是非均匀的，人对细微的颜色差异感觉不明显。是非均匀的，人对细微的颜色差异感觉不明显。是非均匀的，人对细微的颜色差异感觉不明显。例如，人类视觉的一般分辨能力为例如，人类视觉的一般分辨能力为例如，人类视觉的一般分辨能力为例如，人类视觉的一般分辨能力为2626灰度等级，而一般的图像的量灰度等级，而一般的图像的量灰度等级，而一般的图像的量灰度等级，而一般的图像的量化采用的是化采用的是化采用的是化采用的是2828灰度等级，即存在视觉冗余。灰度等级，即存在视觉冗余。灰度等级，即存在视觉冗余。灰度等级，即存在视觉冗余。人类的听觉对某些信号反映不太敏感，使得压缩后再还

14、原有允人类的听觉对某些信号反映不太敏感，使得压缩后再还原有允人类的听觉对某些信号反映不太敏感，使得压缩后再还原有允人类的听觉对某些信号反映不太敏感，使得压缩后再还原有允许范围的变化，人也感觉不出来。许范围的变化，人也感觉不出来。许范围的变化，人也感觉不出来。许范围的变化，人也感觉不出来。(1).(1).人类视觉系统对图像场的敏感性是非均匀的和非线性的人类视觉系统对图像场的敏感性是非均匀的和非线性的人类视觉系统对图像场的敏感性是非均匀的和非线性的人类视觉系统对图像场的敏感性是非均匀的和非线性的;(2).(2).记录图像时假定视觉系统是均匀和线性的记录图像时假定视觉系统是均匀和线性的记录图像时假定

15、视觉系统是均匀和线性的记录图像时假定视觉系统是均匀和线性的,对不同敏感区同样对待对不同敏感区同样对待对不同敏感区同样对待对不同敏感区同样对待,产生了视觉产生了视觉产生了视觉产生了视觉冗余冗余冗余冗余.应对不同敏感部分分开编码应对不同敏感部分分开编码应对不同敏感部分分开编码应对不同敏感部分分开编码;1212本讲稿第十二页，共一百二十八页(3).(3).视觉的非均匀性视觉的非均匀性视觉的非均匀性视觉的非均匀性.视觉系统对图像的亮度和色彩度的敏感性相差很大，视觉系统对图像的亮度和色彩度的敏感性相差很大，视觉系统对图像的亮度和色彩度的敏感性相差很大，视觉系统对图像的亮度和色彩度的敏感性相差很大，RGB

16、NTSCRGBNTSC的的的的YIQYIQ后发现后发现后发现后发现,视觉系统的亮度视觉系统的亮度视觉系统的亮度视觉系统的亮度y y的敏感度远高于色度的敏感度远高于色度的敏感度远高于色度的敏感度远高于色度(I,Q)(I,Q)的敏感度的敏感度的敏感度的敏感度可对可对可对可对IQIQ允允允允许误差大于许误差大于许误差大于许误差大于y y的允许误差的允许误差的允许误差的允许误差;亮度增加时亮度增加时亮度增加时亮度增加时,视觉系统对量化误差的敏感度降低视觉系统对量化误差的敏感度降低视觉系统对量化误差的敏感度降低视觉系统对量化误差的敏感度降低,人眼辨别能力与物体周围的人眼辨别能力与物体周围的人眼辨别能力与

17、物体周围的人眼辨别能力与物体周围的背景亮度成反比背景亮度成反比背景亮度成反比背景亮度成反比.在高亮度区在高亮度区在高亮度区在高亮度区,灰度值的量化可粗糙一些灰度值的量化可粗糙一些灰度值的量化可粗糙一些灰度值的量化可粗糙一些;人眼的视觉系统能把图像的边缘和非边缘区域分开处理人眼的视觉系统能把图像的边缘和非边缘区域分开处理人眼的视觉系统能把图像的边缘和非边缘区域分开处理人眼的视觉系统能把图像的边缘和非边缘区域分开处理边缘区和非边缘边缘区和非边缘边缘区和非边缘边缘区和非边缘区分别编码的依据区分别编码的依据区分别编码的依据区分别编码的依据;人眼的视觉系统是把视网膜上的图像分解成若干个空间有向的视频通道

18、后再进行人眼的视觉系统是把视网膜上的图像分解成若干个空间有向的视频通道后再进行人眼的视觉系统是把视网膜上的图像分解成若干个空间有向的视频通道后再进行人眼的视觉系统是把视网膜上的图像分解成若干个空间有向的视频通道后再进行处理处理处理处理编码时把图像分解成符合这一规律编码时把图像分解成符合这一规律编码时把图像分解成符合这一规律编码时把图像分解成符合这一规律(视觉内在特性视觉内在特性视觉内在特性视觉内在特性)的频率通道的频率通道的频率通道的频率通道,可获大的可获大的可获大的可获大的压缩比压缩比压缩比压缩比;小波编码的特性小波编码的特性小波编码的特性小波编码的特性.1313本讲稿第十三页，共一百二十八

19、页4.4.结构冗余结构冗余结构冗余结构冗余图像纹理区的像素值存在着分布模式图像纹理区的像素值存在着分布模式图像纹理区的像素值存在着分布模式图像纹理区的像素值存在着分布模式:如方格状地板图案如方格状地板图案如方格状地板图案如方格状地板图案;已知分布模式已知分布模式已知分布模式已知分布模式,可通过某一过程生成图像可通过某一过程生成图像可通过某一过程生成图像可通过某一过程生成图像.5.5.知识冗余知识冗余 有些图像的理解与某些知识有相当大的相关性有些图像的理解与某些知识有相当大的相关性有些图像的理解与某些知识有相当大的相关性有些图像的理解与某些知识有相当大的相关性,如人脸的图像有固定结构如人脸的图像

20、有固定结构如人脸的图像有固定结构如人脸的图像有固定结构;规律性结构可由先验知识和背景知识获得规律性结构可由先验知识和背景知识获得规律性结构可由先验知识和背景知识获得规律性结构可由先验知识和背景知识获得知识冗余知识冗余知识冗余知识冗余;由已有知识由已有知识由已有知识由已有知识,对图像中物体构造其基本模型对图像中物体构造其基本模型对图像中物体构造其基本模型对图像中物体构造其基本模型,创建对应各种特征的图像库创建对应各种特征的图像库创建对应各种特征的图像库创建对应各种特征的图像库:存存存存储时只需保存图像的一些特征参数储时只需保存图像的一些特征参数储时只需保存图像的一些特征参数储时只需保存图像的一些

21、特征参数;知识冗余是模型编码主要利用的特征知识冗余是模型编码主要利用的特征知识冗余是模型编码主要利用的特征知识冗余是模型编码主要利用的特征.6.6.图像区域的相同性冗余图像区域的相同性冗余图像中多个区域所对应的像素值相同或者相近图像中多个区域所对应的像素值相同或者相近图像中多个区域所对应的像素值相同或者相近图像中多个区域所对应的像素值相同或者相近,产生重复产生重复产生重复产生重复性存储性存储性存储性存储;向量量化向量量化向量量化向量量化(Vector quantization)(Vector quantization)是针对这种冗余的压缩是针对这种冗余的压缩是针对这种冗余的压缩是针对这种冗余的

22、压缩编码方法编码方法编码方法编码方法.1414本讲稿第十四页，共一百二十八页时间域压缩迅速传输媒体信源频率域压缩并行开通更多业务空间域压缩降低存储费用能量域压缩降低发射功率四、数据压缩的好处多媒体数据压缩的必要性 数据存储 传输带宽1515本讲稿第十五页，共一百二十八页五、压缩编码算法的性能评价指标数据压缩编码算法的评估指标包括：1.压缩比2.保真度保真度3.算法复杂性4.时延时延一个好的算法还要考虑：多媒体系统的软、硬件适应能力。应用环境应用环境技术标准1616本讲稿第十六页，共一百二十八页压缩编码算法的性能评价指标压缩比：压缩比压缩前数据量/压缩后数据量压缩后数据量理论上讲，在保证压缩后图

23、像质量的前提下，压缩比越高越好。保真性：保真是一个对压缩质量进行评价的参数，分为主观保保真是一个对压缩质量进行评价的参数，分为主观保真度和客观保真度。真度和客观保真度。客观保真度用重建信号质量与原信号之间的均方误差来客观保真度用重建信号质量与原信号之间的均方误差来衡量：衡量：xi i和和和和xi i分别对应原信号和重建信号，分别对应原信号和重建信号，分别对应原信号和重建信号，分别对应原信号和重建信号，N N2 2为总信息数量。为总信息数量。为总信息数量。为总信息数量。1717本讲稿第十七页，共一百二十八页压缩编码算法的性能评价指标保真性：客观保真性：将均方误差作为由数据压缩而产生的噪声客观保真

24、性：将均方误差作为由数据压缩而产生的噪声能量，定义压缩信噪比为能量，定义压缩信噪比为主观保真性：在规定的观测条件（图像尺寸、对比度、主观保真性：在规定的观测条件（图像尺寸、对比度、主观保真性：在规定的观测条件（图像尺寸、对比度、主观保真性：在规定的观测条件（图像尺寸、对比度、亮度、观测距离等）下，对一组标准图像压缩前后的质亮度、观测距离等）下，对一组标准图像压缩前后的质亮度、观测距离等）下，对一组标准图像压缩前后的质亮度、观测距离等）下，对一组标准图像压缩前后的质量进行对比的主观评定标准。具体做法是对重建信号的量进行对比的主观评定标准。具体做法是对重建信号的量进行对比的主观评定标准。具体做法是

25、对重建信号的量进行对比的主观评定标准。具体做法是对重建信号的特性进行按等级评分，然后根据下式计算平均分特性进行按等级评分，然后根据下式计算平均分特性进行按等级评分，然后根据下式计算平均分特性进行按等级评分，然后根据下式计算平均分MOSMOS：其中，其中，其中，其中，k为级别数，为级别数，为级别数，为级别数，n ni i为该类别的人数，为该类别的人数，为该类别的人数，为该类别的人数，c ci i为分数。为分数。为分数。为分数。1818本讲稿第十八页，共一百二十八页六、压缩分类（1）1、按照压缩方法是否产生失真分类(1)无失真压缩 无失真压缩要求解压以后的数据和原始数据完全一致。解压后得到的数据是

26、原数据的复制，是一种可逆压缩。无失真压缩法去掉或减少数据中的冗余，恢复时再重新插到数据中，因此是可逆过程根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/21/4。一些常用的无损压缩算法有赫夫曼(Huffman)算法和LZW(Lenpel-Ziv&Welch)压缩算法1919本讲稿第十九页，共一百二十八页(2)有失真压缩 解解压压以以后后的的数数据据和和原原始始数数据据不不完完全全一一致致，是不可逆压缩方式。有失真压缩还原后，不影响信息的表达。是不可逆压缩方式。有失真压缩还原后，不影响信息的表达。例如，图像、视频、音频数据的压缩就可以采用有损压缩方法，例如，图像、视频、音

27、频数据的压缩就可以采用有损压缩方法，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。图像、视频、音频数据意思产生误解，但可大大提高压缩比。图像、视频、音频数据的压缩比可高达的压缩比可高达100:1，但人的主观感受仍不会对原始信息产生，但人的主观感受仍不会对原始信息产生误解。误解。2020本讲稿第二十页，共一百二十八页多媒体信息编码技术主要侧重于有损压缩编码的研究。经过多年的研究与开发,已经出台了

28、一系列有关的国际标准。其中,最著名的是国际标准组织（ISO）制定的JPEG和MPEG。JPEG是静止图像的压缩标准,其压缩比可达401。MPEG（MPEG-1、MPEG-2及MPEG-4）是动态图像的压缩标准,采用MPEG-2标准对NTSC质量视频进行压缩后,网络带宽需求可降低到3.36Mb/s。其它的标准还有国际电信联合会（ITU）制定的用于可视电话、会议电视的H.261和H.263;用于音频的G.711、G.721、G.728等。2121本讲稿第二十一页，共一百二十八页六、压缩分类（2）根据码词长度是否相等分类定长码（fixed-length code）采用相同的位数（采用相同的位数（bi

29、tbit）对对数据数据进进行行编码编码大多数存大多数存储储数字信息的数字信息的编码编码系系统统都采用定都采用定长码长码变长码（variable-length code）采用不相同的位数（采用不相同的位数（bitbit）对对数据数据进进行行编码编码，以，以节节省省存存储储空空间间示例：示例：赫夫曼赫夫曼编码编码2222本讲稿第二十二页，共一百二十八页六、压缩分类（3）按照压缩方法的原理分类按照压缩方法的原理分类预测编码：预测编码：基本思想是利用已被编码的点的数据值，预测邻近的基本思想是利用已被编码的点的数据值，预测邻近的一个像素点的数据值一个像素点的数据值变换编码变换编码:基本思想是将图像的光强

30、矩阵变换到系数空间上，然基本思想是将图像的光强矩阵变换到系数空间上，然后对系数进行编码压缩后对系数进行编码压缩统计编码：统计编码：根据信息出现概率的分布特性而进行的压缩编码根据信息出现概率的分布特性而进行的压缩编码*无失真编码无失真编码*分析合成编码：分析合成编码：基元和特征参数基元和特征参数混合编码：混合编码：混合压缩是利用了各种单一压缩的长处，以求在压缩混合压缩是利用了各种单一压缩的长处，以求在压缩比、压缩效率及保真度之间取得最佳折衷比、压缩效率及保真度之间取得最佳折衷2323本讲稿第二十三页，共一百二十八页多媒体数据压缩编码方法PCM固 定自适应自适应预测编码固 定DPCMMADPCM运

31、动补偿变换编码傅立叶(DFT)离散余弦(DIT)离散正弦(DST)沃尔什-哈达马哈 尔斜变换卡胡南-苏夫(KL)小波变换子带编码统计编码(熵编码)(无损)哈夫曼算术编码费 诺香 农游程(RLC)LZW静图像编码方块逐渐浮现逐层内插位平面抖动电视图像编码帧内预测帧间编码运动估计运动补偿条件补充内 插帧间预测基于重要性矢量量化滤 波子 采 样模型编码分形编码混合编码H.261JPEGMPEG图3-1 多媒体数据压缩编码方法2424本讲稿第二十四页，共一百二十八页3.2无损数据压缩无损数据压缩数据压缩的理论基础为数据压缩的理论基础为ShannonShannon信息论。它一方面给出了数据压缩的理论极限

32、，另一方面又指明了数据压缩的技术途径。香农香农-范诺范诺 霍夫曼编码霍夫曼编码 算术编码算术编码 RLERLE编码编码 词典编码词典编码统计编码统计编码统计编码统计编码2525本讲稿第二十五页，共一百二十八页3.2.1信息熵及基本概念 1信息量与信息熵 信息量信息量 式中，P(xj)是信源X发出xj的概率。I(xj)的含义是，信源X发出xj这个消息（随机事件）后，接收端收到信息量的量度。2626本讲稿第二十六页，共一百二十八页l信源信源X的的“熵熵”：信源X发出的xj（j=1,2,n）共n个随机事件的自信息统计平均，即 等概率事件的熵最大：当P(x1)1时，P(x2)P(x3)P(xj)0，此

33、时熵为由上可得熵的范围为：2727本讲稿第二十七页，共一百二十八页平均码长与熵如果信源X输出为一个随机变量序列aj j，对aj j的编码长度为Lj j，则X的平均码长为：对信源编码的最小平均码长为该信源的熵，为：P Pj j 表示符号表示符号 aj j 在在X X中出现的概率中出现的概率2828本讲稿第二十八页，共一百二十八页在编码中用熵值来衡量是否为最佳编码。若以在编码中用熵值来衡量是否为最佳编码。若以LcLc表示编表示编码器输出码字的平均码长，则当码器输出码字的平均码长，则当LcH(X)LcH(X)有冗余，不是最佳。有冗余，不是最佳。LcLcH(X)H(X)不可能。不可能。LcLcH(X)

34、H(X)最佳编码（最佳编码（LcLc稍大于稍大于H(X)H(X)）。）。熵值为平均码长熵值为平均码长Lc的下限。的下限。平均码长Lc的计算公式为：（j=1,2,n）其中：P(xj)是信源X发出xj的概率，L(xj)为xj的编码长。2929本讲稿第二十九页，共一百二十八页Entropy Example【例1】【例2】一幅用256级灰度表示的图像，如果每一个象素点灰度的概率均为Pi=1/256，编码每一个象素点就需要8位。3030本讲稿第三十页，共一百二十八页【例例3 3】有一幅有一幅40个象素组成的灰度图像，灰度共有5级，4040个象素中出现灰度个象素中出现灰度A A、B、C C、D D、E E

35、的象素数如的象素数如表所示。如果用表所示。如果用3 3个位表示个位表示5个等级的灰度值，也就是个等级的灰度值，也就是每个象素用每个象素用3 3位表示，编码这幅图像总共需要位表示，编码这幅图像总共需要120120位。位。H H(S S)=(15/40)log)=(15/40)log2 2(40/15)+(7/40)log2 2(40/7)+(5/40)log2 2(40/5)=2.196，每每个个符符号号用用2.1962.196位表示，位表示，4040个象素需用个象素需用87.8487.84位。位。符符 号号b bA AB BC CD DE E出现次数出现次数15157 77 76 65 531

36、31本讲稿第三十一页，共一百二十八页2冗余度、编码效率与压缩比冗余度、编码效率与压缩比 设原图像的平均码长为L L，熵熵为为H(X)，压压缩缩后后图图像像的的平平均码长为均码长为Lc，则定义冗余度为，则定义冗余度为：编码效率：编码效率：压缩比：压缩比：在数字图像通信系统中，冗余度、编码效率与压缩比是衡量信源特性以及编解码设备性能的重要指标。3232本讲稿第三十二页，共一百二十八页统计编码的基本思想：其宗旨在于找到一种编码使得平均码长到达熵极限，其宗旨在于找到一种编码使得平均码长到达熵极限，基本思想就是基本思想就是对于无记忆的信源，根据码字出现的概率分布特性寻找概率与码字长度间的最优化匹配。对出

37、现概率较大的符号取较短的码长，而对出现概率对出现概率较大的符号取较短的码长，而对出现概率较小的符号取较大的码长较小的符号取较大的码长，据此对信息进行压缩，据此对信息进行压缩。3.2.2统计编码(信息熵编码)信息熵编码也称为统计编码，是利用信息源出现的概率来进行编码，常见的信息熵编码包括哈夫曼编码、香农-范范诺编码诺编码、行程、行程编码编码和算和算术统计编码术统计编码等。等。3333本讲稿第三十三页，共一百二十八页统计编码统计编码是一种无损编码，常用于图像、文档等要求无损失的压缩中。实现原理：有些媒体（如图像，文档）数据中各样点值的出现概率在编码前可以统计出，结合其出现概率进行的编码可以充分降低

38、数据量，同时又保证了媒体的质量。由于在编码过程中仅仅将这些媒体数据看成是一串数据，没有深入到其物理意义中去研究，所以压缩比率并不高。3434本讲稿第三十四页，共一百二十八页1、仙农-范诺(Shannon-Fano)编码最早阐述和实现这种编码的是Shannon(1948年)和Fano(1949年)，采用从上到下的方法进行编码。按照符号出现的频度或概率排序使用递归方法分成两个部分，每一部分具有近似相同的次数，0分在上，1分在下3535本讲稿第三十五页，共一百二十八页例子1例如，A，B，C，D和E符号符号出现的次数出现的次数(P(Pi i)loglog2 2(1/P(1/Pi i)分配的代码分配的代

39、码需要的位数需要的位数A A15(0.375)15(0.375)1.41501.415000003030B B7(0.175)7(0.175)2.51452.514501011414C C7(0.175)7(0.175)2.51452.514510101414D D6(0.150)6(0.150)2.73692.73691101101818E E5(0.125)5(0.125)3.00003.00001111111515ABCDE00111103636本讲稿第三十六页，共一百二十八页例子2SymbolCountCodeA1500B701D5110C610E5111Firstdivision2n

40、ddivision3rddivision4thdivision3737本讲稿第三十七页，共一百二十八页符号符号频率频率信息量信息量总信息量总信息量A151.3820.68B72.4817.35C62.7016.20D62.7016.20E52.9614.82编码编码码长码长BitBit数数002300121410212110318111315Total85.25bitsTotal89bits3838本讲稿第三十八页，共一百二十八页2.霍夫曼编码基本思想：对于出现概率较大的符号取较短的码长，而对概对于出现概率较大的符号取较短的码长，而对概率较小的符号则取较长的码长。率较小的符号则取较长的码长。霍

41、夫曼编码（Huffman Encoding）又称变长度编码，或最优编码，即遵照霍夫曼编码原则的结果一定是平均码长最短。霍夫曼编码的特点：只适用于有限个离散信源；且实现起来相当复杂。3939本讲稿第三十九页，共一百二十八页具体的编码步骤如下：（1 1）将信源符号出现的概率按由大到小的顺序排序。）将信源符号出现的概率按由大到小的顺序排序。）将信源符号出现的概率按由大到小的顺序排序。）将信源符号出现的概率按由大到小的顺序排序。（2 2）将两处最小的概率进行组合相加，形成一个新的概率。）将两处最小的概率进行组合相加，形成一个新的概率。）将两处最小的概率进行组合相加，形成一个新的概率。）将两处最小的概率

42、进行组合相加，形成一个新的概率。（3 3）将新出现的概率与未编码的字符一起重新排序。）将新出现的概率与未编码的字符一起重新排序。）将新出现的概率与未编码的字符一起重新排序。）将新出现的概率与未编码的字符一起重新排序。（4 4）重复步骤（）重复步骤（）重复步骤（）重复步骤（2 2）、（）、（）、（）、（3 3），直到出现的概率和为），直到出现的概率和为），直到出现的概率和为），直到出现的概率和为1 1。（5 5）分配代码。代码分配从最后一步开始反向进行，对最后两个概率）分配代码。代码分配从最后一步开始反向进行，对最后两个概率）分配代码。代码分配从最后一步开始反向进行，对最后两个概率）分配代码。代

43、码分配从最后一步开始反向进行，对最后两个概率一个赋予一个赋予一个赋予一个赋予0 0代码，一个赋予代码，一个赋予代码，一个赋予代码，一个赋予1 1代码。如此反向进行到开始的概率排列。代码。如此反向进行到开始的概率排列。代码。如此反向进行到开始的概率排列。代码。如此反向进行到开始的概率排列。在此过程中，若概率不变则采用原代码。在此过程中，若概率不变则采用原代码。在此过程中，若概率不变则采用原代码。在此过程中，若概率不变则采用原代码。4040本讲稿第四十页，共一百二十八页例例4 4：设输入图像的灰度级a1,a2,a3,a4,a5,a6a1,a2,a3,a4,a5,a6出现出现的概率分别是的概率分别是

44、0.40.4、0.20.2、0.120.12、0.150.15、0.10.1、0.030.03。试。试进行哈夫曼编码，并计算编码效率、压缩比、冗余度。进行哈夫曼编码，并计算编码效率、压缩比、冗余度。编码步骤：编码步骤：（1 1）初始化，根据符号概率的大小按由大到小顺序对符号）初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如图进行排序，如图4-24-2所示。所示。（2 2）把概率小的两个符号组成一个节点，如图）把概率小的两个符号组成一个节点，如图4-24-2中的中的a5a5、a6a6组成节点组成节点P1P1。（3 3）重复步骤）重复步骤2 2，得到节点，得到节点P2P2、P3P3、P4

45、P4、P5P5，形成一棵，形成一棵“树树”，其中，其中P5P5为根节点。为根节点。（4 4）从根节点）从根节点P5P5开始到相应于每个符号的开始到相应于每个符号的“树叶树叶”，从，从上到下标上上到下标上1 1（上枝）或者（上枝）或者0 0（下枝），至于哪个为（下枝），至于哪个为1 1哪个为哪个为0 0则无关紧要，最后的结果仅仅是分配的代码不同，而代码的则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。平均长度是相同的。最终编码结果为：最终编码结果为：a1=1,a2=000,a1=1,a2=000,a3=011,a3=011,a4=001,a5=0100,a4=001,a5=

46、0100,a6=0101a6=0101 4141本讲稿第四十一页，共一百二十八页由公式（由公式（4-6）可求得图像信源熵是：H(X)=H(X)=-=-（0.4 loglog20.4+0.2 loglog2 20.2+0.12 log2 20.12+0.12+0.150.15 loglog2 20.15+0.1loglog20.1+0.03 loglog20.03）=2.25 bit=2.25 bit 根据哈夫曼编码过程图给出的结果，可求出它的平均码字长度：Lc=0.41+0.23+0.153+0.123+0.14+0.034=2.33编码效率为：压缩之前8个符号需要3个比特量化，经过压缩之后的

47、平均码字长度为2.33，其压缩比为：冗余度为：r=1-=3.4%4242本讲稿第四十二页，共一百二十八页Huffman Coding的问题错错误误传传播播(error(errorpropagation)propagation)：霍夫曼码没有错误保护功能。在译码时，如果码串中没有错误，就能一个接一个地正确译出代码。但如果码串中发生错误，不但这个码本身译错，更糟糕的是一错一大串。霍霍夫夫曼曼码码是是可可变变长长度度码码，因因此此很很难难随随意意查查找找或或调调用用压压缩缩文文件件中中间间的的内内容容，然然后后再再译译码码，这这就就需需要要在在存存储储代代码码之之前前加加以以考考虑虑(必必须须在在存

48、存储储代代码码前前先先进进行行译译码码)。尽尽管管如如此此，霍霍夫夫曼曼码码还还是是得到广泛应用。得到广泛应用。由于一个节点的上下两个分支即可以赋值“0 0”，也也可可以以赋赋值值“1 1”，因因此此同同一一信信源源对对应应的的霍霍夫夫曼曼编编码码并并不不唯唯一一，但但平均码长是相同的。平均码长是相同的。4343本讲稿第四十三页，共一百二十八页霍夫曼编码霍夫曼编码为唯一可译码，即码的任意一串有限长的码符号霍夫曼编码为唯一可译码，即码的任意一串有限长的码符号序列只能被唯一译成所对应的信源符号。序列只能被唯一译成所对应的信源符号。霍夫曼对不同的信源，其编码效率是不同的。当信源概霍夫曼对不同的信源，

49、其编码效率是不同的。当信源概率分布很不均匀时，霍夫曼码会具有显著效果。率分布很不均匀时，霍夫曼码会具有显著效果。如果信源的实际概率模型与构码时所假设的概率模型有差如果信源的实际概率模型与构码时所假设的概率模型有差异，实际的平均码字将大于预期值，编码效率将下降。这异，实际的平均码字将大于预期值，编码效率将下降。这种情况下，唯一的解决办法就是更换码表，使之与实际概种情况下，唯一的解决办法就是更换码表，使之与实际概率模型匹配。率模型匹配。4444本讲稿第四十四页，共一百二十八页Huffman与Shannon-Fano特点霍夫曼编码与仙农-范诺编码这两种方法都自含同步码，即在编码之后的码串中都不需要另

50、外添加标记符号，即在译码时分割符号的特殊代码。霍夫曼编码方法的编码效率比仙农-范诺编码效率高一些。Theorem:The Huffman algorithm generates an optimal prefix code.4545本讲稿第四十五页，共一百二十八页Huffman Coding ExampleCharacterX6 X3 X4 X5 X1 X7 X2Probability0.25 0.2 0.15 0.15 0.1 0.1 0.050.450.250.150.31.00.55CharX6 X3 X4 X5 X1 X7 X2Code10 11 001 011 010 0000 00