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

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

Mean Shift Theory

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

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

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

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

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

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

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

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

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

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

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

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

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

Non-Rigid Object Tracking … …

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 …

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

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

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

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

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

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.

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)

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

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

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

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

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

完 谢谢