图像分割分水岭

1、K-Means、WatershedMean Shift分割,Feature Space,Source: K. Grauman,Feature Space,Source: K. Grauman,Image,Clusters on intensity,Clusters on color,K-means clustering using intensity alone and color alone,Segmentation as clustering,Clustering based on (r,g,b,x,y) values enforces more spatial coherence,K-M

2、eans pros and cons,Pros Simple and fast Easy to implement Cons Need to choose K Sensitive to outliers Usage Rarely used for pixel segmentation,Watershed algorithm,Watershed algorithm,分水岭算法,分割原理 分水岭算法 标记约束分水岭算法 等级分割,(1)任何的灰度级图像都可以被看做是一个地形图,分割原理,(2)假设我们在每个区域最小值位置地方打个洞,让水以均匀的速度上升,从低到高淹没整个地形.当处在不同的汇聚盆地中

3、的水将要聚合在一起时,修建大坝将阻止聚合,最后得到的水坝边界就是分水岭的分割线.,12,Watershed Segmentation Algorithm,13,Watershed Segmentation Algorithm,The objective is to find watershed lines. The idea is simple: Suppose that a hole is punched in each regional minimum and that the entire topography is flooded from below by letting water

4、 rise through the holes at a uniform rate. When rising water in distinct catchment basins is about the merge, a dam is built to prevent merging. These dam boundaries correspond to the watershed lines.,定义变量,分水岭算法,定义变量(续),分水岭算法,初始化:,递归:,定义变量,初始化: 递归:,递归(续),终止:n=max+1,分水岭分割方法应用在图像的梯度,那么集水处在理论上就对应灰度变化最小

5、的区域,而分水岭就对应灰度变化相对最大的区域.,从上到下,从右到左 原始图 梯度图 梯度图的分水岭 最终轮廓,缺点:由于噪声或者局部不规则而引起”过度分割”,电泳凝胶图像与经过分水岭转变的分割图,分水岭算法的改进,对图片进行预处理 分割时添加约束 分割后对图像进行再处理,标记约束分水岭算法,改进的分水岭算法,从先前已经定好的区域开始浸水,Bahadir K. Gunturk,EE 7730 - Image Analysis I,24,A solution is to limit the number of regional minima. Use markers to specify the

6、only allowed regional minima. (For example, gray-level values might be used as a marker.),Watershed Segmentation Algorithm,防止“过度分割”,电泳凝胶图像与经过标记约束分水岭转变的分割图,标记约束分水岭算法应用,钢的断裂面的提取,银色木纹的提取,等级分割,(1)通过分分水岭算法,得到一张初始的分割图片(对比如下),(2)以这些相对高度为基础,再次用分水岭算法,可达下一级的分割图如下,Bahadir K. Gunturk,EE 7730 - Image Analysis I,

7、30,Watershed algorithm might be used on the gradient image instead of the original image.,Watershed Segmentation Algorithm,Bahadir K. Gunturk,EE 7730 - Image Analysis I,31,Due to noise and other local irregularities of the gradient, oversegmentation might occur.,Watershed Segmentation Algorithm,Imag

8、e,Gradient,Watershed boundaries,Watershed Segmentation Algorithm,Simple trick,Use Gaussian or median filter to reduce number of regions,应用,应用,应用,Meyers watershed segmentation,Choose local minima as region seeds Add neighbors to priority queue, sorted by value Take top priority pixel from queue If al

9、l labeled neighbors have same label, assign to pixel Add all non-marked neighbors Repeat step 3 until finished,Meyer 1991,Matlab: seg = watershed(bnd_im),Watershed pros and cons,Pros Fast ( 1 sec for 512x512 image) Among best methods for hierarchical segmentation Cons Not easy to get variety of regi

10、ons for multiple segmentations No top-down information Usage Preferred algorithm for hierarchical segmentation,Mean shift segmentation,Versatile technique for clustering-based segmentation,D. Comaniciu and P. Meer, Mean Shift: A Robust Approach toward Feature Space Analysis, PAMI 2002.,Mean shift al

11、gorithm,Try to find modes of this non-parametric density,Mean-Shift 分割,Mean Shift Theory What is Mean Shift ? Density Estimation Methods Nonparametric Kernel Density Estimation Deriving the Mean Shift Mean shift properties Applications Clustering Discontinuity Preserving Smoothing Segmentation Objec

12、t Contour Detection Object Tracking,outline,Mean Shift Theory What is Mean Shift ? Density Estimation Methods Nonparametric Kernel Density Estimation Deriving the Mean Shift Mean shift properties Applications Clustering Discontinuity Preserving Smoothing Segmentation Object Contour Detection Object

13、Tracking,Intuitive Description,Region of interest,Center of mass,Mean Shift vector,目标：寻找最稠密的区域,Intuitive Description,Region of interest,Center of mass,Mean Shift vector,目标：寻找最稠密的区域,Intuitive Description,Region of interest,Center of mass,Mean Shift vector,目标：寻找最稠密的区域,Intuitive Description,Region of i

14、nterest,Center of mass,Mean Shift vector,目标：寻找最稠密的区域,Intuitive Description,Region of interest,Center of mass,Mean Shift vector,目标：寻找最稠密的区域,Intuitive Description,Region of interest,Center of mass,Mean Shift vector,目标：寻找最稠密的区域,Intuitive Description,Region of interest,Center of mass,目标：寻找最稠密的区域,outline

15、,Mean Shift Theory What is Mean Shift ? Density Estimation Methods Nonparametric Kernel Density Estimation Deriving the Mean Shift Mean shift properties Applications Clustering Discontinuity Preserving Smoothing Segmentation Object Contour Detection Object Tracking,What is Mean Shift ?,非参数密度估计 Non-p

16、arametric Density Estimation,非参数密度梯度估计 Non-parametric Density GRADIENT Estimation (Mean Shift),Discrete PDF Representation,PDF Analysis,特征空间的概率密度函数 颜色空间（color spapce） 尺度空间（Scale space） 事实上我们可以设想的任意特征空间 ,A tool for: 在样本集合中寻找模型，确定N维空间RN里面一个潜在的概率密度函数 (PDF- probability density function ),outline,Mean Sh

17、ift Theory What is Mean Shift ? Density Estimation Methods Nonparametric Kernel Density Estimation Deriving the Mean Shift Mean shift properties Applications Clustering Discontinuity Preserving Smoothing Segmentation Object Contour Detection Object Tracking,Non-Parametric Density Estimation,假设: 数据点是

18、从一个隐含的概率密度函数PDF进行采样,Assumed Underlying PDF,Real Data Samples,Data point density implies PDF value !,2020-07-10,53,Assumed Underlying PDF,Real Data Samples,Non-Parametric Density Estimation,2020-07-10,54,Assumed Underlying PDF,Real Data Samples,?,Non-Parametric Density Estimation,2020-07-10,55,Parame

19、tric Density Estimation,Assumption : The data points are sampled from an underlying PDF,Assumed Underlying PDF,Estimate,Real Data Samples,2020-07-10,56,outline,Mean Shift Theory What is Mean Shift ? Density Estimation Methods Nonparametric Kernel Density Estimation Deriving the Mean Shift Mean shift

20、 properties Applications Clustering Discontinuity Preserving Smoothing Segmentation Object Contour Detection Object Tracking,Kernel Density Estimation,Kernel Properties: Normalized Symmetric Exponential weight decay ?,A function of some finite number of data points x1xn,Parzen Windows - General Fram

21、ework,A function of some finite number of data points x1xn,In practice one uses the forms:,or,Same function on each dimension,Function of vector length only,Kernel Density Estimation,Parzen Windows - General Framework,A function of some finite number of data points x1xn,Examples: Epanechnikov Kernel

22、 Uniform Kernel Normal Kernel,Kernel Density Estimation,Various Kernels,2020-07-10,60,Kernel Density Estimation,Gradient,Give up estimating the PDF ! Estimate ONLY the gradient,Using the Kernel form:,We get :,Size of window,2020-07-10,61,outline,Mean Shift Theory What is Mean Shift ? Density Estimat

23、ion Methods Nonparametric Kernel Density Estimation Computing the Mean Shift Mean shift properties Applications Clustering Discontinuity Preserving Smoothing Segmentation Object Contour Detection Object Tracking,Kernel Density Estimation,Gradient,Computing The Mean Shift,Computing The Mean Shift,Yet

24、 another Kernel density estimation !,Simple Mean Shift procedure: Compute mean shift vector Translate the Kernel window by m(x),Real Modality Analysis,Attraction basin,Attraction basin: the region for which all trajectories lead to the same mode Cluster: all data points in the attraction basin of a

25、mode,outline,Mean Shift Theory What is Mean Shift ? Density Estimation Methods Nonparametric Kernel Density Estimation Computing the Mean Shift Mean shift properties Applications Clustering Discontinuity Preserving Smoothing Segmentation Object Contour Detection Object Tracking,Adaptive Gradient Asc

26、ent,Mean Shift Properties,Automatic convergence speed the mean shift vector size depends on the gradient itself. Near maxima, the steps are small and refined Convergence is guaranteed for infinitesimal steps only infinitely convergent, (therefore set a lower bound) For Uniform Kernel ( ), convergenc

27、e is achieved in a finite number of steps Normal Kernel ( ) exhibits a smooth trajectory, but is slower than Uniform Kernel ( ).,Mean Shift Strengths & Weaknesses,Strengths : Application independent tool Suitable for real data analysis Does not assume any prior shape (e.g. elliptical) on data cluste

28、rs Can handle arbitrary feature spaces Only ONE parameter to choose h (window size) has a physical meaning, unlike K-Means,Weaknesses : The window size (bandwidth selection) is not trivial Inappropriate window size can cause modes to be merged, or generate additional “shallow” modes Use adaptive win

29、dow size,Mean Shift 的收敛性？,outline,Mean Shift Theory What is Mean Shift ? Density Estimation Methods Nonparametric Kernel Density Estimation Computing the Mean Shift Mean shift properties Applications Clustering Discontinuity Preserving Smoothing Segmentation Object Contour Detection Object Tracking,

30、Clustering,Simple Modal Structures,Complex Modal Structures,Synthetic Examples,Clustering,Modes found,Modes after pruning,Final clusters,Feature space: L*u*v representation,Real Example,Initial window centers,L*u*v space representation,Clustering,Real Example,Not all trajectories in the attraction b

31、asin reach the same mode,2D (L*u) space representation,Final clusters,Clustering,Real Example,outline,Mean Shift Theory What is Mean Shift ? Density Estimation Methods Nonparametric Kernel Density Estimation Computing the Mean Shift Mean shift properties Applications Clustering Discontinuity Preserving Smoothing Segmentation Object Contour Detection Object Tracking,Discontinuity Preserving Smoothing,Feature space : Joint domain = spatial coordinates + color space,Meaning : treat the image as data points in