《现代图像分析知识点 (44).pdf》由会员分享，可在线阅读，更多相关《现代图像分析知识点 (44).pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Modern Image Analysis谱聚类分割法谱聚类是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类。18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？7.6 基于聚类分割法7.6 基于聚类分割法 哥尼斯堡“七桥问题”Modern Image Analysis公元1736年，29岁的欧拉向圣彼得堡科学院递交了一份题为哥尼斯堡的七座桥的论文。论文的开头这样写到：欧拉运用娴熟的变换技巧，把哥尼斯堡七桥问题变为读者所熟悉的，简单的几何图形的“一笔画”
2、问题。“讨论长短大小的几何学分支，一直被人们热心地研究着。但是还有一个至今几乎完全没有探索过的分支。莱布尼兹最先提起过它，称之：“位置的几何学”。这个几何学分支讨论只与位置有关的关系，研究位置的性质；它不去考虑长短大小，也不牵涉到量的计算。但是至今未有过令人满意的定义，来刻划这门位置几何学的课题和方法”7.6 基于聚类分割法7.6 基于聚类分割法Modern Image Analysis欧拉是如何解决七桥问题的？又是如何证明要想一次走过七座桥是不可能的呢？欧拉的方法十分巧妙：（1）不考虑4个地区的大小、形状，看成是链接桥梁的4个点；（2）不考虑桥梁的曲直、长短，看成连接4个点的7条线。于是一座
3、仪态万千的哥尼斯堡古城在欧拉笔下就变成了一个结构简单是几何图形。7.6 基于聚类分割法7.6 基于聚类分割法ABCD1234567Modern Image Analysis1857年，英国数学家哈密顿发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个顶点分别表示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次切仅一次再回到原出发点的路，这就是“环球旅行”问题。运筹学中的“中国邮差问题”：一个邮递员从邮局出发要走遍他所负责的每一条街道去送信，蚊蝇如何选怎适当的路线可使所走的总路程最短。这个问题就与欧拉回路有密切的关系。而著名的“货郎担问题”则是一个带权的哈密
4、尔顿回路。开辟了新学科 图论7.6 基于聚类分割法7.6 基于聚类分割法Modern Image Analysis由若干点及连接两点的线所构成的图形，通常用来描述某些事物之间的某种关系，用点代表事物，线表示对应两个事物间具有这种关系。图的定义1 12 23 35 54 46 60.10.80.80.70.20.60.80.8G=(V,E)表示无向图，V 中元素叫做顶点，E 中的元素叫做边。wij表示 vi与 vj之间的关系，称作权重，对于无向图wij=wji。7.6 基于聚类分割法7.6 基于聚类分割法Modern Image Analysis 图的划分图划分是指将图完全划分为若干个子图像，各
5、子图无交集。12kGGGGijGG 划分的要求：同子图内的点相似度高不同子图的点相似度低1 12 23 35 54 46 60.10.80.80.70.20.60.80.8G1G27.6 基于聚类分割法7.6 基于聚类分割法Modern Image Analysis划分时，子图之间被截断边的权重和1212,(,)iji Gj GCut G Gw 定义拉普拉斯矩阵：LDW其中W 是权重矩阵，D为度矩阵，是对角矩阵1niiijjDw 图的划分转换为求 Cut 的最小值问题。7.6 基于聚类分割法7.6 基于聚类分割法Modern Image Analysis1 12 23 35 54 46 60.
6、10.80.80.70.20.60.80.812345610.00.80.60.00.10.020.80.00.80.00.00.030.60.80.00.20.00.040.00.00.20.00.80.750.10.00.00.80.00.860.00.00.00.70.80.0权重矩阵W12345611.50.00.00.00.00.020.01.60.00.00.00.030.00.01.60.00.00.040.00.00.01.70.00.050.00.00.00.01.70.060.00.00.00.00.01.5度矩阵D7.6 基于聚类分割法7.6 基于聚类分割法Modern
7、Image Analysis Minimum Cut方法1212,min(,)min()iji Gj GCut G Gw 1 17 73 35 54 46 60.20.80.80.70.20.60.80.72 20.3Minimum Cut 划分不均衡7.6 基于聚类分割法7.6 基于聚类分割法Modern Image Analysis Ratio Cut方法12121211(,)(,)Rcut G GCut G Gnnn1和 n2是划分到子图1和子图2的顶点个数 Normalized Cut方法12121211(,)(,)Ncut G GCut G Gddd1和 d2是子图1和子图2的权重和
8、7.6 基于聚类分割法7.6 基于聚类分割法Modern Image Analysis 谱聚类算法步骤：输入：样本及类别数k根据样本建立权重矩阵W计算拉普拉斯矩阵L，对于Ncut算法，计算计算L（）的特征值以及特征向量取出前 k个小特征值对应的特征向量，并对矩阵Vk的行向量进行聚类，得到k个类。1122LDLD L 12,eeeenVvvv 12,keeekVvvv 谱聚类可以看成是特征空间中的聚类问题7.6 基于聚类分割法7.6 基于聚类分割法Modern Image Analysis7.6 基于聚类分割法7.6 基于聚类分割法(a)原图像（b）原图像（c）原图像(d)分割结果（e）分割结果（f）分割结果Modern Image Analysis本 章 要 求本 章 要 求本章要求：1.了解图像分割的定义和方法，掌握图像分割的依据；2.掌握边缘点检测的原理和几种常用的点检测算子及其特点；3.了解边缘线跟踪的方法，掌握Hough变换法检测直线的原理和过程；4.了解门限化分割和区域分割的原理和方法，掌握四叉树分裂合并法的过程。