蚁群算法在二维Otsu图像分割中的应用

姜 志，戴文战

（1.浙江理工大学机械与自动控制学院，杭州310018；2.浙江工商大学信息与电子工程学院，杭州310018）

蚁群算法在二维Otsu图像分割中的应用

姜 志1，戴文战2

（1.浙江理工大学机械与自动控制学院，杭州310018；2.浙江工商大学信息与电子工程学院，杭州310018）

提出了一种基于蚁群算法和二维Otsu的图像分割方法，利用蚁群算法快速寻优的特点，求出二维Otsu图像分割的阈值分割点，对图像进行分割。根据源图像和邻域平滑后图像的灰度，以及灰度频数进行聚类。通过灰度直方图的峰值点设置精确的初始聚类中心，解决了蚁群算法运算次数多、计算量大的问题；针对具体应用，对聚类半径、信息激素和启发引导函数进行了修正。实验表明该算法速度快、划分特性好、抗噪声能力强，可以准确地分割出目标。

灰度直方图；图像分割；蚁群算法；二维Otsu算法

0 引 言

图像分割是图像识别、特征提取和自动目标识别等计算机后续处理的前提，是图像处理的最基本任务，同时也在图像处理系统中占据着重要地位。图像分割的目的是将图像中的目标和背景分割开，以便计算机视觉的后续处理。

Otsu算法利用图像的灰度直方图，根据目标与背景之间的最大方差动态地确定图像分割的门限，不需要其他先验知识，应用范围广，分割效果好，是一种有效的图像分割方法。但Otsu法存在分割效果易受噪声影响的缺点。由刘建庄等［1］提出的二维Otsu分割法和由汪海洋等［2］提出的快速二维Otsu分割法，利用图像像素点与邻近像素点的相关性，克服了一维Otsu分割抗噪性不强的缺点，但存在计算复杂运算时间长的缺点。

蚁群算法（ant colony optimization）又称蚂蚁算法，是20世界90年代发展起来的一种模仿蚂蚁群体性行为的智能化算法。基于蚁群算法的聚类分析，将数据视为具有不同属性的蚂蚁，将数据聚类的过程看作蚂蚁寻找食物的过程。在寻找食物的过程中，蚂蚁会在经过的路径上释放信息素，后面的蚂蚁会选择走信息素强的路径，这样信息素强的路径上蚂蚁越来越多，信息素也越来越多，而信息素弱的路径上蚂蚁越来越少，信息素也越来越少，最终所有蚂蚁都选择这条信息素最多的路径，即最优路径。蚁群算法正是利用蚁群聚类寻优的原理，实现快速寻优［3-4］。一幅图像中包括目标、边界、背景和噪声等内容，寻找出体现这些内容之间区别的特征量，对于后继的分类过程至关重要［5］，蚁群算法已在图像分割等很多领域获得应用。王爽等［6］提出的基于蚁群算法的一维Otsu分割方法，正是利用了蚁群算法快速寻优的特点实现了图像的快速分割。由于图像像素点的灰度值仅仅反映像素灰度级的幅值大小，并没有反映出像素与邻域空间的相关信息，因此基于一维Otsu的分割方法具有抗噪性不强的缺点［7］。为此本文将蚁群算法与二维Otsu相结合的图像分割方法。

本文在二维Otsu方法的基础上将蚁群算法应用于阈值选取，利用蚁群算法聚类快速寻优的特点［8］，克服二维Otsu方法遍历搜索图像的每个像素点从而导致计算复杂、运算时间长的缺点，降低了计算复杂度，且基于二维的Otsu分割方法即反映了像素点的灰度分布又体现了像素点与其邻域空间内其他像素点的相关性，提高了分割时的抗噪性，因此本文方法实现了图像快速分割的同时又克服了一维Otsu分割方法抗噪性不足的缺点，为计算机视觉的后续处理提供了基础。

1 二维Otsu图像分割的算法

二维Otsu算法是在一维Otsu算法上发展起来的，利用原图像像素点的灰度值与邻域平滑后图像像素点的灰度值构建二维灰度直方图，克服了一维Otsu算法抗噪性不强的缺点［9-11］。其原理为：设原始图像f（x，y）是灰度级为的图像，计算每个像素点n×n邻域的平均灰度值，得到邻域平滑图像g（x，y）。对于图像中的任何一个像素，构成了一个二元组：像素灰度值和邻域平均灰度值。设表示图像f中像素灰度值为i、邻域平均灰度值为j的像素点的个数，那么可得到该图像的二维灰度直方图，可以定义相应的联合密度：

目标部分和背景部分对应的均值矢量分别为¯u0和：

二维直方图的总体均值矢量为：

由于远离直方图对角线的pi，j为零［12］，故二维Otsu阈值分割法可以忽略远离对角线的像素点，则可得到类间离散测度：

最佳阈值（s′，t′）满足：

由于s、t分别对应灰度阈值和邻域平均灰度阈值，故其最佳阈值分别满足下式［13］：

由上式可知，一个二元函数SB（s，t）的最优解，可以分解为求两个一元函数最优解的和，即：

2 蚁群算法

本文的分割方法是基于图像的灰度直方图，利用像素的灰度值、邻域平均灰度值和灰度值的频数。基于蚁群算法的二维Otsu分割方法即利用了蚁群算法快速寻优的特点又克服了一维Otsu算法抗噪性不强的缺点，在图像分割中取得了很好的分割效果。将蚁群算法应用于聚类问题中，其主要思想是：将图像中各个像素点的灰度值看作一只蚂蚁，将蚂蚁分别聚集到j个聚类中心cj（j=1，2，…，k）的过程。设聚类半径为R，t时刻蚂蚁i到聚类中心cj的路径上含有的信息素的浓度为phi，j（t），蚂蚁与聚类中心的加权欧氏距离为di，j，启发式引导函数为υi，j，启发式引导函数表示蚂蚁i转移至聚类中心cj的期望程度，信息素与启发式引导函数在路径选择中的作用权重为a、b，设第i个蚂蚁与聚类中心cj之间的吸引力为Ni，j，第i个蚂蚁选择聚类中心cj的概率为pi，j

［14］。

其中，S=｛Xs｜dsj≤R，s=1，2，…N｝为可行路径集合，式（12）中的pk为加权因子，pk根据各分量对聚类的影响程度来设定。随着蚂蚁寻找目标的过程，各条路径上经过蚂蚁的数量将发生变换，因此各路径上含有的信息激素的浓度也将发生变化，根据式（16）和式（17）对各路径上的信息量进行调整：

式（16）中q为信息素浓度随着蚂蚁寻找聚类中心过程的时间残留系数。式（17）中Δphi，j为聚类过程中蚂蚁i到聚类中心cj所走路径上的信息激素浓度的增量；Q为蚂蚁的信息常量；Lj为蚂蚁i在本次聚类过程中从起始点到聚类中心走过的路程。

3 基于蚁群聚类算法实现二维Otsu的快速分割

3.1 基于蚁群算法的图像聚类分割

3.1.1 聚类中心

在蚁群算法中蚂蚁行走是具有盲目性和随机性的，为了减少蚂蚁行走过程中的盲目性和随机性，本文以原始图像和邻域平滑后图像的灰度直方图为基础，选择灰度直方图的各个峰值点作为初始聚类中心，同时统计初始聚类中心的个数，这样可以将所有像素之间的大量循环计算转化为各个像素与少数几个峰值点之间的计算。采用灰度直方图的峰值点作为初始聚类中心也可以引导蚂蚁直奔聚类中心，减少了蚂蚁寻找食物的过程，从而减少了计算量。

3.1.2 引导函数

引导函数，是问题本身提供的先验信息，代表第i个蚂蚁选择聚类中心cj的期望程度，即第i个蚂蚁寻找聚类中心j的所经过的路径的能见度。在蚁群算法中每个蚂蚁是否趋向于某一聚类中心，不仅取决于路径上含有的信息激素的浓度，还取决于考虑引导函数。本文算法的引导函数为：

式中di，j代表路径的长度，即数据与聚类中心的相似度。

3.1.3 聚类半径

传统的蚁群算法往往是通过分阶段的局部搜索来获得全局最优。由于蚂蚁寻找聚类中心的过程要受到聚类半径的限制，超出聚类半径R的蚁群不能加入寻找聚类中心的聚类过程，这样既耗费时间又容易使聚类陷入局部最优。为了克服以上问题本算法选择原始图像和邻域平滑后图像的灰度直方图峰值点作为初始聚类中心，使初始聚类中心就在实际聚类中心的附近，蚂蚁直奔聚类中心，不存在受聚类半径影响问题。

3.1.4 信息素更新

将蚂蚁搜索行为集中到最优解附近，可以提高解的质量和收敛速度，从而改进算法的性能。但是这种搜索方式会使算法过早收敛而出现早熟现象，为了克服这种问题，本文采用最大-最小蚂蚁系统（MAX-MIN ant system，MMAS）方法［15］调整信息素，限制各条路径上的信息激素的浓度在区间［τmin，τmax］之内，将超出这个区间的值限制为信息激素浓度允许区间上下限的值，从而有效地避免了某条路径上的信息激素的浓度远超过其他路径而造成的所有蚂蚁都聚集到同一条路径上，导致算法不再扩散，加快收敛速度。具体做法为：首先，将初始化信息量设置为最大值，τi，j（t）=c=τmax。其次，每一次聚类循环后，只有找到最短路径到达聚类中心的蚂蚁才能在其所经过的路径上释放信息激素。即

最后，将τi，j（t），限定在［τmin，τmax］之间。即如果τi，j≤τmin，则τi，j=τmin；如果τi，j≥τmax，则τi，j=τmax。

3.2 算法实现步骤

step 1：对a、b、q、τmin、τmax、R等参数值进行初始化。

step 2：求源图像及邻域平滑后图像的灰度直方图，找出各个灰度直方图的峰值点的灰度值，并把与这些峰值点具有相同灰度值的所有像素点作为初始聚类中心。

step 3：计算所有聚类中心的频数，判断边界、噪声、目标和背景。

step 4：将式（11）选为适应度函数，确定像素Xr到不同聚类中心cj的相似度di，j。根据式（18）计算引导函数。

step 5：按照从四周向中心的顺序选择蚂蚁，开始聚类，据式（15）计算每个蚂蚁选择聚类中心的概率，选择概率最大的路径。

step 6：调整路径上含有的信息激素量，并将具有相同聚类中心灰度值的连通区域合并。

step 7：如果所有蚂蚁都聚类完毕，结束循环，输出分割阈值，利用二维Otsu法对图像进行分割，否则转入step4。

4 结果及分析

为了验证本文方法的有效性，本文选择256× 256的Lena图像为源图像，选择加入噪声的Lena图像为分割对象，如图1所示，为原始的Lena图像和加噪声的Lena图像，图像的灰度级为256，在Win7 PC上采用MATLAB仿真系统进行试验。蚁群规模为30，最大迭代次数200，取R=10，a=b= 0.9，q=0.85。实验结果如图2所示，分别为二维Otsu分割效果图和本文分割方法效果图。由实验结果可知，一维Otsu法分割的图像受噪声影响，分割效果差，本文分割方法与二位Otsu分割方法分割具有相同灰度分割阈值和邻域灰度分割阈值，取得了相同的分割效果，但基于二位Otsu分割方法的分割时间为0.930 67 s，而本文方法的分割时间为0.525 39 s，由此可知虽然本文方法与Otsu分割方法分割效果相同，但本文方法在运算时间上明显较二维Otsu分割方法少，寻优速度更快，有效地减少了分割时间，提高了分割效率，实验结果证实了本文方法的可行性和有效性。

图1 实验原始图像

图2 实验分割图像

5 总 结

Otsu阈值分割方法是一种分割效好、实现简单的阈值分割方法，二维Otsu阈值分割方式克服了一维Otsu分割方法抗噪声能力弱的缺点。蚁群算法作为一种新兴的优化算法，将其应用于图像阈值分割时，缩短了寻找阈值的时间。本文将蚁群算法应用于二维Otsu图像分割中，实现了图像的快速分割的同时又兼具了二维Otsu图像分割抗噪性强、分割效果好的优点，提高了运算效率，减少了分割时间，能够为实施监控系统提供快速有效的分割方法，也为大量的计算机图像分割提供了可行性方法，提高分割效率，缩短工作时间。因此本文方法在计算机视觉系统中、实时监控系统、图像理解系统、机动目标跟踪系统中有着广阔的应用前景。但本文方法在提高二维Otsu分割速度的同时，并没有提高分割的效果，这点在以后的研究中有待进一步的改进。

［1］刘建庄，栗文清.灰度图像的二维Otsu自动阈值分割法［J］.自动化学报，1993，19（1）：101-105.

［2］汪海洋，潘德炉，夏德深.二维Otsu自适应阈值选取算法的快速实现［J］.自动化学报，2007，33（9）：968-971.

［3］Dorigo M，Gambardella L M.Ant colony system：a cooperative learning approach to the traveling salesman problem［J］.IFFF Trans on Fvolutionary Computation，1997，1（1）：53-66.

［4］宋世杰，刘高峰，周忠友，等.于改进蚁群算法求解最短路径和TSP问题［J］.计算机技术与发展.2010（4）：144-147.

［5］白 杨，孙 跃，王 君，等.基于动态自适应蚁群算法的MRI图像分割［J］.计算机科学，2008，35（12）：226-229.

［6］王 爽，黄友锐，李 冬.基于蚁群算法的改进Otsu理论的图像多阈值分割［J］.微计算机应用，2008，3（3）：25-28.

［7］Wang L，Duan H C，Wang J L.A fast algorithm for three-dimensional Otsu's thresholding method［J］.IFFF International Symposium on IT in Medicine and Fducation，2008，2（8）：136-140.

［8］Chen Y F，Liu Y S，Fattah C A.HDACC：a heuristic density-based ant colony clustering algorithm［C］// IFFF/W IC/ACM International Conference on Intelligent Agent Technology.2004，397-400.

［9］郝颖明，朱 枫.二维Otsu自适应阈值的快速算法［J］.中国图象图形学报，2005，10（4）：484-488.

［10］唐英干，刘 冬，关新平.基于粒子群和二维Otsu方法的快速图像分割［J］.控制与决策，2007，22（2）：202-205.

［11］范九伦，赵 凤.灰度图像的二维Otsu曲线阈值分割法［J］.电子学报，2007，35（4）：751-755.

［12］吴一全，樊 军，吴诗婳.改进的二维Otsu法阈值分割快速迭代算法［J］.电子测量与仪器学报，2011，25（3）：218-225.

［13］胡 敏，李 梅，汪荣贵.改进的Otsu算法在图像分割中的应用［J］.电子测量与仪器学报，2010，24（5）：443-449.

［14］杨海峰，侯朝祯.基于二维灰度直方图的蚁群图像分割［J］.激光与红外，2005，35（8）：614-617.

［15］Stutzle T，Hoos H H.MAX-MIN ant system［J］.Future Generation Computer Systems，2000，16（9）：889-914.

AppIication of Ant CoIony AIgorithm in Two-DimensionaI Otsu Image Segmentation

JIANGZhi1，DAI Wen-zhan2
（1.School of Mechanical Fngineering&Automation，Zhejiang Sci-Tech University，Hangzhou 310018；2.School of Information and Flectronic Fngineering，Zhejiang Gongshang University，Hangzhou 310018，China）

This pape proposes an image segmentation method based on ant colony algorithm and twodimensional Otsu and figures out threshold segmentation point of two-dimensional Otsu image to segment the image.Clustering is conducted according to source image，image grayscale after neighbor smoothing and grayscale frequency.The problems of ant colony algorithm（i.e.many operation times and large amount of calculation）are solved by using the peak point of gray histogram to set precise initial clustering center.According to the specific application，this paper corrects the cluster radius，pheromones and enlightening guiding function.The experiments show that the algorithm is fast and can accurately segment the target，with excellent segmentation property and strong anti-noise ability.

gray histogram；image segmentation；ant colony optimization；two-dimensional Otsu algorithm

TP273.2

A

（责任编辑：康 锋）

1673-3851（2014）04-0434-05

2013-11-06

国家自然科学基金（61374022）；国家高新技术研究发展项目（2009AA04Z139）

姜 志（1988-），男，辽宁辽阳人，硕士研究生，主要从事图像处理等方面的研究。

戴文战，F-mail：dwzhan@zstu.edu.cn