基于蟻群搜索的直線檢測算法

車燕芳，于 勇

(中國船舶重工集團(tuán)公司第723研究所,揚州 225001)

?

基于蟻群搜索的直線檢測算法

車燕芳，于 勇

(中國船舶重工集團(tuán)公司第723研究所,揚州 225001)

提出一種直線檢測的蟻群搜索算法,以解決常用的直線檢測方法抑制噪聲能力不強(qiáng)、檢測直線不連續(xù)的缺點。此算法首先進(jìn)行邊緣檢測獲取邊緣點；然后利用邊緣信息引導(dǎo)蟻群迭代搜索可能的直線邊緣,根據(jù)直線的搜索長度更新螞蟻運動路徑上的信息素分布,使搜索逐漸向長直線收斂；最后,依據(jù)搜索路徑的信息素遺留提取圖像中的直線邊緣。多組標(biāo)準(zhǔn)圖像的實驗表明：該算法能夠有效地從圖像中提取直線, 同時具有較強(qiáng)的噪聲抑制能力。

直線檢測；噪聲圖像；蟻群搜索；啟發(fā)式搜索

0 引 言

直線是描述圖像中人造目標(biāo)如機(jī)場、橋梁、道路以及建筑物等的最基本特征,直線檢測是圖像分析和理解中的一個重要環(huán)節(jié)。傳統(tǒng)的邊緣檢測采用Hough變換[1-2]的方法,把圖像的邊緣點按一定的函數(shù)關(guān)系映射到參數(shù)空間后根據(jù)峰值點后提取直線。

Hough變換是一種全局性的檢測方法,具有較強(qiáng)的魯棒性,能很好地抑制噪聲。但該方法存在計算復(fù)雜、參數(shù)難于選擇以及提取的直線不連續(xù)等缺點[3]。

近年來提出的基于主元分析的方法[4-5],首先對邊緣點按方向進(jìn)行標(biāo)記,然后利用主元分析提取直線。該方法克服了Hough變換計算量大、斷點多的缺點,但這種方法對噪聲敏感,且在處理相交直線時存在誤標(biāo)記的情況。

啟發(fā)式搜索[6-8]利用邊緣檢測后的估計圖像,以幅值、相位、曲率等局部和整體信息引導(dǎo)直線搜索,通過多次隨機(jī)搜索獲得可能的直線軌跡。該算法中每一次搜索過程相互獨立,且需要大量的重復(fù)搜索才能達(dá)到抑制噪聲的目的,計算復(fù)雜度較高。

蟻群搜索算法[9-10](ACSA)是一種利用人工螞蟻的正反饋特性智能搜索全局最優(yōu)路徑的仿生優(yōu)化算法,其基本思想是利用一類人工螞蟻并行搜索問題空間的解集,并在其搜索路徑上遺留信息素進(jìn)行螞蟻之間的信息交換,每只螞蟻會以較大概率選擇信息激素較強(qiáng)的路徑,從而導(dǎo)致選擇最優(yōu)路徑的螞蟻增多,形成正反饋過程。蟻群搜索算法具有正反饋、魯棒性、分布式并行計算等特點。蟻群搜索算法已成功應(yīng)用于調(diào)度問題、旅行商問題、圖著色等經(jīng)典問題中[10],在圖像分割[11]、邊緣提取[12-13]等圖像處理領(lǐng)域也有較為豐富的研究成果。

本文提出了一種邊緣引導(dǎo)的蟻群搜索算法,通過螞蟻對邊緣圖像中局部直線的循環(huán)搜索,以及相應(yīng)行走路徑上的信息素更新,使得搜索向連續(xù)的長邊緣直線收斂。

本文提出的方向性信息以及預(yù)測搜索的方法既保持了蟻群算法的多樣性，又提高了收斂的速度。相對傳統(tǒng)的算法,本文的直線提取方法在抑制噪聲和增強(qiáng)直線連續(xù)性方面有顯著提高。

1 直線檢測的蟻群搜索算法

本文的算法中,蟻群搜索的引導(dǎo)度量信息由邊緣檢測結(jié)果提供,這里選取噪聲抑制能力較好的Canny算子來獲取可能邊緣節(jié)點的幅值和相位信息。

搜索過程中,首先根據(jù)候選節(jié)點的幅度信息選擇起始搜索點;然后,螞蟻根據(jù)搜索路徑的信息素分布及啟發(fā)式信息從其相鄰節(jié)點中按狀態(tài)轉(zhuǎn)移概率進(jìn)行擴(kuò)展搜索,直至局部直線邊緣的終點；接著,沿直線方向按一定預(yù)測量繼續(xù)搜索可能的擴(kuò)展點,存在擴(kuò)展點則繼續(xù)向下搜索,如果在預(yù)測范圍內(nèi)沒有擴(kuò)展點則中止搜索；當(dāng)所有螞蟻都完成搜索后進(jìn)行螞蟻行經(jīng)路徑的信息素更新,繼續(xù)進(jìn)行下一輪搜索。通過多次循環(huán),螞蟻的搜索路徑逐漸向長直線邊緣收斂；達(dá)到指定的循環(huán)次數(shù)后,根據(jù)蟻群搜索路徑中的信息素分布即可提取直線。算法流程如圖1所示。

1.1 搜索起始點選擇

(1)

圖1 算法流程

搜索起始點選擇中,首先將連續(xù)隨機(jī)變量賦給每個候選起始點,然后掃描所有的實現(xiàn)值,尋找具有最小值的vi，對應(yīng)的候選起始點ti被定為搜索起始點,其坐標(biāo)為(xi,yi)。通過反復(fù)執(zhí)行上述隨機(jī)選擇過程確定螞蟻的搜索起始點。

根據(jù)式(1)中候選起始點ti的連續(xù)隨機(jī)變量的分布,可以得到ti被選擇為搜索起始點的概率pi為：

(2)

從上式不難看出像素點ti被選擇為起始點的概率與該點的梯度幅值成正比。同時,由于圖像中直線往往對應(yīng)著長的連續(xù)邊緣,會被以更大的概率選擇作為搜索起始點,所以該方法對于增強(qiáng)直線邊緣和抑制短的噪聲邊緣有關(guān)鍵作用。

1.2 節(jié)點轉(zhuǎn)移方法

螞蟻搜索過程主要感知從當(dāng)前節(jié)點到其相鄰節(jié)點的路徑上的信息素分布,以及由該路徑梯度幅值與相位構(gòu)成的啟發(fā)信息,利用各路徑上的信息素及啟發(fā)信息可計算螞蟻轉(zhuǎn)移概率。令節(jié)點(r,s)相鄰節(jié)點的集合為R,螞蟻從節(jié)點(r,s)運動到節(jié)點(i,j)∈R的轉(zhuǎn)移概率為：

(3)

(4)

由于隨機(jī)變量相互獨立,從公式(5)可以得到(r,s)的鄰域節(jié)點(i,j)被選為搜索擴(kuò)展點的概率：

(5)

從上式可以看出,相鄰節(jié)點中轉(zhuǎn)移概率大的節(jié)點會被以更大的概率選為擴(kuò)展搜索點。

1.3 啟發(fā)信息

(6)

圖2(b)～(e)為不同斜率下螞蟻移動路徑的方向性函數(shù)的取值情況。方向信息與α以及Δφ的關(guān)系如下式:

(7)

上式表明,當(dāng)八鄰域的任一方向與直線方向重合時,該方向擴(kuò)展點的方向信息為1,該點被選為擴(kuò)展點的概率較大；而當(dāng)直線處于其他位置時,與直線方向越一致的點,其方向信息取值越高,該點被選為擴(kuò)展點的概率較大。

圖2 直線的方向信息

1.4 信息素更新策略

當(dāng)所有螞蟻完成一次搜索過程后, 按下式更新節(jié)點(r,s)到節(jié)點(i,j)路徑上的信息素分布：

(8)

(9)

(10)

式中:c為信息素更新系數(shù);L(k)為螞蟻k的行走路徑長度。

噪聲信息的隨機(jī)性使得其信息素遺留較小,而邊緣直線具有連續(xù)性,信息素遺留較為突出,根據(jù)信息素的分布可有效去除噪聲。

1.5 基于預(yù)測的搜索中止條件

在螞蟻移動的每一步,首先需要判斷該點是否滿足中止條件,如果滿足,那么搜索就到此為止,否則將選擇下一個擴(kuò)展點。螞蟻搜索的中止條件為：

(1) 螞蟻處于直線端點位置；

(2) 預(yù)測搜索的點均不處于直線上。

(11)

通過簡單的分析,能獲得搜索在(r,s)停止的概率：

(12)

即一點的搜索停止概率與其鄰域的信息素與啟發(fā)信息成反比。端點位置的鄰域節(jié)點相位與端點相差較大且幅值接近于零,其停止搜索的概率較大。

本文采用預(yù)測搜索的方法以消除邊緣斷點的影響。其基本思想是在螞蟻搜索到達(dá)局部直線端點時并不立即中止搜索,而是沿直線方向按一定預(yù)測量繼續(xù)搜索可能的擴(kuò)展點,如擴(kuò)展點均不存在,則判斷該點為直線終點并終止搜索。該方法可補(bǔ)償由于噪聲影響所產(chǎn)生的邊緣斷點,保持所提取直線的連續(xù)性。

1.6 直線提取

2 實驗結(jié)果與分析

采用1組含噪聲的測試圖像評估算法的總體性能,所有實驗程序均在Matlab7.1下運行,實驗參數(shù)選取如下：候選起始點閾值fmin為邊緣最大幅值的1/6,螞蟻數(shù)目m=30,控制因子α=2,β=1，信息素更新系數(shù)c=0.01，搜索循環(huán)次數(shù)為200,邊緣判斷門限τmin=15。圖3為加入了高斯點噪聲的原始圖像,圖4為利用本文算法的直線檢測結(jié)果。從圖4可以看出,本文的算法雖然損失了部分次要的直線片段信息,但是圖像中噪聲得到有效抑制,主要直線信息提取完整。

圖3 加入噪聲的原始圖像

圖4 本文算法檢測的邊緣圖像

3 結(jié)束語

本文提出了一種直線檢測的蟻群搜索算法,利用蟻群搜索的正反饋特征增強(qiáng)直線的方向信息,以邊緣信息引導(dǎo)蟻群搜索點的選擇,同時在擴(kuò)展點選擇的過程中引入方向性函數(shù)增強(qiáng)直線邊緣點的搜索概率。通過螞蟻的迭代搜索,邊緣直線點的信息素遺留逐漸增大,搜索逐漸向長直線收斂。同時,本文采用預(yù)測搜索的方法以消除邊緣斷點的影響,在抑制噪聲的同時保持所提取直線的連續(xù)性。實驗結(jié)果表明,該方法對圖像中的直線檢測具有噪聲抑制能力強(qiáng)、直線信息突出等特點,能夠有效地從噪聲圖像中提取物體的直線特征。

[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] 劉天明,郭雷,韓軍偉.獨立邊界自增強(qiáng)方法[J].自動化學(xué)報,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