第38卷　第2期2004年2月 西　安　交　通　大　学　学　报J OU RNAL OF XI′AN J IAO TON G UN IV ERSIT YVol.38　№2Feb.2004基于线性搜索的快速运动估计算法丁贵广,郭宝龙(西安电子科技大学机电工程学院,710071,西安)摘要:为了减小快速运动估计算法的计算复杂度和提高运动补偿的准确性,提出了一种新的块匹配运动估计算法,称为线性正方形搜索算法.该算法采用运动估计的线性搜索策略,对于不重要的搜索区域利用线性搜索技术进行快速搜索以减小算法的计算复杂度,而对于重要搜索区域,即最佳点所在区域,用9点的正方形模块进行精细搜索以提高算法的搜索精度.实验结果证明,该算法与菱形算法相比不仅计算复杂度减小了10%以上,而且视频编码效率可以提高约011dB.关键词:块匹配算法;运动估计;线性搜索;视频编码中图分类号:TP391　文献标识码:A 文章编号:0253-987X(2004)02-0136-04N e w F ast Motion Estimation Algorithm B ased on Line SearchDi ng Guiguang,Guo B aolong(School of Electromechanical Engineering,Xidian University,Xi′an710071,China)Abstract:In order to reduce the computational complexity of the fast motion estimation and improve the accuracy of motion compensation,a new block2matching algorithm called line2square search(L SS)algorithm was pro2 posed,in which the strategy of the line search was introduced.The L SS algorithm performed the line search for the unimportant area to reduce the computation complexity.For the important search area in which optimal points were existed,a square search pattern consisted of9checking points was used to carry out the refined search,thus the search accuracy and the prediction quality were pared with the diamond search algorithm,experimental results showed that the computational complexity could be reduced up to10%and the coding efficiency could be increased about011dB by the L SS algorithm.K eyw ords:block2m atchi ng al gorithm;motion esti m ation;li ne search;vi deo codi ng 对于视频序列图像,由于相邻帧之间存在很大的时间相关性,即时间冗余,所以通过减少时间冗余,可以大幅度提高视频编码的效率.基于块匹配的运动估计算法是一种有效的方法,它已经被许多视频编码标准所采纳[1,2].在块匹配运动估计算法中,全搜索(FS)算法精度最高,但由于它要对搜索区内的每个搜索点进行检测,因此计算复杂度高,软硬件实现困难.后来人们相继提出了许多快速搜索算法,如三步法(TSS)[3]、四步法(FSS)[4]、二维对数法(TDL)[5]、基于块的梯度下降法(BB G DS)[6]、交叉法(CS)[7]和菱形法(DS)[8,9\〗等,它们通过设计不同的搜索模板和搜索策略,在计算复杂度上比FS 减小了许多,但搜索的准确性比不上FS.因此,有必要寻找更加高效的块匹配运动估计算法.本文在分析运动矢量和绝对差和(Sum of Ab2 solute Difference,SAD)的空间分布特性的基础上,设计了一种新的搜索算法———线性正方形搜索算法(Line2Square Search,L SS).实验结果表明,本文提出的L SS算法在计算复杂度和准确性上都明显优于DS等块匹配算法.收稿日期:2003-05-05.　作者简介:丁贵广(1976～),男,博士生;郭宝龙(联系人),男,教授,博士生导师.　基金项目:国家自然科学基金资助项目(69975015);教育部优秀青年教师计划资助项目.1　DS算法DS算法即菱形搜索(Diamond Search,DS)算法[8],是快速算法中性能最为优异的算法之一,它的综合性能明显优于其他几种快速算法.在DS算法中采用两种搜索模板,分别是有9个搜索点的大模板LDSP(Large Diamond Search Pattern)和有5个搜索点的小模板SDSP(Small Diamond Search Pattern).搜索时先用LDSP计算,当最小块误差(Minimum Block Distortion,MBD)点出现在中心点处时,将LDSP换为SDSP,再进行匹配计算,这时5个点中的MBD即为最优匹配点.否则,改变中心点位置,仍用LDSP重复计算[8].DS算法的特点在于它分析了视频图像中运动矢量的基本规律,选用了大小两种形状的搜索模板.先用LDSP大范围搜索,再用SDSP来准确定位,所以它的性能优于其他算法.但是,DS算法只是一种搜索策略的折中处理,其性能上的缺陷表现在2个方面:①对于大运动的序列,DS算法在搜索最佳点所在区域时,广度搜索和梯度下降搜索同时进行,即同等地对待搜索区域的各部分,造成较大的搜索冗余,影响了算法的搜索速度;②对于保持静止的图像序列,即运动矢量为0的情况,DS算法也要经历由LDSP到SDSP的变化过程,要对13个搜索点进行搜索,所以对于小运动序列,DS算法还有待改进.2　L SS算法L SS算法根据SAD分布的空间方向性和运动矢量分布的中心偏移性,设计了正方形搜索模板和线性搜索策略.通过并行搜索和线性搜索减小了算法的计算复杂度,使用小的正方形模板保证了算法的搜索精度.L SS算法很好地克服了DS等快速算法搜索速度慢的缺点.2.1　LSS算法描述L SS算法的模板和搜索策略如图1所示.根据运动矢量分布的中心偏移性及并行处理的思想,并考虑到视觉中心凹的特点(中心密、四周疏),设计了如图1a所示的正方形模板(Square Pat2 tern,SP).此模板上有9个搜索点(称为内模板)和8个虚拟搜索点(称为外模板,图中的虚线圆),内模板用于精确搜索,外模板用于确定线性搜索的方向,图1b显示了8个可能的线性搜索方向.图1c和图1d 分别说明了MBD在水平方向和对角线方向上进行线性搜索的策略.(a)L SS的正方形搜索模板(b)8个可能的线性搜索方向(c)沿水平方向上的搜索策略(d)沿对角线方向上的搜索策略图1　L SS算法的模板和搜索策略 在描述L SS算法的具体搜索步骤之前,给出如下定义.731　第2期 丁贵广,等:基于线性搜索的快速运动估计算法定义1　中心点是指SP模板的中心位置.定义2　线搜索点是指在搜索过程中SAD值最小的搜索点,中心点和线搜索点一起确定了线性搜索的方向.L SS算法的具体搜索步骤如下.(1)以搜索区原点作为SP的中心点.(2)在SP内模板上的9个点处分别计算出对应的SAD,找出MBD点.若MBD点位于中心,则执行步骤(4);否则,计算此MBD点所在方向上的虚拟搜索点的SAD;若其SAD值大于MBD的SAD 值,则以MBD点为SP的中心点,重新执行步骤(2);若其SAD值小于MBD的SAD值,则以此虚拟搜索点为线搜索点,执行步骤(3).(3)在中心点和线搜索点所确定的方向上计算下一个检测点的SAD,若其SAD值小于线搜索点的SAD,则以线搜索点为中心点,以此检测点为线搜索点,重新执行步骤(3);否则,以线搜索点为SP的中心点,执行步骤(2).(4)将该MBD点作为最佳匹配点,得到运动矢量.由此可以看出,L SS算法具有如下特点:(1)根据SAD分布的空间方向性,提出线性搜索的思想,对于大运动序列,减少了搜索冗余,提高了搜索速度;(2)根据运动矢量分布的中心偏移性,提出了9搜索点、8搜索点的正方形模板,保证了搜索算法的精度;(3)提出基于视觉原理的并行处理的思想,在确定搜索方向的同时进行精确搜索,对于小运动序列,减少了搜索冗余,进一步提高了搜索速度;(4)从算法的实现步骤上看,算法复杂度低,便于软硬件实现.2.2　算法性能分析上面详细论述了L SS算法的原理和执行步骤,下面将通过一个具体例子来说明L SS算法相对于DS算法在速度上的优越性.图2显示了用两种算法搜索到运动矢量(7,-2)的例子.图2a显示了DS 算法的搜索路径,总共搜索了28个点;图2b是用L SS算法搜索到同样点的路径,共搜索了24个点. L SS算法比DS算法少用了4个搜索点,这说明L SS 算法比DS算法的计算复杂度低.从图2b也可以看出,在进行最佳点搜索时,L SS算法对于不重要的区域根据梯度下降法进行线性搜索,减少了不必要的搜索冗余,对于重要区域利用正方形模板进行(a)DS算法搜索路径(b)L SS算法搜索路径图2　两种算法搜索运动矢量(7,-2)的图例精确搜索,提高了算法的搜索精度.3　实验结果比较为了验证L SS算法的性能,在相同条件下对FS、TSS、FSS、DS和L SS进行了计算机仿真实验.用平均搜索点数和搜索准确性2个测度作为算法性能的验证标准.实验以3个标准序列作为测试序列,每个序列选前100帧,其中Claire序列是一种典型的视频会议序列,属于小运动序列;Mobile序列为CIF(Common Intermediate Format)标准灰度格式.选取的宏块大小为16×16,搜索范围为15×15,匹配准则为SAD.实验得到各算法的平均搜索点数如表1所示.从表中可以看出,L SS算法在各种序列中所用的平均搜索点数都是最少的,说明L SS算法是其中搜索速度最快的算法.为了验证LSS算法的准确性,直接用各算法得到的运动矢量,由上一帧恢复出当前图像(注:这里专为测试运动估值的效果,所以过程中跳过了图像编码和解码部分),然后逐帧计算出峰值信噪比(P SNR),最后将所有100帧求平均,结果如表2所示.831西　安　交　通　大　学　学　报 第38卷　表1　几种运动估计算法每块平均搜索点数比较算法Claire序列平均搜索点数加速倍数Mobile序列平均搜索点数加速倍数Football序列平均搜索点数加速倍数FS225.00 1.00225.00 1.00225.00 1.00 TSS25.009.0025.009.0025.009.00 FSS16.5613.5916.9611.1619.3911.60 DS13.3816.8213.2317.0116.8413.36 L SS9.6123.4112.0318.7014.9915.01　表2　几种运动估计算法的平均P SNR比较　dB算法Claire序列P SNRΔP SNR Mobile序列P SNRΔP SNRFootball序列P SNRΔP SNRFS41.460.0022.730.0022.560.00 TSS41.1420.3222.4120.3221.5321.03 FSS41.4020.0622.6420.0921.7720.79 DS41.4520.0122.6620.0721.7420.83L SS41.460.0022.7220.0121.8120.75 注:ΔPSNR为各算法的P SNR值与FS算法的P SNR值之差. 从表2中可以看出,FS算法的平均P SNR最高,说明效果最好;在Claire序列中L SS算法与FS算法的平均P SNR相同,说明对于小运动序列L SS的准确性非常高;在另外2个序列中,L SS算法与FS算法的平均P SNR也非常接近,而且明显高于其他算法.这说明L SS算法在准确性上要比DS等算法更好,是最接近FS算法准确性的快速估计算法.图3显示了测试序列为100帧的Football序列时,不同算法的性能比较结果.从图3a可以看出, L SS算法搜索点数最少,也就是搜索速度最快、计算复杂度最低.图3b为用不同算法求出每一帧对应的P SNR的比较结果.可以看出,L SS算法的P SNR曲线与FS算法更接近,这说明在搜索精度上L SS算法接近于全搜索,优于DS等快速估计算法.DS算法是MPEG2VM编码器中采用的快速运动估计算法,其综合性能代表了当前的国际先进水平.上面的实验结果表明,L SS算法在搜索准确性和速度上均优于DS算法,是一种更高效的快速估计算法.4　结束语本文依据SAD分布的空间方向性和运动矢量的中心偏移性,提出了L SS算法.该算法采用线性搜索确定最佳点所在区域,用正方形模板进行精确(a)平均每块搜索点数比较(b)P SNR比较图3　不同算法的性能比较搜索和选择线性搜索方向.实验结果表明,L SS算法在算法复杂度和准确性上都优于以往的快速运动估计算法.下一步将系统研究线性搜索的原理,并结合并行处理的思想探索线性搜索的最佳方案.参考文献:[1]　ITU2T Rec.H.263(1995),Video Coding for Low BitrateCommunication[S].(下转第173页)931　第2期 丁贵广,等:基于线性搜索的快速运动估计算法(b )口径面尺寸为18×8图5　平面波斜投射在矩形口径上时E面的空时方向图(a )口径面尺寸为8×18面波正投射时,都有随着口径面积的增大辐射场的峰值变大,方向性变好,但波形变宽的特性.在柱面波投射时,第2个脉冲波形的宽度大于第1个脉冲波形的宽度.同时,在口径尺寸大于激励脉冲在自由空间展布的宽度时,第2个波形有明显的畸变,这是由于中心场产生的辐射与边缘场产生的辐射时延增大造成的.在平面波斜投射于相同面积的矩形口径时,如口径的宽边与极化方向一致,则在E 面最大方向将偏离主轴方向,而在H 面并无此现象.在口径窄边与极化方向一致或口径尺寸小于激励脉冲在自由空间展布的宽度时,此现象并不明显.同时亦可看出,对相同面积的矩形口径而言,若矩形口径的窄边与极化方向一致,则该口径辐射场的辐射幅度与辐射脉冲的持续时间大于矩形口径的宽边与极化方向一致时的辐射情况.由此还可得出结论,改变口径面的形状和大小可改变辐射特性.参考文献:[1]　汪文秉.瞬态电磁场[M ].西安:西安交通大学出版社,1991.[2]　Baum C E.Radiation of impulse 2like transient field [R ].Sensor and Simulation Notes ,Note 321.New Mexico ,USA :Air force Weapons Laboratory ,1989.[3]　Sulliven D ,Y oung J L.Far 2field time 2domain calculationfrom aperture radiators using the FDTD method [J ].IEEE Trans on AP ,2001,49(3):464～469.[4]　王向晖,蒋延生,汪文秉.超宽带天线口径辐射效应的时域研究[J ].现代雷达,2003,25(9):38～41.[5]　Y ee K S.Numerical solution of initial boundary valueproblems involving Maxwell ’s equations in isotropic media [J ].IEEE Trans on AP ,1966,14(5):302～307. (编辑　刘　杨)(上接第139页)[2]　ITU 2T Rec.H.264/ISO/IEC 11496210(2002),Ad 2vanced Video Coding [S].[3]　Li R ,Zeng B ,Liou M L.A new three 2step search algo 2rithm for block motion estimation [J ].IEEE Trans Cir 2cuits Systems for Video Technology ,1994,4(4):438～442.[4]　Po M L ,Ma C W.A novel four 2step search algorithm forfast block motion estimation [J ].IEEE Trans Circuits Systems for Video Technology ,1996,6(6):313～317.[5]　Jain J ,Jain A.Dis placement measurement and its appli 2cation in interframe imger coding [J ].IEEE Trans Com 2munication ,1981,29(12):1799～1808.[6]　Liu L K ,Feig E.A block 2based gradient descent searchalgorithm for block motion estimation invideo coding[J ].IEEE Trans Circuits Systems for Video Technolo 2gy ,1996,6(8):419～423.[7]　Ghanbari M.The cross 2search algorithm for motion esti 2mation [J ].IEEE Trans Communication ,1990,38(7):950～953.[8]　Zhu S ,Ma K K.A new diamond search algorithm forfast block 2matching motion estimation [J ].IEEE Trans Image Processing ,2000,9(2):287～290.[9]　Tham Y J ,Ranganath S ,Ranganath M ,et al.Anovelunrestricted center 2biased diamond search algorithm for block motion estimation [J ].IEEE Trans Circuits S ys 2tems for Video Technology ,1998,8(8):369～377.(编辑　刘　杨)371　第2期 王向晖,等:口径天线瞬态辐射特性的研究。