基于改进蚁群算法的图像轮廓高精度分割研究

李巧兰，卢永祥，卢荣辉

(武夷学院 信息技术与实验室管理中心，福建 龙岩 354300)

为辨识和分析目标，需要将图像中的目标部分分割出来，在此基础上才可对目标进一步分析利用，由此产生了图像分割技术，即分割出图像中存在目标部分的区域的过程。因图像分割的质量对后续的分析产生直接的影响，所以分割技术算法的精度至关重要[1]。当前，国内外已经提出上千种图像分割的算法。安霆[2]提出利用遗传算法处理图像噪声，结合进化代数和个体的适应度值提高了图像分割的效率。高蕊[3]等学者提出基于蚂蚁算法提取图像的灰度、梯度和邻域特征，实现图像分割算法的外廓提取。但传统算法存在分割效率低、精度差、稳定性不佳等弊端。

针对传统算法的不足，提出了基于改进蚁群算法的图像轮廓高精度分割算法研究，首先构建一种图像分割路径几何模型，基于蚁群算法进行迭代寻优找出最短路径，并基于GPU技术修正偏差，完成对图像分割的精确计算和控制。实验结果表明，提出的算法设计路径最短、精度高、算法稳定性好。

1 一种图像轮廓目标点间距分布式算法研究

1.1 图像分割路径几何模型的构建

通常采用图像分割的图像的构造较为复杂，由曲线、圆弧、直线等多种元素组成。要准确地计算图像轮廓目标点的间距，可以采用一种分布式的计算模式提高算法的精度[4-5]。首先来构建图像轮廓目标点分割的几何模型，为图像分割设定好工作路径[6-7]。设待分割加工的图像几何轮廓由直线和圆弧等元素组成，如图1所示。

图1 图像轮廓的几何图形

如图1所示，图像轮廓由外环和2个内环组合而成，外环和内环都是由边Ei和定点Ni组合而成，那么外环可以定义为N11-N16，两个内环可以分别定义为N21-N24和N31-N32。图像轮廓分割时，要先分割内环，再分割外环[8]，比如以点N21为开始的分割点，分割后再从该点逐渐移动到其他定点，并充分考虑图像分割时对图像轮廓形变的影响[9]。

将外环定义为L1，内环分别定义为L2和L3，那么内环L2和L3之间的最短间距，可以使用两环定点之间的最短距离dij来定义[10]：

(1)

其中(xik,yik)和(xjk,yjk)分别为L2和L3定点的坐标。图像轮廓分割过程中产生的空行程是外环与内环距离及内环之间的距离的和[11]，图像轮廓分割的几何模型D可以表示为：

D=dij+dik+dik+…+dmo

(2)

图像轮廓目标点间距分布式计算的目的就是要找到使总距离Dmin最短的路径[12]。基于对最短路径的分析，构建图像轮廓分割的几何模型，此时需要找出一条确保空程最短的最优行进路径。这是一个极为复杂的过程，需要确定目标点的具体位置，并选择分割顺序[13]。不同的目标点位置和不同的分割顺序都会产生不同的空程长度[14]。假设图像的环数为n，每个环的顶点数量为m1，这时图像轮廓分割路径的条数ki可以表示为：

(3)

对于最优路径的选择问题，采用了改进蚁群算法，基于蚂蚁行进路径中遗留的信息素浓度和启发因子的变化情况，进行反复的迭代寻优找出最优的分割路径，并提高图像轮廓目标点间距的控制精度。

1.2 基于改进蚁群算法图像轮廓目标点间距分布式计算的实现

蚁群算法是一种仿生学算法，适用于路径寻优，蚁群算法易于与其他的方法相结合、鲁棒性高[15]。改进的蚁群算法，能够在图像轮廓分割过程中选择一条最短路径，并实现对图像轮廓目标点间距的最优控制。蚂蚁在觅食过程中，基于信息度浓度选择最短路径。如果路径上的信息素的浓度越大，选择这条路径的概率就越大。路径寻优的过程，如图2所示。

图2 路径寻优示意图

A点是蚁巢，F点是食物源，由于从A点到F点之间存在障碍物，因此有两条绕过障碍物的路径供选择，分别是ABCDEF和ABGHEF，其中设定ABGHEF路径中BG与HE段长度是ABCDEF路径中BC与DE段长度的2倍。

假定在蚁巢和食物源之间移动蚂蚁个体数量是200，那么在初始时刻由于没有蚂蚁个体通过，各段路径上的蚂蚁信息素浓度指标都为零。当蚂蚁开始在路径上移动时，这种行为是随机的即在ABCDEF和ABGHEF两条路径上都有蚂蚁存在。基于概率学原理，蚂蚁个体选择两条路径的概率是相等的。因此，存在于两条路径上的蚂蚁数量是相同的。蚂蚁个体在向前行进的过程中，会在沿途释放信息素，如果蚂蚁留下的单位信息素相同，根据上述设定的ABGHEF与ABCDEF路径长度，得出路径BG与HE段的信息素浓度是BC与DE段的2倍，而后再通过的蚂蚁个体就会有较大的概率选择ABCDEF路径，这样就找到了一条到达食物源的最短路径。

基于改进蚁群算法的图像轮廓高精度分割算法具有分布式特点。分布式结构[16-18]具有很强的适应性，尽管依赖于系统中的个体行为，但其中某一个个体行为的失效又不会影响系统整体的结构和功能。对于图像轮廓分割的路径优化与选择问题，采用基于改进蚁群算法的图像轮廓目标点间距计算模式，体现出了分布式算法的优势。

蚂蚁根据路径上的信息素浓度信息选择路径，路径上的信息素随着蚂蚁的移动而改变，同时随着时间的推移而挥发，设在蚁群中的蚂蚁个体的数量为a，在t时刻在路径i，j上的信息量表示为ζij(t)，bi(t)表示t时刻在路径i附近的蚂蚁个体数量，则有：

(4)

(5)

式(5)中，sij(t)为蚂蚁个体在路径i，j行进的过程中所释放的信息量、α为启发因子(对蚂蚁行进路径的选择起到了至关重要的作用)、β为期望启发因子、ξik(t)是局部路径启发函数，可以表示为：

(6)

基于仿生学的原理，蚂蚁个体在前进过程中释放的信息素的浓度会不断地增强，同时随着时间的推移，每条路径的总信息素含量也会不断地挥发，即信息素的浓度是动态可变的，t+n时刻在路径i，j上的信息素变化过程如下：

(7)

式(7)中，Δsij(t)表示信息素的增量，在初始时刻Δsij(t)为零，用常数κ表示蚂蚁行进过程中在沿途释放信息素的挥发系数，κ⊂[0,1)，那么(1-κ)即为信息素的残留系数。设lk为蚂蚁k在路径寻优时，所走过的总路程长度，τk表示蚂蚁沿路释放信息素的强度，这时Δsij(t)的求解公式为：

(8)

沿着信息素的增量路径寻优，能够找到一条最佳的路径，并能够保证图像轮廓目标点间距精度最高。经典蚁群算法的不足是迭代寻优和整个计算耗时都较长。采用GPU算法将寻优过程中的数据进行串行计算和连接，并在GPU上运行，实现对经典蚁群算法的加速。由于改进蚁群算法中的全部个体行为都具有一致性，蚂蚁个体依据相同的规则进行路径寻优、互不干扰；但蚂蚁个体之间并不直接联系，而是采用遗留信息素的形式互相协作，这样操作适用于并行运算。

采用了改进的蚁群算法，对图像轮廓目标点间距进行分布式计算，基于蚂蚁行进路径中的信息素含量来判定最优路径，并实现对图像轮廓分割的精确控制。

2 实验部分

为验证所提方法在切割路径寻优和图像轮廓分割的高精度，进行了一组仿真实验，从实际路径长度、迭代次数和图像轮廓分割精度等方面进行对比验证。

2.1 算法参数设定

基于改进蚁群算法的最优路径寻优过程受到其几何模型中各种参数的影响，各种差异化的参数组合会对算法的收敛性能、测量精度产生不同的影响。路径寻优过程中的最佳参数组合，如表1所示。

表1 基于改进蚁群算法的参数组合设定

2.2 实验结果与分析

基于所提方法，在图像轮廓分割的轮廓目标点最短路径选择方面具有明显的优势，与文献[2]方法对比，实际的分割路径曲线分别如图3和图4所示。

图3 文献[2]方法的路径

图4 所提方法路径

两种算法的路径长度统计，如表2所示。

表2 两种算法的路径统计/mm

分析图3和图4的路径及表2的路径统计，所提方法算法的路径更短、无交叉、效率更高。文章分析了基于改进蚁群算法图像轮廓高精度切割路径寻优和图像轮廓分割精度运算控制时的迭代次数变化曲线，如图5所示。

图5 图形间距精度与迭代次数的关系

如图5所示，所提方法算法在迭代300次时就能够寻找到最优路径，其迭代次数明显优于传统寻优方法。

在图像轮廓分割精度控制方面，分别采用文献[2]方法和所提方法算法进行运算，提取了两种算法下的精度测量值与理论值的数据对比结果，如表3所示。

表3 图像轮廓目标点间距精度控制对比/mm

表3的数据对比显示，所提方法更接近理论值，计算精度更高，说明目标点兼具精度的控制效果更理想。

3 结论

图像分割技术在图像识别分析领域有着十分广泛的用途。基于此设计了一种基于改进蚁群算法的图像轮廓高精度分割算法研究，利用改进蚁群算法在迭代寻优方面的优势，识别出最优路径并提高图像轮廓目标点间距控制方面的精度。