DSP的运动目标图像跟踪算法与实现-工学基础

KarthikHariharakrishnanandDanSchonfeld,SeniorMember,IEEE摘要[本文为正文！以下开始就是研究了。]我们提出一个目标跟踪快速算法一用运动矢量数据来预测目标物体轮廓。除了目标的初始化，在基于区域的方法中通用的分割步骤是可以避免的。我们用遮挡/遮挡恢复检测来更新目标轮廓,并用块向量预测目标边界从而实现跟踪。一种自适应的基于模板的方法已经被用于估计帧间的物体运动。一种能高效的控制帧间距的调制方案被用于运动估计。检测遮挡恢复的算法分两步进行。首先，从帧差中估计未遮挡区域。遮挡和遮挡恢复视为二元事件并对它们的关系做出详细解释。依据二元性原理，将遮挡恢复检测算法修改使之发展成为遮挡检测算法。该跟踪算法在计算方式上要优于现存的基于区域的目标跟踪方法。实现该该算法的程序采用了MPEG-4的视频压缩和基于H.264标准的内容检索。初步的仿真结果展示了该算法的表现。关键字：自适应运动估计，K-均值聚类，分割，视觉跟踪。I序言视觉跟踪已经成为计算机视觉领域中被广泛研究的一个课题。面对新兴多媒体标准如MPEG-4的出台，发展一个能让视频跟踪高效运行的的系统平台已经越来越重要。该视频追踪程序运用到了视频压缩，视频检索，交互视频，场景组成等等。多种技术手段已经被运用在提取视频场景中的有意义的目标。最常见的方法被归纳为几下几类：基于区域的跟踪、主动轮廓跟踪和基于网格的追踪。对于第一种方法（基于区域跟踪），视频对象由用户/物体识别算法来初步确定。然后采用经典的工具，如小流域改造来对视频序列进行分割。连续帧中的分割区域之间的通信建立并能够跟踪后续帧图像中的视频目标[3],[7],[13]。主动轮廓方法通常不运用全局物体的空间和运动信息，而只是依赖视频目标的边界附近的信息[2],[5],[11],[12],[16]。“蛇形浮动”[10]是一种采用带参量的光滑曲线（运动轮廓）来跟踪视频目标边界的方法。基于网格的方式[1],[9],[15],[18]以斜率和运动信息为基础定义了边界上节点和目标内部的初始设置。这些节点设置依据一种和Delaunay三角形类似的三角规律进行合并，产生符合要求的网格。依靠光流估计对节点信息进行采样，跟踪节点设置[8]。一种基于区域跟踪的变形（隶属于基于运动的跟踪），在[17]中有所介绍。基于运动的聚类法（运用光流）已经被用于产生连续运动的区域。尽管运动提供了对于视觉图像的有力的描述，但是孤立的基于运动的标准却不能够胜任目标跟踪。跟踪算法中最主要的问题之一是部分遮挡。对于视频序列中的遮挡检测已经提出来了一些解决方法[1],[5],[14]。迄今为止提出的遮挡检测的方法多集中在解决因为遮挡物体而出现的目标的部分藏匿[1],[5],[14]。在这些着作中，对与遮挡恢复的检测并没有做出最够的重视。目标跟踪系统的计算量的复杂与否取决于图形分割、光流或是运动估计操作。因此，实际中的实时系统必须避免这些操作的重复。本文提出的算法的主要目的就是在不需要用户交互的情况下长时间持续地预测目标边界。第二章节给出了所提算法的细节信息。第三章节论述了该算法在视频序列中用于鉴别遮挡/遮挡恢复。第四节包含实验结果证明了这一方法的有效性。结论和进一步研究已包括在最后一节。II基本跟踪算法A.一般方法所提出的算法可以被归类为基于区域的跟踪算法。遮挡和遮挡恢复技术已经被发展成为能够应用在其它的基于区域的技术上以提高跟踪精度。整体算法在（图.1）中进行了概述。所有的步骤（图.1）,在下面几个章节会有解释。在以下章节中，重新分割是指运用遵循以下提到的用户交互的算法进行的帧图像分割，以重新初始化目标部分。量。所有运动合理的区域会被标记为一个掩膜中的目标区域。3）前一步可能包含属于背景的区域。因此，需要自检测操作以去除一些小的区域。开放空间的处理已应用在形态学后期处理。将掩膜中的孔填充以成为最终掩膜。如果获取的掩膜误差太大，手工进行初始化。在游鱼序列中按照以上步骤运行的结果在（图.2）中展示。以上提到的方法对与静态的摄像机取景有很好的效果。目标也可以在图形界面中的手工初始化。如果将要被跟踪的目标类别是知道的，同样可以采用自动初始化。例如，肤色可以用来初始化一个面部跟踪。跟踪算法的效果取决于初始化后的良好的范围。一个完美的初始轮廓是对于一个跟踪算法的最好的输入值。第四章节会分别给出手工初始化和自动初始化的跟踪结果。图.2目标初始化：（a）分割图，（b）分割图中运动合理的区域第图.3对游白色一目标的运动种子快，灰色一背景的运动种子快）第图.3对游白色一目标的运动种子快，灰色一背景的运动种子快）帧中的运动种子块（黑色一不确定块，（b）C.运动估计运动估计是目标跟踪中的根本要素，因此准确的运动估计是最重要的步骤之一。本文提出的计算块尺寸的方法依据块的位置。改变目标边界的块的大小，此法等价于基于网格的运动估计。因此，运动估计比传统的块匹配技术要更加准确。1）块分类：令视频序列的第k帧为I（x,y,k）,并且（x,y）表示一个像素点。每一帧都会估计种子运动块。一个种子运动块任意取在目标或者背景中。该算法以一个大小为16X16像素的块开始并且估计反向运动.I（x,y,k+N0）中的每个快与I（x,y,k）中的对应的块相匹配。并且。用一个32X32的窗进行遍历搜索以计算运动矢量。运动估计已经被运用在Y,U,V空间。位于边界的块被标记为不确定的块，它们会在估计步骤的下一环节被处理。（图.）3显示游鱼序列中算得的种子快。。这些不确定的块会被细分为更小的块（8X8）并且新的种子快会被重估计。搜搜索范围同样会被限定，以保证不会出现错误分类。这个过程会一直持续到出现一个固定的大小为（8X8）像素的块。D.调制方案在很多视频序列中，连续帧之间的运动是比较少的。在所提出的方法中，跟踪是每三帧执行一次。一种调制方案被提出以计算帧间（女&卜+^^的目标运动，并且在被预测的运动较快的轻快的情况下调低运动估计。这种调制方案能在视频序列中的运动较慢的情况下很好的节约资源。基于运动估计算法中的初始化部分（图.3）所得出的初始化种子块，我们建立一个运动模型并算出帧间的运动均值。仿射模型有下面的公式定义到前一帧图像中、,i=l,2...6,在矩阵A中是模型参数。该转换移动参考帧中的点（x,y,k+N0）,到前一帧图像中Xbl二AytZ4口3为y_i_.001i.的（《y；Q。最小二乘算法用来提取运动模型参数。该仿射模型中的转换要素反映了目标的运动过程。如果上述L2模较大的平移分量大于阈值（n），相邻帧的运动估计是重复的（N0=1）。如果该算法一次在三帧图像上应用，能纠正跟踪误差（N0=3）。如果目标的尺寸比帧图像的尺寸小，有可能不存在任何目标种子块。在这种情况下，依据较小的块（如：4x4）算得的运动向量会被用来寻找仿射模型。E.目标掩膜的产生前一帧中与目标相符的部分用尸％表示，它的目的是在给出运动向量的条件下产生当前的目标部分. obj用来支持Pj0。让MVk+N0来描述计算出的运动向量，得到区域（块）Rk+N0gI（X,y,k+N0）。此外让［X］表示'x由hgZ2：［X］={X+hXGX}转化得出的值。在这，h代表每个块的运动向量。当前h h帧的每个块都进行运动补偿（［Rk+N0］ ）以找出坐落在Pk中的部分块。这会给我们当前帧Pk+N0i MVk+n0 obj obb的目标支持。目标掩膜需要进行合适的修改以便照顾遮挡和遮挡恢复。遮挡和遮挡恢复用下一章节的具体方法来解决。III.遮挡和遮挡恢复用来处理遮挡/遮挡恢复的最长用的方法在于找出全局运动向量中的运动补偿帧［1］。该补偿帧是初始帧与阈值a）的差值，给出当前帧的离群像素。如果前向运动估计为kfk+n0）并且第k帧以第k+N0帧重建，离群像素与第k+N0帧中将被覆盖的区域相符。对于落后的运动，第k+N0帧使用第k帧重构.。这种情况下检测到的离群像素对应第k+N0帧中出现的新的（未覆盖）区域。理想的情况下，新的区域应该对应遮挡恢复而覆盖区域对应遮挡。但在许多情况下，其中的一些为覆盖区域并不对应遮挡恢复，一下会做出解释。遮挡恢复算法的目的是用来检测事实上属于遮挡恢复的未覆盖区域。以下段落解释了用于遮挡恢复的算法。二元性原理可以被应用于构建遮挡检测算法。不能被准确地运动补偿的区域被表示成覆盖或为覆盖区域。在很多情况下，现存的不能被准确的运动补偿的区域归因于非刚性结构或光照变化。在这些情况下，覆盖和为覆盖区域并不符合遮挡和遮挡恢复。很明显需要进一步的分类来找出实际中的未覆盖区域中的遮挡恢复部分。要达到这个目标可使用基于运动的标准。AA二原理遮挡和恢复被看作是双重的事件。为检测遮挡遮挡恢复（遮挡），当前帧用下一帧来进行欲动补偿以企鹅的未被覆盖（被覆盖）的区域。在案件遮挡恢复（遮挡），具有目标运动特性的的未遮挡（遮挡）区域中与目标相似（但彼此不同）。这种检测遮挡恢复（遮挡）的算法能找出这种运动相似性。在此二元性的基础上，执行遮挡恢复检测的算法可以被公式化，做些合适的修改就可以用来检测遮挡。B.遮挡恢复检测1）未覆盖区域：为了执行遮挡恢复检测步骤，未来几帧图像中的未遮挡区域需要被预测出来。目标轮廓已经用运动矢量预测，所用公式为Pk+no。新的区域可能出现在当前帧中（k+N）。为了估计obj 0这些区域，当前帧（k+N°）会用第k帧来进行运动补偿。一些预处理操作被应用于掩膜来去除噪音。2）区域分类：如前所述，未遮挡区域不符合实际中的遮挡恢复s。我们用色彩为标准来预测未遮挡的区域。在分类的第二个阶段，运动被用来作为标准。以下是实际中的属于目标的未遮挡区域。?属于目标的未覆盖区域应该具有和目标相似的特性。?与未覆盖区域的其它目标相比较，检查运动的一致性。估计未覆盖区域平均运动向量的一致性。然后做相似的测试将未覆盖区域分成实际遮挡恢复和误报两类。

图.4提取目标（工人）图.5提取目标（车内男子）运动矢量聚类：删除Pk+N0所涵盖的区域，形成一个新的掩膜Pk+N0。Pk+N0中的运动矢obj new_obj new_obj量用如下所述的K-均值算法［4］群集。这些区域中的被覆盖部分应为运动矢量不准确而被移除，因此可能在聚类的时候导致错误。采用了基于块的办法进行来运动估计，每一个块只有一个矢量。这些块矢量会被聚类。聚类仅仅需要依据掩膜Pk+n0中的像素来执行。因此，计算每一个块在掩膜中的像素点数目，得new_obj到聚类的加权采样如（dx,dy）代表带宏的运动矢量，n是指处于Pk+N0中的宏块所包含的像素，M则是指在全部或部ii i new_obj分在Pk+N0中的宏块数目。其中运用了一种用来选择自适应集群的聚类算法。new_objB）相似性测试：以下的相似性测试是针对所有未覆盖区域：令MVib.代表未覆盖区域加中的前向运动矢量，MVibj代表目标也的运动集群的中心。每次计算 07只有在d＜甲（当d=min（di））的情况下，区域j%被认为是包含在Pk+n0中的遮挡恢复。obj,min disocc obj.min obj obj根据Q根据Qk+N0来更新目标掩膜。obj此在这里省略。IV仿真跟踪已经对一些常见的MPEG测试序列与实时视频序列做过测试。所提出的方法（即目标跟踪可以被认为是许多基于跟踪技术的区域的集合）已被文献报道。该方法主要依据运动矢量来预测目标轮廓，这也意味这现如今需要一种针对视频压缩数据的的跟踪算法。计算一帧所需的时间已经与其他两个基于区域的的跟踪办法进行了比较。依据该算法编写的程序并没有全部得到优化，改进后应能获取更佳的效果。A.视频序列在序列（工人）中，目标运动不是始终如一的，因此当观察到有意义的运动时跟踪会放缓。图。4显示了提取包含在众多干扰项中的视频目标。该方法生成的目标掩膜与基于分割的方法一样基本准确，同时它只耗费较少的计算资源。与基于区域的方法相比较的情况如图.5。B・检测调制方案图.6工人序列和游鱼序列的跳帧数目该调制方案为在II-D中描述过的在目标运动相对较慢时跳帧。对于跳帧的目标轮廓可以内插。

示序鱼的游帧目都图.6显了工人列和游序列中跳帧和。在鱼序列，110以前的标运动示序鱼的游帧目都C.遮挡检测和遮挡恢复检测图.7显示了前一节所述的遮挡恢复检测的效果。再次出现的鱼尾与鱼的躯干部分颜色不相似，所以基于颜色相似的区域融合的算法会失效。而应用我们的方法遮挡恢复部分被检测出来并与相符的目标融合。该算法同样被用在实时视频。图.8遮挡和遮挡恢复的检测图.9带有遮挡/遮挡恢复检测的人体跟踪图.7遮挡恢复的检测和融合图.8说明了遮挡检测算法的效果。另一人阻挡了被跟踪目标的一部分然后走开。块匹配算法依赖对平移模式，而且通常是不适合非刚性物体。然而，当跟踪非刚性物体时，遮挡/遮挡恢复检测

的像素。这在一定程度上处理非刚性目标。D,算法比较图10跟踪经方格处理过的目标图.11依据特征区域跟踪目标图.12手动初始化跟踪目标图.13自动初始化跟踪目标（双手都被跟踪）图10跟踪经方格处理过的目标图.11依据特征区域跟踪目标图.12手动初始化跟踪目标图.13自动初始化跟踪目标（双手都被跟踪）以下序列显示了本文提出的算法与基于双区域的方法相比较得出的目标提取效果。给出了一张不同的方法的计算时间表。比较下面两种方法。1）用格分类运算提取目标[6],[7]。2）基于区域的的数学形态学视频编码[12],[13]。图.9显示了遮挡/遮挡恢复的相关算法对于向前运动和向后运动的输出。图.10和图.11显示的算法应用的结果用于比较。对于这个例子目标跟踪优于基于区域的方法。避免向前运动加快了算法，但提取的质量受到影响。为了成功的跟踪手，采用遵循遮挡/遮挡恢复分类的自适应K-均值聚类是必要的。在目标跟踪的像素准确度要求不十分严格的情况下，跟踪算法主要是被设计应用在基于对象的视频编码。因此与基于区域的方法比较，被跟踪目标的边界不是很准确。下表（表一）列出了所涉及的各种算法的运算时间。所有算法在MATLAB上实现。因此，纯粹的时间并不能表明很大的意义。我们也有一个C编写的程序，它根据所跟踪目标的尺寸大小每秒处理4-10帧。如果提出前向运动只保留后向运动，速度可以达到两倍。我们正在进一步研究这个问题。E.自动/手动初始化的结果在随后的视频序列（图12和13），我们比较自动和手动初始化得出的追踪结果。自动初始化能在背景稳定的情况下正常工作。如果背景是变化的就必须应用一种更加精确的初始化方式。在图.12和图.13中，显示的是对手的视频序列的跟踪结果。自动初始化中，我们也用了一个肤色模型结合第二节所提到的算法。我们其实只想跟踪画画的手。自动初始化让我们对两只手同时跟踪。在这种情况下，因为我们有一个强大的肤色模型，所以初始化差不多完美的。但在其它很多视频中，利用第二节中所提到的琐碎的初始化算法效果并不好。V讨论在这篇文章中，我们提出了一个简单的跟踪算法，避免了除开初始帧中的目标部分的图像分割。用块运动矢量进行目标跟踪很少被应用。这种办法可以运用并行处理器，因此适合于实时处理。目标是要发展一种算法用以提取物视频对象，其精度接近于基于区域的方法，并且能够高效地运算。遮挡和遮挡恢复被看做是对立的问题。提出一个高效的用以检测遮挡的算法并运用二元性原理将之修改，发展成为一个检测遮挡修复的算法。因为目标掩膜被修改以照顾遮挡和遮挡恢复，目标可以准确地被跟踪一个较长的时间，而不需要重新初始化/重新分割。跟踪算法可以用前向的方式被拓展成为能够跟踪多个目标。但是这种算法对实际中很小的目标的跟踪效果不理想，正在进一步研究和改进。这种方法可以结合蛇形浮动来跟踪目标轮廓。依靠仿射模型和处理的改进可以纠正预测偏差。这种做法类似于以卡尔曼滤波为基础的办法。这种做法，也正被考虑用以将来的研究。运动估计依靠显着不同特性的和而不考虑高斯噪声会使运动向量有偏差从而导致跟踪效果的降低。这一方面仍需进一步研究。REFERENCES[1]Y.AltunbasakandA.M.Tekalp,“遮挡-adaptive,content-basedmeshdesignandforwardtracking,“IEEETrans.ImageProcess.,vol.6,no9Pp.1270-1280,Sep.1997.[2]A.A.Amini,T.E.Weymouth,andR.C.Jain,“UsingdynamicprogrammingfOrsolvingvariationalproblemsinvision,”IEEETrans.PatternAnal.Mach.Intell.,vol.12,no.9,pp.855-867,Sep.1990.[3]M.J.BlackandA.Jepson,“Eigentracking:robustmatchingandtrackingofarticulatedobjectsusingaview-basedrepresentation,"Int.J.Comput.Vis.,vol.26,no.1,pp.63-84,1998.[4]B.Everitt,ClusterAnalysis,3rded.London,U.K.:Hodder,1993.[5]Y.Fu,T.Erdem,andA.M.Tekalp,“Trackingvisibleboundaryofobjectsusing遮挡adaptivemotionsnake,“IEEETrans.ImageProcess.,vol.9g12,pp.2051-2060,Dec.2000.[6]D.Gatica-Perez,C.Gu,andM.T.Sun,“Semanticvideoobjectextractionusingfour-bandwatershedandpartitionlatticeoperators,“IEEETrans.CircuitsSyst.VideoTechnol.,vol.11,pp.603-618,May2001.[7],“Multiviewextensivepartitionoperatorsforsemanticvideoobjectextraction,“IEEETrans.CircuitsSyst.VideoTechnol.,vol.11,no.7,pp.788-801Jul.2001.[8]B.K.P.HornandB.GSchunck,“Determiningopticalflow,“Artif.Intell.,vol.17,pp.185-203,1981.[9]C.-L.HuangandC.-YHsu,“Anewmotioncompensationmethodforimagesequencecodingusinghierarchicalgridinterpolation,“IEEETrans.CircuitsSyst.VideoTechnol.,vol.4,p.4251,Feb.1994.[10]M.Kass,A.Witkin,andD.Terzopoulos,“Snakes:activecontourmodels,'Tnt.J.Comput.Vis.,vol.1,pp.321—331,1987.[11]N.Peterfreund,“Thevelocitysnake,”Proc.IEEENonrigidArticulatedMotion,pp.70-79,1997.[12]P.SalembierandM.Pardas,“Hierarchicalmorphologicalsegmentationforimagesequencecoding,"IEEETrans.ImageProcess.,vol.3,no.5,pp.639-651,Sep.1994.[13]P.Salembier,L.Torres,F.Meyer,andC.Gu,“Regionbasedvideocodingusingmathematicalmorphology,"Proc.IEEE,vol.83,no.6,pp.843-857,Jun.1995.[14]D.SchonfeldandD.Lelescu,“VORTEX:videoretrievalandtrackingfromcompressedmultimediadatabasesmultipleobjecttrackingfromMPEG-2bitstream,"J.Vis.Commun.ImageRepresent.(SpecialIssueonMultimediaDatabaseManagement),vol.11,pp.154-182,2000.[15]A.M.Tekalp,P.VanBeek,C.Toklu,andB.Gunel,"Two-dimensionalmesh-basedvisualobjectrepresentationforinteractivesynthetic.Naturaldigitalvideo,"Proc.IEEE,vol.86,no.5,pp.1029-1051,Jun.1998.[16]D.TerzopoulosandR.Szeliski,“TrackingwithKalmansnakes,“inActiveVision,A.BlakeandA.Yuille,Eds.Cambridge,MA:MITPress,1992,pp.3-20.[17]J.Y.A.WangandE.H.Adelson,“Representingmovingimageswithlayers,"IEEETrans.ImageProcess.,vol.3,no.5,pp.625-638,Sep.1994.[18]Y.WangandO.Lee,“ActivemeshAfeatureseekingandtrackingimagesequencerepresentationscheme,“IEEETrans.ImageProcess.,vol.3,pp.610-624,Sep.1994.KarthikHariharakrishnanwasborninTamilNadu,India,in1979.HereceivedtheB.E.degreeinelectronicsandinstrumentationfromtheBirlaInstituteofTechnologyandScience,Pilani,India,andtheM.S.degreeinelectricalandcomputerengineeringfromtheUniversityofIllinoisatChicagoin2003.InJuly2004,hejoinedtheDSPandMultimediaGroupofMotorola,India.Hiscurrentresearchinterestsareinmultimediacompressionandretrievalandsignal,image,andvideoprocessing.DanSchonfeid(SM’05)wasborninWestchester,PA,in1964.HereceivedtheB.S.degreeinelectricalengineeringandcomputersciencefromtheUniversityofCalifornia,Berkeley,andtheM.S.andPh.D.degreesinelectricalandcomputerengineeringfromtheJohnsHopkinsUniversity,Baltimore,MD,in1986,1988,and1990,respectively.InAugust1990,hejoinedtheDepartmentofElectricalEngineeringandComputerScience,UniversityofIllinois,Chicago,whereheiscurrentlyanAssociateProfessorintheDepartmentsofElectricalandComputerEngineering,ComputerScience,andBioengineering,andCo-DirectoroftheMultimediaCommunicationsLaboratory(MCL)andmemberoftheSignalandImageResearchLaboratory(SIRL).Hehasauthoredover60techn