任 亮,徐志剛,趙祥模,周經(jīng)美

(長安大學(xué)信息工程學(xué)院,西安710064)

基于Prim最小生成樹的路面裂縫連接算法

任 亮,徐志剛,趙祥模,周經(jīng)美

(長安大學(xué)信息工程學(xué)院,西安710064)

在利用數(shù)字圖像技術(shù)檢測路面裂縫時,由于部分裂縫過窄或被陰影遮擋或被灰塵填充,導(dǎo)致檢測出的裂縫目標不連續(xù),嚴重影響后續(xù)的裂縫參數(shù)測量和評價。為此,提出一種基于Prim最小生成樹的路面裂縫連接算法。利用屋脊邊緣檢測方法識別所有的可疑裂縫目標,運用裂縫形狀特征去除斑點或塊狀噪聲,實現(xiàn)裂縫的粗定位。在此基礎(chǔ)上,通過形態(tài)學(xué)方法提取粗定位裂縫片段的端點,利用Prim算法構(gòu)造最小生成樹實現(xiàn)路面裂縫片段端點的連接,同時使用裂縫的方向和對比度特征去除連接中的強制偽連接;在連接的基礎(chǔ)上對裂縫進行填充和增強,得到完整的裂縫分割目標。對200幅路面圖像進行算法測試,應(yīng)用Hausdorff距離對多種算法的分割性能進行評估,實驗結(jié)果表明,該算法能明顯提高裂縫檢測目標的連續(xù)性,其檢測準確率比灰度直方圖等算法高出6個～13個百分點。

交通工程;路面養(yǎng)護;裂縫檢測;Prim最小生成樹;裂縫連接;Hausdorff距離

1 概述

截至2012年底我國高速公路總里程達9.56萬公里,隨著高速公路通車時間的增長,路面破損養(yǎng)護問題逐漸凸顯出來。路面破損檢測是路面破損養(yǎng)護的重要環(huán)節(jié),能為道路資產(chǎn)信息管理、道路設(shè)施和道路性能評估、道路壽命預(yù)測等提供有力數(shù)據(jù)支持,對道路養(yǎng)護至關(guān)重要[1]。自20世紀80年代以來,歐美等發(fā)達國家將現(xiàn)代光學(xué)技術(shù)和計算機技術(shù)相結(jié)合,先后開發(fā)了基于激光測距和數(shù)字圖像處理的多功能檢測車[2],這種檢測車具有檢測效率高、人為因素少、不影響交通的優(yōu)點,在路面檢測中得到了越來越多的應(yīng)用,我國在這方面雖起步較晚,但是發(fā)展迅速,目前已接近世界先進水平。由于路面裂縫檢測算法還不夠成熟,現(xiàn)有的路面自動檢測系統(tǒng)很大程度上還是采用自動采集與人工識別的方式進行工作。由于路面圖像數(shù)量巨大,人工檢測效率,檢測結(jié)果客觀性差,開發(fā)全自動的高性能路面裂縫識別算法仍然迫在眉睫。

文獻[3]指出路面損壞狀況指數(shù)(PCI)是評價路面損壞程度的重要指標,其主要由瀝青路面破損率(DR)得出。而路面裂縫的種類、面積、長寬等參數(shù)直接影響瀝青路面破損率的計算。國內(nèi)外相關(guān)領(lǐng)域的學(xué)者對基于圖像的路面裂縫自動檢測算法進行了廣泛的研究,多種裂縫檢測算法和理論[4]相繼被提出。目前的研究算法主要分為4類:(1)基于邊緣檢測的方法[5];(2)基于灰度統(tǒng)計的方法[6];(3)基于分塊分析的方法[7];(4)基于幾何分析的方法[8];這些算法也對部分裂縫取得了較好的檢測效果。然而這些方法沒有對路面裂縫進行連接,并未表達出真實的裂縫的完整骨架結(jié)構(gòu)[9]。路面裂縫連接算法對路面裂縫進行連接使得裂縫更加完整、連續(xù),從而使得出的裂縫參數(shù)更加準確,進而能更加客觀地評價路面破損程度。文獻[10]針對路面裂縫對比度低、連續(xù)性差等特點,提出了利用目標點最小生成樹的路面裂縫檢測,但其對大尺度、互相鄰近及交叉的復(fù)雜裂縫(龜裂)效果不理想。

2 本文多功能道路檢測系統(tǒng)

本文在前人研究的基礎(chǔ)上,提出一種基于Prim最小生成樹的路面裂縫連接算法。該算法首先對路面裂縫進行屋脊邊緣檢測,并用裂縫特征去除檢測后的干擾,實現(xiàn)裂縫粗定位;然后用圖論中的最小生成樹來表達粗定位后裂縫骨架之間的連續(xù)性,對裂縫使用Prim算法構(gòu)造最小生成樹實現(xiàn)路面裂縫的連接,同時使用裂縫特征去除連接中的強制錯誤連接;最后在連接的基礎(chǔ)上對裂縫進行填充和增強。

本文采用如圖1所示的自主開發(fā)道路綜合信息采集車來獲取路面圖像,在該系統(tǒng)中,攝像機光軸方向垂直路面,其分辨率為4 096×1 024像素,覆蓋寬度為一個車道(約4 m),長度為1 m,為了便于后期處理,本文將其分割為4幅分辨率為1 024×1 024像素的圖像,每個像素約代表1 mm2的路面。

圖1 多功能道路檢測車示意圖

3 路面裂縫的粗定位

3.1 基于屋脊邊緣的路面裂縫檢測

瀝青路面裂縫邊緣為屋脊邊緣,屋脊邊緣的極值點位置與其剖面上一維信號的一階導(dǎo)數(shù)零點和二階導(dǎo)數(shù)極值點對應(yīng)[11]。高斯函數(shù)對一維信號做卷積運算,相當于對該信號做高斯濾波,高斯函數(shù)的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)與一維信號進行卷積相當于該信號的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)與高斯函數(shù)進行卷積,高斯導(dǎo)數(shù)濾波器示意圖如圖2所示。

圖2 高斯導(dǎo)數(shù)濾波器示意圖

然后用構(gòu)造的濾波器分別與路面圖像的每行和每列進行卷積,通過每行和每列的一階導(dǎo)數(shù)零點和二階導(dǎo)數(shù)強度及像素點的灰度值選出屋脊邊緣極值點。然后對篩選出的行屋脊邊緣極值點圖像和列屋脊邊緣極值點圖像進行疊加,求出路面裂縫屋脊邊緣極值點圖像,如圖3所示。

圖3 路面裂縫屋脊邊緣檢測

3.2 基于形狀特征和形態(tài)學(xué)的裂縫噪聲去除

形態(tài)學(xué)去除噪聲過程如圖4所示。路面裂縫屋脊邊緣極值點圖像中仍存在大量的噪聲,如圖4(a)所示,產(chǎn)生噪聲的主要原因是由于這些噪聲在局部也是屋脊邊緣,而被檢測為裂縫目標。從圖4(a)中可以看出,裂縫主體已被檢測出來,同時伴有大量的噪聲,但噪聲不是很集中,因此可以根據(jù)裂縫表現(xiàn)出的線狀特征和方向性將兩者區(qū)分開[12]。本文根據(jù)裂縫的連通域?qū)傩院托螤顚傩赃x取了以下5個特征因子:

(1)連通域的方向:指二值化裂縫后連通域最小外接橢圓的長軸方向;

(2)連通域的長度:指二值化裂縫后連通域最小外接橢圓的長軸長;

(3)連通域的面積:指二值化裂縫后連通域中的像素個數(shù);

(4)連通域的線性度:指二值化裂縫后連通域最小外接橢圓長軸L與短軸值l之比;

(5)連通域的連續(xù)性:取二值化裂縫后連通域T的最小外接矩形,以該矩形為中心,做該矩形八鄰域方向的8個大小一樣的矩形,統(tǒng)計這8個矩形區(qū)域中的其他連通域像素的個數(shù)M,當M小于置閾值TH時,則認為裂縫是孤立的不連續(xù)的。

由于裂縫局部不連續(xù),因此采用膨脹的方法將局部裂縫連接起來,并對膨脹后的裂縫進行聯(lián)通域標記,結(jié)合裂縫特征因子,去除干擾,實現(xiàn)裂縫的粗定位,如圖4(d)所示。然而,粗定位后的裂縫連續(xù)性差且是零碎、不完整的,因而需要對裂縫進行連接。

圖4 形態(tài)學(xué)去除噪聲過程

4 路面裂縫的連接

由于裂縫過細、縫壁脫落積灰、拍攝時光線強度和方向等因素影響,裂縫只在宏觀上呈現(xiàn)為連續(xù),因此去除干擾后得到的是裂縫的零碎片段。圖論提供了對事物及其之間關(guān)系進行描述、分析和處理的完整理論和方法。用圖來描述粗定位后裂縫零碎片段的空間分布,將方便對其進行全局分析和操作。分析裂縫的成像條件和裂縫的特征,本文采用最小生成樹表現(xiàn)零碎裂縫片段間的連續(xù)性。根據(jù)裂縫的連續(xù)性,將零碎片段連接起來獲得完整的裂縫。

4.1 Prim最小生成樹原理

Prim最小生成樹是從一個具有n個頂點的帶權(quán)無向完全圖中選擇n-1條邊并使這個圖連通,同時使生成樹的權(quán)值最小。Prim算法從圖中的一個頂點開始,把這個頂點包含在一個集合中,反復(fù)尋找一個頂點已在該集合中而另一個頂點還不在該集合中的最小權(quán)邊,把新邊和新結(jié)點歸并到生成樹中,如圖5(a);本文中將零碎片段裂縫看作一個單元,計算各單元之間的距離,按最小距離選擇邊和歸并單元;對于線段裂縫單元,其只有2個端點,且這2個端點不能相連,因此只搜索本端點到其他單元端點之間的距離,按最小距離選擇邊,歸并連接單元的2個端點,如圖5(b);然而對于分叉裂縫單元,其有多個端點,如圖5(c),因此,需要將分叉裂縫單元分解為線段裂縫單元,如圖5(d),然后按線段裂縫單元方法進行處理,如圖5(e)。本文對粗定位后的零碎片段裂縫進行分解并提取端點,使用Prim算法構(gòu)造最小生成樹,并利用裂縫特征改造最小生成樹實現(xiàn)裂縫的連接。

圖5 Prim最小生成樹示意圖

4.2 端點提取

局部裂縫片段并非都是線段單元,因此需要對這些片段進行分解。首先對去除干擾后的裂縫圖像取骨架,并對骨架進行細化處理,去除冗余像素,使其轉(zhuǎn)化為8聯(lián)通情況下的嚴格細化;然后去除其中3個及3個以上的交叉點,使其分解成為線性片段;最后對去除交叉點后的局部細化裂縫單元做這些單元的最小外接矩形,取局部細化裂縫單元與矩形的交點作為該細化裂縫單元的端點,如圖6所示。

圖6 端點提取過程

4.3 基于Prim算法的最小生成樹連接

對所有的局部裂縫取端點得端點集合{T1,T2,…,Ti}。對得到的端點集合{T1,T2,…,Ti},構(gòu)造特殊鄰接矩陣L,該矩陣定義為:

其中,dis(Ti,Tj)為端點Ti到端點Tj的像素距離。

通過Prim算法構(gòu)造最小生成樹:記G=＜V,E＞是取端點后裂縫圖像的一個聯(lián)通的帶權(quán)圖,V即為已得到的端點集{T1,T2,…,Ti},E為邊集,通過鄰接矩陣得到。

(1)初始狀態(tài)為:U={u1,u2}V={v1,v2,…},TE={}。其中,u1,u2為取端點后裂縫圖像中最長局部細化裂縫單元的2個端點,v1,v2為端點集中的端點。

(2)在所有u∈U,v∈V-U的邊(u,v)∈E中找一條權(quán)值最小的邊(u0,v0),將這條邊加進集合TH中,同時將此邊的另一頂點v0及和v0屬于同一裂縫的另一點v1并入U。

(3)如果U=V,則該算法結(jié)束;否則重復(fù)步驟(2)。

算法結(jié)束時,TH中包含了G中的n/2-1條邊。經(jīng)過上述步驟選取到的所有邊恰好就構(gòu)成了圖G的一顆最小生成樹。對圖3(d)中的裂縫構(gòu)造最小生成樹,并對該圖中的裂縫進行連接。

4.4 改造的最小生成樹連接

裂縫的最小生成樹連接是把所有的裂縫按最短路徑相連,裂縫連接的同時把偽裂縫也連接上,如圖7(a)所示,因此,需要對Prim算法構(gòu)造的最小生成樹中的邊進行刪選。由于交叉點之間形成的邊本來是已經(jīng)檢測出的區(qū)域,因此只對非交叉點之間的邊進行刪選;對于非交叉點之間的邊,按下式進行刪除:

其中,θi為邊i的角度;α,β分別為與邊i相連的兩條線狀裂縫的角度;Ci為邊i所在區(qū)域的對比度;TH為對比度閾值;若Pi為1則保留該邊,否則刪去該邊。然后更新邊集E,生成新的最小生成樹,新的最小生成樹去除了那些非裂縫區(qū)域的連接,如圖7(b)所示。對于那些未連接的偽裂縫,按裂縫特征因子去除,如圖7(c)所示。

圖7 基于改進Prim算法的裂縫連接圖

5 裂縫的填充與增強

由于最小生成樹連接為線段連接,而線段連接與實際的裂縫結(jié)構(gòu)有一定差異,為了使連接區(qū)域更接近實際裂縫,去除錯誤的強制連接,本文對強制連接的線段采用其所在區(qū)域的灰度特征進行檢驗,具體過程如下:

(1)計算線段的鄰域范圍,其定義為到這條線段上的像素距離小于閾值L的區(qū)域,如圖8所示。

圖8 線段的鄰域圖

(2)采用P分位數(shù)法對鄰域內(nèi)的像素進行二值化:對鄰域內(nèi)的像素按灰度值進行排序,對于序列中某點xp,當小于xp的灰度值個數(shù)占總個數(shù)的15%時,取點xp的灰度值為閾值,對鄰域中的像素進行二值化。

(3)對二值化后的鄰域進行聯(lián)通域標記,使用裂縫的特征因子計算各連通域的線性度,保留線性度大于M的目標。

對圖7(c)進行填充和增強,結(jié)果如圖9所示。

圖9 填充后的最小生成樹連接

6 實驗結(jié)果及分析

本文算法程序基于matlab7.8開發(fā),運行環(huán)境為WindowsXP,CPU為Intel(R)core(TM)3.10 GHz,內(nèi)存3.29 GB。為了測試本文算法的檢測效果,對200幅路面圖像進行了算法測試,并與其他算法(迭代裁剪法、種子修正法、灰度直方圖法)進行實驗對比。其中,圖2中的5幅圖像的測試結(jié)果如圖10～圖14所示。

圖10 橫縫識別結(jié)果

圖11 縱縫識別結(jié)果

圖12 細縫識別結(jié)果

圖13 粗縫識別結(jié)果

圖14 龜裂識別結(jié)果

為了有效評估裂縫檢測的效果,采用文獻[13]中的基于緩沖的 Hausdorff距離的分值測量方法。Hausdorff距離是描述2組點集之間相似程度的一種量度,它是2個點集之間距離的一種定義形式:假設(shè)有2組集合A={a1,a2,…,ai},B={b1,b2,…,bi},則這2個點集合之間的Hausdorff距離定義為:

其中,mamb分別為A,B集合中點的個數(shù)。由式(3)知,雙向Hausdorff距離H(A,B)是單向距離h(A,B)和h(B,A)兩者中的較大者,它度量了2個點集間的最大不匹配程度。將檢測后的路面裂縫看做一個點集,兩裂縫之間的Hausdorff距離是通過裂縫像素點在圖像中的坐標進行計算。如圖15所示,對于圖15(a)中的裂縫中的點a,它與圖15(b)中裂縫的最短距離點為點b。

圖15 裂縫的Hausdorff距離示意圖

在本文中BH(A,B)為人工裂縫分割圖像和其他算法裂縫分割圖像之間的距離,A和B分別對應(yīng)人工裂縫分割圖像和其他算法裂縫分割圖像中裂縫位置的集合,其分值計算如下:

ScoringMeasure=100-BH(A,B)×100(6)

將各個算法檢測的結(jié)果與人工分割的裂縫圖像作比較,計算分值。表1和圖16給出本文算法與3種經(jīng)典算法的性能對比,結(jié)果表明,本文的識別結(jié)果比其他3種算法的檢測均值高出6個～13個百分點,其對復(fù)雜裂縫(圖13、圖14)的檢測結(jié)果值明顯高于其他算法。

表1 4種算法識別得分對比

圖16 4種算法識別得分對比

7 結(jié)束語

本文提出一種基于Prim最小生成樹的路面裂縫連接算法,并通過研究得出以下結(jié)論:

(1)利用路面裂縫的屋脊邊緣特征對裂縫進行屋脊邊緣檢測,使用路面裂縫形狀特征因子去除檢測后的噪聲,可以實現(xiàn)裂縫的粗定位。

(2)利用最小生成樹來表達粗定位后裂縫骨架之間的連續(xù)性,可以方便對其進行全局分析和操作。對裂縫提取端點,使用Prim算法構(gòu)造最小生成樹實現(xiàn)路面裂縫的連接,同時使用裂縫方向、對比度特征去除連接中的強制連接,可以實現(xiàn)平面圖像上具有相同方向、不同長度、不同位置裂縫的連接。

(3)為了去除強制偽連接,在連接的基礎(chǔ)上,結(jié)合原圖,對連接區(qū)域,提取局部裂縫,在原檢測出來的裂縫上進行填充,可以使連接區(qū)域更接近實際裂縫。

(4)實驗結(jié)果表明,本文算法明顯提高了裂縫檢測目標的連續(xù)性,與人工分割結(jié)果非常接近。

[1] 徐志剛.基于多特征融合的路面破損圖像自動識別技術(shù)研究[D].西安:長安大學(xué),2012.

[2] Huang Y,Xu B.Automatic Inspection of Pavement Cracking Distress[J].Journal of Electronic Imaging, 2006,15(1).

[3] 交通部公路科學(xué)研究院上海市公路管理處.JTG H20-2007公路技術(shù)狀況評定標準[M].北京:人民交通出版社,2008.

[4] Wang K C P.Elements of Automated Survey of Pavements and a 3D Methodology[J].Journal of Modern Transportation,2011,19(1):51-57.

[5] Nejad F M,Zakeri H.An Optimum Feature Extraction Method Based on Wavelet-radon Transform and Dynamic Neural Network for Pavement Distress Classification[J]. Expert Systems with Applications,2011,38(8):9442-9460.

[6] 徐志剛,趙祥模,宋煥生.基于直方圖估計和形狀分析的瀝青路面裂縫識別算法[J].儀器儀表學(xué)報,2010, 31(10):2260-2266.

[7] Huang Y,Xu B.Automatic Inspection of Pavement Cracking Distress[J].Journal of Electronic Imaging, 2006,15(1).

[8] Oh H,Garrick N W,Achenie L E K.Segmentation Algorithm Using Iterative Clipping forProcessing Noisy Pavement Images[C]//Proceedings of the 2nd International Conference on Imaging Technologies:Techniques and Applications in Civil Engineering.[S.1.]:IEEE Press. 1998:259-267.

[9] 楊 松,邵龍?zhí)?郭曉霞,等.基于骨架和分形的混泥土裂縫圖像識別算法[J].儀器儀表學(xué)報,2012, 33(8):1850-1855.

[10] 鄒 勤,李清泉,毛慶洲.利用目標點最小生成樹的路面裂縫檢測[J].武漢大學(xué)學(xué)報:信息科學(xué)版,2011, 36(1):71-75.

[11] Cheng H D,Miyojim M.Automatic Pavement Distress Detection System[J].Information Sciences,1998,108(1): 219-240.

[12] Andaló F A,Miranda P A V,Torres R S,et al.Shape Feature Extraction and Description Based on Tensor Scale[J].Pattern Recognition,2010,43(1):26-36.

[13] Tsai Y C,Kaul V,Mersereau R M.Critical Assessment of Pavement Distress Segmentation Methods[J].Journal of Transportation Engineering,2009,136(1):11-19.

編輯 索書志

Pavement Crack Connection Algorithm Based on Prim Minimum Spanning Tree

REN Liang,XU Zhigang,ZHAO Xiangmo,ZHOU Jingmei
(School of Information Engineering,Chang’an University,Xi’an 710064,China)

When the digital image processing technology is used to detect the cracks on the pavement,it is very hard to detect an intact structure for the cracks because parts of the cracks are very narrow,or shadowed by other objects,or filled with dust.These seriously affects the accuracy of the crack parameter measurement and damage index evaluation.Aiming at the problems above,a pavement crack connection algorithm using Prim minimum spanning tree is proposed.The ridge detection method is used to mark out all the suspicious cracks targets,with the shape features of cracks to remove the noises like spots or blocks.So all the long or obvious cracks are remained.Using the morphology method,the endpoints of the remained crack segments are extracted,and the Prim algorithm is used to construct a minimum spanning tree and makes all the discontinuous cracks connected.All the forced pseudo connections are deleted through the orientation and contrast characteristics of the cracks.On the basis of connection,the cracks are enhanced by filling operation and an intact crack structure is acquired.200 pavement images with cracks are tested,and the Hausdorff distance is used to evaluate the performance of various algorithms.Experimental results show that the proposed algorithm significantly improves the continuity of the detected crack targets,the detection accuracy rate of which is higher than other algorithms with by 6～13 percentage.

traffic engineering;pavement mainteance;crack detection;Prim minimum spanning tree;crack connection; Hausdorff distance

1000-3428(2015)01-0031-06

A

TP751.1

10.3969/j.issn.1000-3428.2015.01.006

國家自然科學(xué)基金資助項目(51278058);中央高?；究蒲袠I(yè)務(wù)費專項基金資助項目(2009JC114,2010ZY007,2010JC056);陜西省自然科學(xué)基金資助項目(S2013JC9397)。

任 亮(1989-),男,碩士研究生,主研方向:圖像處理;徐志剛(通訊作者),副教授、博士;趙祥模,教授、博士;周經(jīng)美,博士研究生。

2014-02-18

2014-03-13 E-mail:945357125@qq.com

中文引用格式:任 亮,徐志剛,趙祥模,等.基于Prim最小生成樹的路面裂縫連接算法[J].計算機工程,2015,41(1): 31-36.

英文引用格式:Ren Liang,Xu Zhigang,Zhao Xiangmo,et al.Pavement Crack Connection Algorithm Based on Prim Minimum Spanning Tree[J].Computer Engineering,2015,41(1):31-36.