摘要：针对传统的基于图论的图像分割方法分割效果不理想的问题，提出一种新的基于图论使用蚁群算法分割图像的算法。该算法基于图论，考虑了图像的灰度信息，采用蚁群算法的基本原理分割图像，使得分割出目标更为准确。
关键词：图论；灰度；蚁群算法；
中图分类号：TP391.41 文献标识码：A 文章编号：1007—9599 （2012） 14—0000—02
一、引言
图论是离散数学的一个分支，以图为研究对象，研究顶点和边组成图形的数学问题。基于图论的图像分割是将图像分割转化为最优化图的划分问题，相比于传统的分割方法有着独特的优势。
蚁群算法是由意大利学者于上世纪90年代提出来的，是分析蚂蚁群体行为的基础上提出来的一种新的仿生类进化算法。蚁群算法在组合优化问题求解方面获得了成功的应用，引发了学者们广泛的关注。
蚁群算法逐次迭代正反馈的搜索目标，将蚁群算法引入图论中可降低算法复杂度，加快分割过程；同时蚁群算法具有较强的鲁棒性，则将蚁群算法引入图论中搜索过程中不需要进行人工的调整，同时分割效果更加准确。
二、图论和蚁群算法的基本介绍
（一）图论的基本介绍
基于图论的图像分割是将图像映射为一幅无向权图G=（V，E，W），其中V={v1，v2，…，vn}称为顶点集，V中的元素vi称为顶点，vi对应于图像中的像每个素点；E={eij}称为边集，E中的元素eij称为边，eij表示V中任意两顶点之间的连线；W={wij}称为权集，W中的元素wij称为边eij的权，wij表示顶点vi，vj之间的相似程度。
（二）蚁群算法的基本思路与步骤
蚁群算法是在分析蚂蚁群体行为的基础上提出来的。昆虫学家观察和研究发现，蚂蚁具有在没有任何提示的情况下，能够找出从其窝巢到食物源的最短路径，并且能够随着环境的变化而改变，适应性搜索新的路径，产生新的选择。这是由于：在蚂蚁搜索食物源时，能够在爬过的路径上释放信息素，使得一定范围内的其它蚂蚁能够获取信息素并影响这些蚂蚁的行为。某条路径上，信息素越多，蚂蚁选择该路径的概率越大，从而又增加了道路上的信息素浓度。
表示蚂蚁x从图像的i行j列转移到k行l列的转移概率，其中pq表示蚂蚁x能够允许转移的城市，τijkl（t）表示路径（ij，kl）上的信息素浓度，ηijkl表示路径（ij，kl）的能见度，并有 ；
调整信息素浓度的公式为：
根据上面对图论和蚁群算法的基本介绍，我们可以将蚁群算法引入图论分割方法中，得出基于图论使用蚁群算法分割图像。
具体实施步骤为：
四、基于图论的蚁群算法的改进
对于图论中，蚁群算法可以经过一系列的改进，从而使图的分割更加清晰，更好分离出目标和背景的同时计算量减小。
当图片像素点较多时，上述3基于图论的蚁群算法计算量较大，假设一幅图像有N个像素点，一群蚂蚁中有n只蚂蚁，则我们必须要重复n次步骤a到e，才能完成图像的分割。因此，可以通过降低图像的分辨率，使得图中顶点的相似取值减少来减少计算量，也适当的粗化原始图片以减少步骤a到e中的运算次数，可以大大的减少计算量。在3中仅仅考虑了图的灰度属性，可以同时考虑图的亮度，纹理等属性来改进的蚁群算法，分析图片，使得图中两顶点间相似度值更加准确。
五、结论
利用蚁群算法进行图像分割较为精确，但是本算法耗时较长，通过改进，可降低运算量同时不影响图像分割的精确度。
参考文献：
[1]贺国光.ITS系统工程导论[M].中国铁道出版社：181—184
[2]运筹学.《运筹学》教材编写组[M].清华大学出版社：251—253
[3]章毓晋.图像处理和分析[M].清华大学出版社：179—215
[4]杨燕，靳蕃，Mohamed Kamel.一种基于蚁群算法的聚类组合方法[J].铁道学报，2004，26，4：64—68
[5]M.Dorigo and T.Stutzle，“The ant colony optimization meta—heuristic：algorithms，applications and advances” in Handbook of Meta—heuristice，F.glover and g.Kochenberger，Eds.Norwell，MA：Kluwer，2002，vol.57，International Series in Operations Research&Management Science.oo：251—285
相关热词搜索： 算法 分割 图像 图论
