（计算机应用技术专业论文）一种基于线性搜索的快速运动估计算法.pdf

浙江大学硕士学位论文 摘要 随着多媒体技术和网络技术的飞速发展，以视频压缩编码为基础的数字视频 的应用也越来越广泛。运动估计是视频压缩编码的核心技术之一，能有效降低序 列图像的帧间冗余，实现高效编码。研究快速有效的运动估计算法一直是视频压 缩编码领域的热点问题之一，其中块匹配运动估计算法具有计算复杂度低和易于 软硬件实现的特点，被广泛应用于m p e g 1 2 4 和h 2 6 x 等视频编码标准中。 在h 2 6 4 视频编码标准中，运动估计占用了编码器极大的计算量。为了降低 运动估计算法的复杂度，提高运动估计的准确性，进而提高编码效率，本文根据 视频序列的各种特性，提出了一种新的线性运动估计算法：首先判断预测运动矢 量的s a d 值是否小于阈值5 1 2 ，如果是则认为当前宏块的运动矢量即为该预测运 动矢量；否则，采用一个3 x 3 的方形模板，确定运动矢量的大致方位，再通过比 较该方位上的三个参考点的s a d 值，进一步确定运动矢量方向，快速定位到运动 矢量点附近。实验结果证明，该算法比其他目前被广泛使用的搜索算法更快速有 效。 关键词：视频编码，块匹配算法，运动估计，线性搜索 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t n o w a d a y s ，w i t ht h er a p i dd e v e l o p m e n to fi n t e r a c ta n dm u l t i m e d i at e c h n o l o g y , d 硒t a lv i d e ob a s e do nv i d e o c o d i n gh a sb e c o m em o r ep o p u l a r m o t i o ne s t i m a t i o n w h i c hp l a y sa ni m p o r t a n tp a r ti nv i d e o - c o d i n gc a nr e d u c et h er e d u n d a n c i e sa m o n g v i d e of l a m e sa n dm a k em o r ee f f e c t i v ei nc o d i n g h o wt of i n da ne f f e c t i v ea l g o r i t h mo f m o t i o ne s t i m a t i o ni so n eo ft h em o s t p o p u l a rt o p i c s i nv i d e o - c o d i n ga r e a b l o c k - m a t c h i n ga l g o r i t h mi ss i m p l ya n de a s i l yc a r r i e do u tb ys o f t w a r ea n dh a r d w a r e , a n di sw i d e l yu s e di nm p e g - 1 2 4a n dh 2 6 x m o t i o ne s t i m a t i o nt a k e st o om u c ht i m ei nv i d e o c o d i n g i no r d e rt or e d u c et h e c o m p u t a t i o n a lc o m p l e x i t ya n di m p r o v et h ea c c u r a c yo fm o t i o ne s t i m a t i o n , w ep r e s e n t an e wb l o c k - m a t c h i n ga l g o r i t h mc a l l e dl i n e a rs e a r c ha l g o r i t h mi nt h i sp a p e r f i r s t ，w e c h e c kt h es a do ft h ep r e d i c t e dm o t i o nv e c t o r i fi ti ss m a l l e rt h a n512 ，t h ep r e d i c t e d m o t i o nv e c t o rc a nb ec o n s i d e r e da st h em o t i o nv e c t o ro fc u r r e n tb l o c k o t h e r w i s e ，a s q u a r es e a r c ht e m p l a t ec o m p o s e do f3 * 3c h e c k i n gp o i n t si su s e dt of i n dt h ed i r e c t i o n o fm o f i o nv e c t o r w ec a np r o m o t et h ep r e c i s i o no ft h em o t i o nv e c t o rb y c h e c k i n gs a d o fo t h e r3p o i n t si nt h i sd i r e c t i o n ，a n df i n a l l yg ot ot h ep o s i t i o nw i mt h es m a l l e s tm e a n b l o c kd i s t o r t i o nr a p i d l y e x p e r i m e n t a lr e s u l t sf i n a l l ys h o wt h a tt h ep r o p o s e da l g o r i t h m i ss u p e r i o rt oo t h e rw i d e l yu s e da l g o r i t h m si nb o t hp e r f o r m a n c ea n dc o m p u t a t i o n a l c o m p l e x i t y k e y w o r d s ：v i d e oc o d i n g ，b l o c k - m a t c h i n ga l g o r i t h m ，m o t i o ne s t i m a t i o n ，l i n e a r s e a r c h 浙江大学硕士学位论文图目录 图目录 图2 1 二维预测编码器编码端4 图2 2 二维预测编码器解码端4 图2 3 预测点位置5 图2 4 运动矢量相关性9 图2 5 运动矢量空间分布图一1 l 图2 6 图像宏块的删d 分布图1 2 图3 1h 2 6 4 编码过程1 4 图3 2 宏块分割方式15 图3 3 残差帧1 6 图3 4 亮度半像素位置内插1 7 图3 5 亮度1 4 像素内插1 8 图3 6 不用去方块滤波的h 2 6 4 编解码器的效果1 9 图3 7 用去方块滤波的h 2 6 4 编解码器的效果一2 0 图3 84 x 4 z i g z a g 扫描2 1 图4 1 预测运动矢量2 3 图4 2 日( ) 变化统计图一2 9 图4 3m ( ) 变化统计图3 1 图5 1 钻石搜索法3 5 图5 2 六边形搜索模板3 6 图5 3u m h e x a g o n s 搜索步骤3 8 图5 4 运动矢量分布区域一4 0 图5 5l s 搜索法。4 2 图6 1a k i y o 序列平均每块搜索点数4 4 图6 2f o r e m a n 序列平均每块搜索点数4 4 图6 3m o b i l e 序列平均每块搜索点数4 5 图6 4 不同算法的f o r e m a n 序列帧比较。4 8 i i i 浙江大学硕士学位论文 表目录 表目录 表2 1 搜索窗为士7 时运动矢量平均分布概率1 0 表4 1 小运动序列运动矢量统计。2 5 表4 2 小运动序列运动矢量比较2 6 表4 3 中等运动序列和大运动序列运动矢量统计2 7 表4 4 中等运动序列和大运动序列运动矢量比较一2 8 表4 5 日( ) 的分布统计表。2 9 表4 6m f ) 的分布统计表3 0 表6 1 几种运动估计算法每块平均搜索点数比较4 5 表6 2 几种运动估计算法的p s n r 比较4 6 表6 3 几种运动估计算法的平均p s n r 比较4 6 表6 4 几种运动估计算法生成的码流大小比较4 7 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝鎏盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名： 箍屈 签字日期： 汩参年乡月乡日 学位论文版权使用授权书 本学位论文作者完全了解逝姿盘堂有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权迸婆盘堂可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 孑蝴 导师签名： 签字日期：冲8 年多月易日 签字日期：年月日 浙江大学硕士学位论文 第l 章绪论 第1 章绪论 1 1 课题背景 在视频编码过程中，通过减少相邻帧时域的相关性可以大大提高编码效率。 基于块匹配的运动估计通过在相关参考帧中搜索当前编码宏块的最佳匹配宏块， 并且对两个宏块的残差( 即残余信息) 进行编码，消除了相邻视频帧之间的时域 冗余，简单并且高效地实现了运动补偿，已经被许多视频编码标准采纳。 h 2 6 4 a v c 是由国际电信联盟( i n t c m a t i o n a lt e l e c o m m u n i c a t i o n s u n i o n t e l e c o m m u n i c a t i o ns t a n d a r d i z a t i o ns e c t o r ，即i t u t ) 的视频编码专家组 ( v i d e oc o d i n ge x p e r t sg r o u p ，即v c e g ) 和国际标准化组织( i n t e r n a t i o n a l s t a n d a r d so r g a n i z a t i o n ，即i s o ) 的活动图像专家组( m o t i o np i c t u r ee x p e r t sg r o u p ， 即m p e g ) 联合最新制定的新一代视频编码标准。相比以往各种视频编码标准， 它同样采用了基于块的运动补偿混合变换结构，但它不仅增强了运动估计的搜索 精度，增大了搜索范围，还使用多种宏块分割模式并支持多个参考帧进行运动估 计，在同样视频质量的条件下，可比h 2 6 3 节约5 0 的码率，但所有这些特性都 极大地增加了它的计算复杂度。所以，提高h 2 6 4 的编码效率显得至关重要。 随着运动估计算法研究的不断深入，通过设计不同的搜索策略、使用不同的 搜索模板，人们相继提出了全搜索( f u l ls e a r c h ，即f s ) 、二维对数法【1 1 ( t w o d i m e n s i o n a ll o g a r i t h m i c ，即t d l ) 、交叉法【2 1 ( c r o s ss e a r c ha l g o r i t h m ， 即c s a ) 、三步法【3 1 ( t h r e es t e ps e a r c h ，即t s s ) 、四步法【4 】( f o u rs t e ps e a r c h ， 即f s s ) 、基于块的梯度下降法【5 】( b l o c k - b a s e dg r a d i e n td e s c e n ts e a r c h ，即 b b g d s ) 、钻石搜索法【6 ( d i a m o n ds e a r c h ，即d s ) 、六边形搜索法【7 ( h e x a g o n b a s e d s e a r c h ，即h e x b s ) 和非对称十字型多层次六边形搜索算法i s l ( u n s y m m e t r i c a l c r o s sm u l t i h e x a g o ns e a r c h ，即u m h e x a g o n s ) 等快速搜索算法。 但即使采用目前最快的运动估计算法，运动估计所需计算量仍然占h 2 6 4 整个编 码过程的4 0 以上。 浙江大学硕士学位论文第1 章绪论 1 2 研究目标 本文的研究目标是在已有的各种块匹配算法的基础上，结合视频序列的各种 特性，以降低搜索复杂度为优化目标，针对h 2 6 4 的编码过程，展开一系列技术 研究，提出有效的运动估计算法，并通过实验分析和评价该算法的性能。 1 3 本文组织结构 根据上述研究内容和研究目标，文章其余部分内容组织如下： 第二章介绍了视频编码的基本原理，简要说明了预测编码、变换编码、熵编 码等技术。另外还介绍了视频序列的各种特性以及这些特性对设计运动估计算法 的参考作用。 第三章介绍了h 2 6 4 的编码过程，详细地介绍了帧间预测的过程，并介绍了 h 2 6 4 的技术特点。 第四章通过实验数据分析了预测运动矢量准确率的分布规律，并在此基础上 找到一个可以用于运动估计提前终止的预测运动矢量的黝d 阈值范围。 第五章详细地介绍和分析了现有的各种高效的块匹配算法，提出了一种针对 h 2 6 4 的基于线形搜索的块匹配算法。 第六章介绍了实验过程，通过实验数据证明了本文提出的算法的优越性。 第七章回顾了本文的主要研究内容，总结了本文的主要贡献以及创新点，并 指出下一步可进行研究的内容。 1 4 本章小结 本章介绍了基于块匹配的运动估计算法的研究现状和本文的研究目标。另 外，本章还列出了本文的组织结构。 2 浙江大学硕士学位论文 第2 章视频压缩编码的基本原理 第2 章视频压缩编码的基本原理 2 1 引言 数字视频为人们展示了一幅广阔的应用前景，但是在存储方面，数字化后的 视频信号数据的数据量非常巨大，需要大量的磁盘空间进行存储；在传输方面， 目前的传输介质中的数据传输速度远远低于活动视频正常播放所需的存取速度， 直接传输数字视频信号数据时会有大量的数据被丢失。因此，需要一种能在尽量 不影响图像画质的前提下大量减少数字视频数据量的视频压缩技术。随着时代的 进步和社会的发展，近1 0 年来，计算机视频压缩技术的发展突飞猛进，产生了 很多实用的数字视频数据压缩技术。 2 2 预测编码 2 2 1 基本概念 预测法是最简单和实用的视频压缩编码方法，通过压缩编码后实际传输的并 不是像素本身的取样幅值，而是该取样的预测值和实际值之差。大量统计实验表 明：空间上，同一幅图像的邻近像素之间有着相关性，邻近像素之间发生突变的 概率很小；时间上，相邻图像中同一位置的像素之间也有较强的相关性。人们可 以利用这些性质进行视频压缩编码。 2 2 2 帧内预测 二维预测编码器框架如图2 1 和图2 2 所示： 3 浙江大学硕士学位论文第2 章视频压缩编码的基本原理 删旭- i 劁圈甲叵 i 讹力硷+ 臃u 罗量 o 预测器y 埔 l二，。一 图2 1 二维预测编码器编码端 圈篓冬 f l ( x , y ) 氘嘉l 预测器| - 丫 ；厂一 图2 2 二维预测编码器解码端 预测运动矢量的计算见公式( 2 1 ) ，其中f ( x ，y ) 为当前像素值，( x , y ) 为其所 在水平和垂直位置的x ，1 ，坐标值。 夕( z ，j ，) = a k f ( x - k ，y - 1 ) ( 2 1 ) ( i ，i ) e z 吼，为二维预测系数，z 为预测区域，( 后，) 分别为对当前点进行预测的像素 的水平和垂直位置坐标值。为了利用数字电路实现预测，往往用l 2 、1 4 、l 8 、 1 1 1 6 之类的分数表示预测系数。因此提出了以下预测值，见公式( 2 2 ) ： 夕( 毛少) = 三厂( 石一1 ，少) + 言厂( x - l , y - 1 ) + l f ( x , y - 1 ) + 言厂( x + 1 , y - 1 ) ( 2 2 ) 其中各预测点的位置如图2 3 所示： 4 浙江大学硕士学位论文 第2 章视频压缩编码的基本原理 2 2 3 帧间预测 f f x - l , y - of ( x , y - 1 )f ( x + l , y - 1 ) f ( x - l , y )俐绺+ l y ) 图2 3 预测点位置 对于视频图像，由于相邻帧的时间间隔非常短( 一般为1 2 5 1 3 0 秒) ，因此 在运动不是非常剧烈的情况下，相邻帧之间的相关性很强，也就是相邻的两幅图 像中存在很多相似部分。如果编码时能够充分利用图像序列在时域上的相关性进 行压缩编码，就可能获得比较高的压缩比，这就是帧间预测编码。例如，可以将 前一帧相同空间位置处的像素值作为当前编码帧该位置像素的预测值，这种预测 对图像中的静止背景部分十分有效，但这种不考虑物体运动的简单的帧间预测效 果并不理想。如果存在一种办法，使得在对当前帧某像素或像素块进行预测时知 道这个像素或像素块是从前一帧哪个位置移动过来的，则在做预测时以真实对应 位置上的像素值作为预测值，这样预测的准确性将大大提高，这就是运动补偿帧 间预测技术。采用运动补偿帧间预测技术，可以更有效地减少图像序列的时域上 的冗余度，大大降低了预测差值的方差，从而降低误码率并提高压缩比， 2 2 4 运动估计 活动图像邻近帧中的背景或运动物体存在着一定的相关性，因此，在帧间预 测编码中，可将活动图像分成若干宏块( m a c r o b l o c k ，即m b ) ，设法搜索出每 个宏块在邻近帧图像中的位置，得出两者之间的空间位置的相对偏移量。这个偏 移量就是通常所说的运动矢量( m o t i o nv e c t o r ，即m v ) ，这种得到运动矢量的过 程被称为运动估计。通过运动估计可以去除帧间冗余度，使得视频传输的比特数 5 浙江大学硕士学位论文第2 章视频压缩编码的基本原理 大为减少，因此，运动估计是视频压缩处理系统中的一个非常重要的组成部分。 运动矢量和经过运动匹配后得到的预测误差共同被发送到了解码端，解码端 按照运动矢量指明的位置，从已经解码的邻近参考帧图像中找到相应的宏块，与 预测误差相加后就得到了宏块在当前帧中的像素数据。 在成像的场景中，一般有多个物体在作不同的运动，如果直接按照不同类型 的运动将图像分割成复杂的区域是十分困难的。最直接方法是给每个像素都指定 运动矢量，这就是基于像素表示法。这种表示法对任何类型图像都适用，但是它 需要估计大量的未知量，并且它的解时常在物理上是不正确，除非在估计过程中 施加适当的物理约束，而这在具体实现时是不可能的。因此，我们通常不采用基 于像素的物体运动表示法。 一般对于包含多个运动物体的图像，实际中普遍采用的方法是把一个图像帧 划分成多个块，每个区域中的运动可以很好地用一个参数化模型来表征，这被称 为块匹配法，即将图像分成若干个，l ，l 块( 典型值：1 6 x 1 6 宏块) ，为每一块寻找 一个运动矢量，并进行运动补偿预测编码。 每一个帧间宏块都是根据先前已编码的数据预测出来的，根据已编码的宏块 的预测的值和当前宏块作差值，该差值被压缩传送给解码器，与解码器所需要的 其他信息( 运动矢量、预测模型等) 一起用来实现解码过程。每个分割区域都有 其对应的运动矢量，并必须对运动矢量以及块的选择方式进行编码和传输。在细 节比较多的帧中如果选择较大的块尺寸，意味着用于表明运动矢量和分割区域类 型的比特数会少些，但是运动补偿残差值数据在压缩后要多一些；如果选择小一 点的块尺寸，那么运动补偿残差值数据在压缩后要少一些，但是表明运动矢量和 分割区域类型所需比特数要比较多。因此必须要权衡块尺寸选择上对压缩效果的 影响，一般对于细节比较少、比较平坦的区域选择块尺寸大一些，对于图像中细 节比较多的区域选择块尺寸小一些。 具体的块匹配算法将在本文第五章进行详细阐述。 6 浙江大学硕士学位论文第2 章视频压缩编码的基本原理 2 3 变换编码 绝大多数图像都有一个共同的特征：细节区域和内容突变区域则占小部分， 而平坦区域和内容缓慢变化区域占据一幅图像的大部分，即图像中高频区占小部 分，直流和低频区占大部分。 因此，空间域的图像变换到频域，会产生相关性很小的一些变换系数，可对 其进行压缩编码，即变换编码。有一类变换叫做正交变换，可用于图像压缩编码。 自从1 9 6 8 年利用快速傅立叶变换( f a s tf o u r i e rt r a n s f o r m ，即f f t ) 进行图像编 码以来，出现了多种正交变换编码的方法，如k - l 变换( k a r h u n e n - l o e v e t r a n s f o r m ) 、离散余弦变换( d i s c r e t ec o s i n et r a n s f o r m ，即d c t ) 等等。其中， 编码性能以k - l 变换最为理想，但它缺乏快速算法，并且变换矩阵与图像相关， 不同图像需计算不同的变换矩阵，因而k - l 变换只用来参考比较。d c t 编码性能 略次于k - l 变换，但它具有快速算法、变换矩阵与图像无关等特点，己被广泛应 用于图像编码。 2 4 熵编码 熵编码是无损压缩的编码方法，它是建立在随机过程的统计特性基础上的， 可以经过编码和解码无失真地恢复出原始数据。 设信息源x 可发出的消息符号集合为a = a ili = l ，2 ，m ，并设x 发出符号 q 的概率为p ( a t ) ，则定义符号哆出现的自信息量为公式( 2 3 ) - ，( q ) = 一l 0 9 2p ( q ) ( 2 3 ) 如果瞑的出现是独立的，则x 发出符号序列的概率等干各符号的概率之积， 该序列出现的信息量等于相继出现的各符号的自信息量之和。这类信源称为无记 忆信源。 对信息源x 的各符号的自信息量取统计平均，可得平均信息量，见公式( 2 4 ) ： 日( x ) = 一p ( a i ) l 0 9 2p ( q ) 1 - 1 7 ( 2 4 ) 浙江大学硕士学位论文第2 章视频压缩编码的基本原理 称日( x ) 为信息源x 的熵( 咖y ) ，单位为b i f f 符号，通常也称为x 的一阶 熵。由信息论的基本概念可以知道，一阶熵是无记忆信息源( 在无失真编码时) 所需数码率的下界。 熵的大小与信源的概率模型有着密切的关系，各个符号出现的概率不同，信 源的熵也不同。当信源中各事件是等概率分布时，熵具有极大值。信源的熵与其 可能达到的最大值之间的差值反映了该信源所含有的冗余度。信源的冗余度越 小，每个符号所独立携带的信息量越大，传送相同的信息量所需要的序列长度越 短，符号位越少。因此，数据压缩的一个基本的途径是去除信源的符号之间的相 关性，尽可能地使序列成为无记忆的，即前一符号的出现不影响以后任何一个符 号出现的概率。 视频编码采用的熵编码常用的有两种：变长编码，也称哈夫曼编码及算术编 码。1 9 5 2 年，哈夫曼提出变长编码方法：对出现概率大的符号分配短字长的二进 制码，对出现概率小的符号分配长字长二进制码，得到符号平均码长最短的码。 变长编码也称最佳编码。理论上，这种编码是最佳的。实际上，利用硬件实现时， 出现概率不可能精确到小数后多少位，而最小存储单元为1 b i t ，会引起概率匹配 不准确及编码效率的下降。算术编码和哈夫曼编码不同，它采用一个浮点数来代 替一串输入符号，经算术编码后输出一个小于1 ，大于或等于0 的浮点数，在解 码端被正确地唯一的解码，恢复原符号序列。 2 5 视频序列的基本性质 数字视频序列在空间、时间、翩d 分布上存在各种特性。可以利用这些性质， 来分析各种运动估计算法的优缺点，并设计更快速、准确、高效的运动估计算法。 2 5 1 序列相关性 相关性是指同一帧图像内的不同部分之间以及相邻帧图像之间像素或宏块 运动的相似性。 大量的统计数据表明，运动物体图像具有空间上和时间上的连续性，同一帧 浙江大学硕士学位论文第2 章视频压缩编码的基本原理 内相邻的像素或宏块具有相同或近似的运动速度和方向，因此同一帧中相邻宏块 之间的运动具有空间相关性；另一方面，运动物体在多个连续帧之间能保持相同 的或近似的运动速度和方向，因而相邻帧之间对应像素或宏块的运动矢量具有时 间相关性【9 】。视频压缩正是利用了视频序列的这种时问和空间上的相关性。 图2 4 显示了p a r i s 视频序列第7 、8 帧的图像和宏块运动矢量( 通过s t r e a m e y e 软件分析) ，可以明显的看出，两幅图像的运动矢量非常相似。同时，对于同一 帧图像来说，女人的手腕部、头部各个宏块的运动矢量也非常接近。 图2 4 运动矢量相关性 9 浙江大学硕士学位论文第2 章视频压缩编码的基本原理 2 5 2 运动规范性 统计实验表明，运动矢量图像的频谱大多呈十字形分布，它分布在水平方向 和竖直方向上的概率比分布在相同距离其他方向上的概率大的多，并且水平方向 的运动矢量往往多于竖直方向的运动矢量【l o l 。文献 1 0 】对1 8 个标准视频序列进行 了统计，其运动矢量的平均概率分布见表2 1 横向为水平方向运动位移的绝对值， 纵向为竖直方向运动位移的绝对值。由表2 1 可知，运动矢量为( o ，0 ) 的概率为 5 8 0 5 ，运动矢量在水平和竖直方向的概率分别为2 2 6 9 和7 4 3 。因此，在运 动估计中，可以利用这个性质尽量把搜索点设置到搜索原点的水平方向和竖直方 向上，加快搜索速度。 表2 1 搜索窗为士7 时运动矢量平均分布概率 ，x 01234567 o0 5 8 0 5o 1 2 8 00 0 5 9 1o 0 1 7 00 0 0 7 20 0 0 5 40 0 0 2 60 0 0 7 6 10 0 5 7 20 0 2 4 20 0 0 9 20 0 0 5 l0 0 0 4 10 0 0 2 90 0 0 2 00 0 0 4 9 20 0 0 6 7 0 0 0 6 20 0 0 3 40 0 0 3 10 0 0 1 70 0 0 1 1 0 0 0 1 00 0 0 2 7 30 0 0 3 10 0 0 2 90 0 0 1 90 0 0 2 20 0 0 1 20 0 0 0 90 0 0 0 80 0 0 2 1 40 0 0 2 20 0 0 1 80 0 0 1 40 0 0 1 20 0 0 1 00 0 0 0 60 0 0 0 70 0 0 1 8 50 0 0 1 20 0 0 1 60 0 0 0 90 0 0 1 10 0 0 0 70 0 0 0 50 0 0 0 6 0 0 0 1 8 60 0 0 2 40 0 0 1 20 0 0 0 80 0 0 0 90 0 0 1 00 0 0 0 5 0 0 0 0 70 0 0 1 6 70 0 0 1 50 0 0 1 40 0 0 1 00 0 0 1 60 0 0 1 20 0 0 1 10 0 0 1 20 0 0 5 2 2 5 3 中心偏置性 运动矢量具有中心偏置性，即运动矢量的概率分布是以( 0 ，0 ) 点为中心向四 周递减的，视频序列中前后帧的运动是缓慢的，最佳匹配点分布在搜索起始点附 近。 通过对标准视频序列运动矢量的统计研究发现，8 0 以上的运动矢量集中在 l o 浙江大学硕士学位论文第2 章视频压缩编码的基本原理 以( 0 ，0 ) 点为中心，边长为5 的正方形范围内。图2 5 显示了f o r e m a n 序列前2 0 帧在搜索半径为7 的条件下的运动矢量分布情况( 百分比) ，可以清楚地看出其 运动矢量分布的中心偏置特性。合理地设置搜索点有利于提高搜索的速度和精 度，因此设计搜索模板时应该充分考虑运动矢量分布的这种中心偏移特性。 图2 5 运动矢量空间分布图 2 5 4s a d 分布呈空间方向性 通常情况下s a d 曲面总是沿着某一个梯度下降方向趋向极小点【l l 】，所以搜索 策略应该体现梯度下降的基本思想。图2 6 是f o r e m a n 序列中第二帧某宏块在 一7 ，+ 7 】范围内的s a d 分布图，可以看出s a d 曲面具有明显的方向性，最小s a d 值 在( 0 ，0 ) 点，附近的s a d 值都基本沿着某一个固定方向趋向于最小s a d 值所在位 詈。 浙江大学硕士学位论文第2 章视频压缩编码的基本原理 2 5 5 误差多峰性 图2 6 图像宏块的s 分布图 在大多数情况下，误差曲面含有一个或多个局部极小点。因此运动估计的搜 索模板不能太小，否则会找到最近的局部极小点。 2 6 本章小结 本章从帧内预测、帧间预测、运动估计、变换编码和熵编码等方面介绍了视 频压缩编码相关的基本技术，同时介绍了视频序列的各种特性以及这些特性对运 动估计算法设计的参考价值。 1 2 浙江大学硕士学位论文第3 章h 2 6 4 编码过程综述 第3 章h 2 6 4 编码过程综述 3 1 引言 h 2 6 4 标准是m t ( i t u tf o ri t ut e l e c o m m u n i c a t i o ns t a n d a r d i z a t i o ns e c t o r ) 的视频编码专家组( v i d e oc o d i n ge x p e r t sg r o u p ，即v c e g ) 和i s o i e c 的活动 图像专家组( m o v i n g p i c t u r ee x p e r tg r o u p ，即m p e g ) 的联合视频组( j o i n tv i d e o t e a m ，即j v t ) 开发的标准，也称为m p e g 4p a r t1 0 。在相同的重建图像质量下， h 2 6 4 比h 2 6 3 节约大约5 0 的码率，比m p e g - 4 节约大约3 0 的码率。但是h 2 6 4 是以计算复杂度的急剧增加来获得优越性能的。 3 2 框架介绍 h 2 6 4 标准分成三个框架( p r o f i l e ) ：b a s e l i n ep r o f i l e 、m a i np r o f i l e 及e x t e n d e d p r o f i l e ，代表了针对不同应用的技术限定和算法集。 基本层次( b a s e l i n ep r o f i l e ) ：该层次使用了i 片和p 片支持帧内和帧间编码， 熵编码采用基于上下文自适应的可变长编码( c a 、l r l c ) 。该层次主要使用于低时 延的实时应用场合。 主要层次( m a i np r o f i l e ) ：支持隔行视频，使用b 片的帧间编码和加权预测 的帧内编码，熵编码采用基于上下文的自适应二进制算术熵编码( c a b a c ) 。它 主要针对于压缩率和质量要求较高，但对时延要求不高的场合。 扩展层次( e x t e n d e dp r o f i l e ) ：使用了s p 和s i 片支持码流之间有效的切换， 它不仅支持b a s e l i n ep r o f i l e 的所有特性，还支持数据分割，但不支持c a b a c 和 隔行视频。该层次主要针对的时各种网络视频流传输方面的应用。 3 3 编码过程 h 2 6 4 标准并不明确地规定一个编解码器如何实现，而是规定了一个编了码 的视频比特流的句法和该比特流的解码方法。 h 2 6 4 编码器的功能组成见图3 1 ： 浙江大学硕士学位论文第3 章h 2 6 4 编码过程综述 固圈- ! ：心! 日 圈 x 图3 1h 2 6 4 编码过程 厘丑围n a t - ， 由图3 1 可见，编码器以宏块为单位处理输入的帧或场e 。首先进行帧内或 帧间预测编码，如果采用帧间预测编码，其预测值p 是由前面已编码的参考图像 联，经运动补偿后得出。为了提高预测精度，从而提高压缩比，实际的参考图像 可在过去已经解码重建和滤波的帧中进行选择。 预测值p 和当前块相减后，产生一个残差块破，经过d c t 变换、量化以后 产生一组变换系数石，再经z 型扫描、熵编码，加上预测模式量化参数、运动矢 量等信息一起组成了一个压缩后的码流。 为了保证编码端预测用的参考图像与解码器解码时的参考图像一致，编码器 必须有重建图像的功能。因此必须使x 经反量化、反变换后得到的碰与预测值尸 相加，得到未经滤波的帧u f ；。编码解码环路中会产生的不确定的噪声，为了提 高参考帧的图像质量，h 2 6 4 设置了一个环路滤波器，滤波后的输出f 即为可用 作参考图像的重建图像。 因此，h 2 6 4 编码主要有以下几个步骤：帧内预测、帧间预测、变换和反 变换) 、量化( 和反量化) 、环路滤波、熵编码。 1 4 浙江大学硕士学位论文第3 章h 2 6 4 编码过程综述 3 3 1 帧内预测 帧内预测模式中，预测块p 是基于已编码重建块和当前块形成的。对亮度像 素而言，p 块用于4 x 4 子块或者1 6 x 1 6 宏块的相关操作。4 x 4 亮度子块适用于带 有大量细节的图像编码，它有9 种可选预测模式，独立预测每一个4 x 4 亮度子块； 1 6 x 1 6 亮度块适用于平坦区域图像编码，有4 种预测模式；色度块也有4 种类似 于1 6 x 1 6 亮度块的预测模式。编码器通常先分别进行1 6 x 1 6 和4 x 4 预测，然后选 择使p 块和编码块之间差异最小的预测模式。 3 3 2 帧间预测 h 2 6 4 帧间预测支持1 6 x 1 6 、1 6 x 8 、8 x 1 6 、8 x 8 、8 x 4 、4 x a m 4 x 4 一共 7 种块尺寸；支持整像素、半像素、1 4 像素多种精度的运动矢量；最多支持1 6 个参考帧。 如图3 2 所示，每个宏块( 1 6 x 1 6 像素) 可以存在4 种分割方式：一个1 6 x 1 6 、 两个1 6 x 8 、两个8 x 1 6 、四个8 x 8 。其运动补偿也相应有四种。而8 x 8 模式的每 个子宏块还可以四种方式分割：一个8 x 8 、两个4 x 8 、两个8 x 4 、4 个4 x 4 。这 些分割和子宏块的设计大大提高了各宏块之间的关联性。这种分割下的运动补偿 则称为树状结构运动补偿。 16 x 16 ( t y p e1 ) 16 x 8 ( t y p e2 ) 8 x 16 ( t y p e3 ) 8 x 8 ( t y p e4 ) 1 6 x 1 6 t y p e s 8 x 8 t y p e s 8 x 8 8 x 4 ( t y p e5 ) 4 x 8 ( t y p e6 ) 4 x 4 ( t y p e7 ) 图3 2 宏块分割方式 1 5 浙江大学硕士学位论文第3 章h 2 6 4 编码过程综述 所有的宏块或子宏块都需进行独立的运动补偿。每个宏块或子宏块的运动矢 量、分割模式的选择也都会被编码到压缩比特流中。因此，分割尺寸的选择是否 合理会对压缩性能产生影响。一般说来，大的分割尺寸适合平坦区域，小尺寸适 合多细节区域。宏块的色度块( c 和c ) 采用和亮度块一样的分割模式，只是 尺寸减半。色度块的运动矢量也是通过相应的亮度块运动矢量的水平和垂直分量 减半而得。 图3 3 显示了一个残差帧( 没有进行运动补偿) 。h 2 6 4 编码器为帧的每个宏 块都选择了最佳分割尺寸，使传输的信息量最小。在多运动区域，选择有效的小 尺寸；在平坦的区域，选择1 6 x 1 6 分割。 麓一蟹黧糍黼曩一圈 曩曩曩 麟 曩雕 藕黧 糜圈纛鬻麟 薯 圈一 麟慝 瓣 蕊 麟 黧震圈蠢缀滋 麓 瓣 熏 豳 缀缀 圈 麟 熬缀滤瓣戮滋麟 曩一纛粪黼葳黼瓣纛熏一麟黼霹缫瞩 一黧麓黼鬣 黼 曩 鬻藏 l 一麟麟一 缀缀 麟溺戮燃隧 曩曩 縻缓戮隧藤戳缓瑷! 翻豳燃 缀 猢隧篱缀溺 震貉甏羹 缓糍猁麟 雾鬈；。 瓣熏 缀隧 滋缀缀缓黝鬻灞燃蘸隧露翳蔫叠 麓嚣j ：巍鳓鳜荔委荔黼黝鼢肇蕊露：毒纛 。鬻豸鬈篓澄 黧瓣熏戮瓣缓灞 辫鹫辫i+ 鬻缓缓麟糕黼 隧 潺黪o 秒4 囊黧震阂 藿麓黧缀鬻一渤纛 鬃黛蘸 图3 3 残差帧 在h 2 6 4 的帧间编码中，宏块或者子宏块都是从参考图像中某一相同尺寸的 1 6 浙江大学硕士学位论文第3 章h 2 6 4 编码过程综述 区域预测而得。对亮度成分采用1 4 像素精度，而色度采用1 8 像素精度。可以 通过邻近已编码点进行内插获取该1 4 像素位置的像素值。图3 4 中，当前帧的 4 x 4 块通过邻近参考图像相应区域预测。如果运动矢量的垂直和水平分量为整 数，参考块相应像素实际存在。如果其中一个或两个为分数，则预测像素通过参 考帧中相应像素内插获得。 田田囚誊固圈口 口圈圈i 蕉固田图 田田 口团因蟹圈口田 口口田霉回圈因 图3 4 亮度半像素位置内插 首先计算半像素点。半像素点( 如b ，h ，m ，j ) 通过使用权重为( 1 3 2 ， 5 3 2 ，5 8 ，5 8 ，5 3 2 ，1 3 2 ) 6 抽头滤波器得出。- s 计算见公式( 3 1 ) ： s = r o u n d ( ( k 一5 三+ 2 0 m + 2 0 一5 p + q ) 3 2 )( 3 1 ) 类似的，m 由口、d 、日、s 、u 滤波得出。一旦邻近( 垂直或水平 方向) 整像素点的所有像素都计算出，剩余的半像素点便可以通过对6 个垂直或 水平方向的半像素点滤波而得。如图3 6 所示，歹由a a ，b b ，b ，s ，g g ，h h 滤 波得出。 1 7 ；i ；| 因_ 圈团删一团 |d扣foj!田_ 嗡团困固团哆固 浙江大学硕士学位论文第3 章h 2 6 4 编码过程综述 半像素点计算出来以后，1 4 像素点就可通过线性内插得出，如图3 5 所示。 网醚童兰叫i 司 匝蠢慝亘窭 回重圆 圈 a | | h ：| 齐 困 图3 5 亮度1 4 像素内插 1 4 像素点( 如a ，c ，i ，k ，d ，f ，n ，g ) 由邻近像素内插而得，见公 式( 3 2 ) ： c = r o u n d ( ( h + 6 ) 2 )( 3 2 ) 剩余1 4 像素点( 如e ，g ，p ，) 由一对对角半像素点线性内插得出。相 应地，色度像素需要1 8 精度的m v ，也同样通过整像素地线性内插得出。 3 3 3d c t 变换 对于实数的d c t 变换，由于在解码端的浮点运算精度问题，会造成解码后 的数据的失配。为此，h 2 6 4 对4 x 4 d c t 进行了改造，采用整数d c t 技术，有 效地减少计算量，同时不损失图像准确度。 3 3 4 量化 h 2 6 4 采用标量量化技术。普通标量量化器的原理见公式( 3 3 ) ： f q = ，d 姗j ( 壶) ( 3 3 ) 其中，y 为输入样本点编码，q p 为量化步长，f q 为y 的量化值，r o u n d ( ) 为 取整函数。反量化的原理见公式( 3 4 ) ： y = f q x9 p( 3 4 ) 在量化和反量化的过程中，量化步长q p 决定量化器的编码压缩率和图像精 浙江大学硕士学位论文第3 章h 2 6 4 编码过程综述 度。q p 越大，量化值f q 动态范围越小，相应的编码长度越小，反量化时会损失 更多的图像细节信息。在h 2 6 4 中，量化步长q p 共有5 2 个值。0 代表最精细的 量化，5 1 代表最粗