（电路与系统专业论文）视频压缩中运动估计算法的研究(1).pdf

# ”，- l 妒硕士论文视频压缩中运动估计算法的研究 摘要 随着近年来多媒体技术的飞速发展，许多应用领域对视频图像的实时压缩提 出了更高的要求，快速、高效的压缩算法是解决这一问题的关键。 运动估计是实现帧间视频压缩的关键，快速运动估计算法一直是视频压缩中 的研究热点。本文在对一些常见的运动估计算法进行分析后，针对一些快速估计 算法过早确定了搜索方向，容易陷入局部最小点，损失了搜索精度的情况，从找 出相邻块的运动矢量的相关性出发，从而得到当前块的起点预测方法。在该起点 预测方法的基础上，针对菱形快速估计算法中对小运动块搜索点数过多的问题， 提出了基于中心偏置的自适应的块匹配运动估计快速搜索算法a s 。该算法提出一 种基于小运动块的中心偏置搜索样式和针对大运动块的起点预测搜索策略。实验 结果表明，与单一的d s 算法相比，a s 算法具有更高的搜索速度和精度。由于运 动估计的精度和计算复杂度都和采用的块匹配准则有关，本文在最常用的s a d 准 则上提出了一种基于块特征的匹配准n s c s a d 。s c - s a d 在增加非常少的计算量的 情况下，通过对残差块的平缓程度判断来实现匹配准则，使运动估计算法在 s c s a d 准则下，提高了图像的质量同时，降低了残差块编码的比特数。在运动估 计过程中，在找到最佳匹配块后，可以预先判断残缺块的d c t 系数是否为全零，预 先判断为零的块可以节省d c t 变换和量化的计算量。本文提出一种预先判断全零 d c t 系数的方法，该方法能有效判断出d c t 全零系数块，而使编码过程计算复杂性 降低，能显著地减少视频编码器的运算量。 翌! ：兰堂塑主熊圭 塑塑堡堑堡垫堕盐基垫盟塑f 薹 a b s t r a c t w i t ht h ef a s td e v e l o po fm u l t i m e d i at e c h n i q u e s ，t h e r ea r em a n ya r e a sn e e dm o r e e f f i c i e n tr e a l t i m e c o m p r e s s i o nt e c h n i q u e s f o r d i g i t a li m a g ep r o c e s s i n g f a s t c o m p r e s s i o na l g o r i t h mi st h ek e yf o rt h i sp r o b l e m m o r i o ne s t i m a t i o ni sr a t h e rc o m p l e xi nc o m p u t a t i o na n ds p e n d sm u c ht i m ei n t h ei n t e r - f r a l t l ev i d e oc o m p r e s s i o n f a s tm o t i o ne s t i m a t i o nh a sa l w a y sb e e naf a v o r i t e t ot h er e s e a r c h e r si nt h ef i e l d i nt h i sp a d e r , w ef i r s ta n a l y s es o m ep o p u l a rm o t i o n e s t i m a t i o na l g o r i t h m s s o m eo ft h e md e t e r m i n e 也es e a r c hd i r e c t i o nt o oe a r l y , a n d e a s i l yf a i ii n t ot h el o c a lm i n i m u mp o i n t ，s op r e c i s i o ni sa f f e c t e d t h em o t i o n v e c t o r s o ft h eb l o c k sw i t h i nt h i sg r o u pm u s th a v es o m er e l a t i o n s h i pb e t w e e nt h e m i ft h e r e l a t i o n s h i pb e t w e e n t h em o t i o nv e c t o r so ft h eg r o u do fb l o c k sc a nb ei d e n t i f i e d i ti s t h e np o s s i b l et op r e d i c tt h et a r g e tm o t i o nv e c t o rf r o mt h em o t i o nv e c t o r so ft h eg r o u p o fb l o c k s s ow ec o u l du s et h ep r e d i c t e dm o t i o nv e c t o ra so u r ss t a r t i n gp o i n t b a s e d t h i sm e t h o do fp r e d i c t i n g s t a r t i n gp o i n t ，w ep r o p o s e af a s tm o t i o ne s t i m a t i o n a l g o r i t h mb a s e do nc e n t e rs e a r c ht od e c r e a s et h ec o m p u t a t i o no f t r i v i a lm o t i o ni nd s s e a r c h i n gp a t t e r na d a p t st ot r i v i a lm o t i o na n d t h em e t h o do f p r e d i c t i n gs t a r t i n gp o i n t a d a p t st of u r i o u sm o t i o na r ed e s i g n e dt os a t i s f yr e q u i r e m e n t so nb o t hs p e e da n d a c c u r a c y t h es i r e u l a t i o nr e s u l t ss h o w t h a tt h es e a r c h i n gs p e e da n da c c u r a c yo ft h e a l g o r i t h ma r es u p e r i o rt ot h er e c e n t l yd e v e l o p e de x c e l l e n ta l g o r i t h md s b e c a u s et h e p r e c i s i o na n dc o m p u t a t i o no fm o t i o ne s t i m a t i o na r er e l e v a n t t ob l o c km a t c h i n g c r i t e r i o n s ow ep r e s e n tan e wc r i t e r i o nc a l l e ds c s a dw h i c he n h a n c e st h e c o n v e n t i o n a ls a df u n c t i o nb ya d d i n gas m o o t h n e s sc o n t r 0 1f o rt h er e s i d u eb l o c kw i t h a d d i n gf e wc o m p u t a t i o n s i m u l a t i o nr e s u l t ss h o w t h a tb ya p p l y i n gt h en e wc r i t e r i o n i nm o t i o ne s t i m a t i o n b o t ht h ei m p r o v e m e n ti np r e c i s i o na n dr e d u c t i o ni nb i tr a t ec a n b ea c h i e y e d i nt h ep r o c e s so fm o t i o ne s t i m a t i o n w h e nw e g e tt h ef i n a lm a t c h e d b l o c k w ec a r lp r e d e t e r m i n et h eb l o c k sw h o s eq u a n t i z e dd c tt o e f f i c i e n t sa r e c o m p l e t e l y z e r o i ti s a p p l i e d t oe l i m i n a t er e d u n d a n t c o m p u t a t i o n s o fd c tt r a n s f o i n a n d q u a n t i z a t i o n an e wm e t h o do fp r e d e t e r m i n i n gt h e b l o c k sw h o s eq u a n t i z e dd c t c o e f f i c i e n t sa r ec o m p l e t e l yz e r oi sp r o p o s e di nt h ep a p e r e x p e r i m e n t a lr e s u l t ss h o w 血a tt h ei m p r o v e dm e t h o dc a nd e t e r m i n et h eb l o c k sw h o s eq u a n t i z e dd c tc o e 伍c i e n t s a r ec o m p l e t e l yz e r oe r i e c t i v e l y , a n di ti sv e r yu s e f u lf o rr e d u c i n gt h ec o m p l e x i t ya n d c o m p u t a t i o n i nv i d e oc o d e r 声$ ，z 妒硕士论文视频压缩中运动估计算法的研究 1 i 视频压缩背景 第一章绪论 随着互联网的飞速发展消费类电子、通信、电视、电影、广播和计算机技 术日益紧密结合起来，计算机与通信、多媒体技术融合的趋势不可逆转，使得基 于互联网的多媒体产业成为目前发展最快、规模最大的产业之一。 众所周知，人类通过视觉获取的信息量约占总信息量的7 0 ，而且视频信息 具有直观性、可靠性等一系列优点，所以多媒体技术中一个重要的技术就是视频 技术。 目前视频技术的应用范围很广，如网上视频会议、网上可视电子商务、网上 政务、网上学校、远程医疗、个人网上聊天、可视咨询等业务。 视频技术应用中传输的数据量非常大，从表1 1 1 可知，单纯用扩大存储器 容量、增加数据传输率的办法是不现实的。数据压缩技术是有效的解决方法，通 过数据压缩，同时也可使计算机实时处理音频、视频信息，以保证播放出高质量 的视频、音频节目。可见，多媒体数据压缩是非常必要的。 表i1 i 信源信号的原始数据速率表 i 电话( 2 0 0 3 4 0 0 h z )8 0 0 0 样本数秒1 2 比特样本= 9 6 k b p s l 带宽音频( 2 0 2 0 0 0 h z )4 4 1 0 0 样本数秒1 6 比特样本2 信道= 1 4 1 2 m b p s 图像5 1 2 x 5 1 2 象素图像2 4 比特象素= 6 3 m 比特图像 视频6 4 0 4 8 0 象索图像2 4 比特象素3 0 帧秒= 2 2 1 m b p s 高清晰度电视1 2 8 0 7 2 0 象素图像2 4 比特象素6 0 帧秒= 1 2 g b p s 从信息论观点来看，声音、图像作为一个信源，描述信源的数据是信息量( 信 源熵) 和信息冗余量之和。信息冗余量有许多种，如空间冗余、时间冗余、结构 冗余、知识冗余、视觉冗余等。数据压缩实质上是减少这些冗余量。可见减少冗 余量可以减少数据量而不减少信源的信息量。从数学上讲，声音和图像可以看作 一个多维函数，压缩描述这个函数的数据量的实质是减少其相关性。另外在一些 情况下，允许信源有一定的失真，而并不妨碍它的实际应用，那么数据量压缩的 p _ ? ，z 妒硕士论文视频胝缩中运动估计算法的研究 可能性就更大了。由于多媒体文、声、静止图像、视频动态图像等信源数据有极 强的相关性，也就是说有大量的冗余信息，数据压缩可以将庞大数据量的冗余信 息去除掉，保留相互独立的信息分量。 1 2 视频数据压缩技术 数据压缩技术是现代多媒体技术实现的关键，近几十年来越来越受到人们的 重视。随着多媒体技术的发展，数据压缩得到了广泛、深入的研究，已经形成了 一系列系统化的数据压缩方法。 1 数据压缩方法分类 数据压缩的分类方法有很多种，可以从不同的角度、不同的特征来对数据压 缩进行不同的分类。 从压缩、解压后的数据与原数据相比较是否有失真的角度可以将压缩方法分 为无失真压缩和有失真压缩，见图1 2 1 。 ( 1 ) 无失真压缩 无失真压缩又称为无噪声编码( n o i s e l e s sc o d i n g ) 、冗余度压缩( r e d u n d a n c y r e d u c t i o n ) 、熵编码( e n t r o p yc o d i n g ) 、无损压缩( l o s sl e s sc o m p r e s s i o n ) 等等。 c e s h a n n o n 在创立信息论时，提出把数据看成是信息和冗余度的组合。无失 真压缩的工作原理是去除或减少数据中的冗余，而不损失数据所包含的信息，因 而是一个可逆过程。这类编码方法包括h u f f m a n 编码、游程长度编码、算术编码。 主要用于对数据质量要求较高、不允许产生失真的应用环境，如电报报文编码、 计算机文件压缩等等。 ( 2 ) 有失真压缩 有失真( l o s s ) 压缩又称熵压缩( e n t r o p yc o d i n g ) 、有损压缩( l o s s c o m p r e s s i o n ) 。这种方法允许解压后的数据与原数据相比有一定的失真，以获 取比无失真压缩更高的压缩比。熵压缩主要有两大类型：特征抽取和量化方法， 特征抽取的典型例子如指纹、汉字的模式识别，一旦抽取出足以有效表征与区 分不同模式的特征参数，便可用它取代原始的图像数据，这一类方法一般是用 于特定的环境。量化则是更为通用的熵压缩技术，除了直接对无记忆信源的单 m ；，漕硕士瓷t视频压缩中运动估计算法的研究 个样本做所谓的零记忆量化外，还可以对有记忆信源的多个相关样本映射到不 列的空间，去除了原始数据中午目关性后再做量化处理，由此又引出了预测编码 和变换编码。另外，在特征抽取与量化相结合的基础上，又发展出一类高效的 分析一综合编码技术。 般撼j l t 犏 蔗欺睡妪撼 懈游：嚣l 戈程避求z - 过编制粕w 粕嬲瞎弼懿 椭游鳓 i 供 拳必蕊蔗薅 肇化 磊菡 晤习医拥i 舒鬟笋 戮薯。i 掣i i 囱匡 照辩i 量l _ _ j l 一 化茬鞴矧由习i i r 乙 渣性线适站 l 一。i 翌詈羹嚣鍪麓最蔷麓筹菡嚣 澍铡雾要鬟蠡翁麓。；蒜；嚣鎏 测潮篓麓莲7 菇 溅“量 在实际应用中，一种高效的编码算法往往是综合利用各类编码技术长处的 混合编码方法，即要用到无失真压缩方法又要用到有失真压缩方法。 2 常用的图像压缩方法 常用的图像数据压缩方法可分为三大类：统计编码、变换编码和较新的各种 分析一综合编码方法“1 。第一类属于无失真压缩，后两类属于有失真压缩。 ( 1 ) 统计编码 统计编码是根据信源的统计概率分布特性来编码，以去除冗余，降低平均 码字长度。统计编码包括霍夫曼( h u f f m a n ) 编码、香农( s h a n n o n ) 编码、算术 ； 琦硕士1 k视频烁缩中运动估计算法的研究 ( a r i t h m e t i c ) 编码、游程氏度编码( r l c ) 。 ( 2 ) 变换编码 变换编码是一种在图像处理领域应用非常广泛的编码方法。其发送端的f 变换将原始信号中的各个样值从一个域变换到另外一个域，然后对变换后的系数 进行量化和编码，使得对这些系数编码所需的总比特数少于对原始数据进行编码 所需的总比特数。 映射变换的方法很多，最常用的是f 交变换，如f o u r i e r 变换、离散余弦变 换( d c t ) 、w a l s h h a d a m a r d 变换和k a r h u n e n l o e v e 最佳变换f k l ) 。23 等等。 ( 3 ) 分析一综合编码 分析一综合编码是一类较新的编码方法，又称为第二代编码方法。这些方 法在本质上都是通过对信源的“分析”，将其分解成一系列更易于表示的基元或 从中提取出若干具有更本质意义的参数，编码仅对这些基本单元或特征参数进 行。接收端借助一定的规则或模型，按一定的算法将这些基元或参数再“综合” 成原信源的一个近似。 典型的分析一综合编码方法有子带编码( s u b b a n dc o d i n g ) 、小波变换 ( w a v e l e tt r a n s f o r m ) 编码、分形图像编码( f r a c t a lc o d i n g ) 、模型基图像编码 ( m o d e l b a s e dc o d i n g ) 等等。虽然这些方法在图像压缩领域的应用时间还不长， 而且其中有些方法还不很成熟，但它们已展示出了巨大的压缩潜力，越来越受到 人们的重视。 3 视频压缩标准 随着数字技术的进步，计算机、通信和大众传播技术的不断结合，全球范 围的信息传输与交换越来越来频繁，为了在世界范围内促进数据压缩技术的应 用，学术界和工业界做了大量的工作，这些工作的成果最后促成了国际标准化组 织的若干有效的图像压缩标准。 目前在众多视频编码标准中，影响最大并被广泛应用的标准是m p e f , 和 h 2 6 x 。这两种编码标准都采用基于运动补偿的预测编码技术来消除帧间的时间 冗余，在运动估计的基础上进行运动补偿，然后对残差帧或整帧数据进行d c t 变换和量化来消除帧内的空间冗余，最后通过变长编码后输出。这两种压缩标准 ，目，z 学硕士论文 视频压缩中运动估计算法的研究 的编码框图都如幽1 2 2 所示。 ( 1 ) m p e g 标准 m p e g 是国际标准化组织i s o i e c 下的一个制定动态视频压缩编码标准的组 织，它为视频压缩编码技术的标准化、实用化做出了巨大贡献。如针对c d r o m 的1 5 m b p s 传输率的m p e g p “、针对h d t v 的6 m b p s 以上传输速率的m p e 62 6 6 都已成功地得到应用，并创造了巨大的商业价值。m p e g 一4 ”_ ”是针对视频会议、 可视电话的甚低速率编码标准，它融入了基于内容的检索与编码，可对压缩数据 内容直接访问。正在制定的m p e g 一7 。1 标准被称为“多媒体内容描述接口”，这种 标准化的描述可以加到任何类型的媒体信息上。不管视频信息的表达形式或压缩 形式如何，具有这种标准化描述的多媒体数据均可被检索。因此，m p e g 一7 的应 用领域主要是数字化图书馆和广播式媒体。 ( 2 ) h 2 6 x 标准 。 h 2 6 1 “”编码是一种帧间预测减少时域冗余、变换编码减少空域冗余的混合 编码方法，具有压缩比高、算法复杂度低等优点，得到较为广泛的应用。在h 2 6 1 的基础上，1 9 9 6 年i t u t 推出了h 2 6 3 “”编码标准。h 2 6 3 在许多方面对h 2 6 1 进行了改进和扩充，如在编码算法复杂度增加很少的基础上，h 2 6 3 能提供更好 的图像质量、更低的速率，十分适合于i p 视频会议、可视电话应用。 图 图1 2 2 视频图像的压缩编码框图 p ，- - l 掌硕士论文 视频压缩中运动估计算法的研究 1 3 视频压缩中的主要研究内容 视频图像中存在冗余信息，即相关性。主要的冗余信息有空间冗余信息和时 间冗余信息。空间冗余信息是指在一帧图像中像素之间的相关性。一帧图像中， 相邻或相近的像素，其灰度值或色度分量的值总是很相近，相邻像素之间存在很 强的相关性。而相邻帧之间的时问间隔是由帧率决定的。帧率越大，相邻帧之间 的时间间隔就越小，一般是几十毫秒。在这样短的时间内，大部分被拍摄的对象 都是静止不动或只有很小的移动，因此视频序列中存在时间上的冗余信息。视频 压缩主要就是从时域、空域两方面去除冗余信息。 ( 1 ) 去时域冗余 视频图像是沿时间轴方向的一个帧序列，其帧间图像相关性很强。具体表 现为两帧间很多静止图像其数据是不变的。实现帧间编码的方法是运动估计和运 动补偿。 其原理是利用帧间的时间相关性，减小时间冗余度。帧间编码可以减小冗余 度，这是因为两帧之间有很大的相似性。如果将前后两帧相减f 移动物体作相应 位移) 得到的误差作编码所需比特要比直接进行帧内编码所需的比特少，帧间差 值集中在零附近，可以用短的码字传送。 ( 2 ) 去空间冗余 视频图像的帧内数据和预测的帧间误差数据，都有很高的空域冗余信息。可 用于减少空域冗余信息的技术很多，主要都是基于块的技术。在基于块的空间冗 余技术领域中，变换编码技术是最常用的方法，归纳起来，可分为三个阶段：正 交变换、对变换系数进行量化、及编码三个阶段。 正交变换：正交变换是将空域图像信号映射变换到另个正交矢量空间如 频域，产生一批变换系数，然后对这些变换系数进行编码处理。最常用的为d c t 变换，它与k l 最佳变换压缩性能和误差非常接近，而且计算量适中，又具有可 分离特性，还有快速算法等特点，所以在图像数据压缩中，采用d c t 变换编码的 方案很多。 量化：变换后系数的量化是关键的操作，量化使变换后的系数用较少的位 数来表示，量化器结合编码才使大部分数据得以压缩。它是不可逆的，是有损的 压缩方法。 # ，z 学硕士论文视频压缩中运动估计算法的研究 编码：量化后数据在编码后输出。将数据有效统计，消除编码冗余，有效 地压缩数据量。 1 4 视频压缩中的运动估计技术 运动估计技术是减少视频图像中的帧间冗余度的代表性技术。h 2 6 l 、h 2 6 3 、 m p e g 一2 、m p e g 一4 等国际标准均采用了运动估计算法。值得注意的是，一系列国 际标准虽然规定了视频编码方法和码流框架结构，但运动估计的具体算法和控制 策略对设计者是开放的。 编码过程中可以对相邻帧之间的相关性进行帧间预测。由于人眼对图像的静 止部分要求具有高的空间分辨率和较低的时间分辨率，而对运动部分恰好相反， 为了利用以上视觉特性，可把图像分割为静止部分和运动部分分别处理。静止部 分可重复前一帧数据，对运动部分则设法测定其位移量，以位移量进行运动部分 预测，并将此信息传送出去，可以改善运动区的帧间预测结果，构成完整的图像， 故称运动估计补偿预测，具体过程如图1 _ 4 1 所示。运动补偿预测假定当前帧中 的像素可以看成由参考帧中像素平移而来。每一帧图像被分成许多宏块，在y u v 为4 2 ：0 的格式”1 中，每一宏块出4 个8 x8 像素的亮度块( b = o ，3 ) ，1 个 8 8 c b 块( b = 4 ) 及1 个8 8 c r 块( b = 5 ) 构成，c b 和c r 为色度块。对每一宏块 的4 个亮度块( 1 6 x 1 6 象素) 进行块匹配，即在参考帧搜索窗( s e a r c h w i n d o w ，s w ) 内，找到与当前帧中宏块即当前块最匹配的宏块，该宏块称为预测块，预测块对 于当前块的位移量即是运动矢量( k ，f ，) 。 运动估计的准确程度对帧间编码的压缩效果非常重要。如果估计做得好，那 么当前块与预测块相减后只留下很小的值来传输，所以运动估计对视频图像压缩 编码系统的编码效率有显著影响。“，采用了运动估计的系统的压缩比，比未采用 的系统编码效率提高约3 倍。运动估计是整个视频编码中运算量最大的模块，可 占整个软件编码器运算量的5 0 以上“”。有效地缩短这部分的计算时间是编码 能否满足实时应用的关键，因此视频系绕中编码器的复杂性部分取决于运动估计 算法体系结构的复杂性。 7 ；* ，z 聋硕士论文视频k 缩中运动估计算法的研究 1 5 论文结构 图1 41 运动估计补偿预测过程 本文主要针对视频压缩中的运动估计算法进行详细的研究。全文安排如下： 第一章提出视频压缩的研究背景及论文结构。 第二章对现有的一些快速运动估计算法进行简要介绍和分析。 第三章提出在快速运动估计算法中加入一种新的起点预测的方法，该方法从 找出当前块和相邻块的运动矢量的相关性出发，预测出当前块的搜索起点。 第四章在基于运动矢量的起点预测基础上，针对d s 算法对于小运动块搜索 点数过多的问题，提出基于中心偏置的自适应的块匹配运动估计快速搜索算法 a s 。该算法以“相关块运动水平”作为分级依据，将当前块的运动水平分为2 个等级以采用不同的搜索策略，对应于小运动块的基于中心偏置搜索样式和针对 大运动块的起点预测搜索策略，目的是为了满足视频编码对运动估计算法在速度 和精度上的双重要求。 第五章提出一种于块特征的匹配准则s c s a d 。s c s a d 在增加非常少的计算 量的情况下，通过对残差块的平缓程度判断来实现匹配准则，使运动估计算法在 s c - s a d 准则下，提高了图像的质量同时，降低了残差块编码的比特数。 第六章讨论了运动估计过程除了可以减少帧间数据的冗余性之外，还能减少 p _ ，z 掌硕士论文视频压缩中运动估计算法的研究 其它编码过程中的冗余计算。提出了在运动估计计算过程中的一种预先判断全零 d c t 系数的方法，该方法能准确预先判断出经过d c t 变换和量化后为零的残差块， 在运动估计过程中加入该方法，能减少残差块的编码的复杂性，并显著地减少视 频编码器的运算量。 第七章为本论文的结论。 9 p _ ，z 妒硕士论文 视频压缩中运动估计算法的研究 第二章运动估计算法分析 在各种视频编码标准中，广泛采用基于块匹配的运动估计与补偿技术来减少 i , z l - i n 冗余。下面对已有的一些常用的基于块匹配法的快速运动估计算法进行简要 讨论和分析。 2 1 块匹配法 视频编码技术在数字电视、高清晰度电视、可视电话、会议电视和多媒体视 频通信服务中起着至关重要的作用。在h 2 6 x 和m p e g 这些视频压缩国际标准中 视频系统编码器的复杂性最主要取决于运动估计。首先讨论一下运动估计中的运 动模型。假定运动目标在帧间做平移运动，相对应的运动模型可以表示为 “= x + 矿 ：( 2 1 1 ) ”2 y + v y 当运动目标在帧间有旋转、形状和大小等变化时，采用式( 2 一t - 1 ) 所表示的 运动模型做运动估计，会产生很大的估计误差。为了解决这个问题，需要从活动 图像中提取运动信息，采用一个更灵活的运动模型，选择合适的运动模型的参数 使总的估计误差最小或尽可能的小。例如有1 2 个参数的运动模型，可以表示为 甜= q 十a z x + a 3 x y + a 4 y ，+ 吩y + 口6 ( 2 一卜2 ) v = h x 2 + b 2 x + b 3 x y + 6 4 y 2 十b s y + 钆 这种参数模型可以用来估计在帧间有平移、旋转和缩放以及有其他任意变化 的运动目标。在视频编码中，运动目标在帧间可以有平移、旋转和缩放以及有其 它任意运动变化，例如物体的一部分向摄像及运动，而另部分背向摄像机运动， 或者物体的一部分在运动，而另部分静止等。式( 2 一卜2 ) 所描述地运动模型可 以有效地估计运动物体的各神不同的运动变化，但需要进行很复杂的参数估计。 在视频编码中，由于实时编码和压缩效率的要求，目前所采用的视频国际标准都 仅考虑物体的平移运动。 在视频编码过程中把图像分割成有不同运动的物体是比较困难的。通常采用 扣女；土曾硪壬瓷氮 视频压缩中运动估计算法的研究 两种比较简单的方法，一是把图像分成若干个矩形块，假定块做平移运动，对块 进行匹配运动估计。另一种方法是对每个象素的位移进行递归估计。通常象素的 递归估计的精度高，对多运动画面的适应性强，但它的跟踪范围小，实现复杂。 块匹配运动估计虽然精度较低“，但它的位移跟踪能力强，且容易实现。 由于受带宽的限制及实时视频回放的迫切需要，视频编码成为许多图像通信 应用中不可缺少的过程，并且总是要求很高的压缩比。为此，首先必须很好地辨 识视频序列中相邻帧间的相关性，并消除所谓的时间冗余。在各种视频编码标准， 如h 2 6 i ，h t2 6 3 ，m p e g l ，m p e g 一2 及m p e g 一4 中，广泛采用块匹配运动估计( b l o c k m a t c h i n g a l g o r i t h m ，b m a ) 与补偿技术来减少时间冗余。因此，发展快速且精确 的块匹配运动估计算法具有非常重要的意义。块匹配法实现效果主要取决于三个 因素：匹配准则、搜索范围和搜索方法。 实用匹配准则有很多种，两种常用的块匹配准则为绝对差值和s a d 以及绝对 方差和s s e ： s a d ( i ，) = ll k ( m ， ) 一i k 一。咖“ m 2 xh 2 r m niv + n - i s s e ( i ，) = ii k ( m ，n ) - i , 一。( m + f ， n + j ) i ， 以十u ，) 1 2 ， ( 2 1 3 ) ( 2 - 1 4 ) 这里i k ( m ，n ) 、i k - ，( m ，1 1 ) 分别表示当前块和参考块图像。( i ，j ) 代表参考 块相对当前块的位移。n a d 对每个象素的算术平均即为平均差值和m a d ，s s e 对 每个象素的算术平均即为平均方差m s e 。选用s a g 和m a b 准则可以避免乘法运算， 而s a d 运算量最小，便于硬件实现，所以用得最多。 搜索范围一般以宏块和块为单位，而搜索方式是影响块匹配法性能的主要因 素，也是运动估计算法中的关键技术。 块匹配原理如图2 t 1 所示，其基本思想是将当前帧分成若干个m n 大小 相同的块( 各类视频压缩标准中块大小均为1 6 1 6 ) ，对每一个块( 当前块) 分别 在参考帧中的一定区域( 称为搜索窗口) 内，假设当前块相对参考块最大位移为d 个象素，那么，参考帧内与当前块相对应的坐标附近n 十2 d 范围为搜索范围。 当前块按照一定的匹配准则在参考帧中搜索与之最接近的块( 称为预测块) ，预测 块与当前块间的位移称为运动矢量，它们的像素间的差值称为残差块，预测块与 身目，z 掌硕士论文视频压缩中运动估计算法的研究 当前块之间通过匹配准刚函数得到的值称为块失真度( b d m ) 。这样在己知参考帧 视频数据时，当前帧中的每一块数据都可用一个残差块和一运动矢量来表示，显 然，残差块和运动矢量的值越小，越有利于压缩。因此运动估计的主要目标就是 使预测块与当前块之间的b d m 和运动矢量的值尽量小，匹配误差最小的参考块所 列应的位移就是所求的运动矢量。目前衡量b d m 最常用的方法是式( 2 - 1 3 ) 所示 的绝对差值和块匹配( s a d ) 准则。相应的运动矢量( m v ) 由下式决定： m v = ( f ，州。删d ( 1 f 2 一卜5 ) 图2 1 1 块匹配方法 2 。2 常用的几种运动估计算法 全搜索算法( f s ) ? ”3 是运动估计中性能最好的算法，而其它快速运动估计 算法有很多，使用较多的如三步搜索法( t s s ) “、共轭方向搜索法( c d s ) d g 、 二维对数搜索法( l o g s ) 、交叉搜索法( c s ) “”、动态搜索窗调整搜索法( d s w a s ) 。2 1 和菱形搜索法( d s ) 等。2 。下面具体介绍精度较高的、简单常用的f s 、t s s 、 d s 算法。 1 f s 算法 要得到最佳匹配的运动矢量，最简单的方法是让i 和j 在( - d ，d ) 范围内逐 _ ，t 妒硕士论文视频压缩中运动估计算法的研究 点取值，在每一点按式( 2 一卜3 ) 计算块匹配误差，然后按式( 2 1 5 ) 求出相应的运 动矢量，这就是全搜索法( f u l ls e a r c h ，f s ) 。用f s 计算一个运动矢量需做( 2 d + 1 ) 2 次块匹配。从式( 2 - 1 3 ) 可以看出，要对个坐标点对应的搜索块完成块匹配， 需要分别计算m x n 个像素点之间的差值( m n 个减法操作) ，然后得到它们的绝 对值，最后将m x n 个绝对值进行加法操作得到s a d 结果。以从3 2 3 2 的点阵中 匹配8 x 8 的点阵为例，对一个坐标点要完成8 x 8 = 6 4 个减法操作，6 4 个求补 加1 操作( 求绝对值) ，6 4 1 = 6 3 个加法操作，完成将6 4 个绝对值求和，串行 执行时至少需要6 4 + 6 4 + 6 3 = 1 9 1 个周期；完成整个3 2 3 2 的匹配需要对( 3 2 8 + 1 ) ( 3 2 8 + 1 ) = 6 2 5 个坐标点进行匹配，即总共需要6 2 5 1 9 1 = 1 1 9 ，3 7 5 个运算周期才能完成，运算量相当大。基于f s 的算法性能很好，且硬件实现简 单、规则，但是计算量很庞大，需要很多处理单元，运动估计要占到整个编码运 算量的5 0 7 0 ，在要求实时编码的情况下难以适用。f s 是性能最好的搜索 算法，但计算量太大。其它的算法都是通过减少在搜索窗中搜索的点数来减少计 算量，但性能都是有所下降，是以牺牲性能来换取处理速度的提高。 2 t s s 算法 由于f s 的运算量十分庞大，为减小运算量，先后提出了许多快速算法，这 些算法均试图构造快速逼近最佳匹配位置的搜索路径，以尽量减少冗余的块匹 配。典型的算法为t s s ( t h r e es t e ps e a r c h ，t s s ) ，其搜索过程如图2 2 1 所示， 这里d - - - - 7 ，它是通过三步搜索，逐步减小搜索步长。每次搜索都是以上一步的 搜索结果为中心，进行周围一定步长的3 1 x3 像素的搜索。第一步，以窗口中心 为中心，步长为4 ，进行周围8 个点搜索，根据匹配准则得到一个最佳匹配点， 共搜索了9 个点；第二步，以上步最佳匹配点为中心，步长为2 ，继续搜索周围 8 个点得到匹配点，共搜索了8 个点；第三步，同上一步，只是步长为l ，最后 得到的最佳匹配点就是要得到的运动估计的点，从而得到运动矢量。进行图像的 预测共进行了2 5 次块匹配，同样情况下，采用f s 则需做2 2 5 次块匹配。一般地， t s s 的运算量为8 l o g ，d 十1 次块匹配。t s s 运算时间明显减少，性能比f s 有所 下降，但它在硬件上容易实现，是一种很常用的快速搜索算法。 _ ，z 妒硕士论文视频压缩中运动估计算法的研究 3 d s 算法 杏 ii i l l l 杏奄 一 蔑 羹 ii 囔 l i y 杏仓审矜裕 ii 匆黼ll 图22i 三步法 d s 算法即菱形搜索( d i a m o n ds e a r c h ，d s ) - 算法，是快速算法中最优秀的算 法之一，被m p e g 一4 国际标准采用并收入验证模型v m ( v e r i f i c a t i o nm o d e l ) 。” 中，是m p e g 一4 建议采用的快速运动估计算法。 ( a )( b )( c ) 图2 2 2 菱形搜索算法 搜索模板的形状和大小不但影响整个算法的运行速度，而且也影响它的性 能。块匹配的误差在搜索范围内构成了误差表面函数，该函数的全局最小点对应 着最佳运动矢量。由于这个误差表面通常并不是单调的，所以搜索窗口太小，就 容易陷入局部最小点；而搜索窗口太大，又容易产生错误的搜索路径。另外，统 计数据表明，视频图像中进行运动估计时，最优点通常在零矢量周围( 以搜索窗 口中心为圆心，两像素为半径的圆内) ，如图2 2 2 ( a ) 所示。基于这两点事实， d s 算法采用了两种搜索模板，分别是有9 个检测点的大模板l d s p ( l a r g ed i a m o n d s e a r c hp a t t e r n ) 和有5 个检测点的小模板s d s p ( s m a l ld i a m o n ds e a r c h p a t t e r n ) ，如图2 2 2 ( b ) 和图2 2 2 ( c ) 所示。搜索时先用大模板l d s p 在搜索区 1 4 p ，t 妒硕士论文视频压缩中运动估计算法的研究 域中心及周围8 个点处进行匹配计算，当最小块误差出现在中心点处时，将大模 板l d s p 换为s d s p ，再进行匹配计算，这时5 个点中的m b d 即为最优匹配点：否 则，改变中心位置，仍用l d s p 重复计算。 2 3 快速算法的分析 在众多运动估计算法中，全搜索运动估计算法由于精度高，应用比较广泛， 但是运算量太大。t s s 是常用，并且实现简单的一种搜索算法。t s s 算法在搜索 区域为( 7 ，7 ) 时初始搜索步长为4 ，对慢速运动块的估计来说太大，t s s 很早就确定了搜索方向，容易陷入局部最小点，损失了搜索精度。d s 算法的特 点在于它分析了视频图像中运动矢量的基本规律，选用了两种形状的搜索模板 l d s p 和s d s p 。先用l d s p 大范围搜索，再用s d s p 来准确定位，所以它的性能优 于其它快速运动估计算法。但是，d s 算法只是一种搜索策略的折衷处理，其缺 陷表现在三个方面： ( 1 ) 对于运动稍微大一点的图像，如果取常用的士7 个像素点的搜索范围， 速度就比不上t s s ，因为t s s 采用9 9 的正方形搜索窗，d s 采用的是5 5 的菱 形搜索窗，t s s 的覆盖范围比l d s p 大。 ( 2 ) 对于保持静止的图像序列，即运动矢量为零矢量的情况，d s 算法必须要 依次计算l d s p 和s d s p 两个模板的1 3 个点，而理想情况是只需计算s d s p 的5 个点，即对于小运动搜索d s 算法还有待改进。 ( 3 ) d s 算法与很多梯度优先算法都是根据s a d 值变化的方向性，即沿着某个 方向s a d 更趋向于到达最小点这个性质，先选定一个方向然后在较小范围再定出 一个更细化的搜索方向，不断重复这一过程直至找到相似的匹配块，但由于过早 选定方向，容易陷入局部极小，这也是各类快速算法性能比f s 算法较差的主要 原因。 本论文着重对菱形搜索算法的缺点展开了一系列的研究。从空域相关性出 发，由相邻块预测出当前块的搜索起点，较大限度地克服搜索陷入局部最小的情 况，并且能较快速度搜索到大运动矢量。针对小运动矢量，提出用基于中心偏置 的自适应搜索算法。除此之外，提出了一种新的块匹配准则，增加非常少的计算 量的条件下，通过对残差块的平缓程度判断来实现匹配准则。在运动估计过程， ，_ j ，z 妒项士论文视频压缩中运动估计算法的研究 提出一种预先判断全为零d c t 系数的方法，使被判断为全零的块可以省去许多冗 余计算。 目；， 鸯硕士论置视频压缩中运动估计算法的研究 第三章运动估计中基于运动矢量 的起点预测 上一章中分析了一些快速运动估计算法容易陷入局部最小点而损失了搜索 精度的特点，为了提高块匹配运动估计快速算法的搜索速度、精度，在此提出一 种基于运动矢量的起点预测方法，该方法从确定当前块是否和相邻块属于同一物 体这一点出发，找出当前块和相邻块的运动矢量的相关性，并且由此预测出当前 块的搜索起点。 3 1 视频图像的运动相关性 运动相关性是指图像序列中同一帧图像内的不同部分之间以及相邻帧图像 之间运动的相似性。例如摄像机的运动会造成整个画面的运动，这种全局的运动 造成了该帧图像不同部分之间运动的空间相关性。，在基于块运动估计中，这两 类情况具体表现为空间相邻块之间的运动具有较强的相似性。 在同一帧图像中，会有各种不同的物体，在基于块匹配的运动估计中，如果 划分出的各块属于同一物体，同一物体划分的块的运动矢量之间会有一定的联 系。如果当前块可以找出属于同一物体的相邻块，那么就可以从这些相邻块的运 动矢量预测到当前块的运动矢量。为确定当前块是否有相邻块属于同一物体，可 以利用目标提取或边缘检测的方法来确定。“，但是这两种方法计算复杂而且计算 时间开销大。如果预测的运动矢量足够精确，以预测运动矢量作为搜索的起点， 那么不仅可以加快搜索的速度，还可以有效地避免搜索陷入局部最小点。 利用视频图像的运动相关性，目前普遍采用的有两种预测起点的办法：一是 基于s a i l 值比较的起点预测方法，分别求出当前块以其各个相邻块的运动矢量为 预测点的s a d 值，并选取s a d 最小的块的运动矢量作为搜索起点。3 “，采用基于 s a d 值比较起点预