改进的Mean Shift跟踪算法在车辆跟踪上的应用

丁 磊，宫宁生，俞克强

(南京工业大学电子与信息工程学院，江苏 南京 211316)

在视频图像处理技术中，目标跟踪算法是一项关键技术，在视频监控、商场人流量监控和车辆监控等方面具有广泛的应用。目标跟踪算法的主要作用是估计出运动目标的位置。由于运动目标在连续帧图像中存在连续性的对应关系，因此在跟踪技术中只要找到这种对应的关系就能实现运动目标的跟踪。本文使用Mean Shift跟踪算法［1－3］实现对每帧视频图像中运动目标的跟踪。

Mean Shift跟踪算法是一种非参数密度估计方法，1975年Fukunaga等人［4］首次提出了 Mean Shift理论，而Yizong Cheng［5］对 Mean Shift理论进行了推广，将 Mean Shift算法成功的应用到视频图像处理中。Comaniciu等人［6］讨论了Mean Shift算法在运动目标跟踪中的应用，从而使得运动目标的跟踪可以实时进行。因此Mean Shift算法在目标跟踪方面取得了较好的效果。

在整个跟踪过程中，Mean Shift跟踪算法中使用的目标跟踪框的大小是固定不变的。但是视频序列中，运动目标的大小可能是变化的，特别是当运动目标由远及近时，运动目标逐渐变大，常常会因为跟踪框大小不变导致跟踪效果不好。

针对Mean Shift目标跟踪算法中存在的跟踪框大小不变的情况，本文采用结合背景帧差［7］的Mean Shift跟踪算法，从而自动地调整目标跟踪框的尺寸。文中将背景帧差提取的运动目标的位置信息和Mean Shift跟踪算法得到的位置信息做比较，如果两个位置的信息相符合，则将背景帧差提取的运动目标的尺寸表示为运动目标的跟踪框大小。本文的算法计算量不大，通过本文的改进算法，达到了优化跟踪效果的目的。

1 Mean Shift算法原理

视频图像序列中，首先应该预先选定目标检测区域，计算出初始帧的每个像素点在特征空间中每个特征值的概率，从而可以建立起目标模型。在后续的每帧图像中，计算出可能会存在目标的区域中所有像素点在特征空间中的特征值概率，从而可以建立起候选目标模型。因此，可以用相似性函数计算当前帧候选目标模型和初始帧目标模型的相似度，从而求解相似性函数的最大值，通过这种方法可以得到运动目标的Mean Shift向量，而求解得到的向量即为运动目标向正确位置移动的向量值。因为Mean Shift算法是具有收敛性的，所以可以使用迭代的方法得到在当前帧中运动目标的真实位置。

在运动目标区域中，Mean Shift算法将颜色空间分成m个子空间，从而可以计算出运动目标的初始模型和候选模型的概率密度函数。

1.1 目标模型的建立

对于初始帧图像目标区域内的所有像素点，可以计算得到在特征空间中特征值的概率密度值，运动目标模型中m个特征值的密度函数为

假定用 {xi}i=1，2，…，n表示目标模型中有 n 个像素点，则目标模型的特征值u=1，2，…，m的概率密度函数公式为

1.2 候选模型的建立

在后续的图像帧中的候选目标区域中，候选目标模型有m个特征值

候选目标的中心位置为y，候选目标区域的像素点用{xi}i=1，2，…，nh表示，则候选目标模型的特征值u=1，2，…，m的概率密度公式为

式中:Ch为归一化的常量。

1.3 目标模型和候选目标模型的相似性

在连续帧中，目标模型和候选目标模型的相似度可以通过相似性函数来判断，理想情况下，两个模型的概率密度分布是完全一致的。本文选择Bhattacharyya系数来判断目标模型和候选模型的相似度，则有

1.4 目标的定位

在当前帧中，可以先由前一帧目标的位置y0开始匹配最优化的目标位置，可以用y表示。计算候选目标模型的概率密度函数(y0)，对式(5)在)处进行一阶泰勒展开，此时Bhattacharyya系数为

由式(4)可得

式中:wi为候选目标区域的像素点权重。则有

核函数k(x)的中心位置从初始位置y0开始不断向新的位置移动，从而进行匹配，新的位置描述为

式中:g(x)=-k′(x)。

2 自适应目标跟踪框

在Mean Shift目标跟踪算法中，运动目标的跟踪过程中会出现跟踪框的大小固定不变的情况。当运动目标远离镜头时，目标变小，但是跟踪框大小不变，可能会对其他运动目标的跟踪带来干扰;当运动目标靠近镜头时，目标变大，但是跟踪框大小依旧不变，可能会出现目标跟丢的情况。

如图1所示，本文应用Surendra背景更新算法［8］获取背景，再通过背景差分法提取出运动目标，得到运动目标后，将此运动目标的位置信息和上文中Mean Shift跟踪算法得到的目标的位置信息做比较，如果两者相符合，则认为检测出的两个运动目标是同一个。记录Surendra背景更新算法提取出运动目标的位置信息(左端点xmin、右端点xmax、上端点ymin和下端点ymax)，从而得到目标的长和宽信息，最后用方框表示出运动目标的位置。在连续帧内，随着目标的运动，会发现运动目标的跟踪框的大小实时变化。

2.1 Surendra背景更新算法

在Surendra背景更新算法中，当算法处理的次数达到最大的迭代次数时，Surendra背景更新会停止，把取到的背景图像当作固定的背景，这不适合亮度有变化的场景。在本文中，取消设置最大迭代次数，使得Surendra背景更新算法一直在处理，从而得到实时的背景。Surendra背景更新算法流程图如图1所示。

图1 Surendra背景更新算法流程图

取第一帧图像f0作为初始背景B0，当前帧和前一帧的差分结果的二值化图像为Di

通过得到的两帧差值结果Di可知，背景更新可以由式(11)表示

式中:α为更新因子。

2.2 背景差分提取运动目标跟踪框

通过Surendra背景更新算法得到实时背景后，将当前帧图像fi和得到的背景Bi相减。如式(12)和式(13)所示，如果得到的差值Di小于阈值T，则认为是背景图像;反之，则认为是前景图像。

通过背景差分提取出运动目标后，可以得到目标的位置信息(左端点xmin、右端点xmax、上端点ymin和下端点ymax)，把两种方法得到的位置信息做比较，如果两者相符，则认为是同一目标;反之，则认为不是同一目标。如式(14)和式(15)可示，背景差分得到的运动目标中心坐标位置和长宽分别为

式中:(xi，yj)为运动目标所在像素点的坐标位置。

3 实验结果

本文采用TI公司的DM642数字信号处理器对采集到的D1格式的视频进行处理。在处理时，本文采用2块DM642处理器同时对Mean Shift算法和改进的Mean Shift算法进行视频帧图像的处理。图2表示的是Mean Shift目标跟踪算法的处理效果，图3表示的是改进的Mean Shift跟踪算法的处理效果。

对比两种算法在实际场景下的处理结果可以知道，运动目标由远及近的过程中，改进算法可以明确看出目标跟踪框是随着目标的变大不断变大的。因此，本文中的改进算法能很好地解决Mean Shift跟踪算法存在的跟踪框大小不变的问题，具有较好的效果;并且DM642处理器的处理速度也没有受到大的影响，可以保证本文的算法可以在DM642处理器上正常运行，实时地进行图像帧的处理。

4 总结

本文以Mean Shift目标跟踪算法来实现运动目标的跟踪，由于传统Mean Shift目标跟踪算法中存在跟踪框大小不变的情况，可能会导致在跟踪过程中目标跟丢的情况发生。本文提出了结合背景差分法来实现目标跟踪框的大小自适应变化，在实际的工程应用中，改进的Mean Shift跟踪算法在DM642上可以流畅地运行，算法的实时性可以保证。由于车辆的速度过快，从而导致跟踪框滞后于车辆的情况发生，对车辆的跟踪以及后续的车速的计算有一定的影响，但是影响不大。

［1］COLLONS R T.Mean－Shift Blob tracking through scale space［C］//Proc.2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.［S.l.］:IEEE Press，2003:234－240.

［2］王宇.基于Mean Shift的序列图像手势跟踪算法［J］.电视技术，2010，34(6):97－99.

［3］梁静，支琤，周军.基于Mean Shift的抗遮挡运动目标跟踪算法［J］.电视技术，2008，32(12):82－85.

［4］FUKUNAGE K，HOSTETLER L D.The estimation of the gradirent of a density function with application in pattern recognition［J］.IEEE Trans.Information Theory，1975，21(1):32－40.

［5］CHENG Y.Mean Shift，mode seeking，and clustering［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，1995，17(8):790－799.

［6］COMANICIU D，MEER P.Mean Shift:a robust approach toward feature space analysis［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，1999，24(5):603－619.

［7］胡彪，龚晓峰.基于改进背景差法的运动目标检测［J］.计算机工程与设计，2010，31(17):3841－3844.

［8］GUPTE S.Detection and classification of vehicles［J］.IEEE Trans.Intelligent Transportation Systems，2002，3:37－40.