第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参数估计方法 移动的方式还没有解决.后者引入外部模型来指引 参数估计方法必须事先知道概率密度函数的形 轮廓向对象边界移动，这种方法明显增加了查询范 式，这在计算机视觉中很推实现，数据模型往往是未