圖論在路面裂縫分割中的應(yīng)用研究

閆 暉，魯統(tǒng)偉

(1．武漢工程大學(xué)計算機科學(xué)與工程學(xué)院，湖北 武漢 430074；2．智能機器人湖北省重點實驗室，湖北 武漢 430074)

0 引 言

隨著社會經(jīng)濟的發(fā)展，全世界絕大多數(shù)國家都已經(jīng)進入了一個熱火朝天的和平建設(shè)發(fā)展階段.其中為了提高國家的基礎(chǔ)設(shè)施和交通運輸?shù)陌l(fā)達水平，世界各國都十分重視公路交通的建設(shè).大量的公路建設(shè)給人們帶來無限便利的同時，也帶了繁重的公路養(yǎng)護的重擔(dān).傳統(tǒng)的路面檢測方法需要人工親臨現(xiàn)場進行檢查、勘測、記錄，耗費了大量的人力和財力，還影響了交通狀況，甚至可能造成人身意外傷亡，采用這種方式進行道路檢測效率低下、檢測精度差等諸多弊病.隨著計算機技術(shù)、數(shù)字圖像技術(shù)、多源傳感器技術(shù)的快速發(fā)展，公路路面破損檢測正經(jīng)歷從人工檢測向自動化檢測的轉(zhuǎn)變.但目前的商業(yè)化產(chǎn)品仍然需要人工交互來實現(xiàn)從圖像中提取路面裂縫，其工作量巨大.因此研究全自動的路面裂縫檢測方法也越來越重要.

基于圖像理解與分析的路面裂縫自動檢測, 其研究始于20 世紀(jì)90 年代初, 進入21 世紀(jì)后受到廣泛關(guān)注, 多種裂縫檢測算法相繼被提出.主要可以分為“圖像邊緣檢測”和“圖像區(qū)域分割”兩大類.在早期的路面裂縫檢測算法中，一些經(jīng)典的邊緣檢測的算法受到國內(nèi)外學(xué)者的關(guān)注和研究，例如，劉渝采用一種連通域去噪方法實現(xiàn)光學(xué)字符數(shù)字的提取[1].Li L.等[2]提出了一種基于soble算子的邊緣檢測方法，Seung-Nam等[3]提出的方法可認為將裂縫提取問題轉(zhuǎn)換成圖頂點之間最小代價搜索問題.然而，由于路面表面具有高紋理特征，導(dǎo)致采集到的路面影像具有很強的噪聲，使得基于圖像邊緣檢測的方法應(yīng)用在裂縫檢測中具有一定的局限性.在最近幾年里，越來越多的研究者將關(guān)注點轉(zhuǎn)向了利用“圖像區(qū)域分割”的方式來提取裂縫.Cheng H. D.[4]等提出了一種路面破損模糊分割方法，經(jīng)差分處理后路面圖像像素灰度值的隸屬度函數(shù)，并利用遺傳算法確定該隸屬度函數(shù)的參數(shù)，接著對路面破損圖像進行模糊化處理，最后根據(jù)破損區(qū)域像素連續(xù)性的特點，將破損區(qū)域像素連接起來得到路面破損圖像的分割結(jié)果.該方法試驗結(jié)果較好，但處理時間也較長.李晉惠[5]根據(jù)裂縫邊緣在各個角度上可能存在梯度，提出了8個方向的模板對圖像進行Sobel邊緣檢測，結(jié)合加權(quán)的鄰域平均噪聲濾除算法和最大類間方差法(OTSU)分割算法對裂縫進行分割，裂縫的邊緣保護的較好，邊緣斷續(xù)的情況較少.文獻[6]中，首先利用直方圖分析方法將路面圖像中的標(biāo)線從圖像中去除，然后對圖像進行二值化處理，采用圖像分塊的方法，通過對小子塊的閾值分割來實現(xiàn)對整體路面圖像的二值化.文獻[7]利用在路面圖像中，裂縫的像素灰度值一般較正常像素點的灰度值要低的特點，并且裂縫像素在平面分布上具有一定的連續(xù)性，提出一種圖像的新的分割方法:首先給出了經(jīng)過差分處理后路面病害圖像的模糊隸屬度，然后對模糊隸屬度中的待定參數(shù)用遺傳算法確定;并進一步對路面圖像進行模糊化處理;將路面中的目標(biāo)利用連續(xù)性連接起來，形成完整的邊緣目標(biāo).

基于圖論的圖像分割技術(shù)是近年來國際上圖像分割領(lǐng)域的一個新的研究熱點.該方法將圖像映射為帶權(quán)無向圖，把像素視作節(jié)點，利用最小剪切準(zhǔn)則得到圖像的最佳分割.該方法本質(zhì)上將圖像分割問題轉(zhuǎn)化為最優(yōu)化問題，是一種點對聚類方法，對數(shù)據(jù)聚類也具有很好的應(yīng)用前景.

從實際出發(fā)，將這種圖論閾值分割算法應(yīng)用到路面裂縫檢測中.

1 典型的閾值分割

1.1 NDHM 方法

NDHM(Neighboring Difference Histogram Method)[8-9]是由李清泉教授在2008年提出的一種路面裂縫影像閾值分割的方法.該方法針對每一個像素點，統(tǒng)計該點臨域內(nèi)所有像素值與目標(biāo)像素值之間的差異，如果臨域內(nèi)像素與目標(biāo)像素之間的差異越大，則目標(biāo)點越接近裂縫點，該方法的基本原理如下:

設(shè)目標(biāo)像素點P(x,y)，其灰度值為i[1,2,…,L].設(shè)目標(biāo)點臨域像素點的個數(shù)為w，以及p(x,y)與臨域內(nèi)像素點差異統(tǒng)計值為ai,p(x,y).

(1)

對于一個路面圖像，所有灰度值的差異統(tǒng)計值之和為Ai,i∈[1,2,…,L].則

(2)

針對圖像數(shù)據(jù)的離散性特征，圖像可以用二維矩陣表示，用X表示圖片二維矩陣的行數(shù)，Y表示圖片二維矩陣的列數(shù).則公式(2)又可表示為

(3)

其中x∈(1,2,…,X),y∈(1,2,…,Y).

NDHM方法提出的最佳分割閾值如下：

(4)

1.2 OTSU方法

OTSU法即最大類間方差法，是由大津展之[10]最先在1979年提出的一種圖像處理方法.該方法是依據(jù)判決分析推導(dǎo)出來的，是一種無參數(shù)無監(jiān)督的自動閾值分割法.其基本思想是通過灰度圖像的直方圖，以目標(biāo)區(qū)域灰度值和背景區(qū)域灰度值的方差最大來動態(tài)的確定圖像分割的閾值[10-11]，它是一種通過一維灰度直方圖來進行計算的簡單圖象分割方法.后來Lee等學(xué)者[12]分別通過以形狀、錯分概率和均勻性度量為準(zhǔn)則函數(shù)來評估了許多不同閾值分割法的性能，其結(jié)果表明，OTSU法是一種直接有效的圖像閾值分割方法.它的基本原理如下：

(5)

設(shè)定圖像分割閾值t，那么通過分割閾值t把圖像分割為目標(biāo)區(qū)域O和背景區(qū)域A兩個區(qū)域，用{f(x,y)≤t}和{t

目標(biāo)部分比例：

(6)

背景部分比例：

(7)

目標(biāo)均值：

(8)

背景均值：

(9)

總均值：

μ=ω0(t)μ0(t)+ω1(t)μ1(t)

(10)

那么通過OTSU方法得到圖像的最佳分割閾值公式為：

Th=argmax[ω0(t)·(μ0(t)-μ)2+
ω1(t)(μ1(t)-μ)2]

(11)

這樣由OTSU方法的公式可知，在目標(biāo)區(qū)域和背景區(qū)域的臨界處的灰度值的變化最明顯，那么這個灰度值即為最佳分割閾值.式(11)中的Th即最大類間方差值.

2 基于圖論的圖像分割算法

任意特征空間的點集都可以采用一個無向圖G(V,E) 來表達,其中V是節(jié)點的集合,E是連接節(jié)點的邊的集合 連接每兩個節(jié)點的邊均賦予權(quán)值w(u,v),該權(quán)值衡量節(jié)點u和v的相似程度. 如果將節(jié)點集V分成兩個獨立的子集A和B,其中B=V-A,那么通過移去連接A和B中所有節(jié)點的邊就可以得到點集A和B之間的分離度,稱為劃分(cut):

(12)

但是這種方法容易產(chǎn)生出孤立點，為了克服這一缺點.研究者們提出了一個歸一化的劃分Ncut(Normal cut)[14].

(13)

本文采用Normal cut方法來對路面圖像進行分割處理.其基本思想是將圖像中的每個像素看作是一個節(jié)點，而連接每兩個節(jié)點的權(quán)值反映了這兩個像素屬于同一類的可能性.權(quán)值越大表明兩個像素越可能屬于同一類.采用基于圖像灰度級的對稱矩陣M(其大小為256 ×256) 來描述圖像中各部分之間的關(guān)系, 而不是采用N×N(其中N為圖中節(jié)點的個數(shù))的對稱矩陣W，也即將單個像素之間的關(guān)系轉(zhuǎn)化為灰度等級之間的關(guān)系.而后對每一個可能門限t，利用矩陣M可快速地計算其對應(yīng)的圖譜劃分值，其最小的圖譜劃分值對應(yīng)的門限即為分割圖像的最佳閾值.

如果將圖像中的每個像素看作一個節(jié)點，每對節(jié)點均用一條邊連接起來, 邊的權(quán)值反映這兩個像素屬于相同目標(biāo)的可能性, 那么就可以構(gòu)建一個帶權(quán)的無向圖G= (V,E).利用像素的灰度值以及它們的空間位置,可以定義圖G中連接兩個節(jié)點u和v的邊的權(quán)值如下:

w(u,v)=

(14)

對任意門限t(0

(15)

那么等式(12)可轉(zhuǎn)換為

令M為256 ×256 的對稱矩陣，mi,j= cut (Vi,Vj) 為其(i,j) 處的元素且有mi,j=mj,i.給定一幅圖像，通過計算圖中所有節(jié)點間的權(quán)值就可以構(gòu)建基于灰度級的權(quán)值矩陣M.矩陣M= [mi,j]256 ×256如圖1 所示.

圖1 對稱矩陣M=[ mi,j]256 ×256的示意圖,其中mi,j = mj,iFig.1 Schematic diagram of symmetric matrixM = [ mi,j] 256 ×256, mi,j= mj,i

定義S1為矩陣M中區(qū)域1中的元素之和，S2為矩陣M中區(qū)域2中的元素之和,S3為矩陣M中區(qū)域3中的元素之和.顯然有，S1= asso(A,A) ，S2=asso(B,B)，S3= asso(A,B).則

而且矩陣M的大小固定為256 ×256 ，與圖像的大小無關(guān)，而矩陣W的維數(shù)則為N×N，其中N為圖像中像素的個數(shù). 顯然采用矩陣M使所需的存儲空間得到了極大的減少.

3 實驗結(jié)果對比與分析

本文實驗影像均由CCD相機拍攝的路面圖片裁剪得到，圖片尺寸大小為512*512像素，且都經(jīng)過了預(yù)處理，如幾何校正、均光、直方圖均衡化等..本文算法程序基于VS2008 開發(fā), 運行環(huán)境為Windows XP, CPU Inter Pentium( R) 2.5 GHz,RAM 2G.

實驗?zāi)康氖菧y試本文方法在檢測裂縫時的性能, 并和傳統(tǒng)方法( OTSU和NDHM方法) 進行比較.圖2中顯示了4幅典型路面裂縫影像，以及分別用3種算法進行處理后的結(jié)果.

圖2 裂縫提取實現(xiàn)Fig.2 Implement of extracting crack

圖2中的4幅路面裂縫圖片，采用相同的預(yù)處理方式進行前期的預(yù)處理，然后將他們分別用OTSU、NDHM、graph-cut進行分割.為了對裂縫提取效果進行量化分析和評價，本文引入完成度指數(shù) 和正確度指數(shù)[14-15].完成度指數(shù)用于描述完成裂縫提取這一任務(wù)的完成程度，正確度指數(shù)則描述完成任務(wù)的質(zhì)量水平.其定義見式(16) 和式(17) .另外，為了對算法的時間效率進行分析，實驗記錄了算法的運行時間.

(16)

(17)

式(16)中，Lr代表提取結(jié)果是真實裂縫的長度；Lgt代表裂縫的實際長度. 通過實地測量和手工編輯得到；LN代表提取結(jié)果的總長度.

表1 裂縫提取結(jié)果評價

表2 算法效率評價Table 2 Evaluation of algorithm efficiency

4 結(jié) 語

通過表1和表2的實驗結(jié)果評價，可以看出在裂縫提取的完成度和正確度方面Graph-cut比OTSU和NDHM算法優(yōu)越，Graph-cut完全將裂縫分割出來，背景只含有少量的與裂縫相似的像素點，而其它兩種方法則背景存在大量與裂縫相似的像素點.因此在路面裂縫分割上，Graph-cut比OTSU和NDHM具有明顯的優(yōu)越性.然而在算法效率方面Graph-cut存在不足，其算法時間復(fù)雜度要比其它兩種算法的要高.對于算法時間復(fù)雜度將在下一步研究中改進.

參考文獻：

[1] 劉渝，張彥鋒，魯統(tǒng)偉.OCR中一種基于最小乘法的連通域去噪方法[J].武漢工程大學(xué)學(xué)報，2011，33(1)：84-87.

[2] Li L, Chan P, Rao A,et al. Flexible pavement distress evaluation using image analysis[C]//Proceeding of the 2nd International Conference on Applications of Advanced Technologies in Transportation Engineering.1991: 473-477.

[3] Seung-Nam Yu, Jae-Ho Jang. Auto inspection system using a mobile robot for detecting concrete cracks in a tunnel[J]. Automation in Construction, 2006,16(3): 255-261.

[4] Cheng H D ，Miyojim M.Automatic Pavement Distress Detection System[J]. Journal of Irfo～afion Sciences，1998(108):204-219．

[5] 李晉惠．公路路面裂縫類病害圖像處理算法研究[J]．計算機工程與應(yīng)用，2003(35)：212-232．

[6] 初秀民，嚴新平，陳先橋，路面破損圖像二值化方法研究[J].計算機工程與應(yīng)用,2008，44(28):161-165.

[7] Cheng H D, Rong jim. Novel approach to pavement cracking detection based on fuzzy set theory[J].ASCE，1999(13):270-280.

[8] Li Q Q, Liu X L. Novel Approach to Pavement Image Segmentation Based on Neighboring Difference Histogram Method[C]//2008 Congress on Image and Signal Processing, Sanya：2008：792-795.

[9] 劉向龍, 李清泉. 基于金字塔結(jié)構(gòu)的海量路面影像破損統(tǒng)計模型[J] . 武漢大學(xué)學(xué)報:信息科學(xué)版,2008, 33(4): 430-432.

[10] Otsu N.A Threshold Selection Method from Gray-level Histogram[J].IEEE Trans，1979(SMC-9):62-66.

[11] 容觀澳. 計算機圖像處理[M].北京：清華大學(xué)出版社，2000.

[12] 付忠良.圖像閾值選取方法的構(gòu)造[J].中國圖像圖形學(xué)報,2000,5(6)：466-469.

[13] Lee S U.A Comparative Performance Study of Several Global Thresholding Techniques for Segmention[J]. CVGIP，1900(52):171-190.

[14] Shi J, Malik J . Normalized cut s and image segmentation[J]. IEEE Transactions on Pattern Analysis Machine Intelligence,2000,22(8):888-905.

[15] Wiedemann C, Ebner H. Automatic completion and evaluation of road networks [J] . Int Arch Photogramm Remote Sens, 2000(33): 976-986.