计算机视觉10 5.2 mean_shift & Ncuts

计算机视觉,机器视觉,中国科学技术大学

Mean Shift Segmentation Algorithm

计算机视觉,机器视觉,中国科学技术大学

主要内容 Mean Shift 理论 What is Mean Shift ?

Density Estimation Methods Deriving the Mean Shift Mean shift properties

Mean Shift 的应用 Clustering Segmentation

计算机视觉,机器视觉,中国科学技术大学

Mean Shift 理论

计算机视觉,机器视觉,中国科学技术大学

基本原理Region of interest Center of mass

Mean Shift vector

Objective : Find the densest region Distribution of identical billiard balls

计算机视觉,机器视觉,中国科学技术大学

基本原理Region of interest Center of mass

Mean Shift vector

Objective : Find the densest region Distribution of identical billiard balls

计算机视觉,机器视觉,中国科学技术大学

基本原理Region of interest Center of mass

Mean Shift vector

Objective : Find the densest region Distribution of identical billiard balls

计算机视觉,机器视觉,中国科学技术大学

基本原理Region of interest Center of mass

Mean Shift vector

Objective : Find the densest region Distribution of identical billiard balls

计算机视觉,机器视觉,中国科学技术大学

基本原理Region of interest Center of mass

Mean Shift vector

Objective : Find the densest region Distribution of identical billiard balls

计算机视觉,机器视觉,中国科学技术大学

基本原理Region of interest Center of mass

Mean Shift vector

Objective : Find the densest region Distribution of identical billiard balls

计算机视觉,机器视觉,中国科学技术大学

基本原理Region of interest Center of mass

Objective : Find the densest region Distribution of identical billiard balls

计算机视觉,机器视觉,中国科学技术大学

什么是Mean Shift ?计算工具: 根据一组数据样本,找到能够反映数据在高维特征空间分布的概率密 度函数(PDF)的模型集合

特征空间的PDF 颜色空间 Non-parametric 尺度空间 Density Estimation 任何可构建的特征空间 …Data Non-parametric Density GRADIENT Estimation (Mean Shift)

Discrete PDF Representation

PDF Analysis

计算机视觉,机器视觉,中国科学技术大学

非参数化的概率密度估计假设: 采样得到的数据点集服从一个隐含的概率密度函数(PDF)由数据点集的密度 可以计算得到PDF的值

假设隐含的 PDF

真实数据点集

计算机视觉,机器视觉,中国科学技术大学

非参数化的概率密度估计

假设隐含的 PDF

真实数据点集

计算机视觉,机器视觉,中国科学技术大学

非参数化的概率密度估计 ?

假设隐含的 PDF

真实数据点集

计算机视觉,机器视觉,中国科学技术大学

参数化的概率密度估计假设: 采样得到的数据点集服从一个隐含的概率密度函数(PDF)( x-μi )2 2 i 2

PDF(x) =

c ei i

Estimate

假设隐含的 PDF

真实数据点集

计算机视觉,机器视觉,中国科学技术大学

核函数密度估计(Kernel Density Estimation)Parzen Windows – 函数形式1 n P ( x) K ( x - x i ) n i 1

用于描述有限数量数据点集 x1…xn的函数

Data在实际应用时经常使用的函数形式为:

K (x) c k ( xi )i 1

d

or

K (x) ck x

在各个数据纬度上使用相同的核函数

建立关于向量长度的核函数

计算机视觉,机器视觉,中国科学技术大学

核函数密度估计(Kernel Density Estimation)各种类型的核函数

1 n P ( x) K ( x - x i ) n i 1

用于描述有限数量数据点集 x1…xn的函数

核函数举例:

c 1 x Epanechnikov Kernel K E (x) 0 Uniform Kernel

2

Data

x 1 otherwise

c x 1 KU (x) 0 otherwise 1 2 K N (x)

c exp x 2

Normal Kernel

计算机视觉,机器视觉,中国科学技术大学

核函数密度估计(Kernel Density Estimation)

梯度1 n P ( x) K ( x - x i ) n i 1

Gradient不估计 PDF ! 只估计概率密度的梯度

假设使用的核函数 形式为: 可以得到:

x - xi K (x - xi ) ck h

2

Size of window

n xi g i c n c n i 1 P(x) ki gi n x n i 1 n i 1 gi i 1 g(x) k (x)

计算机视觉,机器视觉,中国科学技术大学

Computing The Estimation Kernel Density Mean ShiftGradient

n xi g i c n c n i 1 P(x) ki gi n x n i 1 n i 1 gi i 1 g(x) k (x)

计算机视觉,机器视觉,中国科学技术大学

Computing The Mean Shift n xi g i c n c n i 1 P(x) ki gi n x n i 1 n i 1 gi i 1 对核函数密度的梯度进行估计 ! Mean Shift 简易流程: 计算mean shift 向量 n x - xi 2 xi g h i 1 x m ( x) n x - xi 2 g h i 1

根据m(x)移动核函数窗口

g(x) k (x)

计算机视觉,机器视觉,中国科学技术大学

Mean Shift 方向检测当遇到鞍点该如何处理?

在鞍点周围四处移动,检测是否 有梯度增加的方向.

Mean Shift 更新程序: 找到所有的mean shift的方向 四处移动，找到鞍点和高地 取梯度改变最大的方向