第四章 图像分割new

《第四章 图像分割new》由会员分享，可在线阅读，更多相关《第四章 图像分割new（161页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,0,,单击此处编辑母版文本样式,1,,第二级,2,,第三级,3,,第四级,4,,第五级,5,,,,,,*,第十章 图像分割,图像分割引言,,边界分割法,,边缘连接分割法,,阈值分割法,,面向区域的分割,,图像分割引言,引言,,图像分析系统的基本构成,,图像分割的概念,,图像分割的基本思路,,图像分割的基本策略,图像分析系统的构成,,识别,,与,,解释,,,结果,知识库,表示与描述,,,预处理,,分割,,,低级处理,,高级处理,,中级处理,图像获取,,,问题,图像分割,,,,把图像空间按照一定的要求分成一些,“,有意义,”,的区域的技术叫图像分割。,,例如：,,（,1,

2、）要确定航空照片中的森林、耕地、城市区 域等，首先需要将这些部分在图像上分割出来。,,（,2,）要辨认文件中的个别文字，也需先将这些文字分选出来。,,（,3,）,要识别和标定细胞的显微照片中的染色体，需要用图像分割技术。,,,,,,一幅图像通常是由代表物体的图案与背景组成，简称物体与背景。若想从一幅图像中,“,提取,”,物体，可以设法用专门的方法标出属于该物体的点，如把物体上的点标为,“,1,”,，而把背景点标为,“,0,”,，通过分割以后，可得一幅二值图像。,图像分割的应用领域,,,机器阅读理解,,,OCR,录入,(Optical Character Recognition),,遥感图像自

3、动识别,,在线产品检测,,医学图像样本统计,,医学图像测量,,图像编码,,图像配准的预处理,,图像分割的意义,把图像分解成构成它的部件和对象的过程,,有选择性地定位感兴趣对象在图像中的位置和范围,图像分割的基本思路,从简到难，逐级分割,,控制背景环境，降低分割难度,,把焦点放在增强感兴趣对象，缩小不相干图像成分的干扰上,,图像分割方法分类：,,,大致可以分为基于边缘检测的方法和基于区域生成的方法。,,第一类为找出图像的边缘信息，首先检出局部特性的不连续性，再将它们连成边界，这些边界把图像分成不同的区域，从而分割出各个区域，常用边缘检测方法,有基于边缘检测的图像分割、基于阈值选取的图像分割；,图

4、像分割方法分类：,,,第二类为基于区域生成的方法，是将像素分成不同的区域，根据相应的区域特性在图像中找出与其相似的部分并进行处理，常用的方法有区域生长、分裂,-,合并分割方法。,,以上这两类方法互为对偶，相辅相成，有时还要将它们结合起来，以得到更好的分割效果。,图像分割的基本策略,,图像分割的基本策略，基于灰度值的两个基本特性：,,不连续性,——,区域之间,,相似性,——,区域内部,,根据图像像素灰度值的,不连续性,,先找到点、线（宽度为,1,）、边（不定宽度）,,再确定区域,,,,根据图像像素灰度值的,相似性,,通过选择阈值，找到灰度值相似的区域,,区域的外轮廓就是对象的边,,不连续性,,边

5、界分割法,,边缘连接分割法,,相似性,,阈值分割法,,面向区域的分割,,数学形态学图像处理,1,间断检测,间断检测法,,点的检测,,线的检测,,边的检测,1.1,点的检测,用空域的高通滤波器来检测孤立点,,例：,,,,,,R = (-1 × 8 × 8 + 128 × 8) / 9,,= (120 × 8) / 9 = 960 / 9 = 106,,设 ：阈值：,T = 64 R > T,8,8,8,8,128,8,8,8,8,图像,-1,-1,-1,-1,8,-1,-1,-1,-1,模板,点的检测,一个典型的,3×3,模板,点的检测,——,算法描述,,设定阈值,T,，如,T

6、 = 32,、,64,、,128,等,,,并计算高通滤波值,R,,如果,R,值等于,0,，说明当前检测点的灰度值与周围点的相同,,当,R,的值足够大时，说明该点的值与周围的点非常不同，是孤立点。通过阈值,T,来判断,,,|R| >,,T,检测到一个孤立点,点的检测,1.2,线的检测,通过比较典型模板的计算值，确定一个点是否在某个方向的线上。,-1,-1,-1,2,2,2,-1,-1,-1,水平模板,-1,-1,2,-1,2,-1,2,-1,-1,45,度模板,-1,2,-1,-1,2,-1,-1,2,-1,垂直模板,2,-1,-1,-1,2,-1,-1,-1,2,135,度模板,线的检测,,,

7、,,,,用,4,种模板分别计算,,,R,水平,,= -6 + 30 = 24,,R,45,度,,= -14 + 14 = 0,,R,垂直,,= -14 + 14 = 0,,,R,135,度,,= -14 + 14 = 0,1,1,1,5,5,5,1,1,1,1,1,1,5,5,5,1,1,1,1,1,1,5,5,5,1,1,1,,例：,图像,线的检测,——,算法描述,,依次计算,4,个方向的典型检测模板，得到,R,i,,i=1,2,3,4,,如,|,R,i,| > |,R,j,|,对于所有的,j = i,，那么这个点被称为在方向上更接近模板,i,所代表的线,,,设计任意方向的检测模板,,可能大

8、于,3*3,,模板系数和为,0,,感兴趣方向的系数大,,线的检测,1.3,边缘的检测,边界的定义：,,两个具有相对不同灰度值特性的区域的边界线,,适用于：,,假定问题中的区域是非常类似的，两个区域之间的过渡，仅仅根据灰度的不连续性便可确定,,不适用于：,,当假定不成立时，阈值分割技术一般来说比边缘检测更加实用,边缘的检测,,,,,,,,,分割对象区域,分割对象区域,边缘的检测,边缘的检测基本思想,计算局部微分算子,截面图,边界图像,边缘的检测,一阶微分：用梯度算子来计算,特点：对于亮的边，边的变化起点是正的，结束是负的。对于暗边，结论相反。常数部分为零。,,用途：用于检测图像中边的存在,二阶微

9、分：通过拉普拉斯来计算,特点：二阶微分在亮的一边是正的，在暗的一边是负的。常数部分为零。,用途：,,1,）二次导数的符号，用于确定边上的像素是在亮的一边，还是暗的一边。,,2,）,0,跨越，确定边的准确位置,,,边缘的检测,梯度算子,,函数,f(x,y,),在,(,x,y,),处的梯度为,,一个向量：,,,f = [f / x , f / y],,,计算这个向量的大小为：,,,f =,mag(f,) = [(f / x),2,+(f / y),2,],1/2,,,近似为,:,f  |x| + |y|,z,2,z,8,z,5,z,3,z,9,z,6,z,1,z,7,

10、z,4,梯度算子,,,梯度的方向角为：,,,(,x,y,) =,tan(y,/ x),,Sobel,算子,为：,,,,x = (z,7,+ 2z,8,+ z,9,),,- (z,1,+ 2z,2,+ z,3,),,y = (z,3,+ 2z,6,+ z,9,),,- (z,1,+ 2z,4,+ z,7,),,梯度值： ,f  |x| + |y|,-2,2,0,-1,1,0,-1,1,0,0,0,0,-1,-1,-2,1,1,2,x,y,,,Sobel,梯度算子的使用与分析,,,1.,直接计算,y,、,x,可以检测到边的存在， 以及从暗到亮

11、，从亮到暗的变化,,,2.,仅计算,|x|,，,产生最强的响应是正交 于,x,轴的边；,|y|,则是正交于,y,轴的边。,,,3.,Sobel,算子具有平滑效果，由于微分增强 了噪音，这一点是特别引人注意的特性,拉普拉斯,,,二维函数,f(x,y,),的拉普拉斯,,是一个二阶的微分定义为：,,,2,f = [,2,f,／,x,2,, ,2,f,／,y,2,],,,可以用多种方式被表示为数字形式。对于一个,3 × 3,的区域，经验上被推荐最多的形式是,：,,2,f,,= 4z,5,,–,(z,2,+ z,4,+ z,6,+ z,8,),z,2,z,8,z,5,z,3,z,

12、9,z,6,z,1,z,7,z,4,拉普拉斯,拉普拉斯,,拉普拉斯算子的分析,,缺点：对噪音的敏感；会产生双边效果； 不能检测出边的方向,,应用：拉普拉斯算子不直接用于边的检,,测，通常只起辅助的角色；,,检测一个像素是在边的亮的一边还是暗的一边,,利用零跨越，确定边的位置,2,边缘连接和边界检测,边缘连接法,,局部处理法,,Hough,变换,边缘连接的意义,——,边检测算法的后处理,,由于噪音的原因，边界的特征很少能够被完整地描述，在亮度不一致的地方会中断,,因此典型的边检测算法后面总要跟随着连接过程和其它边界检测过程，用来归整边像素，成为有意义的边,2.1,局部连接处理,,连接处理的时

13、机和目的,,连接处理的原理,,局部连接算法描述,连接处理的时机和目的：,,时机：对做过边界检测的的图像进行,,目的：连接间断的边,连接处理的原理,,对做过边检测的图象的每个点,(,x,y,),的特性进行分析,,分析在一个小的邻域（,3×3,或,5×5,）中进行,,所有相似的点被连接，形成一个享有共同特性象素的边界,,用比较梯度算子的,响应强度,和,梯度方向,确定两个点是否同属一条边,点,(,x,’,,y,’,),点,(,x,y,),,,,,,,,,,,,,,,,,,,,,,,,,,,,连接处理的原理,通过比较,梯度,，,确定两个点的连接性：,,对于点,(,x,’,,y,’,),，判断其是否与邻

14、域内的点,(,x,y,),相似，当：,,,,|,f,(,x,y,),–,,f,(,x,’,,y,’,)|,,T,,其中,T,是一个非负的阈值,比较梯度向量的,方向角,,,对于点,(,x,’,,y,’,),，判断其是否与邻域内的点,(,x,y,),的方向角相似，当：,,,|,,(,x,y,),–,,,(,x,’,,y,’,)| < A,,其中,A,是一个角度阈值,连接处理的原理,,,当梯度值和方向角都是相似的，则点,(,x,’,,y,’,),，与边点界,(,x,y,),是连接的,点,(,x,’,,y,’,),点,(,x,y,),,,,,,,,,,,,,,,,,,,,,,,,,,,,局部

15、连接算法描述,,1,）设定,A,、,T,的阈值大小，确定邻域的大小,,2,）对图像上每一个像素的邻域点进行分析， 判断是否需要连接。,,3,）记录像素连接的情况，另开一个空间， 给不同的边以不同的标记。,,4,）最后，删除孤立线段，连接断开的线段。,,2.2,霍夫（,Hough,）变换,,问题的提出,,Hough,变换的基本思想,,算法实现,,Hough,变换的扩展,Hough,变换问题的提出,,在找出边界点集之后，需要连接，形成完整的边界图形描述,,,,,,,,,,,,,,,,,,,,,,,,,,Hough,变换的基本思想,,对于边界上的,n,个点的点集，找出共线的点集和

16、直线方程。,,对于任意两点的直线方程：,y = ax + b,，构造一个参数,a,，,b,的平面，从而有如下结论,：,a,b,Hough,变换的基本思想,,xy,平面上的任意一条直线,y = ax + b,,，对应在参数,ab,平面上都有一个点,,,,过,xy,平面一个点,(,x,y,),的所有直线，构成参数,ab,平面上的一条直线。,a,b,,a,b,,Hough,变换的基本思想,,如果点,(x,1,,y,1,),与点,(x,2,,y,2,),共线，那么这两点在参数,ab,平面上的直线将有一个交点,,,,,,在参数,ab,平面上相交直线最多的点，对应的,xy,平面上的直线就是我们的解,a,b

17、,,y,x,,(x,1,,y,1,),,(x,2,,y,2,),a,’,b,’,Hough,变换的基本思想,,a,b,A,Hough,变换算法实现,,由于垂直直线,a,,为无穷大，我们改用极坐标形式：,,xcos,,,,+,ysin,,=,,,参数平面为,,,,,,，对应不是直线而是正弦曲线,,使用交点累加器，或交点统计直方图，找出相交线段最多的参数空间的点,,然后找出该点对应的,xy,平面的直线线段,,3,门限处理（阈值分割法）,阈值分割法,,通过交互方式得到阈值,,通过直方图得到阈值,,通过边界特性选择阈值,,简单全局阈值分割,,基于多个变量的阈值,3.1,基础,,阈值分割法的基

18、本思想：,,确定一个合适的阈值,T,（阈值选定的,,好坏是此方法成败的关键）。,,将大于等于阈值的像素作为物体或背景，生成一个二值图像。,,If,f(x,y,),,T set 255,,Else set 0,,在四邻域中有背景的像素，既是边,,界像素。,0,255,255,0,255,0,255,255,255,门限处理（阈值分割法）,可被看做一种涉及测试下列形式函数,T,的一种操作,,,T = T[,x,y,p(x,y),f(x,y,)],,,如果,T,取决于,f(x,y,),时，,门限（阈值）就称为全局的,,如果,T,取决于,f(x,y,),和,p(x,y,），,门限（阈值）就称为局

19、部的,门限处理（阈值）分割法的特点,,适用于物体与背景有较强对比的情况，重要的是背景或物体的灰度比较单一。（可通过先求背景，然后求反得到物体）,,这种方法总可以得到封闭且连通区域的边界。,灰度值,f(x,0,,y,0,),T,通过直方图得到阈值,,基本思想,,边界上的点的灰度值出现次数较少,T,,取值的方法：,,取直方图谷底,(,最小值,),的灰度值为阈值,T,,,缺点：会受到噪音的干扰，最小值不是预 期的阈值，而偏离期望的值；,改进：,,,取两个峰值之间某个固定位置，如中间位置上。由于峰值代表的是区域内外的典型值，一般情况下，比选谷底更可靠，可排除噪音的干扰,,T,3.2,亮度的作用,,

20、亮度对门限处理（阈值）分割法的影响，特别是对全局的影响。,,,,讨论,——,,用一幅图像是由反射率分量和亮度分量的乘积组成,The histogram of,z,(,x,,,y,) is given by the convolution of the histograms of,i’,(,x,,,y,) and,r’,(,x,,,y,),照明的作用,用,于,解決非均勻性照明的,实际,作法,,把照明投射至一固定的白色反射面,,,产,生,1,幅影像,,,得到正規化影像,,(,此影像,仅余,反射分量,),,,決定,r,(,x,,,y,),所需的,单,一,临,界值,k,,則,对于,,h,(,x,,,y

21、,),的,临,界值,为,,T,/,k,3.3,基于全局阈值分割,,基本思想：用前述方法获得阈值,T,，并产生一个二值图，区分出前景对象和背景,,算法实现：,,规定一个阈值,T,，逐行扫描图像。,,凡灰度级大于,T,的，颜色置为,255,；凡灰度级小于,T,的，颜色置为,0,,适用场合：明度图像是可以控制的情况，例如用于工业监测系统中,,3.4,基于自适应门限（阈值）,,问题：不均匀,亮度这样的成像因素导致用,直方图得到单一全局,门限处理（阈值）分割法无法有效分割。,,,,方法：将图像进一步细分为子图像，并对不同的子图像使用不同的门限处理（阈值）进行分割。这类门限处理（阈值）是自适应的。,Cha

22、pter 10,,Image Segmentation,Chapter 10,,Image Segmentation,3.5,最佳全局和自适应门限（阈值）,,一种产生最小平均分割误差的估计门限处理（阈值）的方法。,,,讨论,——,,假设一幅图像仅包含两个主要的灰度级区域。,,,,,3.6,利用边界特性改进直方图和局部,,门限处理,,基本思想：,,如果直方图的各个波峰很高、很窄、对称，且被很深的波谷分开时，有利于选择阈值。,,为了改善直方图的波峰形状，我们只把区域边缘的像素绘入直方图，而不考虑区域中间的像素。,,用微分算子，处理图像，使图像只剩下边界中心两边的值。,通过边界特性选择阈值,,基本思

23、想：,,这种方法有以下优点：,,1),在前景和背景所占区域面积差别很大时，,不会造一个灰度级的波峰过高，而另一个过低,,2),边缘上的点在区域内还是区域外的概率是相等的，因此可以,增加波峰的对称性,,3),基于梯度和拉普拉斯算子选择的像素，可以,增加波峰的高度,通过边界特性选择阈值,,,算法的实现：,,1,）对图像进行梯度计算，得到梯度图像。,,2,）得到梯度值最大的那一部分（比如,10%,） 的像素直方图,,3,）通过直方图的谷底，得到阈值,T,,如果用拉普拉斯算子，不通过直方图，直接得到阈值，方法是使用拉普拉斯算子过滤图像，将,0,跨越点对应的灰度值为阈值,T,,Chap

24、ter 10,,Image Segmentation,P,参数法,若各区域面积占图像总面积的比例,p,已知时，可以用,p,参数法,,步骤：若已知低灰度区域面积比例为,p,：,,1.,根据灰度直方图从左到右计算直方图的累加值；,,,,2.,当求得,C,值近似等于已知的面积比例,p,时，查找对应的灰度级,T,；,,3.,以,T,为阈值对图像进行分割；,,相反，如果已知高灰度区域面积比为,p2,的情况，与上述过程类似，只是第一步的累加值变为从右向左求累加。,,最佳阈值法,思路,：使图像中目标物和背景分割错误最小的阈值。,,设目标灰度级分布的概率密度函数为,，,,背景,灰度级分布的概率密度函数为,，,

25、,目标像素占总像素数的比值为 ，,,则图像总的灰度级分布概率密度函数为,若选取分割阈值为,，则,背景像素错分为目标像素的概率,：,,,,同理，,目标像素错分为背景像素的概率,：,,,,,则,总的错分概率,为,,寻找一个,使 取最小值；,,,令,,,,得,,设 ， ，,,代入上式并取对数得,,,,式中： ，,,，,,,,有两个解。,,但当 ，存在唯一解,,,,,,当 时,

26、,,,,,,（引出了均值法、均值迭代,阈值选择法,）,,均值迭代阈值选择法,,1.,选择一个初始阈值的估计值,T,（,一个好的初始值是灰度的均值）。,,2.,用该阈值把图像分割成两个部分,R1,和,R2,；,,3.,分别计算,R1,和,R2,的灰度均值,µ1,和,µ2,；,,4.,选择一个新的阈值,T,：,T,＝,(µ1,＋,µ2)/2,；,,5.,重复步骤,2-4,直至后续的迭代中平均灰度值,µ1,和,µ2,保持不变。,自适应阈值,自适应阈值方法：当光照不均匀、有突发噪声，或者背景灰度变化比较大时，整幅图像分割将没有合适的单一门限，因为单一的阈值不能兼顾图像各个像素的实际情况。这时，可对图像

27、按照坐标分块，对每一块分别选一阈值进行分割。这种与坐标相关的阈值也称为动态阈值方法。 优缺点：时间和空间复杂度比较大，但抗噪声能力比较强，对采用全局阈值不容易分割的图像有较好的效果。,自适应阈值的选取：比较简单的方法是对每个像素确定以它为中心的一个邻域窗口，计算窗口内像素的最大和最小值，然后取它们的均值作为阈值。,,对图像分块后的每一个子块可以采用直方图分析，如果某个子块内有目标和背景，则直方图呈双峰。如果块内只有目标或背景，则直方图没有双峰，可根据邻域各块分割得到的参数插值进行分割。实际的自适应阈值分割完全可以根据图像的实际性质，对每个像素设定阈值，但这个过程要考虑到实际的要求和计算

28、的复杂度问题。,,另外，类间方差最大阈值分割,,最大熵阈值分割等将阈值选取转化为优化问题进行处理,2.,基于曲面拟合的边缘检测,,,基本思想,,先用一个平滑的曲面与待检测点周围某区城内像素的灰度值进行拟合，然后用这个平面或曲面的梯度代替点的梯度，从而实现边缘检测,。,以减小噪声及干扰的影响,目的,,曲面,一次曲面,,二次曲面,一次曲面拟合：,,,令图像面积元由,f,(,x,,,y,),,f,(,x,+1,,y,),,f,(,x,,,y,+1),,f,(,x,+1,,y,+1)4,个相邻元素组成，用一次平面,,ax,+,by,+,c,= 0,去拟合该面积元。即用,,,去逼近,f,(,x,,,y,

29、),。,,,用最小平方误差方法求参数,a,,,b,,,c,,,即使误差极小,对上式分别对,a,,,b,,,c,求偏导,,,并令结果等于零,,,得关于,a, b, c,的,3,个方程组，解得,解得,由梯度定义，平面,ax+ by+,cx,上的梯度幅度为,：,4,,基于区域的分割,区域的分割,,基本概念,,像素集合的,区域增长,,区域分裂,与,合并,4.1,基本概念,,目标：将区域,R,划分为若干个子区域,R,1,,R,2,,,…,,,R,n,，这些子区域满足,5,个条件：,,,1),完备性：,,,2),连通性：每个,R,i,都是一个连通区域,,3),独立性：对于任意,i,≠,j,，,R,i,∩,

30、R,j,=,Ф,基本概念,,4),单一性：每个区域内的灰度级相等，,,,P,（,R,i,）,= TRUE,，,i = 1,2,,…,,n,,5),互斥性：任两个区域的灰度级不等，,,,P,（,R,i,∪,R,j,）,= FALSE,，,i≠j,,4.2,区域增长,,算法实现：,,1,）根据图像的不同应用,选择一个或一组种子,，它或者是最亮或最暗的点，或者是位于点簇中心的点,,2,）选择一个描述符（条件）,,3,）从该种子开始向外扩张，首先把种子像素加入结果集合，然后不断将与集合中各个像素连通、且满足描述符的像素加入集合,,4,）上一过程进行到不再有满足条件的新结点加入集合为止,通过像素集合的,

31、区域增长,,,种子像素,,,,,,,,,,,,,,,,,,,,区域,A,,区域,B,,种子像素,,,4.3,区域分离与合并,,算法实现：,,1,）对图像中灰度级不同的区域，均分为四个子区域,,算法实现：,,2,）如果相邻的子区域所有像素的灰度级相同，则将其合并,,3,）反复进行上两步操作，直至不再有新的分裂与合并为止,,Chapter 10,,Image Segmentation,算法实现：实际应用中还可作以下修改,P(R,i,),的定义为：,,1,）区域内多于,80%,的像素满足不等式,,,|,z,j,-m,i,|<=2σ,i,，,,,其中：,z,j,是区域,R,i,中第,j,个点的灰度级，

32、,,,m,i,是该区域的,平均灰度级,，,,,σ,i,是区域的灰度级的,标准方差,。,,2,）当,P(R,i,)=TRUE,时，将区域内所有像素的灰度级置为,m,i,。,例判断准则像素与种子像素灰度差的绝对值小于阈值,T,（,a,）,给出像素值为,‘,1,’,和,‘,5,’,的种子,,（,b,）,T=3,，,恰好分成两个区域,,（,c,）,T=1,，,有些像素无法判断,,（,d,）,T=6,，,整个图被分成一个区域,区域增长法,,问题,,选择或确定一组能正确代表所需区域的种子像素,,具体问题具体分析,,先验知识（如：军用红外图像中检测目标时，选最亮的像素作为种子）,,无先验知识（可根据直方图选

33、取灰度中像素个数多的像素作为种子）,,确定在生长过程中能将相邻像素合并的准则,,具体问题相关（目标和背景的像素分布特点）,,图像数据种类（单色、灰度还是彩色）,,像素间的连通性和邻近性,,制定让生长过程停止的条件或规则,,一般是没有满足生长的像素,,应考虑图像的局部性质（灰度、纹理和彩色）,,目标的全局性质（尺寸、形状等）,生长准则和过程,,区域生长的关键是选择合适的生长或相似准则,,1,、基于区域灰度差,,基本方法：种子像素的灰度值与邻域像素的差,,改进：先合并具有相同灰度的像素，然后求出所有邻接区域间的平均灰度差，并合并最小灰度差的邻接区域，重复上述步骤直到没有区域合并。,平均灰度的,均匀

34、测度,度量可以作为区域增长的相似性检测准则。,,设某一图像区域,O,，,其中像素数为,N,，,均值表示为,区域,O,均匀测度度量：,上式可解释为：,在区域,O,中，各像素灰度值与均值的差不超过某阈值,K,，,则其均匀测度度量为真。,2,、基于区域灰度分布统计性质,,基本方法：以灰度分布相似性作为生长准则来决定区域的合并步骤：,,1,、把图像分成互不重叠的小区域,,2,、比较邻接区域的累积灰度直方图，根据灰度分布的相似性进行区域合并,,3,、重复,2,，直到满足终止条件,灰度分布相似性的两种检测方法：,,（,1,）,Kolmogorov,-Smirnov,检测,,,,,（,2,）,Smoothe

35、d-Difference,检测,,,,4.5,聚类分割,聚类分析是多元统计分析的方法之一，也是统计模式识别中一个重要分支。它试图根据数据集的内部结构将数据集分成不同的几个子类，使得在同一类的样本尽可能的相似，在不同类的样本尽可能的相异。,,相似性度量,,在确定数据集中样本相似性程度时，距离是常用的测度之一，一些重要距离测度有,:,,欧式距离、,Minkowski,距离、,Chebychev,距离、平方距离、非线性测量以及概率距离测度（如,Bhattacharyya,距离、散度、,Chernoff,概率距离以及,Mahalanobis,距离等）,,,欧式距离二维的公式是,d = sqrt((x1

36、-x2),2,+(y1-y2),2,),目前已提出许多方法来解决聚类问题，大体上可分为硬聚类方法和模糊聚类方法两类。聚类方法的分类如图,,划分聚类算法是将数据集分成若干子集。其中每个子集至少包含一个元素，而数据集中每个元素必须属于且只属于一个子集。,,,给定数据集,X,以及类别数目,k,，划分方法是由一个初始划分开始，通过优化一个评价函数把数据划分为若干子类，因此事实上把聚类问题转化成优化问题。,,,划分聚类方法输出的是多个互不相交的聚类集，常用的基于划分的聚类方法有最近邻法、最大最小距离法、,k-,均值法,(k-means),、,k-,中心法,(,k-medoid,),、,CLARA,方法等

37、,层次聚类方法根据数据集内部相似性，对给定的数据集按层次进行分解，结果形成一棵以数据子集为节点的类别树。,,该过程可通过合并（,agglomerative,）和分裂（,divisive,）两种途径实现。由于一个步骤完成就不能被撤销，不用担心组合数目的不同选择，所以计算代价会较小，但是该技术的一个主要问题是它不能更正错误的决定。现在比较常用的层次聚类方法有,BIRCH (balanced iterative reducing and clustering using,hierarchies)[,[i,],],，,CURE (clustering using,representatives)[,[

38、ii,],],等,,[[i]],Brandtberg,Tomas, Individual tree-based species classification in high spatial resolution aerial images of forests using fuzzy sets. Fuzzy sets and systems. 132(3), 2002, pp.371-387,,[[ii]],Guha,,Sudipto,,,Rastogi,Rajeev, Shim,Kyuseok,. Cure: an efficient clustering algorithm for lar

39、ge databases. Information systems. 26(1), 2001, pp.35-58,基于密度的聚类方法与其他方法的一个根本区别是：它不是基于各种各样距离作为相似性度量，而是基于密度。,,基于密度的算法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可以发现任意形状的类。该方法能克服基于距离的算法只能发现“类圆形”聚类的缺点，可以发现任意形状的聚类，还能够有效去除噪声。具有代表性的基于密度的方法有：,DBSCAN (density based spatial clustering of applications with noise) [,[i],],、,

40、OPTICS (ordering points to identify the clustering,structure)[,[ii,],],、,OETICS (ordering edges to identify clustering,structure)[,[iii,],] DENCLU (density based,clustering)[,[iv,],],等,[[i]],Daszykowski,M.,,Walczak,B.,,Massart,D.L. Representative subset selection.,Analytica,,Chimica,,Acta,, 468(1),2

41、002, pp. 91-103,,[[ii]] M.,Ankerst,, M.M.,Breunig,, H.P.,Kriegel,, J. Sander. OPTICS: Ordering points to identify the clustering structure. Proceedings of the ACM SIGMOD’99 International Conference on Management of Data, Philadelphia, PA, 1999, pp.49-60,,[[iii]],Forina,Michele,,Cerrato,,Oliveros,M.

42、Concepcion,,Casolino,,Chiara,,,Casale,Monica. Minimum spanning tree: ordering edges to identify clustering structure.,Analytica,,Chimica,,Acta,. 515(1)2004, pp.43-53,,[[iv]],Hinneburg,A.,,Keim,D.A. An efficient approach to clustering in large multimedia databases with noise. Proc Int. Conf. Knowledg

43、e discovery and data mining(KDD’98)pp.58-65,,基于网格的聚类方法是指采用一个多分辨率的网络数据结构。它首先将数据空间划分成为有限个单元的网格结构，并且所有的处理都是以单个的单元为对象。这样处理的一个突出优点是处理速度快，通常这是与目标数据库中记录的个数无关的，它只是与把数据空间分成多少个单元有关。常用方法有,STING(statistical,information grid-based,method)[,[i,],],、,Wave,Cluster[,[ii,],],以及,GDILC (grid-based density-,isoline,,clu

44、stering)[,[iii,],],算法等,,,[[i]] Wang W., Yang J.,Muntz,R.. STING: a statistical information grid approach to spatial data mining. Proc. of the 23rd very large databases Conf. (VLDB1997). Athens, Greece.,,[[ii]],Sheikholeslami,G.,,Chatterjee,S., Zhang A.,WaveCluster,: A multi-resolution clustering app

45、roach for very large,spatialdatabases,. Proc. 24th very large databases,Conf.(VLDB,98). New York.,,[[iii]] Zhao Y.C., Song J. GDILC: A grid-based density-,isoline,clustering algorithm. Proc. Inter. Conf. on Info-net, Vol.3, 2001,pp.140-145,,基于模型的聚类方法是给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据集。基于模型的方法试图优化给定的数

46、据和某些数学模型之间的适应性，这样的方法经常是基于这样的假设：数据是根据潜在的概率分布生成的。常用的模型方法又可分为基于统计的方法和基于神经网络的方法,。,模糊聚类方法以,1965,年,Zadeh,提出的模糊集理论为基础，自,1966,年,Bellman,，,Kalaba,和,Zadeh,等,[,[i],],首次将其应用于聚类问题以来，模糊聚类方法引起了广泛关注。,,其发展主要有三大方向：,,一方面是基于模糊理论的深入研究，如基于模糊理论的划分概念,[,[ii],],、基于相似关系和模糊关系的聚类方法,[,[iii],],、模糊矩阵及其传递闭包以及基于模糊关系复合的聚类,[,[iv],],等方

47、法的提出；,,一方面是硬聚类方法的模糊化推广，如模糊,c-,均值方法、模糊神经网络方法等的提出；,,第三是同其它如图论、动态模型等方法理论的结合，如动态模糊图最大树聚类方法,[,[v],],、最优图论方式的聚类方法,[,[vi],],等,,[[i]] R. Bellman, R.,Kalaba,, L.A.,Zadeh,. Abstraction and pattern classification. JMAA. 13,1966, pp. 1-7,,[[ii]] E. H.,Ruspini,. Numerical methods for fuzzy clustering. Inf. Sci.

48、2, 1970, pp.319-350,,[[iii]] S. Tamura et al. Pattern classification based on fuzzy relations. IEEE Trans. SMC. 1(1), 1971, pp.61-66.,,[[iv]],Zkim,Le. Fuzzy relation compositions and pattern recognition. Inf.,Sci,, 89, 1996, pp. 107-130,,[[v]],丁斌,.,动态,Fuzzy,图最大树聚类分析,.,数值计算与计算机应用,.2, 1992, pp.157-159

49、,,[[vi]],Zhenggu,Wu,,R.Leathy,. An optimal graph theoretic approach to data clustering: theory and its application to image segmentation. IEEE Trans. PAMI 15(11), 1993, pp.1101-1113.,实际中最常用的是基于目标函数的聚类方法。该方法成为聚类分析主流的原因主要有两个：一是由于将聚类问题表述成优化问题易于与经典数学的非线性规划领域联系起来，可用现代数学方法来求解；另一方面是由于算法的求解过程比较容易用计算机来实现。,,围

50、绕着目标函数的优化问题，目前主要形成三大方向。一是建立合适的目标函数表达式，用数学规划方法求解最优值，如,C-,均值聚类算法，模糊,C-,均值聚类算法及其推广形式等。这类方法的主要缺陷是对初始化较敏感，易于陷入局部极小点，收敛速度较慢。二是将传统的聚类技术与神经网络相结合，借助神经网络的并行特点提高算法的收敛速度。三是将传统的聚类技术与优化方法相结合，以克服算法对初始化敏感，易于陷入局部极小点等问题。如模拟退火算法,[,[i],],，遗传算法,[,[ii],],，演化算法,[,[iii],],等。,,,[[i]],K.S.Asultan,,,S.Z.Selim,. A global algor

51、ithm for the fuzzy clustering problem. PR, 26(9), 1993, pp. 1357-1361.,,[[ii]] Laszlo M.,,Mukherjee,S. A genetic algorithm using hyper-,quadtrees,for low-dimensional K-means clustering. IEEE Trans. Pattern Analysis and Machine Intelligence. 28(4), 2006, pp.533-543.,,[[iii]] G.P.,Babu,,,M.N.Murty,. C

52、lustering with evolution strategies. PR, 2(27), 1994, pp. 321-329.,C,均值聚类方法,,假设所有样本可分为,c,类，各样本在特征空间依类聚集，且近似球形分布,,用一代表点来表示一个聚类，如类内均值,m,i,来代表聚类,K,i,，,m,i,称为聚类中心,,聚类准则：误差平方和,J,,J=sum,c,i,=1,(sum,x∈Ki,(x,i,-m,i,),2,),,,,步骤：,,1,初始化,:,选择,C,个聚类中心,,2,按照最小距离法则对样本,X,进行分类（计算每个像素特征与聚类中心特征的相似度，根据相似度的大小将像素划分到不同的类

53、别中）,,3,更新每一类别的聚类中心,,4,根据聚类准则函数计算,J,（平方误差和）,,5,判断聚类准则,J,是否满足终止条件，如满足，则终止，否则转,2,模糊,C,均值聚类（,FCM,）,,在,C,均值的基础上引入了模糊理论，根据图像像素核聚类中心的加权相似性测度，对目标函数进行迭代优化以确定最佳聚类。,,通过最小化隶属度矩阵,U,和聚类中心矩阵,V,的目标函数,J,m,(U,V,),来实现,,,,其中,u,ik,为第,k,个像素对第,i,类的隶属度，,U={,u,ik,},为隶属度矩阵，,V={v,1,,…,v,c,},为,c,个聚类中心点集，,m>=1,为模糊加权指数，控制数据划分过程的

54、模糊程度,,为第,k,个像素到第,i,个聚类中心的距离，,FCM,就是通过反复迭代优化目标函数来实现，步骤如下：,,1,初始化聚类中心,V,,2,计算隶属矩阵,,,,,3,更新聚类中心,,,,4,重复,2,，,3,直到目标函数收敛,,群体智能聚类方法,,人类的知识和思想来源于对自然界的观察和认识，由此产生了仿生学的概念。在对蚂蚁、蜜蜂、鸟群等群体的观察中，人们发现了一些有趣现象。,,如蜜蜂觅食时，一旦有蜜蜂发现食源，不久就会有成群的蜜蜂飞向该食源；,,在对蚂蚁觅食行为的观察中，发现蚁群总能找到从蚁穴到达食物源的最短路径，而当路径被障碍物遮挡后，蚂蚁群体也能很快绕过障碍，重新找到到达食物源的最优

55、路径；,,在鸟群的飞行中，每只鸟在初始状态下是处于随机位置向各个随机方向飞行的，但是随着时间的推移，这些初始处于随机状态的鸟通过自组织逐步聚集成一个个小的群落，并且以相同速度朝着相同方向飞行，然后几个小的群落又聚集成大群落，大群落可能又分散为一个个小的群落。以上现象均表现出了依靠个体协作形成整体一致功能的群体智能。,,这些由个体表现出智能性群体行为的现象引起研究人员极大兴趣，经研究发现，无智能群体之所以表现出智能行为，是因为其个体之间存在着某种协作机制。如蜜蜂会用飞行的舞姿（兜圈圈）来传递信息，圈子的轴方向表示花蜜的方向，圈数表示有花蜜地方的距离，别的蜜蜂得到该信号，就纷拥向该方向飞去；蚂蚁在

56、觅食过程中会在走过的路径上留下一种称为信息激素（,pheromone,）的物质，其它蚂蚁在选择路径时以此作为参考；而鸟群的个体在飞行中也遵循一定的规则如：,,避免碰撞（,collision avoidance,）：避免和邻近的个体相碰撞；,,速度一致（,velocity matching,）：和邻近的个体的平均速度保持一致；,,向中心聚集（,Flock centering,）：向邻近个体的平均位置移动。,,这样，个体之间存在的这种直接或间接的信息传递机制，通过个体之间的相互协作使群体行为表现出一致性。,,近年来对群体智能的研究取得了一定的成果，特别是蚁群算法和粒子群算法，从初始对现象的研究，提

57、出基本的观点，到不断的完善和改进，虽然还存在一些问题，但已广泛应用于各个领域，形成了一种新型的智能计算方法。,,蚁群觅食行为数学描述如下：,,给定蚁群,{,X,i,}(i,=1,2,…N),，设每只蚂蚁随机从,i,点向,j,点移动，则路径,ij,的长度,d,ij,用两点间的欧式距离计算：,,（,1,）,,蚂蚁沿路径,ij,行走过程中，会释放信息激素，而蚂蚁在选择路径时，倾向于选择信息激素较强的路径。设,t,时刻路径,ij,上的信息激素浓度为,ph,ij,(t,),，则蚂蚁选择路径,ij,的概率,p,ij,可由下式计算：,,（,2,）,,,,其中，,η,ij,(t,),是启发式引导函数，一般取,

58、η,ij,(t,)=1/d,ij,。,α,、,β,分别为蚂蚁行走过程中所积累的信息激素以及启发式引导函数对路径选择的影响因子。,S,为可行路径集合。,,随着蚂蚁的移动，各路径上信息激素发生两种变化，一是随着时间的延长，信息激素逐渐衰减，另一种变化是每只蚂蚁选择一条路径后会在路径上释放新的信息激素。设第,k,只蚂蚁在路径上留下的信息激素为,Δph,ij,k,，各路径上信息激素根据下式进行调整：,,,（,3,）,,其中，,ρ,为信息激素随时间的衰减程度，△,ph,ij,为本次行走中路径信息激素的增量。,,,,（,4,）,,基于蚁群算法的模糊聚类方法,给定待分类数据集,{,X,i,}∈R,d,(i,

59、=1,2,…N),，经过特征提取后，设每个一维或多维的特征矢量为一只蚂蚁，记为,X,i,(i,=1,2,…N),，则基于蚁群算法的聚类方法可描述如下：,,首先，初始化蚁群算法参数，,α,，,β,，,ε,，,λ,。其中，,α,，,β,分别为信息激素和引导函数对路径选择概率的影响因子，,ε,为一个正的极小值，,λ,为模糊聚类时隶属度阈值。,,第二步，计算任意两只蚂蚁之间的距离,d,ij,，这里以欧式距离为例,,,其中，,m,为蚂蚁矢量的维数，,p,为加权因子，根据蚂蚁矢量各分量对聚类的影响程度设定。,,第三步，根据路径长度，计算引导函数，并初始化各路径的信息激素浓度,phij,。设聚类半径为,r,

60、，则,,,第四步，根据公式（,2,），计算蚂蚁,Xi,和,Xj,属于一类的概率,pij,作为两只蚂蚁属于一类的隶属度，将该隶属度与参数,λ,相比较，如果,pij,>λ,，则将两者归为一类。,,第五步，根据公式（,3,）和（,4,）对各路径上的信息激素进行调整。,,按下式更新第,j,类聚类中心，其中，,J,为第,j,类中元素个数：,,,,第六步，计算各类的类间距离，当类间距离小于阈值,ε,时，将两类合并为一类，更新聚类中心。,,第七步，判断是否满足终止条件，如满足，停止，否则，跳回第二步。,,这样，聚类过程成为一个迭代的正反馈过程，蚁群算法的路径选择过程就是对蚂蚁进行归类的过程。根据前面提到的蚁群算法改进策略，可以针对不同应用得到具有不同性能的改进的聚类算法。,图,‑,,原始图像,,Fig. 3-1 Original image,Sobel,算子边缘检测,Canny,算子边缘检测,,FCM,分割结果,蚁群算法分割结果,