【摘要】  针对医学图像的特点，设计了一种聚类分析的图像分割算法，并且将遗传算法引入聚类，利用遗传算法的并行性和随机搜索性，从DBSCAN算法出发，针对其局限性提出了一种基于取样的DBSCAN算法及其遗传优化，从而达到较好的分割效果。

【关键词】  医学图像; 聚类算法; 遗传算法; 分割

　随着医学技术的发展，有关医学诊断的各种图像在现代疾病辅助诊断中占有相当重要的地位，在分析和阅读灰阶医学图像时，图像的对比度、边缘特征和信噪比等对诊断的正确性致关重要。但是在图像拍摄中避免不了的一些噪声(量子噪声、颗粒噪声、CCD暗电流噪声等)及病变变化微小情况下的不清晰的图像信息，影响了疾病的正确诊断，因此为了提高疾病的正确诊断率，医学图像处理技术就显得尤为重要[1]。

　　近年来，医学图像处理技术中的分割技术是国际上图像分割领域的一个新的研究热点。该方法将图像映射为带权无向图，把像素视作节点。利用最小剪切准则得到图像的最佳分割，该方法本质上将图像分割问题转化为最优化问题。是一种点对聚类方法。对数据聚类也具有很好的应用前景。这种分割技术对医学诊断有很大的帮助。

　　1 聚类算法

　　近年来，大量数据被存储到空间数据库中，如何提高查询效率和从大量数据中提取有用的模式显得尤为重要。聚类分析是将物理或抽象的对象组成的集合分组成为由类似的对象组成的多个簇，使得处于相同簇中的对象具有最大的相似性，而处于不同簇中的对象具有最大的差异性的方法及过程.聚类可以定义如下：在数据空间A中，数据集由许多数据点(或数据对象)组成，数据点 xi=(xi1，……,xid)∈A，xi 的每个属性(或特征、或维度) 既可以是数值型的，也可以是枚举型的.数据集A相当于是一个n×d矩阵.假设数据集X中有n个对象xi(i=1，…，n)。聚类的最终目的是把数据集X划分为K个分割Cm(m=1，… ，K)，也可能有些对象不属于任何一个分割，这些就是噪声Cm。所有这些分割与噪声的并集就是数据集X ，并且这些分割之间没有交集，即：x=c1∪，…,ck∪cnCi∩Cj = (i≠j )这些分割Cm就是聚类[2]。

　　2 DBSCAN聚类算法

　　Ester Martin等人提出的DBSCAN聚类算法是一种基于密度的聚类算法。该算法利用类的密度连通性可以快速发现任意形状的类。其基本思想是：对于一个类中的每个对象，在其给定半径的领域中包含的对象不能少于某一给定的最小数目。在DBSCAN算法中，发现一个类的过程是基于这样的事实：一个类能够被其中的任意一个核心对象所确定。为了发现一个类，DBSCAN先从对象集D中找到任意一对象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个最临近的对象之间的距离。然后，根据求得的距离由小到大排序，并绘出排序后的图，称做kdist图。kdist图中的横坐标表示数据对象与它的第k个最近的对象间的距离;纵坐标为对应于某一kdist距离值的数据对象的个数。R3树的建立和kdist图的绘制非常消耗时间。此外，为了得到较好的聚类结果，用户必须根据kdist图，通过试探选定一个比较合适的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算法的另一个缺点。由于使用全局ε值，若取较小的ε值，较稀的类将被划分成多个性质相似的类;与此相反，若取较大的ε值，那么离得较近而密度较大的那些类将很可能被合并为同一个类.它们之间的差异也就因为选取较大的ε值而被忽略。所以，很难选取一个合适的ε值来进行聚类且得到比较准确的聚类结果。

　　4.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);⑦若t≤T，则t=t+1，转到⑤,否则得到群体P(t)，即优化的核心对象;⑧遗漏点处理及类合并;　⑨输出聚类结果，算法结束。

　　其程序代码是：FuNcTlON ExpandCluster(p，D，eps，MinPts){ retrieve the Epsneighborhood NEps(p)of P;IF NEps(p) mark P as noise and RETURN;ELSEselect a new clusterid and mark all objects in NEps(p)with current clusterid;push all objects from NEps(p){p}onto the stack seeds;WHILE NOT seeds.empty()DO{CurrentObject：seeds.top();retrieve the Epsneighborhood 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 currentclusterid;seeds.pop();RETURN}}ExpandC1uster(p，D，eps，MinPts)函数用来检查p邻域中的核心对象，并进行类的扩展。在算法中使用了堆栈，把对象p的邻域中的对象全部放入堆栈中，然后分别考察这些对象是否是核心对象。

　　5 结论

　　本研究针对医学图像的特点，设计了一种聚类分析的图像分割算法，并且将遗传算法引入聚类，利用遗传算法的并行性和随机搜索性，从DBSCAN算法出发，针对其局限性提出了一种基于取样的DBSCAN算法及其遗传优化。取样技术显著压缩了问题规模，降低了对硬件的要求，而遗传算法又可以对结果进行全局最优化处理，避免陷入局部最优解，保证聚类质量，并能在时间性能上获得较满意的结果。

【参考文献】
  　　1 胡学龙，许开宇.数字图像处理.电子工业出版社，2006.

　　2 Griffith J M，Sorenson J R，JenningsGrant T，et a1.Development of an interactive computerassisted instruction(ICAI)program for patient prenatal genetic screening and carrier testing for use in clinical settings.Patient Education And Counseling，2005，59(2)：199～204.

　　3 石陆魁，何丕廉.一种基于密度的高效聚类算法.计算机应用，2005，25(8)：1824～1826;1839.

　　4 张曙红，孙建勋，诸克军.基于遗传优化的采样模糊C均值聚类算法.系统工程理论与实践，2004，5：121～125.

　　5 李莉平.密度聚类法在图像分割中的应用.计算机时代，2009.

　　6 孙思.利用遗传思想进行数据划分的DBSCAN算法研究.重庆大学计算机学院,2005.