第2卷第4期 智能系统学报 Vol.2№4 2007年8月 CAAI Transactions on Intelligent Systems Aug.2007 一种基于MAS的自适应图像分割方法 陈小波,程显毅 (江苏大学计算机科学与通信工程学院,江苏镇江212013) 摘要:复杂图像的全自动分割是极具挑战性的问题.提出了一种基于MAS的自适应图像分割方法.通过属性和行 为描述Agent个体,通过合作竞争描述了Agent间的交互.MAS系统在Agent反复自适应过程中达到平衡,同时完 成图像分割.通过分割复杂的医学图像证实了该方法的有效性,MAS在图像分割领域具有应用价值, 关键词:MAS:自适应;图像分割 中图分类号:TP391.4文献标识码:A文章编号:1673-4785(2007)04-008006 An ada ptive image segmentation technique based on multi Agent system CHEN Xiao-bo,CHENG Xianyi (School of Computer Science Telecommunication Engineering,Jiangsu University,Zhenjiang 212013,China) Abstract:The automatic segmentation of complex images is a challenging issue.A novel approach was pro- posed to segment images adaptively based on multi-Agent system.Individual agents were described with their attributes and behaviors.The interaction between Agents was described by cooperation and competi- tion.Finally,the MAS reached a balanced state after a process of recursive self-adaptation and the image was segmented.Experiments with complex medical images show that the MAS approach is suitable for use in image segmentation. Key words MAS;self-adaptive;image segmentation 图像分割是特征提取、对象分类的基础,因而在 故在图像处理领域得到了大量应用并取得了很好的 机器视觉模式识别、医学图像处理等领域得到大量 效果.Liu等)利用反应式智能体设计了自动分割 应用.由于分割对象特征不同,至今己开发出很多算 图像的MAS系统,并成功分割了大脑CT图像.文 法.传统的分割算法,如基于各种算子的方法,仅适 献[4]设计了一个检测图像对称轴的MAS系统.自 合于简单、单一物体的分割.针对医学图像、遥感图 然界中存在大量均衡系统,这些系统中的个体虽然 像、自然景观等复杂、多目标图像等则难以分割山, 可能有很大差异,但却得以彼此共存、发展而不是消 近年来,多智能体系统(multi-Agent system, 亡,是由于不断的彼此适应而形成的一种稳定有序 MAS)理论得到了很大发展,MAS是人工智能和计 格局.受此启发,本文设计了一种MAS用于图像分 算机网络的结合.个体Agent是一种具有感知能 割.初始无差异的Agent群体随机分布在图像环境 力、问题求解能力和通信能力的计算系统.一般而 中,由于各自所处的环境不同而具有了不同的目标, 言,它应具有如下特征:反应性、预动性和社会行为 繁殖和移动导致了Agent的扩散,目标和感知的差 能力).MAS则是个体Agent的有机组织,可以求 异导致了Agent能力的不同,Agent间彼此争夺空 解单个Agent无法解决的问题.MAS包括3个要 间导致竞争,为扩张势力而导致合作和目标合并,系 素:Agent个体、Agent组织和Agent交互2).正是 统反复演化最终达到平衡,同时完成图像分割: 由于MAS更适合处理复杂、分布式和并行的任务, 1MAS的体系结构 收稿日期:20060605. MAS是一个会根据其所处的环境而自动调整 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 4 期 智 能 系 统 学 报 Vol. 2 №. 4 2007 年 8 月 CAAI Transactions on Intelligent Systems Aug. 2007 一种基于 MAS 的自适应图像分割方法 陈小波 ,程显毅 (江苏大学 计算机科学与通信工程学院 ,江苏 镇江 212013) 摘 要 :复杂图像的全自动分割是极具挑战性的问题. 提出了一种基于 MAS 的自适应图像分割方法. 通过属性和行 为描述 Agent 个体 ,通过合作竞争描述了 Agent 间的交互. MAS 系统在 Agent 反复自适应过程中达到平衡 ,同时完 成图像分割. 通过分割复杂的医学图像证实了该方法的有效性 ,MAS 在图像分割领域具有应用价值. 关键词 :MAS ;自适应 ;图像分割 中图分类号 : TP391. 4 文献标识码 :A 文章编号 :167324785 (2007) 0420080206 An adaptive image segmentation technique based on multi2Agent system CH EN Xiao2bo , CH EN G Xian2yi (School of Computer Science & Telecommunication Engineering , Jiangsu University ,Zhenjiang 212013 , China) Abstract :The automatic segmentation of complex images is a challenging issue. A novel approach was pro2 posed to segment images adaptively based on multi2Agent system. Individual agents were described wit h t heir attributes and behaviors. The interaction between Agents was described by cooperation and competi2 tion. Finally , the MAS reached a balanced state after a process of recursive self2adaptation and t he image was segmented. Experiments wit h complex medical images show that t he MAS approach is suitable for use in image segmentation. Keywords :MAS;self2adaptive ;image segmentation 收稿日期 :2006206205. 图像分割是特征提取、对象分类的基础 ,因而在 机器视觉、模式识别、医学图像处理等领域得到大量 应用. 由于分割对象特征不同 ,至今已开发出很多算 法. 传统的分割算法 ,如基于各种算子的方法 ,仅适 合于简单、单一物体的分割. 针对医学图像、遥感图 像、自然景观等复杂、多目标图像等则难以分割[1 ] . 近年来 ,多智能体系统 ( multi2Agent system , MAS) 理论得到了很大发展 ,MAS 是人工智能和计 算机网络的结合. 个体 Agent 是一种具有感知能 力、问题求解能力和通信能力的计算系统. 一般而 言 ,它应具有如下特征 :反应性、预动性和社会行为 能力[ 1 ] . MAS 则是个体 Agent 的有机组织 ,可以求 解单个 Agent 无法解决的问题. MAS 包括 3 个要 素 :Agent 个体、Agent 组织和 Agent 交互[2 ] . 正是 由于 MAS 更适合处理复杂、分布式和并行的任务 , 故在图像处理领域得到了大量应用并取得了很好的 效果. Liu 等[ 3 ] 利用反应式智能体设计了自动分割 图像的 MAS 系统 ,并成功分割了大脑 CT 图像. 文 献[4 ]设计了一个检测图像对称轴的 MAS 系统. 自 然界中存在大量均衡系统 ,这些系统中的个体虽然 可能有很大差异 ,但却得以彼此共存、发展而不是消 亡 ,是由于不断的彼此适应而形成的一种稳定有序 格局. 受此启发 ,本文设计了一种 MAS 用于图像分 割. 初始无差异的 Agent 群体随机分布在图像环境 中 ,由于各自所处的环境不同而具有了不同的目标 , 繁殖和移动导致了 Agent 的扩散 ,目标和感知的差 异导致了 Agent 能力的不同 ,Agent 间彼此争夺空 间导致竞争 ,为扩张势力而导致合作和目标合并 ,系 统反复演化最终达到平衡 ,同时完成图像分割. 1 MAS 的体系结构 MAS 是一个会根据其所处的环境而自动调整
第4期 陈小波,等:一种基于MAS的自适应图像分割方法 ·81 其结构的开放系统.根据Guessoum!s1,这样的 3)感知sense:设detector当前位于图像中的i MAS应该由如下3个部分组成 像素处,感知半径为r,则所有满足Ii-j‖<r(与i 与问题/领域相关的Agent.这是自适应MAS 相距不超过)的像素j都可被detector感知,并且 的基础,这些Agent可以有不同的类型、目标和行 感知sense用r内所有像素的均值和方差表示, 为,它们存在于环境中并感知环境的局部信息,由此 sense,=(MD),更复杂的感知还包括灰度直方 进行决策,作出一定的行为 图、纹理特征等」 Agent间关系.个体Agent的能力有限,必须和 4)能力ability:这是detector的核心,反映de 其他Agent共享信息和协作,以完成更复杂的任 tector对当前环境的适应程度,随着其目标和局部 务.Agents间由此形成了一定的依赖关系,这可以 感知环境的变化而变化,定义能力ability:= 用MAS组织结构来表示,这种结构根据需要而产 1/1 goal:-sense),是目标与感知差异的减函数. 生和瓦解,是一种动态结构 能力类似于遗传算法(GA)中的适应度函数,但GA 管理Agent..由于Agent的局部性,无法把握问 中的适应度函数一般是全局且是静态的,而本文的 题求解的整体过程,虽然Agent完全自适应也可以 能力则是局限于每个Agent且会因其选择不同的 用于问题的求解,这正如文献[3]的做法,但这种系 行为、具有不同的目标、感知不同的环境而变化,这 统的鲁棒性不强,无法控制系统的演化方向,尤其是 更符合自然界规律,全局的行为是通过个体通过局 无法获得关于系统更高层的信息.因此,引入的管理 部的自适应而实现的,这种通过个体局部自适应而 Agent用于对系统的当前状态进行全局的监控,根 涌现的智能求解复杂问题正是Agent计算的核心, 据高层知识对问题Agent进行指导和约束,加速求 这正如文献[7]所述 解过程,约束求解方向. 5)类别C:用来表示该detector当前所属类别, 根据上面3条原则,设计用于图像分割的自适 作为图像最终分割的依据。 应MAS结构如图1所示(其中monitor表示管理 6)繁殖与移动向量UQ):用于描述detector Agent,detector表示问题Agent) 在各个方向上繁殖和移动的权重,记录detector的 ©monitor 历史信息,即 U(H刊=[n,b,B,,h,a], QJ)=[q,平,p,…,9=] 图像 式中:w=1,9=1,w∈0,11,g∈0,1], detector 分别为方向,j上的繁殖权重与移动权重.常见的 图1MAS结构 繁殖与移动方向可采用像素的8-邻域,此时n=8. Fig 1 The structure of MAS 7)步数step:用以刻画detector的年龄,初始时 step=0,detector每执行一次移动行为,则其step 2 图像特征检测Agent 将增1. 图像特征检测Agent(问题Agent),简称detec- detector的行为包括: tor,主要用于搜索与自己目标相同的图像区域,它 1)移动(moving):即detector由一个位置迁移 利用典型的反应式Agent结构o(下文所述下标i 到另一个位置,移动方向由其移动向量Q决定,即 均表示Agent的标识) 向Q最大的方向移动.其发生的条件为:ability,< detector的属性包括: A,即detector能力低于某一阈值,此时detector将 I)位置pos:用于描述detector在图像环境中 以概率P触发移动行为,而以概率1·PM触发革 的当前位置不同位置detector将感知不同的局部环 命行为(revolution),其中Pu为detector己经移动 境 步数step的减函数Pu=Pw(step),如图2所示,这 2)目标goal:用期望检测到的图像灰度均值M 表示detector为更好实现目标而改变所处的环境, 和方差D表示,goal:::=(M,D detector每移动一次,其step将增l 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
其结 构 的 开 放 系 统. 根 据 Guessoum [5 ] , 这 样 的 MAS 应该由如下 3 个部分组成. 与问题/ 领域相关的 Agent. 这是自适应 MAS 的基础 ,这些 Agent 可以有不同的类型、目标和行 为 ,它们存在于环境中并感知环境的局部信息 ,由此 进行决策 ,作出一定的行为. Agent 间关系. 个体 Agent 的能力有限 ,必须和 其他 Agent 共享信息和协作 ,以完成更复杂的任 务. Agents 间由此形成了一定的依赖关系 ,这可以 用 MAS 组织结构来表示 ,这种结构根据需要而产 生和瓦解 ,是一种动态结构. 管理 Agent. 由于 Agent 的局部性 ,无法把握问 题求解的整体过程 ,虽然 Agent 完全自适应也可以 用于问题的求解 ,这正如文献[ 3 ]的做法 ,但这种系 统的鲁棒性不强 ,无法控制系统的演化方向 ,尤其是 无法获得关于系统更高层的信息. 因此 ,引入的管理 Agent 用于对系统的当前状态进行全局的监控 ,根 据高层知识对问题 Agent 进行指导和约束 ,加速求 解过程 ,约束求解方向. 根据上面 3 条原则 ,设计用于图像分割的自适 应 MAS 结构如图 1 所示 (其中 monitor 表示管理 Agent ,detector 表示问题 Agent) . 图 1 MAS 结构 Fig11 The structure of MAS 2 图像特征检测 Agent 图像特征检测 Agent (问题 Agent) ,简称 detec2 tor ,主要用于搜索与自己目标相同的图像区域 ,它 利用典型的反应式 Agent 结构[6 ] (下文所述下标 i 均表示 Agent 的标识) . detector 的属性包括 : 1) 位置 pos:用于描述 detector 在图像环境中 的当前位置不同位置 detector 将感知不同的局部环 境. 2) 目标 goal :用期望检测到的图像灰度均值 M 和方差 D 表示 , goali ∶∶= ( Mi D i) . 3) 感知 sense :设 detector 当前位于图像中的 i 像素处 ,感知半径为 r,则所有满足 ‖i - j ‖< r(与 i 相距不超过 r) 的像素 j 都可被 detector 感知 ,并且 感知 sense 用 r 内所有像素的均值和方差表示 , sensei = ( M r i D r i ) , 更复杂的感知还包括灰度直方 图、纹理特征等. 4) 能力 ability :这是 detector 的核心 ,反映 de2 tector 对当前环境的适应程度 ,随着其目标和局部 感知 环 境 的 变 化 而 变 化 , 定 义 能 力 abilityi = 1/ (| goali - sensei | ) ,是目标与感知差异的减函数. 能力类似于遗传算法( GA) 中的适应度函数 ,但 GA 中的适应度函数一般是全局且是静态的 ,而本文的 能力则是局限于每个 Agent 且会因其选择不同的 行为、具有不同的目标、感知不同的环境而变化 ,这 更符合自然界规律 ,全局的行为是通过个体通过局 部的自适应而实现的 ,这种通过个体局部自适应而 涌现的智能求解复杂问题正是 Agent 计算的核心 , 这正如文献[7 ]所述. 5) 类别 C:用来表示该 detector 当前所属类别 , 作为图像最终分割的依据. 6) 繁殖与移动向量 (U Q) :用于描述 detector 在各个方向上繁殖和移动的权重 ,记录 detector 的 历史信息 ,即 U ( H) = [ u1 , u2 , u3 , …, ui , …, un ] , Q( J ) = [ q1 , q2 , q3 , …, qj , …, qn ]. 式中 : ∑ n i = 1 ui = 1 , ∑ n j = 1 qj = 1 , ui ∈[0 ,1 ] , qj ∈[0 ,1 ] , 分 别为方向 i , j 上的繁殖权重与移动权重. 常见的 繁殖与移动方向可采用像素的 82邻域 ,此时 n = 8. 7) 步数 step :用以刻画 detector 的年龄 ,初始时 step = 0 , detector 每执行一次移动行为 ,则其 step 将增 1. detector 的行为包括 : 1) 移动 (moving) :即 detector 由一个位置迁移 到另一个位置 ,移动方向由其移动向量 Q 决定 ,即 向 Qj 最大的方向移动. 其发生的条件为 :abilityi < A ,即 detector 能力低于某一阈值 ,此时 detector 将 以概率 PM 触发移动行为 ,而以概率 1 - PM 触发革 命行为(revolution) ,其中 PM 为 detector 已经移动 步数 step 的减函数 PM = PM (step) ,如图 2 所示 ,这 表示 detector 为更好实现目标而改变所处的环境 , detector 每移动一次 ,其 step 将增 1. 第 4 期 陈小波 ,等 :一种基于 MAS 的自适应图像分割方法 · 18 ·
·82 智能系统学报 第2卷 1.0e 5)竞争(compete):当Agent由于移动、繁殖等 0.9 行为而到达一个已有Agent存在的像素时将触发 0.8 0.7 一革命概率1-P 二者的竞争行为,此时向管理Agent(monitor)提交 0.6 冲突申请,monitor将按照一定的法则(如根据能量 蓝 0.4 大小)进行协调,使得竞争获胜的Agent占据该像 0.3 ·一移动概率卫 素,而竞争失败的Agent将被从图像中删除.这反 0.2 映了自然界中不同类型的系统间的竞争关系,竞争 行为主要发生在图像的边界区域 0 十3寸5689 步数/step 6)死亡(dead):设Agent的最大生命值为S,则 2种情况会导致detector死亡,a)detector的移动导 图2移动/革命概率与步数的关系 致其生命值减少,当移动步数step>S,意味着de Fig 2 Relationship between moving/revolution tector在生命期中仍未找到目标区域,则会死亡,b) probability and steps detector由于竞争失败而死亡,死亡的detector会 2)革命(revolution):革命行为将使detector改 从图像中删除。 变其目标为当前环境以提升能力.当detector经过 Agent的6种行为涉及3个主要参数:能力阈 长时间的移动仍然未找到使其ability,>A的像素 值A、移动步数阈值S、繁殖下一代Aget的个数 时,detector进行革命的可能性越来越大,即detec- B.这6种行为间的关系如图3 tor将以一定的概率1-P触发革命行为,而以概 定居 繁殖 率P,继续移动,以忠实原有目标.革命行为实质上 是为detector更好地适应环境而进行的一种自学习 革命 行为,这正如自然界中的常见规律:当无法改变环境 局部刺激 移动 时,就改变自己,这类似于GA中的变异算子.移动 死亡 和革命行为两者反应了detector在进化和学习间保 竞争 持一种平衡 3)定居(inhabit):发生条件为ability,>A,表示 图3 detector行为间的关系 detector的目标和环境保持很高的一致,即detector Fig 3 Relationship between detector's behaviors 的目标得以实现,从而detector占据该位置并失去 活性,实现对像素的标记.并且detector的繁殖与移 3 管理Agent 动向量(U,Q将用达到目标前的移动方向进行更 detector的特征检测是局部化的,MAS的演化 新,即 是不确定的.管理Agent,简称monitor,用于从更高 1=近土5 层次监控detector的行为并在恰当的时刻给予协 1+Ψ 调 =96±5 1+Ψ monitor的任务是: 平,任在h方向上达到目标,平为方向 I)冲突消解.当具有不同目标的多个detector 式中:5= 0,其他 试图占据同一个图像像素时产生冲突.monitor需 更新的力度大小 要根据一定的判决规则消解冲突.本文采用了基于 4)繁殖(breed):发生条件同3),即找到目标区 能力的判决,即认为能力ability大的detector获 域的定居detector,根据其此时的繁殖向量U在各 胜,其他竞争detector则由于失败而死亡. 个方向上复制出B个下一代detector,U方向权重 2)对所有detector的目标进行协调,这种协调 越大,该方向上复制的detector越多,下代detector 的结果产生了detector所属的类别,对应于图像的 的属性将继承自父detector,以继续搜索同类区域, 一种分割结果.具体过程为:monitor根据当前abil- 这种搜索是有偏的,反映出进化行为,繁殖行为类似 ity>A的所有detectors的目标进行目标的合并和 于GA中的选择算子 修正,对detector的目标进行更新.有2种可行的方 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 2 移动/ 革命概率与步数的关系 Fig12 Relationship between moving/ revolution probability and step s 2) 革命(revolution) :革命行为将使 detector 改 变其目标为当前环境以提升能力. 当 detector 经过 长时间的移动仍然未找到使其 abilityi > A 的像素 时 ,detector 进行革命的可能性越来越大 ,即 detec2 tor 将以一定的概率 1 - PM 触发革命行为 ,而以概 率 PM 继续移动 ,以忠实原有目标. 革命行为实质上 是为 detector 更好地适应环境而进行的一种自学习 行为 ,这正如自然界中的常见规律 :当无法改变环境 时 ,就改变自己 ,这类似于 GA 中的变异算子. 移动 和革命行为两者反应了 detector 在进化和学习间保 持一种平衡[8 ] . 3) 定居(inhabit) :发生条件为 abilityi > A ,表示 detector 的目标和环境保持很高的一致 ,即 detector 的目标得以实现 ,从而 detector 占据该位置并失去 活性 ,实现对像素的标记. 并且 detector 的繁殖与移 动向量 (U , Q) 将用达到目标前的移动方向进行更 新 ,即 u t+1 h = u t h +ζ 1 + Ψ , q t+1 h = q t h +ζ 1 + Ψ . 式中 :ζ= Ψ, (if 在 h 方向上达到目标) , 0 ,其他. Ψ 为方向 更新的力度大小. 4) 繁殖(breed) :发生条件同 3) ,即找到目标区 域的定居 detector ,根据其此时的繁殖向量 U 在各 个方向上复制出 B 个下一代 detector ,Uh 方向权重 越大 ,该方向上复制的 detector 越多 ,下代 detector 的属性将继承自父 detector ,以继续搜索同类区域 , 这种搜索是有偏的 ,反映出进化行为 ,繁殖行为类似 于 GA 中的选择算子. 5) 竞争(compete) :当 Agent 由于移动、繁殖等 行为而到达一个已有 Agent 存在的像素时将触发 二者的竞争行为 ,此时向管理 Agent (monitor) 提交 冲突申请 ,monitor 将按照一定的法则(如根据能量 大小) 进行协调 ,使得竞争获胜的 Agent 占据该像 素 ,而竞争失败的 Agent 将被从图像中删除. 这反 映了自然界中不同类型的系统间的竞争关系 ,竞争 行为主要发生在图像的边界区域. 6) 死亡(dead) :设 Agent 的最大生命值为 S ,则 2 种情况会导致 detector 死亡 ,a) detector 的移动导 致其生命值减少 ,当移动步数 step > S ,意味着 de2 tector 在生命期中仍未找到目标区域 ,则会死亡 ,b) detector 由于竞争失败而死亡 ,死亡的 detector 会 从图像中删除. Agent 的 6 种行为涉及 3 个主要参数 :能力阈 值 A 、移动步数阈值 S 、繁殖下一代 Agent 的个数 B. 这 6 种行为间的关系如图 3. 图 3 detector 行为间的关系 Fig13 Relationship between detector′s behaviors 3 管理 Agent detector 的特征检测是局部化的 ,MAS 的演化 是不确定的. 管理 Agent ,简称 monitor ,用于从更高 层次监控 detector 的行为并在恰当的时刻给予协 调. monitor 的任务是 : 1) 冲突消解. 当具有不同目标的多个 detector 试图占据同一个图像像素时产生冲突. monitor 需 要根据一定的判决规则消解冲突. 本文采用了基于 能力的判决 ,即认为能力 ability 大的 detector 获 胜 ,其他竞争 detector 则由于失败而死亡. 2) 对所有 detector 的目标进行协调 ,这种协调 的结果产生了 detector 所属的类别 ,对应于图像的 一种分割结果. 具体过程为 :monitor 根据当前 abil2 ity > A 的所有 detectors 的目标进行目标的合并和 修正 ,对 detector 的目标进行更新. 有 2 种可行的方 · 28 · 智 能 系 统 学 报 第 2 卷
第4期 陈小波,等:一种基于MAS的自适应图像分割方法 ·83 法 系统自动生成一个monitor,monitor初始化类别数 ①自动合并,根据度量准则将接近的detector C=0 的目标g0al与类别属性(MD)进行合并并对相应 I/生成detector 的detector进行目标修正及类别属性修正,即满足 monitor在U1XU2上生成一定数量的初始detec- 条件IM-Me‖4 then 活动detector数是否为0判断分割是否结束,本文 执行定居及繁殖行为,根据繁殖向量U 采用了后一种方案 产生新一代detector else 4基于MAS的自适应图像分割 if step>S then 算法主要包括三大部分:系统初始化,monitor detector死亡 的自治行为选择及detector自治的行为选择,具体 else 框架为 根据步数计算Pm,随机生成概率P 输入:一个大小为U:U2的灰度数字图像, if P>P then 输出:己标记出的各类分割区域, 根据移动向量Q计算移动目标位置 /1初始化 f目标位置处已有detector then向monitor提 begin 交冲突申请 用户设定系统参数:A,B,S,6u,6o,Ψ else 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
法 : ①自动合并 ,根据度量准则将接近的 detector 的目标 goal 与类别属性 ( M D ) 进行合并并对相应 的 detector 进行目标修正及类别属性修正 ,即满足 条件 ‖Mi - Mc ‖ A then 执行定居及繁殖行为 ,根据繁殖向量 U 产生新一代 detector else if step > S then detector 死亡 else 根据步数计算 Pm ,随机生成概率 P if P > Pm t hen 根据移动向量 Q 计算移动目标位置 if 目标位置处已有 detector t hen 向 monitor 提 交冲突申请 else 第 4 期 陈小波 ,等 :一种基于 MAS 的自适应图像分割方法 · 38 ·
·84· 智能系统学报 第2卷 detector移动到目标位置,并置step=step+I 经过76代运行后,MAS系统收敛,活动detec- endif tor数为0,所有定居detector被划分到4类中.分 else 割过程中的总活动detector数变化如图5,可见在 detector执行革命行为,改变目标为局部感 30代时曲线已几乎收敛.各类别的定居detector数 知,以提升ability 的变化如图6. ×10 endif 2.00 endif 1.8 1.6 endif 1.4 endfor 1.0 endwhile 0.8 end 0.6 0.4 活动detector数 0.2 5 实验结果及分析 0 1020304050607080 本实验利用了一系列医学图像进行验证.其中 代数/代 monitor采用了自动合并和基于能力的冲突消解策 图5 活动detector数的变化 略.图4为256256的原始大脑灰度图像,其中包 Fig 5 Number of active detectors 含4类区域:背景、灰质、白质及脑髓液.用于该图像 30*10 分割的参数如表1 2.5 ·一背景 教 2.0 一灰质 1.5 1.0 。一白质 0.5 ◆一脑髓液 0 10.20 304050607080 代数/代 图6各类定居detector数的变化 Fig 6 Number of inhabit detectors of different classes 图像分割的动态过程如图7所示,表示不同代 数t时定居detector的分布. 图4用于分割的大脑图像 Fig 4 Brain image used for segmentation 表1用于分割的参数 Table 1 Parameters used for segmentation 参数 参数值 初始detector数 5000 (a)t=0 (b)t=3 0.01 中 4 4 6 60 n 50 型 02 (e)1=5 (d=8 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
detector 移动到目标位置 ,并置 step = step + 1 endif else detector 执行革命行为 ,改变目标为局部感 知 ,以提升 ability endif endif endif endfor endwhile end 5 实验结果及分析 本实验利用了一系列医学图像进行验证. 其中 monitor 采用了自动合并和基于能力的冲突消解策 略. 图 4 为 256 ×256 的原始大脑灰度图像 ,其中包 含 4 类区域 :背景、灰质、白质及脑髓液. 用于该图像 分割的参数如表 1. 图 4 用于分割的大脑图像 Fig14 Brain image used for segmentation 表 1 用于分割的参数 Table 1 Parameters used for segmentation 参数 参数值 初始 detector 数 5 000 A 0101 B 4 S 4 δM 60 δD 50 Ψ 012 经过 76 代运行后 ,MAS 系统收敛 ,活动 detec2 tor 数为 0 ,所有定居 detector 被划分到 4 类中. 分 割过程中的总活动 detector 数变化如图 5 ,可见在 30 代时曲线已几乎收敛. 各类别的定居 detector 数 的变化如图 6. 图 5 活动 detector 数的变化 Fig15 Number of active detectors 图 6 各类定居 detector 数的变化 Fig16 Number of inhabit detectors of different classes 图像分割的动态过程如图 7 所示 ,表示不同代 数 t 时定居 detector 的分布. · 48 · 智 能 系 统 学 报 第 2 卷
第4期 陈小波,等:一种基于MAS的自适应图像分割方法 ·85· 一种基于MAS的自适应图像分割方法,模仿了竞 争和扩张过程,MAS演化的平衡即代表了分割图像 的形成.采用了分层MAS结构,底层特征检测A- gent的进化适应行为使得大块同类特征被快速搜 索到,边界特征处则进行竞争标记,高层管理Agent 的引入控制了特征的高层属性,并对底层Agent进 行协调,使得MAS演化更加高效和鲁棒.实验证实 (e)1=10 (01=20 了该方法的有效性, 图7定居detector分布的演化 参考文献 Fig 7 The evolution of inhabit detector [1 WOOLDRIDGE M,J ENNIN GS N R.Intellige-nt A- 从图中看出初始无差异的Agent如何通过自 gents:theory and practice[J].The Knowledge Engineer- 适应行为产生各自目标,使得图像同类特征被快速 ing Review,1995,10(2):115.152 抽取,组织边界特征则延迟通过竞争标记而得到,最 [2]WOOLDRIDGE.多Aget系统导引[M].石纯一,译.北 终完成图像的分割.图像的最终分割结果如图8所 京:电子工业出版社,2003. 示,分别对应于背景和3种组织:灰质、白质及脑髓 [3]LIU J,TANG Y Y.Adaptive image segmentatio-n with distributed behavior-based Agents [J ]IEEE Transac- 液。 tions on PAMI,1999,21(6):544.551 [4]刘俊义,王润生.利用分布式主动智能体检测灰度图像 的对称轴U].软件学报,2002,13(7):1238.1241 LIU Junyi,WANG Runsheng.Using distributed active Agents to detect the symmetry axes in gray imrages [J]. Journal of Software,2002,13 (7):1238 -1241. [5]GUESSOUM Z,BRIOT J P,CHARPENTIER S,MA- RIN O.SENS P.A fault-tolerant multi-Agent frame- work[A].AAMAS[C].[s.1.],2002. (a)背景 ()灰质 [6]程显毅.Agct计算[M)].哈尔滨:黑龙江科学技术出版 社,2003. [7]钟伟才,刘静,刘芳,焦李成.组合优化多智能体 进化算法U].计算机学报,2004,27(10):1341·1353. ZHONG Weicai,LIU Jing,LIU fang,JIAO Licheng. Combinatorial optimization using multi-Agent evolution ary algorithm[J].Chinese Journal of Computers,2004, 27(10):1341.1353. [8 LIU Jiming..多智能体原理与技术[M].靳小龙,张世武, (c)白质 (d髓液 LIU Jiming,译.北京:清华大学出版社,2003. [9]HOLLANDJ H.涌现从混沌到有序[M].陈禹,译.上 图8最终分割结果 海:上海科技教育出版社,2001. Fig 8 The final segment results 作者简介: 本文的方法与文献31相比,文献31分割一类 陈小波,男,1982年生,助教,主要研 组织需要指定14个参数,分割n类则需要14×n个 究方向为模式识别、多Agent系统 参数,并需将系统分别运行n次,本方法在8-邻域 Email xbchen82 @yahoo.com.cn. 的前提下,只需指定7个参数,且与分割类别个数无 关,大大降低了参数设置上的复杂度,并且一次运行 即可完成所有类别的分割.与传统方法如c均值聚 类等相比,由于其需要指定分割类别数,故使用受到 约束,本方法的分割类别数通过系统不断演化趋于 程显毅,男,1956年生,教授,博士生 稳定而涌现形成,反映了系统的自适应性本质,因 导师,主要研究方向为模式识别、多Agent 而具有更广阔的应用前景 系统.发表论文70多篇,参与或主持课题 多项,主要学术专著《Agent计算》, 6结束语 受自然界中存在大量均衡系统的启发,提出了 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 7 定居 detector 分布的演化 Fig17 The evolution of inhabit detector 从图中看出初始无差异的 Agent 如何通过自 适应行为产生各自目标 ,使得图像同类特征被快速 抽取 ,组织边界特征则延迟通过竞争标记而得到 ,最 终完成图像的分割. 图像的最终分割结果如图 8 所 示 ,分别对应于背景和 3 种组织 :灰质、白质及脑髓 液. 图 8 最终分割结果 Fig18 The final segment results 本文的方法与文献[3 ]相比 ,文献[3 ]分割一类 组织需要指定 14 个参数 ,分割 n 类则需要 14 ×n 个 参数 ,并需将系统分别运行 n 次 ,本方法在 82邻域 的前提下 ,只需指定 7 个参数 ,且与分割类别个数无 关 ,大大降低了参数设置上的复杂度 ,并且一次运行 即可完成所有类别的分割. 与传统方法如 c 均值聚 类等相比 ,由于其需要指定分割类别数 ,故使用受到 约束 ,本方法的分割类别数通过系统不断演化趋于 稳定而涌现[9 ]形成 ,反映了系统的自适应性本质 ,因 而具有更广阔的应用前景. 6 结束语 受自然界中存在大量均衡系统的启发 ,提出了 一种基于 MAS 的自适应图像分割方法 ,模仿了竞 争和扩张过程 ,MAS 演化的平衡即代表了分割图像 的形成. 采用了分层 MAS 结构 ,底层特征检测 A2 gent 的进化、适应行为使得大块同类特征被快速搜 索到 ,边界特征处则进行竞争标记 ,高层管理 Agent 的引入控制了特征的高层属性 ,并对底层 Agent 进 行协调 ,使得 MAS 演化更加高效和鲁棒. 实验证实 了该方法的有效性. 参考文献 : [ 1 ] WOOLDRID GE M ,J ENNIN GS N R. Intellige2nt A2 gents :theory and practice[J ]. The Knowledge Engineer2 ing Review ,1995 ,10 (2) :115 - 152. [2 ]WOOLDRID GE. 多 Agent 系统导引[ M ]. 石纯一 ,译. 北 京 :电子工业出版社 ,2003. [3 ]L IU J , TAN G Y Y. Adaptive image segmentatio2n with distributed behavior2based Agents [J ]. IEEE Transac2 tions on PAMI ,1999 , 21 (6) :544 - 551. [4 ]刘俊义 , 王润生. 利用分布式主动智能体检测灰度图像 的对称轴[J ]. 软件学报 ,2002 ,13 (7) : 1238 - 1241. L IU J unyi , WAN G Runsheng. Using distributed active Agents to detect the symmetry axes in gray im2ages [J ]. Journal of Software , 2002 , 13 (7) : 1238 - 1241. [5 ] GU ESSOUM Z , BRIO T J P , CHARPEN TIER S ,MA2 RIN O , SENS P. A fault2tolerant multi2Agent frame2 work[ A ]. AAMAS[C]. [s. l. ] ,2002. [6 ]程显毅. Agent 计算[ M ]. 哈尔滨 :黑龙江科学技术出版 社 , 2003. [7 ]钟伟才 , 刘 静 , 刘 芳 , 焦李成. 组合优化多智能体 进化算法[J ]. 计算机学报 , 2004 ,27 (10) :1341 - 1353. ZHON G Weicai , L IU Jing , L IU fang , J IAO Licheng. Combinatorial optimization using multi2Agent evolution2 ary algorithm[J ]. Chinese Journal of Computers , 2004 , 27 (10) :1341 - 1353. [8 ]L IU Jiming. 多智能体原理与技术[ M]. 靳小龙 ,张世武 , L IU Jiming ,译. 北京 : 清华大学出版社 , 2003. [9 ] HOLLAND J H. 涌现 —从混沌到有序[ M ]. 陈禹 ,译. 上 海 :上海科技教育出版社 ,2001. 作者简介 : 陈小波 ,男 ,1982 年生 ,助教 ,主要研 究方向为模式识别、多 Agent 系统. E2mail :xbchen82 @yahoo. com. cn. 程显毅 ,男 ,1956 年生 ,教授 ,博士生 导师 ,主要研究方向为模式识别、多 Agent 系统. 发表论文 70 多篇 ,参与或主持课题 多项 ,主要学术专著《Agent 计算》. 第 4 期 陈小波 ,等 :一种基于 MAS 的自适应图像分割方法 · 58 ·