计算机科学2008Vol 135№12
基于动态自适应蚁群算法的MRI 图像分割3)
白 杨1 孙 跃1 王 君1 周文俊1 胡宁萍
(温州大学城市学院 温州325000) 1 (温州附二医 温州325010) 2
摘 要 MRI 图像分割在医学图像分析中具有极其重要的理论和应用价值。蚁群算法是一种具有离散性、并行性、
鲁棒性和模糊聚类能力的进化方法。对目标边界模糊、目标灰度不均匀及目标不连续等情况的图像(如医学图像) 分割, 蚁群算法是一个比较好的选择。本文针对基本蚁群算法容易出现早熟和停滞现象的特性, 提出了一种动态自适应蚁群算法, 通过自适应的初始聚类中心调整策略和动态更新局部信息素浓度, 使其收敛性和稳定性有一定的提高。实验证明改进的蚁群算法能够有效地分割MRI 图像。关键词 蚁群算法, 磁共振图像, 图像分割
2
Segmentation of MRI B ased on Dynamic and BAI Yang 1 SUN Yue 1 WAN G J un 1 HU 2(City College ,Wenzhou )
1
2
(The Second Affiliated Hospital of 325010)
Abstract Segmentation of MRI is analysis. Ant colony algorithm (ACA ) is a kind of discrete ,parallel and f uzzy clustering ability. To segment targets with blurry edges , intensity non 2(as medical images ) ,ACA approach is a good choice. A dynamic and a 2daptive is in accordance with the defect of early variety and stagnation. The contribution of the adaptive stratety of primary clustering center and a local updating for pheromone dynami 2cally. Using can segment image fast and accurately. Experimental results show that the improved ACA is an effective MRI segmentation K eyw ords Ant colony algorithm (ACA ) , Magnetic resonance image (MRI ) ,Image segmentation
可以在短时间内较完整地分割出图像, 适应能力强, 大大提高
了磁共振图像的分割效率。
蚁群算法(ant colony algorithm , ACA ) 是受到自然界中真实的蚁群集体行为的启发而提出的一种基于种群的模拟进化算法, 属于随机搜索算法。意大利学者Dorigo 等人在20世纪90年代初首先提出该算法时, 充分利用了蚁群搜索食物的过程与著名的旅行商问题之间的相似性, 通过人工模拟蚂蚁搜索食物的过程来求解TSP , 取得了较为理想的效果[5]。它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等智能算法之后的又一种应用与组合优化问题的启发式智能搜索算法。蚁群算法不仅能够智能搜索、全局优化, 而且具有鲁棒性、正反馈、分布式计算、易与其它算法相结合等特点[5,6]。同时由于蚁群算法的离散性和并行性特点对于数字图像处理非常适用[7], 它的聚类特性与图像的识别过程有相似之处, 因此本文所研究的内容在理论上是具有可行性的。
1 引言
磁共振成像与其他模式的成像技术相比, 多参数成像、任意截面成像、高软组织对比、无电离辐射等优势使其在临床上越来越受到欢迎, 并逐步占据了主导位置。颅脑是人体的重要器官, 也是肿瘤、炎症、多发性硬化症等疾病的好发部位。同时它具有控制和支配人的思维活动的中枢神经系统, 对脑部疾病的诊断和治疗要比对其他部位的诊断和治疗更为重要, 因此大部分的研究都是针对颅脑磁共振图像的[1]。由于颅脑磁共振图像中包括了脑皮层、皮下脂肪、颅骨、脑内膜、灰质、白质、脑脊液等多种组织, 而且每种组织形状不规则且相互重叠、覆盖。图像灰度分布不均匀, 不能简单地用图像的灰度直方图来区分不同的组织灰度分界, 因此用简单的阈值分割法在颅脑磁共振图像分割中是不适用的[2]。另一方面由于医学图像的特殊性, 对分割的精确度要求较高, 哪怕是小错误都可能造成无法挽回的后果。正是因为以上的原因颅脑磁共振图像分割比一般的图像分割更为困难和复杂, 所以尽管近年来国内外许多研究人员对磁共振图像分割提出和开发了多种分割算法, 如阈值法、基于边界的方法和基于区域的方法, 以及人工神经网络等方法[1,3,4], 也取得了一定的成绩, 但总体上, 还不能有一种算法能够对所有的磁共振图像分割取得满意结果。本文提出一种基于动态自适应的蚁群的MRI 分割方法, 较好地抑制了噪声影响, 磁共振图像的分割效果好,
2 基本蚁群算法
虽然蚂蚁没有视觉, 但能找到由蚁穴到食物源的最短路径。单个蚂蚁的行为极其简单, 但由这样的单个简单的个体所组成的蚁群群体却表现出极其复杂的行为, 能够完成复杂的任务, 不仅如此, 蚂蚁还能够适应环境的变化, 比如:在蚂蚁运动路线上突然出现障碍物时, 蚂蚁能够很快重新找到最优路径。蚂蚁是如何完成这些复杂的任务呢? 经过大量的研究
3) 基金项目:浙江省自然科学基金资助项目(No. Y104592) 准确测量脑部纵向变化的四维图像一致性分割算法; 浙江省教育厅资助项目
(20041032) 。白 杨 讲师, 硕士, 主要从事图像处理, 人工智能与模式识别研究。孙 跃 副教授, 研究方向:医学图像处理, 人工智能与模式
识别。
・226・
发现, 蚂蚁个体之间是通过一种称之为信息素的物质进行信息传递的[5], 从而能够相互协作, 完成复杂的任务, 蚂蚁之所以表现出复杂有序的行为, 个体之间的信息交流和相互协作起着重要的作用。蚂蚁在运动过程中, 能够在它所经过的路径上留下该物质, 并以此指导自己的运动方向, 蚂蚁倾向于朝着该物质强度高的方向移动。因此, 由大量蚂蚁组成的蚂蚁的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多, 则后者选择该路径的概率就越大。与此同时信息素会随着时间的推移逐渐挥发。路径上信息素的强弱就和路径的长短以及该路径上经过的蚂蚁多少有关系。蚂蚁之间就是通过这种信息的交流达到搜索食物的目的的。蚁群算法正是模拟真实的蚂蚁协同觅食的过程。
蚂蚁觅食的过程实际上也是一个不断聚类的过程, 食物就是聚类的中心[4]。将蚁群算法用于聚类问题中, 其主要思想是:
假设X ={X i |X i =(x i 1, x i 2, …, x im ) , i =1, 2, …, N}是进行分析聚类问题的数据集合。r 为聚类半径, ph ij (t ) 为t 时刻数据X i 到数据X j 的路径上的信息素浓度, d ij 为样本与聚类中心的加权欧氏距离, p 为加权因子, 可根据各分量在聚类中的影响程度而定。
则
d ij =‖P (X i -X i ) ‖=
=(x -jk ) (1设p h ij (0) r
(2) ph ij (0) =
0d r
, X i
归并到X j 的概率ph ij 为:
βa
j ∈S βa
is (t ) (3) ph ij =∑ph is (t ) η
s ∈S
聚类空间中进一步搜索, 这样就存在陷入局部极小的可能性,
不利于发现更好的解。原因在于信息素轨迹更新规则中不被选用的弧段上的信息素轨迹和选中的弧段上的信息素轨迹的差异会变得越来越大, 而蚂蚁始终沿着信息素轨迹高的弧段爬行, 这就导致当前不被选用的弧段今后被蚂蚁选择的概率变得越来越小, 进而使算法只会在某些局部最优解附近徘徊, 出现早熟和停滞现象。
针对这些缺点本文根据颅脑磁共振图像特点在初始聚类中心、信息素更新等方面加以改进。这样可以降低计算量和加快聚类过程, 并且有效地避免出现局部极值。
3. 1 初始聚类中心设置
蚁群行走是随机的和盲目的。假设图像大小为m 3n , 在聚类循环搜索过程中, 每个像素要和其他m 3n -1个像素进行距离和路径选择概率的计算, 系统必须经过多次循环才能完成聚类过程。整个过程搜索时间长, 。但如果一开始就对聚类中心加以引导, 效率, 。, 背景、脑脊液。, 得到近, 极大地缩短了搜索过程。
3. 2 动态信息素更新
由于蚁群算法自身的特点, 在聚类过程中, 蚂蚁容易选择信息素浓度较大的路径, 本算法从一开始就确定了近优的聚类中心, 蚂蚁虽然避免了陷入局部最优解, 但在某些时刻, 部分路径上的信息素浓度如果与其他路径上的信息素浓度偏差较大, 对聚类结果也会造成一定的不良影响。为此对信息素浓度进行有效的调整是很必要的[8]。
引入了基于均匀分布的信息素浓度均衡算子μ, 即
) =f (μ
d -c
(Q 为待定参数)
(7)
其他
其中, ηij (t ) 是启发式引导函数, 表征蚂蚁X i 转移至X j 的期望程度, 利用启发函数可反映像素之间的相似度, 启发函数越
αβ分别为像素聚类大, 像素归于相同聚类的概率就越大。、
过程中所积累的信息以及启发式引导函数对路径选择的影响因子。S ={X s |d sj ≤r , s =1, 2, …, j , j +1, …, N }, 为可行路径集合。
若p ij (t ) ≥p 0, 则X i 归并到X j 领域。设C j ={X k |d kj ≤r , k =1, 2, …, J }, C j 表示所有归并到X j 领域的数据集合。求出理想的聚类中心:
J
(4) c j =∑X k
J
k =1
其中, c ←min {Δp h 1, Δph 2, …, Δp h k }, d ←max {Δp h 1, Δph 2, …Δph k }, ≤μ, 该路径上新的信息素浓度为
Q
Q
n ew
(t ) =λ3p h old μ) ph ij ij (t ) -f (
(8)
信息素浓度均衡算子μ可以有效地避免蚂蚁过于集中的
路径上的信息素浓度增加过快的现象, 从而避免蚂蚁陷入局部极值, 增大了其它路径选择的可能性, 又能保持路径上较好的信息素浓度。
4 动态自适应蚁群MRI 分割方法
要分割图像, 就必须找出包括目标、背景、边界和噪声等内容。像素的灰度值是区别目标和背景的重要特征, 因此可以选择像素的灰度值作为聚类的重要特征, 另外在边界点和噪声点灰度一般会发生突变, 该点的梯度值即可作为一个重要的特征来区分边界点和背景以及目标区域[9]。上述两个特征反映了目标、背景、边界和噪声的特点, 这样我们可以把图像内每个像素看成是一只蚂蚁, 每只蚂蚁成为一个以灰度和梯度为特征的二维向量, 此时样本与聚类中心的加权欧氏距离d ij 为:d ij =p 1(x i 1-x j 1) 2+p 2(x i 2-x j 2) 2, 各聚类中心看作是蚂蚁所寻找的“食物源”集合的过程, 即数据样本的归类过程。
算法步骤如下:
(1) 对颅磁共振图像进行预处理, 去除大脑周围的颅骨和脂肪等组织。只保留大脑实质, 并取得图像的灰度直方图。
(2) 对图像的灰度直方图进行一维投影, 求得相对准确的
其中:X k ∈C j
随着蚂蚁的移动, 各路径上信息素的量发生变化, 经过一次循环, 按全局调整规则调整各路径上的信息素如下[5]:
(5) ph ij (t ) =ρph ij (t ) +Δp h ij
其中, ρ为信息素随时间的衰减系数, 一般取0. 5～0. 99左右, Δph ij 为本次循环中路径信息素的增量。
Δp h ij =∑Δph k ij
k =1N
(6)
Δp h k ij 表示第k 只蚂蚁在本次循环中留在路径中的信息素的量。
3 动态自适应蚁群算法
蚁群算法中搜索进行到一定的程度后, 所有蚂蚁个体发现的解趋于一致, 此时, 即使使用随机搜索策略, 也不可能在
・227・
聚类中心。
(3) 初始化蚁群算法各参量, N , r, β, λ, P 0, ph ij (0) =0, M , Q , 其中N 为蚂蚁个数, r 为聚类半径, 根据多次仿真实验结果, 确定参数α=1. 6; β=3; λ=0. 9; Q =100; P 0值为0. 8。M 为聚类中心的个数, 脑部MRI 包含的组织类别有:背景、脑白质、脑灰质和脑脊液, 则与之相对应的聚类中心的个数为4。即M 为4。
(4) 根据公式(1) 计算各蚂蚁到聚类中心的距离, 根据公式(2) 计算各路径上的信息素。再由式(3) 计算X i 归并到X j 的概率ph ij , 并判断p ij (t ) ≥p 0是否成立, 如果成立则X i 归并到X j 领域, 否则, 说明X i 不属于X j , 即不将X i 归并到X j 领域。
(5) 然后根据公式(4) 计算该类的聚类中心, 得到新的聚类中心后再根据公式(8) 计算信息素等值继续迭代, 直到聚类中心不再改变。
(6) 最后判断是否还有没分类的数据, 如果有, 则继续按以上方法归并到相应的类中, 没有, 则输出最终的聚类结果。
FCM 算法经过了21次迭代得到最优结果, 运行时间为66. 67s ; 应用动态自适应蚁群算法经过8次迭代得到最优结
果, 运行时间为17. 99s
。
5 实验结果
本文采用MA TL AB 进行仿真, 以一幅256×256人脑磁共振图像为例进行实验, 经网络[6]的方法和FCM 的方法分割, 实验经验。络[10]以及FCM :
, 图3、图4、图5为应、脑灰质和脑脊液图像; 图6～图8为应用的神经网络的方法分割的效果图; 图9～图11为应用了FCM 的方法得到的脑白质、脑灰质和脑脊液图像, 虽然在脑脊液的分割上没有太大的差异, 但是在脑白质和脑灰质的分割中差异是显而易见的。另外从三种算法的收敛速度上比较, 蚁群算法优势更加明显。应用神经网络算法经过28次迭代得到最优结果, 运行的时间为87. 43s ; 应用
・228・
结束语 实验结果表明, 与神经网络和FCM 等方法相比较, 该算法能够较准确地分割出颅磁共振图像各元素。动态自适应蚁群算法也更具有灵活性, 它能灵活地调整聚类过程, 可以更准确地识别结果, 运行速度比较快, 但缺点是一些参数要经过反复的试验才能确定。作为一种新的智能优化计算方法, 蚁群算法的许多理论还需要完善, 在磁共振图像分割的应用中才刚刚开始, 而且也只是局限于实验室阶段。希望随着研究的不断深入, 将会有更多的成果出现, 并能应用到实际的问题当中。
34
徐海祥, 喻莉, 朱光喜, 等. 基于支持向量机的磁共振脑组织图像分割[J].中国图像图形学报, 2005,10(10) :12754～1280
Suri J S ,Singh S ,Reden L. Computer Vision and Pattern Recogni 2tion Techniques for 22D and 32D MR Cortical Segmention (Part I ) :A State 2of 2t he 2Art [C ]. Pattern Analysis &Applications,2002,55
参考文献
12
汪红志, 聂生东. ]. (5) Chiu Ming 2J 2Kai 2Hasiang ,et al. Tis 2sue Analysis of MRI for Human Motor
Response :AnCombining Artificial Neural Network and Fuzzy C Means[C].Journal of Digital Imaging ,2004,1(5) :38～47
Dorigo M C. Ant :Asurvey[C].,344～278
6,Liu time series data for seg 2
by [C]. European Jour 2,2006,173:921～937
R K ,Ramakrishnan S. A hybrid approach for fea 2
subset selection using neural networks and ant colony optimi 2zation[C ].Expert Systems wit h Applications , 2006, 121:134～146
8杨瑞. 基于蚁群算法的模糊小波网络控制策略及其应用研究[D ]:
[西安理工大学博士论文].2005
9毕晓君. 基于智能信息技术的纹理图像识别与生成研究[D ]:[哈
尔滨工程大学博士论文].2006
10黄永锋, 赵俊, 庄天戈. 遗传神经网络在颅磁共振图像分割中的应
用[J].上海交通大学学报,2004,38(5) :771～774
(上接第210页)
7
Dhenain M , Ruffins SW , J acobs RE. Three 2dimensional digital mouse atlas using high resolution MRI. Developmental Biology , 2001, 232(2) :458～470
Park S Y , Subbarao M. A multiview 3D modeling system based on stereo vision techniques. Machine Vision and Applications , 2005, 16:148～156Y 1lmaz U , M ülayim A , Atalay V. Reconst ruction of Three Di 2mensional Models from Real Images. In :Proceedings of t he First International Symposium on 3D Data Processing Visualization and Transmission (3DPV T. 02) ,2002
Sainz M , Pajarola R , Mercade A. A Simple Approach for Point 2Based Object Capturing and Rendering. IEEE Computer Graphics and Applications ,J uly 2August 2004. 24～33
刘钢, 王章野, 彭群. 自由拍摄视点下的可见外壳生成算法. 计算机辅助设计与图形学学报, 2004,16(11) :1501～1505
Montenegro A A , Carvalho P C P , Velho L , Gattass M. Space carving wit h a hand 2held camera. In :Proceedings of t he XVII Brazilian Symposium on Computer Graphics and Image Processing (SIB GRAPI ’04) , 2004. 396～403
Esteban C H , Schmitt F. Silhouette and stereo fusion for 3D ob 2ject modeling. Computer Vision and Image Understanding , 2004, 96:367～392
Sarti A , Tubaro S. Image based multiresolution implicit object modeling. EU RASIP J. Appl. Signal Process , 2002, 10:1053～1066
Brand M , Kang K , Cooper D B. Algebraic solution for t he visual hull. In :Proceedings of t he 2004IEEE Computer Society Confer 2ence on Computer Vision and Pattern Recognition , CVPR 2004. 133～135
Yang Y K , Lee J , K im S K , K im C H. Adaptive Space Carving wit h Texture Mapping. L NCS 3482, 2005. 1129～1138
De L uca L , Veron P , Florenzano M. Reverse engineering of ar 2chitectural buildings based on a hybrid modeling approach. Com 2puters &Graphics , 2006, 30:160～176
8
9
10
1112
13
14
15
1617
18Digital Michelangelo project. http ://graphics. stanford. edu/da 2
ta/mich/
19Levoy M , Pulli K , Curless B , et al. The digital Michelangelo
Project :3D scanning of large statues. In Siggraph 2000, 2000. 131～144
20Stanford digital Formae Urbis Romae project. http ://formaur 2
bis. stanford. edu/index. ht ml
21Mueller P , Vereenooghe T , Vergauwen M , Van G ool L , Waelk 2
ens M. Photo 2realistic and detailed 3D modeling :t he Antonine nymphaeum at Sagalassos (Turkey ) . Computer Applications and Quantitative Met hods in Archaeology (CAA ) :Beyond t he arti 2fact 2Digital interpretation of t he past. [http ://www. vision. ee. et hz. ch/～pmueller/document s/caa04_pmueller. pdf , accessed Mar. 2005]
22魏迎梅, 栾悉道. 虚拟现实技术. 电子工业出版社,2005
23Lian Qin , Li Di 2Chen , Tang Y i 2Ping , Zhang Y ong 2Rui. Comput 2
er modeling approach for a novel internal architecture of artificial bone. CAD Computer Aided Design , 2006, 38(5) :507～51424Sun W , Starly B , Nam J , Darling A. Bio 2CAD modeling and it s
applications in computer 2aided tissue engineering. Computer 2Ai 2ded Design , 2005, 37:1097～1114
25Santos D M C , Pertence A E M , Campos H B , Cetlin P R. The
development of 3D models t hrough rapid prototyping concept s. Journal of Materials Processing Technology , 2005, 169:1～426Lewis A C , Gelt macher A B. Image 2based modeling of t he re 2
sponse of experimental 3D microstructures to mechanical loading. Scripta Materialia , 2006,55(1) :81～85
27Makkonen T , Nevala K , Heikkil R. A 3D model based control
of an excavator. Automation in Construction , 2006, 15(5) :571～577
28Qin S F , Harrison R , West A A , Wright D K. Development of a
novel 3D simulation modelling system for distributed manufactur 2ing. Computers in Industry , 2004,54:69～81
29邱建雄, 赵跃龙, 杨瑞元. 基于图像的建模和绘制技术综述. 小
型微型计算机系统, 2004,25(5) :908～912
・229・
计算机科学2008Vol 135№12
基于动态自适应蚁群算法的MRI 图像分割3)
白 杨1 孙 跃1 王 君1 周文俊1 胡宁萍
(温州大学城市学院 温州325000) 1 (温州附二医 温州325010) 2
摘 要 MRI 图像分割在医学图像分析中具有极其重要的理论和应用价值。蚁群算法是一种具有离散性、并行性、
鲁棒性和模糊聚类能力的进化方法。对目标边界模糊、目标灰度不均匀及目标不连续等情况的图像(如医学图像) 分割, 蚁群算法是一个比较好的选择。本文针对基本蚁群算法容易出现早熟和停滞现象的特性, 提出了一种动态自适应蚁群算法, 通过自适应的初始聚类中心调整策略和动态更新局部信息素浓度, 使其收敛性和稳定性有一定的提高。实验证明改进的蚁群算法能够有效地分割MRI 图像。关键词 蚁群算法, 磁共振图像, 图像分割
2
Segmentation of MRI B ased on Dynamic and BAI Yang 1 SUN Yue 1 WAN G J un 1 HU 2(City College ,Wenzhou )
1
2
(The Second Affiliated Hospital of 325010)
Abstract Segmentation of MRI is analysis. Ant colony algorithm (ACA ) is a kind of discrete ,parallel and f uzzy clustering ability. To segment targets with blurry edges , intensity non 2(as medical images ) ,ACA approach is a good choice. A dynamic and a 2daptive is in accordance with the defect of early variety and stagnation. The contribution of the adaptive stratety of primary clustering center and a local updating for pheromone dynami 2cally. Using can segment image fast and accurately. Experimental results show that the improved ACA is an effective MRI segmentation K eyw ords Ant colony algorithm (ACA ) , Magnetic resonance image (MRI ) ,Image segmentation
可以在短时间内较完整地分割出图像, 适应能力强, 大大提高
了磁共振图像的分割效率。
蚁群算法(ant colony algorithm , ACA ) 是受到自然界中真实的蚁群集体行为的启发而提出的一种基于种群的模拟进化算法, 属于随机搜索算法。意大利学者Dorigo 等人在20世纪90年代初首先提出该算法时, 充分利用了蚁群搜索食物的过程与著名的旅行商问题之间的相似性, 通过人工模拟蚂蚁搜索食物的过程来求解TSP , 取得了较为理想的效果[5]。它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等智能算法之后的又一种应用与组合优化问题的启发式智能搜索算法。蚁群算法不仅能够智能搜索、全局优化, 而且具有鲁棒性、正反馈、分布式计算、易与其它算法相结合等特点[5,6]。同时由于蚁群算法的离散性和并行性特点对于数字图像处理非常适用[7], 它的聚类特性与图像的识别过程有相似之处, 因此本文所研究的内容在理论上是具有可行性的。
1 引言
磁共振成像与其他模式的成像技术相比, 多参数成像、任意截面成像、高软组织对比、无电离辐射等优势使其在临床上越来越受到欢迎, 并逐步占据了主导位置。颅脑是人体的重要器官, 也是肿瘤、炎症、多发性硬化症等疾病的好发部位。同时它具有控制和支配人的思维活动的中枢神经系统, 对脑部疾病的诊断和治疗要比对其他部位的诊断和治疗更为重要, 因此大部分的研究都是针对颅脑磁共振图像的[1]。由于颅脑磁共振图像中包括了脑皮层、皮下脂肪、颅骨、脑内膜、灰质、白质、脑脊液等多种组织, 而且每种组织形状不规则且相互重叠、覆盖。图像灰度分布不均匀, 不能简单地用图像的灰度直方图来区分不同的组织灰度分界, 因此用简单的阈值分割法在颅脑磁共振图像分割中是不适用的[2]。另一方面由于医学图像的特殊性, 对分割的精确度要求较高, 哪怕是小错误都可能造成无法挽回的后果。正是因为以上的原因颅脑磁共振图像分割比一般的图像分割更为困难和复杂, 所以尽管近年来国内外许多研究人员对磁共振图像分割提出和开发了多种分割算法, 如阈值法、基于边界的方法和基于区域的方法, 以及人工神经网络等方法[1,3,4], 也取得了一定的成绩, 但总体上, 还不能有一种算法能够对所有的磁共振图像分割取得满意结果。本文提出一种基于动态自适应的蚁群的MRI 分割方法, 较好地抑制了噪声影响, 磁共振图像的分割效果好,
2 基本蚁群算法
虽然蚂蚁没有视觉, 但能找到由蚁穴到食物源的最短路径。单个蚂蚁的行为极其简单, 但由这样的单个简单的个体所组成的蚁群群体却表现出极其复杂的行为, 能够完成复杂的任务, 不仅如此, 蚂蚁还能够适应环境的变化, 比如:在蚂蚁运动路线上突然出现障碍物时, 蚂蚁能够很快重新找到最优路径。蚂蚁是如何完成这些复杂的任务呢? 经过大量的研究
3) 基金项目:浙江省自然科学基金资助项目(No. Y104592) 准确测量脑部纵向变化的四维图像一致性分割算法; 浙江省教育厅资助项目
(20041032) 。白 杨 讲师, 硕士, 主要从事图像处理, 人工智能与模式识别研究。孙 跃 副教授, 研究方向:医学图像处理, 人工智能与模式
识别。
・226・
发现, 蚂蚁个体之间是通过一种称之为信息素的物质进行信息传递的[5], 从而能够相互协作, 完成复杂的任务, 蚂蚁之所以表现出复杂有序的行为, 个体之间的信息交流和相互协作起着重要的作用。蚂蚁在运动过程中, 能够在它所经过的路径上留下该物质, 并以此指导自己的运动方向, 蚂蚁倾向于朝着该物质强度高的方向移动。因此, 由大量蚂蚁组成的蚂蚁的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多, 则后者选择该路径的概率就越大。与此同时信息素会随着时间的推移逐渐挥发。路径上信息素的强弱就和路径的长短以及该路径上经过的蚂蚁多少有关系。蚂蚁之间就是通过这种信息的交流达到搜索食物的目的的。蚁群算法正是模拟真实的蚂蚁协同觅食的过程。
蚂蚁觅食的过程实际上也是一个不断聚类的过程, 食物就是聚类的中心[4]。将蚁群算法用于聚类问题中, 其主要思想是:
假设X ={X i |X i =(x i 1, x i 2, …, x im ) , i =1, 2, …, N}是进行分析聚类问题的数据集合。r 为聚类半径, ph ij (t ) 为t 时刻数据X i 到数据X j 的路径上的信息素浓度, d ij 为样本与聚类中心的加权欧氏距离, p 为加权因子, 可根据各分量在聚类中的影响程度而定。
则
d ij =‖P (X i -X i ) ‖=
=(x -jk ) (1设p h ij (0) r
(2) ph ij (0) =
0d r
, X i
归并到X j 的概率ph ij 为:
βa
j ∈S βa
is (t ) (3) ph ij =∑ph is (t ) η
s ∈S
聚类空间中进一步搜索, 这样就存在陷入局部极小的可能性,
不利于发现更好的解。原因在于信息素轨迹更新规则中不被选用的弧段上的信息素轨迹和选中的弧段上的信息素轨迹的差异会变得越来越大, 而蚂蚁始终沿着信息素轨迹高的弧段爬行, 这就导致当前不被选用的弧段今后被蚂蚁选择的概率变得越来越小, 进而使算法只会在某些局部最优解附近徘徊, 出现早熟和停滞现象。
针对这些缺点本文根据颅脑磁共振图像特点在初始聚类中心、信息素更新等方面加以改进。这样可以降低计算量和加快聚类过程, 并且有效地避免出现局部极值。
3. 1 初始聚类中心设置
蚁群行走是随机的和盲目的。假设图像大小为m 3n , 在聚类循环搜索过程中, 每个像素要和其他m 3n -1个像素进行距离和路径选择概率的计算, 系统必须经过多次循环才能完成聚类过程。整个过程搜索时间长, 。但如果一开始就对聚类中心加以引导, 效率, 。, 背景、脑脊液。, 得到近, 极大地缩短了搜索过程。
3. 2 动态信息素更新
由于蚁群算法自身的特点, 在聚类过程中, 蚂蚁容易选择信息素浓度较大的路径, 本算法从一开始就确定了近优的聚类中心, 蚂蚁虽然避免了陷入局部最优解, 但在某些时刻, 部分路径上的信息素浓度如果与其他路径上的信息素浓度偏差较大, 对聚类结果也会造成一定的不良影响。为此对信息素浓度进行有效的调整是很必要的[8]。
引入了基于均匀分布的信息素浓度均衡算子μ, 即
) =f (μ
d -c
(Q 为待定参数)
(7)
其他
其中, ηij (t ) 是启发式引导函数, 表征蚂蚁X i 转移至X j 的期望程度, 利用启发函数可反映像素之间的相似度, 启发函数越
αβ分别为像素聚类大, 像素归于相同聚类的概率就越大。、
过程中所积累的信息以及启发式引导函数对路径选择的影响因子。S ={X s |d sj ≤r , s =1, 2, …, j , j +1, …, N }, 为可行路径集合。
若p ij (t ) ≥p 0, 则X i 归并到X j 领域。设C j ={X k |d kj ≤r , k =1, 2, …, J }, C j 表示所有归并到X j 领域的数据集合。求出理想的聚类中心:
J
(4) c j =∑X k
J
k =1
其中, c ←min {Δp h 1, Δph 2, …, Δp h k }, d ←max {Δp h 1, Δph 2, …Δph k }, ≤μ, 该路径上新的信息素浓度为
Q
Q
n ew
(t ) =λ3p h old μ) ph ij ij (t ) -f (
(8)
信息素浓度均衡算子μ可以有效地避免蚂蚁过于集中的
路径上的信息素浓度增加过快的现象, 从而避免蚂蚁陷入局部极值, 增大了其它路径选择的可能性, 又能保持路径上较好的信息素浓度。
4 动态自适应蚁群MRI 分割方法
要分割图像, 就必须找出包括目标、背景、边界和噪声等内容。像素的灰度值是区别目标和背景的重要特征, 因此可以选择像素的灰度值作为聚类的重要特征, 另外在边界点和噪声点灰度一般会发生突变, 该点的梯度值即可作为一个重要的特征来区分边界点和背景以及目标区域[9]。上述两个特征反映了目标、背景、边界和噪声的特点, 这样我们可以把图像内每个像素看成是一只蚂蚁, 每只蚂蚁成为一个以灰度和梯度为特征的二维向量, 此时样本与聚类中心的加权欧氏距离d ij 为:d ij =p 1(x i 1-x j 1) 2+p 2(x i 2-x j 2) 2, 各聚类中心看作是蚂蚁所寻找的“食物源”集合的过程, 即数据样本的归类过程。
算法步骤如下:
(1) 对颅磁共振图像进行预处理, 去除大脑周围的颅骨和脂肪等组织。只保留大脑实质, 并取得图像的灰度直方图。
(2) 对图像的灰度直方图进行一维投影, 求得相对准确的
其中:X k ∈C j
随着蚂蚁的移动, 各路径上信息素的量发生变化, 经过一次循环, 按全局调整规则调整各路径上的信息素如下[5]:
(5) ph ij (t ) =ρph ij (t ) +Δp h ij
其中, ρ为信息素随时间的衰减系数, 一般取0. 5～0. 99左右, Δph ij 为本次循环中路径信息素的增量。
Δp h ij =∑Δph k ij
k =1N
(6)
Δp h k ij 表示第k 只蚂蚁在本次循环中留在路径中的信息素的量。
3 动态自适应蚁群算法
蚁群算法中搜索进行到一定的程度后, 所有蚂蚁个体发现的解趋于一致, 此时, 即使使用随机搜索策略, 也不可能在
・227・
聚类中心。
(3) 初始化蚁群算法各参量, N , r, β, λ, P 0, ph ij (0) =0, M , Q , 其中N 为蚂蚁个数, r 为聚类半径, 根据多次仿真实验结果, 确定参数α=1. 6; β=3; λ=0. 9; Q =100; P 0值为0. 8。M 为聚类中心的个数, 脑部MRI 包含的组织类别有:背景、脑白质、脑灰质和脑脊液, 则与之相对应的聚类中心的个数为4。即M 为4。
(4) 根据公式(1) 计算各蚂蚁到聚类中心的距离, 根据公式(2) 计算各路径上的信息素。再由式(3) 计算X i 归并到X j 的概率ph ij , 并判断p ij (t ) ≥p 0是否成立, 如果成立则X i 归并到X j 领域, 否则, 说明X i 不属于X j , 即不将X i 归并到X j 领域。
(5) 然后根据公式(4) 计算该类的聚类中心, 得到新的聚类中心后再根据公式(8) 计算信息素等值继续迭代, 直到聚类中心不再改变。
(6) 最后判断是否还有没分类的数据, 如果有, 则继续按以上方法归并到相应的类中, 没有, 则输出最终的聚类结果。
FCM 算法经过了21次迭代得到最优结果, 运行时间为66. 67s ; 应用动态自适应蚁群算法经过8次迭代得到最优结
果, 运行时间为17. 99s
。
5 实验结果
本文采用MA TL AB 进行仿真, 以一幅256×256人脑磁共振图像为例进行实验, 经网络[6]的方法和FCM 的方法分割, 实验经验。络[10]以及FCM :
, 图3、图4、图5为应、脑灰质和脑脊液图像; 图6～图8为应用的神经网络的方法分割的效果图; 图9～图11为应用了FCM 的方法得到的脑白质、脑灰质和脑脊液图像, 虽然在脑脊液的分割上没有太大的差异, 但是在脑白质和脑灰质的分割中差异是显而易见的。另外从三种算法的收敛速度上比较, 蚁群算法优势更加明显。应用神经网络算法经过28次迭代得到最优结果, 运行的时间为87. 43s ; 应用
・228・
结束语 实验结果表明, 与神经网络和FCM 等方法相比较, 该算法能够较准确地分割出颅磁共振图像各元素。动态自适应蚁群算法也更具有灵活性, 它能灵活地调整聚类过程, 可以更准确地识别结果, 运行速度比较快, 但缺点是一些参数要经过反复的试验才能确定。作为一种新的智能优化计算方法, 蚁群算法的许多理论还需要完善, 在磁共振图像分割的应用中才刚刚开始, 而且也只是局限于实验室阶段。希望随着研究的不断深入, 将会有更多的成果出现, 并能应用到实际的问题当中。
34
徐海祥, 喻莉, 朱光喜, 等. 基于支持向量机的磁共振脑组织图像分割[J].中国图像图形学报, 2005,10(10) :12754～1280
Suri J S ,Singh S ,Reden L. Computer Vision and Pattern Recogni 2tion Techniques for 22D and 32D MR Cortical Segmention (Part I ) :A State 2of 2t he 2Art [C ]. Pattern Analysis &Applications,2002,55
参考文献
12
汪红志, 聂生东. ]. (5) Chiu Ming 2J 2Kai 2Hasiang ,et al. Tis 2sue Analysis of MRI for Human Motor
Response :AnCombining Artificial Neural Network and Fuzzy C Means[C].Journal of Digital Imaging ,2004,1(5) :38～47
Dorigo M C. Ant :Asurvey[C].,344～278
6,Liu time series data for seg 2
by [C]. European Jour 2,2006,173:921～937
R K ,Ramakrishnan S. A hybrid approach for fea 2
subset selection using neural networks and ant colony optimi 2zation[C ].Expert Systems wit h Applications , 2006, 121:134～146
8杨瑞. 基于蚁群算法的模糊小波网络控制策略及其应用研究[D ]:
[西安理工大学博士论文].2005
9毕晓君. 基于智能信息技术的纹理图像识别与生成研究[D ]:[哈
尔滨工程大学博士论文].2006
10黄永锋, 赵俊, 庄天戈. 遗传神经网络在颅磁共振图像分割中的应
用[J].上海交通大学学报,2004,38(5) :771～774
(上接第210页)
7
Dhenain M , Ruffins SW , J acobs RE. Three 2dimensional digital mouse atlas using high resolution MRI. Developmental Biology , 2001, 232(2) :458～470
Park S Y , Subbarao M. A multiview 3D modeling system based on stereo vision techniques. Machine Vision and Applications , 2005, 16:148～156Y 1lmaz U , M ülayim A , Atalay V. Reconst ruction of Three Di 2mensional Models from Real Images. In :Proceedings of t he First International Symposium on 3D Data Processing Visualization and Transmission (3DPV T. 02) ,2002
Sainz M , Pajarola R , Mercade A. A Simple Approach for Point 2Based Object Capturing and Rendering. IEEE Computer Graphics and Applications ,J uly 2August 2004. 24～33
刘钢, 王章野, 彭群. 自由拍摄视点下的可见外壳生成算法. 计算机辅助设计与图形学学报, 2004,16(11) :1501～1505
Montenegro A A , Carvalho P C P , Velho L , Gattass M. Space carving wit h a hand 2held camera. In :Proceedings of t he XVII Brazilian Symposium on Computer Graphics and Image Processing (SIB GRAPI ’04) , 2004. 396～403
Esteban C H , Schmitt F. Silhouette and stereo fusion for 3D ob 2ject modeling. Computer Vision and Image Understanding , 2004, 96:367～392
Sarti A , Tubaro S. Image based multiresolution implicit object modeling. EU RASIP J. Appl. Signal Process , 2002, 10:1053～1066
Brand M , Kang K , Cooper D B. Algebraic solution for t he visual hull. In :Proceedings of t he 2004IEEE Computer Society Confer 2ence on Computer Vision and Pattern Recognition , CVPR 2004. 133～135
Yang Y K , Lee J , K im S K , K im C H. Adaptive Space Carving wit h Texture Mapping. L NCS 3482, 2005. 1129～1138
De L uca L , Veron P , Florenzano M. Reverse engineering of ar 2chitectural buildings based on a hybrid modeling approach. Com 2puters &Graphics , 2006, 30:160～176
8
9
10
1112
13
14
15
1617
18Digital Michelangelo project. http ://graphics. stanford. edu/da 2
ta/mich/
19Levoy M , Pulli K , Curless B , et al. The digital Michelangelo
Project :3D scanning of large statues. In Siggraph 2000, 2000. 131～144
20Stanford digital Formae Urbis Romae project. http ://formaur 2
bis. stanford. edu/index. ht ml
21Mueller P , Vereenooghe T , Vergauwen M , Van G ool L , Waelk 2
ens M. Photo 2realistic and detailed 3D modeling :t he Antonine nymphaeum at Sagalassos (Turkey ) . Computer Applications and Quantitative Met hods in Archaeology (CAA ) :Beyond t he arti 2fact 2Digital interpretation of t he past. [http ://www. vision. ee. et hz. ch/～pmueller/document s/caa04_pmueller. pdf , accessed Mar. 2005]
22魏迎梅, 栾悉道. 虚拟现实技术. 电子工业出版社,2005
23Lian Qin , Li Di 2Chen , Tang Y i 2Ping , Zhang Y ong 2Rui. Comput 2
er modeling approach for a novel internal architecture of artificial bone. CAD Computer Aided Design , 2006, 38(5) :507～51424Sun W , Starly B , Nam J , Darling A. Bio 2CAD modeling and it s
applications in computer 2aided tissue engineering. Computer 2Ai 2ded Design , 2005, 37:1097～1114
25Santos D M C , Pertence A E M , Campos H B , Cetlin P R. The
development of 3D models t hrough rapid prototyping concept s. Journal of Materials Processing Technology , 2005, 169:1～426Lewis A C , Gelt macher A B. Image 2based modeling of t he re 2
sponse of experimental 3D microstructures to mechanical loading. Scripta Materialia , 2006,55(1) :81～85
27Makkonen T , Nevala K , Heikkil R. A 3D model based control
of an excavator. Automation in Construction , 2006, 15(5) :571～577
28Qin S F , Harrison R , West A A , Wright D K. Development of a
novel 3D simulation modelling system for distributed manufactur 2ing. Computers in Industry , 2004,54:69～81
29邱建雄, 赵跃龙, 杨瑞元. 基于图像的建模和绘制技术综述. 小
型微型计算机系统, 2004,25(5) :908～912
・229・