目标跟踪——meanshift
Meanshift背景
Mean Shift 这个概念最早是由Fukunaga 于1975 年在一篇关于概率密 度梯度函数的估计中提出来的,其最初含义正如其名,就是偏移的均 值向量,在这里Mean Shift 是一个名词,它指代的是一个向量,但随着 Mean Shift 理论的发展,Mean Shift 的含义也发生了变化,如果我们说 Mean Shift 算法,一般是指一个迭代的步骤,即先算出当前点的偏移 均值,移动该点到其偏移均值,然后以此为新的起始点,继续移动,直到 满足一定的条件结束.
在计算机视觉中，最常用的是放射状对称核函数。
是放射状核函数 是 的轮廓函数 标准化常量 是个正数，保证 H为带宽矩阵。
积分为1
在实际中常采用H为单位矩阵的比例形式，即
KH
x
H12
1 KH 2x
若再考虑到 这个表达式就是基于核函数 的概率密度函数的估计
怎样找到数据集合中数据最密集的地方呢？
数据最密集的地方，对应于概率密度最大的地方。我们可 以对概率密度求梯度，梯度的方向就是概率密度增加最大 的方向，从而也就是数据最密集的方向。
目标模型的描述
在起始帧，通过鼠标确定一个包含所有目标特征的椭圆， 称为被跟踪目标的目标区域，这个目标区域也是核函数作 用的区域，区域的大小等于核函数的带宽。
对目标区域进行描述，常用的方法是按照直方图的方式 将图像像素的值域等分成k个区间，每个区间按照值域的大 小对应一个特征值。然后求出图像的像素值取每个特征值 的概率。
向量表示. X的模x 2 xT x 。K (x)表示该空间的核函
数，其定义为： K (x)= k（||X||）
(1)k 是非负的. (2) k是非增的,即 如果 那么
(3) k是分段连续的,并且 0 k(r)dr
• 常见的核函数
以上是均匀核、依潘涅契科夫核，双权核、高斯核、 双指数核、双依潘涅契科夫核。
Mean Shift 矢量
直观描述
感兴趣区域 质心
目的：找出最密集的区域 完全相同的桌球分布
Mean Shift
矢量
直观描述
感兴趣区域
质心
目的：找出最密集的区域 完全相同的桌球分布
Mean Shift
矢量
直观描述
感兴趣区域 质心
目的：找出最密集的区域 完全相同的桌球分布
Mean Shift
矢量
目标区域的中心为 ，假设其中有n个象素用 特征值的个数为m个 ,则目标模型的特征值 度估计为：
表示， 的概率密
q qu u1..m
m
qu 1
u1
为核函数的轮廓函数，由于遮挡或者背景的影响，目 标模型中心附近的象素比外物象素更可靠， 对中心的象素 给一个大的权值，而远离中心的象素一个小的权值
总得作用是判断目标区域中象素的值是否属于
令
,假设除了有限个点，轮廓函数 的梯度对所
有
均存在 。将 作为轮廓函数，核函数 为：
fh,K
x
2ck,d nhd2
n i1
xi xg
xxi h
2
2ck,d h2cg,d
ncgh,dd
n i1 g
xxi h
2ini1n1xgigxxhhxxi i 22x
基于核函数G(x)的 概率密度估计
直观描述
感兴趣区域 质心
目的：找出最密集的区域 完全相同的桌球分布
扩展的Mean Shift
• 核函数 • Mean Shift概率密度估计
为什么要引入核函数
1.克服了直方图估计对高维数据的失效性。 2.能够比较好的抑制噪声的影响 3.增强数据的有效性
核函数说明
对在d维欧式空间中，x表示该空间中的一个点，用一列
Mean shift向量
Mean shift向量的物理意义的什么呢？
为了更好地理解这个式子的物理意义，假设上式中g(x)=1 平均的偏移量会指向样本点最密的方向，也 就是概率密度函数梯度方向
均值漂移在目标跟踪中应用
1：目标模型叙述 2：候选目标叙述 3: 相似型函数比较 4：目标定位 5：整个算法流程
在Mean Shift中,有两类核函数经常用到,他们分别 是,单位均匀核函数:
F(x)
1 0
if if
x 1 x 1
单位高斯核函数:
N(x) e x 2
多维空间下的meanshift向量密度估计： 在d维欧式空间X中，x表示该空间中的一个点， 核函数, 空间中点x的概率密度估计值为:
表示该空间中的
Mean Shift示意图
直观描述
感兴趣区域 质心
目的：找出最密集的区域 完全相同桌球分布
Mean Shift 矢量
直观描述
感兴趣区域
质心
目的：找出最密集的区域 完全相同的桌球分布
Mean Shift 矢量
直观描述
感兴趣区域 质心
Objective : Find the densest region Distribution of identical billiard balls
第u个特征值。b(xi)是灰度值索引函数。属于该特征则值为1，
否则为0。
C是一个标准化的常量系数，使得
于是我们得到了基于图像灰度特征的颜色直方图。
基本Mean Shift
• 给定d维空间R d中的n个样本点 ,i=1,…,n,在 点的Mean Shift向量的基
本形式定义为:
Mh
x
1 k xiSh
xi
x
• 其中, S h 是一个半径为h的高维球区域,满足以下关系的y 点的集合,
S hx y :y x T y x h 2
• k表示在这n个样本点 中,有k个点落入S h 区域中.
Meanshift背景
• 然而在以后的很长一段时间内Mean Shift 并没有引起人们的注意, 直到20 年以后,也就是1995 年,另外一篇关于Mean Shift 的重要文 献才发表.在这篇重要的文献中,Yizong Cheng对基本的Mean Shift 算法在以下两个方面做了推广,首先Yizong Cheng 定义了一族核函 数,使得随着样本与被偏移点的距离不同,其偏移量对均值偏移向 量的贡献也不同,其次YizongCheng 还设定了一个权重系数,使得不 同的样本点重要性不一样,这大大扩大了Mean Shift 的适用范围.另 外Yizong Cheng 指出了Mean Shift 可能应用的领域,并给出了具体 的例子.