圖論在路面裂縫分割中的應用研究

閆 暉，魯統偉

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

0 引 言

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

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

基于圖論的圖像分割技術是近年來國際上圖像分割領域的一個新的研究熱點.該方法將圖像映射為帶權無向圖，把像素視作節點，利用最小剪切準則得到圖像的最佳分割.該方法本質上將圖像分割問題轉化為最優化問題，是一種點對聚類方法，對數據聚類也具有很好的應用前景.

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

1 典型的閾值分割

1.1 NDHM 方法

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

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

(1)

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

(2)

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

(3)

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

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

(4)

1.2 OTSU方法

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

(5)

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

目標部分比例：

(6)

背景部分比例：

(7)

目標均值：

(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方法的公式可知，在目標區域和背景區域的臨界處的灰度值的變化最明顯，那么這個灰度值即為最佳分割閾值.式(11)中的Th即最大類間方差值.

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

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

(12)

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

(13)

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

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

w(u,v)=

(14)

對任意門限t(0

(15)

那么等式(12)可轉換為

令M為256 ×256 的對稱矩陣，mi,j= cut (Vi,Vj) 為其(i,j) 處的元素且有mi,j=mj,i.給定一幅圖像，通過計算圖中所有節點間的權值就可以構建基于灰度級的權值矩陣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中區域1中的元素之和，S2為矩陣M中區域2中的元素之和,S3為矩陣M中區域3中的元素之和.顯然有，S1= asso(A,A) ，S2=asso(B,B)，S3= asso(A,B).則

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

3 實驗結果對比與分析

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

實驗目的是測試本文方法在檢測裂縫時的性能, 并和傳統方法( OTSU和NDHM方法) 進行比較.圖2中顯示了4幅典型路面裂縫影像，以及分別用3種算法進行處理后的結果.

圖2 裂縫提取實現Fig.2 Implement of extracting crack

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

(16)

(17)

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

表1 裂縫提取結果評價

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

4 結 語

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

參考文獻：

[1] 劉渝，張彥鋒，魯統偉.OCR中一種基于最小乘法的連通域去噪方法[J].武漢工程大學學報，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]．計算機工程與應用，2003(35)：212-232．

[6] 初秀民，嚴新平，陳先橋，路面破損圖像二值化方法研究[J].計算機工程與應用,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] 劉向龍, 李清泉. 基于金字塔結構的海量路面影像破損統計模型[J] . 武漢大學學報:信息科學版,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].北京：清華大學出版社，2000.

[12] 付忠良.圖像閾值選取方法的構造[J].中國圖像圖形學報,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.