Mean Shift跟踪的背景优化及动态分析

王建华， 王春平， 梁 伟， 王惠萍

(1.白求恩军医学院计算机教研室，石家庄 050081; 2.军械工程学院光学与电子工程系，石家庄 050003)

0 引言

随着计算机视觉的快速发展，目标跟踪已成为视觉领域的一个重要研究方向，广泛应用于视频监控、人工智能、运动分析等领域［1］。其中的一类算法是基于目标表达和定位的方法，Mean Shift则属于这类算法中比较成功的算法之一，它是一种基于最优梯度下降的方法，通过迭代来寻找目标，从而实现对目标的跟踪。自从1995年被Yizong Cheng［2］引入到计算机视频，就由于具有计算量小、跟踪效果好、实时性强等特点，被广泛应用于目标跟踪的各个领域。但传统的Mean Shift算法存在以下缺点:1)背景像素的参与容易带来定位偏差;2)缺乏相应的动态分析方法;3)对于目标的刚性形变和严重遮挡比较敏感。为了解决这些问题，许多专家和学者给出过不尽相同的改进方法，例如:文献［3］将 SIFT(Scale Invariant Feature Transform)与Mean Shift结合;文献［4］用联合颜色纹理直方图表示目标特征计算目标模型;文献［5］通过自适应调整核函数宽度实现对大小变化的目标跟踪;文献［6］利用分块的方法实现目标在遮挡情况下的跟踪;文献［7］中将粒子滤波与Mean Shift相结合的算法。综合考虑以上算法的优缺点，针对Mean Shift算法在目标快速运动且目标大小变化较大、存在严重遮挡情况下容易丢失目标的问题，本文提出两方面的改进措施:1)将跟踪窗口内的区域区分为目标和背景两部分，通过减少背景像素在概率密度函数(PDF)中的权重来对背景进行优化，以降低背景对目标跟踪的影响，提高定位精度;2)采用分块的方法对跟踪状态进行动态分析，根据目标的大小变化，更新跟踪窗口大小及模板，实时判断遮挡状态，根据遮挡位置和目标实际大小的不同，动态计算目标的位置，当存在严重遮挡时，采用最小二乘法进行二维线性预测，解决目标在短时间内被完全遮挡的跟踪问题。对上述改进方法进行实验，实验结果验证了该方法对于复杂条件下的目标跟踪的稳健性。

1 传统Mean Shift算法原理

Mean Shift算法［8］是一种基于密度估计的非参数匹配算法，利用目标区域的颜色概率直方图分布建立目标模型，根据均值平移向量，在临近区域内自动搜索匹配度最高的区域，作为新的目标位置，该算法不需要进行穷尽搜索，实时性强，在基于图像处理的目标跟踪中得到广泛应用。其实现过程如下所述。

1)在初始帧中，利用手动或自动检测算法检测到目标所在区域，利用颜色概率直方图分布建立初始目标模型。设目标中心为y0，像素位置为，其中n为目标所包含的像素点的个数，该目标区域的像素灰度级范围为［0，H－1］。则可得到目标区域的统计直方图分布模型为

2)在当前帧的y0点位置，像素位置为{xi}，i=1，…，nh，统计候选目标的直方图分布

3)用Bhattacharyya系数计算候选目标与初始目标模型的相似度。

4)计算跟踪窗内像素的权重。

5)根据均值平移向量，搜索新的目标位置。

同时计算Bhattacharyya系数为

6)比较Bhattacharyya系数，更新候选目标位置，如果，则

7)判断是否达到最优，如果‖y1－y0‖＜ξ，停止迭代;否则置y0=y1跳转到第2)步。

2 背景优化

从Mean Shift算法中，可以看出跟踪窗内所有像素(目标和背景)均参与直方图分布的统计对目标进行建模，当跟踪窗内包括的背景像素比较少时，Mean Shift算法能稳定跟踪目标，但当跟踪窗内的背景像素比较多或背景变化比较明显时，就会产生定位偏差，甚至丢失目标。因此，减少或消除背景像素的影响对于提高目标跟踪的定位精度是非常必要的。

本文将跟踪窗内的目标和背景分为两部分，通过减少背景像素在概率密度函数中的权重来对背景进行优化，以降低背景对目标跟踪的影响，提高定位精度。设跟踪窗内像素xi灰度为h的像素的权重为λh，则

类似地，将目标模型进行如上改进。

采用最大类间法对跟踪窗口内的像素进行阈值分割，以将目标和背景区分开来，对于目标或背景内出现的空洞，采用数学形态学的方法予以消除。这里需要指出的是，为了保证建立目标模型数据的原始性，避免引入二次误差，该二值图像仅用来判断参与建立模型的像素是否属于目标，建立目标模型时用到的图像数据仍然是跟踪窗口内的原始图像数据。

3 跟踪状态的动态分析

由于Mean Shift算法以候选目标和目标模型的模板相似度最大化为判断准则，所以模板对于跟踪的稳定性起着至关重要的作用。但在实际图像跟踪中，一成不变的目标是非常少见的，大多数情况下，都会由于目标运动状态、背景变化或其他物体遮挡等因素的影响，目标在图像中的运动形态会发生很大变化，因此为了提高该算法的跟踪鲁棒性和稳定性，需要对跟踪状态进行实时分析，根据跟踪状态的不同，及时调整跟踪策略，以满足复杂情况下运动目标跟踪的需要。

本文采用的动态分析方法基于分块的思想［9］，动态计算每个子块相对于目标中心位置的位置偏差，根据目标与模板的相似性系数，判断是否有遮挡发生，如果存在遮挡，则根据遮挡的位置，自动根据其他子块相对于目标中心的位置偏差对目标位置进行定位。子块数量选择的基本原则是:数量过多影响算法的实时性，数量过少抗遮挡能力差。为了提高抗干扰能力，又要保证算法的实时性，这里以中心对称的方式将目标模板分为4块，图1为分割示意图。

图1 分块示意图Fig.1 Fragments of object region

其中，Δyave-b，Δyave-a分别为跟踪窗口调整前后位置偏差平均值。当有遮挡情况发生时，不更新目标模板及跟踪窗口，待目标脱离遮挡后，再进行更新操作。

4 算法流程

为了提高Mean Shift算法的跟踪精度和抗遮挡能力，将背景优化方法和跟踪状态的动态分析方法统一到一个跟踪框架结构中，具体算法流程如下所述。

1)初始化跟踪目标(本文采用手动的方法选定目标)，将目标模板按图1所示进行分块。对模板进行阈值分割，区分目标和背景，根据式(7)针对原始图像数据统计目标模型的直方图分布。

2)读取新一帧图像，确定模板的坐标位置。

①对跟踪窗口内的像素进行阈值分割，以区分目标和背景;

②利用式(8)统计候选目标的直方图分布;

③利用传统Mean Shift算法的3)～7)步计算目标位置，并记录最终的目标相似度ρ;

④ 若 ρ≥ρth(ρth为预先设定的遮挡阈值)，说明目标没有被遮挡，记录目标的位置信息并根据跟踪窗口及分块的基本方法，计算每个子块相对于目标坐标的位置偏差，读取下一帧图像，返回步骤①;若ρ＜ρth，执行步骤⑤;

5 实验结果及分析

本实验采取的图像序列是在室外获取的人由远及近且存在遮挡的视频。图2给出了跟踪效果图。

图2 跟踪实例Fig.2 Example of tracking

图中，黑色矩形是传统Mean Shift算法的跟踪结果;白色矩形区域是经过背景优化和动态分析后的目标跟踪结果。其中，第1帧中黑色矩形区域为手动的方法选取的目标位置;在第88帧中，我们发现用传统的Mean Shift算法虽然能跟上目标，但由于它没有根据目标的大小变化及时更新核窗的大小，使得跟踪位置出现偏差，而改进算法加入了背景优化及动态分析策略，算法自动根据目标大小变化调整跟踪窗口，目标跟踪定位较为准确;在第167帧中，目标被部分遮挡，传统的Mean Shift算法出现了很大的位置偏差，而改进算法判断遮挡情况，自动根据第1、2子块信息进行整个目标位置的判定，结果较好;在第269帧到第345帧中，目标经历了一个完全遮挡过程，传统的Mean Shift算法陷入了局部最小值，而改进算法此时所有的子块的均小于设定的阈值，采用二维线性预测方法进行预测，当目标脱离遮挡时，更新目标模板，重新跟踪。

将算法跟踪结果与手动提取的结果采用计算定位偏差的方法进行比较，结果如表1所示。定位偏差Ei为

其中:(xo，yo)为手动的方法提取的目标中心位置;(xi，yi)为算法跟踪的中心位置结果，单位为像素;i为帧数序列。从表中可以看出，改进的算法具有更高的跟踪精度。

表1 定位偏差比较Table 1 Comparasion of location errors

6 结束语

传统的Mean Shift算法由于算法简洁、实时性强，被广泛应用于视频目标跟踪领域，但该算法中，参与目标定位时，在包括目标的同时不可避免地会引入背景像素，因此背景像素无疑会给定位结果带来偏差;此外，由于传统的Mean Shift算法没有相应的动态分析方法，使得目标在发生遮挡时，算法容易陷入局部最小值，造成跟踪失败。本文针对传统Mean Shift算法的上述缺陷，提出了两方面的改进措施:1)对跟踪窗口内的背景像素进行优化，采取阈值分割、数学形态学等方法区分目标和背景，对目标和背景采取不同的权值进行建模;2)以基于分块思想的动态分析方法，实时判断是否存在遮挡，当有部分遮挡时，利用其余未遮挡的子块根据各自的位置偏差进行目标定位，当目标被完全遮挡时，利于二维线性预测的方法对目标进行预测，防止目标的丢失。整个跟踪过程中根据子块的位置偏差不断更新跟踪窗口的大小，间隔固定帧数或目标脱离遮挡时更新模板。实验表明，将背景优化和动态分析方法附加在传统的Mean Shift算法中，有效改善了Mean Shift跟踪算法的不足，对于复杂条件下的运动目标跟踪具有很好的鲁棒性。

［1］ 刘钢，刘明，匡海鹏，等.多目标跟踪方法综述［J］.电光与控制，2004，11(3):26-29.

［2］ CHENG Yizong.Mean Shift，mode seeking，and clustering［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1995，17(8):790-799.

［3］ ZHOU Huiyu，YUAN Yuan，SHI Chunmei.Object tracking using SIFT features and mean shift［J］.Computer Vision and Image Understanding，2009，113(3):345-352.

［4］ NING Jifeng，ZHANG Lei，ZHANG D.Robust object tracking using joint color-texture histogram［J］.International Journal of Pattern Recognition ＆ Artificial Intelligence，2009，23(7):1245-1263.

［5］ 付勇，何明一，刘超.Mean Shift目标跟踪核函数宽度的自适应调整［J］.计算机工程与应用，2010，46(17):243-245.

［6］ 颜佳，吴敏渊，陈淑珍，等.应用Mean Shift和分块的抗遮挡跟踪［J］.光学精密工程，2010，18(6):1413-1418.

［7］ 张旭，李志国.基于粒子滤波和均值平移的目标跟踪［J］.激光与红外，2008，38(8):834-836.

［8］ COMANICIU D，RAMESH V，MEER P.Real-time tracking of non-rigid objects using Mean Shift［C］//IEEE Conference on Computer Vision and Pattern Recognition，2000:142-149.

［9］ ADAM A，RIVLIN E，SHIMSHON L.Robust fragments-based tracking using the integral histogram［C］//Computer Vision and Pattern Recognition，IEEE Computer Society Conference，2006:798-805.

［10］ 王春平，王建华，朱元昌.遮挡情况下运动目标的航迹预测方法研究［J］.火力与指挥控制，2005，30(s):107-108.