基于MeanShift的目标跟踪算法精编

I

1 一、 绪 论

（一） 课题研究背景及意义

视觉系统是人类获取外界信息的最主要途径，但是人类的精力、视野等会受到环境很大的限制，人类自身的视觉系统已经不能满足人类的需求。随着计算机技术的快速发展，利用计算机处理视觉信息、弥补人类视觉缺憾受到越来越广泛的关注，计算机视觉研究应运而生。

计算机视觉是融合了图形图像处理、计算机、模式识别、人工智能、数学、物理学、计算机图形学等众多学科的交叉性学科。计算机视觉主要用来对环境中的物体的几何信息——物体的位置、形状、运动等，进行感知、描述、存储和理解。运动目标跟踪技术在当今社会发挥着越来越显著的作用。在生活领域，运动目标跟踪可以帮助人类及时、准确地处理异常情况；在军事领域，运动目标跟踪可以提高攻击的准确度，从而提高军事作战能力。

总之，目标跟踪技术的日益成熟对人类社会生活的日益发展有着不可或缺的作用，人类对目标跟踪技术的发展与研究也越来越关注。

（二） 国内外研究现状

目标跟踪逐渐受到人们的关注与计算机技术的发展是密不可分的。上世纪80年代之前，由于计算机技术发展不成熟，使得计算机对图形图像的处理和分析主要以静态的为主，而对于动态图形图像的分析、处理、跟踪则带有很强的静态图形图像分析的特点。动态图形图像序列的分析研究进入一个崭新的阶段则是在光流法被提出之后。一直到二十世纪90年代中期，光流法一直是人们研究的热点，但由于光流法所需的运算量太大，不能很好地达到实时性的要求，同时，光流法采用假设，这就造成了光流法的局限性，使得光流法对噪声很敏感，很容易产生错误的结果。在二十世纪80年代后期又相继出现了其他的跟踪算法，主要有Micheal Isare 和Andrew Black 在1998年提出的Condensation算法[1]，这是第一次在视频序列目标跟踪中应用粒子滤波的思想；Comaniciu等在2003年提出的Mean Shift 跟踪框架，这种算法计算复杂程度低，理论较严谨，对目标的遮挡、尺寸的变化、外表的变化具有一定的自适应能力。Mean Shift 算法的这些优点使得它成为目标跟踪算法研究的热点。

就研究现况来看，国外对目标跟踪算法的研究起步较早。早在20世纪50年代初期，GAC公司就为美国海军研发了自动识别跟踪系统（Automatic Terrain

Recognition and Navigation(System),ATRAN）。在1997年，美国国防高级研究计划局又与卡内基梅隆大学、麻省理工学院等高校合作，研发了视频监控重大项目VSAM（Visual Surveillance and Monitoring）。相比较之下，国内对目标跟踪算法的研究起步较晚。一直到1986年我国才正式立项研究视频跟踪技术。到现在，中科院自动化研究所下属的模式识别国家重点实验室成立的视频监控小组在目标跟踪的研究中已经取得了不错的成绩。此外，国内一些其他高校也进行了相应程度的研究。

（三） 目标跟踪算法简介

运动目标跟踪首先在静态图像中进行目标分割，从而进行运动目标检测。提取完目标后，将目标用颜色直方图、目标轮廓、区域特征点、目标几何形状等一定的形式表示出来。目标检测完成后再进行目标跟踪，目标跟踪的主要目的是获

2 取运动目标随时间运动的轨迹，即目标在任一时刻可能处在的位置，并建立起不同帧之间目标的对应关系，在此基础上预测未来某时刻目标的位置。

（四） 本文主要研究内容

本文简单介绍了目标跟踪技术及常见的目标跟踪算法，其中着重研究Mean

Shift 跟踪算法。Mean Shift 算法原理简单、实现方便、实时性好，是一种高效的模式匹配算法。在对实时性要求较高的目标跟踪领域中，Mean Shift 算法已经得到了广泛的运用。本文利用Mean Shift 算法通过实验实现简单的目标跟踪。

二、 目标跟踪算法综述

（一） 引言

目标检测是运动目标跟踪的基础，只有准确检测出跟踪目标，后续的匹配、跟踪工作才能进行。目标检测利用运动目标的几何特征和统计特征，通过分析图像帧的变化情况利用阈值法将不断变化着的运动目标和不变的背景区分开来，进而提取出运动目标。因获取视频图像的方法各有不同，目标检测的方法主要有静止背景下的目标检测和运动背景下的目标检测。静止背景下的目标检测方法主要有帧差法、光流法和背景减除法；运动背景下的目标检测主要有图像拼接法和多传感器的图像融合法。

运动目标跟踪的主要工作是对从目标检测中检测出来的目标进行定位和跟踪，并记录和标示目标的运动速度、运动轨迹、所处位置等，从而为当前阶段任务提供提示信息，为后续的处理工作提供详细的参考信息。运动目标跟踪的方法根据目标建模和算法原理的不同，主要有基于形状匹配、区域建模、轮廓模型、运动分析和统计模型的算法。基于形状匹配的算法利用相似性函数度量建立的目标模型和邻近区域的候选模型的相似度，从而判断出目标的运动。基于区域建模的算法首先对矩形或椭圆的目标区域建立目标模型，然后逐帧寻找最优匹配模型，从而取得目标的运动信息。基于轮廓模型的算法通过对目标状态的形状和运动参数进行定义，然后依靠轮廓模型的后验概率最大化实现目标跟踪。基于运动分析的算法利用目标的运动信息，将运动着的目标和相对静止的背景区分开，再进行对目标的跟踪。基于统计模型的算法首先利用概率论的相关知识建立运动分析的数学模型，然后通过求解方程组来估计目标的运动状态，最终实现跟踪目标。

本章的以下部分主要针对几种常用的算法进行介绍。

（二） 常用检测算法介绍

本文主要介绍静止背景下的视频图像序列的检测算法，主要有帧差法[2]、光流法[3]和背景减除法[4]。

1. 帧差法

帧差法顾名思义就是将视频图像序列的连续两帧进行差分运算，然后根据预定义阈值来判断哪些像素点属于运动目标，进而确定运动点团区域。帧差法计算量小，易于实现，对光照的变化不敏感，鲁棒性好，适应性强。但是帧差法的阈值选择比较困难并且过于依赖经验，阈值选择过小则没有实用的意义，阈值选择过大则容易遗漏部分有用信息。此外，当运动目标内部有较大面积的平坦区域时，

3 前后两帧做差后就会出现目标内部相应区域的“空洞”，且难以消除，目标的完整性没有保障。

帧差法算法步骤：

（1）预处理：视频图像序列中会夹杂随机噪声，应该用滤波器对视频图像序列进行滤波来消除随机噪声的影响。

（2）差分运算：将当前帧与预存的上一帧图像做差分运算，公式如下：

1(,)(,)(,)kkkDxyIxyIxy (2-1)

其中(,)kDxy表示像素差分后的值，(,)kIxy表示当前帧像素值，1(,)kIxy表示上一帧像素点的值。

（3）目标提取：将得到的(,)kDxy和预先设置好的阈值相比较，取二值化[5]区域即为目标点团区域。公式如下：

1,D(,)(,)0,kkxyTExyelse (2-2)

其中，(,)1kExy的区域就是目标的点团区域，T是预先设定好的阈值。

（4）后处理：第三步得到的目标点团区域通常不能很好地满足人们的需求，所以需要利用形态学滤波[6]等方法进行后续处理，从而使目标区域更准确。

2. 光流法

光流法主要通过对独立运动的目标进行光流分析，计算光流场，来获得运动目标的相对运动速度、目标距离和目标的表面结构等有用信息。光流的计算需要利用光流约束方程，再结合物体移动时呈现的光学特性，将二维速度场与图像中点的灰度值的变化相关联，提出两个基本假设：(1)在很短的时间间隔内运动着的物体上某一点的灰度值保持不变；(2)速度向量场的变化在给定的邻域内是连续且缓慢的。(,)mxy像素点t时刻的灰度值用(,,)Ixyt表示，该点光流的x、y分量分别为(,)uxy和v(,)xy，由(1)可知光流约束方程为：

0tIvI (2-3)

其中IIIxy为图像在点m处的梯度，(,)vuv代表像素点m处的速度；xyIvIuIv；tI为连续两帧像素点灰度的变化率。由(2)可以求解光流：

()()xytemIuIvI (2-4)

22222()+uuvvsmxyxy (2-5)

2222Eemasmdxdy (2-6)

上式中(2-4)为光流误差方程，(2-5)为速度分量的平方和积分表达式，(2-6)为将平滑性测度和加权微分约束测量组合起来的公式，对其求解就可计算出目标的运动信息。

4 3．背景减除法

背景减除法又称为背景差分法，是一种直观且优秀的算法。它以点为单位进行建模，且以点为单位将当前帧图像和构造的背景图像做差，依靠阈值来获取运动着的目标的点团区域。某一像素点的像素如果是背景则其值的变化会在一定范围内（即阈值），只有当运动的物体经过该点时其值才会发生明显的波动超出阈值设定的范围，这样我们就可以检测出目标点团区域了。

算法流程：

(1) 预处理：对图像帧进行滤波处理，去除噪声减少其对运算结果的影响。

(2)背景建模：依据不同的假定和数学算法，建立背景模型(,)kBxy。

(3)更新背景模型：用当前帧和背景模型进行差分运算得到值(,)kDxy，用此差值更新背景模型(,)kBxy。

(,)(,)(,)kkkDxyIxyBxy (2-7)

(4)提取目标：将(,)kDxy与阈值作比较，并二值化结果得到目标的点团区域，计算方法为：

1,D(,)(,)0,kkxyTExyelse (2-8)

该算法中对背景模型的建立和实时更新是关键部分，只有这样才能适应场景的变化，提高检测的准确度，目前主流的更新方法有均值法和高斯混合模型法[7]。

均值法即取多帧图像的均值作为背景模型：

1(,)(,,)NbiIxyIxyin (2-9)

其增量形式可表示为：

11(,)(,)(,,)bbnIxyIxyIxynnn (2-10)

这种算法的优点是运算速度快，缺点是内存开销大，且容易产生亮度错误的积累。可以利用加权的方式对其进行改进，如下：

(,)(1)(,,)(,bbIxyaIxynaIxyn (2-11)