下载文档原格式
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 维空间dR 中的n 个样本点i x ,i=1,…,n,在x 点的Mean Shift 向量的基本形式定义为:()()1i hh i x S M x x x k ∈≡-∑ (1)其中,h S 是一个半径为h 的高维球区域,满足以下关系的y 点的集合,()()(){}2:Th S x y y x y x h ≡--≤ (2)k 表示在这n 个样本点i x 中,有k 个点落入h S 区域中.我们可以看到()i x x -是样本点i x 相对于点x 的偏移向量,(1)式定义的Mean Shift 向量()h M x 就是对落入区域h S 中的k 个样本点相对于点x 的偏移向量求和然后再平均.从直观上看,如果样本点i x 从一个概率密度函数()f x 中采样得到,由于非零的概率密度梯度指向概率密度增加最大的方向,因此从平均上来说, h S 区域内的样本点更多的落在沿着概率密度梯度的方向.因此,对应的, Mean Shift 向量()h M x 应该指向概率密度梯度的方向.图1,Mean Shift 示意图如上图所示, 大圆圈所圈定的范围就是h S ,小圆圈代表落入h S 区域内的样本点i h x S ∈,黑点就是Mean Shift 的基准点x ,箭头表示样本点相对于基准点x 的偏移向量,很明显的,我们可以看出,平均的偏移向量()h M x 会指向样本分布最多的区域,也就是概率密度函数的梯度方向.扩展的Mean Shift核函数首先我们引进核函数的概念.定义:X 代表一个d 维的欧氏空间,x 是该空间中的一个点,用一列向量表示. x 的模2T x x x =.R 表示实数域.如果一个函数:K X R →存在一个剖面函数[]:0,k R ∞→,即()2()K x k x=(3)并且满足:(1) k 是非负的.(2) k 是非增的,即如果a b <那么()()k a k b ≥. (3) k 是分段连续的,并且()k r dr ∞<∞⎰那么,函数()K x 就被称为核函数.举例:在Mean Shift 中,有两类核函数经常用到,他们分别是, 单位均匀核函数:1 if 1()0 if 1 x F x x ⎧<⎪=⎨≥⎪⎩(4)单位高斯核函数:2()xN x e-= (5)这两类核函数如下图所示.图2, (a) 单位均匀核函数 (b) 单位高斯核函数一个核函数可以与一个均匀核函数相乘而截尾,如一个截尾的高斯核函数为,()2if ()0 ifx e x N F x x ββλλλ-⎧<⎪=⎨≥⎪⎩ (6)图 3 显示了不同的,βλ值所对应的截尾高斯核函数的示意图.图3 截尾高斯核函数 (a) 11N F (b) 0.11N FMean Shift 扩展形式从(1)式我们可以看出,只要是落入h S 的采样点,无论其离x 远近,对最终的()h M x 计算的贡献是一样的,然而我们知道,一般的说来,离x 越近的采样点对估计x 周围的统计特性越有效,因此我们引进核函数的概念,在计算()h M x 时可以考虑距离的影响;同时我们也可以认为在这所有的样本点i x 中,重要性并不一样,因此我们对每个样本都引入一个权重系数.如此以来我们就可以把基本的Mean Shift 形式扩展为:()11()()()()()nHi i i i nHi i i Gx x w x x x M x Gx x w x ==--≡-∑∑ (7)其中: ()()1/21/2()H i i G x x HG H x x ---=-()G x 是一个单位核函数H 是一个正定的对称d d ⨯矩阵,我们一般称之为带宽矩阵()0i w x ≥是一个赋给采样点i x 的权重在实际应用的过程中,带宽矩阵H 一般被限定为一个对角矩阵221diag ,...,d H h h ⎡⎤=⎣⎦,甚至更简单的被取为正比于单位矩阵,即2H h I =.由于后一形式只需要确定一个系数h ,在Mean Shift 中常常被采用,在本文的后面部分我们也采用这种形式,因此(7)式又可以被写为:()11()()()()()ni i i i h ni i i x xG w x x x hM x x x G w x h ==--≡-∑∑ (8)我们可以看到,如果对所有的采样点i x 满足(1)()1i w x =(2) 1 if 1()0 if 1 x G x x ⎧<⎪=⎨≥⎪⎩则(8)式完全退化为(1)式,也就是说,我们所给出的扩展的Mean Shift 形式在某些情况下会退化为最基本的Mean Shift 形式.Mean Shift 的物理含义正如上一节直观性的指出,Mean Shift 指向概率密度梯度方向,这一节将证明Mean Shift 向量()h M x 是归一化的概率密度梯度.在本节我们还给出了迭代Mean Shift 算法的详细描述,并证明,该算法会收敛到概率密度函数的一个稳态点.概率密度梯度对一个概率密度函数()f x ,已知d 维空间中n 个采样点i x ,i=1,…,n, ()f x 的核函数估计(也称为Parzen 窗估计)为,11()ˆ()()ni i i n di i x x K w x h f x h w x ==-⎛⎫ ⎪⎝⎭=∑∑ (9)其中()0i w x ≥是一个赋给采样点i x 的权重()K x 是一个核函数,并且满足()1k x dx =⎰我们另外定义: 核函数()K x 的剖面函数()k x ,使得()2()K x kx=(10);()k x 的负导函数()g x ,即'()()g x k x =-,其对应的核函数()2()G x g x= (11)概率密度函数()f x 的梯度()f x ∇的估计为:()2'1212()ˆˆ()()()ni i i i nd i i x x x x k w x h f x f x h w x =+=⎛⎫--⎪ ⎪⎝⎭∇=∇=∑∑(12)由上面的定义, '()()g x k x =-,()2()G x gx=,上式可以重写为()()21212112112()ˆ()()()()2 ()()nii i i nd i i n i n i i i i i i n d n i i i i i x xx x G w x h f x h w x x x x x x x G w x G w x h h x x h h w x G w x h =+=====⎛⎫-- ⎪ ⎪⎝⎭∇=⎡⎤⎛⎫-⎡-⎤⎛⎫-⎢⎥ ⎪ ⎪ ⎪⎢⎥⎢⎥⎝⎭⎝⎭⎢⎥=⎢⎥-⎛⎫⎢⎥⎢⎥ ⎪⎢⎥⎝⎭⎢⎥⎣⎦⎣⎦∑∑∑∑∑∑ (13)上式右边的第二个中括号内的那一部分就是(8)式定义的Mean Shift 向量,第一个中括号内的那一部分是以()G x 为核函数对概率密度函数()f x 的估计,我们记做ˆ()Gf x ,而(9)式定义的ˆ()f x 我们重新记做ˆ()Kf x ,因此(11)式可以重新写为: ˆ()f x ∇=ˆ()K f x ∇=()22ˆ()Gh f x M x h(14)由(12)式我们可以得出,()2ˆ()1ˆ2()Kh G f x M x h f x ∇= (15)(15)式表明,用核函数G 在x 点计算得到的Mean Shift 向量()h M x 正比于归一化的用核函数K 估计的概率密度的函数ˆ()Kf x 的梯度,归一化因子为用核函数G 估计的x 点的概率密度.因此Mean Shift 向量()h M x 总是指向概率密度增加最大的方向.Mean Shift 算法 算法步骤我们在前面已经指出,我们在提及Mean Shift 向量和Mean Shift 算法的时候指代不同的概念,Mean Shift 向量是名词,指的是一个向量;而Mean Shift 算法是动词,指的是一个迭代的步骤.我们把(8)式的x 提到求和号的外面来,可以得到下式,()11()()()()ni i i i h n i i i x xG w x x hM x x x x G w x h ==-=--∑∑(16)我们把上式右边的第一项记为()h m x ,即11()()()()()ni i i i h n i i i x xG w x x hm x x x G w x h ==-=-∑∑(17)给定一个初始点x ,核函数()G X , 容许误差ε,Mean Shift 算法循环的执行下面三步,直至结束条件满足, (1).计算()h m x(2).把()h m x 赋给x(3).如果()h m x x ε-<,结束循环;若不然,继续执行(1).由(16)式我们知道, ()()h h m x x M x =+,因此上面的步骤也就是不断的沿着概率密度的梯度方向移动,同时步长不仅与梯度的大小有关,也与该点的概率密度有关,在密度大的地方,更接近我们要找的概率密度的峰值,Mean Shift 算法使得移动的步长小一些,相反,在密度小的地方,移动的步长就大一些.在满足一定条件下,Mean Shift 算法一定会收敛到该点附近的峰值,这一收敛性由下面一小节给出证明.算法的收敛性证明我们用{}j y ,1,2,...j =来表示Mean Shift 算法中移动点的痕迹,由(17)式我们可写为,111()()()()ni ji i i j ni j i i x y G w x x hy x y G w x h =+=-=-∑∑, 1,2,...j = (18) 与j y 对应的概率密度函数估计值ˆ()jf y 可表示为, 11()ˆ()()ni j i i K j n di i x y K w x h f y h w x ==-⎛⎫⎪⎝⎭=∑∑ (19)下面的定理将证明序列{}j y 和{}ˆ()jf y 的收敛性. 定理:如果核函数()K x 有一个凸的,单调递增的剖面函数,核函数()G x 由式(10)和(11)定义,则序列{}j y 和{}ˆ()jf y 是收敛的. 证明:由于n 是有限的,核函数()(0)K x K ≤,因此序列{}ˆ()j f y 是有界的,所以我们只需要证明{}ˆ()jf y 是严格递增的的,即要证明,对所有j=1,2,…如果1j j y y +≠,那么ˆ()j f y 1ˆ()j f y +< (20)不失一般性,我们可以假设0j y =,由(19)式和(10)式,我们可以得到1ˆ()j f y +ˆ()j f y -=221111 ()()n i j i ji ni d i i x y x y k k w x h h h w x +==⎡⎤⎛⎫⎛⎫--⎢⎥ ⎪ ⎪- ⎪ ⎪⎢⎥⎝⎭⎝⎭⎣⎦∑∑ (21)由于剖面函数()k x 的凸性意味着对所有12,[0,)x x ∈∞且12x x ≠,有'2121()()()()k x k x k x x x ≥+-(22)因为'()()g x k x =-,上式可以写为,2112()()()()k x k x g x x x -≥-(23)结合(21)与(23)式,可以得到,1ˆ()j f y +ˆ()jf y -222111211()()ni j i j i i n i d i i x y g x y x w x h h w x ++=+=⎛⎫-⎡⎤⎪≥--⎢⎥⎣⎦ ⎪⎝⎭∑∑221111211 2()()ni j T j i j i n i d i i x y g y x y w x h h w x +++=+=⎛⎫-⎡⎤⎪=-⎢⎥⎣⎦ ⎪⎝⎭∑∑12221211112()()()j n nT ii i i j i n d i i i i x x y x g w x y g w x h h h w x +++===⎡⎤⎛⎫⎛⎫=-⎢⎥ ⎪ ⎪ ⎪ ⎪⎢⎥⎝⎭⎝⎭⎣⎦∑∑∑(24)由(18)式我们可以得出,1ˆ()j f y +ˆ()jf y -2211211()n ij n i d i i x y g hhw x +=+=⎛⎫≥ ⎪ ⎪⎝⎭∑∑(25)由于剖面函数()k x 是单调递减的,所以求和项210ni i x g h =⎛⎫> ⎪ ⎪⎝⎭∑,因此,只要10j j y y +≠= (25)式的右边项严格大于零,即1ˆ()j f y +ˆ()jf y >.由此可证得,序列{}ˆ()j f y 收敛 为了证明序列{}j y 的收敛性,对于0j y ≠,(25)式可以写为1ˆ()j f y +ˆ()jf y -2211211()ni j j jn i d i i x y y y g hhw x +=+=⎛⎫- ⎪≥- ⎪⎝⎭∑∑(26) 现在对于标号j,j+1,…,j+m -1,对(26)式的左右两边分别求和,得到 ˆ()j m f y +ˆ()jf y -22111211...()ni j m j m j m ni d i i x y y y g h h w x +-++-=+=⎛⎫- ⎪≥-+ ⎪⎝⎭∑∑2211211()ni jj jn i d i i x y y y g hhw x +=+=⎛⎫- ⎪+- ⎪⎝⎭∑∑2211211...()j m j m j j n d i i y y y y M h w x ++--+=⎡⎤≥-++-⎢⎥⎣⎦∑2211()j m j n d i i y y M hw x ++=≥-∑(27)其中M 表示对应序列{}j y 的所有求和项21ni ji x y g h =⎛⎫-⎪ ⎪⎝⎭∑的最小值.由于{}ˆ()j f y 收敛,它是一个Cauchy 序列,(27)式意味着{}jy 也是一个Cauchy 序列,因此,序列{}j y 收敛.Mean Shift 的应用从前面关于Mean Shift 和概率密度梯度的关系的论述,我们可以清楚的看到,Mean Shift算法本质上是一个自适应的梯度上升搜索峰值的方法,如下图所示,如果数据集{},1,...i x i n =服从概率密度函数f(x),给定一个如图初始点x ,Mean Shift 算法就会一步步的移动,最终收敛到第一个峰值点.从这张图上,我们可以看到Mean Shift 至少有如下三方面的应用:(1)聚类,数据集{},1,...i x i n =中的每一点都可以作为初始点,分别执行Mean Shift 算法,收敛到同一个点算作一类;(2)模态的检测,概率密度函数中的一个峰值就是一个模态,Mean Shift 在峰值处收敛,自然可以找到该模态.(3)最优化,Mean Shift 可以找到峰值,自然可以作为最优化的方法,Mean Shift 算法进行最优化的关键是要把最优化的目标转化成Mean Shift 隐含估计的概率密度函数.图4.Mean Shift 算法示意图Mean Shift 算法在许多领域获得了非常成功的应用,下面简要的介绍一下其在图像平滑,图像分割以及物体跟踪中的应用,一来说明其强大的生命力,二来使对上文描述的算法有一个直观的了解.图像平滑与分割一幅图像可以表示成一个二维网格点上p 维向量,每一个网格点代表一个象素,1p =表示这是一个灰度图,3p =表示彩色图,3p >表示一个多谱图,网格点的坐标表示图像的空间信息.我们统一考虑图像的空间信息和色彩(或灰度等)信息,组成一个2p +维的向量(,)s r x x x =,其中s x 表示网格点的坐标,r x 表示该网格点上p 维向量特征.我们用核函数,s r h h K 来估计x 的分布, ,s r h h K 具有如下形式,22,2s rs r h h p s r sr C x x K k k h h h h ⎛⎫⎛⎫ ⎪ ⎪= ⎪ ⎪⎝⎭⎝⎭ (28)其中,s r h h 控制着平滑的解析度,C 是一个归一化常数.我们分别用i x 和i z ,i =1,…,n 表示原始和平滑后的图像.用Mean Shift 算法进行图像平滑的具体步骤如下, 对每一个象素点, 1,初始化1j =,并且使,1i i y x =2,运用Mean Shift 算法计算,1i j y +,直到收敛.记收敛后的值为,i c y3.赋值(),,s r i i i c z x y =图5是原始图像,图中40⨯20白框区域被选中来更好的显示基于Mean Shift 的图像平滑步骤,图6显示了这一区域的平滑步骤,x, y 表示这一区域内的象素点的坐标,图6(a)在一个三维空间显示了各个象素点的灰度值,图6(b)显示各点的移动痕迹,黑点是最终收敛值,图6(c)显示了平滑后的各象素点的灰度值,图6(d)是继续分割后的结果.图5.原始图像图6.(a)原始图像的各象素点灰度值.(b)各象素点的Mean Shift移动路径.(c)平滑后的各象素点的灰度值.(d)分割后的结果图7显示了图5经过平滑后的结果,我们可以看到,草地上的草地纹理被平滑掉了,而图像中边缘仍然很好的保持着..图7平滑后的结果h h是非常重要的参数,人们可以根据解析度的在基于Mean Shift的图像平滑中,式(28)中的,s rh h会对最终的平滑结果有一定的影响,图7显示了这两个参数对平要求而直接给定,不同,s rh影响更大一些.滑结果的影响,我们可以看出,s图8,原始图和平滑后的图基于Mean Shift的图像分割与图像平滑非常类似,只需要把收敛到同一点的起始点归为一类,然后把这一类的标号赋给这些起始点,在图像分割中有时还需要把包含象素点太少类去掉,图6(d)显示分割后的灰度值.图8,显示了图5经过分隔后的结果图8,分割后的结果物体跟踪我们用一个物体的灰度或色彩分布来描述这个物体,假设物体中心位于0x ,则该物体可以表示为()21ˆi i s ns u i x xqC k b x u h δ=⎛⎫- ⎪⎡⎤=-⎣⎦ ⎪⎝⎭∑(29)候选的位于y 的物体可以描述为()21ˆ()hn s s i u h i i x ypy C k b x u h δ=⎛⎫-⎡⎤ ⎪=-⎣⎦ ⎪⎝⎭∑(30)因此物体跟踪可以简化为寻找最优的y ,使得ˆ()u py 与ˆu q 最相似. ˆ()u py 与ˆu q 的最相似性用Bhattacharrya 系数ˆ()y ρ来度量分布,即 []ˆ()(),mu y p y q ρρ=≡= (31)式(31)在ˆu p()0ˆy 点泰勒展开可得,[]1111(),(22m mu u u p y q p y ρ==≈∑(32)把式(30)带入式,整理可得,[]2111(),22mnhii u i C y x p y q w k h ρ==⎛⎫-≈ ⎪ ⎪⎝⎭∑ (33)其中,1[()mi i u w b x u δ==-∑对式(33)右边的第二项,我们可以利用Mean Shift 算法进行最优化.在Comaniciu 等人的文章中,他们只用平均每帧图像只用4.19次Mean Shift 迭代就可以收敛,他们的结果很显示在600MHz 的PC 机上,他们的程序可以每秒处理30帧352⨯240象素的图像.下图显示了各帧需要的Mean Shift 迭代次数.图9,各帧需要的Mean Shift迭代次数下图显示了Comaniciu等人的跟踪结果图10,基于Mean Shift的物体跟踪结果结论本文回顾了Mean Shift的发展历史,介绍了它的基本思想,给出了具体的算法步骤,详细证明了它与梯度上升搜索法的联系,并给出Mean Shift算法的收敛性证明,最后给出了Mean Shift在图像平滑,图像分割以及实时物体跟踪中的具体应用,显示Mean Shift强大的生命力.参考文献[1]The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition (1975)[2]Mean shift, mode seeking, and clustering (1995)[3]Mean Shift: a robust approach toward feature space analysis (2002)[4]Real-time tracking of non-rigid objects using mean shift (2000)[5]Mean-shift Blob Tracking through Scale Space (2003)[6]An algorithm for data-driven bandwidth selection(2003)。
基于Mean Shift视频运动目标跟踪作者：魏保华来源：《计算机光盘软件与应用》2014年第01期摘要：视频监控是安全防范系统的重要组成部分，而视频运动目标检测和跟踪技术则是智能视频监控的关键技术。
Mean Shift算法是一种在一组数据的密度分布中寻找局部极值的稳定的方法，并因其它计算量小，简单易实现而广泛应用于实时跟踪场合。
在离散的数据集上，Mean Shift能很快的找到数据分布最密集的点，本文介绍了使用OpenCV实现Mean Shift的方法，分析其在跟踪方向的优势与不足。
关键词：目标跟踪；OpenCV；Mean；Shift；颜色直方图中图分类号：TP391.41视觉是人类从外界获取信息的主要途径。
运用摄影机和电脑代替人眼对目标进行识别、跟踪和测量，将三维环境信息储存为二维信息，并进一步做图像处理，合成为更适合人眼观察或传送给仪器检测的图像。
计算机视觉试图建立能够从图像或者多维数据中获取…信息‟的人工智能系统。
在这些应用领域中，如何利用计算机把运动目标从有干扰的背景中检测出来并对其进行识别、跟踪、管理等处理是需要研究的关键技术。
1 视频运动目标跟踪20世纪60年代后期，蒙特卡罗方法被引入自动控制领域。
1975年，Fukmaga等人在一篇关于概率密度梯度函数的估计中提出Mean shift。
1995年，Yizong Cheng在“Mean shift mode seeking and clustering”中定义了一族核函数，设定了一个权重系数，扩充了基本Mean Shift算法，扩大了其适用范围。
1999年，Intel公司在均值偏移理论的基础上建立了CAMSHIb'T算法，以及基于此算法的人脸跟踪系统，将均值偏移算法扩展到运动目标跟踪领域中。
基于Mean shift的研究有许多成果发表[1-3]。
2000年，Comaniciu[4-5]等人将Mean Shift作用于非刚性物体的实施跟踪。
mean-shift算法公式Mean-shift算法是一种无参聚类算法，常用于图像分割、目标跟踪和模式识别等领域。
本文将详细介绍mean-shift算法的原理、公式和实际应用场景。
一、原理Mean-shift算法的核心思想是密度估计和质心漂移。
它基于高斯核函数，通过不断更新质心，最终将数据点分为不同的簇。
具体而言，我们要对每个数据点x_i进行密度估计，将其周围的点加权后求和得到密度估计值f(x_i)。
给定一个初始质心x_c，我们通过以下公式计算新质心x_c’：x_c' = \frac{\sum_{x_i \in B(x_c,r)} w(x_i) \times x_i}{\sum_{x_i \in B(x_c,r)} w(x_i)}B(x_c,r)表示以x_c为圆心，半径为r的区域，w(x_i)为高斯权重系数，可以写作w(x_i) = e ^ {-\frac{(x_i - x_c)^2}{2 \times \sigma^2}}\sigma是高斯核函数的标准差，控制窗口大小和权重降低的速度。
在计算新质心后，我们将其移动到新位置，即x_c = x_c’，然后重复以上步骤，直到质心不再改变或者达到预定的迭代次数为止。
最终，所有距离相近的数据点被归为同一簇。
算法的时间复杂度为O(nr^2)，其中n为数据点数量，r为窗口半径。
可以通过调整r和\sigma来平衡速度和准确率。
二、公式1. 高斯核函数w(x_i) = e ^ {-\frac{(x_i - x_c)^2}{2 \times \sigma^2}}其中x_i和x_c是数据点和质心的位置向量，\sigma是高斯核函数的标准差。
该函数表示距离越大的数据点的权重越小，与质心距离越近的数据点的权重越大，因此可以有效估计密度。
2. 新质心计算公式x_c' = \frac{\sum_{x_i \in B(x_c,r)} w(x_i) \times x_i}{\sum_{x_i \in B(x_c,r)} w(x_i)}B(x_c,r)表示以x_c为圆心，半径为r的区域，w(x_i)为高斯权重系数。
基于Mean-Shift的自适应窗宽视频跟踪算法研究金广智石林锁白向峰牛武泽（第二炮兵工程学院五系，陕西西安，710025）摘要：针对视频跟踪中的传统Mean-Shift方法不能有效跟踪尺度有明显变化的目标这一问题，将图像信息量度量理论引入到了算法之中，提出了一种自适应窗宽的改进Mean-Shift 跟踪算法，实现了跟踪窗宽随着目标尺度的变化而自适应调整。
实验仿真结果表明改进算法能较好适应目标的尺度变化，跟踪效果良好。
关键词：目标跟踪 Mean-Shift算法自适应窗宽中图分类号：TP391 文献标识码：AStudy on Adaptive Bandwidth Mean-Shift Algorithm In VideoTrackingJIN Guangzhi,SHI Linsuo,BAI Xiangfeng,NIU Wuze(Department No.5, The Second Artillery Engineering College, Xi’an, Shaan Xi, 710025)A bstract: The traditional Mean-Shift algorithm in video tracking cannot be adapted to object of the changes in size. To solve the problem, we introduce the Image information measure theory, and propose an adaptive bandwidth Mean-Shift tracking algorithm, the improved algorithm achieves tracking windows’automatic adjustment to the change of the target size. The experimental results indicate that the bandwidth can better adapt to the size change of the target, and the tracking effect is good.Keywords: object tracking, Mean-Shift algorithm, adaptive bandwidth引言目标跟踪一直是计算机视觉研究领域的热点问题,在视频监控、物体识别、人机界面等领域有着广泛的应用。
第7卷第2期2014年4月中国光学Chinese OpticsVol．7No．2Apr．2014收稿日期：2013-12-21；修订日期：2014-02-23基金项目：中国科学院长春光学机密机械与物理研究所三期创新工程资助项目（No．065X32CN60）文章编号2095-1531（2014）02-0332-07Mean-shift 跟踪算法及其在光电跟踪系统中的应用王铭明1，2，陈涛1*，王建立1，阴玉梅1（1．中国科学院长春光学精密机械与物理研究所，吉林长春130033；2．中国科学院大学，北京100049）摘要：针对光电跟踪系统中实时提取运动目标脱靶量的应用需求，设计了一种基于灰度直方图的Mean-shift 图像跟踪算法，对算法中目标模型与候选模型的建立进行了改进，抑制了背景像素对目标跟踪产生的影响。
算法在系统上位机Vis-ual C ++6．0平台上实现，当光电跟踪系统捕获到运动目标后，利用Mean-shift 图像跟踪算法跟踪运动目标，并实时将运动目标脱靶量作为伺服控制系统的输入信号，驱动跟踪器跟踪目标。
实验结果表明：设计的算法可以实时、准确、有效地跟踪运动目标，使稳定后的脱靶量换算得到的角偏差量控制在30ᵡ之内。
关键词：光电跟踪系统;图像跟踪;运动目标;Mean-shift ;背景加权;脱靶量中图分类号：TP391．4文献标识码：Adoi ：10．3788/CO．20140702．0332Mean-shift tracking algorithm and its applicationin optoelectronic tracking systemWANG Ming-ming 1，2，CHEN Tao 1*，WANG Jian-li 1，YIN Yu-mei 1（1．Changchun Institute of Optics ，Fine Mechanics and Physics ，Chinese Academy of Sciences ，Changchun 130033，China ；2．University of Chinese Academy of Sciences ，Beijing 100049，China ）*Corresponding author ，E-mail ：chent @ciomp．ac．cnAbstract ：In order to fulfill the requirement to extract miss distance of moving target in real time in optoelec-tronic tracking system ，a Mean-shift image tracking algorithm based on gray histogram is designed．The target model and the candidate model of the algorithm are improved ，and the impact of background pixels on target tracking is suppressed．The algorithm is implemented in the Visual C ++6．0platform in the upper computer of the system．When the optoelectronic tracking system captures the moving target ，the system uses the Mean-shift image tracking algorithm to track the moving target．The miss distance is used as the input signal of the servo control system to drive the tracking device to track the target．Experiment results show that the proposed Mean-shift algorithm is able to track the moving target in real time precisely and effectively so that the angledeviation can be limited within30arc sec．Key words：optoelectronic tracking system；image tracking；moving object；Mean-shift；background weighted；miss distance1引言光电跟踪系统是典型的光、机、电、控制和信号处理一体化的集成装置，广泛应用于实时监控、导弹导引、激光通信、武器火控系统等领域［1-2］。
MeanShift算法相关应用作者：廖礼来源：《科教导刊·电子版》2019年第07期摘要 MeanShift算法是一种无参数概率密度估计的算法。
通过概率密度函数和有限次的迭代，能快速找到数据分布的模式。
具有原理简单、参数少，无需预处理等诸多优点，被广泛应用于图像平滑、边缘检测、目标跟踪等领域。
本文简要介绍了MeanShift算法的几种应用。
关键词 MeanShift 图像平滑边缘检测目标跟踪中图分类号：TP391.41 文献标识码：A0引言MeanShift （均值漂移）是一种非参数概率密度估计的方法，一种最优的寻找概率密度极大值的梯度上升法，在解决计算机视觉底层过程中表现出了良好的鲁棒性和较高的处理速度。
MeanShift最早于1975 年由Fukunaga等人在关于概率密度梯度函数的估计一文中提出。
MeanShift 算法一般指的是一个迭代的步骤，即先算出当前点的漂移均值，移动该点到其漂移均值，然后以此为新的起始点，继续移动，直到满足一定的条件结束。
随着时间的推移，MeanShift也由最基本的形式得到了完善和发展。
首先，Yizong Cheng定义了一族核函数，使得随着样本与被漂移点的不同，其漂移量对均值漂移向量的贡献也不同；其次又设定了一个权重系数，使得不同样本点的重要性不一样。
因此MeanShift 的适用范围得到了扩大。
接着Comaniciu 等人将MeanShift 算法运用到了特征空间的分析之中，对图像进行平滑和分割处理，并把非刚体的跟踪问题近似为一个MeanShift 最优化问题，使得跟踪可以实时地进行。
由于MeanShift 算法完全依靠特征空间中的样本点进行分析，不需要任何先验知识，收敛速度快，近年来在图像平滑、边缘检测以及目标跟踪等许多计算机视觉研究领域开始得到广泛的关注和应用。
1 MeanShift算法的相关应用1.1基于MeanShift的图像平滑一幅图像可以表示成一个二维网格点上p维向量，每一个网格点代表一个像素，p=1表示这是一个灰度图，p=3表示彩色图，p>3表示一个多谱图，网格点的坐标表示图像的空间信息。
§5-1Mean Shift 算法Mean Shift 算法是由Fukunaga 和Hosteler 于1975年提出的一种无监督聚类方法[109]，Mean Shift 的含义是均值偏移向量，它使每一个点“漂移”到密度函数的局部极大值点。
但是再提出之初，Mean Shift 算法并没有得到广泛的重视，直到1995年，Cheng 等人对该算法进行了进一步的研究[110]，提出了一般的表达形式并定义了一族核函数，从而扩展了该算法的应用领域，此后Mean Shift 算法逐步得到了人们的重视。
目前，Mean Shift 算法已广泛应用于目标跟踪[111~114]、图像分割与平滑[115~118]等领域，同时由于该算法具有简洁、能够处理目标变形等优点，也是目前目标跟踪领域的一个重要研究热点。
5-1-1 Mean Shift 算法原理Mean Shift 算法是一种基于密度梯度的无参数估计方法，从空间任意一点，沿核密度的梯度上升方向，以自适应的步长进行搜索，最终可以收敛于核密度估计函数的局部极大值处。
基本的Mean Shift 算法可以描述为：设{}()1,,i x i n = 为d 维空间R d 中含有n 个样本点的集合，在点x 处的均值偏移向量的基本形式可以由式(5.1)表示：1()()hh ix S M x xx k∈=-∑ (5.1)其中，S h 是R d 中满足式(5.2)的所有y 点集合，其形状为一个半径为h 的高维球区域。
k 为所有n 个样本点中属于高维球区域的点的数目。
(x i -x )为样本点相对于点x 的偏移向量。
根据式(5.1)的定义可知，点x 的均值偏移向量就是所有属于S h 区域中的样本点与点x 的偏移向量均值，而S h 区域中的样本点大多数是沿着概率密度梯度的方向，所以均值漂移向量的方向与概率密度梯度方向一致，图5.1为具体的示意图。
{}2():()()Th S x y y x y x h=--≤ (5.2)图5.1 Mean Shift 示意图 Fig.5.1 Mean Shift sketch map根据式(5.1)和图5.1可以看出，所有属于区域S h 中的样本点对于点x 的均值漂移向量贡献度相同，而与这些点与点x 间的距离无关。
mean shift算法讲解Mean shift算法是一种无监督的聚类算法，它的主要思想是通过不断迭代寻找数据点的概率分布密度的众数，从而实现数据的聚类。
本文将详细介绍Mean shift算法的具体步骤和实现流程，并深入解析其原理和应用场景。
一、算法背景和基本原理Mean shift算法最初由Comaniciu和Meer于1992年提出，它是一种基于密度估计的聚类方法。
其核心思想是通过计算每个数据点周围的概率密度分布，不断调整数据点的位置直到达到局部极大值点（众数），从而实现数据点的聚集。
Mean shift算法的基本原理如下：1.初始化：选择一个合适的核函数和带宽，然后从数据集中选择一个数据点作为初始中心点。
2.密度估计：计算每个数据点周围的概率密度分布，以核函数和带宽作为参数。
3.均值偏移：根据密度估计结果，通过计算梯度的方向，将当前中心点移动到密度分布的局部极大值点。
4.收敛判断：判断当前中心点和移动后的中心点之间的距离，如果小于某个阈值，则认为算法收敛，结束迭代。
否则，将移动后的中心点作为新的中心点，重复步骤2-4直到收敛。
二、算法步骤详解下面将详细解释Mean shift算法的每一步骤。
1.初始化为了实现Mean shift算法，我们首先需要选择一个适当的核函数和带宽。
核函数可以是高斯核函数或者其他类型的核函数。
带宽决定了数据点的搜索半径，即计算密度估计的范围。
一个较小的带宽会导致聚类过于散乱，而一个较大的带宽会导致聚类过于集中。
因此，合适的带宽选择是非常重要的。
2.密度估计在第二步中，我们需要计算每个数据点周围的概率密度分布。
这可以通过核函数和带宽来实现。
对于给定的数据点xi，其密度估计可以表示为：f(xi)=1/N*ΣK(xi-xj)/h其中，N是数据点的总数，K是核函数，h是带宽。
该公式意味着每个数据点的密度估计值是通过计算该数据点和所有其他数据点之间的核函数和的平均值得到的。
3.均值偏移在第三步中，我们通过计算梯度的方向来将当前中心点移动到密度分布的局部极大值点。
