《数字图像处理系统导论》课件第5章

第五章运动目标检测与跟踪5.1运动目标检测

5.2运动目标跟踪

5.3特征点跟踪示例lkdemo.c略析

5.4小结习题

运动目标检测是指在序列图像中检测出变化区域，并将运动目标从背景图像中提取出来。通常情况下，目标分类、跟踪和行为理解等后处理过程仅仅考虑图像中的运动目标的像素区域，因此运动目标的正确检测与分割对于后期处理非常重要。

一般而言，好的视频跟踪算法要满足两个基本的要求：(1)实时性好，算法费时少。如果系统的跟踪环节后面还有其他的图像处理环节，那么就要预留较多的时间给后面的处理，无法实现正常跟踪，所以实时性至关重要。

(2)鲁棒性强。实际的观测环境及图像的背景可能很复杂，光照、图像噪音及随时可能出现的对目标的遮挡均使目标的跟踪变得非常困难，这样对算法的鲁棒性要求就很高。

由于场景的动态变化，如天气、光照、阴影及杂乱背景干扰等的影响，使得运动目标的检测与分割变得相当困难。图5-1所示为变化背景下运动目标的检测结果。图5-1变化背景下运动目标的检测结果

5.1运动目标检测

5.1.1静态背景下的运动目标检测

大多数视频监控系统的摄像头是固定的，因此静态背景下的运动目标检测算法受到广泛关注，常用的方法有帧差法、

累积差分法、光流法、背景减除法等。

1.帧差法

帧间差分法，简称帧差法，检测相邻两帧图像之间的变化，直接比较两帧图像对应像点的灰度值的不同，然后通过阈值来提取序列图像中的运动区域。由于相邻两帧间的时间间隔非常短，用前一帧图像作为当前帧的背景模型具有较好的实时性，其背景不积累，且更新速度快，算法简单，计算量小。下面介绍帧差法的算法实现。

第k帧图像的灰度值Ik(xi，yi)和第k+1帧图像的灰度值

Ik+1(xi，yi)的变化用二值差分图像DPk,k+1(x，y)表示为

式中：(x，y)为运动车辆在图像空间的位置；T为阈值。阈值的选择相当关键，若选择过低，则不足以抑制图像中的噪声；若选择过高，则忽略了图像中有用的变化。运动序列的帧间差分法结果如图5-2所示。(5-1)图5-2运动序列的帧间差分法结果

2.累积差分法

缓慢运动的物体在图像中的变化量是一个很小的量，累积差分图像方法(AccumulativeDifferencePicture，ADP)的基本思想是通过分析整个图像序列的变化(而不是仅仅分析两帧之间的变化)来检测小位移或缓慢运动的物体。这种方法不仅能用来可靠检测微小运动或缓慢运动的物体，也可用来估计物体移动速度的大小、方向以及物体尺度的大小。

下面介绍累积差分法的算法实现。

累积差分图像可分为一阶累积差分图像(FADP)和二阶累积差分图像(SADP)。一阶累积差分图像的形成过程如下：将图像序列的每一帧图像与一幅参考图像进行比较，当差值大于某一阈值时，就在累积差分图像中加1。通常将图像序列的第一帧作为参考图像，并且置累积差分图像FADP0的初始值为0。这样，在第k帧图像上的累积差分图像FADPk(x，y)为

二阶差分图像的构造为：对应于第n帧(n=0，1，…，N且n>1)的二阶差分图像在(x，y)位置的值为“1”，表明在这个位置上第n－1和n帧的一阶差分图像FADP具有不同符号。

累积差分图像具有许多性质，可以用于描述物体运动的总体参数。(5-2)(5-3)

3.光流法

光流(opticalflow)是指图像亮度模式的表观(或视在)运动(apparentmotion)。光流法的主要任务就是计算光流场，即在适当的平滑性约束条件下，根据图像序列的时空梯度估算运动场，通过分析运动场的变化对运动目标和场景进行检测与分割。给图像中的每一像素点赋予一个速度向量，就形成了图像运动场(motionfield)，对应于物体三维运动。例如,在一个摄像机前，让一个颜色均匀的小球均匀转动，运动场因为有角速度，不为零，但因为图像并不随时间而变化，所以光流场处处为零。图5-3所示的Barber的运动场和光流场的方向也不一致。图5-3

Barber的运动场和光流场对于运动检测，通常有基于全局光流场和特征点光流场两种方法。

1)光流方程

在视频中，对于t和t+dt帧的光流计算，相当于两幅图像的像素匹配过程。我们假设在视频帧中，物体的对应像素的灰度值不因运动而变化，则可得到光流的基本公式：

I(x+udt，y+vdt，t+dt)=I(x，y，t) (5-4)

令u=dx/dt，v=dy/dt分别表示水平方向和垂直方向的光流速度，I*表示某方向的梯度，用一阶差分代替一阶微分，则光流基本公式可以表示为

Ixu+Iyv+It=0 (5-5)

Ix、Iy、It的计算用离散的差分代替导数。而未知数u和v只有一个方程，这种问题称为孔径问题(apertureproblem)。

为了解决孔径问题，可以假设在一个小窗口内的像素光流是一致的：①亮度恒定；②时间连续或者运动是“小运动”；③空间一致，临近点有相似运动，保持相邻。

图5-4所示为一致光流及其方程。图5-4一致光流及其方程则光流方程矩阵可以表示为

Au=b (5-6)

使用最小二乘法解Au=b中的向量，考虑矩阵的可逆性：

则

u=(ATA)－1ATb (5-7)

u即为所求的光流矢量。

2)经典算法

经典的全局光流场计算方法是L-K(Lucas-Kanade)法和H-S(Horn-Schunck)法，Lucas和Kanade假设在一个小的空间邻域Ω上运动矢量保持恒定，然后使用最小二乘方估计光流。

在L-K算法中，有些情况会导致矩阵不可逆。利用图像的特征角点计算光流，具有计算量小、快速灵活的特点，但当物体运动范围较大时，计算误差很大。这时，可以引入金字塔的思想，对原始图像进行采样，由粗到精，先通过高层金字塔找出大的运动量，再逐步细化，计算小的运动量并不断纠正大运动量的精确度。总的来说，光流法不需要预先知道场景的任何信息，就能够检测到运动对象，可处理背景运动的情况，但噪声、多光源、阴影和遮挡等因素会对光流场分布的计算结果造成严重影响。

3)应用示例

在摄像机固定的情况下，运动物体的检测其实就是分离前景和背景的问题，得到光流场后通过比较运动目标与背景之间的运动差异对运动目标进行光流分割，如图5-5所示。对于背景，理想情况下，其光流应当为0，前景光流不为0。所以我们并不要求通过求解光流约束方程求出u、v，只要求出亮度梯度方向的速率就可以了，即求出sqrt(u*u+v*v)。

而由光流约束方程可以很容易求到梯度方向的光流速率为V=abs(It/sqrt(Ix*Ix+Iy*Iy))。这样我们设定一个阈值T，若V(x，y)>T，则(x，y)是前景，反之是背景。图5-5目标运动的光流检测结果

4.背景减除法

背景减除法的基本思想是利用背景的参数模型来近似背景图像的像素值，将当前帧与背景图像进行差分，实现对运动区域的检测，其中区别较大的像素区域被认为是运动区域，而区别较小的像素区域被认为是背景区域。背景减除法必须要有背景图像，并且背景图像必须是随着光照或外部环境的变化而实时更新的，因此背景减除法的关键是背景建模及其更新。

混合高斯模型(GaussianMixtureModel，GMM)可对存在渐变及重复性运动的场景进行建模，被认为是最好的背景模型之一。基于高斯分布背景模型的差分方法，将图像中的每个图像单位(像素、块等)看成是从混合高斯分布样本中采样得到的随机变量。根据先验知识，每个像素点是前景或背景的先验概率可以估值。通过背景的分布模型判断一个像素点是否属于背景点，以此区分前景点和背景点，前景点就构成分割出来的物体，如图5-6所示。图5-6高斯背景减除法检测结果最常用的描述背景点颜色分布的概率分布是高斯分布(正态分布)，实际上也就是对每个像素考察其像素值与背景模型中的高斯分布的匹配程度。例如，当像素值在一个高斯分布的16以内时就认为它与该高斯分布匹配，即认为其属于背景点；而如果不与背景中任何一个高斯分布匹配，则认为其为前景点。背景模型的建立可以通过训练得到，并在处理中不断更新，这些过程除了需要人为地少量干预之外，可以自动地实现。

混合高斯模型使用k个(基本为3～5个)高斯模型来表征图像中各个像素点的特征，在新一帧图像获得后更新混合高斯模型，用当前图像中的每个像素点与混合高斯模型匹配，如果成功则判定该点为背景点，否则为前景点。通观整个高斯模型，主要由方差和均值两个参数决定，对均值和方差的学习，采取不同的学习机制，将直接影响到模型的稳定性、精确性和收敛性。由于我们是对运动目标的背景提取建模，因此需要对高斯模型中方差和均值两个参数实时更新。为提高模型的学习能力，改进方法对均值和方差的更新采用不同的学习率；为提高在繁忙的场景下大而慢的运动目标的检测效果，引入权值均值的概念，建立背景图像并实时更新，然后结合权值、权值均值和背景图像对像素点进行前景和背景的分类。初始化混合模型参数包括每个高斯模型的所占权重、每个高斯模型的均值和标准差。K个高斯模型的均值u为输入视频的第一帧对应的像素值或平均值，所有高斯模型的初始

方差都是相等的，方差取值表现该视频的动态特性，因为标准差的大小与各个高斯模型像素值的波动范围直接相关。高斯模型的权重的初始化就是对背景的分布进行先验概率的估值，在初始化时，一般将第一个高斯模型的权重取较大，其他就相应地取值较小，即(5-8)如果对于所有的颜色分量都成立，那么就把该像素归于第B个高斯模型，说明该像素点属于背景点，则第B个背景分布输出了一个采样值，这时所有分布都需要进行参数更新。野点指的是该像素值不符合任何一个高斯分布，此时我们把该像素点看成是视频中出现的新情况，用这种新情况来代替第k个高斯分布，其权重和均值以及方差都按照初始化思路确定，也就是分配一个较小的权重，和一个较大的方差，同时确定该点是前景点。

最后一步就是把k个高斯模型按照优先级别进行从大到小的排序，这里的优先级别取决于权值和方差之比，即(5-9)上式直接说明了在方差相等的情况下，权重越大，就越趋向于背景分布；在权重相等的情况下，方差越小，也就是变量的分布越集中，那么就更加趋向于背景分布；反之则趋向于前景分布。

基于高斯背景模型的运动目标检测方法，首先利用统计的方法得到背景模型，并实时地对背景模型进行更新以适应光线变化和场景本身的变化，用形态学方法和检测连通域面积进行后处理，消除噪声和背景扰动带来的影响。图5-7所示为高斯背景建模运动检测。图5-7高斯背景建模运动检测综上所述，高斯背景建模方法将图像中的每个图像单位看做从混合高斯分布样本中采样得到的随机变量，一般的混合高斯模型采用3～5个单高斯模型进行混合。该方法根据先验知识，对每个像素点是前景或背景的先验概率进行估值，并考虑到背景的多模态和复杂度，具有较好的检测效果。

基于统计背景模型的运动目标检测方法主要存在以下问题：

(1)背景获取。在场景存在运动目标的情况下获得背景图像。

(2)背景扰动。背景中可以含有轻微扰动的对象，如树枝、树叶的摇动，扰动部分不应该被看做前景运动目标。

(3)外界光照变化。一天中不同时间段光线、天气等的变化对检测结果的影响。

(4)背景中固定对象的移动。背景中的固定对象可能移动，如场景中的一辆车开走、一把椅子移走，对象移走后的区域在一段时间内可能被误认为是运动目标，但不应该永远被看做前景运动目标。

(5)背景的更新。背景中固定对象的移动和外界光照条件的变化会使背景图像发生变化，需要及时对背景模型进行更新，以适应这种变化。

(6)阴影的影响。通常，前景目标的阴影也被检测为运动目标的一部分，但这样会影响对运动目标的进一步处理和分析。5.1.2动态背景下的运动目标检测

基于帧间差分检测方法的前提是背景本身是静止的。在图像处理中，我们通常是通过摄像机获得原始的视频序列图像的。很多情况下，摄像机安装在运动平台上，摄像机本身也要在全空间范围内作扫描运动。这样一来，固定的背景物体会在图像平面上显示出一种全局的二维运动，这就是图像背景的全局运动。全局运动对动目标检测增加了图像处理的复杂度。这时，首先要做的就是帧间图像的配准，经过全局背景运动补偿后，帧间图像相对静止，可通过差分检测检测

出目标的轮廓。图5-8所示为背景存在运动的图像序列。图5-8背景存在运动的图像序列

1.基本原理

一般的目标检测系统首先估计摄像机的运动参数，再根据这些运动参数进行运动补偿，最后通过图像的差分求得运动目标区域，流程如图5-9所示。图5-9运动背景下目标检测算法流程框图在目标检测与跟踪系统中，摄像机与场景之间距离一般较大，通常用仿射模型来逼近场景图像的运动，普通仿射模型包括平移(a5，a6)、旋转和缩放(a1，a2，a3，a4)三种运动。

仿射模型将直线映射成直线，将平行线映射成平行线，其方程式为

式中：(x1，y1)为第一幅图像的特征点坐标；(x2，y2)为第二幅图像的对应特征点坐标；a1、a2、a3、a4、a5、a6为六个未知数。理想情况下，只要知道三个对应特征点就可解出此方程。但是由于图像噪声、目标以及遮挡等影响，不能准确地得到最能代表背景全局运动的三个特征点来求解这六个参数，必须采用鲁棒估计的方法得到精确的仿射运动参数。(5-10)

2.算法实现

通过全局运动估计进行运动目标检测，主要包括以下三个步骤：

(1)运动估计：估计帧间的运动参数，主要是运动模型的选择和图像运动的检测。首先需要选择一定的运动模型，然后在此基础上计算和估计摄像机的运动参数。

(2)运动补偿：根据运动估计的结果计算出全局的变换参数，或者说是去除不想要的(unwanted)运动，使观察者看起来有摄像机的晃动已被消除或减弱的感觉。

(3)目标检测：根据运动补偿模块的全局变换参数来改变当前帧，即得到了稳定的图像序列，两帧图像作差，可以获得运动目标的检测。下面对这三个步骤进行详细介绍。

1)基于特征点的运动估计

运动矢量估计的算法主要包括灰度投影法、光流场法、图像块匹配法、特征匹配法和相位法等。传统的灰度投影法尽管实现简单，但只能解决平移运动的问题。光流场法的计算较复杂，而且对噪声敏感。基于傅氏变换的方法采用了傅氏变换、相关运算或者极坐标变换，计算复杂度同样很高。目前较为常用的方法是图像块匹配法和特征匹配法。

基于块(Block-based)的运动分析在图像运动估计和其他图像处理和分析中得到了广泛的应用。块运动估计与光流计算不同，它无需计算每一个像素的运动，而只是计算由若干像素组成的像素块的运动，如图5-10所示。对于许多图像分析和估计应用来说，块运动分析是一种很好的近似。图5-10运动估计搜索示意图特征点匹配的关键在于特征点的选择和匹配策略的选择。所谓特征点的匹配，就是在待匹配图像中找到基准图像中的每一特征点的唯一匹配点。通过两帧之间特征点的位置变化，可以求出该特征点的局部运动矢量，而将所有特征点在两帧之间的位置变化信息代入运动模型，即可求出背景的全局运动矢量。因此，所有的特征点能否精确匹配，关键在于所选用的匹配准则和搜索策略。相比于块匹配法，利用这些特征点来估计运动矢量可以有效地减少数据量，提高计算的速度，且有利于图像的可靠匹配。

以基准图像的特征点为中心，构造了一定大小的M×M(5×5或7×7)的图像块，利用这些图像块，在待匹配图像的一定范围内进行搜索，来完成待匹配图像中的匹配特征点的获取。可以利用三步搜索法(TSS)进行快速搜索。需要指出的是，全部特征点中，只有部分能得到正确的匹配。这是因为匹配算法本身的缺陷或特征点由于其他的原因而消失，如被遮挡或移出视野等。

2)运动补偿

考虑到所有背景像素点符合同一摄像机运动参数模型这一基本事实，不需要估计所有像素点的运动矢量，只需要通过估计少量背景的像素点运动来估计出摄像机的运动参数，就可以通过该摄像机运动参数模型来估计图像背景中所有像素点的运动矢量。在特征点匹配的基础上，可以利用特征点之间一一对应的位置关系来估计全局运动参数，即仿射变换模型参数。设时刻tk的某一特征点坐标为(X，Y)，它在时刻tk+1的坐标为(X′，Y′)。如果以二维仿射变换描述特征点的运动，则两个特征点间的关系可以表示为(5-11)二维仿射变换有六个参数，需要三个不共线的特征点及其匹配点才能求得唯一解。仅仅由三对特征点估算全局的二维仿射变换参数并不合理，因为如果一个特征点的位置有较大的误差，或者错误的匹配都会给最终的计算结果带来很大的偏差。为此可以采用最小二乘法，用所有已知的特征点来求解变换参数。

根据求取的运动估计对抖动的图像作反向运动补偿，可使当前帧图像补偿到参考帧图像的位置上，使两帧图像完全重合，消除了因抖动造成的视频抖动，从而得到一个稳定的、静止的图像序列。

3)目标检测

将背景稳定序列进行帧差即可获得运动目标区域。图5-11为实验结果，AB为两帧相邻图像，图(a)为根据运动参数配准后的结果，图(b)为运动补偿后的图像结果，图(c)为帧差后提取的运动目标结果。图5-11实验结果

5.1.3运动目标检测的应用

根据对运动目标的检测和分析结果，可以衍生出不同的应用模式：

(1)周界警戒及入侵检测。在摄像机监视的场景范围内，可根据监控需要和目的设置警戒区域，系统可以自动检测入侵警戒区域内的运动目标及其行为，一旦发现有满足预设警戒信息的警情，即用警告框标示出进入警戒区的目标，同时标识出其运动轨迹，如图5-12所示。图5-12区域警戒检测结果

(2)运动物体流的统计。运动物体流检测技术就是在视频场景内能找到和发现要找的运动物体，并从视频背景中区分出来，然后进一步对该物体流的数量进行统计的技术。此外，还可以设定物体流经过的区域和流向并以此来判断是否作为统计目标，有非常广泛的应用。图5-13所示为公交车人流统计。图5-13公交车人流统计

(3)面向对象的视频编码。视频编码标准技术中，运动估计、运动补偿技术是提高编码效率的主要措施。因此，高效且精确的视频对象分割和先进的运动估计、运动补偿算法是基于内容的视频编码的一项关键技术。视频对象分割在时域和空域把视频分为多个视频对象(如图5-14所示)，是基于内容的交互式视频处理系统的关键前处理技术，也是MPEG-4与MPEG-7的重要组成部分。图5-14视频对象分割结果

(4)运动人体行为分析。一般利用混合高斯模型建立背景的算法，在复杂背景中提取清晰、完整的运动目标，通过自适应阈值进行背景更新，消除外界环境变化的影响，并对阴影进行检测和抑制，然后进行人体行为识别。运动人体行为分析技术在智能监控、人机交互等方面应用广泛。图5-15所示为运动对象分割结果。图5-15运动对象分割结果

5.2运动目标跟踪

视频目标跟踪技术在军用视觉制导、机器人视觉导航、安全监测、交通管制、医疗诊断、虚拟现实和战场警戒、公共安全监视、视频压缩以及气象分析等许多方面都有广泛的应用。在民用领域，具有目标跟踪功能的数字视频监视系统已取代模拟系统，并在多种领域获得了广泛的应用。

“神州”号飞船的发射时间之所以选择在夜晚而不是白天，主要是便于飞船发射升空时，地面的光学跟踪测量设备易于捕捉到跟踪目标。在夜晚或凌晨发射，由于喷射的火焰特别显眼，所以地面的光学跟踪测量设备容易跟踪目标。而白天就不利于地面光学跟踪设备对飞船的跟踪。图5-16给出了一运动目标跟踪示例。图5-16运动目标跟踪示例5.2.1视频目标跟踪方法

1.基于区域匹配的跟踪算法

图像相关匹配是一种基于最优相关理论的图像处理方法，在相关匹配过程中，需要一个表示目标的模板，通过计算目标模板与候选目标的相似程度，来确定当前图像中目标的具体位置。基于区域匹配相关的算法由于用到目标的全局信息，比如灰度、色彩、纹理等，因此具有较高的可信度。它可以利用色度信息建立目标区域的特征模板，通过MeanShift算法对其进行特征匹配，寻找最佳匹配的区域作为目标，如图5-17所示。此方法可以克服目标的不完全遮掩，对颜色特征明显的目标跟踪准确率较高，目前应用很广泛。图5-17

MS方法跟踪结果

2.基于特征点的跟踪算法

基于特征点的跟踪算法包括特征提取和特征匹配两个过程。特征点是目标上具有多个方向奇异性的点，其匹配搜索也是基于最优相关匹配理论的。由于特征点分布在整个目标上，因此即使有一部分被遮挡，仍然可以跟踪到另外一部分特征点，可以解决部分遮挡问题。基于特征点的跟踪算法中，难点在于目标发生旋转等形变后的特征点自适应，对于非刚性目标，运动过程中部分特征点会消失。图5-18为特征点方法跟踪结果。图5-18特征点方法跟踪结果

3.基于活动轮廓的跟踪算法

活动轮廓方法利用封闭的参数化曲线表示运动目标轮廓，在由图像构造的特征场中通过极小化以曲线函数为参数的能量来进行动态迭代，使得该轮廓能够自动连续地更新，如图5-19所示。相对于区域跟踪方法，该方法计算量小，但是初始化轮廓是算法的关键，而且不易做好，在目标跟踪中的应用较少。图5-19活动轮廓方法目标跟踪结果

4.基于光流的跟踪算法

光流法根据连续图像计算各像素运动的大小和方向，利用运动矢量场区分背景和运动对象，通常有特征光流场和全局光流场两种方法。全局光流场的计算方法有Horn-Schunck方法、Lucas-Kanade方法等，得到全局光流场后通过比较运动目标与背景之间的运动差异对运动目标进行光流分割，从而达到跟踪的目的。全局光流法的缺点是计算量大。特征光流法通过特征匹配来求得特征点处的流速，这种算法具有计算量小和快速灵活的特点，如图5-20所示。图5-20光流特征方法目标跟踪结果5.2.2

MeanShift目标跟踪方法

1.基本理论

MeanShift这个概念最早是由Fukunaga等人于1975年在一篇关于概率密度梯度函数的估计(TheEstimationoftheGradientofaDensityFunction，withApplicationsinPattern

Recognition)的文章中提出来的，其最初含义正如其名，就是偏移的均值向量。在这里，MeanShift是一个名词，它指代的是一个向量，一般是指一个迭代的步骤，即先算出当前点的偏移均值，移动该点到其偏移均值，然后以此为新的起始点,继续移动,直到满足一定的条件结束。1995年，Cheng的文章将它引入计算机视觉领域。空间Rd中有n个样本点xi(i=1，…，n)，x点的MeanShift向量的基本形式定义为

其中，Sh是一个半径为h的高维球区域，是满足以下关系的y点的集合:

Sh(x)≡{y：(y－x)T(y－x)≤h2}

(5-13)

k表示在这n个样本点xi中，有k个点落入Sh区域中。(5-12)可以看到(xi－x)是样本点xi相对于点x的偏移向量。式(5-12)定义的MeanShift向量Mh(x)就是对落入区域Sh中的k个样本点相对于点x的偏移向量求和，然后再平均。从直观上看,如果样本点xi从某个概率密度函数f(x，y)中采样得到，则非零的概率密度梯度指向概率密度增加最大的方向。因此，对应的MeanShift向量Mh(x)应该指向概率密度梯度的方向。图5-21所示为MeanShift示意图，图中，大圆圈所圈定的范围就是Sh，小圆圈代表落入Sh区域内的样本点xi∈Sh，黑点就是MeanShift的基准点x，箭头表示样本点相对于基准点x的偏移向量。图5-21

MeanShift示意图我们可以看出，平均的偏移向量Mh(x)会指向样本分布最多的区域，也就是概率密度函数的梯度方向。这个关系可

以直观地描述为“局部平均值向着大多数点所在的区域移动”。MeanShift向量和局部梯度估计平行，它指向估计密度的“定点”，密度的模式就是那些“定点”。反复地进行如下步骤，就是MeanShift过程：

(1)计算MeanShift向量Mh(x);

(2)用Mh(x)平移x;

(3)如果||Mh(x)－x||<ε，则结束循环，否则返回步骤(1)继续执行。最终，中心点收敛到数据空间中密度最大的点，即收敛到密度梯度为零的点。特征空间分析对密度很低的区域不感兴趣，在这些区域里，MeanShift过程的步长很大。而在感兴趣特征的区域，步长越小，越接近最大密度处，即越接近局部极大值，步长越小，分析得以优化。因而MeanShift过程是一个梯度自适应方法。图5-22所示为MeanShift收敛过程示意图。图5-22

MeanShift收敛过程示意图

2.MeanShift目标跟踪

在视频目标跟踪中，均值偏移向量的计算，由目标建模、相似性度量和模板匹配三部分组成。首先初始化候选目标模板，计算与目标模板的相似度函数；然后利用均值偏移迭代快速的特点，得到均值偏移矢量，它是使每一个点“漂移”到密度函数的局部极大值点，即目标所在当前帧的位置。

1)目标模型

MeanShift算法是一种非参数密度估计算法，使用空间分布和纹理信息作为匹配距离信息。我们用一个物体的灰度或色彩分布来描述这个物体，假设物体中心位于x0处，u表示特征，s为计算窗口大小，b(xsi)为当前点的数值，则该物体特征分布可以表示为

候选的位于y的物体可以描述为

因此，物体跟踪可以简化为寻找最优匹配的y，使得与最相似。与的相似性用Bhattacharrya距离来度量分布，即(5-16)(5-15)(5-14)图5-23所示为三个目标的Bhattacharrya距离。图

5-23三个目标的Bhattacharrya距离

2)算法实现

CAMShift算法全称是ContinuouslyAdaptiveMeanShiftAlgorithm，是MeanShift算法的改进算法。CAMShift算法充分利用了MeanShift算法计算简单快捷的优点，并且在不增加计算复杂度的同时，实现了自适应的窗口大小控制。

该算法的实现步骤如下：

(1)确定初始目标及其区域，计算出目标的色度(Hue)分量的直方图。

(2)将搜索初始点设置为目标初始位置，利用直方图计算输入图像的Bhattacharrya距离图。

(3)利用MeanShift算法在反向投影图中迭代搜索，直到其收敛或达到最大迭代次数，返回跟踪目标的零阶矩M00，

(4)调整搜索窗口大小，用来初始化下一帧中的搜索窗口。

(5)根据更新大小的窗口作为下一帧视频的初始窗口，并且将MeanShift所得到的迭代窗口中心重新作为目标初始位置，执行步骤(2)。若视频结束，则返回。

图5-24所示为跟踪结果图。(5-17)(5-18)图5-24跟踪结果及Bhattacharrya距离图我们也可以根据需要，计算目标的偏移角度。可以得出，椭圆的旋转角度为(5-19)

3.MeanShift扩展形式

从式(5-12)我们可以看出，只要是落入Sh的采样点，无论其离x远还是近，对最终的Mh(x)计算的贡献是一样的。然而一般来说，离x越近的采样点，对估计x周围的统计特性越有效。因此，我们引进核函数的概念，在计算Mh(x)时可以考虑距离的影响，认为在这所有的样本点xi中，都引入一个权重系数。可以把基本的MeanShift形式扩展为(5-20)其中

GH(xi－x)=｜H｜－1/2G(H－1/2(xi－x))

在实际应用的过程中，带宽矩阵H一般被限定为一个对角矩阵H=diag［h21，…，h2d］，甚至更简单地被取为H=h2I。由于后一形式只需要确定一个系数h，故在MeanShift中常常被采用，在后面部分我们也采用这种形式，因此式(5-20)又可以写为(5-21)我们可以看到，如果对所有的采样点xi都满足

(1)w(xi)=1;

(2)

则式(5-21)完全退化为式(5-12)。也就是说，我们所给出的扩展的MeanShift形式在某些情况下会退化为最基本的MeanShift形式。5.2.3视频目标跟踪中的粒子滤波方法

1.粒子滤波原理

粒子滤波(ParticleFilter，PF)的思想基于蒙特卡洛(MonteCarlo)方法，它是利用粒子集来表示概率，可以用在任何形式的状态空间模型上。它通过从后验概率中抽取的随机状态粒子来表达其分布，是一种顺序重要性采样法(SequentialImportanceSampling)。在滤波过程中，以大量采样的分布近似来表示p(x)。因此，在滤波过程中粒子滤波可以处理任意形式的概率，而不像Kalman滤波那样只能处理高斯分布的概率问题。粒子滤波首先根据x(t－1)和其概率分布生成大量的采样，这些采样就称之为粒子。那么这些采样在状态空间中的分布实际上就是x(t－1)的概率分布了。依据状态转移方程加上控制量可以对每一粒子得到一个预测粒子。越是接近真实状态的粒子，越有可能获得观测值y。于是，我们对所有的粒子进行评价p(y|xi)，这个条件概率代表了假设真实状态x(t)取第i个粒子xi时获得观测y的概率，令这个条件概率为第i个粒子的权重。因此，预测信息融合在粒子的分布中，观测信息又融合在了每一粒子的权重中。然后采用重采样算法，去除低权值的粒子，复制高权值的粒子。下一轮滤波，再将重采样过后的粒子集输入到状态转移方程中，直接就能够获得预测粒子了。

如图5-25所示，t－1时刻的先验概率由带有权值的粒子近似表示，经过系统观测后，重新计算权值，那些权值大的粒子可以分裂出若干新的粒子，而权值很小的将被丢弃，得到一组新的粒子。这些新的粒子加入随机量，预测在t时刻的状态，即系统状态转移过程。最后再次进入系统观测过程，预测下一时刻状态。图5-25粒子采样过程示意图

2.粒子滤波的单目标跟踪算法

(1)提取跟踪目标特征：指定跟踪目标，计算跟踪目标的特征，采用目标的颜色特征，计算该区域色调(Hue)空间的直方图，即为目标的特征。所以目标特征就是一个N×1的向量V。

(2)目标搜索阶段：根据目标的特征产生一定数量的粒子，去搜索目标对象。粒子有很多种初始化方式：

①均匀初始化，即在整个图像平面均匀分布(uniformdistribution)的粒子；

②在上一帧得到的目标附近按照高斯分布初始化，也就是靠近目标的地方粒子较多，远离目标的地方较少。粒子按照初始化阶段得到的目标特征(色调直方图、向量V)计算它所在位置处图像的颜色特征，得到一个色调直方图和向量Vi，计算该直方图与目标直方图的相似性。相似性有多种度量，最简单的一种是计算sum(abs(Vi－V))。算出每个粒子的相似度后再进行归一化，使得所有粒子得到的相似度加起来等于1。

(3)决策阶段。分布的粒子向我们发回报告，“一号粒子处图像与目标的相似度是0.3”，“二号粒子处图像与目标的相似度是0.02”，“三号粒子处图像与目标的相似度是0.0003”……“N号粒子处图像与目标的相似度是0.013”。我们通过加权平均计算目标的位置。设N号粒子的图像像素坐

标是(Xn，Yn)，它报告的相似度是Wn，于是目标最可能的像素坐标为X=sum(Xn*Wn)，Y=sum(Yn*Wn)。

(4)重采样阶段(Resampling)。在目标跟踪过程中，目标处在运动过程。在新的一帧图像里，目标可能在哪里呢？我们通过粒子的分布进行求解。回顾粒子的相似性信息：“一号粒子处图像与目标的相似度是0.3”，“二号粒子处图像与目标的相似度是0.02”，“三号粒子处图像与目标的相似度是0.0003”……“N号粒子图像与目标的相似度是0.013”。综合所有粒子的报告，一号粒子处的相似度最高，三号粒子处的相似度最低，于是我们要重新分布粒子，在相似度最高的粒子附近初始化更多的粒子。这就是SamplingImportanceResampling(根据重要性重采样)。(2)→(3)→(4)→(2)如此反复循环，即完成了目标的动态跟踪。图5-26所示为重采样流程图。图5-26重采样流程图

3.简单多视觉跟踪算法

对于多视觉目标跟踪，给定两个假设：①视觉目标观测是标记的，即视觉目标观测直接与其状态关联；②在运动中，各视觉目标不存在交互，是彼此独立的。于是，在k时刻T个视觉目标的联合状态Xk可表示为Xk={Xk，1，…，Xk，T}，视觉目标观测Zk可表示为Zk={Zk，1，…，Zk，T}。对于视觉目标t，其状态转移概率和观测概率可表示为(5-22)在粒子滤波理论框架下，该视觉目标跟踪问题可通过多目标状态独立滤波实现。这样一来，多视觉目标跟踪问题就简化为多视觉目标状态独立滤波问题，而且各个视觉目标的独立跟踪可通过基于标准粒子滤波的视觉跟踪算法实现。于是，该多视觉目标跟踪算法可表示如下：

(1)初始化。令k=0，对于多视觉目标1，…，T，根据先验分布p(X0，t)建立初始状态样本集 。

(2)粒子状态转移。根据特定的状态转移模型和粒子

，计算粒子 。

(3)粒子的权值计算。根据选择的视觉特征，计算观测概率 ，进而计算样本 的权值

，并进行归一化，有 。

(4)视觉目标状态估计输出。计算视觉目标状态估计 。

(5)重采样。根据粒子的权

从粒子集

重新抽取N个粒子，形成新的粒子集

。

(6)令k=k+1，返回步骤(2)。跟踪结果如图5-27所示。图5-27粒子滤波多目标跟踪结果

4.其他粒子滤波

正则粒子滤波(RegularizedParticleFilter，RPF)是为了解决由重采样引入的新问题而提出的一种改进的粒子滤波。当通过序贯重要性采样而引起粒子退化问题时，可以用重采样的方法来减小退化的影响，但是引入重采样策略的同时也引入了新的问题，即粒子匮乏问题。经过若干次迭代之后，所有粒子都趋向于同一个粒子，导致粒子的多样性丧失。这是因为在重采样过程中，粒子是从离散分布中采样取得的，而不是从连续分布中采样得到的。

Pitt和Shephard在标准SIR滤波算法的基础上提出了辅助粒子滤波(AuxiliaryParticleFilter，APF)。与标准序贯重要性重采样(SIR)算法相比，APF也是以序贯重要性采样(SIS)算法为基础，只是选择了不同的重要性密度函数。与SIR滤波算法相比，辅助粒子滤波算法的优势在于，它在k－1时刻的样本集合上随机抽取了一些点，抽取时以当前的观测数据为条件，这样可以更加接近真实的状态。

Jayesh和Petar提出，将高斯滤波和粒子滤波结合，这种方法称为高斯粒子滤波(GaussianParticleFilter，GPF)。该方法的前提是用高斯分布来近似后验分布，它比其他高斯滤波方法的适用性更强，能处理更多非线性动态系统问题。而与一般的粒子滤波相比，因为GPF用高斯分布近似后验分布，所以只要所用的高斯分布是正确的，就不会产生粒子退化问题，就不需要对粒子进行重采样，从而减小了算法的计算量，降低了复杂度。 5.3特征点跟踪示例lkdemo.c略析

LK稀疏光流Demo可以在场景中自动找出关键点并自动跟踪，也可以使用鼠标在指定位置添加关键点，此程序是很好的学习光流的示例。光流法的目的是跟踪目标(featuretracking)，即由(x，y)确定的物体上的某点的运动，即计算出这个特征点的运动。

示例的完整程序请参照OPENCV的例程lkdemo.c。部分代码如下：特征点提取与跟踪结果如图5-28所示。图5-28特征点提取与跟踪结果关键点分析：

(1)该程序运行流程：从计算机摄像头中获取视频，起初不作任何分析。按“r”后初始化，显示所获取的特征点。当视频显示时，可以用鼠标任意添加和去除特征点；当视频中的物体运动时，特征点也会随之运动，即特征点的跟踪。

(2)获取特征点的过程：由两个函数，即cvGoodFeaturesToTrack和cvFindCornerSubPix实现，前者实现的任务是，提取出图像image中规定上限个数的特征点(在本例中，上限为500)，然后存放于数组points［1］中。后者实现的任务是，将points［1］中的点作精确处理。这两个函数的参数含义将在(5)中给出。

(3)点是如何画出来的呢？其实就是由画圆函数cvCircle(image，cvPointFrom32f(points［1］［i］)，3，CV_RGB(0，255，0)，－1，8，0)实现的。

(4)有一个比较重要的函数，即cvCalcOpticalFlowPyrLK，正是这个函数实现了特征点的跟踪。

其参数包括：(constCvArr*prev，constCvArr*curr，CvArr*prev_pyr，CvArr*curr_pyr，constCvPoint2D32f*prev_features，CvPoint2D32f*curr_features，intcount，CvSizewin_size，intlevel，char*status，float*track_error，CvTermCriteriacriteria，intflags)。

各参数的含义如下：

prev：前一帧;

curr：当前帧;

prev_pyr：第一帧的金字塔缓存;

curr_pyr:当前帧的金字塔缓存;

prev_features：需要发现光流的点集;

curr_features：包含新计算出来的位置的点集;

count：特征点的数目;

win_size：每个金字塔层的搜索窗口尺寸;

level：最大的金字塔层数;

status：数组，如果对应特征的光流被发现，数组中的每一个元素都被设置为1，否则设置为0;

error：双精度数组，包含原始图像碎片与移动点之间的差，为可选参数，可以是NULL;

criteria：准则，指定在每个金字塔层，为某点寻找光流的迭代过程的终止条件;

flags：其他选项，包括

CV_LKFLOW_PYR_A_READY，在调用之前，第一帧的金字塔已经准备好;

CV_LKFLOW_PYR_B_READY，在调用之前，第二帧的金字塔已经准备好;

CV_LKFLOW_INITIAL_GUESSES，在调用之前，数组B包含特征的初始坐标。

函数cvCalcOpticalFlowPyrLK实现了金字塔中Lucas-Kanade光流计算的稀疏迭代版本。它根据给出的前一帧特征点坐标计算当前视频帧上的特征点坐标。函数寻找具有子像素精度的坐标值。两个参数prev_pyr和curr_pyr都遵循下列规则：如

果图像指针为0，则函数在内部为其分配缓存空间，计算金字塔，然后再处理过后释放缓存。否则，函数计算金字塔且将它存储到缓存中，除非设置标识CV_LKFLOW_PYR_A［B］_READY。图像应该足够大以便能够容纳Gaussian金字塔数据。调用函数以后，计算金字塔，并设置相应图像的标识，为下一次调用做好准备(比如，对除第一个图像外的所有图像序列，设置标识CV_LKFLOW_PYR_A_READY)。

(5)其他函数简介。

①voidcvGoodFeaturesToTrack(constCvArr*image，CvArr*eig_image，CvArr*temp_image，CvPoint2D32f*c