Mean Shift算法在目标跟踪领域的应用研究

Application of Mean Shift Algorithm in Target Tracking Field

摘要: 目标跟踪物在运动过程不断移动以及在运动过程中被遮挡的问题一直是研究的一个焦点和重点问题。本文通过阐述Mean Shift算法原理，研究了Mean Shift算法对目标物的快速跟踪过程。并通过两组实验分别对运动目标物及在遮挡条件下运动目标物进行跟踪。第一组实验中，选取移动的物体篮球为目标物，并通过Mean Shift算法，不断迭代跟踪新的篮球位置，实现对篮球的跟踪。第二个实验中，选取移动的人为目标物，目标物在移动过程中被其他人遮挡，通过将颜色灰度特征应用到Mean Shift算法中，减少了其他物体对目标物跟踪的干扰，从而实现不断跟踪新目标。实验结果证明，Mean Shift算法能够快速、有效地实现目标跟踪。

Abstract: It is still a challenge to study a real-time and accurate algorithm to solve the problem of target tracker moving constantly and being blocked in the process of movement. Mean Shift algorithm is simple in calculation and can quickly track the target. The Mean Shift algorithm principle is expounded, and two groups of experiments are carried out to track moving targets and moving targets under occlusion condition respectively. The experimental results prove that Mean Shift algorithm can realize fast and effective tracking.

1. 引言

目标跟踪在计算机视觉领域有着非常重要的应用 [1]。对于目标物的跟踪，如果单纯靠人眼识别观察，不仅耗费大量时间，而且可能会出现差错。视频目标跟踪，就是确定视频序列中每幅图像运动目标的位置 [2]。随着科学技术的发展，视频目标跟踪技术已经被广泛应用于智能视频监控 [3]、现代化军事 [4]、航空航天 [5]、智能交通系统 [6]、人机交互 [7] 以及工业生产、检测诊断等众多领域 [8]。

在进行目标跟踪时，目标速度过快，跟踪的实时性问题是跟踪技术的难点 [9]，运动跟踪算法的优劣极大影响跟踪结果的好坏。Mean Shift算法是一种基于迭代收敛到概率密度的局部极大的非参数估计算法，减少了跟踪算法的计算量 [10]，具有实时性好，对目标的旋转、变形、以及边缘状态遮挡不敏感的优点 [11]。

而在复杂的运动环境下，物体被遮挡等其他因素干扰对目标的区分与跟踪就显得困难 [12]。通过KCF算法可将灰度特征换成多通道的彩色特征，即可实现在跟踪过程中利用颜色特征，实现对目标物运动甚至遮挡条件下的跟踪。

本文通过对Mean Shift算法的研究，将算法应用到目标跟踪技术中。通过两组实验，分别对运动物体以及运动物体在遮挡条件下进行目标跟踪。

2. Mean Shift目标跟踪算法

2.1. Mean Shift算法介绍

Mean Shift (均值漂移)是一种非参数概率密度估计的方法，一种最优的寻找概率密度极大值的梯度上升法，在解决计算机视觉底层过程中表现出了良好的鲁棒性和较高的处理速度。Mean Shift最早于1975年由Fukunaga等人在关于概率密度梯度函数的估计一文中提出 [13]。Mean Shift算法一般指的是一个迭代的步骤，即先算出当前点的漂移均值，移动该点到其漂移均值，然后以此为新的起始点，继续移动，直到满足一定的条件结束。

2.2. Mean Shift算法原理

假设在给定的空间中有n个样本点， $x_i$， $i=1,\cdots ,n$，则在x点的Mean Shift向量的基本形式定义为：

$M_h\left(x\right)=\frac{1}{k}{\displaystyle {\sum }_{x\in S_h}\left(x_i-x\right)}$ (1)

其中， $S_h$ 是一个半径为h的高维球区域，它是满足下面关系式的所有点的集合：

$S_{h\left(x\right)}=P\left\{y:{\left(y-x\right)}^{\text{T}}\left(y-x\right)\le h^2\right\}$ (2)

k表示的是在有多少个样本落在了上述的多样本区域中。如图1所示，大圆所圈定的范围是 $S_h$，小圆表示落入大圆区域的样本点 $x_i$，黑点代表Mean Shift的基准偏移中心x，箭头表示样本点 $x_i$ 相对于基准点的偏移向量。在式(1)中， $\left(x_i-x\right)$ 表示的是相关区域内的样本点相对于中心的偏移向量，所以计算得到的Mean Shift向量 $M_h\left(x\right)$ 是对落入区域内的所有样本点相对于中心偏移向量的平均值。由梯度的相关知识可知，非零概率密度函数的梯度总是指向概率密度函数增加最快的方向，所以平均基准点 $M_h\left(x\right)$ 会指向样本分布最多的区域，即概率密度函数的梯度方向。

Figure 1. Mean Shift schematic

图1. Mean Shift示意图

2.3. Mean Shift跟踪

因为Mean Shift向量总是指向概率密度函数的梯度方向，即概率密度增加的方向，因此通过Mean Shift向量反复迭代，会定义一条通往局部极值的路径。通过Mean Shift算法利用目标的颜色特征概率密度描述运动目标区域中心位于x的目标模型，在目标中心邻域搜索窗口内以相似性度量最大为原则，寻找最优的位于y的目标模型，使得两次移动距离小于某一阈值，以达到目标的真实位置，采用Bhattacharyya系数度量目标模型概率密度函数 ${\hat{q}}_u$ 和候选模型 ${\hat{p}}_u\left(y\right)$ 的相似程度。模型根据目标区域颜色特征的概率密度函数来描述：

目标模型：

$\hat{q}={\left\{{\hat{q}}_u\right\}}_{u=1,\cdots ,m}{\displaystyle {\sum }_{u=1}^m{\hat{q}}_u}=1$ (3)

候选目标：

$\hat{p}={\left\{{\hat{p}}_u\left(y\right)\right\}}_{u=1,\cdots ,m}{\displaystyle {\sum }_{u=1}^m{\hat{p}}_u\left(y\right)}=1$ (4)

目标模型概率密度函数：

${\hat{q}}_u=C{\displaystyle {\sum }_{i=1}^{n}k\left({\Vert x_i^{*}\Vert }^2\right)\delta \left[b\left(x_i^{*}\right)-u\right]C}=\frac{1}{{\displaystyle {\sum }_{i=1}^{n}k\left({\Vert x_i^{*}\Vert }^2\right)}}$ (5)

候选目标概率密度函数：

${\hat{p}}_u=C_k{\displaystyle {\sum }_{i=1}^{n}k\left({\Vert \frac{y-x_i}{h}\Vert }^2\right)\delta \left[b\left(x_i^{\text{*}}\right)-u\right]C_k}={\displaystyle {\sum }_{i=1}^{n_k}\frac{1}{k\left({\left|\left|\frac{y-x_i}{h}\right|\right|}^2\right)}}$ (6)

Bhattacharyya系数相似度测度：

$\hat{\rho }\left(y\right)=\rho \left[\hat{p}\left(y\right),\hat{q}\right]={\displaystyle {\sum }_{u=1}^m\sqrt{{\hat{p}}_u{\hat{q}}_u}}$ (7)

权重系数 $w_i$ ：

$w_i={\displaystyle {\sum }_{u=1}^m\sqrt{\frac{{\hat{q}}_u}{{\hat{p}}_u\left(y_0\right)}}\delta \left[b\left(x_i\right)-u\right]}$ (8)

新目标位置：

$\widehat{y_1}=\frac{{\displaystyle {\sum }_{i=1}^{n_k}{x}_i{w}_{i}g\left({\Vert \frac{\widehat{y_0}-x_i}{h}\Vert }^2\right)}}{{\displaystyle {\sum }_{i=1}^{n_k}{w}_{i}g\left({\Vert \frac{\widehat{y_0}-x_i}{h}\Vert }^2\right)}}g\left(x\right)=-k^{\prime }\left(x\right)$ (9)

其中u为目标的特征值，y为最优候选区域中心。 $\hat{\rho }\left(y\right)$ 越大，表示两模型越相似。为定位下一帧目标，应使每 $\hat{\rho }\left(y\right)$ 最大化。

将当前帧的候选目标的中心初始为前一帧目标中心 $\widehat{y_0}$，然后在其领域内搜索匹配目标，不断地从目标的当前位置 $y_0$ 移动到新目标位置 $\widehat{y_1}$，若Mean Shift向量 $\widehat{y_1}-\widehat{y_0}$， $\Vert \widehat{y_1}-\widehat{y_0}\Vert <\epsilon$ 则停止迭代，使得 $\hat{\rho }\left(y\right)$ 最大，直到候选区域与目标区域足够相似，此时目标区域中心位置会由 $\widehat{y_0}$ 移动到新位置 $\widehat{y_1}$，如图2。

Figure 2. Mean Shift tracking algorithm

图2. Mean Shift跟踪算法

3. 实验验证

物体在运动过程中，通过Mean Shift算法，验证运动的物体和运动物体在遮挡条件下的跟踪效果。实验采用视频为篮球场上物体的运动和足球场上人的运动。实验一中目标跟踪物选取为运动的篮球，实验二中目标跟踪物选取为穿红衣服的人。

3.1. 算法实现流程

首先，在一段视频序列中选取第一帧作为初始模型，框选目标跟踪物，通过Mean Shift算法迭代计算出目标的新位置，此位置作为下一次目标的新位置，以此类推，不断得到目标的新位置，如图3所示。

Figure 3. Program flow

图3. 程序流程

3.2. 实验结果

3.2.1. 运动物体的跟踪

Figure 4. Tracking of basketball in motion state

图4. 运动状态下篮球的跟踪

图4为多人在球场上打球，这里选取红色的篮球作为跟踪目标，其中有多个穿不同颜色衣服的人会对跟踪目标造成干扰，如灰色，红色，蓝色，黑色衣服。选取篮球为跟踪目标物，通过Mean Shift算法对该视频序列进行目标跟踪，图4为分别选取第1帧，第10帧，第21帧，第150帧的实验结果。在第1帧中，选取了红色的篮球为目标跟踪物，第1帧作为初始模型，通过Mean Shift算法得到目标的新位置，以此类推，不断迭代得到新的位置。第10帧中，篮球落到地上，实验结果表明这段时间通过Mean Shift算法判断的红色框与实际目标物相吻合，第21帧中篮球靠近人的手，并在之后被人投出，投出后的通过Mean Shift算法判断的红色框区域仍与篮球目标物吻合。实验结果验证，本算法能够实现对运动物体的准确跟踪。

3.2.2. 运动物体遮挡条件下的跟踪

Figure 5. Tracking of a moving person under occlusion

图5. 运动的人在遮挡条件下的跟踪

选取足球场上特定行人进行目标跟踪，如图5，实验中有身穿红衣服和黑衣服的人在足球场上进行走动，红衣服人与黑衣服人在移动过程中相互存在相互遮挡的情况，选取黑衣服的人进行目标跟踪。图5分别为第1帧，第15帧，第30帧，第60帧的实验结果。第一帧中选取目标模型，下一帧中，通过Mean Shift算法得到新的位置，并且将颜色灰度特征应用到Mean Shift算法中，减少了黑衣服人对红衣服人遮挡的干扰，通过Mean Shift算法不断迭代，得到目标物运动过程中的新位置，在移动过程中，如图5，第15帧及第30帧黑色衣服的人被红色衣服的人遮挡，实验结果中，通过Mean Shift算法判断的目标物红色框的新位置与实际目标物位置一致。遮挡结束后见第60帧，依然能够实现对红衣服的人的跟踪。实验证明，将颜色灰度特征应用到Mean Shift算法中，能够实现目标物在遮挡条件下的跟踪。

4. 结语

本文主要阐述并采用Mean Shift算法对目标物进行跟踪，通过两组实验，实验结果表明了Mean Shift在运动物体跟踪中能排除其他背景的干扰，可以准确地实现运动目标物的跟踪与运动目标跟踪物在遮挡条件下的跟踪。Mean Shift因其较为简单，复杂度不高的特性，能够简便快速地实现目标跟踪的效果。

基金项目

面向国际工程教育认证的机械类专业课程综合性实验体系构建与教学模式研究(西安交通大学校级：17ZX002)。

NOTES

^*通讯作者。