meanshift算法综述均值漂移.doc-资料库

u011056525-5574971-4744302542929970796.doc.pdf-第1页.png

第1页 / 共21页

u011056525-5574971-4744302542929970796.doc.pdf-第2页.png

第2页 / 共21页

u011056525-5574971-4744302542929970796.doc.pdf-第3页.png

第3页 / 共21页

u011056525-5574971-4744302542929970796.doc.pdf-第4页.png

第4页 / 共21页

u011056525-5574971-4744302542929970796.doc.pdf-第5页.png

第5页 / 共21页

u011056525-5574971-4744302542929970796.doc.pdf-第6页.png

第6页 / 共21页

u011056525-5574971-4744302542929970796.doc.pdf-第7页.png

第7页 / 共21页

u011056525-5574971-4744302542929970796.doc.pdf-第8页.png

第8页 / 共21页

mean shift 及其改进算法图像跟踪原理和应用 Mean Shift 简介 Mean Shift 这个概念最早是由 Fukunaga 等人于 1975 年在一篇关于概率密度梯度函数的估计中提出来的,其最初含义正如其名,就是偏移的均值向量,在这里 Mean Shift 是一个名词,它指代的是一个向量,但随着 Mean Shift 理论的发展,Mean Shift 的含义也发生了变化,如果我们说 Mean Shift 算法,一般是指一个迭代的步骤,即先算出当前点的偏移均值,移动该点到其偏移均值,然后以此为新的起始点,继续移动,直到满足一定的条件结束. 然而在以后的很长一段时间内 Mean Shift 并没有引起人们的注意, 直到 20 年以后,也就是 1995 年,另外一篇关于 Mean Shift 的重要文献才发表.在这篇重要的文献中,Yizong Cheng 对基本的 Mean Shift 算法在以下两个方面做了推广,首先 Yizong Cheng 定义了一族核函数,使得随着样本与被偏移点的距离不同,其偏移量对均值偏移向量的贡献也不同,其次 Yizong Cheng 还设定了一个权重系数,使得不同的样本点重要性不一样,这大大扩大了 Mean Shift 的适用范围.另外 Yizong Cheng 指出了 Mean Shift 可能应用的领域,并给出了具体的例子. Comaniciu 等人把 Mean Shift 成功的运用的特征空间的分析,在图

像平滑和图像分割中 Mean Shift 都得到了很好的应用. Comaniciu 等在文章中证明了,Mean Shift 算法在满足一定条件下,一定可以收敛到最近的一个概率密度函数的稳态点,因此 Mean Shift 算法可以用来检测概率密度函数中存在的模态. Comaniciu 等人还把非刚体的跟踪问题近似为一个 Mean Shift 最优化问题,使得跟踪可以实时的进行. 在后面的几节,本文将详细的说明 Mean Shift 的基本思想及其扩展, 其背后的物理含义,以及算法步骤,并给出理论证明.最后本文还将给出 Mean Shift 在物体实时跟踪这个方面的具体应用. Mean Shift 的基本思想及其扩展基本 Mean Shift 给定 d 维空间 dR 中的 n 个样本点 ix ,i=1,…,n,在 x 点的 Mean Shift 向量的基本形式定义为:  M x h   1 k  x S i h  x i  x  (1) 其中, hS 是一个半径为 h 的高维球区域,满足以下关系的 y 点的集合,  hS x    y  : y  x T   y  x   h 2 (2) k 表示在这 n 个样本点 ix 中,有 k 个点落入 hS 区域中. 我们可以看到 ix x 是样本点 ix 相对于点 x 的偏移向量,(1)式定义 

的 Mean Shift 向量 ( ) hM x 就是对落入区域 hS 中的 k 个样本点相对于点 x 的偏移向量求和然后再平均.从直观上看,如果样本点 ix 从一个概率密度函数  f x 中采样得到,由于非零的概率密度梯度指向概率密度增  加最大的方向,因此从平均上来说, hS 区域内的样本点更多的落在沿着概率密度梯度的方向.因此,对应的, Mean Shift 向量 ( ) hM x 应该指向概率密度梯度的方向 . 图 1,Mean Shift 示意图如上图所示, 大圆圈所圈定的范围就是 hS ,小圆圈代表落入 hS 区域 x 内的样本点 i S ,黑点就是 Mean Shift 的基准点 x ,箭头表示样本点相 h 对于基准点 x 的偏移向量,很明显的,我们可以看出,平均的偏移向量 hM x 会指向样本分布最多的区域,也就是概率密度函数的梯度方向. ( ) 扩展的 Mean Shift 核函数首先我们引进核函数的概念.

定义: X 代表一个 d 维的欧氏空间, x 是该空间中的一个点,用一列向量表示. x 的模 2 x  T x x . R 表示实数域.如果一个函数 :K X R 存在一个剖面函数  : 0, k    ,即 R ( )K x  k  2 x (3) 并且满足: (1) k 是非负的. (2) k 是非增的,即如果 a b 那么 ( ) k a ( ) k b . (3) k 是分段连续的,并且  那么,函数 ( )K x 就被称为核函数.  0 ( ) k r dr   举例:在 Mean Shift 中,有两类核函数经常用到,他们分别是, 单位均匀核函数: ( ) F x 1 if    0 if  x x   1 1 (4) 单位高斯核函数: ( ) N x e 2 x (5) 这两类核函数如下图所示.

图 2, (a) 单位均匀核函数 (b) 单位高斯核函数一个核函数可以与一个均匀核函数相乘而截尾,如一个截尾的高斯核函数为,   N F   ( ) x x   2 if e   0 if  x x     (6) 图 3 显示了不同的 ,值所对应的截尾高斯核函数的示意图. 图 3 截尾高斯核函数 (a) 1 1N F (b) 0.1 N F 1 Mean Shift 扩展形式从(1)式我们可以看出,只要是落入 hS 的采样点,无论其离 x 远近,对最终的 ( ) hM x 计算的贡献是一样的,然而我们知道,一般的说来,离 x 越近的采样点对估计 x 周围的统计特性越有效,因此我们引进核函数的概念, 在计算 ( ) hM x 时可以考虑距离的影响;同时我们也可以认为在这所有的样本点 ix 中,重要性并不一样,因此我们对每个样本都引入一个权重系数. 如此以来我们就可以把基本的 Mean Shift 形式扩展为:

n  i 1   M x   ( G x i H  ( ) x w x i )( x i  x ) n  i 1  ( G x i H  ) ( x w x i ) (7) 其中: 阵 ( G x i H  x )  H  1/ 2  G H  1/ 2  x i  x   ( )G x 是一个单位核函数 H 是一个正定的对称 d d 矩阵,我们一般称之为带宽矩 ( iw x  是一个赋给采样点 ix 的权重 ) 0 在实际应用的过程中, 带宽矩阵 H 一般被限定为一个对角矩阵 H  diag 2 h 1   ,..., h 2 d  ,甚至更简单的被取为正比于单位矩阵,即  2 H h I  .由于后一形式只需要确定一个系数 h ,在 Mean Shift 中常常被采用,在本文的后面部分我们也采用这种形式,因此(7)式又可以被写为: x i  h ( G x x i ) ( w x )( x i i  x ) x  h ) ( w x ) i G ( n  i 1  n  i 1   M x h   (8) 我们可以看到,如果对所有的采样点 ix 满足 (1) ( ) 1 iw x  (2) ( ) G x 1 if    0 if  x x   1 1 则(8)式完全退化为(1)式,也就是说,我们所给出的扩展的 Mean Shift 形式在某些情况下会退化为最基本的 Mean Shift 形式.

Mean Shift 的物理含义正如上一节直观性的指出,Mean Shift 指向概率密度梯度方向,这一节将证明 Mean Shift 向量  hM x 是归一化的概率密度梯度.在本节我们还  给出了迭代 Mean Shift 算法的详细描述,并证明,该算法会收敛到概率密度函数的一个稳态点. 概率密度梯度对一个概率密度函数 ( ) f x ,已知 d 维空间中 n 个采样点 ix ,i=1,…,n, f x 的核函数估计(也称为 Parzen 窗估计)为, ( ) ˆ( ) f x  其中  n 1 i  x i  K    d h ( w x i ) x    h  ( w x n 1 i  ) i ( iw x  是一个赋给采样点 ix 的权重 ) 0 ( )K x 是一个核函数,并且满足 ( ) k x dx   (9) 1 我们另外定义: 核函数 ( )K x 的剖面函数 ( ) k x ,使得 ( )K x  k  2 x (10); k x 的负导函数 ( )g x ,即 ( ) ( ) g x   ' ( ) k x ,其对应的核函数 ( )G x   g x 2 (11)

概率密度函数 ( ) f x 的梯度 ( ) 2  n 1 i   x  ˆ  ( ) f x   ˆ ( ) f x  ' 2 x x i     f x 的估计为:     n 1 i  ( )G x  h ( w x i ( w x i  g x 2  , ) )   x k i  ' ( ) k x 2 d h     n i  1 i x  h ( w x ( w x ) i 2 x     ) i 由上面的定义, ( ) g x   ,上式可以重写为 2  n i  1  x i   x G d  2 h  x i ˆ  f ( x )    n i  1 G d h 2 2 h            h x    ( w x n i  1 ( w x ) i ) i               n i  1  x i   x G  n i  1 G x    ( w x ) i     i x i x  h  h    2 x ( w x     ) i        (12) (13) 上式右边的第二个中括号内的那一部分就是(8)式定义的 Mean Shift 向量,第一个中括号内的那一部分是以 ( )G x 为核函数对概率密度函数 f x 的估计,我们记做 ˆ ( ) ( ) x ,而(9)式定义的 ˆ( ) f x 我们重新记做 ˆ ( ) x ,因 Kf Gf 此(11)式可以重新写为: ˆ ( ) x Kf ˆ ( ) f x   2 ˆ ( ) h f G 2  x M x h 由(12)式我们可以得出,  M x h   1 2 2 h ˆ ( ) f x  K ˆ ( ) x f G  (14) (15) (15)式表明,用核函数 G 在 x 点计算得到的 Mean Shift 向量  hM x 正比  于归一化的用核函数 K 估计的概率密度的函数 ˆ ( ) x 的梯度,归一化因 Kf 子为用核函数 G 估计的 x 点的概率密度.因此 Mean Shift 向量  hM x 总  是指向概率密度增加最大的方向.

资料库

meanshift算法综述均值漂移.doc

相关推荐

开发技术

热门标签

最新资料