第5卷第2期 智能系统学报 Vol.56.2 2010年4月 CAAI Transactions on Intelligent Systems Apr.2010 doi:10.3969/i.i8gn.1673-4785.2010.02.001 视觉跟踪算法综述 杨戈，刘宏 (1.北京大学深别研究生院集成微系统科学工程与应用重点实验宣，广东深圳518055；2.北京大学机器感知与智 能救育部重，点实验室，北京100871) 摘要：随着信息技术与智能科学的迅速发展，计算机视觉已经成为T产业和高新技术领域的前沿.视觉跟踪是当 前计算机视觉领域的热点问题之一.阐述了视觉跟踪算法的研究现状，包括视觉跟踪算法的种类，常用数学方法，研 究了基于区域的跟踪算法、基于模型的跟踪算法、基于特征的跟踪算法、基于主动轮廓的跟踪算法、参数估计方法和 无参密度估计方法，并探讨了视觉跟踪算法的未来研究方向. 关键词：计算机视觉；视觉跟踪；粒子滤波；均值漂移 中图分类号：TP文献标识码：A文章编号：16734785(2010)020095-11 Survey of visual tracking algorithms YANG Ge,LIU Hong (1.Key Laboratory of Integrated Microsystems,Shenzhen Graduate School of Peking University,Shenzhen 518055,China;2.Key La- boratory of Machine Perception,Peking University,Beijing 100871,China) Abstract:Progress in information technology and intelligent systems has brought computer vision to the forefront of IT research.Visual tracking is currently one of the most active research topics in computer vision.The state of re- search in visual tracking algorithms was examined for this paper.The authors reviewed the common visual tracking algorithms and their main mathematical methods.The examination included region-based tracking algorithms,ac- tive contour-based tracking algorithms,feature-based tracking algorithms,model-based tracking algorithms,param- eter estimate algorithms and non-parameter density estimate algorithms.Significant issues needing further study were then discussed. Keywords:computer vision;visual tracking;particle filter;mean shift 随着信息技术与智能科学的迅速发展，计算机 等应用中的重要性，对其进行研究是非常紧迫的，也 视觉已经成为T产业和高新技术领域的前沿.由于 是非常必要的. 视频包含海量的信息而在多媒体中占有非常重要的 视觉分析一般步骤包括视觉检测(visual detec 地位，但随之而来的问题是如何利用计算机理解大 tion)、视觉跟踪(visual tracking)和视觉理解(visual 量的视频信息.鉴于视觉分析在人与机器人的交互understanding)川.视觉检测是检测视频序列中的目 技术(human robot interaction,HRI)、智能监控、虚拟 标，将它从图像中分割出来，检测目标的效果将直接 现实技术、基于模型的图像编码、流媒体的内容检索 影响图像后续处理的结果.视觉跟踪是在图像序列 的每一帧图像中找到感兴趣的运动目标所处的位 收稿日期：2009-11-15 置，即要在一段视频的不同帧中把被跟踪的物体标 基金项目：国家“863”计划资助项目(2006AA04Z247):国家自然科学 基金资助项目(60675025,60875050)：广东省自然科学基 记出来.视觉理解包括行为识别和行为描述，它是分 金资助项目(9151806001000025)：深圳市科技计划项目及 基础研究计划资助项目(JC200903160369A). 析和识别人体运动模型、实现行为的高级别描述.视 通信作者：杨戈.E-mail:yangge@(szpku..ed.cn 觉理解的关键问题是：如何从训练样本中学会参考
·96 智能系统学报 第5卷 行为；如何有效地用自然语言解释行为；如何有效地 因为目标假设作为分析图像的限制条件；但是它的 利用训练和匹配算法来处理在空间和时间域中与其 性能很大程度是由产生和校正这些假设的方法来决 有相似的行为模式的差异.但是，如何让机器自动地 定的，为了获得健壮的跟踪效果，需要很多目标假 跟踪目标是计算机视觉领域的一个难点，也是目前 设，而对这些假设进行估计又需要大量的计算.其中 研究的热点之一 后者是目前视觉跟踪的主流方法，但将这2种数学 1视觉跟踪算法的分类 方法结合起来有助于提高跟踪算法的健壮性又可以 减少计算量. 视觉跟踪简单地说就是估计一个对象的运动轨 视觉跟踪算法之间的差别一般有以下几方面： 迹.另外，一个跟踪系统还可以获得被跟踪对象的一 1)跟踪对象的表示； 些信息：对象的运动方向、速度、加速度、位置，从而 2)跟踪对象的外表、运动、形状的表示； 为进一步处理与分析，实现对运动对象的行为理解， 3)图像特征的选择 完成更高一级的任务做准备 传统的跟踪对象可以表示成点、原始的几何形 一个理想的视觉跟踪算法应具有以下特性： 状（如矩形、椭圆形等）、对象的轮廓和投影、骨架模 1)快捷性：视觉跟踪算法应该能够有效地跟踪 型、关节状模型等2) 运动目标，同时对场景的突然变化做出反应，这是视 视觉跟踪算法一般分成基于区域的跟踪算法 觉跟踪算法的根本目的； (region-based tracking algorithm)、基于模型的跟踪 2)鲁棒性：鲁棒性意味着可用性.被跟踪对象 算法(model--based tracking algorithm)、基于特征的 从3-D投影到2-D时会造成信息损失、图像中的噪 跟踪算法(feature-based tracking algorithm)、基于主 声、物体运动的复杂、物体的非刚性或关节的本质、 动轮廓的跟踪算法(active contour-.based tracking al- 部分和全部遮挡造成的信息暂时消失、物体姿态的 gorithm).常用的数学方法有：卡尔曼滤波器(Kal 复杂性、场景的光照变化等，客户希望在这些复杂环 man filter)、Mean shift、粒子滤波器(particle filter)、 境和情况下可以随时应用视觉跟踪算法； 动态贝叶斯网络等3] 3)透明性：视觉跟踪算法对客户应是透明的，客户 1.1基于区域的跟踪算法 得到的结果仅仅是快速的响应和良好的可用性； 基于区域的跟踪首先要分割出视频对象(video 4)高效性：视觉跟踪算法带来的运算开销越小 objects),在连续帧中建立起被分割区域之间的联 越好； 系，进而对视频对象进行跟踪4.它在包含多个对 5)稳定性：视觉跟踪算法不应给后续的运动识 象的场景中能够取得较好的效果，但不能可靠地处 别带来不稳定因素； 理对象之间的遮挡，而且只能获得区域级别的跟踪 6)简单性：视觉跟踪算法越容易实现则越容易 结果，不能获得对象的3-D姿势(3-D姿势由对象的 被普遍接受，一个理想的视觉跟踪配置应简单易行. 位置和方向构成)或轮廓31： 通常，为了更快地运行视觉跟踪算法，减少对资 文献[5]针对对象和摄像机运动无规则的环 源的需求，视觉跟踪算法应该设计得更简单；为了实 境，根据运动显著性检测的机制，提出了新的跟踪方 行更准确的跟踪目标，视觉跟踪算法又往往但要设 法，结合了目标对象的多个空间特征来实现基于区 计得很复杂 域的跟踪任务.基于区域的跟踪模型是：每帧都对每 视觉跟踪的数学解决方法有2类：自底向上和 个目标对象的特征进行更新，产生自适应的模版，如 自顶向下.自底向上方法通常是通过分析图像内容 果匹配错误较少，则运动显著图中的兴趣区域就被 来重建目标状态，如重建参数化的形状.这种方法在 标记成目标对象.但是，它没有考虑遮挡问题， 计算量上是有效的，但它的健壮性很大程度依赖于 文献[6]针对室内环境，利用一些特征来实现 对图像的分析能力.自顶向下方法产生和估计一系 单个人体的跟踪.人体被考虑成由代表人体各个部 列基于目标模型的状态假设，通过估计和校正这些 分（如头、四肢等）的块(blobs)的结合.它采用最大 图像观测的假设来实现跟踪，它通常有4个组成成 后验概率(maximum a posteriori probability,MAP)方 分：目标表示、观测表示、假设的产生和假设的估计. 法，结合先验知识来检测和跟踪人体运动，它对每个 这种方法的健壮性较少依赖于对图像的分析，这是 像素都进行高斯建模处理，然后由分类器决定这个
第2期 杨戈，等：视觉跟踪算法综述 ·97· 像素是否属于前景，属于人体的像素被指定到相应 结的形状和大小以及运动；对象外表模型是描述颜 的人体部分块(blobs)中；但是Pfinder系统只能适 色、纹理和用在连结上的材料，对象外表模型和对象 应场景较小范围或者逐渐变化的情况，不适合场景 几何模型共同决定了对象每点的位置和外表；图像 较大范围或者剧烈变化的情况， 模型是用数学方式描述摄像机；对象动态模型是通 文献[7]将图像序列中的当前帧分割成不重叠 过状态空间来描述关于运动的假设.在整体系统模 的区域：跟踪区域(the tracking regions)和非跟踪区 型中，通过初始化函数来实现其他模型.但是，它需 域(non-tracking region),这个分割可以看成马尔可 要事先给定被跟踪对象的外表模型和结构，造成一 夫标记过程.在贝叶斯框架中，它使用区域的空间特 定的局限性。 征概率表示式作为条件分布，这个跟踪算法能够解 文献[9]在3-D时空空间中，提出了基于格子 决局部变形和部分遮挡问题.它没有要求跟踪区域 的马尔可夫任意域的模型，它由表现拓扑约束的全 的形状属于特定形状，也没有要求跟踪区域和背景 局晶格结构和处理局部几何以及外表变化的图像观 有较大区别.它使用二重随机模型使得估计最优标 测模型构成，利用信任传播和粒子滤波器实现了跟 记域更加快速和准确.但是，它要求跟踪区域的外形 踪算法，不需要对运动类型或光照条件做任何假设， 服从确定的概率分布 有效地解决了动态近似纹理跟踪的困难.这个跟踪 1.2基于模型的跟踪算法 算法由纹理检测、空间推理、时间跟踪和模板更新等 基于模型的跟踪算法首先由先验知识产生对象 构成.但是它不允许格子拓扑在跟踪过程中动态变 的模型，然后将图像数据和对象模型进行匹配来实 化，失去了自适应性， 现跟踪对象)].它能够利用对象表面或轮廓的先验 文献[10]提出了基于模型的跟踪算法，它通过 知识，这种跟踪算法具有较强的健壮性，即使对象间 检测和跟踪运动对象提取了目标的轨迹，构造了 互相遮挡或干扰的情况下，也能取得较好的性能.对 个模型，然后用模型和后续的图像进行匹配，实现跟 于人体跟踪，能够综合考虑人体结构、人体运动的限 踪对象.这个模型能够表示目标对象的区域和结构 制和其他先验知识；对于3-D模型的跟踪，一旦建立 特征，如对象的形状、纹理、颜色、边缘等.它包括2 了2-D图像坐标和3-D坐标的几何关联，也就自然 个模块：预计模块和更新模块.预计模块用来估计目 获得了对象的3-D姿势、即使对象改变了较大的角 标对象的运动参数，更新模块是用来表示目标对象 度，也可以运用基于3-D模型的跟踪算法。 的变化.它还设计了能够体现跟踪对象的结构属性 文献[2]将人体模型分成：线图模型、2-D模型、 和光谱属性的能量函数，运用卡尔曼滤波器预计运 3D模型、等级模型.线图模型把身体各个部分用线 动信息，减少了匹配过程的搜索空间.但是，它没有 以及关节（关节用线连接起来）相连接的方式再现。 考虑跟踪对象的遮挡 2-D模型是把身体直接投影到图像平面上，但它对观 文献[11]针对较低分辨率的脸部图像，提出了 测角度进行了限制.3-D模型包括椭圆圆筒状、圆锥 基于3-D几何模型的脸部跟踪算法，首先估计3-D 体等，它不需要对观测角度进行限制，但它需要更多 脸部模型的运动参数，然后，提取脸部模型的稳定纹 的参数，更复杂的计算.等级模型将人体分成骨架、代 理图.脸部纹理图像的表面变化反映了运动估计的 表脂肪的椭圆球、代表皮肤和阴影的多边形表面，这 准确性或者光线变化的情况，所以脸部纹理图像的 种模型可以获得更加准确的效果，但也更复杂 表面变化又被用来估计脸部运动.但是，它的计算成 文献[8]针对复杂的、有关节的对象提出了基 本较高 于模型的跟踪算法，跟踪算法将规测到的场景灰度 1.3基于特征的跟踪算法 图像和以前收集到的被跟踪对象的配置信息结合起 基于特征的跟踪算法是通过提取图像中元素， 来，估计被跟踪对象的配置.它是基于对象上的离散 把它们归结为高级别的特征，在图像之间匹配这些 特征之间的联系来跟踪对象的，首先通过模板匹配 特征，从而实现对象的跟踪.这种算法的好处是：即 来搜索特征的位置，然后从特征之间的联系来推断 使出现局部遮挡，运动对象的一些子特征仍然可见， 对象的运动.整个跟踪系统建立了5个模型：整体系 它分成基于全局特征的跟踪算法、基于局部特征的 统模型、对象几何模型、对象外表模型、图像模型、对 跟踪算法、基于依赖图像的跟踪算法3] 象动态模型.对象几何模型是描述关节对象各个连 为了解决遮挡问题，改善基于特征的跟踪，文献
·98 智能系统学报 第5卷 [12]提出了分布实时的计算平台，它使用了智能多 法的描述对象更简单、更有效，减少了计算的复杂 视角的空间综合方法，使得在特征点被遮挡时，仍能 性，即使在干扰或被部分遮挡的情况下，仍能连续跟 实现准确的特征跟踪.它对空间数据运用概率权值 踪对象，但是基于主动轮廓的跟踪算法的准确性被 配置，实现了简单的动态多维拓扑结构的贝叶斯信 限制在轮廓级别，而且它对跟踪的初始化特别敏感， 任网，通过综合考虑时间和空间的信任分布，改善了 如果初始轮廓位置设置不当，可使得能量函数只是 被遮挡特征的跟踪.但是，它的实现需要多个摄像机 达到局部极小，这时的分割结果就是错误的，使得这 从不同视角协同工作，增加了协调的难度！ 种跟踪算法很难自动地开始运行[3].Snake模型非 为了从视频中检测出公路标志上的文本，文献 常适合可变形目标的跟踪， [13]设计了一个健壮的框架，它实现了公路标志的 Snake模型根据运动模型、曲线模型、解决方 定位和标志中文本的检测2个子功能，通过基于特 法、曲线影响条款的类型等来进行分类18]，又分成 征的跟踪算法把2个子功能自然地合并成一个统一 参数模型94]和非参数模型25].参数模型引入的能 的框架 量函数不是固定的，它是通过参数来表示和改变的， 文献[14]提出了在自然环境中，移动机器人基 通过参数来决定外部力量的形式，在外部力量和内 于视觉的3-D定位系统，通过使用特征跟踪和迭代 部力量之间调整，取得平衡.因此，寻找适合的参数 运动估计，得到准确的运动向量，场景特征和机器人 是实现这种模型的难点.非参数模型是把寻找适合 的3-D位置通过卡尔曼滤波器来修正.但是它的计 参数的问题转化成寻找适合的密度估计问题 算成本较高，实现较困难 文献[19]第一次提出了主动轮廓模型，设计这 文献[15]提出了基于视觉的移动机器人的双 样一个能量函数：其局部极值组成了可供高层视觉 目稀疏特征分段算法，它使用Lucas-Kanade特征检 处理进行选择的方案，从该组方案中选择最优的一 测和匹配来决定图像中人体的位置，并控制机器人 种是由能量项的迭加来完成.这样，在寻找显著的图 随机抽样舆论策略被用来分隔稀疏不等图，同时估 像特征时，高层机制可能通过将图像特征推向一个 计人体和背景的运动模型.它不要求人体穿戴和周 适当的局部极值点而与模型进行交互.它通过收敛 围环境不同颜色的衣服，能够可靠地跟踪室内和室 曲线能量函数实现对图像轮廓的精确定位，更好地 外的人体.但是，仅仅依靠稀疏特征使得系统容易被 利用了能量函数，使用尺度空间来扩大兴趣特征周 具有相似运动的其他对象干扰，另外，它不能处理被 围的抓取区域.它把过去需要不同对待的视觉问题 跟踪的人体离开摄像机视野的情况，也不能处理被 归结成可以统一处理，在同一框架中，边缘、线条、轮 跟踪的人体被其他对象完全遮挡的情况， 廓可以很容易被找到并进行处理.但它更侧重于跟 1.4基于主动轮廓的跟踪算法 踪时变图像的轮廓，算法的搜索效率也不是很理想 基于主动轮廓的跟踪（基于Snake模型的跟踪， 文献[20]提出了能够自动提取用户嘴唇的模 基于可变形模型的跟踪)通常不是利用整体对象的 型，它使用了高斯混合模型、线形判别模型、贝叶斯 空间和运动信息，仅仅依靠视频对象边界的信息来 模型等.它实现了无需他人监督的分割方法，能够定 实现跟踪4].它再现对象的轮廓，在后续的视频帧 位用户的脸、嘴唇.随着兴趣区域被自动定位，模型 中动态地更新对象的轮廓.它被广泛研究并应用于 的提取问题转化成传统的模型相称的问题.它把常 边缘检测、图像分割、形状建模和物体跟踪等图像处 用形状作为先验知识来提高提取嘴唇模型的准确 理和计算机视觉领域.Snake是在图像域内定义的 性.但是它没有给出在分级分割过程中混合器的最 可变形曲线，通过对其能量函数的最小化，从而调整 佳数目，实现较困难 Snake的自然形状使与对象轮廓相一致.Snake的形 文献[2l]提出了基于Kalman滤波器的Kalman 状由曲线本身的内力和图像数据的外力所控制.作 Snake模型，它由2部分组成：基本Snake模型，用于 用在Snake上的力依据于轮廓所处的位置和其形状 单帧图像的分割；用于设定每帧Snake的初始位置， 局部调整曲线的变化.内力和外力的作用是不同的： 由前n帧位置的Kalman估计得到.Kalman Snake模 内力起到平滑约束的作用，描述弹力的属性和轮廓 型能够检测运动图像中对象的位置和运动速度.它 的刚性，而外力则引导Snake向图像边界移动161 把基于梯度的图像潜力和沿着轮廓的光流作为系统 和基于区域的跟踪算法比，基于主动轮廓的跟踪算 的测量方法，使用基于光流法的检测机制，提高了算
第2期 杨戈，等：视觉跟踪算法综述 ·99 法的健壮性，解决了遮挡问题.但这种模型比较复 围，克服了初始化困难的情况.另外一个问题是，无 杂，对于剧烈变化的运动（如跳水）效果不太理想， 法沿着边界进入凹点的情况，解决方法有定向景 在分析微脉管系统时，通过视频显微镜方法，检 点31]、控制点[32]、压力力量[334]等，有效地解决了 测和跟踪血管边界是很困难的，文献[22]提出了新 抓取范围的问题，也提供了一个理论和有效地定义 的基于主动轮廓的跟踪算法，它将梯度向量流和B- 外部域的方法，对初始化不敏感，而且能够解决进入 spline模型相结合，改进了多尺度梯度向量流，减少 边界凹点的问题.但是参数模型，为了找到适合的结 了噪声的干扰.但是它过于复杂，实现较困难. 果，需要以一系列不同参数值运行算法多次，直到取 文献[23]使用一系列的模板（轮廓）变形来模 得满意的性能 拟和跟踪视频对象，它将变形分成等级：全局仿射变 2视觉跟踪的常用方法 形、局部仿射变形、任意光滑变形（蛇形）.这样使得 跟踪算法能够及时地适应被跟踪对象姿势和形状的 视觉跟踪的常用方法有：参数估计方法和无参 变化.如果被跟踪对象是非刚性的，每个视频帧以后 密度估计方法.参数估计方法假设特征空间服从已 要更新整个模板；如果被跟踪对象是刚性的，只需要 知一个概率密度函数，通过估计目标区域中的数据 更新对象的姿势.但是它不能处理更一般的需求，在 估计密度函数的参数，得到这个概率密度函数，这个 跟踪过程中，不能自动调整参数和模板的类型， 函数一般是典型的函数，大部分是单峰的.但是在实 文献[24]通过使用局部运动和颜色信息，运用 际中，这个概率密度函数很难确定，而且特征空间也 分段轮廓预测，实行了视频对象的边界跟踪.分段轮 不一定服从一个概率密度函数.这时，无参密度估计 廓预测和对每个轮廓段两侧运动的建模使得跟踪算 方法能较好地处理这个问题， 法能够准确地决定是否以及哪里发生了被跟踪的边 设状态空间中的状态序列是{x}k=0,12.…,动态 界被其他对象遮挡，预测出可视对象的边界.能量函 状态方程是x=f(-1,),可能的观测值序列是 数是和轮廓段相关，而和尺度（分辨率）无关，针对多 {ak=l,2,观测方程是k=h(xk,n),通常f、h 尺度轮廓跟踪，不需要重新调整能量函数的权重.轮 是向量值，也是随着时间变化的函数，{，k=12, 廓的预测可以通过比真实轮廓更低尺度的图像来实 {nsk=l,2…,是噪声序列，假定它们是独立同分布. 现，可以用合理的计算成本跟踪很高分辨率的轮廓. 跟踪的目的就是在给定所有的观测值云1：k估计状态 文献[25]针对被跟踪对象的形状已知或最终 xk,或构造概率密度函数p(k|a1,).实现跟踪目标 形状和初始形状相似，提出了基于测地线主动轮廓 一般分成2步骤：预测和更新.预测是根据动态方程 的非参数拓扑约束的分割模型，整体考虑了拓扑约 和已经计算出来的时刻t=k-1状态概率密度函数 束，拓扑约束是基于几何观测的，在轮廓更新过程中 p(xk-1|1:k-1),得出目前状态的先验状态概率密度 作为约束条件 函数p(x|:k-1);更新是使用当前观测的似然函数 文献[2627]提出了非参数主动轮廓方法，首先 p(k〡x),来计算后验状态概率密度函数 不需要考虑轮廓形状就利用边域，由非参数Snake p(xx). 优先定义局部轮廓形状，基于核密度估计的表示方 如果噪声序列是高斯分布，f和h.是线性函数， 式呈现了一个便利的参数选择框架，而且更具有健 可以利用卡尔曼滤波器实现跟踪，它产生的后验概率 壮性.但它不能由一个可调整的粒度水平来控制多 密度函数也是高斯分布.如果f和h,是非线性函数， 个分段 通过线性化，可以利用扩展卡尔曼滤波器实现跟踪， 文献[28]提出了基于贝叶斯决策理论的非参 它产生的后验概率密度函数也是高斯分布.如果状态 数统计压力Snake,非参数方法用来取得统计模型， 空间是由离散的有限的状态构成，可以利用隐马尔可 来驱动曲线，实现了多颜色目标的跟踪 夫滤波器实现跟踪.如果噪声序列是非高斯分布， 目前解决基于主动轮廓的跟踪算法初始化问题 和，是非线性函数，可以利用粒子滤波器实现跟踪， 的方法有：基于多分辨率的方法9、距离潜能方 它产生的后验概率密度函数也是非高斯分布， 法[3o.但是前者对如何通过不同分辨率决定Snake 2.1参数估计方法 移动的方式还没有解决.后者引入外部模型来指引 参数估计方法必须事先知道概率密度函数的形 轮廓向对象边界移动，这种方法明显增加了查询范 式，这在计算机视觉中很推实现，数据模型往往是未
·100 智能系统学报 第5卷 知的，如果假设的密度模型不恰当，估计就会有偏 2.2无参密度估计方法 差，而且偏差又很难消除，另外参数的估计也不一定 2.2.1 Mean shift方法 是最优的，有时只是收敛于一些局部点， Mean shift方法是一种快速的、沿着梯度方向进 文献[35]提出了线性无偏递推卡尔曼滤波器， 行迭代的方法，因此能够较快地找到核密度估计的峰 将状态变量引入到滤波器理论中，用状态空间模型 值（模式）.它倾向于忽略离感兴趣区域较远的数据。 代替通常用来描述它们的协方差函数.Kalman滤波 Mean shift的优点： 器是针对线性状态空间模型的最优的最小均方误差 1)Mean shi进计算量不大，在目标区域已知的情 估计.传统的卡尔曼滤波器只是适用状态方程和观 况下完全可以做到实时跟踪； 测方程是线性系统的情况，同时要求后验概率分布 2)作为一个无参数密度估计算法，很容易作为 密度和系统噪声以及观测噪声都是服从高斯分布 一个模块和别的算法集成； 实际状态方程或者观测方程却是非线性系统，为此 3)采用核函数直方图建模，对边缘遮挡、目标 很多研究学者对传统的卡尔曼滤波器进行了相应的 旋转、变形和背景运动不敏感 扩展.最直接的扩展是扩展卡尔曼滤波器(extended Mean shift的缺点： Kalman filter,EKF)[364o1,它是通过方程的一级泰勒 1)缺乏必要的模板更新算法； 展开式来近似最优解，即先将随机非线性系统模型 2)跟踪过程中窗宽的大小如果保存不变，当目 的非线性向量函数f,和h,围绕滤波值线性化，得到 标有尺度变化时，可能跟踪失败； 系统线性化模型，然后应用卡尔曼基本方程，解决非 3)直方图是一种比较弱的对目标特征的描述， 线性滤波问题！ 当背景和目标的颜色分布较相似时，算法效果欠佳， Iterated EKF(IEKF)以迭代的方式使用状态向 当场景中目标的运动速度很快时，目标区域在 量的当前估计来线性化观测方程36：7列 相邻2帧间会出现没有重叠的区域的情况，目标这 Unscented Kalman filter(UKF)[36-3,l4s]是性能 时往往收敛于背景中与目标颜色分布比较相似的物 比EKF更高的替代方法，两者的主要不同是高斯随 体，而不是场景中的目标.文献[4546]定义了一系 机变量传递的表示法不同.在UKF中，它使用确定 列核函数和权重系数，指出mean shift的应用领域： 性抽样方法，即无味转换(unscented transformation, UT).虽然UT需要几个近似值，但它还是比其他用 文献[47]把跟踪作为二值化分类问题来处理， 通过在线方式训练弱分类器来区别对象特征和背景 非线性转换传递随机变量的方法准确.UKF的另外 一个优点是不需要转换观测方程的解析表达式，使 特征，强分类器用来计算下一帧的信任图，通过 得它能应用到基于仿真的系统中.状态分布由随机 mean shi进算法找到信任图的峰值（对象的新位 变量来近似，这些高斯型随机变量是通过一些抽样 置).通过不断地训练弱分类器，更新强分类器，使 点(sigma点)来确定的.这些点完全代表了随机变 得跟踪器以较低的计算成本取得较好的健壮性.文 量的真实均值和协方差，而且不管非线性程度如何， 献[47]能够跟踪各种场景，包括：摄象机静止或移 后验均值和协方差都能准确地获取到第2级（泰勒 动、灰度图象或红外图象、不同尺寸的对象.这个跟 级数展开)，因此它比EKF具有更好的滤波性能.当 踪算法还能处理一些遮挡：分类评分被用来检测遮 状态维数是n,则只需要2n+1个sigma点.另外， 挡：粒子滤波器被用来克服遮挡.但是，这个跟踪算 UKF不需要明确衍生的计算，也不需要对非线性系 法不能处理长时间、大范围的遮挡，另外目前被选择 统的表示进行分析.UKF的计算复杂度和EKF的相 的特征空间没有考虑空间信息， 同级别36.不同的方法在计算成本和结果的准确性 针对非刚性对象，文献[48]提出了新的对象表 方面有不同的性能特点， 示和定位方法，基于直方图的对象表示由各向同性 文献[44]提出了基于窗口匹配的跟踪算法，它 的核来规范化，对象的定位问题转化成寻找局部最 使用差平方和作为距离相似的量度，结合了卡尔曼滤 大兴趣区的问题.对象模型和对象候选区模型的相 波器，增加了跟踪算法的鲁棒性.这个跟踪算法可以 似程度由Bhattacharyya系数来表示，使用mean shift 应用到市内车辆跟踪，2人会面中的跟踪，乒乓比赛 来优化.文献[48]能够较好的处理镊像机运动，部 中对球的跟踪.但这个跟踪算法没有解决遮挡问题， 分遮挡、混乱、对象尺度变化等问题.但是，它不是针
·102 智能系统学报 第5卷 管道和并行技术，减少了处理时间，通过解决一系列 种视觉跟踪方法相互配合的跟踪系统，提高整体性 凸规划来实现对相应参数的选择， 能.因为不同的方法在计算成本和结果的准确性方 文献[66]提出了针对多目标跟踪的基于概率 面有不同的性能特点，对计算成本过高的方法对其 密度假说的滤波框架，可以和检测目标对象位置和 复杂性进行研究，构造快速算法；另外，鉴于纯数学 空间信息的对象检测器结合使用.它提出了新的粒 的算法通常要较长的计算时间，因此应用人工智能 子再抽样策略，可以平滑轨迹，克服短期的遮挡.它 技术，采用专家系统，降低对寻优精度的要求，从而 能够将由于跟踪对象数目的增加而增加的计算成本 提高速度，也是一种现实的途径 从指数级别减少到线性级别.但是它没有和事件检 4)针对2-D和3-D跟踪算法的融合，如何决定 测算法相结合，不能提取出更高级别的信息， 使用2-D跟踪算法和3-D跟踪算法的时间.当跟踪 文献[67]提出了针对多目标跟踪的配置视频 算法从2-D转到3-D时，如何根据2-D跟踪算法的 和音频传感器的跟踪系统，它使用了基于状态空间 跟踪结果来初始化3-D跟踪算法的姿态参数.因为 方法的粒子滤波器.首先使用估计声音到达方向的 2-D跟踪算法和3-D跟踪算法各有优缺点. 滑动窗口来讨论声音状态空间表达式，然后提出了 5)全方位视觉.因为能搜集到360°的场景信 视频状态空间来跟踪目标对象的位置.它结合了个 息，成本也越来越低而逐渐得到人们的重视，但需要 体特征的状态向量，同时提出了时延变量来处理由 解决全方位视觉镜头造成的图像扭曲和图像细节丢 音频传播延迟引起的音频和视频数据同步的问题. 失等情况， 文献[68]提出了自适应的Rao-Blackwellized粒 4 结束语 子滤波器，使用状态变量之间的从属关系改进了常 规粒子滤波器的效率和准确性.它把状态变量分成 总之，向用户提供快捷、稳定、准确、低成本的跟 单独的组，线性部分由卡尔曼滤波器来计算，非线性 踪结果是视觉跟踪系统追求的目标，也是视觉跟踪取 部分由粒子滤波器来计算，使用和粒子滤波框架中 得成功的关键；为此本文介绍了视觉跟踪算法的研究 的每个粒子相关联的卡尔曼滤波器来更新线性变量 现状，包括视觉跟踪算法的分类、常有数学方法，讨论 的分布.但是，当有大量的状态变量时，它不能找到 了遮挡问题和辅助物的利用等.但是因为被跟踪对象 状态变量之间恰当的从属关系模型. 周围环境的多样性和复杂性，使得视觉跟踪技术仍然 3 有很多需要解决的问题摆在研究者面前. 需要进一步研究的问题 尽管视觉跟踪技术在近几年已经取得了很大的 参考文献： 研究进展，但是仍然有许多问题和难点需要解决： [1]WANG Liang,HU Weiming,TAN Tieniu.Recent develop- 1)针对人的感知特性，如何建立一个感知特性 ments in human motion analysis[J].Pattem Recognition, 的数学模型.因为视觉跟踪的过程与人的感知特性紧 2003,36(3):585-601. 密联系，它又是很多问题的基础.比如建立适当的视 [2]YILMAZ P,JAVED O,SHAH M.Object tracking:a sur- 觉注意机制、发现辅助物的数量和可靠性的关系、如 vey[J].ACM Computing Surveys (CSUR),2006,38(4): 145. 何快速发现辅助物、在短时间内发现更多的辅助物 [3]HU Weiming,TAN Tieniu,WANG Liang,MAYBANK S. 在更长的时间内发现少而更可靠的辅助物等，这就需 A survey on visual surveillance of object motion and behav- 要以后对这个问题作深人的研究，进行统计建模， iors[J].IEEE Transactions on Systems,Man,and Cyber- 2)针对多线索的融合，如何建立一个多线索融 netics,Part C:Applications and Reviews,2004,34(3): 合的模型，尤其是多线索之间的同步和每个线索的 334-352. 异步更新.如在视觉跟踪中，通过颜色分布、运动轨 [4]HARIHARAKRISHNAN K,SCHONFELD D.Fast object 迹预测、被跟踪对象轮廓和辅助物等多线索实现跟 tracking using adaptive block matching[J].IEEE Transac- 踪；在多人视觉跟踪中，可以引入音频跟踪技术，提 tions on Multimedia,2005,7(5):853-859. 高定位的准确性，解决一定程度的遮挡问题， [5]LI Shan,LEE M C.Fast visual tracking using motion sali- 3)针对视觉跟踪方法的性能，如何建立一个多 ency in video[C]//IEEE Intemational Conference on A-
第2期 杨戈，等：视觉跟踪算法综述 ·101 对特定任务的跟踪算法，没有和特定任务的先验知 低了粒子滤波器的性能.权值退化问题主要原因是 识相结合。 重要性权值的方差随时间变化不断增加.因此增加 文献[49]提出了基于视觉特征的非刚性对象 粒子数目可以解决退化问题，但是又使计算量上升， 的实时跟踪算法，它适合各种颜色/纹理模型的对 影响算法的实时性.一般粒子的数量由状态方程的 象，对于部分遮挡，摄像机位置变化等都具有健壮 维数、先验概率密度函数和重要密度函数的相似度 性.Mean shift迭代被用来找到和给定目标模型最相 以及迭代次数决定 似的目标候选区，其中的相似程度由Bhattacharyya 再取样方法主要包括：Multinomial重取样方 系数来表示。 法s3s4]、Systematic重取样方法[3s]、Residual重取 文献[50]提出了一种在mean shif跟踪框架中 样方法534,6、采样一重要性重取样4,89和局 嵌入自适应特征选择的方法，根据贝叶斯错误率选 部蒙特卡洛重取样4).虽然再取样方法能够减少权 择最有决定性的特征，然后建立一个权重图像，使用 值退化问题，但再取样方法是在高权值的粒子区域 mean shift定位被跟踪的对象.但它假定每个被选择 取样，需不断复制大量相同的粒子.因此随着时间的 特征的贝叶斯错误率服从高斯分布，应用范围受到 改变，给粒子滤波器带来许多新的问题：再取样以 一定限制. 后，模拟的轨迹不再统计独立，因此收敛结果不再有 在基于核的对象跟踪中，模型不变和不佳的尺 效：再取样使得有较高权重的粒子在统计上被选择 度自适应性是2个主要的限制因素，文献[51]针对 很多次，这样算法会失去多样性4] 这2个因素，提出了新的基于核的跟踪方法，它把尺 基于扩展卡尔曼滤波的粒子滤波器算法称为扩 度估计和对象模型更新相结合，这种方法不受对象 展粒子滤波器(extended particle filter,EPF)【o,文 尺度和外表变化的影响.但是，它只是在手型跟踪中 献[60]用扩展粒子滤波器实现了对每个对象速度 验证了这个方法，缺乏一般性。 和位置概率估计的多模分布.基于unscented卡尔曼 2.2.2粒子滤波 滤波的粒子滤波器算法称为unscented粒子滤波器 为了实行递归的贝叶斯滤波器，文献[52]提出 (unscented particle filter,UPF)[6.文献[6l]将颜 了bootstrap滤波算法，状态向量的密度由一系列随 色分布，小波矩(wavelet moment)和UPP算法相结 机抽样表示，不需要假设系统是线性的或噪声服从 合，增加了跟踪算法的准确性，减少了计算的复杂 高斯分布.bootstrap滤波算法在重要性取样后复制 性，可以处理部分遮挡、尺度变化等.文献[62]利用 高权值的粒子，抛弃低权值的粒子，重新分配权值并 UPF框架对声音和视觉进行跟踪.文献[63]提出了 规范化，它克服了早期算法的退化问题，出现了第一 外表引导的粒子滤波，它结合外表和运动转换信息 个可操作的蒙特卡洛滤波器，即粒子滤波器 实现了概率传递模型，通过使用预收集的因子在高 粒子滤波器是一种基于贝叶斯递归推理和蒙特 维状态空间中引导跟踪，避免了粒子滤波漂移的影 卡洛方法的非线性系统分析工具.粒子滤波器主要 响.但是，贝叶斯网络的因子是根据经验或者在状态 包含重要性取样和选择（再取样）.它有2个重要的 空间中均匀分布来选择的，不能适应被跟踪的运动 成组成：动态模型和似然模型，动态模型决定粒子如 序列的变化. 何在状态空间中传播，似然模型赋予粒子权值，随后 文献[64]在粒子滤波器中结合了自适应外表 和噪声测量相关联， 模型，实现了基于自适应外表模型的观测模型和基 序贯列重要性取样其基本思想是使用大量具有 于自适应噪声变化的速度运动模型，粒子数目也是 权值的粒子（样本）近似（逼近）目标状态的后验概 自适应的.自适应的速度模型来源于一级线性预测， 率分布，但权值退化问题一直是序贯重要性取样技 这个预测基于观测和以前粒子配置之间的外表差 术的瓶颈问题.序贯重要性取样方法中存在的权值 异.这个方法可以对室内室外的视频序列进行有效 退化问题，即粒子经过几次迭代之后，会出现其中的 地跟踪， 一个粒子的规范化权值趋于1，而其他粒子的重要 文献[65]分析了传统粒子滤波算法计算上的 性可忽略不计的现象，导致许多状态更新的轨迹对 缺点，提出了新的实现方法，它使用独立主要哈希抽 估计不起任何作用，在浪费大量计算资源的同时降 样器(independent metropolis Hastings sampler),采用
第2期 杨戈，等：视觉跟踪算法综述 ·103· coustics,Speech and Signal Processing (ICASSP 2007). object based on object tracking and matching[J].Journal Honolulu,USA,2007:1073-1076 of China Institute of Communications,2001,22(11):77- [6]WREN C R.AZARBAYEJANI A,DARREL L.PENT- 85. LAND A P.Pfinder:real-time tracking of the human body [18]NIETHAMMER M,TANNENBAUM A,ANGENENT S. [J].IEEE Transactions on Pattern Analysis and Machine Dynamic active contours for visual tracking[J].IEEE Intelligence,1997,19(7）:780-785. Transactions on Automatic Control,2006,51 (4):562- [7]YUAN Xiaotong,YANG Shutang,ZHU Hongwen.Region 579. tracking via HMMF in joint feature-spatial space[C]//IEEE [19]KASS M,WITKIN A,TERZOPOULUS D.Snakes:active Workshop on Motion and Video Computing.(WACV/MO- contour models[J].Interational Journal of Computer Vi- TIONS '05).Breckenridge,CO,USA,2005:72-77. ion,1987,1:321-331. [8]NICKELS K,HUTCHINSON S.Model-based tracking of [20]CHAN M T.Automatic lip model extraction for constrained complex articulated objects[J].IEEE Transactions on Ro- contour-based tracking[C]//Interational Conference on botics and Automation,2001,17(1):28-36. Image Processing(ICIP 99).Kobe,1999:848-851. [9]LIN W C,LIU Yanxi.A lattice-based MRF model for dy- [21]PETERFREUND N.Robust tracking of position and veloc- namic near-regular texture tracking[J].IEEE Transactions ity with Kalman snakes[J].IEEE Transactions on Pattern on Patter Analysis and Machine Intelligence,2007,29 Analysis and Machine Intelligence,1999,21 (6):564- (5):777-792. 569. [10]JANG D,CHOI H.Moving object tracking using active [22]TANG Jinshan,ACTON S T.Boundary tracking for intrav- models[C]//International Conference on Image Processing ital microscopy via multiscale gradient vector flow snakes (ICIP 98).Chicago,USA,1998:648-652. [J].IEEE Transactions on Biomedical Engineering,2004, [11]WEN Zhen,HUANG T S.Enhanced 3-D geometric-mod- 51(2):316-324. el-based face tracking in low resolution with appearance [23]SCHOEPFLIN T,CHALANA V,HAYNOR D R,KIM Y. model[C]//IEEE International Conference on Image Pro- Video object tracking with a sequential hierarchy of tem- cessing(ICIP 2005).Genoa,Italy,2005:350-353. plate deformations[J].IEEE Transactions on Circuits and [12]DOCKSTADER S L,TEKALP A M.Multi-view spatial in- Systems for Video Technology,2001,11(11):1171-1182. tegration and tracking with Bayesian networks[C]//Inter- [24]FU Yue,ERDEM A T,TEKALP A M.Tracking visible national Conference on Image Processing.Thessaloniki, boundary of objects using occlusion adaptive motion snake 2001:630-633. [J].IEEE Transactions on Image Processing,2000,9 [13]WU Wen,CHEN Xilin,YANG Jie.Detection of text on (12):2051-2060. road signs from video[J].IEEE Transactions on Intelligent [25 ]Le GUYADER C,VESE L A.Self-repelling snakes for to- Transportation Systems,2005,6(4):378-390. pology-preserving segmentation models[J].IEEE Transac- [14]SAEEDI P,LAWRENCE P D,LOWE D G.Vision-based tions on Image Processing,2008,17(5):767-779. 3-D trajectory tracking for unknown environments J]. [26]OZERTEM U,ERDOGMUS D.Nonparametric snakes IEEE Transactions on Robotics,2006,22(1):119-136. [J].IEEE Transactions on Image Processing,2007,16 [15]CHEN Zhichao,BIRCHFIELD S T.Person following with (9):2361-2368. a mobile robot using binocular feature-based tracking [27]OZERTEM U,ERDOGMUS D.A nonparametric approach [C]//IEEE/RSJ Intermational Conference on Intelligent for active contours[C]//International Joint Conference on Robots and Systems(IROS 2007).San Diego,2007:815- Neural Networks IJCNN 2007).Orlando,USA,2007: 820. 1407-1410. [16]李培华，张田文.主动轮廓线模型（蛇模型）综述[J].[28]ABD-ALMAGEED W,SMITH C E,RAMADAN S.Ker 软件学报，2000,11(6)：751-757. nel snakes:non-parametric active contour models[C]/ LI Peihua,ZHANG Tianwen.Review on active contour IEEE International Conference on Systems,Man,and Cy- model[J].Joural of Software,2000,11(6):751-757. bemetics.Washington,USA,2003:240-244. [17]史立，张兆扬，马然.基于运动跟踪匹配技术的视 [29]LEROY B,HERLIN I,COHEN L D.Multiresolution al- 频对象提取[J].通信学报，2001,22(11)：77-85. gorithms for active contour models[C]//12th Interational SHI Li,ZHANG Zhaoyang,MA Ran.Extraction of video Conference on Analysis and Optimization System.Paris
·104· 智能系统学报 第5卷 France,1996:5865 adaptive unscented Kalman filter for nonlinear estimation 30]COHEN L D,COHEN I.Finite element methods for active [C]//IEEE Conference on Decision and Control.New Or- contour models and baloons for 2-D and 3-D images[J. 1eans,USA,2007:4293-4298. IEEE Transactions on Pattern Analysis and Machine Intelli- [43]AKIN B,ORGUNER U,ERSAK A.State estimation of gence,1993,15(11):1137-1147. induction motor using unscented Kalman filter[C]//IEEE [31]ABRANTES A J,MARQUES J S.A class of constrained Conference on Control Applications (CCA 2003).Istan- clustering algorithms for object boundary extraction[J]. bul,Turkey,2003:915-919. IEEE Transactions on Image Process,1996,5(11):1507- [44]VIDAL F B,ALCALDE V H C.Window-matching tech- 1521 niques with Kalman filtering for an improved object visual [32]DAVATZIKOS C.PRINCE J L.An active contour model tracking[C]//IEEE International Conference on Automa- for mapping the cortex[J].IEEE Transactions on Medical tion Science and Engineering(CASE 2007).Scottsdale, Imaging,1995,14(1):6580. USA,2007:829-834. [33]COHEN L D.On active contour models and balloons[J]. [45 ]COMANICIU D,MEER P.Mean shift analysis and appli- CVGIP:Image Understand,1991,53:211-218. cations[C]//The Proceedings of the Seventh IEEE Inter- [34]XU C,PRINCE P L.Snakes,shapes and gradient vector national Conference on Computer Vision.Kerkyra,Greeke, flow[J].IEEE Transactions on Image Process,1998,7 1999:1197-1203. (3):359-369. [46]CHENG Yizong.Mean shift,mode seekiong,and cluste- [35]KALMAN R E.A new approach to linear filtering and pre- ring[J].IEEE Transactions on Pattern Analysis and Ma- diction problems [J].Joural of Basic Engineering chine Intelligence,1995,17(8):790-799. (ASME),1960,82D:3545. [47]AVIDAN S.Ensemble tracking[J].IEEE Transactions on 36]ANTONIOU C,AKIVA M B,KOUTSOPOULOS H N.On- Patter Analysis and Machine Intelligence,2007,29(2): line calibration of traffic prediction models[C]//IEEE In- 261-271. telligent Transportation Systems Conference.Washington, [48]COMANICIU D,RAMESH V,MEER P.Kernel-based USA,2004:8287. object tracking[J].IEEE Transactions on Pattern Analy- 37]ANTONIOU C,BEN-AKIVA M,KOUTSOPOULOS H N. sis and Machine Intelligence,2003,25(5):564-577. Nonlinear Kalman filtering algorithms for on-line calibration [49 ]COMANICIU D,RAMESH V,MEER P.Real-time track- of dynamic traffic assignment models[J].IEEE Transac- ing of non-rigid objects using mean shift[C]//IEEE Con- tions on Intelligent Transportation Systems,2007,8(4): ference on Computer Vision and Pattern Recognition.Hil- 661670. ton Head Island,SC,2000:142-149. [38]SCHLOSSER M S,KROSCHEL K.Limits in tracking with [50 LIANG Dawei,HUANG Qingming,JIANG Shuqiang, extended Kalman filters J].IEEE Transactions on Aero- YAO Hongxun,GAO Wen.Mean-shift blob tracking with space and Electronic Systems,2004,40(4):1351-1359. adaptive feature selection and scale adaptation [C]/ [39]BITTANTI S,SAVARESI S M.On the parametrization and IEEE International Conference on Image Processing.San design of an extended Kalman filter frequency tracker[J]. Antonio,USA,2007:369-372. IEEE Transactions on Automatic Control,2000,45 (9): [51 YAO Anbang,WANG Guijin,LIN Xinggang,WANG 1718-1724. Hao.Kemel based articulated object tracking with scale 40]PERALA T,PICHE R.Robust extended Kalman filtering adaptation and model update[C]//IEEE Interational in hybrid positioning applications[C]//4th Workshop on Conference on Acoustics,Speech and Signal Processing Positioning,Navigation and Communication(WPNC '07). (ICASSP 2008).Las Vegas,USA,2008:945-948. Hannover,Germany,2007:55-63. [52]GORDON N J,SALMOND D J,SMITH A F M.Novel ap- [41]WU Xuedong,JIANG Xinhua,ZHENG Rongjin,HUANG proach to nonlinear/non-Gaussian Bayesian state estimation Jiashan.An application of unscented Kalman filter for pose [J].IEEE Proceedings Radar and Signal Processing, and motion estimation based on monocular vision[C]/ 1993,140(2):107-113. IEEE Intemational Symposium on Industrial Electronics. [53 ]CHEN Z.Bayesian filtering:from Kalman filters to parti- Montreal,Canada,2006:2614-2619. cle filters,and beyond.Manuscript[EB/OL].[2009-01- [42]JIANG Zhe,SONG Qi,HE Yuqing,HAN Jianda.A novel 03].http://www.math.u-bordeaux1.fr/~delmoral/chen_