基于块匹配的运动估计算法研究和优化

论文

第3卷第 6 0期20 0 8年 1 2月

武汉理工大学学报 信息与管理程版J U N LO T F R TO& MA A E N N I E R N ) O R A FWU fN O MA I N I N G ME TE G N E I G

Vo. 0 No 6 j3 .

De .2 0 c 08

文章编号：07—14 ( 0 8 0 0 6—0 10 4 X 2 0 )6— 8 1 4

基于块匹配的运动估计算法研究和优化王会鲜， 伟谢涛郑洪江陈，, '(. 1武汉理亡大学信息工程学院，湖北武汉 4 07 2塔里木大学信息工程学院， 30 0;.新褫阿拉尔 8 30 4 30)

摘

要：了克服视频编码中运动估计运算量大的困难， H S和 MV B算法进行了深入讨论；为对 B C并利用白适

应静止块检测准则和基于运动相关性自适应的初始搜索点预测方法，实现了对 M C V B算法的优化，少了算减法的搜索点数，有效提高了搜索速度。实验表明，在保证图像质量的前提下，改进后的算法平均搜索点数比H S和 MV B算法分别下降了 4%和 2%。 B C 8 9 关键词：运动估计；匹配； S块 A D准则；起点预测中图法分类号：N 1 .3 T 9 17文献标志码： A

运动估计是视频编码器中计算量最大的一个模块，由于能够有效地减少帧问相关性，广泛用被

于各种视频编码标准中， M E如 P G一1MP G一 、 E 2、MP G一 H. 6、 2 3和 H_ 6/ V等。在 E 4、 2 1 H. 6 24A C

lI

工) t- -

整个视频压缩过程中，运动估计几乎占到总运算量的 6%~8% _ J 0 0 1。尤其是 H.6 24标准引入了多种预测块模式、多参考帧、大搜索范围和亚较像素精度后，然编码性能得到了提高，运 4 虽但动估计的运算耗时却成倍地增长，大地增加了极 H 24 A C编码器的计算量。因此，高运动估 .6/ V提

州卜 卅(偏重于水平方向 a )

() b偏重于垂直方向

图】 H S法的搜索模板 B算

遍历一次模板所搜索的总点数更少，因而运动矢量分布在搜索中心及其附近，只需进行一次模板搜索。因此， S算法比其他算法 ( D、 X HB如 S HE - B S等 )度更快。

速 12 MV B算法 . CMV B( o o etrcr lt n b sd mo o C m t nv c o e i ae t n i o rao i

计算法的速度是提高整个编码速度的关键。 笔者在对 H S算法和 M C B V B算法进行分析研究的基础上，现对 MV B算法的优化。实 C

1相关算法研究1 1 HB . S算法

et ai l rh算法是基于运动矢量相关性 sm tna oi m) i o g t H S hro B (oi n—b ssac )法是一种基于 z i erh算 a水平偏置中心分布模型的快速搜索算法，用了使两个偏向性的模板，图 1所示。在图 1 a和如 () ( ),号为 12和 3的点都是必须要搜索的 b中标、点，号为 4的点为补充点，标只有当上一步搜索的最佳匹配点为 3号点时才搜索与其相邻的一个 4号点。一

的自适应运动估计搜索算法。 该算法的具体步骤如下： () 1根据当前块的坐标判断是否处于图像帧的边沿。若当前块为帧的第一行、一列或最后第列宏块，则跳至步骤 ( )否则， 4;转至步骤 ( ) 2。

() 2根据 C值 ( T矢量相关判决阈值，o e . cr l ra tntrsod, i ehl)其取值特性如图 2所示，断当前 o h判宏块左、上和右上 3个相邻运动矢量间的相关性。 若3个矢量两两相关，则宏块为相关类型宏块，转至步骤 ( )若 3 3;个矢量不为两两相关，则宏块为

HS B算法的搜索模板模型，符合运动矢量的真实分布规律，利于快速找到最佳运动矢量，有且

收稿日期：0 8—0 20 6—1 . 2

作者简介：王会鲜( 9 0女， 18一)河南许昌人，武汉理工大学信息工程学院硕士研究生基金项目：国家自然科学基金资助项目( 0 00 8 . 4 76 5 )

论文

82 6

武汉理工大学学报 信息与管理工程版

判决阈值在一定范围内做一个动态的调整。f s:3 4,l 1 T 8 P≤

ls:mn pe_A l r _A 2 0 8P T i(r S D, e S D )× .,l:2 d pd2

l8, ip _DpdA,dA ) I== (dAlr S 2r S 3× pm 3 r S, _Dp _D ne e e 0 .ls=ae g(r— D, e— D, e_A 3 T vr epe S

1 r S 2 r S D, a dA p dA p dI九— D )×s lf c r l p S 4 c e at,=4 dA a_ o P ls=m xpe_ A l r—A 2 r _A 3 F a(r S D, e S D, e S D, d pd pd￣e S r d AD4 pr d, e_ _

S D5 A )×sae atrP clf c,1=5 o() 1

图 2 C值与矢量距离的对应关系 T

独立类型宏块，跳至步骤 ( ) 4。

2 2基于运动相关性的自适应初始搜索点预测 .

( ) 3个相邻运动矢量为候选搜索中心， 3取每个中心以及其上、、和右 4个相邻点为候选下左搜索点，历候选搜索点，中，相互重叠的点遍其对仅执行一次搜索。得到的最优匹配点对应的矢量即为当前块的运动矢量。跳至步骤 ( ) 5。 ( ) HB 4用 S算法进行运动搜索得到当前宏块的运动矢量。

实际视频编码中，当前帧的视频对象里的分

块将前一帧重建的 V P里同一对象的相应位置 O作为起始搜索点。依据分块之间的空间/间相时关性，个分块周围可被采用的用于预测的分块一数为 1 4或 1~— 9块。它们在不同情况下各自的重要程度用加权的方式来体现，值能够根据权待编码视频的特性白适应变化，以反映两者重要程度的变化，:即4,

() 5搜索结束。相关实验结果表明： B H S和 MV B算法的搜 C索速度明显优于现有的几个经典算法。但 HB S

4

(。y) A×∑kp, p,o= xP ixP) ( Y/∑k+9,

算法只是一个单纯的快速模板算法， V B算法 M C在模板算法的基础上，根据相邻矢量的相关性对块的运动情况分类来进行运动估计，两种算法都没有使用其他辅助技术。因此，可以结合亚采样匹配、点预测、止块检测和提前中止等技起静

9

(+ ) 1 A×∑kp,￣ ixp) (￣y/∑

() 2

初始搜索点在当前编码块坐标系统下的坐标为：(,1 1Y ): ( 0Y )一(, )+(,y ) ,o ZZ p op 0() 3

术，对算法进一步改进，使算法的速度和性能得到进一步的提高。

权值 A为：9,

9

2优化算法2 1 AS准则 . D

A:——————

(,o一，x y/ d )∑kp,,∑ y<j ) pl 1 』=1

————￡ L一

∑kp,∑k∑k x y/ ix Y/ i￣ j￣∑ ( ) P+ (,) pp‘ 1 』 1

笔者在 MV B算法的基础上引入自适应静 C止块检测准则 ( S准则 )基于运动相关性的 AD和

() 4

式中，,为 0或 1当该块存在时为 1不存在时 kk i,,则为 0 (x,。为当前分块的初始搜索点的修；p。P ) Y正向量；p P为当前 V P内的已被预测的相 (x,Y) O

自适应初始搜索点的预测方法， MV B算法进对 C行优化。 定义变量 P为当前块左、 .左上、和上右 4个上相邻块以及前一帧相同位置总共 5个块中静止块

邻分块的绝对坐标下的运动矢量；pj ) (x,为前 一

重建 V P内的对应的分块及其自身周围的相 O

的个数，为前一帧中静止块总数在一帧的总块 p 数中所占比例，s自 7为适应阈值，r— A 1 1 Pe S D (≤ d

邻分块的绝对坐标下的运动矢量；权重系数， A为 0< A<1 ( Z)前后帧 V P之间在绝对坐标； Z,为 O下的距离；d。d。为搜索后的运动矢量。 (x,y) 2 3优化后的算法描述 .

i。为时间和空间上相邻的静止块的 S D值，≤p) A s a efc r c l at为缩放系数， a _at=( 2+ ) o s lf c r ce o 4/_

5 S。A D准则见式( )式中， a _ c r 1, s lf t的值在区 ceao间[.,.]间。s lf c r 08 12之 c e at根据前一帧静止 a_ o块的比例来预测当前块中静止块的分布概率，对

优化算法具体步骤描述如下： () 1直接对当前块的零矢量计算 S D A。若计

算出的 SD值小于阈值 ( A该值由式 ( ) 1自适应

论文

第3 0卷第 6期

王会鲜，:等基于块匹配的运动估计算法研究和优化

83 6

调整获得 )则直接跳至步骤 ( )并将零矢量作， 6,为当前块的最终运动矢量；则，至步骤 ( )否转 2。() 2根据当前块的坐标判断是否处于图像帧的边沿。若当前块为帧的第一行、一列或最后第一

法预测当前宏块的初始搜索点，后用 H S算法而 B进行运动搜索得到当前宏

块的运动矢量。

() 6搜索结束。

列宏块，至步骤 ( )否则，跳 5;转至步骤 ( ) 3。

3实验结果和分析笔者将改进后的算法在 V C++ 60平台上用 . c++语言实现，并与 M tb结合对算法进行仿真， aa l对 ai、 o e— agt、 o e、os ur、 rm n k o m t r duhe f w rcat a f e a y h rl g d o

() 3根据 C值判断当前宏块左、 T上和右上 3个相邻运动矢量问的相关性。若 3个矢量两两相

关，则宏块为相关类型宏块，转至步骤 ( )若 3 4; 个矢量不为两两相关，则宏块为独立类型宏块，跳至步骤 ( ) 5。

和 t pt这 6个序列的前 8 e e m e 0帧进行了编码， F、与 S

(取 3个相邻运动矢量为候选搜索中心， 4) 每个中心以及其上、、和右 4个相邻点为候选下左

HS M C B和 V B算法比较重建帧信噪比以及搜索点数。在 M C V B和改进算法中的 C T值取 4。图 3和图 4为这几种算法在 a i ky o和 tm e e pt e

搜索点，遍历候选搜索点，中，其对相互重叠的点仅执行一次搜索。得到的最优匹配点对应的矢量即为当前块的运动矢量。跳至步骤 ( ) 6。 () 5首先用基于运动相关性的自适应预测方

序列中性能比较的结果。图中的 ( ) a是逐帧比较

噪声比的结果，中的( )图 b是逐帧比较搜索点数的结果。表 1中列出了这 6个序列测试得到的信噪比和搜索点数。

图 3 ai ky o序列性能比较

图 4 e pt序列性能比较 tm e e表 1算法性能比较

由图 3图 4和表 1可以看出，小运动的、在

—序列FS

—HBS MV C B

塑室盛MVCB

ai序列和运动表现为镜头拉仲的 tm ee列 ky o e pt序

譬

中，进后的算法的重建帧信噪比与 H S算法和改 B M C V B算法基本相当。在运动比较剧烈的 f e o r ma n和纹理丰富细节变化多的 fw r序列中， l e o改

进后的算法的重建帧信噪比与 H S B算法相当，略高于 MV B算法。在运动很剧烈的 catur C os ad序 g

列中，改进后的算法的重建帧信噪比要略高于其他的快速算法。在搜索速度上，改进后的算法的

搜索点数要少于 HB S和 MV B算法。在小运动 C

的 ai k o和 m t r duh r y o e— agt序列中， h e改进后的算

论文

84 6

武汉工大学学报 信息与管理工程版

20 0 8年 1 2月

法的速度提升最为明显。 笔者在 MV B算法巾引入 A D准则和基于 C S

E AND T,UL I S LVAN G, J T AR G,ta. J B 0N EG D e 1 [] W1G 4O e e f t e H. 6/ C v d o o i g sa d r v￣i w o h 2 4 AV i e c d n t n a d

运动相关性的自适应初始搜索点预测方法后，在保证图像质量的前提下，少算法的搜索点数，减有

{ . E rn . rut a d S se o ie J{ I EE Ta s On Ci i n ytmsfrVd o c s

T c . 2 0,3 7:6 5 6 e h,0 3 1 ( ) 5 0— 7 .

效提高了搜索速度改进后算法的平均搜索点数比 H S和 M C B V B算法分别下降 _ 4%和 2%。 r 8 9 参考文献：张明，笃彦.匹配运动估计算法研究进展毕块[]电视技术，0 7 3 ( ) 8—1 . J. 20,1 3: 1

[]沈渝力. 5视频编码块匹配运动估计算法研究[ . D]

浙江：浙江大学信息科学与工程学院，0 7 20 .[]许 6磊.基于块匹配的序列图像运动估计算法研究

[]山东： D.山东大学通信与信息系统所，07 20 . J ONG J a tmoin et t n .F s t si i o ma o[] C IW,EON B, E 7 HO Jwi d f d da n e r h frv ra l t n b o k t mo i e imo d s a c a ib emo i lc h i o o

s e[] Itra oa C neec m g rcs n i s J . nent nl ofrne I aePoes g z i iI E,0 3 3 6:7 3 4 E E 2 0, ( ) 3 t一 7 .

[]李志欣， 2李建华，侯建党 .一种改进的运动估计新算法[]计算机工程与应用，0 74 ( 8:1 2 J. 20,3 1 )5—5 .[]周 3巍，史浩 l, l瑚 l l欣.翠于 H.6 2 4的快速运动估计算法[]汁算机 L巧 J. t没}, 07,

8 2) f20 2 (:‘3 9—3 . 7 81

『] VANNE J 8 ,HAMAL NE AI N T D.KUU I I S LNNA K. Ap r l lme r y tm r a a l lc aa l mo ys s e e f r b e b o k—sz t n o vi ie moi o

et mt n a oi m J . i u s a d S s m o s n i l r h sf] C r i n yt s f i o g t ct e r

Vd oTc nl y20,8 4:3 5 3 ie eh o g,0 8 1 ( )5 8— 4 . o

Su n t dy a d Optm ia i n o o i n Esi to Al o ihm s d o o k— m a c ng i z to n M to tma i n g rt Ba e n Bl c— t hi

W NGHu in C E e, I a, H N o g a g A i a, H N W iX E T o Z E G H nf n x iAb t a t T v ro h ih c mp tt n l e n so e vd o c d n t n e t t n, S a g rt m a d MVC lo s r c: o o e c me te hg o u ai a d ma d f h ie o i g i moi si i HB lo h n o t n o ma o i B ag— r h wee d s u s d A a t e S ai i m r ic s e . d p i t t t v c—b o k Dee t n c i r n a d t e a a t e i i a e r h p i t rd ci n me h d b s d( lc tc i r e i n h d p i n t l ac on e it t o a e ) o t o v i s p o nt e mo in c re ain w r s ( t e l et e o t z t n o e MVC lo i m, ih r d c d t es ac on sa d ef ci e h t o r lt e e u e] o r ai h p i ai ft o o z mi o h B ag rt h whc e u e e r h p it n f t h e v l mp o e h e r h s e d o t n e t t n r i e p r n e u t s o a i h ma e q ai u rn e d t ea e a e y i r v d t es ac p e f mo i si i .r e x e i o

ma o l me t s l h w t t t t e i g u l yg a a te v r g r s h w h t h s a c on so r v d ag rtm e u e b u 4% a d 2% r s e t ey c mp r d t h S ag r h a d MVC lo e l h p it fi o e lo i mp h rd c d a o t 8 n 9 e p ci l o a e o te HB lo t m n v i B ag—rti ih 1 1

Ke r s: t n e t t l:b o k l a( l g y wo d moi si i 1 lc n l h n;A 1 c i r n;i i a e r h p i t r dc in o ma o S ) rt i eo n t l a c on e it i s p oW ANG ui an:Po t rdu t S h,lo If l to1 gn e H xi sg a ae; e ( f n i t o o ma En ie lng, UT, u n 4 00 0 Ch n i W W ha 3 7 ia,

[编辑：王志全]

(上接第 88页) 4An I mpr v d Al o ih o r s Lo a i n o e g rt m f r I i c toWANG n ZENG n Ho g, WeAb t a t Ii lc t n i a mp r n tg h i rc g i o y tm. t c u a y a d s e d w l af c ep r r n eo e s r c: r ai n i o t t a e i t e i s e o n t n s se Isa c rc n p e i f t h ef ma c f h so o s a s n r i l e t o t

w oesse Ac odn otega e trso ss a mpo e loi m fin rii b u d r a rsne h l ytm. c rigt ryfaue f r e,ni rv dag r h o e r o n ayw sp ee td:Frt in ri h i i t n s i l n e s y,—

r on a a uhyl a zdb rypo c o, e iue nldn uiw s r pd w i a eue r or i bu d r w s og l o le yga r et n t na c r ic igi ppl a c p e,hc cnb sdf as s y r c i j i h pt u n o h o c e

l ao

nr o na yga r et naan I d io,o bndwt o g a s r f r u r on a,ni poe o t ni e u dr b rypo co gi.nadt n cm ie i H u ht nf m o Isot ud r a rvd ci n b y j i i h r o i eb y mC n y o eao a ein d t ee te g nyi e c l iet n T ee p r n eut po eta hsi rv dMg r h i a n p rtrw sd sg e od tc d eo l v aia rci . h x ei t s l rv h tti n d o me r s mpo e o tm s iefci e a d f a; 1 f t n e s e v h

Ke r s i sl c t n;g a rj c in;C n y e g e e t n;Ho g r n fr y wo d:r o ai i o r y p oe t’ o a n d e d tc i o u h t s m a oW ANG n Ho g:P o.; c o lo f r t n E gn e n, UT, u a 3 0 0, h n . rf S h o fI o mai n i e r g W n o i W h n 4 0 7 C ia

[编辑：周廷美]

本文来源：https://www.bwwdw.com/article/02jj.html