Mean Shift 算法原理和在目标跟踪上的应用

Presentation on theme: "Mean Shift 算法原理和在目标跟踪上的应用"— Presentation transcript:

1 Mean Shift 算法原理和在目标跟踪上的应用

2 Agenda Mean Shift Theory What is Mean Shift ?
Density Estimation Methods Deriving the Mean Shift Mean shift properties Applications Clustering Discontinuity Preserving Smoothing Object Contour Detection Segmentation Object Tracking

3 Mean Shift Theory

4 Intuitive Description
Region of interest Center of mass Mean Shift vector Objective : Find the densest region Distribution of identical billiard balls

5 Intuitive Description
Region of interest Center of mass Mean Shift vector Objective : Find the densest region Distribution of identical billiard balls

6 Intuitive Description
Region of interest Center of mass Mean Shift vector Objective : Find the densest region Distribution of identical billiard balls

7 Intuitive Description
Region of interest Center of mass Mean Shift vector Objective : Find the densest region Distribution of identical billiard balls

8 Intuitive Description
Region of interest Center of mass Mean Shift vector Objective : Find the densest region Distribution of identical billiard balls

9 Intuitive Description
Region of interest Center of mass Mean Shift vector Objective : Find the densest region Distribution of identical billiard balls

10 Intuitive Description
Region of interest Center of mass Objective : Find the densest region Distribution of identical billiard balls

11 研究现状 Mean shift算法是Fukunaga于1975年提出的，其含义即偏移的均值向量。随着Mean shift理论的发展，它的含义也发生了变化。现在一般是指一个迭代的步骤，即先算出当前点的偏移均值，移动该点到其偏移均值,然后以此为新的起始点，继续移动，直到满足一定的条件结束。Cheng Yizong定义了一族核函数 ，将Mean shift算法引入到计算机视觉领域。Bradski G R对Mean shift算法进行改进，发展建立了Camshift算法，将Mean shift方法扩展应用到了目标跟踪中来。

12 Mean shift的基本形式 给定d维空间 中的n个样本点,i=1,…,n,在点 的Mean Shift向量的基本形式定义为:
其中， 是一个半径为h的高维球区域， k表示在这n个样本点中，有k个点落入区域 中.

13 Mean shift的扩展 核函数： 代表一个d维的欧氏空间， 是该空间中的一个点，用一列向量表示。 的模 。 表示实数域。如果一个函数 存在一个剖面函数 ，即 剖面函数的性质： （1） 是非负的 ； （2） 是非增的； （3） 是分段连续的,并且

14 Kernel Density Estimation Various Kernels
在选定的空间中，x1…xn 是有限的样本点。 例: Epanechnikov Kernel Uniform Kernel （均匀核函数） Normal Kernel （高斯核函数）

15 核密度 估计 梯度 使用核函数 的形式: 得到 : 窗宽带宽

16 Computing The Mean Shift
Yet another Kernel density estimation ! Simple Mean Shift procedure: Compute mean shift vector Translate the Kernel window by m(x)

17 Non-Rigid Object Tracking
… …

18 Mean-Shift Object Tracking General Framework: Target Representation
Choose a reference model in the current frame Choose a feature space Represent the model in the chosen feature space Current frame …

19 Mean-Shift Object Tracking General Framework: Target Localization
Start from the position of the model in the current frame Search in the model’s neighborhood in next frame Find best candidate by maximizing a similarity func. Repeat the same process in the next pair of frames Current frame … Model Candidate

20 Mean-Shift Object Tracking Target Representation
Choose a reference target model Represent the model by its PDF in the feature space Quantized Color Space Choose a feature space Kernel Based Object Tracking, by Comaniniu, Ramesh, Meer

21 Mean-Shift Object Tracking PDF Representation
Target Model (centered at 0) Target Candidate (centered at y) Similarity Function:

22 Mean-Shift Object Tracking Finding the PDF of the target model
model y candidate Target pixel locations A differentiable, isotropic, convex, monotonically decreasing kernel Peripheral pixels are affected by occlusion and background interference The color bin index (1..m) of pixel x Probability of feature u in model Probability of feature u in candidate Normalization factor Pixel weight Normalization factor Pixel weight

23 Mean-Shift Object Tracking Similarity Function
Target model: Target candidate: Similarity function: 1 The Bhattacharyya Coefficient

24 Mean-Shift Object Tracking Target Localization Algorithm
Start from the position of the model in the current frame Search in the model’s neighborhood in next frame Find best candidate by maximizing a similarity func.

25 Mean-Shift Object Tracking Approximating the Similarity Function
Model location: Candidate location: Linear approx. (around y0) Independent of y Density estimate! (as a function of y)

26 Mean-Shift Object Tracking Maximizing the Similarity Function
The mode of = sought maximum Important Assumption: One mode in the searched neighborhood The target representation provides sufficient discrimination

27 Mean-Shift Object Tracking Applying Mean-Shift
The mode of = sought maximum Original Mean-Shift: Find mode of using Extended Mean-Shift: Find mode of using

28 Mean-Shift Object Tracking About Kernels and Profiles
A special class of radially symmetric kernels: The profile of kernel K Extended Mean-Shift: Find mode of using

29 Mean-Shift Object Tracking Choosing the Kernel
A special class of radially symmetric kernels: Epanechnikov kernel: Uniform kernel(单位均匀核函数): Extended Mean-Shift:

30 Mean-Shift Object Tracking Adaptive Scale
Problem: The scale of the target changes in time The scale (h) of the kernel must be adapted Solution: Run localization 3 times with different h Choose h that achieves maximum similarity

31 完 谢谢