动态图象运动矢量多重跟踪搜索算法及实现皇甫正贤钱昱明(东南大学自动控制系,南京210096)摘要针对动态图象运动矢量搜索过程中,使用普通的对数搜索方法有可能无法搜索到真实最优运动矢量的问题,分析了产生该问题的原因,并提出使用运动矢量多重跟踪方法进行运动矢量搜索。

在图象匹配的过程中应用亚采样模板有效地降低了该方法的计算量。

对大量数据的分析试验证实,该方法具有很好地适应多极点匹配图象的特点,能准确搜索到真实最优运动矢量点。

关键词图象压缩,图象匹配,运动矢量,多重跟踪,亚采样模板1 引言在各种动态图象压缩编码中,为达到较高的压缩率,一般都采用帧相关压缩的技术,以使相邻帧之间的数据冗余度最小。

不论采用何种压缩方法进行帧相关的压缩,对运动矢量的搜索计算都是必不可少的,而运动矢量的精确获得又对尽可能大地压缩数据量至关重要,因此如何能够即快又准地搜索到运动矢量就关系到整个压缩算法的优劣。

目前已经有一些广泛使用的帧搜索算法,如全局搜索[1,2],2-D搜索[2],对数搜索[3,4],以及其他一些滤波匹配算法[5~7],就精度而言,全局搜索的精度显然最高,它在选定的搜索范围内对所有位移情况进行评价,选取最为匹配的位移作为运动矢量,因此可以将其搜索结果作为近似的真实运动矢量,但这种方法的计算量过大而不实用,从而有了改进的2-D搜索策略,但仍过于费时。

对数搜索策略的产生使计算量降低到可接受的范围之内,但就搜索精度而言较全局搜索差,很多情况下搜索不到运动矢量的最优点。

这种情况的产生主要是由于图象内容具有复杂性,导致匹配的结果具有多极值的特点。

本文据此进行了研究,提出一种运动矢量多重跟踪搜索策略,该策略是对数搜索策略的改进算法,使其能够适应多极值的匹配结果,进而搜索到真实的运动矢量。

试验结果表明该搜索方法比对数搜索方法的准确度有较大提高,而计算量却没有显著增加。

2 图象匹配的多峰值特性图1显示了一个典型的图象多峰值匹配结果,该图是使用全局搜索方法在某2幅连续图象间选取40×40点阵进行逐点匹配的结果。

由图中可以看出,匹配的结果具有2个凹点,前方的凹点是真实的最优匹配点,而后方的凹点属于假匹配。

在该图中取不同的初始点作对数运动矢量搜索,得到的结果肯定是这2点之一,但最后的结果属于哪一个凹点则由于初始点取值及所采用搜索策略的不同而不同。

如果进行对数搜索,对这一过程可以进行以下分析:由于对数搜索策略搜索方向的选取规则是在8个方向分别取一点进行匹配,取其匹配值最小点所在方向为新的初始点,并缩小网格距离,进行二次匹配,直到网格距离缩小到1/2点距。

这正如图2所示,由于匹配结果的不均匀性和多极点性,很可能出现某次匹配时真实最优点附近的匹配值反而比虚假最优点附近的匹配值大,导致搜索方向向虚假最优点前进,从而使搜索范围脱离真实最优点区间而进入虚假最优点的收敛区间,最终的搜索结果收敛于虚假最优点。

2 多重跟踪搜索方法对数搜索策略存在上述问题的关键原因在于,在每一次网格计算的8点匹配值中仅选取一点最佳匹配值,并以该点作为起始点进行下一步的跟踪。

由于开始搜索时范围较大,步长较长,因此匹配值较小的点很可能接近某个局部最优点,但所选取的匹配点可能均离真实的全局最优点较远,由此导致离全局最优点最近的匹配点匹配结果可能反而不及离局部最优点最近的点的匹配结果。

由于以后的搜索以上一次搜索的最佳匹配点为基准将步长减半进行,一旦某一次选错了最优匹配点,就不可能再搜索到真实最优点的区间。

因此该方法搜索到的点仅能说明是局部最优,但并不能保证全局最优。

对此的一个解决办法是同时进行多个方向的矢量跟踪搜索,方法如下:在每一步的匹配结果得到以后,选取2个最佳匹配值的点作为进一步跟踪的起始点,在每个起始点周围选取8点作进一步匹配,并比较这18个点的匹配值,从中再次选取2个最小值点,重复该过程,直到网格间距达到1点。

此时比较出2个最小值点中的一个最小点,并按照对数搜索方法进行半象素点匹配,就基本可以得到准确的最优运动矢量。

对这一过程的分析可以得知,使用该方法,在第1步就选取了2个最优方向进行2重跟踪,2个最优方向上找到真实运动矢量的可能性要大大高于仅选取一个方向时的可能性。

在进行第二次及以后更多次的跟踪步骤时,由于搜索步长减小,因此所选取的匹配点距离真实最优点较近,所匹配的结果也较接近真实最优点的匹配结果。

虚假最优点附近的匹配点由于离真实最优点较远,它能够取得较小匹配结果的可能性就小得多。

对匹配结果的比较就导致放弃虚假最优点附近的继续跟踪转而跟踪真实最优点附近的匹配值,最终搜索到真实最优运动矢量。

该方法在保持了对数搜索方法计算量较少的基础上改进了匹配点的选取规则,因而得到较高的搜索精度。

对于使用并行硬件实现该算法来讲,由于搜索的步数与对数搜索相同,因此耗时也相同。

经过对大量的图象进行统计分析表明,一般在一个匹配极值点的正负5点之内为单调收敛区间,在该收敛区间内的起始点进行对数运动矢量搜索都可以收敛于该极值点。

超出5点范围之外就很可能有其它的极值点收敛区间存在,因此单纯的对数搜索策略对于小范围运动矢量的搜索较为有效,但对于运动矢量较大时的应用一如可视电话,图象监控等低码率应用失配,的可能性就大大增加了。

对于这类情况,使用运动矢量多重跟踪搜索策略就能够得到较好效果。

以16×16点阵范围内的搜索为例,标准的对数搜索需要进行26次匹配。

而多重跟踪搜索需要匹配39次。

因此从计算量的角度看似乎多重跟踪算法要多出1/3,这一问题可以通过对图象匹配过程的加速处理来消除3 图象匹配的加速算法在运动矢量搜索过程中正确选取匹配函数对于能够既快又准地进行搜索有很大关系,这是由于块匹配函数处于矢量搜索过程的最底层,以对数搜索为例,每一宏块运动矢量的搜索至少都要进行9次到9n次块匹配(n为搜索的迭代次数)。

如果可以将块匹配运算的计算量减少一半就可以使所有矢量的搜索速度都提高一倍。

块匹配的准则也有几种,效果较好的是运动补偿块与当前块间的均方误差最小,另一种较简单算法是补偿块与当前块间的平均绝对误差较小。

在一般的活动图象压缩算法中对块匹配准则的建议是采用绝对误差平均值MAD作为最优化目标函数。

绝对误差均值函数[8]算法简单,只包含加法和绝对值运算,效率较高。

(m,n)为当前块左上角坐标值。

M为该宏块的行列数。

上述函数是将该宏块内的所有象素点都参与块匹配,这样的结果当然精度较高,但效率则并不很高。

为了在满足精度的条件下尽可能提高效率,一个可行的方法就是采用模板方式进行块匹配。

模板匹配方法在文献[8]中有介绍,它的理论基础是在一幅图象中,图象的相邻象素点具有很大的相关性,在粗略的情况下可以使用相邻象素点代替当前象素点。

特别是经过对对数搜索流程的分析表明,只有最后进行整象素点和半象素点匹配时需要较高的精度以保证获得运动矢量的准确性,其他中间搜索环节所获得的运动矢量误差都大于2个象素点,此时以单象素点精度进行块匹配并不能起到提高整体运动矢量搜索精度的目的,是对计算能力的浪费。

在非单象素点和半象素点匹配时,对于标准的16×16宏块,可以采用上述模板进行亚抽样匹配,由图5可以看出,采用亚抽样后需要计算的数据点数减少为全匹配图象的1/2,相应的计算速度也提高到原有匹配算法的2倍。

在对数搜索的最后阶段,即使用单象素点和半象素点搜索时,使用上述模板便不能够满足精度要求,仍然需要使用全象素点匹配。

使用图5中的亚抽样匹配模板,利用多重搜索策略进行16×16点搜索与原有对数搜索算法的计算量之比为:(假设各运动矢量可能性均等)运用多重搜索,共需要进行非单象素点匹配24次,单象素点及半象素点匹配16次。

对于非单象素点匹配过程使用亚抽样模板,需要的匹配计算量为(1/2 * 24 +16)*Cn(Cn为单次全象素点匹配所需的计算量)。

使用对数搜索,需要匹配的点共有26个,计算量为26*Cn,故二者计算量之比为:这表明使用该多重搜索方法对计算量的需求与对数搜索方法基本相当。

4 试验结果为了验证该方法的有效性,对上百幅连续图象的运动矢量进行了搜索测试。

由于采用全局搜索算法可以准确地找到运动矢量匹配值的最小点,故将全局搜索的结果作为真实最优点,同时使用对数搜索算法和多重搜索算法进行矢量搜索,计算两种方法能够找到最优点的比例及所花费时间,结果如下:由图6可以看出,两种方法的计算量需求基本相当,但使用普通对数搜索策略可能有20%的情况找不准最优运动矢量,在运用了运动矢量多重跟踪搜索策略后,这一比例下降到了5%左右。

而这最后的5%的情况并不一定表明搜索结果错误,很可能是运动矢量根本不存在,在本试验中由于将全局搜索的结果作为运动矢量,因此不论何种条件都可以得到一个最小值点,但这个最小值点并不一定就是运动矢量。

这种情况下,实际应用中的处理一般是该帧作为非相关帧直接进行帧内编码。

5 结束语测试结果表明运动矢量多重跟踪搜索算法对于图象匹配所产生的多极点现象具有很好的适应能力,与对数搜索算法相比较,在整体计算量基本持平的情况下能够使运动矢量搜索的准确率有较大的提高。

在不要求搜索精度很高的情况下,也可以仅采用算法中的亚采样匹配模板,这时可以将对数搜索的计算量减少1.6倍。

参考文献1 Arum ravali,Barry G.Haskell.Digital Pictures, represen-tation and compression Plenum Press.1988.2 Puri A Aravind R. Motion Comprnstated Video Coding withAdaptive Perceptual Quantization. IEEE Trans on Circuits andSystems for V ideo Technology, 1991,1.3 ITU-T Draft Recommendation H.263, Video Coding for Low Bi-tRate Communication,1995.4 CCITT Recommenxdation H.261, Codec for audioVisual ser-vices at px64k bits/s ,Geneva, 1990.5 Chang, Shifan. Scalable array architecture design for full searchblock matching.IEEE Transactions on Circuits and Systems for Video Technology, 1995, 5(4):332~343.6 Y eo, Hangu.Novel modular systolic array architecture for full-search blockmatching motion estimation, Special Sessions ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing-Proceedings v 5 1995. IEEE, Piscataway,NJ,USA,95CH35732:3303~3306.7 Namazi N M.Nonuniform image motion estimation using Kalmanfiltering, Proceedings -ICASSP, IEEE International Conferenceon Acoustics,Speech and Signal Processing v 5 1994. IEEE, Pis-cataway, NJ, USA,94CH3387-8:229~232.8 陈廷标,夏良正.数字图象处理.北京:人民邮电出版社, 1989.。