图像分割:Mean shift&Ncuts

本章介绍图像分割中的Mean Shift 算法和Ncuts,通过示例说明了Mean Shift是根据一组数据样本,找到能够反映数据在高维特征空间分布的概率密度函数(PDF)的模型集合,并介绍了非参数化的概率密度估计、参数化的概率密度估计、核函数密度估计(Kernel Density Estimation)几种方法,还介绍了其在据类和图像分割中的应用;举例说明Ncuts:Normalized Cuts,基于图的图像分割及其数学模型的建立和求解。
展开查看详情

1.Mean Shift Segmentation Algorithm

2. 主要内容 • Mean Shift 理论 • What is Mean Shift ? • Density Estimation Methods • Deriving the Mean Shift • Mean shift properties • Mean Shift 的应用 • Clustering • Segmentation

3.Mean Shift 理论

4. 基本原理 Region of interest Center of mass Mean Shift vector Objective : Find the densest region Distribution of identical billiard balls

5. 基本原理 Region of interest Center of mass Mean Shift vector Objective : Find the densest region Distribution of identical billiard balls

6. 基本原理 Region of interest Center of mass Mean Shift vector Objective : Find the densest region Distribution of identical billiard balls

7. 基本原理 Region of interest Center of mass Mean Shift vector Objective : Find the densest region Distribution of identical billiard balls

8. 基本原理 Region of interest Center of mass Mean Shift vector Objective : Find the densest region Distribution of identical billiard balls

9. 基本原理 Region of interest Center of mass Mean Shift vector Objective : Find the densest region Distribution of identical billiard balls

10. 基本原理 Region of interest Center of mass Objective : Find the densest region Distribution of identical billiard balls

11. 什么是 Mean Shift ? 计算工具 : 根据一组数据样本 , 找到能够反映数据在高维特征空间分布的概率 密度函数 (PDF)PDF) 的模型集合 特征空间的 PDF • 颜色空间 Non-parametric • 尺度空间 Density Estimation • 任何可构建的特征空间 •… Discrete PDF Representation Data Non-parametric Density GRADIENT Estimation (Mean Shift) PDF Analysis

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

13. 非参数化的概率密度估计 假设隐含的 PDF 真实数据点集

14. 非参数化的概率密度估计 ? 假设隐含的 PDF 真实数据点集

15. 参数化的概率密度估计 假设 : 采样得到的数据点集服从一个隐含的概率密度函数 (PDF)PDF) ( x-μi )2  PDF(x) =  c e i i 2 i 2 Estimate 假设隐含的 PDF 真实数据点集

16.核函数密度估计 (PDF)Kernel Density Estimation) Parzen Windows – 整体框架 1 n P ( x)   K ( x - x i ) 用于描述有限数量数据点集 n i 1 x1…xn 的函数 核函数性质 : Data •归一化的 K (x)dx 1 Rd • 对称的 xK (x)dx 0 Rd •指数衰减 d lim x K (x) 0 • ??? x   K (x)dx cI T xx Rd

17.

18.Example: Given a set of five data points x1 = 2, x2 = 2.5, x3 = 3, x4 = 1 and x5 = 6, find Parzen probability density function (pdf) estimates at x = 3, using the Gaussian function with σ = 1 as window function.

19.

20.核函数密度估计 (PDF)Kernel Density Estimation) Parzen Windows – 函数形式 1 n P ( x)   K ( x - x i ) 用于描述有限数量数据点集 n i 1 x1…xn 的函数 Data 在实际应用时经常使用的函数形式为 : d K (x) c k ( xi ) or K (x) ck  x  i 1 在各个数据纬度上使用相同的核函数 建立关于向量长度的核函数

21. 核函数密度估计 (PDF)Kernel Density Estimation) 各种类型的核函数 1 n P ( x)   K ( x - x i ) 用于描述有限数量数据点集 n i 1 x1…xn 的函数 核函数举例 : Data • Epanechnikov Kernel K E (x)    c 1  x 2  x 1  0 otherwise  c x 1 • Uniform Kernel KU (x)   0 otherwise  1 2 • Normal Kernel K N (x) c exp   x   2 

22.核函数密度估计 (PDF)Kernel Density Estimation) 梯度 Gradient 1 n 不估计 PDF ! P( x)   K ( x - xi ) n i 1 只估计概率密度的梯度 假设使用的核函数  x - xi 2  形式为 : K (x - xi ) ck    h   可以得到 : Size of window  n    x g i i  c n c n P ( x)   ki    g i    n i 1  x n i 1 n  i 1      i 1 gi  g(x)  k (x)

23.Computing Kernel Density The Estimation Mean Shift Gradient  n    x g i i  c n c n P ( x)   ki    g i    n i 1  x n i 1 n  i 1      i 1 gi  g(x)  k (x)

24. Computing The Mean Shift  n    x g i i  c n c n P ( x)   ki    g i    n i 1  x n i 1 n  i 1      i 1 gi  对核函数密度的梯度进行估计 ! Mean Shift 简易流程 : • 计算 mean shift 向量  n  x - xi 2     xi g     i 1  h   m ( x )    x  n  x - xi  2    g  h    i 1    •根据 m(PDF)x) 移动核函数窗口 g(x)  k (x)

25. Mean Shift 方向检测 当遇到鞍点该如何处理 ? 在鞍点周围四处移动 , 检测是否 有梯度增加的方向 . Mean Shift 更新程序 : • 找到所有的 mean shift 的方向 • 四处移动,找到鞍点和高地 • 取梯度改变最大的方向

26. Mean Shift 特性 • 自动收敛的速度– mean shift 向量的大小取决于 Adaptive 梯度本身 Gradient Ascent • 在最大值附近,步长很小而且非定值 • 理论上需要无限步数 , 因此需要设定一个下界。 • 对于 Uniform Kernel (PDF) ), 可以在有限步数内收 敛 • Normal Kernel (PDF) ) 可以得到平滑轨迹 , 但是收 敛速度慢于 Uniform Kernel (PDF) ).

27. 真实模态分析 将整个数据空间窗口化 并行运行程序

28.真实模态分析 蓝色的数据点是被窗口移动时经过的

29.真实模态分析 An example 窗口是向着梯度变化最剧烈的方向移动的