基于蒙特卡罗方法的目标跟踪

中国图象图形学报Journal of I m age and Graphics

Vol .13,No .5

M ay,2008

　　基金项目:国家自然科学基金委员会与微软亚洲研究院联合资助项目(60672161)

收稿日期:2006208231;改回日期:2006212205

第一作者简介:张海青(1977～　),男。工程师。2000年于工程学院通信工程系获学士学位,现为中国科学技术大学电子工程与信息科学系硕士研究生。主要研究方向为计算机视觉。E 2mail:wjzhq@mail .ustc .edu .cn;wjzhq@s ohu .com

基于蒙特卡罗方法的目标跟踪

张海青

李厚强

(中国科学技术大学电子工程与信息科学系,合肥　230027)

摘　要　为了更鲁棒和快速地进行目标跟踪,在基于粒子滤波的目标跟踪方法的启发下,提出了一种新的基于蒙特卡罗方法的目标跟踪方法。该方法首先运用蒙特卡罗技术对下一帧目标可能出现的位置和尺度进行抽样;然后计算各抽样与参考目标的相似度;最后通过估计目标状态来获得跟踪目标。实验表明,该方法无需目标运动信息,特别适用于目标灵活运动时的跟踪,与现有的算法相比,不仅算法实现简单,同时有较好的鲁棒性和通用性。关键词　目标跟踪　蒙特卡罗方法　贝叶斯滤波　粒子滤波

中图法分类号:TP391.41　　文献标识码:A 　　文章编号:1006261(2008)0520937207

O bject Track i n g w ith M on te Carlo M ethods

Z HANG Hai 2qing,L I Hou 2qiang

(D epart m ent of Electronic Engineering and Infor m ation Science,U niversity of Science &Technology of China,Hefei 230027)

Abstract 　For tracking object more r obustly and rap idly,a novel app r oach f or object tracking usingMonte Carl o method is p resented,which is motivated by the method of tracking with particle filter .I n this app r oach,the l ocati ons and scales of the candidates in the next fra me are sa mp led thr ough Monte Carl o technique .Then the si m ilitude degree bet w een the sa mp les and the reference objects are calculated .A t last,the object states are esti m ated and the object under tracking is attained .This method does not need the moti on inf or mati on of the object,s o it is es pecially good at tracking flexible object .The method is easier t o i m p le ment than other p resent methods .Further more,it is p r oved t o be quite r obust and versatile by the nu merical experi m ents .

Keywords 　object tracking,Monte Carl o methods,Bayesian filtering,particle filtering

1　引　言

目标跟踪,即在视频序列中对感兴趣的目标进行有效的跟踪,一直都是计算机视觉领域中的一个典型问题。在视觉分析系统的处理过程中,跟踪是位于运动检测和目标分类之后、行为理解与描述之前的不可缺少的关键部分。简单而言,跟踪等价于在连续的图像帧间创建基于位置、速度、形状、纹理、色彩等有关特征的对应匹配问题,如何对目标进行高效的模式匹配以及如何有效地适应目标自身的运动变化和排除场景干扰是一个优秀的跟踪系统必须

解决的两个关键问题。这两个问题反映到跟踪算法的性能上就是实时性和稳健性。

由于应用场合与要求的不同,目前存在多种跟踪系统和不同的跟踪方法。跟踪系统按跟踪对象不同,有整体跟踪和局部跟踪两类;按跟踪视角不同,有对应于单摄像机的单一视角跟踪、对应于多摄像机的多视角跟踪和全方位视角跟踪等;按跟踪空间不同,有2维跟踪和3维跟踪;按跟踪目标数目不同,有单目标跟踪和多目标跟踪等。目前不同的跟踪方法大致有:(1)基于模型的跟踪,该方法首先对目标建立模型,然后利用该模型来产生运动目标的描述,最后通过在连续的图像帧间匹配模型来获得

　中国图象图形学报第13卷

目标运动的定量描述,如适用于人体运动跟踪的线图模型[1]、纸板人模型[2]、椭圆锥台3维人体模型[3]等;(2)基于活动轮廓的跟踪,即利用封闭的曲线轮廓来表达运动目标,并且该轮廓能够自动连续地更新,如level set方法[4];(3)基于特征的跟踪,该方法包括特征的提取和特征的匹配两个过程,如文献[5]的跟踪系统就是使用运动轮廓的角点作为对应特征的,这些特征点通过基于位置和点的曲率值的距离度量在连续帧间进行匹配;(4)目标跟踪的统计计算方法,如基于粒子滤波的跟踪[6,7],该方法基于贝叶斯统计计算,首先把跟踪问题转化为非线性非高斯的贝叶斯滤波问题,然后通过对滤波问题的求解来获得跟踪目标;(5)mean2shift方法[8,9],该方法先把跟踪问题转化为寻找模式点的问题,再通过经典的mean2shift算法(一种基于核密度估计的无参快速模式匹配算法)得到极值点,该点就是跟踪目标的位置。

以上的方法中,除mean2shift方法外,复杂度都较高,很难满足实时性要求,而mean2shift方法又存在缺陷,即由于该方法只能得到局部极值点,因此不适用于背景嘈杂情况下的跟踪,且其在考虑目标尺度变化时,算法计算量显著增加。

本文在基于粒子滤波目标跟踪方法的启发下,提出了一种新的基于蒙特卡罗的目标跟踪方法。该方法首先运用蒙特卡罗技术对下一帧目标可能出现的位置和尺度进行抽样;然后计算各抽样与参考目标的相似度;最后通过估计目标状态来获得跟踪目标。由于该方法无需目标运动信息,因此特别适用于目标灵活运动时的跟踪,与现有的算法相比,该算法实现简单,同时实验表明,该方法有较好的鲁棒性和通用性。

2　基于粒子滤波的目标跟踪

211　目标跟踪的动态模型

　　本文首先把视频序列跟踪中的目标状态(例如:位置和速度)随时间变化的过程看作是一个动态过程;然后用动态系统来为此过程建模,而目标跟踪则相应成为基于动态系统的目标状态的在线估计问题。简言之,目标跟踪问题可以描述为在给定一组观测值的条件下,对系统的状态进行估计的问题。

动态模型,即状态空间模型(如图1所示),

它

图1　动态模型

Fig11　Dyna m ic model

由以下两部分组成:

状态方程

x k=f k(x k-1,ωk)(1)观测方程

y k=h k(x k,υk)(2)其中,x

k

、y

x

分别是k时刻的状态变量和观测变量,

ω

k

、υ

k

分别为状态和测量噪声。目标跟踪可理解为

根据已知观测变量y

1∶k

和目标状态变量x

0∶k-1

求解x k的贝叶斯滤波问题,y1∶k表示1到k时刻的观测变

量,x

0∶k-1

表示初始到k-1时刻的状态变量。根据贝叶斯滤波理论,贝叶斯滤波的递推过程包括预测和更新两步,即

p(x k|y1∶k-1)=∫p(x k|x k-1)p(x k-1|y1∶k-1)d x k-1 p(x k|y1∶k)=C・p(y k|x k)∫p(x k|x k-1)p(x k-1|y1∶k-1)d x k-1其中,

C-1=∫p(y k|x k)p(x k|y k-1)d x k

对于线性高斯系统,概率密度函数可完全由均值和方差表示,这时状态变量的最小方差估计可由卡尔曼滤波方程给出。对于非线性非高斯过程,由于并不能找到一个通用的解析表达式用来描述所需要的概率密度函数,因此只有寻找近似算法来获得状态的贝叶斯估计[10]。近似算法包括扩展卡尔曼滤波、混合高斯滤波、基于网格的滤波、蒙特卡罗粒子滤波等等,在众多的近似算法中,蒙特卡罗粒子滤波正引起人们越来越多的关注。

在计算机视觉跟踪中,有许多种因素可能导致非线性、非高斯分布情况的出现,例如复杂的目标运动模型和系统状态的表达方式,而最常见的原因是由于图像中杂物的存在,从而导致了系统观测模型的非线性,以及由于背景图像中具有多个与前景目

第5期张海青等:基于蒙特卡罗方法的目标跟踪939

　标相似的观测变量,使得观测噪声也不能满足高斯

分布的要求,因此,一般的目标跟踪问题可以描述为在给定一组观测变量的条件下,对动态系统进行非线性非高斯滤波的问题。

212　蒙特卡罗粒子滤波

粒子滤波是用蒙特卡罗模拟方法来解决非线性

非高斯的贝叶斯滤波问题的,其主要思想是寻找一组在状态空间中传播的随机样本(带有权值的随机样本集)对后验密度进行近似,并以样本均值代替数学期望,来获得状态的最小方差估计。

粒子滤波器用带权值的粒子表示概率密度(如图2所示),粒子的中心是状态变量x 的随机抽样点,粒子的半径(权值)代表该抽样点处概率的大小

。

图2　概率密度用带权值的粒子近似

Fig 12　The p r obability density is app r oxi m ated by

several weighted sa mp les

这样k 时刻状态的后验概率分布可以用下式逼近:

p (x 0∶k |y 1∶k )≈

∑N

i =1

w

(i )

k δ(x 0∶k -x (i )

0∶k

)(3)

其中,w (i )

k 是k 时刻第i 个粒子的权值,N 为抽样数。

换句话说,如果能得到满足后验概率分布的抽样x (i )0∶k ～p (x 0∶k |y 1∶k ),那么就可以得到状态变量的后验概率密度,进而获得以下状态变量的估计:

E (g (x 0∶k ))=∫

g (x 0∶k )p (x 0∶k |y 1∶k )d x 0∶k

E ^(g (x 0∶k

))=1

N

∑N

i =1

g (x

(i )

0∶k

)(4)

然而,直接根据后验概率抽样是不可能的,由重要性

采样知,从一个已知的且容易抽样的概率密度得到

抽样x (i )

0∶k ～q (x 0∶k |y 1∶k )后,就可以获得以下状态变量和后验概率密度的估计:

E

^(g (x 0∶k

))=

∑N

i =1g (x

(i )

0∶k

)w k (x (i )

0:k )

p (x 0∶k |y 1∶k )≈

∑

N

i =1

w (i )

k δ(x 0∶k -x (i )

0∶k )

(5)

其中归一化的权重为

w k (x

(i )

0∶k

)=

w k (x (i )

0∶k )

∑

N

i =1

w k (x (i )

0∶k )

w k (x 0∶k )

=p (y 1∶k |x 0∶k )p (x 0∶k )

q (x 0∶k |y 1∶k )

　　重要性采样虽是一种常用的蒙特卡罗积分方

法,但是由于在它最简单的形式下,还不足以用来递

归估计,因此需使用序贯重要性采样(SI S )策略[11]

,

即在时间k 抽样时,不改动过去的抽样集。使用序贯重要性采样,可以得到以下递归形式的权重:

w k =w k -1

p (y k |x k )p (x k |x k -1)

q (x k |x 0∶k -1,y 1∶k )

(6)

　　然而序贯重要性采样粒子滤波器存在退化现象,即在经过数次迭代后只剩下一个粒子具有不可

忽视的权值,这说明重要性权值的方差会随时间增长而增加,而且此问题无法避免。为了克服SI S 算法存在的权重系数退化问题,可在SI S 递推过程中对由粒子及其相应权重表达的密度函数进行重新采样,其目的是减少小权重样本的数量,增加大权重样

本的数量,即在重采样过程中,权重较大的样本将多

次被复制,而权重较小的样本将可能被抛弃。综上所述,基本的粒子滤波器就是序贯重要性抽样和重抽样的结合。

213　目标跟踪

在基于粒子滤波的目标跟踪方法中,通常把物

体的运动模型描述为一个二阶自回归(AR )过程,

其模型参数可由先验知识或通过学习获得,而观测模型则根据应用选择。然而在大多数情况下,由于物体的运动模型和观测模型很难准确地得到,因此在基于粒子滤波的目标跟踪方法中,难点在于如何合理地建立与物体特征相关联的运动模型和非线性观测模型,因为模型建立的好坏直接影响着跟踪的效果。

3　基于蒙特卡罗方法的目标跟踪

本文从粒子滤波的蒙特卡罗方法得到启发,提出了一种新的目标跟踪方法。该方法基于蒙特

卡罗的方法,蒙特卡罗方法亦称为随机模拟方法、随机抽样技术或统计检验方法,它的基本思想是首先建立一个概率模型或随机过程,并使它的参数等于问题的解;然后通过对模型或过程的观测

940　中国图象图形学报第13卷

或抽样试验来计算所求参数的统计特征;最后给出所求解的近似值。本文的跟踪方法与基于粒子滤波的目标跟踪方法存在着一定的联系,但也有本质的区别。

311　目标模型

图像特征的提取与表达是目标跟踪的基础,这里图像的特征指的是图像的视觉特征(如色彩、纹理、形状、对象表面等)。其中颜色特征是在目标跟踪中应用广泛的视觉特征,其主要原因在于颜色往往和图像中所包含的物体或场景十分相关,且提取与表达较为简单,适用于实时跟踪的要求。此外,与其他的视觉特征相比,由于颜色特征对图像本身的尺寸、方向、视角的依赖性较小,从而具有较高的鲁棒性。

颜色直方图是在许多图像系统中被广泛采用的颜色特征,它所描述的是不同色彩在整幅图像中所占的比例,而并不关心每种色彩所处的空间位置。颜色直方图可以基于不同的颜色空间和坐标系,最常用的颜色空间是RG B 颜色空间。计算颜色直方图需要先将颜色空间划分成若干个小的颜色区间,每个小区间成为直方图的一个bin ,这个过程称为颜色量化;然后通过计算颜色落在每个小区间内的像素数量就可以得到颜色直方图。一般来说,颜色小区间的数目越多,直方图对颜色的分辨能力就越强,然而bin 的数目很大的颜色直方图会增加计算负担,不利于实时跟踪。本文把RG B 颜色空间均匀划分成8×8×8个bins ,并将取得的颜色直方图作为跟踪目标的特征。目标区域的颜色特征可由下式表示:

p j (y )=c ・

∑

n

i =1

δ[b (x i

)-j](7)

其中,c 为归一化系数,函数b ∶R 2

→{1,…,m }用于

计算每个像素x i 的颜色值,j 表示颜色直方图的颜色小区间的序号(j =1,…,m )。用同样的方法可以求得第u 个候选目标区域的颜色特征q j (y )。

本文使用Bhattacharyya 系数来描述目标和候选目标的相似程度:

ρ[p,q ]=

∑

m

j =1

p j ×q j (8)

定义它们之间的距离为

d =

1-ρ[p,q ](9)

312　跟踪算法

目标跟踪就是在当前帧中搜索使得距离函数取

得最小值时所对应的目标新位置。在实际情况下,

由于目标运动的灵活性和未知性,所以当前帧中目标可能出现在任意位置,但是考虑到相邻两帧中,目标位移不会太大,即满足“近邻”原则,目标应该在前一帧中的目标位置附近,而且距离越远出现的概率越小,而且各个方向出现的概率相同。如果用矩形框来表示跟踪目标的位置(如图3(a )所示),

那么假设当前帧中表示候选目标的矩形框的中心服从2维高斯分布是合理的。

图3　当前帧的候选目标

Fig 13　Candidate objects of current frame

因此,在当前帧中产生n 个矩形抽样,且这些矩形中心的分布服从2维高斯分布,高斯分布的均值为前一帧中表示目标的矩形的中心,而方差大小则反映了目标的运动速度。矩形中心坐标的蒙特卡罗

抽样可由Box 2Muller 方法[12]

产生,令随机变量x 和y 服从[0,1]的均匀分布,那么由式(10)表示的随机变量u 和v 服从2维高斯分布:N (μ,σ)

u =(-2ln x co s

πy )×σ+μv =(

-2ln x sin

πy )×σ+μ(10)

　　另外,考虑到相邻两帧目标大小也可能变化,由

“近邻”原则,相邻两帧中的目标大小变化不会太大,假设这种变化也服从高斯分布,即尺度变化小的

第5期张海青等:基于蒙特卡罗方法的目标跟踪941

　概率较大,尺度变化大的概率较小,高斯分布的均值

为前一帧中表示目标的矩形的尺度,而方差大小则反映了目标尺度的变化速率。综合矩形框的位置和尺度变化,当前帧候选目标区域的蒙特卡罗抽样如图3(b )所示。

取得第s 个抽样x s (包括位置和尺度)后,即可由式(7)计算每一抽样的颜色直方图,若用式(8)和式(9)计算每一抽样与参考目标的相似度和距离,并按距离大小赋予每一抽样一个权值w s ,则当前帧目标的跟踪结果可由下式计算得到:

x

^=∑n

s =1

w s

x

s

其中

w s =

1

2

πσ0exp

-

d 2s

σ

2

(11)

　　由于存在光照变化、目标形变和场景干扰等,因此必须考虑参考目标的更新。当表示当前帧目标的跟踪矩形与参考目标矩形的相似度大于某一阈值时,则目标模型(即参考目标直方图)更新为

p (j )k =(1-α)p (j )k -1+αq (j )

k (12)其中,p (j )

k 为更新后的目标模型,p (j )

k -1为更新前的目标模型,q (j )k 为当前帧的目标颜色模型,α为更新率。算法归纳如下:

(1)初始化目标,可以是手工初始化,也可以由运动检测等先前处理过程自动产生要跟踪的目标;

(2)计算目标参考模型,即颜色直方图;

(3)在下一帧中产生n 个蒙特卡罗抽样矩形,同时计算每一抽样与参考模型的相似度和距离,并由式(11)得到当前帧目标跟踪的结果;

(4)更新目标参考模型,并返回上一步。

313　与基于粒子滤波的目标跟踪方法的关系

前面介绍了粒子滤波理论,知道基于粒子滤波的跟踪方法需要建立与物体特征相关联的运动模型

和观测模型,即需要得到动态模型的转移概率和观测概率。如果把本文提出的基于蒙特卡罗方法的跟踪纳入贝叶斯滤波框架下,候选矩形框的位置和尺度表示目标的状态变量,颜色直方图为观测变量,则状态转移概率为一高斯分布,即

p (x k |x k -1)～N (μ,σ)

(13)其中,x k 为目标状态变量,μ=x k -1和σ反映了位移和尺度变化的大小。另外,基于蒙特卡罗的跟踪方法中,每一抽样的权重w s 可对应为以下观测概率:

p (y k |x k )∝exp (-λd 2

)(14)

　　通过式(13)和式(14)发现,本文提出的基于蒙特卡罗的跟踪方法与基于粒子滤波的跟踪方法具有内在的联系,即如果把本文提出的方法纳入贝叶斯滤波框架下,那么该方法就可以看作是基于粒子滤波跟踪方法的特例。但基于粒子滤波的跟踪方法中,只有初始产生的粒子进行迭代运算,因此为了保持算法的可靠性(解决粒子退化问题),需要引入重抽样

[11]

等其他策略;而基于蒙特

卡罗的跟踪方法中由于抽样粒子不进行迭代运算,故不存在退化问题,所以不需重抽样,即算法复杂度小。另外,两个方法本质上也是不同的,基于粒子滤波的跟踪方法实质为贝叶斯滤波框架下

的非线性非高斯滤波问题;而本文的方法实质为基于蒙特卡罗方法的特征匹配问题,是一种的跟踪方法。

4　实验结果和分析

为了说明并检验本文提出的跟踪方法的跟踪效果,使用下列视频测试序列进行了目标跟踪实验。

实验在PC 机(celer on CP U 1170G/W indows XP )上运行,视频图像帧的大小为300×245,使用RG B 颜色空间,并均匀划分为8×8×8个bins,抽样数为200。

本文方法适用于目标灵活运动、存在形变、尺度变化和环境光照变化等情况时的跟踪,下面选择几组视频序列进行说明。图4(a )中人体头部的运动无规律性,但采用本文的方法则能够得到很好的跟踪结果,其原因是由于蒙特卡罗方法只按“近邻”原则进行高斯抽样,故能适应实际跟踪中目标运动不可预测的情况。图4(b )中目标被短暂遮挡时,是采用参考目标更新策略,由于此时相似度未大于阈值,故不更新,所以目标重新出现时能够正确跟踪。另外,图4(b )中的跟踪目标附近有类似干扰,此时由于算法在真实目标附近的抽样数远远多于干扰目标处的抽样,因此按式(11)计算后,其最终结果会靠近真实目标,而不是干扰目标,若要更好地解决类似干扰,则理论上需要利用到目标的运动信息(特征),多特征的目标跟踪将在以后的研究中探讨。图4(c )中的目标存在尺度变化(由于摄像机的拍摄产生尺度变化而致),由于蒙特卡罗的方法在抽样时不仅考虑了位置变化,还考虑了尺度变化,所以可以很好地解决这一

942　中国图象图形学报第13卷

问题,且比mean 2shift 方法解决尺度问题简单有效。

从实验结果可以看到,基于蒙特卡罗的跟踪

方法算法不仅实现简单,且有较好的鲁棒性和通用性

。

图4　蒙特卡罗方法的跟踪结果

Fig 14　Tracking results with Monte Carl o methods

第5期张海青等:基于蒙特卡罗方法的目标跟踪943

5　结　论

本文提出了一种基于蒙特卡罗的目标跟踪方法,该方法不需要目标运动信息,就能够有效地跟踪灵活运动的目标,并能较好地解决场景干扰、目标遮挡和目标尺度变化等复杂情况。另外,通过分析基于粒子滤波的跟踪方法还发现,两种方法存在着联系,同时又存在着本质的区别。本文的目标跟踪方法是一种基于蒙特卡罗方法的特征匹配方法,也是一种的目标跟踪方法。通过实验证明,该方法不仅跟踪效果满意,且算法实现简单,可满足实时跟踪的要求。前面提到如果要使跟踪算法更加可靠,以适应多种环境变化,则理论上需要利用目标的多种特征,这将在以后的工作中研究。

参考文献(References)

1　Karaul ova I,Hall P,Marshall A.A hierachical model of dyna m ics for tracking peop le with a single video camera[A].I n:Pr oceedings of

B ritish Machine V isi on Conference[C],B rist ol,UK,2000:

352～361.

2　Ju S,B lack M,Yaccob Y.Cardboard peop le:a para meterized model of articulated i m age moti on[A].I n:Pr oceedings of I EEE

I nternati onal Conference on Aut omatic Face and gesture Recogniti on

[C],Killingt on,Ver mont,US A,1996:38～44.

3　W achter S,Nagel H H.Tracking pers ons in monocular i m age sequences[J].Computer V isi on and I m age Understanding,1999, 74(3):174～192.4　Paragi os N,Deriche R.Geodesic active cont ours and level sets f or the detecti on and tracking of moving objects[J].I EEE Transacti ons on Pattern Analysis and Machine I ntelligence,2000,22(3):266～280. 5　Segen J,Pingali S.A ca mera2based syste m for tracking peop le in real ti m e[A].I n:Pr oceedings I nternati onal Conference on Pattern recogniti on[C],V ienna,Austria,1996,63～67.

6　Nu mm iar o K,Merier E K,Gool L V.An adaptive col or2based particle filter[J].I m age and V isi on Co mputing,2003,21(1):99～110.

7　Lee Mun2wai,Cohen I,Soon Ki2Jung.Particle filter with analytical inference f or human body tracking[A].I n:Pr oceedings of I EEE

I nternati onal Conference on Moti on and V ideo Computing[C],

O rlando,Fl orida,US A,2002:159～165.

8　Comaniciu D,Ramesh V,Meer P.Real2ti m e tracking of non2rigid objects using mean shift[A].I n:Pr oceedings of I EEE I nternati onal Conference on Computer V isi on and Pattern Recogniti on[C],

H ilt on Head Island,South Car olina,US A,2000:142～149.

9　Collins R T.Mean2shift bl ob tracking thr ough scale s pace[A].I n: Pr oceedings of I EEE Computer Society Conference on Computer V isi on and Pattern Recogniti on[C],Madis on,W I,US A,2003: 234～240.

10　A rula mpala m M S,Maskell S,Gordon N,et al.A tut orial on particle filters for online nonlinear/non2Gaussian Bayesian tracking [J].I EEE Transacti ons on Signal Pr ocessing,2002,50(2):174～188. 11　Doucet A,Godsill S,Andrieu Ch.On sequential Monte Carl o samp ling methods for bayesian filtering[J].Statistics and Computing,2000,10(3):197～208.

12　Gerhard W inkler.I m age Analysis,Random Fields and Dyna m ic Monte Carl o Methods[M].Ne w York,US A:Sp ringer,1995: 293～294.