基于多特征在线模板更新的鲁棒目标跟踪算法

陈东岳，陈宗文，桑永嘉

(东北大学信息科学与工程学院，110136沈阳)

目标跟踪是计算机视觉领域的核心研究课题之一，在视频监控、智能机器人、导弹制导、汽车辅助驾驶系统、体感控制等诸多领域有着广泛的应用.

基于单摄像机的目标跟踪算法根据算法思想的不同可以分为三大类.第一类是基于在线学习的跟踪算法，这类算法可以通过学习建立并更新目标的表观模型，也可以通过学习训练分类器，实现目标与背景的区分.代表性工作包括在线Adaboost算法(简称 OAB)［1-2］、多实例学习算法(简称MIL)［3］.这类算法的本质是通过单帧目标检测与识别实现跟踪，因此又称为“先检测后跟踪”.此类方法的特点是鲁棒性强，缺点是训练耗时，跟踪速度较慢.

第二类是蒙特卡罗跟踪算法，这类算法将跟踪问题转化为非线性非高斯的贝叶斯滤波问题，通过求解滤波问题实现目标的状态估计.比较典型的算法包括粒子滤波跟踪［4-5］与马尔可夫链蒙特卡罗方法［6］.由于实际跟踪问题都是非线性非高斯的，其贝叶斯准则下的后验概率计算是一个积分运算.考虑到退化问题，大多数粒子滤波算法采用候选样本状态的加权均值进行目标状态估计［7］.马尔可夫链蒙特卡罗方法则从众多候选框中选取后验概率最大的样本，通常还会与扩展卡尔曼滤波方法相结合进行运动估计［8］.此类方法在理论上比较完善，但现实中的跟踪问题通常难以满足贝叶斯估计的要求，因此在实际应用中效果并不理想.

第三类算法是以均值漂移(Mean-shift)和活动轮廓模型为代表的基于特征概率密度梯度的迭代跟踪算法.Mean-shift算法使用色彩作为基本特征［9-11］，而活动轮廓模型通常使用梯度作为基本特征［12-13］.这两种方法的本质都是有约束的梯度搜索，相比之下Mean-shift算法更加简单快速，鲁棒性更好;但在跟踪精度上略逊于活动轮廓模型.而活动轮廓模型则对背景和目标本身的纹理复杂度和轮廓清晰程度比较敏感.

通过对上述算法的分析，各类算法各有利弊.目前目标跟踪领域研究的主流思想是通过多种方法的融合解决实际跟踪过程中出现的目标突变、光照变化、遮挡、目标消失以及复杂动态环境等问题.本文正是基于上述思想，在Mean-shift算法框架下提出了一种基于多特征融合与模板在线更新策略的鲁棒跟踪算法.

1 算法概述

1.1 Mean-shift跟踪算法分析

Mean-shift算法最早是由 Comaniciu 等［9］于2000年首次将其应用于目标跟踪问题，取得了较好效果.经典的Mean-shift跟踪算法的核心思想可以用式(1)来描述:

式中:x为跟踪框的中心位置坐标，xi，i=1，2，…，n为跟踪框覆盖的全部n个像素点的坐标，G为核函数，用于调节跟踪框内不同位置的像素在概率密度估计中的作用;函数w(xi)用于度量像素xi从属于待跟踪目标的程度或可能性，尽管在不同的算法中函数w(xi)的数学形式略有区别，但总体上可以定性地理解为:像素xi对应的特征在跟踪模板中出现的可能性越大则w(xi)越大．因此，Mean-shift算法的核心思想就是寻找到一个跟踪框使其加权中心与几何中心重合．而这个寻找过程是通过一种迭代逼近的方式完成的．目前，关于Mean-shift算法中的核函数选择的研究已经比较成熟．因此Mean-shift算法的改进主要集中在如何计算函数w(xi)，如何优化搜索方式以及模板更新策略等问题上．

分析后，发现函数w(xi)主要与两个因素有关:一是用什么特征来描述像素xi，二是如何定义待跟踪目标的模板．而实际上经典Mean-shift算法的大部分缺陷也体现在这两个因素上.经典Mean-shift算法使用色彩作为基本特征，并利用色彩直方图描述跟踪模板，且其跟踪模板通常仅取决于第一帧初始跟踪框内的图像块，在跟踪过程中不进行更新.然而，在实际应用中，可能出现遮挡、目标形变以及目标与背景的色彩过于相似等问题.当目标与背景的色彩相似时，色彩直方图无法有效区分目标与背景，会造成跟踪漂移甚至跟踪失败.遮挡与目标形变则使得目标表观特征与跟踪模板的相似度下降，当两者差异累积到一定程度时，原有模板已经无法有效描述当前目标，从而导致跟踪失败.本文试图通过引入多特征融合与模板更新机制解决由色彩相似或模板偏差造成的跟踪漂移和跟踪失败问题.

1.2 算法流程

在经典的Mean-shift跟踪算法框架下，提出了色彩与纹理特征的融合机制以及能够区分目标渐变与目标遮挡的在线模板更新算法.与传统Mean-shift算法相比，本文在算法流程中添加了特征融合与模板更新两个环节.在特征融合部分，将光照不变性色彩特征与旋转不变性纹理特征通过BWH算法进行加权融合以获取跟踪目标位置的估计值;在模板更新环节，建立遮挡检测算法判别遮挡现象与自身形变，从而为决定是否进行模板更新.具体的算法流程如图1所示.

图1 算法流程图

2 色彩与纹理特征的提取与融合

在特征的选择上，为了解决目标与背景的某种特征过于相似的问题，应选取具有互补性的局部特征.因此本文提出了基于色彩特征与纹理特征相融合的像素权值估计方法.

2.1 照度不变性色彩特征提取

在跟踪过程中，随着光照条件的变化，目标色彩与亮度会发生变化，目标当前色彩直方图与模板的色彩直方图的相似度降低，从而导致跟踪失败.因此，目标的色彩特征应具有较强的光照不变性.在比较了不同的色彩空间的特性后，本文选用了HSV色彩空间，去除亮度分量V，保留色调分量H和饱和度分量S，用于建立二维色彩直方图.一般将每个分量的数值范围线性划分为16个级别，构建一个16×16的直方图矩阵.图2给出了两幅内容相同，照度不同的图像.两幅图像在HSV空间的直方图相似度较高，能够满足算法的要求.

图2 不同光照条件下的色彩直方图对比

2.2 基于LBP的纹理特征提取

纹理是反映目标表面色度和亮度变化模式的视觉特征.考虑到本文所需的纹理特征必须是与像素一一对应的局部特征，因此没有选择熵、高阶矩以及频率能量等统计性特征，而是提出了一种具有旋转不变性的LBP(local binary pattern)特征的提取算法.LBP特征最早由Ojala等［14］于1994年提出，是一种高效的局部纹理特征提取算法.按照传统的LBP算法，首先以当前像素点gc为中心(gc为该点的亮度值)，r为半径，建立圆形，并在圆周上顺指针取点gi，i=1，2，…，N建立邻域点集．图3给出了3种不同半径下的邻域点集分布模式(改自文献［14］)．

图3 3种不同的LBP邻域点分布

本文使用半径为r=1，邻域点个数为N=8的情况．逐个将邻域点gi与中心点gc进行比较，如gi的亮度高于gc，记为1;否则记为0．则圆周上的8个像素将对应于一个八位二进制数．将该二进制数转化为十进制数，即为当前像素gc对应的LBP特征，其值域范围为［0，255］．

LBP特征能够较好的反映像素点局部邻域的空间分布模式，能够为边缘、角点等特征点提供可分性较强的数学描述.然而，传统的LBP算法并不具有旋转不变性.Salberg等［15］提出了一些具有旋转不变性的改进型LBP算法.但考虑到计算的复杂度以及可区分度方面的要求，对于实时目标跟踪问题而言效果并不理想.针对上述问题，将形状数的概念引入到LBP特征描述方法中，提出了一种新的具有旋转不变性的鲁棒LBP特征提取算法(RRLBP，rotation-invariant robust LBP).

首先，为克服局部噪声对LBP特征的影响，定义RRLBP二进制序列计算函数如式(2)所示.其中Bi(gc)表示像素gc对应的LBP二进制数中的第i位.

对生成的二进制数B进行循环移位操作．设循环左移 p位后得到的二进制数记为 Bp，p=1，2，…，m．在循环左移产生的全部m个新的二进制数中，找到数值最小的一个，将其转为十进制数作为LBP特征输出．例如，gc对应的原二进制数为00110001，则其对应的最小二进制数为循环左移5位得到的00010011，对应的RRLBP特征为19.从算法中不难看出，目标或目标局部的RRLBP特征具有较好的旋转不变性.基于上述算法，以本文提出的RRLBP为局部像素基本特征，参照标准Meanshift算法对跟踪框内的图像块进行核化RRLBP直方图估计(为去除平坦区域对Mean-shift算法的影响，RRLBP特征为0的点不参与直方图的统计).图4(a)、(b)给出了具有旋转变化和光照变化的2张手部图像以及相应的RRLBP特征图.图4(c)、(d)为相应的RRLBP核化直方图.从图中可以看出，两幅图像的直方图几乎没有变化，相关系数达到0.987 8.这说明本文提出的RRLBP特征具有较强的旋转不变性和对光照条件变化的鲁棒性.

图4 RRLBP特征提取结果

2.3 基于BWH的自适应特征融合

利用照度不变性色彩特征提取及LBP的纹理特征提取的方法可以实现目标色彩特征与纹理特征的提取.然而在Mean-shift算法框架下每个像素只能被赋予一个权值w(xi)．因此需要对特征进行融合.本文算法提取的色彩特征和纹理特征具有较强的互补性，其目的在于增强算法对不同目标和背景的适应性.例如当目标色彩与背景色彩有明显区别时，应以色彩特征为主进行跟踪;而在二者的纹理特征区别比较明显时，则对纹理特征赋予更大权重.基于上述考虑，本文提出了一种基于BWH(background-weighted histogram)算法的自适应特征融合方法.

BWH最早用于去除由于目标初始化不准确造成的背景像素对目标模板直方图的影响［16］.本文则利用BWH算法对不同特征进行权值调整.设目标模板直方图为 {qu}u=1，2，…，m，当前帧目标候选区域直方图{pu}u=1，2，…，m，背景模板直方图为{ou}u=1，2，…，m，则修正后的目标模板直方图{u}u=1，…，m可由式(3)得到

其中

式中:o*为背景模板直方图{ou}u=1，2，…，m的非零最小值，经过上述修正，目标模板直方图中与背景模板直方图相似的特征成分将会被抑制．分别对色彩特征直方图和纹理特征直方图进行上述操作，修正后的两种特征的目标模板直方图分别记为．对于某个给定的像素xi，若其色彩特征值为u*，纹理特征值为v*．则其权值w(xi)为

其中

在实际操作中，背景模板直方图通过统计图5中的大框与小框之间的回字形区域得到．图5中的第二行给出了特征融合前后的像素权值空间分布图．其中图5(a)、(c)为直方图修正前基于色彩特征和纹理特征的像素权值分布图图5(b)、(d)为直方图修正后的两种特征对应的像素权值分布(x);图5(e)为特征融合后最终得到的w(x)的分布．从图5(a)可以看出，在直方图修正前，背景的绿色区域的像素权值很大;图5(c)中基于LBP特征的目标与背景边界区域的像素权值也较高;经过修正后，基于色彩特征的像素权值分布主要集中在目标身上的方框区域(区别于草地的浅绿色)，而基于LBP特征的高权值像素则主要集中在目标球衣上的数字区域．从图5(e)给出的融合结果可以看出，两种特征的数值大小比例比较合理，球员背后的数字区域权值较高，从而避免了球衣和草地颜色相近造成的混淆．这说明本文提出的基于BWH的特征融合方法具有较强的自适应调节能力，能够自动选择合理的加权比例以实现目标与背景的区分．

图5 特征融合结果

3 迭代搜索与在线模板更新

Mean-shift算法在每一帧的跟踪过程中，使用迭代更新像素加权中心的方式实现目标搜索.然而当目标或背景特征分布比较复杂，或目标自身发生形变以及遮挡现象时，传统的Mean-shift算法难以保证算法的鲁棒性，容易发生基于累积误差的漂移现象.为了解决上述问题，本文在传统的Mean-shift算法框架下加入了基于直方图相似度校验的迭代搜索策略以及基于直方图差异空间分布图的模板更新策略.

3.1 目标搜索策略

传统Mean-shift算法的搜索步骤是计算当前跟踪框内像素的核化加权中心xc，将跟踪框的几何中心x0移动加权中心xc，重复上述过程直至xc=x0．然而在实际过操作过程中，经常会出现迭代难以收敛和跟踪框漂移现象．为此，本文提出了基于直方图相似度校验的迭代搜索策略，具体算法步骤如下:

1)根据式(6)计算当前跟踪框内图像的修正色彩直方图

3)按照传统Mean-shift算法将跟踪框中心移动至当前框内像素加权中心，重复步骤1和2.若重复过程中得到的直方图总相似度S从第i次搜索开始连续3次呈现下降趋势，则将跟踪框移动至第i次的中心位置xi与第i-1次的中心位置xi-1连线的中点，并随机加上1～2个像素的扰动．

4)重复上述步骤，直到跟踪框位置收敛或达到最大迭代次数则停止搜索.

3.2 遮挡检测

在模板更新策略的设计方面，需要考虑两个基本问题，即“何时需要更新模板”以及“如何更新模板”.一般来讲，当目标的表观特征发生变化时需要更新模板，然而在实际问题中，目标表观特征的变化既可能是目标自身的变化、光照条件变化或摄像机视角变化引起的，也可能是由遮挡现象引起的.因此如何区分二者成为跟踪问题中的一个难题.

式(7)的本质是寻找面积比例增加最快的某种色彩．显然新加入的遮挡物会产生较大的θu．然而单纯依靠式(7)仍然不能完善的解决遮挡现象与自身形变的区分．以人员跟踪为例，目标在行走过程中可能突然转身，由于其衣服的色彩前后不同造成某种全新的色彩在跟踪框中所占比例突然增大，又或者是彩色光照条件的变化引发目标表观特征中的色彩分量的比例发生变化．为解决上述问题，定义直方图差异空间分布图φ(x)．设点x的色彩特征为Ⅰ(x)，Ⅰ(x)的取值为1，2，…，m．令

显然新加入的色彩将会在空间分布图φ(x)具有较高的灰度．图6给出了遮挡现象发生时的检测结果．图6(a)为视频中发生遮挡现象的一帧图像，方框区域为跟踪结果．图6(b)为直方图差异空间分布图φ(x)．从中可以看出遮挡物(书籍)区域的直方图差异明显高于目标及其他背景区域．图6(c)为直方图差异θu．从中可以看出对应于遮挡物的蓝色分量数值远高于其他分量．基于上述结果，本文综合直方图总相似度S、直方图差异θu以及直方图差异空间分布图φ(x)3个指标对遮挡现象与自身变化进行区分．将φ(x)的灰度加权中心与几何中心的距离记为d．则以下3个条件同时满足时，判为遮挡现象．

条件1S＜TS，TS为相似度阈值，一般取0.6～0.7．

条件2 max(θu)＞Tθ，Tθ为直方图差异阈值，一般为跟踪框像素个数的1/50～1/25．

条件3d＞Td，Td为距离阈值，一般取值为跟踪框对角线长度的0.1～0.5倍．

根据图1的算法流程，首先判断是否发生遮挡.如发生遮挡则不更新模板，否则对模板进行更新.需要注意的是本文算法共有4个模板，分别为:目标色彩直方图模板，目标纹理直方图模板，背景色彩直方图模板，背景纹理直方图模板.4个模板的更新算法均相同，设t时刻的待更新模板为H(t)，当前跟踪结果对应的模板为L(t)，则更新公式为

式中:一般ρ取2，以使新进入的模板具有更大的权重，从而提高算法对目标形变的跟踪能力.将本文提出的特征提取与融合算法以及迭代搜索算法带入传统Mean-shift跟踪算法框架，并添加遮挡判断与模板更新环节.实现对具有自身形变的目标的鲁棒跟踪.

图6 遮挡现象检测结果

4 实验与分析

为测试本文方法的跟踪性能，作者从多篇相关文献和互联网上搜集了8段比较有代表性的视频(Animal、 Basketball、 Soccer、 Singer、 Skating1、Skating2［16］，Footbal［17］，Tabletennisl(CIPR SIF Sequence数据库［18］)).时长从3 ～795 s不等;帧率从23～29 fps不等;单帧分辨率从352×240～1280×720不等.并选取了加入BWH机制的Mean-shift算法(简称 BWH+MS)［19］、OAB 算法［1］、MIL 算法［3］3种性能较好的跟踪算法进行比较.所有算法均在Window7，64位操作系统下运行，电脑配置为内存 4 G，Intel Corel，i7-2720QM CPU 2.20G.其中本文方法和BWH+MS的方法在Matlab 2012a平台运行;OAB和MIL算法则使用作者提供的源代码在VC2005平台运行.

图7给出了4种算法对“Basketball”视频中部分关键帧的跟踪结果.可以看出:OAB算法在42帧开始已经出现了明显的跟踪漂移现象;MIL算法约在451帧左右出现漂移，并迅速转移至另一名球员身上，这是算法对于同色遮挡现象的处理能力不足导致的;在第1 036帧，由于闪光灯作用，单帧图像照度突然变化，恰在此时待跟踪目标与另一名同色球衣的球员相邻，因此BWH+MS算法的跟踪框转移到了另一名球员身上;在4种算法中只有本文算法能够完整地跟踪到目标，直到视频结束.这说明本文算法对于遮挡，同色干扰以及照度突变等现象有较强的抵抗能力.

图7 Basketball视频跟踪结果对比

图8给出的“Skating1”视频是目标跟踪领域经典难题之一.主要难点在于目标运动速度不稳定，背景复杂、光照条件变化快速且剧烈，尤其是视频的后半段目标几乎完全进入阴影区域，对于算法鲁棒性的要求非常高.从图8给出的实验结果看，MIL算法和OAB算法在舞台灯光的干扰下，先后在第250帧和第435帧丢失了目标.从第435～890帧，OAB算法始终将地灯错认为目标，直到真正的目标偶然经过该区域对地灯造成了遮挡，才使得跟踪框重新回到目标身上，之后约在1 470帧左右由于背景照度剧烈下降导致目标丢失，直到视频结束.BWH+MS算法在第1 069帧第一次丢失目标，主要原因是由于滑冰者右脚白色冰鞋扬起造成跟踪框漂移，之后搜索陷入局部最小，导致跟踪失败.本文方法则始终保持良好的跟踪效果，直至视频结束.这一结果在现有的跟踪算法中极为少见，说明本文算法对于上述复杂背景条件和各类干扰的处理能力较强.

图8 Skating1视频跟踪结果对比

由于本文算法中在初始化和算法执行过程中(模板更新策略)存在一定的随机性，为了得到具有统计意义的实验数据，采用4种算法对每段视频重复10次跟踪过程，每次的初始跟踪框的位置和大小均进行随机小幅度调整.表1给出了10次平均成功跟踪帧数以及10次中成功完成跟踪直至视频结束的次数.从结果中可以看出本文方法对于8段中6段视频都能较好完成跟踪，对于比较困难的“Skating1”和“Skating2”两段视频的跟踪成功率也在50%以上.而BWH+MS、OAB以及MIL对于8段视频中的4～5段几乎都无法完成跟踪，对于比较困难的 Skating1、Skating2和Singer则在10次测试中从未成功完成过跟踪任务.通过比较可以看出，本文算法具有较强的鲁棒性和较高的准确性.

表1 跟踪结果数据统计 帧/次数

5 结语

视频目标跟踪是计算机视觉领域的经典问题之一，之所以历经数十年始终保持研究热度是由于视频跟踪问题本身的复杂性.与传统的目标检测和识别问题不同，在实际应用中待跟踪目标和背景的表观特征经常会发生快速且剧烈的变化.这些现象对跟踪算法的鲁棒性和快速适应能力提出了极高的要求.本文方法充分考虑到这些困难，将Mean-shift算法、多特征融合、鲁棒搜索以及模板更新等多种算法策略结合在一起，取得了比较好的跟踪效果.

然而本文仍存在一些问题有待改进，首先是算法的参数较多，不易调节和操作;其次是算法没能实现跟踪框大小的自动调节，对于由完全遮挡造成的目标消失现象也未给出全面的解决方案.未来的工作将围绕上述问题展开，并将跟踪算法应用于某一特定任务，取得应用成果.

［1］GRABNER H，BISCHOF H.Online boosting and vision［C］//Computer Society Conference on Computer Vision and Pattern Recognition.New York:IEEE，2006:260-267.

［2］GRABNER H，GRABNER M，BISCHOF H.Real-time tracking via on-line boosting［C］//British Machine Vision.Edinburgh:Springer，2006:47-56.

［3］BABENKO B，YANG Ming-Hsuan，BELONGIE S.Robust object tracking with online multiple instance learning［J］. IEEE Transactionson Pattern Analysisand Machine Intelligence，2011，33(8):1619-1632.

［4］YONG Rui， CHENG Yunqiang. Betterproposal distributions:object tracking using unscented particle filter［C］//IEEE ComputerSocietyConferenceon Computer Vision and Pattern Recognition.Redmond:IEEE，2001:786-793.

［5］TEHRANI N H，TAKEUCHI A，MITA S，et al.On-road multivehicle tracking using deformable object model and particle filter with improved likelihood estimation［J］.Intelligent Transportation Systems，IEEE Transactions on，2012，13(2):748-758.

［6］SANTHOSHKUMAR S，KARTHIKEYAN S，MANJUNATH B S.Robust multiple object tracking by detection with interacting markov chain monte carlo［C］//IEEE International Conference on Image Processing.Melbourne:IEEE，2013:2953-2957.

［7］TIAN Jun，QIAN Jiansheng，LI Shiyin，et al.Visual tracking with adaptive multi-cue fusion particle filter［J］.Optics and Precision Engineering，2010，18(10):2254-2261.

［8］DORE A，SOTO M，REGAZZONI C S.Bayesian tracking for video analytics［J］.Signal Processing Magazine，2010，27(5):46-55.

［9］COMANICIU D，RAMESH V，MEER P.Real-time tracking of non-rigid object susingmean shift［C］//IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Hilton:IEEE，2000:142-149.

［10］DU Kai，JU Yongfeng，JIN Yinli，et al.MeanShift tracking algorithm with adaptive block color histogram［C］//ConsumerElectronics， Communications and Networks (CECNet)，2012 2nd International Conference on.Yichang:IEEE，2012:2692-2695.

［11］WANG Daihou，WANG Changhong，QU Zhenshen.Adaptive model mean shift tracking［C］//Fifth International Conference on Machine Vision(ICMV 12).International Society for Optics and Photonics.Wuhan:SPIE，2013:878403-878405.

［12］YILMAZ A，LI X，SHAH M.Contour-based object tracking with occlusion handling in video acquired using mobile cameras［J］.Pattern Analysis and Machine Intelligence，IEEE Transactions on，2004，26(11):1531-1536.

［13］JEAN J H，LIAN F L.Robust visual servo control of a mobile robot for object tracking using shape parameters［J］.Control Systems Technology，IEEE Transactions on，2012，20(6):1461-1472.

［14］OJALA T，PIETIKÄINEN，HARWOOD D.Performance evaluation of texture measures with classification based on Kull back discrimination of distributions［C］//Proceedings of the 12th IAPR International Conference on Pattern Recognition.Israel:IEEE，1994:582-585.

［15］SALBERG A B，HARDEBERG J Y，JENSSEN R.Rotation invariant image description with local binary pattern histogram fourier features［C］//ISCIA 2009 Proceedings.Heidelberg:Springer，2009:61-70.

［16］KWON J，LEE K.Visual tracking decomposition［C］//IEEE Computer Society Conference on Computer Vision and Pattern Recognition.San Francisco:IEEE，2010:1269-1276.

［17］COMANICIU D，MEMBER V，MEER P.Kernel-based object tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25(5):564-575.

［18］HOSSEINI M S，PLATANIOTIS K S.Temporal derivatives in compressed video sensing［C］//MMSP 2012 IEEE 14th International Workshop on.Banff，AB:IEEE，2012:31-36.

［19］JEYAKAR J，BABU R V，RAMAKRISHNAN K R.Robust object tracking with background-weighted local kernels［J］.Computer Vision and Image Understanding，2008，112(1):296-309.