Introduction To Mean Shift

Presentation on theme: "Introduction To Mean Shift"— Presentation transcript:

1 Introduction To Mean Shift
Ma Long

2 Diagram – Contents 1 Basic Mean Shift 2 The Extension of Mean Shift
Sufficient Condition of Convergence 3 4 Step of the Algorithm 5 Example of Usage

3 1. Basic Mean Shift Assume that the basic formulation of Mean Shift :

4 1. Basic Mean Shift

5 2. The Extension of Mean Shift
: unit kernel function : weight at xi H: a symmetric positive definite d*d bandwidth matrix 公式1

6 2. The Extension of Mean Shift
, let 公式2

7 核函数方法 估计的目的：从样本集K= {x1, x2,…, xN}估计样本空间中任何一点的概率密度p(x)
非参数 估计 核函数方法 估计的目的：从样本集K= {x1, x2,…, xN}估计样本空间中任何一点的概率密度p(x) 基本方法：用某种核函数表示某一样本对待估计的密度函数的贡献，所有样本所作贡献的线性组合视作对某点概率密度p(x)的估计

8 非参数 估计 核函数方法图解 一个样本对自己所在位置的分布贡献最大，离得越远贡献越小

9 2. The Extension of Mean Shift
Given n data points xi in the d-dimensional space and its PDF f(x), the multivariate kernel density estimator computed in the point x is given by: 公式3

10 2. The Extension of Mean Shift
According to the definition of kernel function, there exist a profile function that satisfy: Let , it’s corresponding kernel function: The gradient of the function f(x) can be estimated as(对公式3求导)

11 2. The Extension of Mean Shift
The first term is proportional to the density estimate at x computed with the kernel G, let to represent it ; The second term is the mean shift -- the difference between the weighted mean, using the kernel G for weight, and x, the center of the kernel, let to represent it.

12 2. The Extension of Mean Shift
At location x, the mean shift vector computed with kernel G is proportional to the normalized density gradient estimate obtained with kernel K. The mean shift vector thus always points toward the direction of maximum increase in the density.

13 3.Sufficient Condition of Convergence
Denote by {yj}(j=1,2,3,4)the sequence of successive locations of the kernel G: The corresponding sequence of density estimates computed with kernel K, is given by

14 3.Sufficient Condition of Convergence
If the kernel K has a convex and monotonically decreasing profile, the sequence {yj} and converge, and is monotonically increasing

15 4. Step of the Algorithm First step, given an initial point x(i):
Second step: x(i+1)= Third step: x(i+1)-x(i)>d

16 Thank You !