目标跟踪meanshift算法综述均值漂移

目标跟踪meanshift算法综述均值漂移

Mean Shift 概述

Mean Shift 简介

Mean Shift 这个概念最早是由Fukunaga等人[1]于1975年在一篇关于概率密度梯度函数的估计中提出来的,其最初含义正如其名,就是偏移的均值向量,在这里Mean Shift是一个名词,它指代的是一个向量,但随着Mean Shift理论的发展,Mean Shift的含义也发生了变化,如果我们说Mean Shift算法,一般是指一个迭代的步骤,即先算出当前点的偏移均值,移动该点到其偏移均值,然后以此为新的起始点,继续移动,直到满足一定的条件结束.

然而在以后的很长一段时间内Mean Shift并没有引起人们的注意,直到20年以后,也就是1995年,另外一篇关于Mean Shift的重要文献[2]才发表.在这篇重要的文献中,Yizong Cheng对基本的Mean Shift算法在以下两个方面做了推广,首先Yizong Cheng定义了一族核函数,使得随着样本与被偏移点的距离不同,其偏移量对均值偏移向量的贡献也不同,其次Yizong Cheng还设定了一个权重系数,使得不同的样本点重要性不一样,这大大扩大了Mean Shift的适用范围.另外Yizong Cheng指出了Mean Shift可能应用的领域,并给出了具体的例子.

Comaniciu等人[3][4]把Mean Shift成功的运用的特征空间的分析,在图像平滑和图像分割中Mean Shift都得到了很好的应用. Comaniciu等在文章中证明了,Mean Shift算法在满足一定条件下,一定可以收敛到最近的一个概率密度函数的稳态点,因此Mean Shift算法可以用来检测概率密度函数中存在的模态.

Comaniciu等人[5]还把非刚体的跟踪问题近似为一个Mean Shift最优化问题,使得跟踪可以实时的进行.

在后面的几节,本文将详细的说明Mean Shift的基本思想及其扩展,其背后的物理含义,以及算法步骤,并给出理论证明.最后本文还将给出Mean Shift在聚类,图像平滑,图像分割,物体实时跟踪这几个方面的具体应用.

Mean Shift 的基本思想及其扩展

基本Mean Shift

给定d维空间R中的n个样本点xi,i=1,…,n,在x点的Mean Shift向量的基本形式定义为:

d

Mh x

1

xi x kxi Sh

(1)

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

目标跟踪meanshift算法综述均值漂移

Sh x y: y x

T

y x h2 (2)

k表示在这n个样本点xi中,有k个点落入Sh区域中.

我们可以看到 xi x 是样本点xi相对于点x的偏移向量,(1)式定义的Mean Shift向量

Mh(x)就是对落入区域Sh中的k个样本点相对于点x的偏移向量求和然后再平均.从直观

上看,如果样本点xi从一个概率密度函数f x 中采样得到,由于非零的概率密度梯度指向概率密度增加最大的方向,因此从平均上来说, Sh区域内的样本点更多的落在沿着概率密度梯度的方向.因此,对应的, Mean Shift向量Mh(x)应该指向概率密度梯度的方向

.

图1,Mean Shift示意图

如上图所示, 大圆圈所圈定的范围就是Sh,小圆圈代表落入Sh区域内的样本点xi Sh,

黑点就是Mean Shift的基准点x,箭头表示样本点相对于基准点x的偏移向量,很明显的,我们可以看出,平均的偏移向量Mh(x)会指向样本分布最多的区域,也就是概率密度函数的梯度方向.

扩展的Mean Shift

2

核函数

首先我们引进核函数的概念.

定义:X代表一个d维的欧氏空间,x是该空间中的一个点,用一列向量表示. x的模

x xTx.R表示实数域.如果一个函数K:X R存在一个剖面函数k: 0, R,即

目标跟踪meanshift算法综述均值漂移

K(x) k x

2

并且满足:

(1) k是非负的.

(2) k是非增的,即如果a b那么k(a) k(b). (3) k是分段连续的,并且

k(r)dr

那么,函数K(x)就被称为核函数.

举例:在Mean Shift中,有两类核函数经常用到,他们分别是, 单位均匀核函数:

F(x)

1 if x 1

1

0 if x单位高斯核函数: 2

N(x) e

x

这两类核函数如下图所示

.

图2, (a) 单位均匀核函数 (b) 单位高斯核函数

一个核函数可以与一个均匀核函数相乘而截尾,如一个截尾的高斯核函数为,

2

xN

F e if x (x)

0 if x 图 3 显示了不同的 , 值所对应的截尾高斯核函数的示意图

.

图3 截尾高斯核函数 (a) N1

F0.1

1 (b) NF1

(3)

(4) (5)

(6)

目标跟踪meanshift算法综述均值漂移

Mean Shift扩展形式

从(1)式我们可以看出,只要是落入Sh的采样点,无论其离x远近,对最终的Mh(x)计算的贡献是一样的,然而我们知道,一般的说来,离x越近的采样点对估计x周围的统计特性越有效,因此我们引进核函数的概念,在计算Mh(x)时可以考虑距离的影响;同时我们也可以认为在这所有的样本点xi中,重要性并不一样,因此我们对每个样本都引入一个权重系数.

如此以来我们就可以把基本的Mean Shift形式扩展为:

M x

G

i 1

n

H

(xi x)w(xi)(xi x)

(7)

H

G

i 1

1/2

n

(xi x)w(xi)

其中:

GH(xi x) H

G H 1/2 xi x

G(x)是一个单位核函数

H是一个正定的对称d d矩阵,我们一般称之为带宽矩阵

w(xi) 0是一个赋给采样点xi的权重

2

2

在实际应用的过程中,带宽矩阵H一般被限定为一个对角矩阵H diag h1,...,hd ,甚至更简单的被取为正比于单位矩阵,即H hI.由于后一形式只需要确定一个系数h,在Mean Shift中常常被采用,在本文的后面部分我们也采用这种形式,因此(7)式又可以被写为:

2

Mh x

G(

i 1

n

xi x

)w(xi)(xi x)h

n

xi xG()w(xi) hi 1

(8)

我们可以看到,如果对所有的采样点xi满足

(1)w(xi) 1

1 if x 1

(2) G(x)

0 if x 1

则(8)式完全退化为(1)式,也就是说,我们所给出的扩展的Mean Shift形式在某些情况下会退

化为最基本的Mean Shift形式.

目标跟踪meanshift算法综述均值漂移

Mean Shift的物理含义

正如上一节直观性的指出,Mean Shift指向概率密度梯度方向,这一节将证明Mean Shift向量

Mh x 是归一化的概率密度梯度.在本节我们还给出了迭代Mean Shift算法的详细描述,并

证明,该算法会收敛到概率密度函数的一个稳态点.

概率密度梯度

对一个概率密度函数f(x),已知d维空间中n个采样点xi,i=1,…,n, f(x)的核函数估计(也称为Parzen窗估计)为,

xi x K i 1 w(xi)

h (x) f nd

h i 1w(xi)

n

(9)

其中

w(xi) 0是一个赋给采样点xi的权重

K(x)是一个核函数,并且满足 k(x)dx 1

我们另外定义:

概率密度函数f(x)的梯度 f(x)的估计为:

核函数K(x)的剖面函数k(x),使得K(x) k

x

2

2

(10);

k(x)的负导函数g(x),即g(x) k'(x),其对应的核函数G(x) gx

(11)

xi x'

2 i 1 x xi k

h f(x) f(x) n

…… 此处隐藏：8026字，全部文档内容请下载后查看。喜欢就下载吧 ……