资源预览内容
第1页 / 共4页
第2页 / 共4页
第3页 / 共4页
第4页 / 共4页
亲,该文档总共4页全部预览完了,如果喜欢就下载吧!
资源描述
1改进的聚类算法在医学图像分割中的应用【摘要】 针对医学图像的特点,设计了一种聚类分析的图像分割算法,并且将遗传算法引入聚类,利用遗传算法的并行性和随机搜索性,从 DBSCAN 算法出发,针对其局限性提出了一种基于取样的 DBSCAN 算法及其遗传优化,从而达到较好的分割效果。 【关键词】 医学图像; 聚类算法; 遗传算法; 分割随着医学技术的发展,有关医学诊断的各种图像在现代疾病辅助诊断中占有相当重要的地位,在分析和阅读灰阶医学图像时,图像的对比度、边缘特征和信噪比等对诊断的正确性致关重要。但是在图像拍摄中避免不了的一些噪声(量子噪声、颗粒噪声、CCD 暗电流噪声等)及病变变化微小情况下的不清晰的图像信息,影响了疾病的正确诊断,因此为了提高疾病的正确诊断率,医学图像处理技术就显得尤为重要1。近年来,医学图像处理技术中的分割技术是国际上图像分割领域的一个新的研究热点。该方法将图像映射为带权无向图,把像素视作节点。利用最小剪切准则得到图像的最佳分割,该方法本质上将图像分割问题转化为最优化问题。是一种点对聚类方法。对数据聚类也具有很好的应用前景。这种分割技术对医学诊断有很大的帮助。1 聚类算法近年来,大量数据被存储到空间数据库中,如何提高查询效率和从大量数据中提取有用的模式显得尤为重要。聚类分析是将物理或抽象的对象组成的集合分组成为由类似的对象组成的多个簇,使得处于相同簇中的对象具有最大的相似性,而处于不同簇中的对象具有最大的差异性的方法及过程.聚类可以定义如下:在数据空间 A 中,数据集由许多数据点(或数据对象)组成,数据点 xi=(xi1,,xid)A,xi 的每个属性(或特征、或维度) 既可以是数值型的,也可以是枚举型的.数据集 A 相当于是一个 nd 矩阵.假设数据集 X 中有 n 个对象 xi(i=1,n)。聚类的最终目的是把数据集 X 划分为 K 个分割 Cm(m=1, ,K),也可能有些对象不属于任何一个分割,这些就是噪声 Cm。所有这些分割与噪声的并集就是数据集 X ,并且这些分割之间没有交集,即:x=c1,,ckcnCiCj = (ij )这些分割 Cm 就是聚类2。2 DBSCAN 聚类算法Ester Martin 等人提出的 DBSCAN 聚类算法是一种基于密度的聚类算法。该算法利用类的密度连通性可以快速发现任意形状的类。其基本思想是:对于一个类中的每个对象,在其给定半径的领域中包含的对象不能少于某一给定的最小数目。在 DBSCAN 算法中,发现一个类的过程是基于这样的事实:一个类能够被其中的任意一个核心对象所确定。为了发现一个类,DBSCAN 先从对象集 D 中找到2任意一对象 P,并查找 D 中关于半径 Eps 和最小对象 Minpts 的从 P 密度可达的所有对象。如果 P 是核心对象,即半径为 Eps 的 P 的邻域中包含的对象不少于Minpts,则根据算法,可以找到一个关于参数 Eps 和 Minpts 的类。如果 P 是一个边界点,则半径为 Eps 的 P 邻域包含的对象少于 Minpts,P 被暂时标注为噪声点。然后,DBSCAN 处理 D 中的下一个对象。密度可达对象的获取是通过不断执行区域查询来实现的。一个区域查询返回指定区域中的所有对象。为了有效地执行区域查询,DBSCAN 算法使用了空间查询 R 树结构。在进行聚类前,必须建立针对所有数据的 R3 树。另外,DBSCAN要求用户指定一个全局参数 Eps(为了减少计算量,预先确定参数 Minpts)。为了确定取值,DBSCAN 计算任意对象与它的第 k 个最临近的对象之间的距离。然后,根据求得的距离由小到大排序,并绘出排序后的图,称做 kdist 图。kdist图中的横坐标表示数据对象与它的第 k 个最近的对象间的距离;纵坐标为对应于某一 kdist 距离值的数据对象的个数。R3 树的建立和 kdist 图的绘制非常消耗时间。此外,为了得到较好的聚类结果,用户必须根据 kdist 图,通过试探选定一个比较合适的 Eps 值。DBSCAN 算法不进行任何的预处理而直接对整个数据集进行聚类操作。当数据量非常大时,就必须有大内存量支持,I/O 消耗也非常大。其时间复杂度为 O(nlogn)(n 为数据量),聚类过程的大部分时间用在区域查询操作上。DBSCAN 算法对参数 Eps 及 Minpts 非常敏感,且这两个参数很难确定3。3 DBSCAN 算法的性能分析DBSCAN 算法可将具有足够高密度的图像点划分为簇,它能找到图像样本比较密集的部分,概括出图像样本相对比较集中的类,并可在带有“噪声”的图像中进行聚类,完成图像分割;有较强的抗“噪声”能力。但是,该算法对用户定义的参数较敏感, 邻域、最小数目 minpts 的设置的细微不同将导致聚类结果的较大差异;且此算法需扫描整个图像数据库.对每个点对象都进行一次查询,所以计算复杂度较大。在图像分割过程中,若能建立空间索引降低计算量,且通过反复实验能找到适当的 邻域和最小数目 minpts 值,则 DBSCAN 算法是一种较优的图像分割算法4。4 DBSCAN 算法的缺点及改进思路4.1 DBSCAN 算法的缺点对输入参数 敏感是 DBSCAN 算法的主要缺点之一。确定邻域大小的参数 是由用户指定的,但是实际上,参数 很难在算法运行前确定。设每个图像点与它的第 k 个最近图像点之间的距离为 d,用户可根据 d 的排序情况确定参数。但在实际操作中,通过这种方法确定的 与“理想的” 常有微小差距,结果造成聚类结果的很大不同。难以发现密度相差较大的簇是 DBSCAN 算法的另一个缺点。由于使用全局 值,若取较小的 值,较稀的类将被划分成多个性质相似的类;与此相反,若取较大的 值,那么离得较近而密度较大的那些类将很可能被合并为同一个类.它们之间的差异也就因为选取较大的 值而被忽略。所以,很难选取一个合适的 值来进行聚类且得到比较准确的聚类结果。34.2 DBSCAN 算法的改进思路4.2.1 SDGO 算法(sampling DBSCAN with genetic optimization)SDGO 算法的基本思想是:首先确定最小的数据取样量,按取样率从数据集中随机选取数据,对取样数据应用 DBSCAN 算法,然后应用遗传算法对聚类结果进行优化,最后进行遗漏点处理及类合并。由于取样技术显著压缩了问题规模,而遗传算法又可以对结果进行全局最优化处理,因此在时间性能和聚类质量上都能获得较满意的结果。4.2.2 遗传算法5遗传算法的主要思想是基于 C.R.Darwin 的生物进化论和 G.Mendel 的遗传学。它从某一随机产生的或是特定的初始群体出发(作为父本),按照一定的操作规则,如选择、交叉、变异等,不断地迭代计算,并根据每一个个体的适应度值,保留优良品种,淘汰次品,引导搜索过程向最优解逼近。4.2.3 SDGO 算法描述输入:控制参数、聚类数据集输出:聚类结果初始化控制参数。包括样本集大小,交叉概率 pc,变异概率 pm,迭代次数 T,设置进化代数计数器t=0,Eps 和 MinPts;根据式(1)计算最小取样量 minM 并确定取样率(保证取样数据量大于最小取样量)I;对数据集进行取样,依 Eps 和 MinPts 对取样数据应用 DBSCAN 算法,将产生的核心对象作为初始种群;对数据进行正规化处理并用二进制编码;计算群体 p(t)中各个个体的适应度;群体 P(t)经过选择、交叉和变异操作后得到下一代群体 P(t+1);若 tT,则 t=t+1,转到,否则得到群体 P(t),即优化的核心对象;遗漏点处理及类合并;输出聚类结果,算法结束。其程序代码是:FuNcTlON ExpandCluster(p ,D,eps,MinPts) retrieve the Epsneighborhood NEps(p)of P;IF NEps(p) mark P as noise and RETURN;ELSEselect a new clusterid and mark all objects in NEps(p)with current clusterid;push all objects from NEps(p)ponto the stack seeds;WHILE NOT seeds.empty()DOCurrentObject:seeds.top();retrieve the Epsneighborhood NEps(currentObject)of currentobject;IF NEps(currentObject)Minptsselect all objects in NEps(eurrentobject)not yet classified or aremarked as noise;push the unclassified objects onto seeds and mark all of these objects with currentclusterid;seeds.pop();RETURNExpandC1uster(p ,D,eps,MinPts)函数用来检查 p 邻域中的核心对象,并进行类的扩展。在算法中使用了堆栈,把对象 p 的邻域中的对象全部放入堆栈中,然后分别考察这些对象是否是核心对象。5 结论4本研究针对医学图像的特点,设计了一种聚类分析的图像分割算法,并且将遗传算法引入聚类,利用遗传算法的并行性和随机搜索性,从 DBSCAN 算法出发,针对其局限性提出了一种基于取样的 DBSCAN 算法及其遗传优化。取样技术显著压缩了问题规模,降低了对硬件的要求,而遗传算法又可以对结果进行全局最优化处理,避免陷入局部最优解,保证聚类质量,并能在时间性能上获得较满意的结果。【参考文献】1 胡学龙,许开宇.数字图像处理.电子工业出版社,2006.2 Griffith J M,Sorenson J R,JenningsGrant T,et a1.Development of an interactive computerassisted instruction(ICAI)program for patient prenatal genetic screening and carrier testing for use in clinical settings.Patient Education And Counseling,2005,59(2):199204.3 石陆魁,何丕廉.一种基于密度的高效聚类算法.计算机应用,2005,25(8):18241826;1839.4 张曙红,孙建勋,诸克军.基于遗传优化的采样模糊 C 均值聚类算法.系统工程理论与实践,2004,5:121125.5 李莉平.密度聚类法在图像分割中的应用.计算机时代,2009.6 孙思.利用遗传思想进行数据划分的 DBSCAN 算法研究.重庆大学计算机学院,2005.
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号