目录基于聚类的图像分割算法 k-means 算法 mean-shift 算法基于图的图像分割算法

Size: px

Start display at page:

Download "目录基于聚类的图像分割算法 k-means 算法 mean-shift 算法基于图的图像分割算法"

尻温
5 years ago
Views:

1 图像处理与分析图像分割授课教师 : 孙剑 jiansun@mail.xjtu.edu.cn 西安交通大学数学与统计学院

2 目录基于聚类的图像分割算法 k-means 算法 mean-shift 算法基于图的图像分割算法

3 图像分割问题图像分割 : 将图像区域分割为颜色纹理或语义一致的区域底层分割 : 将图像分割为颜色或纹理一致的区域, 但每个分割区域内没有确定的语义信息 ; 中层分割 : 将图像分割为具有中层语义信息的图像块例如前景 / 背景分割 ; 语义分割 : 将图像逐点分割为不同语义信息的图像分割块

4 分割和聚类 l 图像分割任务 : 通过将图像或者视频分割为多个分割块, 获得图像或视频的一个更为精炼的表达 Ω = Ω Ω i i Ω j =, i j l 基于聚类的分割算法思想 : 将相似的图像特征进行聚类, 每一类即为图像的一个分割块图像特征 : 颜色纹理等如何判断特征的相似性? 如何建模图像聚类问题? i

5 分割和聚类 l 分割算法的基本思想自下而上的分割方法 : 基于特征的局部相似性进行像素点的聚类自上而下的分割方法 : 像素位于同一个物体之上, 则认为像素属于一类自下而上的分割方法自上而下的分割方法

6 分割和聚类 l 视觉聚类原理 :Gestalt 心理学原理, 即描述人是如何将感知到的事物聚合到一起

7 分割和聚类

8 基于 k-means 聚类的图像分割算法 l K-Means 聚类算法 : 是典型的基于特征相似性的聚类算法算法流程 : 初始化 K 个中心点 : 迭代进行如下步骤 : Step 1: 将每个点 {µ 1,,µ K } x i 赋给最近邻中心点 l(x) = argmin x j µ i 所在的类, 即 : ; Step 2: 将重新计算每个类别的中心点 µ c = 1 N x j, l(x j )=c i

10 基于 k-means 聚类的图像分割算法输入图像颜色 (LUV) 特征

11 基于 k-means 聚类的图像分割算法输入图像灰度值聚类结果颜色值聚类结果 K-means 聚类结果 From: Computer Vision - A Modern Approach. Slides by D.A. Forsyth

12 K-means using color alone, 11 segments.

13 基于 k-means 聚类的图像分割算法 l K-Means 聚类算法的优点简单快速收敛到目标函数的局部极小值点 l K-means 聚类算法的缺点需要选择合适的 K 对初始化敏感对数据点分布要求 : 对球形分布数据聚类结果好对误差敏感

14 基于 mean-sift 聚类的图像分割算法 Mean-sift 聚类基本思想 : 在特征空间中找到特征密度分布的局部极大值点 [ 参考文献 ]:

15 基于 mean-shift 聚类的图像分割算法特征空间的密度估计 ( 核密度估计算法 ): Mean-shift 算法的聚类目标 : 寻找密度的局部极值点 Mean-shift

16 基于 mean-shift 聚类的图像分割算法 Mean-Shift 迭代公式 : x = y i

25 基于 mean-shift 聚类的图像分割算法 Mean-Shift 算法流程 :

Mean-Shift 算法程序 : http://coewww.rutgers.

27 Mean-Shift 算法程序 : Edge Detection and Image Segmentation System

28 Mean-Shift 滤波 :

29 基于 mean-shift 聚类的图像分割算法 Mean-Shift 算法优点 : 可以聚类非球形分布的数据类仅依赖于一个参数 ( 窗口参数 ) 可找到多个局部极大值对异常点具有鲁棒性 Mean-Shift 算法缺点 : 输出的聚类结果依赖于窗口函数计算量很高对高维度数据的可扩展性不足

30 基于 mean-shift 聚类的图像分割算法 l 图 (Graph) G(V,E): 图 G 是由节点集合 V(G), 和边集合 E(G) 构成, 图上的边建模了节点之间的连接关系

31 基于图的图像分割算法 Image (I) Eigenvector X(W) Discretization Intensity Color Edges Texture Graph Affinities (W) 1 1 Ncut( A, B) = cut( A, B) + vol( A) vol( B) ( D W ) X = λdx X A 1 if i A ( i) = 0 if i A Slide from Timothee Cour (

32 基于图的图像分割算法 - 图的定义 G = {V,E} V: 图节点 E: 节点之间的连接边 V: 像素 E: 像素之间的相似形 Slides from Jianbo Shi

33 基于图的图像分割算法 - 图的定义 l 相似性矩阵 : [ ] W = w i, j w i = e, j X ( i ) σ X 2 X ( j ) 2 2 Slides from Jianbo Shi

34 基于图的图像分割算法 - 图的定义 l 相似性矩阵 : N pixels 选择的像素点 ( 星号点 ) 与其它像素点的相似性越亮意味着越相似 M pixels Reshape N*M pixels N*M pixels

35 基于图的图像分割算法 - 图的定义 l 图节点的度数 : d i w i, j j = Slides from Jianbo Shi

36 基于图的图像分割算法 - 图的定义 l 集合的体积 : vol ( A) = d, i A i A V Slides from Jianbo Shi

37 基于图的图像分割算法 - 图的定义 l 图上的切 (Cut): cut( A, A) = w i, j i A, j A Slides from Jianbo Shi

38 基于图的图像分割算法 - 图的定义分割矩阵 X: segments [ X ] X =,..., 1 X K pixels 逐点相似矩阵 (Affinity Matrix)W: W ( i, j) = aff ( i, j) 度数矩阵 (Degree Matrix)D: D ( i, i) = j w i, j 拉普拉斯矩阵 L: L = D W

39 亮度纹理距离 ) ( ) ( ), ( I j i I I e j i W σ = ) ( ) ( ), ( X j i X X e j i W σ = ) ( ) ( ), ( c j i c c e j i W σ = 基于图的图像分割算法 - 相似性度量

40 基于图的图像分割算法 - 最小切 l 分割准则 ( 最小切 ): mincut( A, B) = Problem! Weight of cut is directly proportional to the number of edges in the cut. min A, B u A, v B w( u, v) A B 这两种图切的代价低于理想的图切代价理想的图切 First proposed by Wu and Leahy

41 基于图的图像分割算法 - 正规切正规切或平衡切 (Normalized cut or balanced cut): Ncut( A, B) = cut( A, B) 1 vol( A) + 1 vol( B) Finds better cut 参考文献 : Jianbo Shi, Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997

42 基于图的图像分割算法 - 正规切 l 如何极小化 Ncut? 将图切目标函数转化为矩阵形式, 可以得到简化形式 : min x Subject to: Ncut( x) = min y T D1 = 0 y y T ( D T y W ) y Dy Rayleigh 熵 NP-Hard!

43 基于图的图像分割算法 - 正规切 l 将目标函数进行松弛化, 得到如下连续的推广特征值系统 : max ( y y T ( D W )y) subject to ( y T Dy = 1) 即求解 : ( D W ) y = λdy l 最小特征值为 0: ( D W )1 = 0, 相应的特征向量为 y 0 =1. l 第 2 个最小特征向量是问题的真正解

44 1. 定义两个图节点之间的相似性 : 2. 计算相似性矩阵 (W) 和度数矩阵 (D). 3. 求解 4. 利用第二小特征值对应的特征向量进行图分割. Dy y W D λ = ) ( ) ( ) ( ) ( ) (, X j i I j i X X F F j w i e σ σ + = 基于图的图像分割算法 - 正规切

45 基于图的图像分割算法 - 正规切 l 二值化分割 : 将图像分割为两个区域分割阈值的选择 : a) 选择为常数 (0, or 0.5). b) 选择为种值. c) 选择一个阈值可以极小化 Ncuts 目标函数

46 基于图的图像分割算法 - 正规切 l l 多值分割 : 将图像分割为多个图像块算法流程 : 使用多个特征向量作为特征, 采用 k-means 聚类获得初始分割, 然后进行如下处理 : a) 融合分割块以极小化 k-way 正规切目标函数. b) 使用 k 个分割块, 并用穷举搜索算法找到最优分割 ;

47 基于图的图像分割算法 - 正规切 Images from Matthew Brand (TR )

48 基于图的图像分割算法 - 正规切特征向量分割块

49 基于图的图像分割算法 - 正规切分割结果 * Slide from Khurram Hassan-Shafique CAP5415 Computer Vision 2003

50 Figure from Image and video segmentation: the normalised cut framework, by Shi and Malik, 1998

51 Figure from Normalized cuts and image segmentation, Shi and Malik, 2000

54 作业 l 复习 Mean-shift 和 Normalized Cut 算法思想参考文献 : Jianbo Shi, Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997 D. Comaniciu, et.al., Mean Shift: A Robust Approach Toward Feature Space Analysis IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002 尝试运行两种算法程序 : Edge Detection and Image Segmentation System

JOURNAL OF APPLIED SCIENCES Electronics and Information Engineering Vol. 28 No. 6 Nov DOI: /j.issn Nor

28 6 2010 11 JOURNAL OF APPLIED SCIENCES Electronics and Information Engineering Vol. 28 No. 6 Nov. 2010 DOI: 10.3969/j.issn.0255-8297.2010.06.008 Normalized Cut 200433 normalized cut (Ncut). Ncut.. 112.

目录 基于聚类的图像分割算法 k-means 算法 mean-shift 算法 基于图的图像分割算法

目录基于聚类的图像分割算法 k-means 算法 mean-shift 算法基于图的图像分割算法