基于改进粒子群算法的阈值图像分割

＼　＼　＼　图形图像　文章编号：１００７—１４２３（２０１３）１８—００１８—０４　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１００７—１４２３．２０１３．１８．００５　基于改进粒子群算法的阈值图像分割　张新娟　（西安外事学院，西安７１００７７）　摘　要：针对基本粒子群算法目前存在的收敛速度过慢且容易于陷入局部极值等方面问题，提出根　据蜂群算法的领域搜索思想．改变算法中粒子领域结构　通过借鉴蜂群的领域搜索策略解　决粒子群算法陷入局部极值的问题．提高收敛速度。并将改进后粒子群算法应用于阈值图　像分割中．仿真结果表明改进算法在图像阈值分割中减少阈值的寻优时间，优化收敛精度，　提高图像处理的实时性和精度性　关键词：粒子群优化；图像分割；领域搜索策略　０　引言　易于实现．无需复杂调整等优点，自算法提出以来，在　阈值法［１－４］是图像众多分割方法中之一．该方法因　数据聚类、函数优化、模糊系统控制、神经网络训练等　其实现简单且有效而成为图像分割中使用频率最高的　领域引起极为广泛的关注　方法　该方法是通过设置一个或几个阈值将图像的灰　本文针对基本粒子群算法中存在的易于陷入局部　度级划分成几个部分．认为属于同一个部分的像素为　极值．易于出现“早熟”现象和收敛速度慢等问题，利用　同一物体．依次将整个图像在空间上划分成不同区域　粒子的领域搜索思想对基本ＰＳＯ算法进行了改进．提　这种分割方法由于易于理解，因而在医学图像分析、文　出一个新的改进ＰＳＯ算法．并将改进后的ＰＳＯ算法用　字识别、指纹识别、多目标识别等领域中有着极为广泛　于图像最佳熵阈值分割中．通过仿真实验，结果表明改　应用　其中．该方法中阈值的合理选取是阈值图像分割　进算法不仅能实现对图像的准确分割．而且与基本　的关键．选取的阈值合适与否直接影响到图像分割效　ＰＳＯ算法相比较．改进算法能够以更小的计算代价获　果的好坏。常用阈值选取方法有：最大类别方差法　得最优阈值　（Ｏｔｓｕ法）、最小误差阈值法、最佳直方图熵法等。根据　１　ＰＳＯ算法理论　Ｓｈａｏｏ等人利用形状参数与均匀性参数对标准图分割　１．１基本粒子群　结果的评估，Ｊｏｈａｎｎｓｅｎ法、０ｔｓｕ法、最佳熵法、Ｂｉｌｌｅ法　ＰＳＯ算法是根据模拟自然界中鸟群和鱼群捕食的　和Ｔｓａｉ＊矩不变法是比较理想的分割方法　所述的这几　社会行为提出的一种群体智能算法　ＰＳＯ算法是将问　种方法都涉及到寻最优值的问题．因此如何有效快速　题的所有可能解作为粒子的种群．通过种群里个体对　的选取最优阈值是图像阈值分割的关键　自身最优位置的记忆和个体之间的相互协作来实现对　粒子群优化算法［４－５］（Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉ０ｎ．　问题最优解的搜索。算法形式化描述为：假设在一个ｄ　ＰＳＯ）是由Ｋｅｎｎｅｄｙ和Ｅｂｅｒｈａｒｔ于１９９５年提出的一种　维搜索目标空间里．有ｐ个粒子组成粒子群．粒子位置　群体智能算法。由于ＰＳＯ算法设置参数少，流程简单、　表示为：ＣＰｉ￣（ＣＰ　，…，　），　１，２，…，Ｐ。粒子速度表示　收稿日期：２０１３—０５—０６　修稿日期：２０１３—０５—２６　作者简介：张新娟（１９８３－），女，陕西西安人，硕士，研究方向为图像处理、智能算法优化　＠　现代计算机２０１３．０６下　为：Ｖｉ￣（Ｖ　，…，Ｖ　），ｉ＝１，２，…，ｐ。每个粒子的飞行速　度和方向由速度和位置所决定．同时每个粒子由一个　被优化函数所决定的适应度函数来判断其解是否优　劣．每次迭代各个粒子通过动态跟踪自身个体极值　（ｐｂｅｓｔ）和种群全局极值（ｇｂｅｓｔ）来不断更新自己速度和　位置，公式如下：　【，＝ｗｘＶ　ｆ＋ｃ￣ｒｌ（ｐｂｅｓｔ　）＋ｃ２ｒ２（　ｅｓｔ　）　（１）　ｋ　＋ｌ　ｋ　＋１　＝＝　＋　（２）（ｚ　　式中，ｉ＝１，２，…，Ｐ　ｊ＝ｍ，２，…，Ｐ；ｃ　，Ｃ　为收缩因子　ｒ　，ｒ２产生［０，１］的随机数。Ｗ为惯性权重，是个非负数。　Ｗ取值较大时．算法具有较强的全局寻优能力：Ｗ取值　较小时，算法倾向于局部搜索。一般Ｗ的取值是从　一　随迭代次数的增加线性递减至Ｗ　。具体实现由如下式　子决定：Ｗ＝Ｉ一一　ｘｉｔｅｒ。其中：Ｗｍａｘ、Ｗ　分别为的　最大值和最小值：ｉｔｅｒ、Ｍａｘｉｔｅｒ分别为当前迭代次数和　最大迭代次数　粒子在解空间内不断跟踪自身个体极　值和种群全局极值．直到达到设定的最大迭代次数或　满足设定的误差标准为止。粒子在整个搜索寻找过程　中，粒子的位置限定在［　～，　］之间，每一维飞行的速　度也不能超过设定的最大速度　一。　较大则可以确　保种群的全局寻优能力，　一较小则可以保证种群的局　部寻优能力　１．２改进粒子群算法　为了杜绝算法出现“早熟”收敛，本文将蜂群算法　的领域搜索思想引入到粒子群算法中。在粒子群算法　中．对每一个粒子按照公式ｆ３）搜索种群粒子中的一部　分粒子作为该粒子的领域粒子，对其领域内的粒子进　行搜索．如果领域里的粒子个性极值优于该粒子历史　最优极值时．则让其领域中的极值作为其局部极值。　ｎｅｗ＿＿ｘ　＝　＋ｒ（　—　）　（３）　ｒ为『０，１１之间的随机数，ｉ为解向量的维数，ｋ属于　ｆ１，２，…，ｓｉｚｅ｝之间随机生成的数，随着迭代次数的增　加，（　）的值会逐渐减小，即粒子领域搜索空间逐渐　缩小．有助提高算法精度搜索。。　２　改进ＰＳＯ算法在最大熵阈值图像分割中　的应用　２．１最大熵阈值分割　将信息论中的Ｓｈａｎｎｏｎ熵概念嘲引入到图像分割　中．其依据是将图像中背景和目标分布的信息量最大　化．即通过测量图像的灰度直方图的熵．找到最佳分割　阈值。对于灰度值范围在｛０，１，…，ｌ一１｝之间的图像，每　一个灰度级出现的概率为Ｐ（ｘ）．则计算该灰度级的熵　为Ｈ—Ｐ（ｘ）ｌｎｐ（ｘ）ｄｘ，假设以灰度级ｔ分割图像，图像　中灰度级低于ｔ的像素点构成目标物体（Ｏ），灰度级高　于Ｔ的像素点构成背景（Ｂ），各个灰度级在本区域的分　布概率为［　：　０区：址（ｉ＝１，２，…，ｔ）　ｐ　Ｂ区：　Ｌ（　＝　＋ｌ，ｔ＋２，…，ｚ一１）式中的ｐ　Ｐ　１－ｐｔ　ｉ＝１　对于图像中的目标和背景区域的熵分割为：　Ｈ。（￡）＝Ｐ斟ｐ－ｅ　Ｌｎ　ｎ　箸　＝　Ｌｎ　Ｌ　ｌ＿聃４等　则熵函数定义为：　日（　）：Ｈ。（　）埘Ｂ（ｆ）：Ｌｎ（１一　）＋丝＋竽丑　ｐ￡　ｌ－Ｐｔ　（４）　当熵函数取得最大值时所对应的灰度值Ｔ　的值　就是所求的最大阈值。即：　Ｔ　＝Ａ　ｆｍａｘＨ（ｔ）｝　（５）　２．２用于图像分割的改进粒子群算法的步骤　该改进算法的基本思想是：在图像灰度空间里搜　索．使目标函数式（４）取得最大值的优化问题。考虑粒　子群算法的特点和图像最大熵阈值分割的原理．将熵　函数式（４）作为评价粒子优劣的适应度函数，通过迭代　寻找使得总熵取值最大的阈值．该阈值作为图像分割　的阈值．其具体操作步骤为：　（１）设置各参数，初始粒子群。　（２）根据公式（４）计算各个粒子的适应度函数值。　（３）根据适应度函数计算各个粒子所在领域种群　的领域极值　对各个粒子的自身个体极值和领域种群　的极值进行比较．如果领域极值优于该粒子自身个体　极值．则领域极值为该粒子个体极值。　（４）￣ｌＪ用公式（１）和（２）分别更新各粒子速度和位置。　（５）如果算法迭代次数达到最大迭代次数或系统　的适应值误差值达到了设定误差标准．算法演化结束．　此时的全局极值为所需求的最优阈值；否则转至（２）。　现代计算机　２０１３．０６下　／　Ｔｈｅ　Ｉ　ｍｐｒｏｖｅｄ　ＰＯＣＳ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｅｄｇｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ＬＩ　Ｄａｎ—ｐｉｎｇ　．　ＹＵ　Ｗｅｎ－ｊｉｎｇ　（Ｓｏｕｔｈ　Ｃｈｉｎａ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｓｏｆｔｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ，ＧＺＵ，Ｇｕａｎｇｚｈｏｕ　５１０９９０）　Ａｂｓｔｒａｃｔ：Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｏｂｔａｉｎ　ｈｉｇｈ－ｒｅｓｏｌｕｔｉｏｎ　ｉｎｆｏｒｍａｔｉｏｎ　ｆｒｏｍ　ｔｈｅ　ｌｏｗ－ｒｅｓｏｌｕｔｉｏｎ　ｉｍａｇｅ，ｔｈｅ　ｉｍａｇｅ　ｓｕｐｅｒ—　ｒｅｓｏｌｕｔｉｏｎ　ｔｅｃｈｎｏｌｏｇｙ　ｉｓ　ｕｓｕａｌｌｙ　ｕｓｅｄ　ｔｏ　ｏｂｔａｉｎ　ｈｉｇｈ—ｒｅｓｏｌｕｔｉｏｎ　ｉｍａｇｅｓ．Ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｒｅｓｅａｒｃｈ　ｏｎ　ｓｕｐｅｒ－ｒｅｓｏｌｕｔｉｏｎ　ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ，ａｎａｌｙｓｅｓ　ｔｈｅ　ｐｒｏｃｅｓｓ　ｐｒｉｎｃｉｐｌｅ　ｏｆ　ｐｒｏｊ‘ｅｃｔｉｏｎ　ｏｎｔｏ　ｃｏｎｖｅｘ　ｓｅｔｓ（ＰＯＣＳ）ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｉｔｓ　ａｄｖａｎｔａｇｅｓ　ａｎｄ　ｄｉｓａｄｖａｎｔａｇｅｓ，ｐｒｏｐｏｓｅｓ　ａ　ｋｉｎｄ　ｏｆ　ａｌｇｏ—　ｒｉｔｈｍ　ｗｉｔｈ　ｅｄｇｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｆａｃｔｏｒ．Ａｄａｐｔｓ　ｔｈｒｅｅ　ｓｐｌｉｎｅ　ｉｎｔｅｒｐｏｌａｔｉｏｎ　ａｌｇｏｒｉｈｍ，ｍｅｄｉｔａｎ　ｆｉｌｔｅｒ　ｔｏ　ｉｍｐｒｏｖｅ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ．Ｃａｒｒｉｅｓ　ｏｕｔ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｓｉｍｕｌａｔｉｏｎ　ｔｅｓｔｓ　ｂｙ　ｕｓｉｎｇ　ＭａｔＬａｂ，ｔｈｅ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｓｉｇｎｉｉｆｃａｎｔｌｙ　ｉｍｐｒｏｖｅｄ　ｉｍａｇｅｓ　ｒｅｓｏｌｕｔｉｏｎ　ａｎｄ　ｉｔ＂Ｓ　ｆｅａｓｉｂｉｌｉｔｙ．　Ｋｅｙｗｏｒｄｓ：Ｓｕｐｅ卜Ｒｅｓｏｌｕｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ；Ｒｅｃｏｎｓｔｕｃｔｒｉｏｎ；Ｐｒｏｊｅｃｔｉｏｎｓ　ｏｎｔｏ　Ｃｏｎｖｅｘ　Ｓｅｔｓ　Ｍｅｔｈｏｄ（ＰＯＣＳ）；　Ｅｄｇｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　（上接第２０页）　Ｔｈ　ｒｅｓｈｏｌｄ　Ｉ　ｍａｇｅ　Ｓｅｇｍｅｎｔａｔｉｏｎ　Ｂａｓｅｄ　ｏｎ　Ｉ　ｍｐｒｏｖｅｄ　ＰＳＯ　Ａｌｇｏｒｉｔｈｍ　ＺＨＡＮＧ　Ｘｉｎ－ｊｕａｎ　（Ｘｉ＇ａｎ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ＇ａｎ　７１００７７）　Ａｂｓｔｒａｃｔ：Ａｃｃｏｒｄｉｎｇ　ｔｏ　ｌａｒｇｅ　ａｍｏｕｎｔ　ｏｆ　ｃａｌｃｕｌａｔｉｏｎ，ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｍｉｇｈｔ　ｅａｓｉｌｙ　ｆａｌｌ　ｉｎｔｏ　ｌｏｃａｌ　ｏｐｔｉｍａｌ　ｖａｌｕｅｓ　ａｎｄ　ｌｏｎｇ　ｒｎｎｔｉｍｅ，ｗｅ　ｃｈａｎｇｅ　ｔｈｅ　ｓｔｒｕｃｔｕｒｅ　ｏｆ　ｔｈｅ　ｐａｒｔｉｃｌｅｓ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｎｅｉｇｈ—　ｂｏｕｒ　ｓｅａｒｃｈｉｎｇ　ｏｆ　ｗａｓｐ　ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ．Ａｐｐｌｉｅｓ　ｓｏｌｖｅｓ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｌｏｃａｌ　ｏｐｔｉｍａｌ　ｐｏｓｉｔｉｏｎ　ａｎｄ　ｅｎｈａｎｃｅ　ｔｈｅ　ｍｅｒｇｉｎｇ　ｓｐｅｅｄ．Ａｎ　ｉｍｐｒｏｖｅｄ　ＰＳＯ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｔｈｒｅｓｈｏｌｄ　ｉｍａｇｅ　ｓｅｇｍｅｎｔａｔｉｏｎ．　Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｓｈｏｗｓ　ｔｈａｔ　ｔｈｅ　ｒｅａｌ－ｔｉｍｅ　ａｎｄ　ｔｈｅ　ｐｒｅｃｉｓｉｏｎ　ｅｆｆｅｃｔ　ｏｆ　ｉｍａｇｅ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｉｎ　ｔｈｒｅｓｈｏｌｄ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｉｓ　ｉｍｐｒｏｖｅｄ　ｔｏｏ．　Ｋｅｙｗｏｒｄｓ：Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　０ｐｔｉｍｉｚａｔｉ０ｎ（ＰＳ０）；Ｉｍａｇｅ　Ｓｅｇｍｅｎｔａｔｉｏｎ；Ｎｅｉｇｈｂｏｕｒ　Ｓｅａｒｃｈｉｎｇ　Ｓｔｒａｔｅｇｙ　现代计算机　２０１３．０６下　固