多媒体通信之编码完整PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,现代多媒体技术应用教程,罗万伯 主编,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,现代多媒体技术应用教程,罗万伯 主编,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,多媒体通信之编码,2,第,2,章,数据编码,数据压缩概述,有损编码,无损编码,赫夫曼编码,算术编码,行程长度编码,词典编码,变换编码,基于模型编码,分形编码,其他压缩编码,差错检测和校正编码,3,数据编码,数据编码包括：,信源编码,信道编码,信源编码：为了表示和,/,或压缩从信号源产生出来的信号而进行的编码，主要解决有效性问题。,信道编码：为了使处理过的信号在传输过程中不出错或少出错，以及即使出了错也能自动检错或尽量纠错而进行的编码，主要解决可靠性问题。,4,2.1,数据压缩概述,多媒体数据的压缩主要是对视频数据和音频数据的压缩，二者使用的基本技术是相同的。,为什么要压缩,数据的冗余性,压缩和解压缩过程,压缩评价和分类,数据压缩常常又称为数据信源编码，或简称为数据编码。,数据压缩的逆过程称为数据解压缩，也称为数据信源解码，或简称为数据解码。,5,2.1.1,为什么要压缩,多媒体数据压缩的目的：为了最有效地利用有限资源（例如存储和传输资源）。,一般来说，压缩是信源信号（采样和量化后数字信号），如语音、静止图像、音乐或电视等的有效的数字化表示。,压缩的任务,：,保持信源信号在一个可以接受的状况的前提下把需要的比特数减到最少程度，,以,减少存储、处理和传输的成本。,6,信源,存储量,电话,(200Hz,至,3.4kHz),8000,样本,/,秒,12,比特,/,样本,=96kbps,宽带语音,(50Hz,至,7kHz),16000,样本,/,秒,14,比特,/,样本,=224kbps,宽带音频,(20Hz,至,20kHz),44100,样本,/,秒,2,通道,16,比特,/,样本,=1.412Mbps,图像,512512,像素彩色图像,24,比特,/,像素,6.3,兆比特,/,图像,视频,640480,像素彩色图像,24,比特,/,像素,30,图像,/,秒,221Mbps,高清晰度电视,1280720,像素彩色图像,60,图像,/,秒,24,比特,/,像素,1.3Gbps,未压缩信源的大致比特率,7,2.1.2,数据的冗余性,数据压缩的前提：基本原始信源的数据存在着很大的冗余度（,Redundant,）。,空间冗余,时间冗余,信息熵冗余,结构冗余,知识冗余,认知（视觉听觉）冗余,其他冗余,数据压缩就是去掉信号数据的冗余性。,8,2.1.2,数据的冗余性,空间冗余,在同一幅图像中，规则物体和规则背景（所谓规则是指表面颜色分布是有序的而不是完全杂乱无章的）的表面物理特征具有相关性，这些相关性在数字化图像中就表现为数据冗余。,9,2.1.2,数据的冗余性,时间冗余,图像序列中的两幅相邻的图像，后一幅图像与前一幅图像之间有较大的相关性，这反映为时间冗余。同理，在言语中，由于人在说话时发音的音频是一连续的渐变过程，而不是一个完全在时间上独立的过程，因而存在时间冗余。,10,2.1.2,数据的冗余性,信息熵冗余,（编码冗余）,信息量,I(xi),的概率平均值叫做信息熵，或简称熵。,熵是信息量的度量方法，,定义了观察到单个信源符号输出时获得的平均信息量。,信息熵冗余,信息熵冗余：信源编码时，当分配给第,i,个码元类的比特数,b（y,i,）=-log,p,i,，,才能使编码后单位数据量等于其信源熵，即达到其压缩极限。但实际中各码元类的先验概率很难预知，比特分配不能达到最佳。实际单位数据量,dH（S），,即存在信息冗余熵。,信息论认为：若信源编码的熵大于信源的实际熵，该信源中一定存在冗余度。,11,12,2.1.2,数据的冗余性,结构冗余,有些图像从大的区域上看存在着非常强的纹理结构，例如布纹图像和草席图像，我们说它们在结构上存在冗余。,知识冗余,有许多图像的理解与某些基础知识有相当大的相关性。这类规律性的结构可由先验知识和背景知识得到，我们称此类冗余为知识冗余。,13,2.1.2,数据的冗余性,认知（视觉听觉）冗余,人类视觉系统对于图像场的任何变化，并不是都能感知的。,事实上人类视觉系统一般的分辨能力约为,2,6,灰度等级，而一般图像量化采用,2,8,灰度等级，这类冗余我们称为视觉冗余。,对于听觉，也存在类似的冗余。,其他冗余,例如由图像的空间非定常特性所带来的冗余。,14,2.1.3,压缩和解压缩过程,数据压缩就是去掉信号数据的冗余性。数据压缩常常又称为数据信源编码，或简称为数据编码。,与此对应，数据压缩的逆过程称为数据解压缩，也称为数据信源解码，或简称为数据解码。,15,2.1.3,压缩和解压缩过程,数据压缩的典型操作包括预准备、处理、量化和编码等过程。,16,2.1.3,压缩和解压缩过程,解压缩是压缩的逆过程,具体的编码器和解码器以不同的方法构成,在对称应用中,(,如对话应用,),，编码和解码代价应基本相同,在非对称应用中，解码过程比编码过程耗费的代价要小，这种技术用于以下情形,：,压缩的过程仅一次，采样的时间不限,；,解压缩经常用到并需要迅速完成。,17,2.1.4,压缩评价和分类,衡量数据压缩技术的三个重要指标：,压缩比,：,要大。,恢复效果,：,要好，要尽可能地恢复原始数据。,压缩算法,：,要简单，压缩、解压速度快，尽可能地做到实时压缩、解压。,18,2.1.4,压缩评价和分类,影响多媒体数据压缩技术发展的因素,:,技术的使用目的,面向存储的技术,：要求实时，非常看重压缩能力,面向传输的技术,：编解码算法实现的实时性和成本却是非常敏感的问题。,压缩算法的压缩能力、实现复杂性与成本等方面进行平衡与折中,数据模型,数据模型的选择和参数优化对于压缩算法的进步也十分关键,19,压缩分类（,1,）,根据压缩过程中是否减少了熵，目前常用的压缩编码方法可以分为两大类：,无损压缩编码（,Lossless compression coding,）,压缩是可逆的，也称为无失真压缩,、冗余压缩或熵编码,一般用于文本、数据以及应用软件的压缩,压缩比较低,，,如,LZ,编码、行程长度编码、赫夫曼编码的压缩比一般在,2:1,至,5:1,之间,有损压缩编码（,Loss compression coding,）,压缩是,不,可逆的,，也称为熵压缩法,允许一定程度的失真，,压缩比,高,20,常用压缩编码方法分类,有损压缩与无损压缩,21,冗余压缩法：,熵压缩法：,22,压缩分类（,2,）,根据码词长度是否相等,分类,定长码（,fixed-length code,）,采用相同的位数（,bit,）对数据进行编码,大多数存储数字信息的编码系统都采用定长码,变长码（,variable-length code,）,采用不相同的位数（,bit,）对数据进行编码，以节省存储空间,示例：,赫夫曼编码,23,2.2,赫夫曼编码,赫夫曼（,Huffman,）在,1952,年提出的一种编码方法,从下到上的编码方法，属于变长码类。,赫夫曼编码可区别的不同码字的生成是基于不同符号出现的不同概率。,自含同步码，在编码之后的码串中都不需要另外添加标记符号，即在译码时切分符号的特殊代码。,基于一种称为,“,编码树,”,（,coding tree,）的技术。,得到广泛应用,24,赫夫曼编码算法步骤,（,1,）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。,（,2,）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。,（,3,）重复第,2,步，直到形成一个符号为止（树），其概率最后等于,1,。,（,4,）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为,1,，上分枝赋值为,0,。,25,赫夫曼编码例,编码结果,：,w,(,A,)=100,w,(,B,)=0,w,(,C,)=111,w,(,D,)=101,w,(,E,)=110,p(C)=0.09,p(E)=0.11,p(D)=0.13,p(A)=0.16,p(B)=0.51,p(CE)=0.20,p(AD)=0.29,p(ADCE)=0.49,p(ADCEB)=1.00,1,0,0,1,0,1,0,1,信道编码：为了使处理过的信号在传输过程中不出错或少出错，以及即使出了错也能自动检错或尽量纠错而进行的编码，主要解决可靠性问题。,52)的第1个1/10,（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。,数据压缩就是去掉信号数据的冗余性。,第一类词典法：查找正在压缩的字符序列是否在前面的输入数据中出现过，如果是，则用指向早期出现过的字符串的“指针”替代重复的字符串。,A A B C D B C D A B C D,在同一幅图像中，规则物体和规则背景（所谓规则是指表面颜色分布是有序的而不是完全杂乱无章的）的表面物理特征具有相关性，这些相关性在数字化图像中就表现为数据冗余。,面向传输的技术：编解码算法实现的实时性和成本却是非常敏感的问题。,p(ADCEB)=1.,LZ77是一种普遍的无损压缩方法。,信息量I(xi)的概率平均值叫做信息熵，或简称熵。,使用LZ77编码效率略高于使用定长二元码,如果变换后的协方差矩阵接近对角矩阵，该类变换称为准最佳变换，典型的有DCT（离散余弦变换）、DFT（离散傅立叶变换）、DWT（离散小波变换）等。,马华东多媒体技术原理及应用北京：清华大学出版社2002年8月,傅立叶变换(Fourier Transform)的物理意义：将信号从时间域（time domain）变换到频率域（frequency domain）。,向量量化是一种限失真编码，其原理仍可用信息论中的率失真函数理论来分析。,算法必须设计成解压程序能够在编码和原始数据序列推导出当前的映射。,正变换：给定由N个信号样本（均匀间隔）x(0),x(1),x(N-1)组成的信号序列，离散傅立叶变换（DFT，Discrete Fourier Transform）：,26,改进的,赫夫曼,编码算法,自适应赫夫曼编码（,Adaptive Huffman code,）,根据符号概率的变化动态地改变码字，产生的代码比原始赫夫曼编码更有效,扩展的赫夫曼编码（,Extended Huffman code,）,允许编码符号组而不是单个符号,52)的第7个1/10,经过分带编码、译码后合成的输出音频信号会有混迭效应。,有些图像从大的区域上看存在着非常强的纹理结构，例如布纹图像和草席图像，我们说它们在结构上存在冗余。,其音质不如非压缩的 G.,影响多媒体数据压缩技术发展的因素:,经过小波变换后的图像能量很集中，便于对不同的分量作不同的处理，达到较高的压缩比。,u,v =0,1,2,N-1,然而人的视觉系统对彩色色度的感觉和亮度的敏感性是不同的，因此产生了不同的彩色空间表示。,根据压缩过程中是否减少了熵，目前常用的压缩编码方法可以分为两大类：,正变换：给定由N个信号样本（均匀间隔）x(0),x(1),x(N-1)组成的信号序列，离散傅立叶变换（DFT，Discrete Fourier Transform）：,小波变换是一个线性变换，能够将一个信号分解成对空间和时间、频率的独立贡献，同时又不失原信号所包含的信息。,根据码词长度是否相等分类,27,采用赫夫曼编码时的问题,采用赫夫曼编码时有两个问题值得注意：,差错传播,(error propagation),：赫夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，那怕仅仅是,1,位出现错误，也会引起一连串的错误。,赫夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。,28,2.3,算术编码,基本原理：将编码的消息表示成实数,0,和,1,之间的一个间隔（,Interval,），消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。,两个基本的参数：符号的概率和它的编码间隔。,算术编码过程举例,符号,A,B,C,D,概率,0.1,0.4,0.2,0.3,初始编码间隔,0,，,0.1,）,0.1,，,0.5,）,0.5,，,0.7),0.7,，,1),信源符号、概率和初始编码间隔,30,编码过程,步骤,输入符号,编码间隔,编码判决,1,C,0.5,，,0.7),符号的间隔范围,0.5,，,0.7),2,A,0.5,，,0.52),0.5,，,0.7),间隔的第一个,1/10,3,D,0.514,，,0.52),0.5,，,0.52),间隔的最后,3,个,1/10,4,A,0.514,，,0.5146),0.514,，,0.52),间隔的第一个,1/10,5,C,0.5143,，,0.51442),0.514,，,0.5146),间隔的第五个,1/10,开始，二个,1/10,6,D,0.514384,，,0.51442),0.5143,，,0.51442),间隔的最后,3,个,1/10,7,B,0.5143836,，,0.514402),0.514384,，,0.51442),间隔的,4,个,1/10,，从第,1,个,1/10,开始,8,从,0.5143876,，,0.514402,中选择一个数作为输出：,0.5143876,31,译码过程,步骤,间隔,译码符号,译码判决,1,0.5,，,0.7),C,0.51439,在间隔,0.5,，,0.7),2,0.5,，,0.52),A,0.51439,在间隔,0.5,，,0.7),的第,1,个,1/10,3,0.514,，,0.52),D,0.51439,在间隔,0.5,，,0.52),的第,7,个,1/10,4,0.514,，,0.5146),A,0.51439,在间隔,0.514,，,0.52),的第,1,个,1/10,5,0.5143,，,0.51442),C,0.51439,在间隔,0.514,，,0.5146),的第,5,个,1/10,6,0.514384,，,0.51442),D,0.51439,在间隔,0.5143,，,0.51442),的第,7,个,1/10,7,0.51439,，,0.5143948),B,0.51439,在间隔,0.51439,，,0.5143948),的第,1,个,1/10,8,译码出来的消息：,C A D A C D B,32,算术编码需要注意的问题,需要注意的问题：,溢出：由于实际的计算机的精度不可能无限长，运算中容易出现溢出。但多数机器都有,16,、,32,或者,64,位的精度，因此这个问题可使用比例缩放方法解决。,算术编码器对整个消息只产生一个码字，这个码字是在间隔,0,，,1),中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。,对错误很敏感：如果有一位发生错误就会导致整个消息译错。,33,2.4,行程长度编码,行程长度编码（,RLE,，,Run-length encoding,）：非常简单,基于简单的编码数据原则：重复的数据值序列（或称为,“,流,”,）用一个重复次数和单个数据值来代替。这里，重复的值称为一个,“,顺串,”,或,“,连续,”,（,run,）。,控制符,重复次数,被重复字符,三字节码字格式,示例：,RTAAAASDEEEEE,经,RLE,压缩后为：,RT*4ASD*5E,34,RLE,算法,应用,RLE,算法是,BMP,、,PCX,、,TIFF,等图像压缩技术的一部分，在,PDF,文件格式中也得到应用。,存在着不同的实现技术和文件格式,。,零抑制：,文本里的空白（,space,）字符,压缩,CompuServe,格式,：,1,比特图像的压缩,MS Windows,的格式,：,用于,4,比特和,8,比特彩色图像,PDF,和,TIFF,等,35,2.5,词典编码,词典编码分类,LZ77,算法,LZSS,算法,LZ78,算法,LZW,算法,36,2.5.1,词典编码分类,词典编码的根据：数据本身包含有重复代码序列。,属于通用编码技术,和,无损压缩技术,词典编码法分类,第一类词典法：查找正在压缩的字符序列是否在前面的输入数据中出现过，如果是，则用指向早期出现过的字符串的,“,指针,”,替代重复的字符串。,第二类算法：从输入的数据中创建一个,“,短语词典,(dictionary of the phrases),”,。编码数据过程中当遇到已经在词典中出现的,“,短语,”,时，编码器就输出这个词典中的短语的,“,索引号,”,，而不是短语本身。,37,第一类词典法编码概念,基本思想：查找正在压缩的字符序列是否在前面的输入数据中出现过，如果是，则用指向早期出现过的字符串的,“,指针,”,替代重复的字符串。,“,词典,”,是隐含的，指用以前处理过的数据。,以,Abraham Lempel,和,Jakob Ziv,在,1977,年开发和发表的算法（称为,LZ77,算法）为基础,。,改进算法是由,Storer,和,Szymanski,在,1982,年开发的，称为,LZSS,算法,。,38,第二类词典法编码概念,基本思想：从输入的数据中创建一个,“,短语词典,(dictionary of the phrases),”,。,编码数据过程中当遇到已经在词典中出现的,“,短语,”,时，编码器就输出这个词典中的短语的,“,索引号,”,，而不是短语本身。,A.Lempel,和,J.Ziv,在,1978,年首次发表了介绍这种编码方法的文章，称为,LZ78,。,Terry A.Welch,在,1984,年,改进了这种,算法,。,称为,LZW(Lempel-Ziv Walch),压缩编码。,39,2.5.2 LZ77,算法,起源：,1977,年，,Jacob Ziv,和,Abraham Lempel,描述了一种基于滑动窗口缓存的技术，该缓存用于保存最近刚处理的文本（,J.Ziv and A.Lempel,“,A Universal Algorithm for Sequential Data Compression,”,IEEE Transaction on Information Theory,May 1977,）。这个算法一般称为,IZ77,。,基本思想：在正文流中词汇和短语,(GIF,中的图像模式,),很可能会出现重复。当出现一个重复时，重复的序列可以用一个短的编码来代替。压缩程序扫描这样的重复，同时生成编码来代替重复序列。随着时间的过去，编码可以重用来捕获新的序列。算法必须设计成解压程序能够在编码和原始数据序列推导出当前的映射。,LZ77算法,40,LZ77,是一种普遍的无损压缩方法。,ZIP,就是运用这种方法。,举例，比如要传输一串字符,如果使用定长二元码,A A B C D B C D A B C D,00 00 01 10 11 01 10 11 00 01 10 11,这种编码效率低下，因为,-,忽略了字符的模式,-,忽略了字符的频率,LZ77算法思想,41,如果我们可以尝试用一段较短的代码来代替重复的模式（字符串）,代码告诉解码器应该从历史数据中的何处开始读取多少位数据，编码者使用一个缓冲器来保存数据，并尝试在历史信息中匹配信息。,如果没有匹配的，则输出该字符,如果有匹配，则按照（位置，长度）的形式输出。,LZ77算法思想,42,需要注意的问题,-,每一次输入的数据都要在历史缓冲器搜索。,-,使用最长的匹配。,则刚才的字符串,AABCDBCDABCD,就变成,AABCD(3,3)(2,4),LZ77算法思想,43,如果使用定长二元码编码需要,12*2=24bit,如果使用,LZ77,来进行编码，对字符仍然需要,2bit,，对,3bit,表示数字则需要,5*2+4*3=22bit,使用,LZ77,编码效率略高于使用定长二元码,思考,LZ77,是否对于所有的多媒体信号都适用？,44,2.6,变换编码,变换的基本原理,离散傅立叶变换,离散余弦变换,小波变换,45,2.6.1,变换的基本原理,变换编码：先对信号进行某种函数变换，从一种信号（空间）变换到另一种（空间），然后再对信号进行编码。,变换编码系统中压缩数据有变换、变换域采样和量化三个步骤。,变换本身并不进行数据压缩，它只把信号映射到另一个域，使信号在变换域里容易进行压缩，变换后的样值更独立和有序。量化操作通过比特分配可以有效地压缩数据。,46,变换编码、解码原理框图,47,2.6.1,变换的基本原理,当经过正交变换后的协方差矩阵为一对角矩阵，且具有最小均方误差时，该变换称为最佳变换，也称,Karhunen-Loeve,变换（,K-L,变换）。,K-L,变换的突出优点是相关性好，是均方误差（,MSE,，,Mean Square Error,）意义下的最佳变换，它在数据压缩技术中占有重要地位。,如果变换后的协方差矩阵接近对角矩阵，该类变换称为准最佳变换，典型的有,DCT,（离散余弦变换）、,DFT,（离散傅立叶变换）、,DWT,（离散小波变换）等。,48,2.6.2,离散傅立叶变换,一个变量的周期函数,g(x),能够通过傅立叶级数表示出来：,系数（,A,0,、,A,n,和,B,n,）的值按照下面的公式计算：,49,傅立叶变换,傅立叶变换,(Fourier Transform),的物理意义：将信号从时间域（,time domain,）变换到频率域（,frequency domain,）。,50,一维离散傅立叶变换（,DFT,）,正变换：,给定由,N,个信号样本（均匀间隔）,x(0),x(1),x(N-1),组成的信号序列，离散傅立叶变换（,DFT,，,Discrete Fourier Transform,）：,=0,1,2,N-1,逆变换：,k=0,1,2,N-1,51,二维离散傅立叶变换（,DFT,）,正变换：,给定一个二维信号的样本序列,x(k,l),k=0,1,N-1,l=0,1,N-1,，二维离散傅立叶变换（,2D-DFT,）,：,u,v =0,1,2,N-1,逆变换：,k,l=0,1,2,N-1,52,2.6.2,离散傅立叶变换,傅立叶分析法是一个强有力的工具，它使许多非常困难的问题变得简单和易于处理，傅立叶系数能够被变换、存储、传送，并且还能够被用做重建信号或者信号的函数。,已经发展了一套快速傅立叶变换（,FFT,，,Fast Fourier Transform,）的计算机算法，促进了它在信号处理中的应用，特别是在语音处理中的应用。,53,2.6.3,离散余弦变换,一维离散余弦变换,二维离散余弦变换,修改的离散余弦变换,54,2.6.3.1,一维离散余弦变换,p(x),的正离散余弦变换（,DCT,）,逆离散余弦变换（,IDCT,）,55,2.6.3.2,二维离散余弦变换,(,二维逆,DCT,),像素的二维排列能够通过水平和垂直方向的频率项乘积表示出来：,p,（,x,，,y,）的二维,DCT,56,2D-DCT,57,DCT,和,IDCT,例,58,2.6.3.3,修改的离散余弦变换,实际常常使用修改的离散余弦变换（,MDCT,，,Modified DCT,），,使用一种称为时域混,叠,消除（,TDAC,，,time domain aliasing cancellation,）技术，,抗混叠（,anti-aliasing,）效果好。,2,.,6,.3,.4,小波变换编码,小波变换是一个线性变换，能够将一个信号分解成对空间和时间、频率的独立贡献，同时又不失原信号所包含的信息。经过小波变换后的图像能量很集中，便于对不同的分量作不同的处理，达到较高的压缩比。,小波变换的具体内容在图像编码中详细讲解。,60,2.7,基于模型编码,基于模型的编码就是第二代编码技术。,基于模型方法的基本思想是：在发送端，利用图像分析模块对输入图像提取紧凑和必要的描述信息，得到一些数据量不大的模型参数；在接收端，利用图像综合模块重建原图像，是对图像信息的合成过程。,61,基于模型的图像编码基本原理框图,图像输入,图像分析,编码器,提取的模型参数,图像传输或存储,解码器,图像综合,模型,已量化的模型参数,图像输出,62,2.8,其他压缩编码,子带编码,向量量化编码,感知编码,63,2.8.1,子带编码,子带编码（,SBC,，,Sunband Coding,）是一种在频率域中进行数据压缩的方法，它主要利用一些频带比另一些在感知上作用更大。,在子带编码中，若各个子带的带宽,Wk,是相同的，则称为等带宽子带编码，否则，称为变带宽子带编码。,64,子带的概念,65,子带,编码器,66,子带,解码器,67,2.8.1,子带编码,对每个子带分别编码的好处是：,可以利用人耳（或人眼）对不同频率信号感知灵敏度不同的特性，在人的听觉（或视觉）不敏感的频段采用较粗糙的量化，从而达到数据压缩的目的。,各个子带的量化噪声都束缚在本子带内，这就可以避免能量较小的频带内的信号被其他频带中量化噪声所掩盖。,通过频带分裂，各个子带的取样频率可以成倍下降。,68,2.8.1,子带编码,经过分带编码、译码后合成的输出音频信号会有混迭效应。采用正交镜像滤波器（,QMF,，,quandrature mirror filter,）来划分频带，混迭效应在最后合成时可以抵消。,69,2.8.2,向量量化编码,在向量量化编码中，则是把输入数据几个一组地分成许多组，成组地量化编码，即将这些数看成一个,k,维向量，然后以向量为单位逐个向量进行量化。,向量量化是一种限失真编码，其原理仍可用信息论中的率失真函数理论来分析。,向量量化编码,向量量化编码是一种量化与压缩相结合的方法。,向量量化编码由两部分组成，,1,向量训练，,2,向量划分。,向量训练：在离线状态下，通过训练达到最佳的量化空间划分，尽量减少平均失真。已被量化的不重叠的空间称为,CodeBook,（,CB,）代码本,向量划分：将需要编码的代码看做向量，根据已有的,CB,进行划分到某一个空间中去。,70,VQ training,VQ example,Given the following CB(which has been calculated via training previously,find the CB vector(and index)that minimimises the distortion for the input vector x=5 2 8,VQ example,The distortion for each vector is:,The index that minimises D is index 2 and,the quantised vector is thus y(2)=2 3 8.,74,向量量化编码原理框图,75,2.8.2,向量量化编码,衡量两个向量之间接近程度的度量标准可以用均方误差准则：,也可以用其他准则,。,76,2.8.2,向量量化编码,在向量量化编码中，关键是码本的建立和码字搜索算法。,码本的生成算法有两种类型，一种是已知信源分布特性的设计算法；另一种是未知信源分布，但已知信源的一列具有代表性且足够长的样点集合（即训练序列）的设计算法,。,码字搜索是向量量化中的一个最基本问题，向量量化过程本身实际上就是一个搜索过程，即搜索出与输入最为匹配的码字。,77,2.8.3,感知编码,感知编码将感知知识应用于编码中。,感知编码的主要步骤是：首先将输入信号分解为各频谱元素，再根据某个心理听觉阈值和掩蔽门限进行量化编码，最后生成比特流。听觉阈值和掩蔽门限的计算需要对输入信号进行频域分解。,78,感知编码基本结构框图,2.9,差错检测和校正编码,放入附录中，请同学们自行学习,79,2,.,10,音频的压缩,音频频率范围,低频声音(Infra-sound)：0Hz20Hz,人类听觉频率范围的声音：20Hz20kHz,高频(Ultrasound)：20kHz1GHz,超声波(Hypersound)：1GHz10THz,不同音频的带宽,语音：200Hz3.4kHz,调幅广播：50Hz7kHz,调频广播：20Hz15kHz,宽带音响:20Hz20kHz,2,.,10,.1 音频压缩编码的基本方法,无失真压缩,音频压缩方法,有失真压缩,Huffman,编码,行程编码,波形编码,参数编码,混合编码,全频带编码,PCM,DPCM,ADPCM,子带编码,自适应变换编码,ATC,心理学模型,矢量量化,线性预测,LPC,矢量和激励线性预测,VSELP,多脉冲线性预测,MP-LPC,码本激励线性预测,CELP,2.10.2 质量的语音压缩标准,ITU,TS,建议的语音压缩的标准,G.711：,采用,PCM,编码，采样速率为8,kHz，,量化位数为8,bit，,对应的比特流速率为64,kbit/s。,G.721：,ITU,建议的,G.721,将64,Kbps,的比特流转换为32,Kbps,的流，它是基于,ADPCM,技术。每个数值差分用4位编码，其采样率为8,kHz。,2.10.2 质量的语音压缩标准,G.723：,G.723,是一种以24,Kbps,运行的基于,ADPCM,的有损耗压缩标准。其音质不如非压缩的,G.711PCM,标准以及基于,SBADPCM,的,G.722,标准。,G.723.1,和,G.723.2,用于,H.324,标准。,G.728：,它的 比特率为16,Kbps，,带宽限于3.4,kHz。,其音质比,G.711,或,G.722,差得多。它基于一种称为低延迟代码激励线性预测(,LDCELP),的向量量化技术。,2.10.2 质量的语音压缩标准,CELP是一种常用的语音压缩技术。它用于美国联邦标准1016，可将语音压缩至4.8Kbps。美国联邦标准1015使用 CELP的一个简本，称为线性预测编码(LPC)。LPC一10E标准可以运行于2.4Kbps。采用了一种向量量化方法。声音听起来有点象机器在说话，但4.8Kbps与 差不多。,2,.,10,.3 调幅广播质量的音频压缩标准,调幅广播质量：50,Hz7kHz，,称“7,kHz,音频信号”。,G.722：,G.722,基于子带,ADPCM,技术(,SBADPCM)，,它是将现有的带宽分成两个独立的子带信道分别采用差分脉码调制算法。,G.722,压缩信号的带宽范围为50,Hz,到7,kHz，,而,G.711,仅限于3.4,kHz。,其比特率为48、56、64,Kbps，,在标准模式下，采样速率是16,KHz，,幅度深度为14比特。,2,.,10,.4 高保真立体声音频压缩标准,高质量的声音信号频率范围：50,Hz20kHz,目前国际上比较成熟的高质量声音压缩标准为,MPEG,音频。,MPEGl,的音频信号在,ISO 111723,文档中的描述。,MPEG,音频不是单个一种压缩算法，而是3种音频编码和压缩方案的一个系列。,MPEG,声音编码分为：层,l、,层2、层3。随着层数的增加算法的复杂度也增大。,2,.,10,.4 高保真立体声音频压缩标准,所有3层都分级兼容。最复杂的译码器(即在层3工作的译码器)也可对层2或层,l,的码流进行译码。,所有3层都运用同一原理：变换编码和子带编码。,频谱被分为32个子带。,应用快速博里叶变换来表示高频域中的信号。,应用心理声学模式来变换信号以估计刚能引起注意的噪音级。,层,l、2,和 3主要在最后一个阶段-即量化阶段的方式上有所区别，但不是唯一的差别。,2,.,11,图像和视频的压缩,2,.,11,.1 图像和视频压缩编码的基本方法,图像和视频压缩方法,无失真压缩,有失真压缩,Huffman,编码,行程编码,算术编码,LZW,编码,预测编码,运动补偿,变换编码,DCT,变换,小波变换,子带编码,模型编码,分形编码,基于重要性,滤波,子采样,矢量量化,混合编码,JPEG,MPEG,H.261,2,.,11,.1 图像和视频压缩编码的基本方法,原始的彩色图像，一般由红、绿、蓝三种基色的图像组成（,R、G、B）。,然而人的视觉系统对彩色色度的感觉和亮度的敏感性是不同的，因此产生了不同的彩色空间表示。,H、S、I,彩色空间：,H,为色调、,S,为饱和度、,I,表示光的强度或亮度。,Y