基于Ncut分割和SVM分类器的医学图像分类算法

1、文章编号:1004-9037(200906-0734-04基于Ncut 分割和SVM 分类器的医学图像分类算法谢红梅连宇彭进业(西北工业大学电子信息学院,西安,710072摘要:为解决医疗诊断中由于疲劳和主观因素影响导致的诊断错误,本文提出了基于N cut 分割方法的医学CT 图像的分割、特征提取和诊断的新方案。将N cut 分割方法应用于脑CT 图像。先进行图像分割,提取感兴趣区域,再从边缘、灰度,纹理三方面提取特征,最后利用支持向量机(SV M 对图像进行分类,为医生的诊断提供参考。从表格化的分类结果看,所提方案有较大的应用价值。关键词:医学图像;N cut 图像分割;特征提取;分类;计算

2、机辅助诊断(CA D中图分类号:T P 391.41;T P 274;T N 911.73文献标识码:A基金项目:西北工业大学毕业设计重点扶持(521030102资助项目;新世纪优秀人才支持(N CET -07-0693资助项目。收稿日期:2008-07-15;修订日期:2008-09-20Ncut -Based Segmentation and SVM Classifier for MedicalImage ClassificationX ie H ongmei ,L ian Yu ,Peng J iny e(Scho ol of Elect ro nic and Infor mation,

3、N o rthw estern P olytechnical U niver sity ,Xi an,710072Abstract :T o identify tum or par t o n a co mputer to mog raphy (CT image,this paper proposes a no vel computer aided diagnosis (CADscheme based on normalized cut (Ncutimage segmen-tation and support vector m achine (SVM classifier .Firstly ,

4、the Ncut segmentation metho d is used to perfo rm the segmentation and to obtain the region o f interest (ROI.T hen,such im -age features like histo gram ,g ray lev el co-occurrence matrix to co nstruct the feature space are extracted.Finally ,SVM classifier is trained and used to perform the classi

5、fication.T he classi-fication r esults show that the new schem e can prov ide useful help fo r better diagnosis .Thus ,the method can solve the problem of medical diag nosis error caused by the hum an fatig ue and the subjective factor.Key words :medical imag e classification ;N cut (Norm alized cut

6、 ;image segm entatio n ;featureextraction ;classifier ;co mputer aided diagnosis (CAD 引言随着医学成像技术的发展,医学图像数据在日常的医疗诊断和医学研究中发挥着越来越重要的作用。医院每天都会产生大量的医学图像数据,如CT,MRI,超声图像等。由于医师在诊断过程中受到影响因素较多,如:医生的医学知识水平和医师经验不同会导致诊断的结果不同;医生人眼疲劳的原因容易忽略某些细微的改变,因此,如何有效地对医学图像进行正确的处理从而诊断出有病变的部位成为当前研究的一个热点课题。针对以上问题,本文提出了以下方法:首先应用归

7、一化分割(Nor malized cut,N cut1,2方法进行图像的分割,提取感兴趣区域;然后对提取的感兴趣区域进行特征提取构成特征空间,接着用支持向量机(Suppo rt vector machine ,SVM 3分类器进行训练;最后进行分类诊断,得出诊断结果。1Ncut 图像分割方法和SVM 分类器1.1Ncut 图像分割方法人们提出了上千种的图像分割方法,常见的有:局部滤波方法,如边缘检测方法,但它仅利用图像局部信息,不能保证得到连续的闭合边界;活动第24卷第6期2009年11月数据采集与处理Jour nal of D ata A cquisition &P ro cessi

8、ng Vo l.24N o.6N o v.2009轮廓方法(Active contour,简称Snakes,其速度是一个瓶颈问题;区域生长与合并算法,如K-均值法、EM算法;基于能量函数的全局最优化方法如水平集分割方法等2。其他图像分割方法还有基于统计迭代方法的Mean shift(均值平移算法,但这些算法往往由于陷入非全局最优而导致实时性比较差。Ncut准则是一种无监督图像分割技术,它不需要初始化,并具有3个主要的特点:(1它将图像分割问题转换为图的划分问题;(2它是一个全局准则;(3它同时最大化不同组之间的不相似性和同一组内的相似性。1997年,由J Shi与J Malik1-2提出Ncu

9、t分割方法,用于解决图像分割与聚类中的问题。该方法对于一幅输入的图像或一个特征点集建立一个带权的无向图,每一个像素或者特征点代表图中的一个节点,边上的权值代表像素或者特征点之间的近似关系,然后在所建立的图上寻找一个正规化的最小割,来对图中的节点进行划分,进而可以完成对图像或者特征点集的分割。它的基本原理是:对于一个给定的图G=(V, E,假设将其分为两个不相交的部分A与B,AB=V,这两个部分不相似程度可以定义为原先连接两部分而现在被删去的所有边的权的综合,定义为图的一个割:cut(A,B=iA,jBw(i,j(1式中w(i,j即连接点i和点j的边的权,它表示两点之间的相似程度。一幅图的最优二

10、分法即是使cut的值最小,但由于割直接与割中边的数目成比例,因此最小割通常并非就是最优割。鉴于最小割的缺点,本文采用归一化割作为最优化准则,从而实现一种有效的图的划分算法4。因此,定义一种新的不同组之间的不相似性度量,即归一化割:Ncut(A,B=cut(A,Bassoc(A,V+cut(A,Bassoc(B,V(2其中assoc(A,V=uA,vVw(u,v表示A中的点和图中所有点之间总的联系程度,assoc(B,V的定义与值类似。同样可以定义同一组内相似性度量函数NassocNassoc(A,B=assoc(A,Aassoc(A,V+assoc(B,Bassoc(B,V(3其中asso c

11、(A,A和asso c(B,B分别表示A与B中所有边的权的总和。可以推出Ncut和Nassoc之间存在如下式表述的必然联系:Ncut(A,B=2-Nassoc(A,B(41.2Ncut图像分割方法的实现设x是一个N= V 维的指示向量,x i=1表示节点i在A中,x i=-1表示节点i在B中,d i=jw(i,j表示点i与其他点之间的所有联系。Ncut可以重写成Ncut(A,B=cut(A,Bassoc(A,V+cut(A,Bassoc(B,V=xi>0,xj<0-w ij x i x jxi>0d i+xi<0,xj>0-w ij x i x jxi<0d

12、 i(5令W为n×n的对称矩阵且W(i,j=w ij,D=diag(d1,d2,d N。这样寻找全局最优值简化为min x Ncut(x=m in yy T(D-Wyy T Dy(6且y i1-xi>0d ixi<0d i,y Td1d N=0,如果y只取实值,则可以通过解决广义特征值问题来求解式(6。(D-Wy= Dy(7y的约束来自于相应的指示x的条件。式(7可以写成规范特征值问题:D-12(D-WD-12z= z(8式中z=D-12y。该特征值问题的对应具有第二个最小特征值的特征向量满足规范约束,即可以利用该特征向量对图进行划分。本文所采取的是将每个子图单独划分,再

13、用递归的方法进行处理4。应用此方法,利用M ATLAB7.0软件进行仿真,选取一幅脑肿瘤CT图像(图1进行分割。对于不同的区域,选择不同的颜色加以标注,不同区域的边缘也可以清晰的显示,分割的结果见图2。由图2可以看出,肿瘤区域被标注出来,肿瘤的形状与大小通过坐标可以获知。根据先验知识,仿真实验中可以通过点击肿瘤区域将肿瘤的图像提取出来并将其保存(见图3,作为下一步分类判断的样本。Ncut方法的重要意义在于:归一化割着重于提取整幅图像的特征,同时度量不同分组之间的总体不相似性和各个组内的相似性的总和。为了计算最小归一化割,可以将其转换为广义特征值问题来对待。735第6期谢红梅,等:基于N cut

14、分割方法和SVM分类器的医学图像分类算法 图1原始脑肿瘤CT 图像图2 待分割的图像图3分割后的脑肿瘤图像1.3特征提取通过上面的方法,脑肿瘤(感兴趣区域已被提取出来,进一步使用机器学习的方法将其有效特征提取出来,而后训练分类器,最后达到利用训练好的分类器区分病变部分和正常组织的目的。(1均值M c 1=1M ×N Mx =1Ny =1f (x ,y (2方差M 2c 2=1M ×N Mx =1Ny =1(f (x ,y -M c 12(3偏度M c 3=1M 3c 2M x =1Ny =1(f (x ,y -M c 13(4峰值M c 4=1M c 2Mx =1Ny =1

15、(f (x ,y -M c 14灰度共生矩阵定义为i 点离开某个固定位置关系 =(D x ,D y 的点上的灰度为j 的概率。灰度共生矩阵用P 表示:P (i ,j (i ,j =0,1,L -1,其中L 为图像的灰度级,i ,j 分别为两个像素的灰度; 表示两个像素间的空间的位置关系。不同的 决定了两个像素间的距离和方向。当两像素间的位置关系 选定后,就生成一定 下的灰度共生矩阵P 。生成了灰度共生矩阵后,提取图像的纹理特征:(1能量(角二阶矩J =L -1i =0L -1j =0P 2(i ,j 它是一种表示灰度分布一致性的统计量。(2反差(对比度G =L -1i =1L -1j =1(i

16、 -j 2P (i ,j 它是描述纹理反差的统计量,当纹理粗时反差小。(3熵:S =-L -1i =0L -1j =0P(i ,j lo g P(i ,j (4逆差:Q =L -1i =0L -1j =0P(i ,j 1+(i -j 2肿瘤图像的空间分辨率高,包含了丰富的边缘、灰度、纹理信息。虽然这些特征都有着很好的数学理论基础,但还是无法完全地涵盖医生所描述有关肿瘤的信息。因此本文还采用了包括边缘在内的辅助特征。经过大量的实验,在特征提取的过程中,本文分别选取如表1所示的共22维典型特征。1.4支持向量机(SVM 分类支持向量机(SVM 理论于1963年由V .Vap-nik 3提出,是一种

17、基于统计学习理论的模式识别方法。基本思想是:通过非线性映射把样本空间映736数据采集与处理第24卷表1脑肿瘤图像分类中采用的特征特征类别特征量边缘特征(2维 边缘矩阵的均值 边缘矩阵的方差灰度特征(4维 灰度均值 灰度方差灰度偏度!灰度峰值纹理特征(16维 能量 对比度相关!熵射到一个高维乃至于无穷维的特征空间(Hilbert 空间,在特征空间中寻求最优划分或回归线性超平面,从而解决样本空间中的高度非线性分类和回归等问题。但这个办法带来的困难就是计算复杂度的增加,而核函数正好巧妙地解决了这个问题。也就是说,只要选用适当的核函数,就可以得到高维空间的分类函数。从而解决回归问题(时间序列分析和模式

18、识别(分类问题、判别分析等诸多问题。SVM常用核函数的有以下几种:(1多项式核函数:K(x,x i=(xx i+1q(2径向基函数:K(x,x i=ex p- x-x i 2(3Sig moid核函数:K(x,x i=tanh(xx i+c在比较实验中,通过选择不同的核函数和不同的惩罚因子可以得到SVM分类器的最优参数配置。2实验结果和分析本文实验硬件环境是:处理器为Intel Cor e Duo(1.6GHz,内存为1024M B;软件环境是: Window s XP操作系统;所用工具软件:包括M ATLAB7.0,LibSvm-2.865和V C+6.0。本文的实验数据的分辨率为512&#

19、215;512。选取100幅脑CT图像对分类器进行训练,共提取124个疑似脑肿瘤区域图像,其中正类样本68个,负类样本56个,按照表1共提取22维特征。待特征提取完成之后,将训练样本送入SVM分类器进行训练。再选取50幅脑CT图像进行测试,共提取60个疑似脑肿瘤区域图像,其中正类样本为30个,负类样本30个,并分别比较将惩罚因子设定为100, 150,200,比较不同情况下的分类精确度,从而达到分类器参数的最优设置。表2不同参数的分类准确率核函数多项式径向基Sig moid由表2可以得到SVM最优的参数设置为:径向基核函数,惩罚因子C=100。3结束语脑肿瘤CT图像的计算机辅助诊断已成为目前的

20、研究热点。计算机辅助诊断的各个环节相辅相成,其中对病理的提取和模式分类显得尤为重要。从实验结果看,应用Ncut方法进行分割较为准确,特征提取较为完整,且设置最优的参数可以得到较为满意的分类精确度,可以帮助医生做辅助的诊断参考,具有一定的应用价值。针对脑CT肿瘤图像的诊断,提取特定区域的图像的特征、利用多核SVM(MKSVM6使其对分类效果更加明显仍然是目前的一个重大问题,需要进一步研究。参考文献:1Shi J,M alik J.No rm alized cuts and imag e segmen-tationCP r oc of IEEE Co nf Co mputer V isio n andPat tern R eco g nitio n.San Juan,Puerto R ico:IEEE,1997:731-737.2Shi J,M alik J.N o rmalized cut s and imag e segmen-tationJ.IEEE T