車燕芳，于 勇

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

?

基于蟻群搜索的直線檢測(cè)算法

車燕芳，于 勇

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

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

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

0 引 言

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

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

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

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

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

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

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

1 直線檢測(cè)的蟻群搜索算法

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

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

1.1 搜索起始點(diǎn)選擇

(1)

圖1 算法流程

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

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

(2)

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

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

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

(3)

(4)

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

(5)

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

1.3 啟發(fā)信息

(6)

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

(7)

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

圖2 直線的方向信息

1.4 信息素更新策略

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

(8)

(9)

(10)

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

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

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

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

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

(2) 預(yù)測(cè)搜索的點(diǎn)均不處于直線上。

(11)

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

(12)

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

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

1.6 直線提取

2 實(shí)驗(yàn)結(jié)果與分析

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

圖3 加入噪聲的原始圖像

圖4 本文算法檢測(cè)的邊緣圖像

3 結(jié)束語

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

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