资源描述
第第3章章 数字视频编码原理数字视频编码原理第3章 数字视频编码原理n了解图像和视频编码技术的发展历程,熟悉视频编码的各种了解图像和视频编码技术的发展历程,熟悉视频编码的各种方法。方法。n重点掌握哈夫曼编码、算术编码、预测编码和基于重点掌握哈夫曼编码、算术编码、预测编码和基于DCT的变的变换编码基本原理。换编码基本原理。n掌握运动估计和运动补偿预测编码的基本原理。掌握运动估计和运动补偿预测编码的基本原理。本章学习目标本章学习目标了解图像和视频编码技术的发展历程,熟悉视频编码的各种方法。本n3.1 数字视频编码概述数字视频编码概述n3.2 熵编码熵编码n3.3 预测编码预测编码n3.4 变换编码变换编码第第3章章 数字视频编码原理数字视频编码原理3.1 数字视频编码概述第3章 数字视频编码原理3.1.1 数字视频压缩的必要性和可能性数字视频压缩的必要性和可能性n数数据据压压缩缩的的理理论论基基础础是是信信息息论论。从从信信息息论论的的角角度度来来看看,压压缩缩就就是是去去掉掉数数据据中中的的冗冗余余,即即保保留留不不确确定定的的信信息息,去去掉掉确确定定的的信信息息(可可推推知知的的),也也就就是是用用一一种更接近信息本质的描述来代替原有冗余的描述。种更接近信息本质的描述来代替原有冗余的描述。n在在一一般般的的图图像像和和视视频频数数据据中中,主主要要存存在在以以下下几几种种形形式的冗余。式的冗余。3.1.1 数字视频压缩的必要性和可能性数据压缩的理论基础是n空间冗余:空间冗余:也称为空域冗余,是一种与像素间相关也称为空域冗余,是一种与像素间相关性直接联系的数据冗余。性直接联系的数据冗余。例例:图像中包含许多规则物体,它们的亮度、饱和度及颜图像中包含许多规则物体,它们的亮度、饱和度及颜色可能都一样,因此,图像在空间上具有很强的相关性。例色可能都一样,因此,图像在空间上具有很强的相关性。例如如 Lenna Lenna 图像的脸部和肩部。图像的脸部和肩部。3.1.1 数字视频压缩的必要性和可能性数字视频压缩的必要性和可能性空间冗余:也称为空域冗余,是一种与像素间相关性直接联系的数据n时间冗余:时间冗余:也称为时域冗余,它是针对视频序列图也称为时域冗余,它是针对视频序列图像而言的。像而言的。视视频频序序列列每每秒秒有有25 30帧帧图图像像,相相邻邻帧帧之之间间的的时时间间间间隔隔很很小小;同同时时实实际际生生活活中中的的运运动动物物体体具具有有运运动动一一致致性性,使使得得视频序列图像之间有很强的相关性。视频序列图像之间有很强的相关性。3.1.1 数字视频压缩的必要性和可能性数字视频压缩的必要性和可能性时间冗余:也称为时域冗余,它是针对视频序列图像而言的。3.1n统计冗余统计冗余 n信源熵:信源熵:如果将信源所有可能事件的信息量进行平均,如果将信源所有可能事件的信息量进行平均,就得到了信源熵就得到了信源熵(entropy)。熵就是平均信息量。熵就是平均信息量。n当当 xj 等概率时,等概率时,H(X)最大。最大。n当当 xj 非等概率时,非等概率时,H(X)不是最大,就存在冗余。不是最大,就存在冗余。采用可变长编码技术,对出现概率大的符号用短码字采用可变长编码技术,对出现概率大的符号用短码字表示,对出现概率小的符号用长码字表示,则可去除符号表示,对出现概率小的符号用长码字表示,则可去除符号冗余,从而节约码字,这就是冗余,从而节约码字,这就是熵编码熵编码的思想。的思想。3.1.1 数字视频压缩的必要性和可能性数字视频压缩的必要性和可能性统计冗余 当 xj 等概率时,H(X)最大。n结构冗余:结构冗余:在有些图像的部分区域内有着在有些图像的部分区域内有着很相似的纹理结构,或是图像的各个部分很相似的纹理结构,或是图像的各个部分之间存在着某种关系,例如自相似性等,之间存在着某种关系,例如自相似性等,这些都是结构冗余的表现。这些都是结构冗余的表现。分形图像编码分形图像编码的基本思想就是利用了结的基本思想就是利用了结构的自相似性。构的自相似性。3.1.1 数字视频压缩的必要性和可能性数字视频压缩的必要性和可能性结构冗余:在有些图像的部分区域内有着很相似的纹理结构,或是图n知识冗余:知识冗余:在某些特定的应用场合,编码对象中包含的在某些特定的应用场合,编码对象中包含的信息与某些先验的基本知识有关。信息与某些先验的基本知识有关。例如例如:人脸的图像有同人脸的图像有同样的结构:嘴的上方有鼻子,鼻子上方有眼睛,鼻子在中样的结构:嘴的上方有鼻子,鼻子上方有眼睛,鼻子在中线上线上 可可以以利利用用这这些些先先验验知知识识为为编编码码对对象象建建立立模模型型。通通过过提提取取模模型型参参数数,对对参参数数进进行行编编码码而而不不是是对对图图像像像像素素值值直直接接进进行行编编码码,可可以以达达到到非非常常高高的的压压缩缩比比。这这是是模模型型基基编编码码(或或称知识基编码、语义基编码)的基本思想。称知识基编码、语义基编码)的基本思想。3.1.1 数字视频压缩的必要性和可能性数字视频压缩的必要性和可能性知识冗余:在某些特定的应用场合,编码对象中包含的信息与某些先n人眼的视觉冗余人眼的视觉冗余 视视觉觉冗冗余余度度是是相相对对于于人人眼眼的的视视觉觉特特性性而而言言的的。压压缩缩视视觉觉冗冗余余的的核核心心思思想想是是去去掉掉那那些些相相对对人人眼眼而而言言是是看看不不到到的的或或可可有有可可无无的的图图像像数数据据。对对视视觉觉冗冗余余的的压压缩缩通通常常反反映映在在各各种种具具体体的压缩编码过程中。的压缩编码过程中。3.1.1 数字视频压缩的必要性和可能性数字视频压缩的必要性和可能性人眼的视觉冗余3.1.1 数字视频压缩的必要性和可能性n1948年提出电视信号的数字化,人们开始了对图像压缩编码的研究工作。n1952年哈夫曼给出最优变长码的构造方法。3.1.2 数字视频编码数字视频编码技术的进展技术的进展1948年提出电视信号的数字化,人们开始了对图像压缩编码的研n预测编码n1952年年,贝贝尔尔实实验验室室的的奥奥利利弗弗等等人人开开始始研研究究线线性性预预测测编编码码理论理论n1958年,格雷哈姆用计算机模拟法研究图像的年,格雷哈姆用计算机模拟法研究图像的DPCM方法方法n1966年年,奥奥尼尼尔尔通通过过理理论论分分析析和和计计算算模模拟拟比比较较了了PCM和和DPCM对电视信号进行编码传输的性能对电视信号进行编码传输的性能n20世纪世纪70年代开始进行了年代开始进行了帧间预测编码帧间预测编码的研究的研究n20世世纪纪80年年代代初初开开始始对对作作运运动动补补偿偿预预测测所所用用的的运运动动估估值值进进行研究行研究3.1.2 数字视频编码数字视频编码技术的进展技术的进展预测编码3.1.2 数字视频编码技术的进展n变换编码n首先讨论了包括首先讨论了包括K-L(Karhunen-Loeve)变换、变换、傅立叶变换等正交变换傅立叶变换等正交变换n1968年安德鲁斯等人采用二维离散傅立叶变换年安德鲁斯等人采用二维离散傅立叶变换(2D-DFT)提出了变换编码)提出了变换编码n此后相继出现了沃尔什此后相继出现了沃尔什-哈达玛(哈达玛(Walsh-Hadamard)变换、斜()变换、斜(Slant)变换、)变换、K-L变换、变换、离散余弦变换(离散余弦变换(DCT)等)等3.1.2 数字视频编码数字视频编码技术的进展技术的进展变换编码3.1.2 数字视频编码技术的进展n子带编码n1976年美国贝尔系统的克劳切等人提出了话音的年美国贝尔系统的克劳切等人提出了话音的子带编码。子带编码。n1985年奥尼尔将子带编码引入到图像编码。年奥尼尔将子带编码引入到图像编码。3.1.2 数字视频编码数字视频编码技术的进展技术的进展子带编码3.1.2 数字视频编码技术的进展n算术编码n1960年,年,P.Elias提出了算术编码的概念。提出了算术编码的概念。n1976年,年,R.Pasco和和J.Rissanen分别用定长的寄存器实现了分别用定长的寄存器实现了有限精度的算术编码。有限精度的算术编码。n1979年年Rissanen和和G.G.Langdon一起将算术编码系统化,一起将算术编码系统化,并于并于1981年实现了二进制编码。年实现了二进制编码。n1987年年Witten等人发表了一个实用的算术编码程序,即等人发表了一个实用的算术编码程序,即CACM87(后被(后被ITU-T的的H.263视频压缩标准采用)。视频压缩标准采用)。n同期,同期,IBM公司发表了著名的公司发表了著名的Q-编码器(后被编码器(后被JPEG建议建议的扩展系统和的扩展系统和JBIG二值图像压缩标准采用)。二值图像压缩标准采用)。3.1.2 数字视频编码数字视频编码技术的进展技术的进展算术编码3.1.2 数字视频编码技术的进展n基于模型编码n1983年瑞典的年瑞典的Forchheimer 和和Fahlander提出了提出了基于模型编码(基于模型编码(Model-Based Coding)的思想)的思想。3.1.2 数字视频编码数字视频编码技术的进展技术的进展基于模型编码3.1.2 数字视频编码技术的进展n小波变换编码n1986年,年,Meyer在理论上证明了一维小波函数的在理论上证明了一维小波函数的存在。存在。n1987年年Mallat提出了多尺度分析的思想及多分辨提出了多尺度分析的思想及多分辨率分析的概念,提出了相应的快速小波算法率分析的概念,提出了相应的快速小波算法Mallat算法,并把它有效地应用于图像分解和重算法,并把它有效地应用于图像分解和重构。构。n1989年,小波变换开始用于多分辨率图像描述。年,小波变换开始用于多分辨率图像描述。3.1.2 数字视频编码数字视频编码技术的进展技术的进展小波变换编码3.1.2 数字视频编码技术的进展n分层可分级编码n20世世纪纪90年年代代中中后后期期,Internet迅迅猛猛发发展展,移移动动通通信信也也迅迅速速在在全全球球普普及及,因因此此人人们们开开始始有有了了在在网网络络上上传传输输视视频频和和图图像像的的愿愿望望。在在网网络络上上传传输输视视频频和和图图像像等等多多媒媒体体信信息息除除了了要要解解决决误误码码问问题题之之外外,最最大大的的挑挑战战在在于于用用户户可可以以获获得得的的带带宽宽在在不不停停地地变变化化。为为了了适适应应网网络络带带宽宽的的变变化化,提提出出了了分分层层(layered)、可分级()、可分级(scalable)编码的思想。)编码的思想。3.1.2 数字视频编码数字视频编码技术的进展技术的进展分层可分级编码3.1.2 数字视频编码技术的进展压缩编码技术无损编码有损编码哈夫曼编码游程编码算术编码有损预测编码 变换编码 其他编码3.1.2 数字视频编码数字视频编码技术的进展技术的进展压缩编码技术无损编码有损编码哈夫曼编码游程编码算术编码有损预n无失真编码 无失真编码又称无损编码、信息保持编码、熵编码。无失真编码又称无损编码、信息保持编码、熵编码。熵熵编编码码是是纯纯粹粹基基于于信信号号统统计计特特性性的的一一种种编编码码方方法法,它它利利用用信信源源概概率率分分布布的的不不均均匀匀性性,通通过过变变长长编编码码来来减减少少信信源源数数据据冗冗余余,解解码码后后还还原原的的数数据据与与压压缩缩编编码码前前的的原原始始数数据据完完全全相相同同而不引入任何失真。而不引入任何失真。无无失失真真编编码码的的压压缩缩比比较较低低,可可达达到到的的最最高高压压缩缩比比受受到到信信源熵的理论限制,一般为源熵的理论限制,一般为2 1到到5 1。最最常常用用的的无无失失真真编编码码方方法法有有哈哈夫夫曼曼(Huffman)编编码码、算算术编码和游程编码术编码和游程编码(Run-Length Encoding,RLE)等。等。3.1.2 数字视频编码数字视频编码技术的进展技术的进展无失真编码3.1.2 数字视频编码技术的进展n限失真编码 限失真编码也称有损编码、非信息保持编码、熵压缩编限失真编码也称有损编码、非信息保持编码、熵压缩编码。码。限失真编码方法利用了人类视觉的感知特性,允许压缩限失真编码方法利用了人类视觉的感知特性,允许压缩过程中损失一部分信息,虽然在解码时不能完全恢复原始数过程中损失一部分信息,虽然在解码时不能完全恢复原始数据,但是如果把失真控制在视觉阈值以下或控制在可容忍的据,但是如果把失真控制在视觉阈值以下或控制在可容忍的限度内,则不影响人们对图像的理解,却换来了高压缩比。限度内,则不影响人们对图像的理解,却换来了高压缩比。在限失真编码中,允许的失真愈大,则可达到的压缩比愈高。在限失真编码中,允许的失真愈大,则可达到的压缩比愈高。常见的限失真编码方法有:预测编码、变换编码、矢量常见的限失真编码方法有:预测编码、变换编码、矢量量化、基于模型的编码等。量化、基于模型的编码等。3.1.2 数字视频编码数字视频编码技术的进展技术的进展限失真编码3.1.2 数字视频编码技术的进展n3.1 数字视频编码概述数字视频编码概述n3.2 熵编码熵编码n3.3 预测编码预测编码n3.4 变换编码变换编码第第3章章 数字视频编码原理数字视频编码原理3.1 数字视频编码概述第3章 数字视频编码原理3.2 熵编码熵编码 熵熵编编码码的的基基本本原原理理就就是是去去除除图图像像信信源源在在空空间间和和时时间间上上的的相相关关性性,去去除除图图像像信信源源像像素素值值的的概概率率分分布布不不均均匀匀性性,使使编编码码码码字字的的平平均均码码长长接接近近信信源源的的熵熵而而不不产产生生失失真真。由由于于这这种种编编码码完完全全基基于于图图像像的的统统计计特特性性,因因此此,有有时时也也称称其其为为统统计计编编码码。n哈哈夫夫曼曼(Huffman)编编码码n算算术术编编码码n游游程程编编码码(Run-Length Encoding,RLE)3.2 熵编码 熵编码的基本原理就是去除图像信 哈哈夫夫曼曼(Huffman)于于1952年年提提出出一一种种编编码码方方法法,完完全全依依据据符符号号出出现现概概率率来来构构造造异异字字头头(前前缀缀)的的平平均均长长度度最最短短的的码码字字,有有时时称称之之为最佳编码。为最佳编码。哈哈 夫夫 曼曼 编编 码码 是是 一一 种种 可可 变变 长长 度度 编编 码码(Variable Length Coding,VLC),各各符符号与码字一一对应,是一种分组码。号与码字一一对应,是一种分组码。3.2.1 哈夫曼哈夫曼编码编码 哈夫曼(Huffman)于1952年提出一种l Huffman编码过程(编码过程(1)把信源符号按概率大小顺序排列,并设法按逆次序分配把信源符号按概率大小顺序排列,并设法按逆次序分配 码字的长度。在分配码字的长度时,首先将出现概率最码字的长度。在分配码字的长度时,首先将出现概率最 小的两个符号的概率相加,合成一个概率;第二步把这小的两个符号的概率相加,合成一个概率;第二步把这 个合成概率看成是一个新组合符号的概率,重复上述操个合成概率看成是一个新组合符号的概率,重复上述操 作,直到最后只剩下两个符号的概率为止。作,直到最后只剩下两个符号的概率为止。3.2.1 哈夫曼哈夫曼编码编码 Huffman编码过程(1)把信源符号按概率大小顺序排 完成以上概率相加顺序排列后,再反过来逐步向前进行完成以上概率相加顺序排列后,再反过来逐步向前进行 编码,每一步有两个分支,各赋予一个二进制码,可以编码,每一步有两个分支,各赋予一个二进制码,可以 对概率大的编码赋予对概率大的编码赋予0,概率小的编码赋予,概率小的编码赋予1。反之,。反之,也可以对概率大的编码赋予也可以对概率大的编码赋予1,概率小的编码赋予,概率小的编码赋予0。l Huffman编码过程(编码过程(2)3.2.1 哈夫曼哈夫曼编码编码 完成以上概率相加顺序排列后,再反过来逐步向前进行 Hufl Huffman编码举例编码举例编码编码过程过程cbafe10f=01 e=11 a=10 b=001 c=0001 d=0000d10101010aaaa bbb cc d eeeee fffffff Huffman编码举例编码过程cbafe7/225/224输入输入S1S2S3S4S5S6输入概率输入概率0.40.30.10.10.060.04l Huffman编码举例编码举例输入输入概率 Huffman编码举例输入输入S1S2S3S4S5S6输入概率输入概率0.40.30.10.10.060.04第一步第一步0.40.30.10.10.1l Huffman编码举例编码举例输入输入概率第一步 Huffman编码举例输入输入S1S2S3S4S5S6输入概率输入概率0.40.30.10.10.060.04第一步第一步0.40.30.10.10.1第二步第二步0.40.30.20.1l Huffman编码举例编码举例输入输入概率第一步第二步 Huffman编码举例输入输入S1S2S3S4S5S6输入概率输入概率0.40.30.10.10.060.04第一步第一步0.40.30.10.10.1第二步第二步0.40.30.20.1第三步第三步0.40.30.3l Huffman编码举例编码举例输入输入概率第一步第二步第三步 Huffman编码举例输入输入S1S2S3S4S5S6输入概率输入概率0.40.30.10.10.060.04第一步第一步0.40.30.10.10.1第二步第二步0.40.30.20.1第三步第三步0.40.30.3第四步第四步0.60.4l Huffman编码举例编码举例输入输入概率第一步第二步第三步第四步 Huffman编码举例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101l Huffman编码举例编码举例输入输入概率第一步第二步第三步第四步00000 Huffma输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S1=1l Huffman编码举例编码举例输入输入概率第一步第二步第三步第四步00000S1=1 Hu输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S2=00l Huffman编码举例编码举例输入输入概率第一步第二步第三步第四步00000S2=00 H输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S3=011l Huffman编码举例编码举例输入输入概率第一步第二步第三步第四步00000S3=011 输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S4=0100l Huffman编码举例编码举例输入输入概率第一步第二步第三步第四步00000S4=0100输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S5=01010l Huffman编码举例编码举例输入输入概率第一步第二步第三步第四步00000S5=0101输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S6=01011l Huffman编码举例编码举例输入输入概率第一步第二步第三步第四步00000S6=0101例:例:信源有四个符号:信源有四个符号:X a1 a2 a3 a4 1/2 1/4 1/8 1/8n信源熵:信源熵:nHuffman(二进制编码)(二进制编码)a1 a2 a3 a4 0 10 110 111 平均码长:平均码长:Iav=(1/2)1+(1/4)2+(1/8)6=1.75 bit/字符字符 编码效率:编码效率:=1.75/1.75=100%编码冗余:编码冗余:R=0a1 1/2a2 1/4a3 1/8a4 1/800011/211/4 1010110111例:信源有四个符号:Huffman(二进制编码)n4 个符号的等长码:个符号的等长码:B=log24=2bit a1 a2 a3 a4 00 01 10 11 L=2 编码效率:编码效率:=H(X)/L=1.75/2=87.5%nHuffman 编码举例:编码举例:原信源输出序列:原信源输出序列:a1 a2 a1 a3 a2 a1 a1 a4.编码后的序列:编码后的序列:0 10 0 110 10 0 0 111.4 个符号的等长码:Huffman 编码举例:Huffman 码解码码解码nHuffman 码是非歧义的码是非歧义的,在解码过程中,对某个码字的解,在解码过程中,对某个码字的解释是唯一的。释是唯一的。n原信源输出序列:原信源输出序列:a1 a2 a1 a3 a2 a1 a1 a4.,编码后的序,编码后的序列:列:0 10 0 110 10 0 0 111.n当接收端收到码流当接收端收到码流 01001101000111 时,按照码表,以时,按照码表,以 0 开头开头的码字只有的码字只有 0,因此,解出第,因此,解出第 1 个符号为个符号为 a1;n去掉已解码的去掉已解码的 0 后,码流剩下后,码流剩下 1001101000111,以,以 1 开头,第开头,第2比比特是特是 0,因此,码字是,因此,码字是 10,因此,解出第,因此,解出第 2 个符号为个符号为 a2;n.n顺着码树解码,树根顺着码树解码,树根树干树干树枝树枝树叶树叶00010 a110 a211110 a3111 a4码码树树结结构构00010 a110 a2110 a3111 a411Huffman 码解码Huffman 码是非歧义的,在解码过n哈夫曼编码的特点n哈哈夫夫曼曼编编码码的的算算法法是是确确定定的的,但但编编出出的的码码并并非非是是唯一的。唯一的。n由由于于哈哈夫夫曼曼编编码码的的依依据据是是信信源源符符号号的的概概率率分分布布,故其编码效率取决于信源的统计特性。故其编码效率取决于信源的统计特性。n哈夫曼码没有错误保护功能。哈夫曼码没有错误保护功能。n哈哈夫夫曼曼码码是是可可变变长长度度码码,码码字字字字长长参参差差不不齐齐,输输出出码码率率是是变变化化的的。因因此此,对对于于恒恒定定码码率率信信道道,需需要增加输出缓存器来平滑。要增加输出缓存器来平滑。n对对信信源源进进行行哈哈夫夫曼曼编编码码后后,形形成成了了一一个个哈哈夫夫曼曼编编码码表表,解解码码时时,必必须须参参照照这这一一哈哈夫夫编编码码表表才才能能正正确解码。确解码。3.2.1 哈夫曼哈夫曼编码编码哈夫曼编码的特点3.2.1 哈夫曼编码3.2.1 哈夫曼哈夫曼编码编码3.2.1 哈夫曼编码n从理论上分析,采用哈夫曼编码可以获得最从理论上分析,采用哈夫曼编码可以获得最佳信源字符编码效果佳信源字符编码效果;n实际应用中,由于信源字符出现的概率并非实际应用中,由于信源字符出现的概率并非满足满足2 2的负幂次方,因此往往无法达到理论上的负幂次方,因此往往无法达到理论上的编码效率和压缩比。的编码效率和压缩比。3.2.2 算术编码算术编码从理论上分析,采用哈夫曼编码可以获得最佳信源字符编码效果;3n设字符序列设字符序列x,y对应的概率为对应的概率为1/3,2/3,Nx和和Ny分别表示字符分别表示字符x和和y的最佳码长,则根据信息论有:的最佳码长,则根据信息论有:3.2.2 算术编码算术编码设字符序列x,y对应的概率为1/3,2/3,Nx和Nn字符字符x、y的最佳码长分别为的最佳码长分别为1.58bit和和0.588bit;n这表明,要获得最佳编码效果,需要采用小数码字这表明,要获得最佳编码效果,需要采用小数码字长度长度,这是不可能实现的这是不可能实现的;n即采用哈夫曼方法对即采用哈夫曼方法对x,y的码字分别为的码字分别为0和和1,也,也就是两个符号信息的编码长度都为就是两个符号信息的编码长度都为1。对于出现概。对于出现概率大的字符率大的字符y并未能赋予较短的码字并未能赋予较短的码字;n实际编码效果往往不能达到理论效率实际编码效果往往不能达到理论效率;n为提高编码效率,为提高编码效率,Elias等人提出了算术编码算法。等人提出了算术编码算法。3.2.2 算术编码算术编码字符x、y的最佳码长分别为1.58bit和0.588bit;算术编码是一种非分组编码,它用一个算术编码是一种非分组编码,它用一个浮点数值表示浮点数值表示整个信源符号序列整个信源符号序列。算术编码。算术编码将被编码的信源符号序列表示成实数半开区将被编码的信源符号序列表示成实数半开区间间0,1)中的一个数值间隔。这个间隔随)中的一个数值间隔。这个间隔随着信源符号序列中每一个信源符号的加入逐着信源符号序列中每一个信源符号的加入逐步减小,每次减小的程度取决于当前加入的步减小,每次减小的程度取决于当前加入的信源符号的先验概率。信源符号的先验概率。3.2.2 算术编码算术编码 算术编码是一种非分组编码,它用一个浮点数值表n符号序列符号序列 S3S3S2S4 为例为例S1S2S3S4S1S2S3S4S1S2S3S401/83/87/81.000.0010.0110.1111.00.0110.1110.0111 0.10010.1101在算术编码中通常采用二进制分数表示在算术编码中通常采用二进制分数表示概率,概率,每个符号所对应的概率区间都是每个符号所对应的概率区间都是半开区间半开区间,即该区间包括左端点,而不,即该区间包括左端点,而不包括右端点,如包括右端点,如 S1对应对应 0,0.001),S2 对对应应 0.001,0.01)等。等。3.2.2 算术编码算术编码符号序列 S3S3S2S4 为例S1S2S3S4S1S2游程编码,也称游程编码,也称行程编码行程编码或或游程(行程)长度编码游程(行程)长度编码(Run Length Encoding,RLE)n游游程:具有相同灰度值的像素序列程:具有相同灰度值的像素序列。n游程长度:灰度值相同的相邻像素的数目。游程长度:灰度值相同的相邻像素的数目。n游程编码游程编码思想:思想:去除像素冗余。去除像素冗余。n用游程的灰度和游程的长度代替游程本身。用游程的灰度和游程的长度代替游程本身。例:设重复次数为例:设重复次数为 iC,iC,重复像素值为重复像素值为 iPiP编码为:编码为:iPiC iPiC iPiCiPiC iPiC iPiC 编码前:编码前:aaaaaaaaaaaaaabbbbbbbbbbbbcccccccccccccccc 编码后:编码后:a a7 7b b6 6c c8 83.2.3 游程编码游程编码游程编码,也称行程编码或游程(行程)长度编码(Run Lenq由于一幅图像中有许多颜色相同的图块,用一整数对存储一由于一幅图像中有许多颜色相同的图块,用一整数对存储一个像素的颜色值及相同颜色像素的数目(长度)。例如:个像素的颜色值及相同颜色像素的数目(长度)。例如:(G G,L 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对数据对数据3.2.3 游程编码游程编码由于一幅图像中有许多颜色相同的图块,用一整数对存储一个像素的n3.1 数字视频编码概述数字视频编码概述n3.2 熵编码熵编码n3.3 预测编码预测编码n3.4 变换编码变换编码第第3章章 数字视频编码原理数字视频编码原理3.1 数字视频编码概述第3章 数字视频编码原理3.3 预测编码预测编码 预预测测编编码码的的基基本本原原理理就就是是利利用用图图像像数数据据的的相相关关性性,利利用用已已传传输输的的像像素素值值对对当当前前需需要要传传输输的的像像素素值值进进行行预预测测,然然后后对对当当前前像像素素的的实实际际值值与与预预测测值值的的差差值值(即即预预测测误误差差)进进行行编编码码传传输输,而而不不是是对对当当前前像像素素值值本本身身进进行行编编码码传传输输,以以去去除除图图像像数数据据中中的的空空间间相相关关冗冗余余或时间相关冗余。或时间相关冗余。3.3 预测编码 预测编码的基本原理就是利用图n预测编码:根据某一预测编码:根据某一模型模型,利用信号以,利用信号以往的样本值对新样本值进行预测,对往的样本值对新样本值进行预测,对预预测误差测误差进行编码。进行编码。n对于对于相关性较强相关性较强的信号,如果建立的信号,如果建立合适合适的模型的模型,预测误差预测误差的幅值将远远小于原的幅值将远远小于原始信号,从而可以用较少的始信号,从而可以用较少的量化级量化级对其对其误差信号进行误差信号进行量化量化,得到较大的数据压,得到较大的数据压缩效果。缩效果。3.3.1 帧内预测编码帧内预测编码预测编码:根据某一模型,利用信号以往的样本值对新样本值进行预n问题:能否问题:能否精确精确地地预测预测数据源输出?数据源输出?答案答案:否否 数据源是不确定的数据源是不确定的n几乎没有一个实际的系统能找到可以精几乎没有一个实际的系统能找到可以精确预测输出的确预测输出的模型模型n 能找到的能找到的最优预测模型最优预测模型是以某种是以某种最小误最小误差差意义下的预测模型。意义下的预测模型。3.3.1 帧内预测编码帧内预测编码问题:能否精确地预测数据源输出?3.3.1 帧内预测编码n对于静止图像,由于相邻像素具有很强的对于静止图像,由于相邻像素具有很强的相关性,这样当前像素的灰度(颜色)值相关性,这样当前像素的灰度(颜色)值可用前面已经出现的像素值进行预测,得可用前面已经出现的像素值进行预测,得到一个预测值,对实际值与预测值的差值到一个预测值,对实际值与预测值的差值进行编码,进行编码,3.3.1 帧内预测编码帧内预测编码对于静止图像,由于相邻像素具有很强的相关性,这样当前像素的灰3.3.1 帧内预测编码帧内预测编码n1.DPCM系统的基本原理系统的基本原理 DPCM(Differential Pulse Code Modulation,差,差分脉冲编码调制分脉冲编码调制)3.3.1 帧内预测编码1.DPCM系统的基本原理n2.预测模型预测模型 设设 时刻之前的样本值时刻之前的样本值 与预测值之间的关系呈现某种函数形式与预测值之间的关系呈现某种函数形式n线性预测编码器线性预测编码器n非线性预测编码器非线性预测编码器3.3.1 帧内预测编码帧内预测编码2.预测模型3.3.1 帧内预测编码 在图像数据压缩中,常用如下几种图像数据压缩中,常用如下几种线性线性预测预测方案:方案:n前值预测前值预测,即,即n一维预测一维预测,即采用同一扫描行中前面已知的,即采用同一扫描行中前面已知的若干个样值来预测。若干个样值来预测。n二维预测二维预测,即不但用同一扫描行中的前面几,即不但用同一扫描行中的前面几个样值,而且还要用以前几行扫描行中样值个样值,而且还要用以前几行扫描行中样值来预测。来预测。3.3.1 帧内预测编码帧内预测编码 在图像数据压缩中,常用如下几种线性预测方案:3.3.2 帧间预测编码帧间预测编码序列图像在时间上的冗余情况可分为如下几种:序列图像在时间上的冗余情况可分为如下几种:n对于静止不动的场景对于静止不动的场景,当前帧和前一帧的图像内容,当前帧和前一帧的图像内容是完全相同的。是完全相同的。n对于运动的物体对于运动的物体,只要知道其运动规律,就可以从,只要知道其运动规律,就可以从前一帧图像推算出它在当前帧中的位置。前一帧图像推算出它在当前帧中的位置。n摄像机摄像机对着场景的横向移动、焦距变化等操作会引对着场景的横向移动、焦距变化等操作会引起整个图像的平移、放大或缩小。对于这种情况,起整个图像的平移、放大或缩小。对于这种情况,只要只要摄像机的运动摄像机的运动规律和镜头改变的参数已知,图规律和镜头改变的参数已知,图像随时间所产生的变化也是可以推算出来的。像随时间所产生的变化也是可以推算出来的。3.3.2 帧间预测编码序列图像在时间上的冗余情况可分为如下帧间预测的依据:帧间预测的依据:n图像序列在时间轴方向的相关性;图像序列在时间轴方向的相关性;n物体的背景或物体的一部分相对不变或变化缓慢;物体的背景或物体的一部分相对不变或变化缓慢;n人类的视觉特性:人类的视觉特性:n 人类的视觉对静止图像有较高的空间分辨率,但是可以减人类的视觉对静止图像有较高的空间分辨率,但是可以减少传输帧数来降低时间轴分辨率,未传输的帧可以通过计算少传输帧数来降低时间轴分辨率,未传输的帧可以通过计算补出来;补出来;n 对运动图像分辨率低,可以对这一部分图像降低清晰度。对运动图像分辨率低,可以对这一部分图像降低清晰度。3.3.2 帧间预测编码帧间预测编码帧间预测的依据:3.3.2 帧间预测编码为什么进行运动补偿预测?为什么进行运动补偿预测?n 对于活动图像编码,帧间预测是主要的手段;对于活动图像编码,帧间预测是主要的手段;n 基本帧间预测方法对于存在大量静止区域或缓变区域基本帧间预测方法对于存在大量静止区域或缓变区域的图像,预测效果不错;的图像,预测效果不错;n 对于活动的物体,预测效果不理想;对于活动的物体,预测效果不理想;n 对于一些发生运动的图像进行预测编码,采用运动补对于一些发生运动的图像进行预测编码,采用运动补偿预测的方法。偿预测的方法。3.3.2 帧间预测编码帧间预测编码为什么进行运动补偿预测?3.3.2 帧间预测编码n运动补偿预测运动补偿预测 3.3.2 帧间预测编码帧间预测编码运动补偿预测 3.3.2 帧间预测编码运动补偿预测的基本原理:运动补偿预测的基本原理:u自然场景的视频图像只有其中的部分区域在运动,同一场景自然场景的视频图像只有其中的部分区域在运动,同一场景相邻的两帧图像之间差异也不会太大,编码器无需将视频序相邻的两帧图像之间差异也不会太大,编码器无需将视频序列中每帧图像的所有信息都进行编码后传输给解码器端,只列中每帧图像的所有信息都进行编码后传输给解码器端,只要将当前帧中目标的运动信息告知解码器端,解码器可根据要将当前帧中目标的运动信息告知解码器端,解码器可根据运动信息和前一帧图像内容来更新当前帧图像,获得当前帧运动信息和前一帧图像内容来更新当前帧图像,获得当前帧的真实数据的真实数据。(可有效降低编码所需数据量)(可有效降低编码所需数据量)u从序列图像中提取有关物体运动的信息的过程从序列图像中提取有关物体运动的信息的过程运动运动估计估计(如何快速、有效的获得足够精度的运动矢量);(如何快速、有效的获得足够精度的运动矢量);u把前一帧相应的运动部分信息根据运动矢量补偿过来的把前一帧相应的运动部分信息根据运动矢量补偿过来的过程过程运动补偿运动补偿(Motion Compensation,MC)。)。3.3.2 帧间预测编码帧间预测编码运动补偿预测的基本原理:3.3.2 帧间预测编码n 运动估计运动估计将当前帧活动图像分为若干局部结构将当前帧活动图像分为若干局部结构(像素块),检测出每个局部结构在前一帧图像中(像素块),检测出每个局部结构在前一帧图像中的位置,从而可以估计出这个结构的位移。即对运的位置,从而可以估计出这个结构的位移。即对运动物体从前一帧到当前帧位移的方向和像素数作出动物体从前一帧到当前帧位移的方向和像素数作出估计,也就是求出估计,也就是求出运动矢量运动矢量。n 运动补偿运动补偿根据求出的运动矢量,找到当前帧的根据求出的运动矢量,找到当前帧的像素(或像素块)是从前一帧的哪个位置移动过来像素(或像素块)是从前一帧的哪个位置移动过来的,从而得到当前帧像素(或像素块)的预测值。的,从而得到当前帧像素(或像素块)的预测值。3.3.2 帧间预测编码帧间预测编码 运动估计将当前帧活动图像分为若干局部结构(像素块),检运动估计与运动补偿预测编码步骤:运动估计与运动补偿预测编码步骤:n 分割图像为若干局部结构分割图像为若干局部结构划分静止和运动区域;划分静止和运动区域;n 最简单方法:最简单方法:分块分块n 运动估计运动估计对每一个运动物体进行位移估计;对每一个运动物体进行位移估计;n 运动补偿运动补偿由位移估计建立同一运动物体在不同帧由位移估计建立同一运动物体在不同帧空间位置对应关系,建立预测关系;空间位置对应关系,建立预测关系;n 对于运动补偿后的位移帧差信号、运动矢量进行编码对于运动补偿后的位移帧差信号、运动矢量进行编码传输。传输。3.3.2 帧间预测编码帧间预测编码运动估计与运动补偿预测编码步骤:3.3.2 帧间预测编码n运动估计方法运动估计方法:n像素递归法像素递归法:根据像素间亮度的变化和梯度,通过递:根据像素间亮度的变化和梯度,通过递归修正的方法来估计每个像素的运动矢量。接收端在归修正的方法来估计每个像素的运动矢量。接收端在与发送端同样的条件下,用与发送端相同的方法进行与发送端同样的条件下,用与发送端相同的方法进行运动估值。像素递归法估计精度高,可以满足运动补运动估值。像素递归法估计精度高,可以满足运动补偿帧内插的要求。但接收端较复杂,不利于一发多收偿帧内插的要求。但接收端较复杂,不利于一发多收(如数字电视广播等)的应用。(如数字电视广播等)的应用。n块匹配算法块匹配算法:块匹配算法对当前帧图像的每一子块,:块匹配算法对当前帧图像的每一子块,在前一帧(第在前一帧(第K-1K-1帧)的一定范围内搜索最优匹配,帧)的一定范围内搜索最优匹配,并认为本图像子块就是从前一帧最优匹配块位置处平并认为本图像子块就是从前一帧最优匹配块位置处平移过来的。块匹配算法虽然作了一定假设(移过来的。块匹配算法虽然作了一定假设(假设位于假设位于同一图像子块内的所有像素都作相同的运动,且只作同一图像子块内的所有像素都作相同的运动,且只作平移运动平移运动),但满足了计算复杂度和实时实现的要求。),但满足了计算复杂度和实时实现的要求。3.3.2 帧间预测编码帧间预测编码运动估计方法:3.3.2 帧间预测编码n块匹配算法块匹配算法(BMA)(BMA):3.3.2 帧间预测编码帧间预测编码块匹配算法(BMA):3.3.2 帧间预测编码运动矢量的算法框图3.3.2 帧间预测编码帧间预测编码运动矢量的算法框图3.3.2 帧间预测编码n方块大小的选取块块大大时时,一一个个方方块块可可能能包包含含多多个个作作不不同同运运动动的的物物体体,块块内内各各像像素素作作相相同同平平移移运运动动的的假假设难以成立,影响估计精度。设难以成立,影响估计精度。若若块块太太小小,则则估估计计精精度度容容易易受受噪噪声声干干扰扰的的影影响响,不不够够可可靠靠,而而且且传传送送运运动动矢矢量量所所需需的的附加比特数过多,不利于数据压缩。附加比特数过多,不利于数据压缩。一般都用一般都用1616像素的块作为匹配单元。像素的块作为匹配单元。块匹配算法块匹配算法(BMA)方块大小的选取块匹配算法(BMA)n最优匹配准则n绝对差均值(绝对差均值(MAD,Mean Absolute Difference)最小准则)最小准则 n均方误差(均方误差(MSE,Mean Squared Error)最小准则)最小准则n归一化互相关函数最大准则归一化互相关函数最大准则块匹配算法块匹配算法(BMA)最优匹配准则块匹配算法(BMA)n最优匹配点的搜索方法最优匹配点的搜索方法n穷尽搜索穷尽搜索(full search,也称,也称全搜索全搜索)n快快速速搜搜索索:其其算算法法共共同同之之处处在在于于它它们们把把使使准准则则函函数数(例例如如,MAD)趋趋于于极极小小的的方方向向视视同同为为最最小小失失真真方方向向,并并假假定定准准则则函函数数在在偏偏离离最最小小失失真真方方向向时时是是单单调调递递增增的的,即即认认为为它它在在整整个个搜搜索索区区内内是是(i,j)的的单单极极点点函函数数,有有唯唯一一的的极极小小值值,而而快快速速搜搜索索是是从从任任一一猜猜测测点点开开始始沿沿最最小小失失真真方方向向进进行的。行的。n分分级级搜搜索索:先先通通过过对对原原始始图图像像滤滤波波和和亚亚采采样样得得到到一一个个图图像像序序列列的的低低分分辨辨率率表表示示,再再对对所所得得低低分分辨辨率率图图像像进进行行全全搜搜索索。由由于于分分辨辨率率降降低低,使使得得搜搜索索次次数数成成倍倍减减少少,这这一一步步可可以以称称为为粗粗搜搜索索。然然后后,再再以以低低分分辨辨率率图图像像搜搜索索的的结结果果作作为为下下一一步步细细搜搜索索的的起起始始点点。经经过过粗粗、细细两两级级搜搜索索,便得到了最终的运动矢量估值。便得到了最终的运动矢量估值。块匹配算法块匹配算法(BMA)最优匹配点的搜索方法块匹配算法(BMA)BMA常用搜索算法常用搜索算法三步搜索法三步搜索法:BMA常用搜索算法三步搜索法:BMA常常用搜索算法用搜索算法二维对数搜索法二维对数搜索法:BMA常用搜索算法二维对数搜索法:n在视频帧序列中设置参照帧,且第在视频帧序列中设置参照帧,且第1帧总是参照帧。帧总是参照帧。n对对于于当当前前的的编编码码帧帧,首首先先在在该该帧帧的的前前一一帧帧和和/或或后后一一帧帧(参参照照帧帧)中中寻寻找找与与该该帧帧的的一一个个图图像像方方块块最最优优匹匹配的图像方块。配的图像方块。n如果找到这样的最优匹配块,则进行下列计算:如果找到这样的最优匹配块,则进行下列计算:n计计算算当当前前块块的的像像素素值值与与参参照照帧帧中中最最优优匹匹配配块块(称称参照块)的像素值之间的差值,即预测误差;参照块)的像素值之间的差值,即预测误差;n计计算算当当前前块块相相对对于于参参照照块块在在水水平平(x)和和垂垂直直(y)两个方向上的位移,即运动矢量。)两个方向上的位移,即运动矢量。n如如果果找找不不到到最最优优匹匹配配块块,则则必必须须进进行行帧帧内内编编码码,即即对当前块的像素样本值进行编码传输。对当前块的像素样本值进行编码传输。运动补偿帧间预测编码过程运动补偿帧间预测编码过程在视频帧序列中设置参照帧,且第1帧总是参照帧。运动补偿帧间预帧间预测编码帧间预测编码原理图原理图帧间预测编码原理图n单向运动补偿预测:单向运动补偿预测:只使用前参照帧或后参只使用前参照帧或后参照帧中的一个来进行预测。照帧中的一个来进行预测。n双向运动补偿预测:双向运动补偿预测:使用前、后两个帧作为使用前、后两个帧作为参照帧来计算各块的运动矢量,最后只选用参照帧来计算各块的运动矢量,最后只选用与具有最小匹配误差的参照帧相关的运动矢与具有最小匹配误差的参照帧相关的运动矢量值。量值。n插值运动补偿预测:插值运动补偿预测:取前参照帧预测值与后取前参照帧预测值与后参照帧预测值的平均值。这时,需要对两个参照帧预测值的平均值。这时,需要对两个运动矢量分别进行编码传输。运动矢量分别进行编码传输。运动补偿帧间预测类型运动补偿帧间预测类型单向运动补偿预测:只使用前参照帧或后参照帧中的一个来进行预测双向预测双向预测B帧的压缩编码原理帧的压缩编码原理双向预测B帧的压缩编码原理n3.1 数字视频编码概述数字视频编码概述n3.2 熵编码熵编码n3.3 预测编码预测编码n3.4 变换编码变换编码第第3章章 数字视频编码原理数字视频编码原理3.1 数字视频编码概述第3章 数字视频编码原理n预测编码希望通过对信源建模尽可能精确地预预测编码希望通过对信源建模尽可能精确地预测数据,然后对预测误差进行编码。测数据,然后对预测误差进行编码。n变换编码的思路:将原始数据从时间域或者空变换编码的思路:将原始数据从时间域或者空间域间域“变换变换”到另一个更为紧凑表示、适合于到另一个更为紧凑表示、适合于压缩的变换域(通常为频域),从而得到比预压缩的变换域(通常为频域),从而得到比预测编码更高效率的数据表示(压缩)。测编码更高效率的数据表示(压缩)。n预测编码消除相关性的能力有限,变换编码是预测编码消除相关性的能力有限,变换编码是一种更高效的压缩编码。一种更高效的压缩编码。3.4.1 变换编码的基本原理变换编码的基本原理3.4.1 变换编码的基本原理3.4.2 基于基于DCT的的图像编码图像编码3.4.2 基于DCT的图像编码88 二维二维DCT变换变换88 二维二维DCT反变换反变换当当 时,时,当当u、v为其他值时为其他值时3.4.2 基于基于DCT的的图像编码图像编码88 二维DCT变换3.4.2 基于DCT的图像编码 88二维二维DCT反变换的变换核函数为反变换的变换核函数为 按按u,v分别展开后得到分别展开后得到64个个88像素的图像块像素的图像块组,称为基图像。组,称为基图像。3.4.2 基于基于DCT的的图像编码图像编码3.4.2 基于DCT的图像编码88二维二维DCT变换基图像变换基图像88二维DCT变换基图像n量化量化 量化处理是一个多到一的映射,它是造成量化处理是一个多到一的映射,它是造成DCT编解码信息损失的根源。编解码信息损失的根源。根据人眼的视觉特性,对不同的变换系数根据人眼的视觉特性,对不同的变换系数设置不同的量化步长。设置不同的量化步长。3.4.2 基于基于DCT的的图像编码图像编码量化3.4.2 基于DCT的图像编码JPEG标准中亮度标准中亮度DCT系数的量化步长系数的量化步长3.4.2 基于基于DCT的的图像编码图像编码JPEG标准中亮度DCT系数的量化步长3.4.2 基于DCJPEG标准中色度标准中色度DCT系数的量化步长系数的量化步长3.4.2 基于基于DCT的的图像编码图像编码JPEG标准中色度DCT系数的量化步长3.4.2 基于DCnZig-Zag(或或 称称“Z”字字形形,“之之”字形)扫描字形)扫描 DC直直流流系系数数AC01交流系数扫描开始交流系数扫描开始交流系数扫描结束AC07AC70AC77变换系数变换系数熵编码熵编码3.4.2 基于基于DCT的的图像编码图像编码Zig-Zag(或称“Z”字形,“之”字形)扫描DC直流系数n直直流流分分量量(DC):相相邻邻图图像像子子块块的的直直流流分分量量(图图像像子子块块的的平平均均样样值值)也也存存在在着着相相关关性性,所所以以对对DC的的量量化化系系数数用用DPCM编编码码较较合合适适,即即对对当当前前块块和和前前一一块块的的DC系数的差值进行编码。系数的差值进行编码。n交交流流分分量量(AC):把把数数值值为为0的的连连续续长长度度(即即0游游长长)和和非非0值值结结合合起起来来构构成成一一个个事事件件(Run,Level),然然后再对事件(后再对事件(Run,Level)进行熵编码)进行熵编码。变换系数变换系数熵编码熵编码
展开阅读全文