0 引言

　　目标跟踪是计算机视觉领域的一个重要研究方向，在智能监控、智能交通、视频检索和人机交互等方面具有重要的应用价值。同时，目标跟踪也引起了国内外学者的广泛关注和研究，提出了多种目标跟踪算法。但是由于视频中目标的形变、光照变化、遮挡、背景混淆等因素的影响[1-4]，创建一个能够抵抗外界因素干扰，并且具有鲁棒性和高效性的目标跟踪算法，仍然是一项极具挑战的任务。

　　目标外观模型的建立是目标跟踪算法的一个重要组成部分，一个高效的且合适的外观模型能大大提高目标跟踪算法的性能[5-8]。文献[3]利用分块的策略来建立待跟踪目标的外观模型，用以处理目标姿势的变化和部分遮挡问题。文献[7]对目标进行稀疏表示，能够很好地处理部分遮挡、光照和姿势的变化。文献[9]同时利用目标和背景区域的特征，运用多个弱分类器增强的算法进行目标的跟踪。文献[10]基于图像颜色特征和粒子滤波算法来进行目标跟踪，虽然颜色特征的提取比较容易，但是当跟踪目标的颜色和背景颜色非常相近时，就会导致跟踪的失败。文献[11-12]提出基于压缩感知理论的跟踪算法，并且证明，从高维尺度图片中随机提取的低维特征可以有效地保留图片内在的辨别能力，使得目标跟踪过程实现起来更加方便。文献[13-16]中基于多实例学习框架提出的跟踪算法，可以有效地处理目标跟踪中正样本位置模糊问题。这些跟踪方法都是针对单目标设计，对于多目标跟踪的研究还相对较少，然而现实生活中，很多情况下需要同时跟踪多个目标。

　　通常，在复杂环境中的多目标跟踪问题往往充满了更多不确定性因素[17]，例如目标的消失与出现、目标的重叠与分离。进行多目标跟踪，首先自动检测出所感兴趣的目标，然后对这些目标进行特征表示，建立外观模型，最后运用搜索策略在视频序列中搜索定位目标，同时伴随目标变化不断更新模型。鉴于在目标发生遮挡或漂移的情况下，局部特征表现出的优势，本文采用形状上下文特征[18]建立目标的外观模型。由于实际问题的复杂性，目标跟踪面临的多是非线性非高斯问题，粒子滤波算法在解决非线性非高斯问题上具有很大优越性，因此被广泛应用于目标跟踪领域[10，19-20]。本文结合形状上下文和粒子滤波算法，提出一种基于形状上下文特征和粒子滤波的多目标跟踪算法。实验证明本文提出的算法在实时性和准确性方面都有优势。

1 目标检测

1.1 自适应增强检测算法

　　级联的自适应增强检测算法[21]最初用于人脸检测，效果显著。其主要思想是，首先对多个弱分类器根据其区分正负样本的能力进行权值分配，为分类效果好的弱分类器分配相对大的权值，反之给予小的权值；其次把分类效果好的弱分类器组合成强分类器，然后根据其分类效果重新分配新的权值，如此循环直至形成分类效果鲁棒的强分类器；最后，用训练好的强分类器对筛选好的haar特征进行目标的检测与分类。本文采用自适应增强检测算法，训练一个级联的分类器进行目标检测。在待检测场景中采集包含目标的众多图像区域，归一化到相同尺寸作为训练正样本。为了加快正样本采集的速率，需使用一种简单高效的策略，即在靠近中心的位置以低强度提取样本，外围区域以高强度提取样本。需要注意的是，以这种策略产生的样本数据进行训练不是最理想的，在边缘处会产生一些错分的正样本。而人工选择一个更大的训练集会训练出更好的增强的分类器，但是在场景混乱或目标重叠区域仍然会失效。负样本则从目标周围不包含目标的背景区域中采集。

　　图1展示了自适应增强检测算法在冰球场数据集中的检测结果。(a)和(b)为自适应增强检测算法对于冰球运动员进行的精确检测结果。不难看出，自适应增强检测算法在冰球场场景中具有很好的检测效果。其中，对于视频中的新增目标、重叠目标和不同大小的目标，该算法也实时地给出了准确的检测。

　　1.2 引入自适应增强检测算法的目的

　　对运动目标进行跟踪，经常会遇到某个目标进入或离开场景的情况，一个好的多目标跟踪算法需要能够准确检测出目标何时离开或进入场景，并删除或添加目标跟踪框。因此本文在跟踪中引入自适应增强检测算法来解决这个问题，利用自适应增强检测算法检测出可能包含目标的小区域，结合粒子滤波最终确定目标位置。实验证明，加入检测算法能够有效避免目标偏移，特别是，当运动目标进入和离开运动场景时，都可以很好地对目标进行检测定位和跟踪目标框的移除，实现了对运动目标的实时跟踪。

2 基于形状上下文和粒子滤波的多目标跟踪

　　本节详细介绍基于形状上下文和粒子滤波的多目标跟踪算法。在目标跟踪的过程中，首先提取目标区域的形状上下文特征作为目标模板，然后搜索候选目标区域，比较其形状上下文特征与目标模板的相似性，最相似的候选目标区域即确定为目标的当前位置。

　　2.1 形状上下文特征提取

　　目标跟踪问题可以被看作是目标模板与候选目标之间的匹配问题。形状上下文算法在衡量形状相似性和形状匹配方面表现出良好的特性，因此本文使用形状上下文描述符表示目标的外观模型。

　　采用边缘检测算法检测出被跟踪目标的轮廓，从中采集n个特征点来表示目标的整个形状结构，采集的特征点越多，越能展现目标的形状细节。这些特征点有些分布在目标轮廓上，有些分布在目标轮廓内部。图2展示了特征点的采集过程。图2(a)为视频中的一帧原始图像，图2(b)是对原始图进行边缘检测的结果，图2(c)中方框里的点为采集的目标的特征点。

　　对于形状[18，22]中的任一特征点pi，通过计算其余特征点在每个组距的分布，建立其在极坐标下的直方图hi，如图3所示，hi定义如下：

　　hi(k)=#{q≠pi：(q-pi)∈bin(k)}(1)

　　第一个形状中的特征点pi与第二个形状中的特征点qj之间的匹配成本为：

　　其中，K表示组距的数目，hi和hj分别表示在pi和qj处的形状上下文直方图。

　　两个形状匹配的总成本可由最小化这些特征点的匹配成本得到：

　　该最小化问题可以采用Hungarian方法[23]在O(N3)的时间内解决，但是这对于目标跟踪问题来说时间消耗太大，因此本文使用的改进的形状上下文特征[24]来减少时间的开销。假设目标模板包含s个形状上下文直方图，从候选目标中随机地选取r个形状上下文直方图，则目标模板与候选目标的匹配成本转化该s个目标模板形状上下文直方图与r个候选目标形状上下文柱状图之间的匹配成本。通常s大约是r的20倍，因此该方法的速度将会比之前大大提高。

　　如图3所示，(a)是无遮挡的图像，(b)是有遮挡的图像，(c)是用来计算形状上下文柱状图的极坐标，(d)、(e)和(f)是分别表示矩形、圆形和三角形处的形状上下文柱状图。由图可以看出，矩形点和圆点所表示形状上下文柱状图非常相似，在原图像中也是一致对应的点，这样形状上下文特征就可以很好地处理遮挡问题。

　　2.2 粒子滤波

　　粒子滤波由于其在解决非线性非高斯问题的优越性，被广泛应用于目标跟踪中。粒子滤波的思想基于蒙特卡洛方法，采用一组随机状态粒子来逼近状态的后验概率密度函数。令Xt表示t时刻的目标状态，Yt表示t时刻的观测值，则在贝叶斯框架下，后验概率密度p(Xt|Y1:t)可通过如下递归过程来获得[10]：

　　其中，Y1:t-1={Y1，Y2，…，Yt-1}，p(Yt|Xt)表示观测模型[25]。

　　粒子滤波算法包括预测和更新两个操作阶段。预测阶段，由1～(t-1)时刻的观测值估计t时刻的状态：

　　其中，后验概率分布p(Xt|Y1:t)可由被赋予不同重要性权重(i-1，…，n)的n个粒子(i=1，…，n)近似估计得到，并且，这n个粒子服从重要性分布q(Xt|X1:t-1，Y1:t)，其权重。

　　粒子的权重通过以下公式进行更新：

　　通常认为目标状态满足马尔科夫性，且状态转移与观测值相互独立，则重要性分布可简化为一阶马尔科夫过程q(Xt|X1:t-1，Y1:t)=p(Xt|Xt-1)，相应地，权重更新公式变为。为避免粒子的退化而根据权值的大小对粒子进行重采样。

　　本文中使用矩形框来表示目标[26]，粒子在t时刻的状态被定义为Xt=(xt，yt，st)，xt和yt表示矩形框的中心坐标，st表示矩形框的尺寸。粒子的状态转移采用二阶自回归模型：

　　其中，V表示高斯噪音，分布为V～N(0，)。

　　2.3 算法的执行过程

　　算法的具体执行过程如下：

　　(1)利用自适应增强检测算法对于动态的运动目标进行检测。

　　(2)粒子初始化：设置每个目标的粒子状态和权重。

　　(3)预测：根据状态转移公式预测粒子状态。

　　(4)提取特征：根据式(1)提取每个目标的每个粒子的形状上下文特征。

　　(5)更新：更新粒子权重，并对权值进行归一化。依据最大后验准则，确定t+1时刻的目标位置。

　　(6)粒子重采样：根据权重的大小进行粒子的重采样过程。

　　(7)t=t+1，转到步骤(3)。

3 实验分析

　　本文选取了如下两个应用场景对提出的多目标跟踪算法进行实验，一个是冰球运动的比赛现场；另一个是交叉路口的视频监控。

　　3.1 冰球运动场的实验结果

　　图4展示了本文提出的算法对于冰球运动员的比赛场景中的跟踪效果。从图中可以看出，该算法对每个目标的检测跟踪效果都很好，最重要的是，即使场景中出现的运动目标非常多以及环境稍微复杂的情况下，本算法可以成功地适应场景中发生的一些改变，并且可以对此及时做出调整和继续保持跟踪。可见该算法对于类似于运动员比赛的快速运动场景中的多目标跟踪具有一定的准确性和鲁棒性。

　　图4(a)显示一位运动员将要进入拍摄场景，图4(b)显示两帧后该运动员进入场景后的跟踪结果。可以看出，当新目标将要进入比赛场景中时，自适应增强算法可以在两帧的时间内快速检测出该目标即将进入比赛场景中，在自适应增强检测算法对此做出目标检测后，就可以立即指派粒子对这个新的运动员进行定位和跟踪。图4(c)和4(d)展示了运动员离开拍摄场景的跟踪效果。可以看出，当自适应增强算法检测出该运动员要离开场景时，算法可以迅速做出相应的回应，放弃对他的检测和跟踪。

　　3.2 交叉路口的实验结果

　　图5展示了本文提出的算法对交叉路口的行人进行检测跟踪效果，可以看出，无论是在新的行人进入，还是两人的重叠与分离的情形，本文的算法都能进行比较准确的跟踪。从图5(a)中可以看出，在行人较多，背景较为复杂的情况下，该算法依然能够将监控区域内行人全部检测出来并进行跟踪。图5(b)中当有新的目标进入时，该算法能准确检测出目标并进行跟踪。图5(b)和5(c)中右边两个行人由重叠的到发生分离的过程，也可以被很好地检测出来，然后把目标框分离成两个跟踪框，并且做出相应目标的跟踪。从图中还可以看出，当中间的行人经过电线杆遮挡时，对于该行人的跟踪依然存在且继续，并没有发生目标跟丢情况，可见本文的算法也能一定程度处理目标遮挡问题。

　　从上述实验可以看出，本文提出的基于形状上下文和粒子滤波的多目标跟踪算法加入了自适应增强的检测算法对多个目标进行检测跟踪，具有很好的自适应检测能力和目标跟踪的功能。本文的算法能处理目标进出场景的情形，对于应用场景的适应性较强，而且能处理遮挡和复杂背景问题。

4 总结

　　本文提出的基于形状上下文和粒子滤波的多目标跟踪算法充分利用自适应增强检测算法的优势，结合形状上下文特征，融入粒子滤波方法中，能有效处理目标进入与离开场景的问题和目标重合与分离的问题，在单一背景和复杂背景下都能进行较为准确的跟踪，还能有效处理部分遮挡问题。下一步研究的重点是在保证实验效果的同时，进一步提高算法的执行效率。

参考文献

　　[1] GODEC M，ROTH P M，BISCHOF H.Hough-based trackingof non-rigid objects[J].Computer Vision and Image Under-standing，2013，117(10)：1245-1256.

　　[2] SONG L，WANG Y.Multiple target counting and tracking using binary proximity sensors: bounds, coloring, and filter[C].Proceedings of the 15th ACM International Symposium on Mobile Ad Hoc Networking and Computing，ACM，2014：397-406.

　　[3] ADAM A，RIVLIN E，SHIMSHONI I.Robust fragments-based tracking using the integral histogram[C].Computer Vision and Pattern Recognition，2006 IEEE Computer Soci-ety Conference on.IEEE，2006，1：798-805.

　　[4] WU Y，LIM J，YANG M H.Online object tracking：A ben-chmark[C].Computer Vision and Pattern Recognition (CVPR)，IEEE Conference on.IEEE，2013：2411-2418.

　　[5] ROSS D，LIM J，LIN R S.YANG M H.Incremental learning for robust visual tracking[J].International Journal of Com-

　　puter Vision，2008，77(1)：125-141.

　　[6] GRABNER H，LEISTNER C，BISCHOF H.Semi-supervised on-line boosting for robust tracking[M].Computer Vision-ECCV 2008，Springer Berlin Heidelberg，2008：234-247.

　　[7] MEI X，LING H.Robust visual tracking using l1 minimiza-tion[C].Computer Vision，2009 IEEE 12th International

　　Conference on，IEEE，2009：1436-1443.

　　[8] KALAL Z，MATAS J，MIKOLAJCZYK K.Pn learning：Boot-strapping binary classifiers by structural constraints[C].Computer Vision and Pattern Recognition(CVPR)，2010 EEE Conference on，IEEE，2010：49-56.

　　[9] AVIDAN S.Ensemble tracking[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，2007，29(2)：261-271.

　　[10] PREZ P，HUE C，VERMAAK J，et al.Color-based probabilistic tracking[M].Computer vision-ECCV 2002，Springer Berlin Heidelberg，2002：661-675.

　　[11] ACHLIOPTAS D.Database-friendly random projections: Johnson-Lindenstrauss with binary coins[J].Journal of Computer and System Sciences.2003，66(4)：671-687.

　　[12] CANDES E J，TAO T.Near-optimal signal recovery from mation Theory，IEEE Transactions on，2006，52(12)：5406-5425.

　　[13] ZHOU Q H，LU H，YANG M H.Online multiple support instance tracking[C].Automatic Face & Gesture Recogni-tion and Workshops(FG 2011)，2011 IEEE International Conference on，IEEE，2011：545-552.

　　[14] BABENKO B，YANG M H，BELONGIE S.Robust object tracking with online multiple instance learning[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，2011，33(8)：1619-1632.

　　[15] LEISTNER C，SAFFARI A，BISCHOF H.Miforests: multi-ple-instance learning with randomized trees[C].European Conference on Computer Vision(ECCV).Crete，Greece.2010，1：29-42.

　　[16] ZEISL B，LEISTNER C，SAFFARI A，et al.On-line semimultiple-instance boosting[C].Computer Vision and Pattern Recognition(CVPR)，2010 IEEE Conference on.IEEE，2010：1879-1879.

　　[17] INTILLE S S，DAVIS J W，BOBICK A F.Real-time closed-world tracking[C].Computer Vision and Pattern Recognition，1997.Proceedings，1997 IEEE Computer SoConference on，IEEE，1997：697-703.

　　[18] BELONGIE S，MALIK J，PUZICHA J.Shape matching andobject recognition using shape contexts[J].Pattern Analysisand Machine Intelligence，IEEE Transactions on，2002，24(4)：509-522.

　　[19] ISARD M，BLAKE A.Condensation—conditional density propagation for visual tracking[J].International Journal of Computer Vision，1998，29(1)：5-28.

　　[20] RUI Y，CHEN Y.Better proposal distributions：object tracking using unscented particle filter[C].IEEE Conference on Computer Vision and Pattern Recognition(CVPR).2001，2(2)：786-793.

　　[21] VIOLA P，JONES M.Rapid object detection using a boostedcascade of simple features[C].IEEE Conference on Com-puter Vision and Pattern Recognition.2001，1(1)：511-518.

　　[22] GUI Y，SU A，DU J.Point-pattern matching method usingSURF and shape context[J].Optik-International Journal for Light and Electron Optics，2013，124(14)：1869-1873.

　　[23] PAPADIMITRIOU C H，STEIGLITZ K.Combinatorial opti-mization：algorithms and complexity[M].Courier Dover Publications，1998.

　　[24] MORI G，BELONGIE S，MALIK J.Efficient shape match-ing using shape contexts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(11)：1832-1837.

　　[25] MEI X，LING H.Robust visual tracking and vehicle clas-sification via sparse representation[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，2011，33(11)：2259-2272.

　　[26] QU M，PANG E，LIU R，et al.Object tacking based on shape context features and particle filter[J].Journal of Information and Computation Science，2012，9(7)：1905.