基于蚁群搜索的直线检测算法

车燕芳，于 勇

(中国船舶重工集团公司第723研究所,扬州 225001)



基于蚁群搜索的直线检测算法

车燕芳，于 勇

(中国船舶重工集团公司第723研究所,扬州 225001)

提出一种直线检测的蚁群搜索算法,以解决常用的直线检测方法抑制噪声能力不强、检测直线不连续的缺点。此算法首先进行边缘检测获取边缘点；然后利用边缘信息引导蚁群迭代搜索可能的直线边缘,根据直线的搜索长度更新蚂蚁运动路径上的信息素分布,使搜索逐渐向长直线收敛；最后,依据搜索路径的信息素遗留提取图像中的直线边缘。多组标准图像的实验表明：该算法能够有效地从图像中提取直线, 同时具有较强的噪声抑制能力。

直线检测；噪声图像；蚁群搜索；启发式搜索

0 引 言

直线是描述图像中人造目标如机场、桥梁、道路以及建筑物等的最基本特征,直线检测是图像分析和理解中的一个重要环节。传统的边缘检测采用Hough变换[1-2]的方法,把图像的边缘点按一定的函数关系映射到参数空间后根据峰值点后提取直线。

Hough变换是一种全局性的检测方法,具有较强的鲁棒性,能很好地抑制噪声。但该方法存在计算复杂、参数难于选择以及提取的直线不连续等缺点[3]。

近年来提出的基于主元分析的方法[4-5],首先对边缘点按方向进行标记,然后利用主元分析提取直线。该方法克服了Hough变换计算量大、断点多的缺点,但这种方法对噪声敏感,且在处理相交直线时存在误标记的情况。

启发式搜索[6-8]利用边缘检测后的估计图像,以幅值、相位、曲率等局部和整体信息引导直线搜索,通过多次随机搜索获得可能的直线轨迹。该算法中每一次搜索过程相互独立,且需要大量的重复搜索才能达到抑制噪声的目的,计算复杂度较高。

蚁群搜索算法[9-10](ACSA)是一种利用人工蚂蚁的正反馈特性智能搜索全局最优路径的仿生优化算法,其基本思想是利用一类人工蚂蚁并行搜索问题空间的解集,并在其搜索路径上遗留信息素进行蚂蚁之间的信息交换,每只蚂蚁会以较大概率选择信息激素较强的路径,从而导致选择最优路径的蚂蚁增多,形成正反馈过程。蚁群搜索算法具有正反馈、鲁棒性、分布式并行计算等特点。蚁群搜索算法已成功应用于调度问题、旅行商问题、图着色等经典问题中[10],在图像分割[11]、边缘提取[12-13]等图像处理领域也有较为丰富的研究成果。

本文提出了一种边缘引导的蚁群搜索算法,通过蚂蚁对边缘图像中局部直线的循环搜索,以及相应行走路径上的信息素更新,使得搜索向连续的长边缘直线收敛。

本文提出的方向性信息以及预测搜索的方法既保持了蚁群算法的多样性，又提高了收敛的速度。相对传统的算法,本文的直线提取方法在抑制噪声和增强直线连续性方面有显著提高。

1 直线检测的蚁群搜索算法

本文的算法中,蚁群搜索的引导度量信息由边缘检测结果提供,这里选取噪声抑制能力较好的Canny算子来获取可能边缘节点的幅值和相位信息。

搜索过程中,首先根据候选节点的幅度信息选择起始搜索点;然后,蚂蚁根据搜索路径的信息素分布及启发式信息从其相邻节点中按状态转移概率进行扩展搜索,直至局部直线边缘的终点；接着,沿直线方向按一定预测量继续搜索可能的扩展点,存在扩展点则继续向下搜索,如果在预测范围内没有扩展点则中止搜索；当所有蚂蚁都完成搜索后进行蚂蚁行经路径的信息素更新,继续进行下一轮搜索。通过多次循环,蚂蚁的搜索路径逐渐向长直线边缘收敛；达到指定的循环次数后,根据蚁群搜索路径中的信息素分布即可提取直线。算法流程如图1所示。

1.1 搜索起始点选择

(1)

图1 算法流程

搜索起始点选择中,首先将连续随机变量赋给每个候选起始点,然后扫描所有的实现值,寻找具有最小值的vi，对应的候选起始点ti被定为搜索起始点,其坐标为(xi,yi)。通过反复执行上述随机选择过程确定蚂蚁的搜索起始点。

根据式(1)中候选起始点ti的连续随机变量的分布,可以得到ti被选择为搜索起始点的概率pi为：

(2)

从上式不难看出像素点ti被选择为起始点的概率与该点的梯度幅值成正比。同时,由于图像中直线往往对应着长的连续边缘,会被以更大的概率选择作为搜索起始点,所以该方法对于增强直线边缘和抑制短的噪声边缘有关键作用。

1.2 节点转移方法

蚂蚁搜索过程主要感知从当前节点到其相邻节点的路径上的信息素分布,以及由该路径梯度幅值与相位构成的启发信息,利用各路径上的信息素及启发信息可计算蚂蚁转移概率。令节点(r,s)相邻节点的集合为R,蚂蚁从节点(r,s)运动到节点(i,j)∈R的转移概率为：

(3)

(4)

由于随机变量相互独立,从公式(5)可以得到(r,s)的邻域节点(i,j)被选为搜索扩展点的概率：

(5)

从上式可以看出,相邻节点中转移概率大的节点会被以更大的概率选为扩展搜索点。

1.3 启发信息

(6)

图2(b)～(e)为不同斜率下蚂蚁移动路径的方向性函数的取值情况。方向信息与α以及Δφ的关系如下式:

(7)

上式表明,当八邻域的任一方向与直线方向重合时,该方向扩展点的方向信息为1,该点被选为扩展点的概率较大；而当直线处于其他位置时,与直线方向越一致的点,其方向信息取值越高,该点被选为扩展点的概率较大。

图2 直线的方向信息

1.4 信息素更新策略

当所有蚂蚁完成一次搜索过程后, 按下式更新节点(r,s)到节点(i,j)路径上的信息素分布：

(8)

(9)

(10)

式中:c为信息素更新系数;L(k)为蚂蚁k的行走路径长度。

噪声信息的随机性使得其信息素遗留较小,而边缘直线具有连续性,信息素遗留较为突出,根据信息素的分布可有效去除噪声。

1.5 基于预测的搜索中止条件

在蚂蚁移动的每一步,首先需要判断该点是否满足中止条件,如果满足,那么搜索就到此为止,否则将选择下一个扩展点。蚂蚁搜索的中止条件为：

(1) 蚂蚁处于直线端点位置；

(2) 预测搜索的点均不处于直线上。

(11)

通过简单的分析,能获得搜索在(r,s)停止的概率：

(12)

即一点的搜索停止概率与其邻域的信息素与启发信息成反比。端点位置的邻域节点相位与端点相差较大且幅值接近于零,其停止搜索的概率较大。

本文采用预测搜索的方法以消除边缘断点的影响。其基本思想是在蚂蚁搜索到达局部直线端点时并不立即中止搜索,而是沿直线方向按一定预测量继续搜索可能的扩展点,如扩展点均不存在,则判断该点为直线终点并终止搜索。该方法可补偿由于噪声影响所产生的边缘断点,保持所提取直线的连续性。

1.6 直线提取

2 实验结果与分析

采用1组含噪声的测试图像评估算法的总体性能,所有实验程序均在Matlab7.1下运行,实验参数选取如下：候选起始点阈值fmin为边缘最大幅值的1/6,蚂蚁数目m=30,控制因子α=2,β=1，信息素更新系数c=0.01，搜索循环次数为200,边缘判断门限τmin=15。图3为加入了高斯点噪声的原始图像,图4为利用本文算法的直线检测结果。从图4可以看出,本文的算法虽然损失了部分次要的直线片段信息,但是图像中噪声得到有效抑制,主要直线信息提取完整。

图3 加入噪声的原始图像

图4 本文算法检测的边缘图像

3 结束语

本文提出了一种直线检测的蚁群搜索算法,利用蚁群搜索的正反馈特征增强直线的方向信息,以边缘信息引导蚁群搜索点的选择,同时在扩展点选择的过程中引入方向性函数增强直线边缘点的搜索概率。通过蚂蚁的迭代搜索,边缘直线点的信息素遗留逐渐增大,搜索逐渐向长直线收敛。同时,本文采用预测搜索的方法以消除边缘断点的影响,在抑制噪声的同时保持所提取直线的连续性。实验结果表明,该方法对图像中的直线检测具有噪声抑制能力强、直线信息突出等特点,能够有效地从噪声图像中提取物体的直线特征。

[1]HOUGHPVC.Methodandmeansforrecognizingcomplexpatterns[P].USPatentNo.3069654,1962-06-09.

[2]CHUNGKL,CHENTC,YANWM.Newmemory-andcomputationefficientHoughtransformfordetectinglines[J].PatternRecognition,2004,37(5):953-963.

[3]JANGJH,HONGKS.Fastlinesegmentgroupingmethodforfindinggloballymorefavorablelinesegments[J].PatternRecognition,2002,35(10):2235-2247.

[4]SHEKARBH,GURUDS,NAGABHUSHANP.Objectrecognitionthroughtheprincipalcomponentanalysisofspatialrelationshipamongstlines[C]//ACCV2006.LNCS3851,2006:170-179.

[5]LEEYS,KOOHS,JEONGCS.Astraightlinedetectionusingprincipalcomponentanalysis[J].PatternRecognitionLetters,2006,27(14):1744-1754.

[6]VENKATESWARV,CHELLAPPAR.Extractingstraightlinesinaerialimages[J].IEEETransactiononPatternAnalysisandMachineIntelligent,1992,14(11):1111-1114．

[7]FARAGAA,DELPEJ.Edgelinkingbysequentialsearch[J].PatternRecognition,1995,28(5):611-633.

[8] 刘天明,郭雷,韩军伟.独立边界自增强方法[J].自动化学报,2002,28(2):1-7.

[9]DorigoM,CAROG.Theantcolonyoptimizationmeta-heuristic[J].NewIdeasinOptimization,1999,28(3):11-32.

[10]DORIGOM,MANIEZZOV,COLORNIA.Theantsystem:optimizationbyacolonyofcooperatingagents[J].IEEETransactionsonSystems,Man,andCybernetics-PartB,1996,26(1):29-41.

[11]HANYF,SHIPF.Animprovedantcolonyalgorithmforfuzzyclusteringinimagesegmentation[J].Neurocomputing,2007,70(4-6):665-671.

[12]FERNANDESC,RAMOSV,ROSAAC.Self-regulatedartificialantcoloniesondigitalimagehabitats[J].ComputerScience,2005,2(5):463-470.

[13]NEZAMABADI-POURH,SARYAZDIS,RASHEDIE.Edgedetectionusingantalgorithm[J].SoftComput,2006,10(7):623-628.

Line Detection Algorithm Based on Ant Colony Search

CHE Yan-fang,YU Yong

(The 723 Institute of CSIC,Yangzhou 225001,China)

This paper puts forward an ant colony search algorithm of line detection,which is used to solve the problems such as weak noise restrain ability,discontinuous line detection due to common line detection algorithm.The algorithm firstly performs edge detection to fetch edge points,then uses edge information to guide ant colony to iteratively search possible line edge,updates the information element distribution in ant motion approach according to the search length of the line,in order that the search route converges on long line;finally extracts the line edge of the image according to the pheromone bequeathment of search route.Experimental results on several standard images show that:the algorithm can effectively extract the line from image and has strong ability to restrain noise.

line detection;noise image;ant colony search;heuristic search

2016-03-09

TP391

A

CN32-1413(2016)04-0063-05

10.16426/j.cnki.jcdzdk.2016.04.015