第2卷第1期 智能系统学报 Vol.2 Ng 1 2007年2月 CAAI Transactions on Intelligent Systems Fcb.2007 基于粒子群优化算法和改进的 Snake模型的图像分割算法 王科俊，郭庆昌 (哈尔滨工程大学自动化学院，黑龙江哈尔滨150001) 摘要：基于活动轮廓(Snake))模型的目标轮廓提取是图像分割中一种重要的方法.为了克服传统Snake模型在图像 分割中不能向凹处收敛和收敛不准确的缺点，提出了一种粒子群优化算法与改进的Sake模型相结合的图像分割算 法.改进的Snake模型，即在传统的Snake模型的基础上增加了一个向心能量，增加此能量可以使初始化曲线向目标 的凹处收敛.又由于粒子群优化算法具有获得全局最优的能力，可以使曲线能更准确地收敛到目标的边界，通过实 验证明此方法可以取得很好的分割效果. 关键词：Snake模型：图像分割：PSO算法 中图分类号：TP391文献标识码：A文章编号：1673-4785(2007)01-0053-06 Image segmentation algorithm based on the PSO and improved Snake model WANG Ke-jun,GUO Qingchang (College of Automation,Harbin Engineering University,Harbin 150001,China) Abstract:Getting the contour of an object according to the Snake model is an important method in the im- age segmentation.Because traditional Snake model cannot reach the concave of the object and the result of convergence is not accurate,an image segmentation algorithm based on the PSO and improved Snake model is proposed.The improved Snake model is generated by adding centripetal energy to traditional Snake model.The curve can reach the concave of the object because of the centripetal energy.Because the PSO has the ability of getting the global optimization,the curve can exactly reach the edge of the object.It is proved by experiment that preferable image segmentation result is gotten based on the algorithm. Keywords:Snake model;image segmentation;PSO algorithm 图像分割是图像处理的一项关键技术，迄今为 和外部能量的共同作用下最后使曲线收敛到目标的 止已经提出了许多图像分割方法.这些方法虽然简 真实轮廓，此时曲线的能量最小.然而，传统的 单，但对噪声敏感并且很难得到连续的边界.于是基 Snake模型有许多局限性，不能向凹处收敛，易陷入 于轮廓变化的形变模型近年来在图像分割中得到了 能量局部极值.针对传统Snake模型存在的这些缺 广泛的应用.目前常见的图像分割模型有2种：基于 点，有不少文献已经提出了改进的方法，如Cohen 参数的模型和基于几何特性的模型.Snake模型就 引入了膨胀力，从而保证了Snake的收敛性；Xu 是一种基于参数的模型，它在1987年由Kass)提 等提出了梯度向量流(gradient vector flow,GVF) 出，被用于跟踪人脸嘴部的运动.而且Snake模 Snake模型)，该模型对图像梯度场逼近构造了一 型21也是一种动力学模型，首先在目标周围定义 种新的外力，通过严格地在内力和外力的作用下达 一条带有能量的初始化曲线，在曲线本身内部能量 到平衡时来得到目标边缘.陈允杰、张建伟提出了遗 传算法在Snake模型中的应用s],此算法虽然提高 收稿日期：2006-07-22 了传统Snake模型的分割精度，但是对有凹处目标 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 1 期 智 能 系 统 学 报 Vol. 2 №. 1 2007 年 2 月 CAA I Transactions on Intelligent Systems Feb. 2007 基于粒子群优化算法和改进的 Snake 模型的图像分割算法 王科俊 ,郭庆昌 (哈尔滨工程大学 自动化学院 ,黑龙江 哈尔滨 150001) 摘 要 :基于活动轮廓(Snake) 模型的目标轮廓提取是图像分割中一种重要的方法. 为了克服传统 Snake 模型在图像 分割中不能向凹处收敛和收敛不准确的缺点 ,提出了一种粒子群优化算法与改进的 Snake 模型相结合的图像分割算 法. 改进的 Snake 模型 ,即在传统的 Snake 模型的基础上增加了一个向心能量 ,增加此能量可以使初始化曲线向目标 的凹处收敛. 又由于粒子群优化算法具有获得全局最优的能力 ,可以使曲线能更准确地收敛到目标的边界. 通过实 验证明此方法可以取得很好的分割效果. 关键词 :Snake 模型 ;图像分割 ; PSO 算法 中图分类号 : TP391 文献标识码 :A 文章编号 :167324785 (2007) 0120053206 Image segmentation algorithm based on the PSO and improved Snake model WAN G Ke2jun , GUO Qing2chang (College of Automation , Harbin Engineering University , Harbin 150001 ,China) Abstract : Getting the contour of an object according to t he Snake model is an important met hod in the im2 age segmentation. Because traditional Snake model cannot reach t he concave of the object and t he result of convergence is not accurate , an image segmentation algorit hm based on t he PSO and improved Snake model is propo sed. The improved Snake model is generated by adding centripetal energy to traditional Snake model. The curve can reach t he concave of t he object because of t he centripetal energy. Because t he PSO has t he ability of getting the global optimization , t he curve can exactly reach t he edge of the object. It is proved by experiment t hat preferable image segmentation result is gotten based on t he algorit hm. Keywords : Snake model ; image segmentation ; PSO algorit hm 收稿日期 :2006207222. 图像分割是图像处理的一项关键技术 ,迄今为 止已经提出了许多图像分割方法. 这些方法虽然简 单 ,但对噪声敏感并且很难得到连续的边界. 于是基 于轮廓变化的形变模型近年来在图像分割中得到了 广泛的应用. 目前常见的图像分割模型有 2 种 :基于 参数的模型和基于几何特性的模型. Snake 模型就 是一种基于参数的模型 ,它在 1987 年由 Kass [1 ] 提 出 ,被用于跟踪人脸嘴部的运动. 而且 Snake 模 型[2 - 5 ]也是一种动力学模型 ,首先在目标周围定义 一条带有能量的初始化曲线 ,在曲线本身内部能量 和外部能量的共同作用下最后使曲线收敛到目标的 真实轮廓 , 此时曲线的能量最小. 然而 , 传统的 Snake 模型有许多局限性 ,不能向凹处收敛 ,易陷入 能量局部极值. 针对传统 Snake 模型存在的这些缺 点 ,有不少文献已经提出了改进的方法 ,如 Cohen 引入了膨胀力[6 ] ,从而保证了 Snake 的收敛性 ; Xu 等提出了梯度向量流 ( gradient vector flow , GVF) Snake 模型[7 ] ,该模型对图像梯度场逼近构造了一 种新的外力 ,通过严格地在内力和外力的作用下达 到平衡时来得到目标边缘. 陈允杰、张建伟提出了遗 传算法在 Snake 模型中的应用[ 8 ] ,此算法虽然提高 了传统 Snake 模型的分割精度 ,但是对有凹处目标
·54 智能系统学报 第2卷 的分割效果并不理想 数B的值越大曲线的收缩速度越快，所以称B为弹 粒子群算法(particle swarm optimization, 力系数 PSO)是一种模拟鸟群飞行的仿生算法，有着个体 Eue(i,材表示离散点间的二阶微分的平方 数目少，计算简单，鲁棒性好等优点，而且是一种高 和，表示曲线的曲率变化率，主要控制活动曲线向目 效的全局最优化的搜索方法 标移动.而系数ā控制着活动曲线向目标变化的速 于是文中根据以上分析提出了一种基于PSO 度.这一项使得活动曲线的运动就如同一条刚体绳 和改进的Snake模型相结合的图像分割算法.此算 子的运动，它可以使活动曲线在运动的过程中保持 法不仅较好地解决了传统Snake分割算法不能向凹 光滑性.由于当a值较大时活动曲线就会变得很僵 处收敛和易进入局部最优的缺点，而且也保持了传 硬而不容易发生弯曲，而当·值较小时则活动曲线 统Snake模型几何拓扑的性质，并且很好地提高了 会变得很柔软易于形变，所以称a为强度系数 图像分割的精度 Em(i,d是初始化曲线收敛到真实边界的最 重要判断条件.在边界处曲线的图像能量很大，而在 1传统Snake模型 非边缘处图像能量较小，所以为了使曲线收敛到目 活动轮廓模型的基本方法是首先在图像中目标 标的边缘时能量最小，Eme(i,:常取负值，Y为图 的周围设置一条封闭曲线，然后在内部能量和外部 像力系数，并且Y相对a和B较大 能量的共同作用下使曲线向合适的位置移动并且不 2改进的Snake模型 断更新曲线能量，曲线最后到达目标的轮廓，此时曲 线能量最小 为了克服传统Snake算法在图像分割中的缺 曲线能量函数是内部能量和外部能量的加权 点，文中对传统算法进行了改进，即增加了一个可以 和.内部能量可由曲线形状得到，而外部能量则从图 使曲线向凹处收敛的向心能量 像中得到 改进的Snake模型表示如下： 传统Snake模型的离散化表示如下： Efim +r(s)Fex+e(s)Eemet ds. 3) E=Eimt (i.k)Eext (i, 1) 式3)的分解式为 式中：E(i,)表示图像在第k次迭代点i的内部 E-fa(s)Eomned +B(s)Eune +r(s)Eimas+ 能量，此能量一般由弯曲能量和连接能量表示 E(s)Ecemter)ds (4) Ei,材表示图像在第k次迭代点i的外部能量， 式4的离散化形式如下： 一般由图像的梯度表示 式()的分解式为 B=a(0 Eomms (i.B(Eune (i. r(k)Eimage (i,k)+e(i)Ecemter(i.k)]. 5) E=E作.州+Em在.+Eei,I 式中：i表示曲线的第i个点，k表示曲线的迭代次 (2) 数，如Eoonnect(i,付表示第k次迭代点i处的连接能 式中：Eme(i,付表示曲线在第k次迭代点i处的 量，其他能量表示类似，n为曲线上离散点的个数， 弯曲能量，Euea.表示曲线在第k次迭代点i处的 下面将结合图1对式(5)中的各项进行详细的 连接能量，Eme(i,利表示曲线第k次迭代点i处的 说明.图1中p为选定的目标内一点，i为当前运动 图像能量，n表示曲线上离散点的个数.这里 的点，点i的作用范围为1点周围55个点（包括 a Eeurve(i,材+Ecomnect(i,材相当于式(I)中的内部能 i,作用范围可以根据图像进行调整)以s表示，点 量Et(i,材.Em(i,相当于式(1)中的外部能量 i-1和1+1为点i的2个相邻点，1为s范围内任意 Eext (i.k) 点.实线为收敛曲线，虚线表示各点之间的连接关 Em(i,材相当离散点间的一阶微分，表示活 系 动曲线长度的变化率，主要控制曲线在收敛时的连 2.1。连接能量 续性.由于系数B可以控制活动曲线的收缩速度，系 连接能量Eoanect的表示形式为 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
的分割效果并不理想. 粒 子 群 算 法 ( particle swarm optimization , PSO) [9 ]是一种模拟鸟群飞行的仿生算法 ,有着个体 数目少 ,计算简单 ,鲁棒性好等优点 ,而且是一种高 效的全局最优化的搜索方法. 于是文中根据以上分析提出了一种基于 PSO 和改进的 Snake 模型相结合的图像分割算法. 此算 法不仅较好地解决了传统 Snake 分割算法不能向凹 处收敛和易进入局部最优的缺点 ,而且也保持了传 统 Snake 模型几何拓扑的性质 ,并且很好地提高了 图像分割的精度. 1 传统 Snake 模型 活动轮廓模型的基本方法是首先在图像中目标 的周围设置一条封闭曲线 ,然后在内部能量和外部 能量的共同作用下使曲线向合适的位置移动并且不 断更新曲线能量 ,曲线最后到达目标的轮廓 ,此时曲 线能量最小. 曲线能量函数是内部能量和外部能量的加权 和. 内部能量可由曲线形状得到 ,而外部能量则从图 像中得到. 传统 Snake 模型的离散化表示如下 : E = ∑ n i =1 Eint ( i , k) + Eext ( i , k) . (1) 式中 : Eint ( i , k) 表示图像在第 k 次迭代点 i 的内部 能量 ,此能量一般由弯曲能量和连接能量表示. Eext ( i , k) 表示图像在第 k 次迭代点 i 的外部能量 , 一般由图像的梯度表示. 式(1) 的分解式为 E = ∑ n i =1 [αEcurve (i, k) +βEconnect (i , k) + rEimage (i , k) ]. (2) 式中 : Econnect ( i , k) 表示曲线在第 k 次迭代点 i 处的 弯曲能量 , Ecurve ( i , k) 表示曲线在第 k 次迭代点 i 处的 连接能量 , Eimage ( i , k) 表示曲线第 k 次迭代点 i 处的 图像 能 量 , n 表 示 曲 线 上 离 散 点 的 个 数. 这 里 αEcurve ( i , k) +βEconnect ( i , k) 相当于式(1) 中的内部能 量 Eint ( i , k) . Eimage ( i , k) 相当于式 (1) 中的外部能量 Eext ( i , k) . Econnect ( i , k) 相当离散点间的一阶微分 ,表示活 动曲线长度的变化率 ,主要控制曲线在收敛时的连 续性. 由于系数β可以控制活动曲线的收缩速度 ,系 数β的值越大曲线的收缩速度越快 ,所以称β为弹 力系数. Ecurve ( i , k) 表示离散点间的二阶微分的平方 和 ,表示曲线的曲率变化率 ,主要控制活动曲线向目 标移动. 而系数α控制着活动曲线向目标变化的速 度. 这一项使得活动曲线的运动就如同一条刚体绳 子的运动 ,它可以使活动曲线在运动的过程中保持 光滑性. 由于当α值较大时活动曲线就会变得很僵 硬而不容易发生弯曲 ,而当α值较小时则活动曲线 会变得很柔软易于形变 ,所以称α为强度系数. Eimage ( i , k) 是初始化曲线收敛到真实边界的最 重要判断条件. 在边界处曲线的图像能量很大 ,而在 非边缘处图像能量较小 ,所以为了使曲线收敛到目 标的边缘时能量最小 , Eimage ( i , k) 常取负值 ,γ为图 像力系数 ,并且γ相对α和β较大. 2 改进的 Snake 模型 为了克服传统 Snake 算法在图像分割中的缺 点 ,文中对传统算法进行了改进 ,即增加了一个可以 使曲线向凹处收敛的向心能量. 改进的 Snake 模型表示如下 : E =∫Eint +γ(s) Eext +ε(s) Ecenter ds. (3) 式(3) 的分解式为 E =∫(α(s) Econnect +β(s) Ecurve +γ(s) Eimage + ε(s) Ecenter ) ds. (4) 式(4) 的离散化形式如下 : E = ∑ n i = 1 [α( i) Econnect ( i , k) +β( i) Ecurve ( i , k) + r( k) Eimage ( i , k) +ε( i) Ecenter ( i , k) ]. (5) 式中 :i 表示曲线的第 i 个点 , k 表示曲线的迭代次 数 ,如 Econnect ( i , k) 表示第 k 次迭代点 i 处的连接能 量 ,其他能量表示类似 , n 为曲线上离散点的个数. 下面将结合图 1 对式 (5) 中的各项进行详细的 说明. 图 1 中 p 为选定的目标内一点 , i 为当前运动 的点 ,点 i 的作用范围为 i 点周围 5 ×5 个点 (包括 i ,作用范围可以根据图像进行调整) 以 s 表示 , 点 i - 1和 i + 1 为点 i 的 2 个相邻点 , i′为 s 范围内任意 点. 实线为收敛曲线 ,虚线表示各点之间的连接关 系. 211 连接能量 连接能量 Econnect的表示形式为 ·54 · 智 能 系 统 学 报 第 2 卷
第1期 王科俊，等：基于粒子群优化算法和改进的Sake模型的图像分割算法 ·55 max(max(-G() min(W=min(-Gfi',*又Ii',材) 式中：Gi,为第k次迭代点i处的高斯值，V1(i, 从为第k次迭代点i处的图像梯度.s为点i周围5 5区域，max(材为第k次迭代s范围内图像能量 的最大值，min(材为第k次迭代s范围内图像能量 的最小值 图像经过高斯平滑后，可以使图像能量的作用 范围加大，使曲线更易于收敛，而且可以降低图像噪 图1点运动示意图 声的干扰.但同时也降低了曲线的收敛精度，可能产 Fig 1 Sketch map of dot moving Em(i.ave(dis)min( 生过收敛现象.于是文中首先用改进的Snake模型 max(-min( 拟合目标的边缘，然后用PSO在拟合曲线的周围搜 (6) 索，得到准确的目标边界 dis=sqrm·h2+(my-月 2.4向心能量 max(max(l avg(dis..(). 向心能量Eenter(i,W表达式为 min(=min(l avg(dis,.) Exmer (1.lvepll min( (9) max(-min() avg(dis/N max(=max(llv p 式中：s为当前运动点i周围55区域，avg(W为在 min(min(llv pll. 第k次迭代中s内所有点到点i:1的平均距离，' 为s中任意点，N为s中点的个数，dis.,1(材为在第 式中：lw-p‖为s范围内任意点到p(目标内开 k次迭代中s范围内任意点与点i-1的距离，v表 始选定的点)的距离；min()为s范围内任意点到p 示曲线上的点，max(:为在第k次迭代中s内所有 的最小距离；max()为s范围内任意点到p的最大 点与点i-1的距离的最大值：min(材为在第k次迭 距离.￡()为向心能量系数 代中s范围内所有点与点i-1的距离的最小值。 向心能量不仅可以使曲线向凹处收敛并且可以 2.2弯曲能量 加快曲线的收敛速度， 弯曲能量Ee(i,k材表达式为 五e作，村=a段-h-A、a-min园 3粒子群优化算法 max(W-min(付 粒子群算法由Kennedy和Eberhart1在1995 (7 年提出，该算法模拟鸟集群飞行觅食的行为，通过鸟 max(max (v.(v()(v(v() 之间的集体协作使群体达到最优目的.PS0算法属 min(=min(v(v()(v(v() 于进化算法的一种，和遗传算法类似，它也是从随机 式中：.1(W和+1（付为在第k次迭代中点i的2 解出发，通过迭代寻找最优解，它也是通过适应度来 个连接点，s为点i周围55区域()为s范围内 评价解的品质.但是它没有遗传算法的“交叉” 任意点.max(材为第k次迭代中s范围内所有点与 (Crossover)和“变异”(Mutation)操作，而是通过追 点i-1和点i+1之间差分的最大值：min(付为在 随当前搜索到的最优值来寻找全局最优.在P$0系 第k次迭代中s内所有点与点i-1和点1+1之间 统中，每个备选解被称为一个“粒子”(particle),多 差分的最小值 个粒子共存、合作寻优，每个粒子根据它自身的“经 2.3图像能量 验”和粒子群的最佳“经验”在问题空间中向更好的 文中采用的图像能量表达式为 Emea,龙=-Gd*又(i min(4 位置“飞行”，搜索最优解 max(k)min() PSO算法数学表示如下： 8 设搜索空间为D维，总粒子数为n第i个粒子 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 1 点运动示意图 Fig11 Sketch map of dot moving Econnect (i , k) = | (avg( k) - disi′,i- 1 ( k)) - min(k) | max(k) - min( k) . (6) disi′, i- 1 = sqrt ( vi′, x - vi , x ) 2 + ( vi′, y - vi , y ) 2 . max ( k) = max i′∈s (| avg ( k) - disi′, i- 1 ( k) | ) . min ( k) = min i′∈s (| avg ( k) - disi′, i- 1 ( k) | ) . avg ( k) = i′∑∈s disi′, i- 1 / N . 式中 :s 为当前运动点 i 周围 5 ×5 区域 ,avg ( k) 为在 第 k 次迭代中 s 内所有点到点 i - 1 的平均距离 , i′ 为 s 中任意点 , N 为 s 中点的个数 , disi , i - l ( k) 为在第 k 次迭代中 s 范围内任意点与点 i - 1 的距离 , v 表 示曲线上的点 ,max ( k) 为在第 k 次迭代中 s 内所有 点与点 i - 1 的距离的最大值;min ( k) 为在第 k 次迭 代中 s 范围内所有点与点 i - 1 的距离的最小值. 212 弯曲能量 弯曲能量 Ecurve ( i , k) 表达式为 Ecurve (i, k) = ( vi- 1 ( k) - vi′( k)) - ( vi′( k) - vi+1 ( k)) - min( k) max( k) - min( k) . (7) max(k) = max i′∈s ( vi- 1 ( k) - vi′( k)) - ( vi′(k) - vi+1 (k)) . min(k) = min i′∈s (vi- 1 ( k) - vi′( k)) - ( vi′( k) - vi+1 ( k)) . 式中 : vi - 1 ( k) 和 vi + 1 ( k) 为在第 k 次迭代中点 i 的 2 个连接点 ,s 为点 i 周围 5 ×5 区域 vi′( k) 为 s 范围内 任意点. max ( k) 为第 k 次迭代中 s 范围内所有点与 点 i - 1 和点 i + 1 之间差分的最大值; min ( k) 为在 第 k 次迭代中 s 内所有点与点 i - 1 和点 i + 1 之间 差分的最小值. 213 图像能量 文中采用的图像能量表达式为 Eimage ( i , k) = | - G( i′, k) 3 ¨ I( i′, k) - min ( k) | max ( k) - min ( k) . (8) max ( k) = max i′∈s ( - G( i′, k) 3 ¨ I ( i′, k) ) . min ( k) = min i′∈s ( - G( i′, k) 3 ¨ I ( i′, k) ) . 式中 : G( i , k) 为第 k 次迭代点 i 处的高斯值 , ¨ I ( i , k) 为第 k 次迭代点 i 处的图像梯度. s 为点 i 周围 5 ×5 区域 , max ( k) 为第 k 次迭代 s 范围内图像能量 的最大值 ,min ( k) 为第 k 次迭代 s 范围内图像能量 的最小值. 图像经过高斯平滑后 ,可以使图像能量的作用 范围加大 ,使曲线更易于收敛 ,而且可以降低图像噪 声的干扰. 但同时也降低了曲线的收敛精度 ,可能产 生过收敛现象. 于是文中首先用改进的 Snake 模型 拟合目标的边缘 ,然后用 PSO 在拟合曲线的周围搜 索 ,得到准确的目标边界. 214 向心能量 向心能量 Ecenter ( i , k) 表达式为 Ecenter ( i , k) = ( ‖vi′ - p ‖- min ( k) ) max ( k) - min ( k) . (9) max ( k) = max i′∈s ( ‖vi′ - p ‖) . min ( k) = min i′∈s ( ‖vi′ - p ‖) . 式中 : ‖vi′- p ‖为 s 范围内任意点到 p (目标内开 始选定的点) 的距离;min ( k) 为 s 范围内任意点到 p 的最小距离;max ( k) 为 s 范围内任意点到 p 的最大 距离.ε( i) 为向心能量系数. 向心能量不仅可以使曲线向凹处收敛并且可以 加快曲线的收敛速度. 3 粒子群优化算法 粒子群算法由 Kennedy 和 Eberhart [10 ] 在 1995 年提出 ,该算法模拟鸟集群飞行觅食的行为 ,通过鸟 之间的集体协作使群体达到最优目的. PSO 算法属 于进化算法的一种 ,和遗传算法类似 ,它也是从随机 解出发 ,通过迭代寻找最优解 ,它也是通过适应度来 评价解的品质. 但是它没有遗传算法的“交叉” (Crossover) 和“变异”(Mutation) 操作 ,而是通过追 随当前搜索到的最优值来寻找全局最优. 在 PSO 系 统中 ,每个备选解被称为一个“粒子”(particle) ,多 个粒子共存、合作寻优 ,每个粒子根据它自身的“经 验”和粒子群的最佳“经验”在问题空间中向更好的 位置“飞行”,搜索最优解. PSO 算法数学表示如下 : 设搜索空间为 D 维 ,总粒子数为 n. 第 i 个粒子 第 1 期 王科俊 ,等 :基于粒子群优化算法和改进的 Snake 模型的图像分割算法 ·55 ·
·56· 智能系统学报 第2卷 位置表示为向量X=(xa,xa,xD);第i个粒子 4应用粒子群的Snake模型 运动中的最优位置为P,=(P1,P2,Pn),式中 第g个粒子最优位置Pg为所有P,(i=1,2, 4.1 Snake曲线的粗收敛 中的最优：第ⅰ个粒子的位置变化率即速度向量为 首先用文中所提的改进的Snake模型进行目标 V,=(a,v2,,vo).每个粒子的位置按如下公式 轮廓的粗收敛，由于在图像能量和向心能量的作用 进行变化： 下，此收敛曲线可能产生过收敛（收敛位置在目标真 va(t+l)=w·va()+c·rand()·(pa()- 实边界内侧)，由于图像本身的特点有时也可能产生 xid(1))+crand(1)(psd(1)-xid(1)). 欠收敛（收敛位置在目标真实边界外侧）.但是通过 10) 粗收敛不仅可以减少基于粒子群Snake算法的计算 xd(t+1)=xa)+va(1+1) 量，而且可以为粒子的初始化进行很好的定位 1≤i≤n,0≤d≤D). 11) 4.2初始粒子的选取 式中：a,a为正常数，称为加速因子；rand()为 1)基于4.1粗收敛的曲线，在曲线上选取间隔 0,1]之间的随机数；w称惯性因子，w较大适于对 大致相同的n个离散点{%，M,1.在点”和 解空间进行大范围搜索，w较小适于进行小范围搜 点P(目标内一点，大约在形心附近)的连线上取m 索.第d维(1≤d≤D)的位置变化范围为 个点w.0,p.1,w,m1(式中包含{，n, [-Y maxa,Y maxa],速度变化范围为[-Vmaxa, ),这些点大致分部在目标边界的两侧，如图1 Vmaxa],迭代中若位置和速度超过边界范围则取边 所示 界值.Maurice等对上述参数进行了分析，给出了 2)选取w0,w1.,”wa.1/0≤m-1)作 PSO算法收敛的参数条件口 为粒子 粒子群初始位置和速度随机产生，然后按式 3)重复2)m次，共得到m个粒子，每个粒子所 (10)、(11)进行迭代，直至找到满意的解 含的点数都相同 PSO算法可用伪代码表示如下： 初始化粒子群； Do For每个粒子 计算其适应度； f(适应度优于粒子历史最佳值) (a)粒子取法示意图 (b)矩形放大图 用值更新历史个体最佳P； End 选取当前粒子群中最佳粒子； 图2粒子取法示意图 (当前最佳粒子优于群历史最佳粒子) Fig 2 Sketch map of selecting particle 用当前群最佳粒子更新， 4.3适应度函数 For每个粒子 目标函数选择传统Snake模型的能量函数，使 按式(10)更新粒子速度； 其极小化： 按式(11)更新粒子位置； End E= aEcune(BEome (m While最大迭代数未达到或最小误差未达到. 近几年的研究和实践表明，P$O在多维空间多 通过不断迭代选取出使上式值最小的粒子，作 峰问题寻优、动态目标寻优方面有着速度快、解质量 为曲线收敛的最后结果 高、鲁棒性好等优点 主要根据以下2点选择传统Snake模型的能量 函数作为适应度函数： 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
位置表示为向量 Xi = ( xi1 , xi2 , …, xiD ) ;第 i 个粒子 运动中的最优位置为 Pi = ( Pi1 , Pi2 , …, PiD ) ,式中 第 g 个粒子最优位置 Pg 为所有 Pi ( i = 1 , 2 , …, n) 中的最优;第 i 个粒子的位置变化率即速度向量为 Vi = ( vi1 , vi2 , …, viD ) . 每个粒子的位置按如下公式 进行变化 : vid ( t + 1) = w ·vid ( t) + c1 ·rand ( t) ·( pid ( t) - xid ( t) ) + c2 ·rand ( t) ·( pgd ( t) - xid ( t) ) . (10) xid ( t + 1) = xid ( t) + vid ( t + 1) (1 ≤i ≤n , 0 ≤d ≤D) . (11) 式中 : c1 , c2 为正常数 , 称为加速因子; rand ( ) 为 [0 ,1 ]之间的随机数; w 称惯性因子 , w 较大适于对 解空间进行大范围搜索 , w 较小适于进行小范围搜 索. 第 d 维 ( 1 ≤ d ≤ D ) 的 位 置 变 化 范 围 为 [ - X maxd , X maxd ] ,速度变化范围为[ - V maxd , V maxd ] ,迭代中若位置和速度超过边界范围则取边 界值. Maurice 等对上述参数进行了分析 , 给出了 PSO 算法收敛的参数条件[11 ] . 粒子群初始位置和速度随机产生 , 然后按式 (10) 、(11) 进行迭代 ,直至找到满意的解. PSO 算法可用伪代码表示如下 : 初始化粒子群 ; Do For 每个粒子 计算其适应度 ; If (适应度优于粒子历史最佳值) 用值更新历史个体最佳 P; End 选取当前粒子群中最佳粒子 ; If (当前最佳粒子优于群历史最佳粒子) 用当前群最佳粒子更新 ; For 每个粒子 按式(10) 更新粒子速度 ; 按式(11) 更新粒子位置 ; End While 最大迭代数未达到或最小误差未达到. 近几年的研究和实践表明 ,PSO 在多维空间多 峰问题寻优、动态目标寻优方面有着速度快、解质量 高、鲁棒性好等优点. 4 应用粒子群的 Snake 模型 411 Snake 曲线的粗收敛 首先用文中所提的改进的 Snake 模型进行目标 轮廓的粗收敛 ,由于在图像能量和向心能量的作用 下 ,此收敛曲线可能产生过收敛(收敛位置在目标真 实边界内侧) ,由于图像本身的特点有时也可能产生 欠收敛(收敛位置在目标真实边界外侧) . 但是通过 粗收敛不仅可以减少基于粒子群 Snake 算法的计算 量 ,而且可以为粒子的初始化进行很好的定位. 412 初始粒子的选取 1) 基于 411 粗收敛的曲线 ,在曲线上选取间隔 大致相同的 n 个离散点{ v0 , v1 , …, vn - 1 } . 在点 vi 和 点 P (目标内一点 ,大约在形心附近) 的连线上取 m 个点 w i ,0 , wi ,1 , …, wi , m - 1 (式中包含 { v0 , v1 , …, vn - 1 }) ,这些点大致分部在目标边界的两侧 ,如图 1 所示. 2) 选取 w0 , j , w1 , j , …, wn - 1 , j (0 ≤j ≤m - 1) 作 为粒子. 3) 重复 2) m 次 ,共得到 m 个粒子 ,每个粒子所 含的点数都相同. 图 2 粒子取法示意图 Fig12 Sketch map of selecting particle 413 适应度函数 目标函数选择传统 Snake 模型的能量函数 ,使 其极小化 : E = ∑ n i =1 [αEcurve ( i , k) +βEconnect ( i , k) + rEimage ( i , k) ]. 通过不断迭代选取出使上式值最小的粒子 ,作 为曲线收敛的最后结果. 主要根据以下 2 点选择传统 Snake 模型的能量 函数作为适应度函数 : ·56 · 智 能 系 统 学 报 第 2 卷
第1期 王科俊，等：基于粒子群优化算法和改进的Sake模型的图像分割算法 ·57 1)经过改进的Snake模型收敛后，曲线已经在 实验2：通过较复杂的大脑图像（图4）验证了本 目标真实边界的附近，此时己经不存在曲线向凹处 算法的有效性.从拟合的图像中可以很清楚的看出 收敛的问题 本算法的拟合结果更加准确.在图3中，在粗收敛时 2)图像经高斯平滑后可能使曲线过收敛，所以 各能量系数为1,1,5,0.3.在用PS0精确收敛时适 适应度函数中采用图像的一阶梯度作为图像能量. 应度方程中各能量系数为1,1,2.应用传统Snake 4.4算法的实现 模型收敛时各能量系数为1,0.8,3. 1)首先计算初始M个粒子能量E,(j=0,1, …,m-1),取能量最小的作为初始能量值（也就是 适应度的值)，将此值赋给P()作为初始全局最 优。 2)用式(10)、(11)更新每个粒子的位置，如果 (a)原始的初始化图像 (b)改进的Snake模型 v、x超过其范围取边界值」 3)计算每个粒子的适应度值！ 4)如果某个粒子的当前值优于此粒子的历史最 优值，则将当前值作为此粒子的历史最优值，当前位 置为此粒子的历史最优位置pa(). 5)比较所有粒子的最优位置，选取出最优的一 (c)改进的Snake模型粗收敛(d)PS0优化结果 个作为Pd() 6)当迭代一定次数后，适应度值和Ps则()都趋 于一定值，将Pa()作为最后的收敛结果 5 实验结果及分析 (e)传统Snake算法收敛 (f)GVF方法收敛 实验1：通过对比度较大、无噪声的图3验证了 本算法的有效性.在粗收敛时各能量系数为1,0.6， 图4实验2 2.5,1.2.在用PS0精确收敛时适应度方程中各能 Fig 4 Experiment two 实验结果分析： 量系数为1,0.6,25.应用传统Snake模型收敛时 1)改进Snake模型使曲线较好地收敛到被拟合 各能量系数为10.82 目标的凹处，但是在边界处不是很准确： 2)本算法得到更加准确的边界； 3)传统Snake无法收敛到日标的边界； 4)GVF也可以很好地收敛到目标的凹处，但易 (a)原始的初始化图像 (b)改进的Snake模型 过收敛 6结束语 (d)PSO优化结果 从以上的理论分析和试验结果中可以很清楚地 (c)改进的Snake模型粗收敛 看出本算法收敛的准确性.充分地利用了P$O具有 全局搜索能力和改进的Snake模型具有向凹处收敛 的能力，使初始化曲线可以很准确地收敛到目标的 (e)传统Snake算法收敛结果 (DGVF方法收敛结果 边界.但是本算法仍存在需要改进的地方：能量方程 图3实验1 中的能量系数需人为设定，对噪声很大的图像收敛 Fig 3 Experiment one 结果不是很准确，这些将在以后的工作中完成 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
1) 经过改进的 Snake 模型收敛后 ,曲线已经在 目标真实边界的附近 ,此时已经不存在曲线向凹处 收敛的问题. 2) 图像经高斯平滑后可能使曲线过收敛 ,所以 适应度函数中采用图像的一阶梯度作为图像能量. 414 算法的实现 1) 首先计算初始 M 个粒子能量 Ej ( j = 0 , 1 , …, m - 1) ,取能量最小的作为初始能量值 (也就是 适应度的值) ,将此值赋给 pgd ( t) 作为初始全局最 优. 2) 用式 (10) 、(11) 更新每个粒子的位置 ,如果 v、x 超过其范围取边界值. 3) 计算每个粒子的适应度值. 4) 如果某个粒子的当前值优于此粒子的历史最 优值 ,则将当前值作为此粒子的历史最优值 ,当前位 置为此粒子的历史最优位置 pid ( t) . 5) 比较所有粒子的最优位置 ,选取出最优的一 个作为 pgd ( t) . 6) 当迭代一定次数后 ,适应度值和 pgd ( t) 都趋 于一定值 ,将 pgd ( t) 作为最后的收敛结果. 5 实验结果及分析 实验 1 :通过对比度较大、无噪声的图 3 验证了 本算法的有效性. 在粗收敛时各能量系数为 1 ,016 , 215 ,112. 在用 PSO 精确收敛时适应度方程中各能 量系数为 1 ,016 ,215. 应用传统 Snake 模型收敛时 各能量系数为 1 ,018 ,2. 图 3 实验 1 Fig13 Experiment one 实验 2 :通过较复杂的大脑图像(图 4) 验证了本 算法的有效性. 从拟合的图像中可以很清楚的看出 本算法的拟合结果更加准确. 在图 3 中 ,在粗收敛时 各能量系数为 1 ,1 ,5 ,013. 在用 PSO 精确收敛时适 应度方程中各能量系数为 1 ,1 ,2. 应用传统 Snake 模型收敛时各能量系数为 1 ,018 ,3. 图 4 实验 2 Fig14 Experiment two 实验结果分析 : 1) 改进 Snake 模型使曲线较好地收敛到被拟合 目标的凹处 ,但是在边界处不是很准确 ; 2) 本算法得到更加准确的边界 ; 3) 传统 Snake 无法收敛到目标的边界 ; 4) GVF 也可以很好地收敛到目标的凹处 ,但易 过收敛. 6 结束语 从以上的理论分析和试验结果中可以很清楚地 看出本算法收敛的准确性. 充分地利用了 PSO 具有 全局搜索能力和改进的 Snake 模型具有向凹处收敛 的能力 ,使初始化曲线可以很准确地收敛到目标的 边界. 但是本算法仍存在需要改进的地方 :能量方程 中的能量系数需人为设定 ,对噪声很大的图像收敛 结果不是很准确 ,这些将在以后的工作中完成. 第 1 期 王科俊 ,等 :基于粒子群优化算法和改进的 Snake 模型的图像分割算法 ·57 ·
·58· 智能系统学报 第2卷 CHEN Yunjie,ZHAN GJianwei.Genetic algorithms ap- 参考文献： plied in snake model [J].Computer Applications,2004, [1]KASS M,WITKIN A,TERZOPULOS D.Snakes:ac- 24(5):80-81,84. tive contour models[A].In:Proceeding of the First In- [9]KENNEDYJ,EBERHART R C.Particle swarm opti- ternational Conference on Computer Vision[C].London, mization[A].Proceedings of IEEE International Confer- 1987 ence on Neural Networks[C].Perth,1995. [2]KASS M,WITKIN A,TERZOPOULOS D.Snakes: [10]EBERHART R C,SHI Y.Particle swarm optimization active contour models[J].Int'IJ Computer Vision,1988, developments,applications and resources[A].Proceed- 1(4):321-331. ings of the Congress on Evolutionary Computation[C]. [3]TSECHPENA KIS G,RAPANTZIKOS K,TSAPAT- Piscataway,2001. SOULIS N,KOLLIAS S.A snake model for object [11]MAURICE C,KENNEDYJ.The particle swarm-ex- tracking in natural sequences[J].Signal Processing:Im- plosion,stability,and convergence in a multidimension- age Communication,2004,19(3):219-238. al complex space[J].IEEE Transactions on Evolution- [4]PENGJ,ZHANGD,LIU Y.An improved Snake model ary Computation,2002,6(1):58-73. for building detection from urban aerial images[J].Pat- 作者简介： tern Recognition Letters,2005,26(5):587-595 王科俊，男，1962年生，教授，博士 [5]邱书波，王化祥，梁志伟.一种新的B-Snake算法在目标 生导师，主要研究方向为模式识别与智 轮廓跟踪中的应用U].中国图象图形学报，2005,10(5)： 能系统.中国人工智能学会理事，参加 585-589 并完成的科研项目中获得部级科技进 QIU Shubo,WAN G Huaxiang,LIANG Zhiwei.Tracking 步二等奖2项，三等奖3项，省高校科 object contour using a novel bSnake algorithm[J].Jour- 学技术一等奖1项、二等奖1项.获国 nal of Image and Graphics,2005,10(5):585-589. 家版权局软件著作权登记1项. [6]CO HEN L D.On active contour models and balloon[A]. E mail wangkejun @hrbeu.edu.cn. CV GIP,1991,53(2):211.218. [7]XU C,PRINCE PL.Snakes,shapes and gradient vector 郭庆昌，男，1979年生，硕士研究 flow[J].IEEE Trans on Image Processing,1998,1(7): 生，主要研究方向为模式识别与智能系 359.369 统、图像处理」 [8]陈允杰，张建伟.遗传算法在Snake模型中的应用U].计 算机应用，2004,24(5)：80.81,84. 1994-2009 China Academic Journal Eleetronic Publishing House.All rights reserved.http://www.cnki.net
参考文献 : [1 ] KASS M , WIT KIN A , TERZOPULOS D. Snakes: ac2 tive contour models[ A ]. In : Proceeding of the First In2 ternational Conference on Computer Vision[C]. London , 1987. [ 2 ] KASS M , WIT KIN A , TERZOPOULOS D. Snakes: active contour models[J ]. Int′IJ Computer Vision ,1988 , 1 (4) :321 - 331. [ 3 ] TSECHPENA KIS G, RAPAN TZIKOS K , TSAPA T2 SOUL IS N , KOLL IAS S. A snake model for object tracking in natural sequences[J ]. Signal Processing : Im2 age Communication ,2004 , 19 (3) :219 - 238. [4 ] PEN GJ , ZHAN G D , L IU Y. An improved Snake model for building detection from urban aerial images[J ]. Pat2 tern Recognition Letters , 2005 , 26 (5) :587 - 595. [5 ]邱书波 ,王化祥 ,梁志伟. 一种新的 B2Snake 算法在目标 轮廓跟踪中的应用[J ]. 中国图象图形学报 ,2005 ,10 (5) : 585 - 589. QIU Shubo ,WAN G Huaxiang , L IAN G Zhiwei. Tracking object contour using a novel b2Snake algorithm[J ].Jour2 nal of Image and Graphics , 2005 ,10 (5) :585 - 589. [6 ]CO HEN L D. On active contour models and balloon[ A ]. CV GIP , 1991 , 53 (2) : 211 - 218. [ 7 ]XU C , PRINCE P L. Snakes , shapes and gradient vector flow[J ]. IEEE Trans on Image Processing ,1998 ,1 (7) : 359 - 369. [8 ]陈允杰 ,张建伟. 遗传算法在 Snake 模型中的应用[J ]. 计 算机应用 ,2004 , 24 (5) :80 - 81 ,84. CHEN Yunjie , ZHAN GJianwei. Genetic algorithms ap2 plied in snake model[J ]. Computer Applications , 2004 , 24 (5) :80 - 81 ,84. [9 ] KENNED Y J , EBERHART R C. Particle swarm opti2 mization[ A ]. Proceedings of IEEE International Confer2 ence on Neural Networks[C]. Perth , l995. [10 ] EBERHART R C , SHI Y. Particle swarm optimization developments , applications and resources[A ]. Proceed2 ings of the Congress on Evolutionary Computation[ C]. Piscataway ,2001. [11 ] MAURICE C , KENN ED Y J. The particle swarm2ex2 plosion , stability , and convergence in a multidimension2 al complex space [J ]. IEEE Transactions on Evolution2 ary Computation , 2002 , 6 (1) : 58 - 73. 作者简介 : 王科俊 ,男 ,1962 年生 ,教授 ,博士 生导师 ,主要研究方向为模式识别与智 能系统. 中国人工智能学会理事 ,参加 并完成的科研项目中获得部级科技进 步二等奖 2 项 ,三等奖 3 项 ,省高校科 学技术一等奖 1 项、二等奖 1 项. 获国 家版权局软件著作权登记 1 项. E2mail :wangkejun @hrbeu. edu. cn. 郭庆昌 ,男 , 1979 年生 ,硕士研究 生 ,主要研究方向为模式识别与智能系 统、图像处理. ·58 · 智 能 系 统 学 报 第 2 卷
