Mean Shift Segmentation Algorithm

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

Mean Shift 理论

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

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

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

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

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

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

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

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

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

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

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

假设: 采样得到的数据点集服从一个隐含的概率密度函数(PDF) 参数化的概率密度估计 假设: 采样得到的数据点集服从一个隐含的概率密度函数(PDF) Estimate 假设隐含的 PDF 真实数据点集

核函数密度估计(Kernel Density Estimation) Parzen Windows – 整体框架 用于描述有限数量数据点集 x1…xn的函数 Data 核函数性质: 归一化的 对称的 指数衰减 ???

Example: Given a set of five data points x1 = 2, x2 = 2 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.

核函数密度估计(Kernel Density Estimation) Parzen Windows – 函数形式 用于描述有限数量数据点集 x1…xn的函数 Data 在实际应用时经常使用的函数形式为: or 在各个数据纬度上使用相同的核函数 建立关于向量长度的核函数

核函数密度估计(Kernel Density Estimation) 各种类型的核函数 用于描述有限数量数据点集 x1…xn的函数 Data 核函数举例: Epanechnikov Kernel Uniform Kernel Normal Kernel

核函数密度估计(Kernel Density Estimation) 梯度 Gradient 不估计 PDF ! 只估计概率密度的梯度 假设使用的核函数 形式为: 可以得到: Size of window

Kernel Density Estimation Computing The Mean Shift Gradient

Computing The Mean Shift 对核函数密度的梯度进行估计 ! Mean Shift 简易流程: 计算mean shift 向量 根据m(x)移动核函数窗口

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

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

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

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

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

Mean Shift 应用

聚类 Cluster : All data points in the attraction basin of a mode Attraction basin : the region for which all trajectories lead to the same mode Mean Shift : A robust Approach Toward Feature Space Analysis, by Comaniciu, Meer

聚类 实例 特征空间: L*u*v r颜色空间 输入初始窗口 Modes found Modes after pruning Final clusters

聚类 实例 L*u*v space representation

聚类 实例 2D (L*u) space representation Final clusters Not all trajectories in the attraction basin reach the same mode

Segmentation Example …when feature space is only gray levels…

Segmentation Example

Segmentation Example

Segmentation Example

Segmentation Example

Segmentation Example

Segmentation Example

PAMI, 2000

基于图的图像分割

基于图的图像分割 首先: 选择感兴趣的区域

基于图的图像分割 怎样自动选取目标? ?

基于图的图像分割 两个要素:图(graph)和割(cut) ?

基于图的图像分割 什么是图(graph)? 节点-Nodes 通常是像素组合 有时候是样本 边-Edges 连接权重(W(i,j)) 例如颜色差异

基于图的图像分割 什么是割(cuts)? 每个 “cut” -> 一些点, W(I,j) 最优化问题 W(i,j) = |LUV(i) – LUV(j)|

基于图的图像分割 回到已选择的区域 每个 “cut” -> 一些点, W(I,j) 最优化问题 W(i,j) = |LUV(i) – LUV(j)|

基于图的图像分割 回到已选择的区域 每个 “cut” -> 一些点, W(I,j) 最优化问题 W(i,j) = |LUV(i) – LUV(j)|

基于图的图像分割 希望得到权重和的最大 每个 “cut” -> 一些点, W(I,j) 最优化问题 W(i,j) = |LUV(i) – LUV(j)|

基于图的图像分割 希望得到权重和的最大 每个 “cut” -> 一些点, W(I,j) 最优化问题 W(i,j) = |LUV(i) – LUV(j)| 这些Cuts 作用在权重大的位置

基于图的图像分割 希望得到权重和的最大 每个 “cut” -> 一些点, W(I,j) 最优化问题 W(i,j) = |LUV(i) – LUV(j)| 这些Cuts 作用在权重小的位置

Normalized Cuts-Ncuts 为什么要归一化? – 避免噪声的影响!

基于图的图像分割 最优化求解 递归求解: 区域增长 If W(i,j) low Stop Continue

基于图的图像分割 只能得到孤立的解

Solve for minimum penalty 算法流程 输入:图像 输出:分割块 每次迭代分割成两块 Yes Subdivide? No Assign W(i,j) Solve for minimum penalty Cut into 2 Subdivide? No Yes

权重函数W(i,j) 颜色可能会包含比较多的噪声! 可以使用亮度和位置 亮度特征项 位置项

目标函数的最小化 与割连接的所有边的权重和 与子集A连接的所有边的权重和

通过对目标函数的最小化进行求解 Partition A Partition B cut

通过对目标函数的最小化进行求解 求解归一化的拉普拉斯特征方程 W(N x N) : weights associated with edges D (N x N) : diagonal matrix with summation of all edge weights for the i-th pixel N : number of pixels in the image (N) : eigenvalues (N x N) : eigenvectors are real-valued partition indicator O(N^3) complexity in general O(N^(3/2)) complexity in practice a) Sparse local weights, b) Only need first few eigenvectors, c) Low precision

Laplacian Matrix Definition Laplacian matrix is the difference of the degree matrix and the adjacency matrix of the graph. Definition degree matrix is a diagonal matrix which contains information about the degree of each vertex. adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice

Laplacian Matrix Definition Laplacian matrix is the difference of the degree matrix and the adjacency matrix of the graph. Definition degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice Laplacian matrix is a matrix representation of a graph spectral graph theory

Gaussian Laplacian Matrix Compare with the traditional weighted function:

Matting Laplacian Matrix Compare with the traditional weighted function: Using Mahalanobis Distance instead of the Euclidean Distance

Comparing eigenvectors Input image Matting Eigenvectors Global- Eigenvectors

细分? 可以根据第二大的特征向量对图像进一步的分割 < Threshold ? Yes – stop here No – continue to subdivide

下一步研究: 视频分割-Video Segmentation Incorporating video information into low-level segmentation Graph-Based Video Segmentation: Matthias Grundmann, et al

下一步工作: 语义分割-Semantic Segmentation Incorporating top-down information into low-level segmentation Interactive Graph Cuts: Yuri Boykov, et al