黎 明， 計春雷， 張鴻洲

（1.上海電機學(xué)院 電子信息學(xué)院，上海 200240；2.公安部第三研究所，上海 201204）

車道線的GrowCut快速檢測算法

黎 明1， 計春雷1， 張鴻洲2

（1.上海電機學(xué)院 電子信息學(xué)院，上海 200240；2.公安部第三研究所，上海 201204）

針對目前智能交通領(lǐng)域中車道線檢測算法效率低、魯棒性差等問題，提出了一種基于GrowCut的車道線快速檢測方法。從監(jiān)控攝像機中采集圖像并標(biāo)定初始種子點，利用GrowCut算法進行邊緣分割，對分割結(jié)果經(jīng)過中值平滑濾波、邊緣提取、分半處理及曲線擬合，最終得到清晰的車道線。將GrowCut算法與分水嶺算法進行了對比，結(jié)果表明：該算法簡便快捷、魯棒性好，優(yōu)于經(jīng)典算法，可廣泛應(yīng)用于智能交通、公共安全領(lǐng)域。

車道線檢測；圖像分割；智能交通

車道線檢測是PTZ（Pan Tilt Zoom，PTZ）攝像機自動標(biāo)定、智能視頻分析、汽車輔助駕駛以及室外機器人自動導(dǎo)航的首要環(huán)節(jié)和關(guān)鍵步驟，具體是指從監(jiān)控攝像頭獲取的視頻圖像中，根據(jù)車道線的顏色、紋理、形狀等特征，將車道線與背景分離，從而獲得車道線的走向或標(biāo)記車道的區(qū)域范圍［1］，而圖像分割是其中的一個重要環(huán)節(jié)。

經(jīng)典的圖像分割算法大致可以分為閾值分割法［2-3］、區(qū)域增長法［4］、聚類法［5］等。閾值分割法是最為基礎(chǔ)的圖像分割算法，由于計算量小、實現(xiàn)簡單、性能穩(wěn)定等諸多優(yōu)點而得到廣泛應(yīng)用，但閾值的選取往往是決定分割成敗的關(guān)鍵因素。區(qū)域增長法由于涉及迭代操作，效率不高，并且容易發(fā)生過分割現(xiàn)象，分水嶺算法［6］就是其中的典型代表。聚類法對數(shù)據(jù)維數(shù)較為敏感，通常需要耗費大量運算時間和資源，很難滿足實時性要求，因此不適用于車道線檢測研究領(lǐng)域。當(dāng)前最流行的圖像分割算法還包括：Magic Wand，Intelligent Paint［7］，Intelligent Scissors［8］，Graph Cut［9-10］，GrabCut［11］等。其中，Intelligent Paint和Intelligent Scissors是交互式的圖像分割方法，可以快速準(zhǔn)確地分割圖像中的目標(biāo)區(qū)域。Graph Cut算法將圖像作為圖形進行處理，每個圖像像素代表一個圖形節(jié)點，然后采用最大流最小割算法計算最優(yōu)像素點標(biāo)記。作為Graph Cut算法的擴展，GrabCut算法的分割效果通常更佳。

目前，車道線檢測多采用經(jīng)典的Hough變換及形態(tài)學(xué)方法，提取車道圖像中的強邊緣，然后通過曲線擬合來確定車道線。文獻［12］中提出了一種基于Hough變換的道路邊緣檢測和跟蹤方法，可以實現(xiàn)低曲率道路（如高速路）的車道線檢測。然而實際交通路況中，特別是在智能交通、汽車輔助駕駛等應(yīng)用中，道路狀況復(fù)雜多變，多數(shù)車道圖像中都包含有較高曲率的路段；此外，Hough變換的運算量大，難以滿足實時性要求。為了解決這一問題，文獻［13］中提出了一種基于分層累加的Hough變換算法，可以大幅提高運算效率。文獻［14］中提出了一種基于形態(tài)學(xué)結(jié)構(gòu)元素建模的車道線檢測算法，具有較好的魯棒性。經(jīng)典車道線檢測方法的檢測結(jié)果易受視頻圖像分辨率、道路狀況等因素影響，誤差通常較大。

針對現(xiàn)有車道線檢測技術(shù)的不足，本文提出一種基于GrowCut［15］的車道線快速檢測算法，采用新的邊緣分割方法對車道線進行分割、平滑濾波處理，不僅能有效去除椒鹽噪聲，還能保留更多的圖像邊緣信息，最后進行曲線擬合，從而確定車道線。該算法可以對低分辨率、無明顯車道邊界線及具有較高曲率路段的視頻圖像進行車道線的快速檢測，同時算法對光照、噪聲不敏感。

1 GrowCut圖像分割

GrowCut算法采用了全新的思路進行像素標(biāo)記，分割效果更好。具體來講，GrowCut算法是一種基于元胞自動機［16］的交互式多標(biāo)記n維圖像分割方法。元胞自動機是一個三元組

其中，S為非空狀態(tài)集，N 為鄰域系統(tǒng)，δ：SN→S表示從SN映射到S的一個局部轉(zhuǎn)移函數(shù)。

當(dāng)前一時步的鄰近元胞狀態(tài)已知時，局部轉(zhuǎn)移函數(shù)可用于計算下一時步的元胞狀態(tài)。常用的鄰域系統(tǒng)有馮·諾依曼領(lǐng)域和摩爾領(lǐng)域兩種。

（1）馮·諾依曼鄰域

（2）摩爾鄰域

式中，p為當(dāng)前元胞；q為鄰域元胞；Zn為圖像像素空間，n為空間維數(shù)；?p∈P?Zn，P為元胞空間。

元胞狀態(tài)Sp是一個三元組（lp，θp，Cp），其中l(wèi)p為p 的標(biāo)記；θp為p 的力量，θp∈［0，1］；Cp為元胞特征向量。

對于一幅圖像，初始元胞狀態(tài)為

式中，RGBp為像素p在RGB空間的三維色彩向量。因此，利用元胞自動機進行圖像分割的目標(biāo)就是為圖像中的每個像素分配一種狀態(tài)（或指定一個標(biāo)記）。

利用GrowCut進行圖像分割的原理可以從生物學(xué)角度加以解釋：把圖像像素點的標(biāo)記化過程看作是多種細菌的生長與競爭過程，其中細菌代表元胞。每種細菌都從種子像素點開始擴散并試圖占領(lǐng)整幅圖像。在生長過程中，每個細菌都試圖攻擊其鄰近細菌，只有當(dāng)前細菌的攻擊強度大于防守細菌的防守力量時，攻擊才成功，此時防守細菌被占領(lǐng)，并改變其標(biāo)記。如此循環(huán)，直至元胞自動機收斂，分割結(jié)束。

2 車道線檢測

本文基于GrowCut算法提出了新的車道線快速檢測算法，流程圖如圖1所示。

圖1 車道線檢測算法流程圖Fig.1 Flow chart of the proposed lane detection algorithm

2.1 關(guān)鍵幀選取

采集監(jiān)控視頻，通過解幀操作將其序列化為多幀圖像，從中挑選一幀圖像作為關(guān)鍵幀。從多幀圖像中選取關(guān)鍵幀的方法有兩種：① 選取清晰度較高、車道分界線相對明顯的幀作為關(guān)鍵幀；② 選擇圖像質(zhì)量相對穩(wěn)定，且圖像內(nèi)容沒有明顯跳變的一段，對多幀圖像取平均值作為關(guān)鍵幀。

在關(guān)鍵幀圖像中手動標(biāo)定邊緣分割初始種子點，并利用GrowCut算法進行邊緣分割，步驟如下：① 獲取初始種子點的標(biāo)記lp，力量θp和特征向量值Cp。② 保存當(dāng)前狀態(tài)。③ 元胞開始生長。④ 利用初始狀態(tài)值計算攻擊強度。⑤ 當(dāng)前元胞嘗試攻擊鄰近元胞。⑥ 判斷當(dāng)前元胞的攻擊強度是否大于防守元胞的防守力量，若否，則繼續(xù)攻擊相鄰元胞；若是，則防守元胞被占領(lǐng)，同時改變其標(biāo)記和力量值。⑦ 上述步驟循環(huán)進行，直至元胞自動機收斂，邊緣分割結(jié)束。

2.2 邊緣提取

采用中值濾波器對分割結(jié)果進行平滑濾波。中值濾波是一種非線性平滑方法，可以有效濾除分割結(jié)果圖像邊緣附近存在的椒鹽噪聲，同時還可以更多地保留邊緣信息。其原理是，將圖像中某像素點的值用該像素鄰域中其他各點值的中值代替，讓周圍的像素值更接近真實值，從而消除孤立噪聲點。具體操作時，定義一個二維滑動模板，其大小通常是奇數(shù)，如3×3或5×5，利用該模板對整幅圖像進行滑動平均處理。模板的形狀可以根據(jù)4鄰域、8鄰域等分別定義為十字形、圓形或其他拓撲結(jié)構(gòu)。在本文算法中，中值濾波模板大小取值9×9。

平滑濾波之后進行邊緣提取。通常，邊緣提取采用索貝爾（Sobel）算子，也可用Robert，Canny和Prewitt等算子替代，這對邊緣提取的效果不會產(chǎn)生太大差異。這是由于經(jīng)GrowCut分割且平滑濾波后，圖像邊緣比較連續(xù)、完整，因此邊緣提取較易實現(xiàn)。

2.3 車道線分半處理

完成上述步驟之后，需要對提取到的道路邊緣進行分半處理，分別得到左側(cè)車道線和右側(cè)車道線。目前，由于我國布控的路況攝像機中，有相當(dāng)數(shù)量的攝像機為模擬設(shè)備，視頻圖像的分辨率不高；同時，由于部分車道并沒有劃分虛、實線，因此利用傳統(tǒng)形態(tài)學(xué)、分水嶺等算法分割出來的車道線往往與實際不符，存在過分割和欠分割現(xiàn)象。而采用GrowCut算法分割后，雖然車道邊緣輪廓整體較好，但仍有可能存在粘連、分叉等現(xiàn)象，特別是對于彎曲的道路、十字路口等。故對提取到的邊緣進行分半處理，可以使后續(xù)步驟的車道線擬合更加準(zhǔn)確。對分割出來的車道線進行分半處理的流程如圖2所示。

2.4 車道線擬合

利用多項式對車道邊緣進行曲線擬合，得到最終車道線。該多項式為

圖2 分半處理流程圖Fig.2 Flow chart of the splitting procedure

式中，fj（j＝1，2，…，m＋1）為多項式系數(shù)，m 為多項式階數(shù)。根據(jù)道路的彎曲程度確定相應(yīng)的階數(shù)，從而實現(xiàn)車道線的擬合。

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

為了驗證本文算法的魯棒性，采集了多種環(huán)境條件下的圖像，分別針對單車道／多車道、無標(biāo)志線車道／間斷標(biāo)志線車道、直線車道／高曲率車道進行了實驗。實驗所用圖像通過在道路上方架設(shè)監(jiān)控攝像機實時采集得到。

3.1 單車道檢測

從單車道監(jiān)控視頻中截取圖像，道路中沒有標(biāo)識線，左側(cè)車道線從視覺上尚能分辨，而右側(cè)車道由于邊緣不明顯，因此很難分辨出車道與人行道的分界線。分別采用經(jīng)典的分水嶺算法和本文提出的算法對該圖像進行車道線檢測，并比較其效果。

圖3（a）和（b）是采用分水嶺算法的初始種子點標(biāo)記及分割的結(jié)果。為了取得圖中所示的分割效果，需要精心選取種子點，同時種子點數(shù)量要盡可能多，才能確保車道右側(cè)邊緣能較好地分割出來。盡管如此，在道路上方仍有一小段高曲率的彎曲車道沒有分割出來。

圖3（c）和（d）是采用本文算法的初始種子點標(biāo)記及分割的結(jié)果。相對于對于分水嶺算法，本文算法的初始種子點只有18個，并且不需要精確選擇，只需沿著人眼視覺可辨的車道線邊緣粗略選取若干標(biāo)記點即可。但分割效果明顯優(yōu)于分水嶺算法，不僅很好地檢測出右側(cè)的微弱道路邊緣，也成功地檢測出了道路上方的高曲率路段。

為了比較2種算法的車道線檢測效果，對圖3（b）和（d）分別進行了分半處理和曲線擬合，擬合結(jié)果分別如圖3（e）和（f）所示。從圖3（e）可以看出，左側(cè)車道線檢測效果較好，而右側(cè)車道線由于分割效果較差，故檢測到的車道線偏離實際道路，誤差較大。

圖3（f）是利用本文算法的車道線檢測結(jié)果，可以看出車道所在區(qū)域已被完整地標(biāo)記出，便于后續(xù)的攝像機標(biāo)定或者車輛計數(shù)、流量監(jiān)測等研究工作。

3.2 多平道檢測

從多車道監(jiān)控視頻中截取到圖像，各個車道之間采用白色間斷線加以標(biāo)識。

圖4（a）和（b）是采用分水嶺算法的初始種子點標(biāo)記及分割的結(jié)果，圖4（c）和（d）是采用本文算法的初始種子點標(biāo)記及分割結(jié)果。對圖4（b）和（d）分別進行了分半處理和曲線擬合，擬合結(jié)果分別如圖4（e）和（f）所示。

從圖4（e）可以看出，對于有標(biāo)識線的車道圖像，分水嶺算法的分割效果優(yōu)于無標(biāo)識線的車道分割結(jié)果，但是依然需要手動精確選取大量初始種子點，否則在車道線的間斷處很容易發(fā)生過分割現(xiàn)象，將其他車道的部分劃入本車道，影響后續(xù)的車輛計數(shù)、跟蹤識別等操作。此外，由于左側(cè)車道部分路段存在過分割現(xiàn)象，因此擬合后的車道線與實際不符，存在較大誤差。而本文算法的車道線分割結(jié)果基本上沒有發(fā)生過分割的情況，雖然初始種子點數(shù)目比圖3有所增加，但相比分水嶺算法仍占據(jù)優(yōu)勢，同時車道線檢測結(jié)果也更好。

4 結(jié) 語

本文提出了一種基于GrowCut的車道線快速檢測方法。采用GrowCut算法替代傳統(tǒng)的形態(tài)學(xué)、區(qū)域增長及分水嶺等方法對視頻圖像進行邊緣分割，然后對分割結(jié)果進行平滑濾波，在去除椒鹽噪聲的同時保留更多的邊緣細節(jié)，最后進行曲線擬合，確定車道線。通過該方法，可以對低分辨率、沒有明顯車道邊界線以及包含高曲率路段的視頻圖像進行車道線的快速檢測。利用本文算法對路況攝像機進行自動標(biāo)定、輔助汽車自動駕駛以及機器人的自動導(dǎo)航等均能取得較好的效果，目前已在公安系統(tǒng)內(nèi)部試點應(yīng)用。

［1］Kastrinaki V，Zervakis M，Kalaitzakis K.A survey of video processing techniques for traffic applications［J］.Image and Vision Computing，2003，21（1）：359－381.

［2］Otsu N.A threshold selection method from graylevel histogram［J］.IEEE Transactions on System，Man and Cybernetics，1979，9（1）：62－66.

［3］肖超云，朱偉興.基于Otsu準(zhǔn)則及圖像熵的閾值分割算法［J］.計算機工程，2007，33（14）：188－189，209.

［4］Adams R，Bischof L.Seeded region growing［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1994，16（6）：641－647.

［5］Coleman G B，Andrews H C.Image segmentation by clustering［J］.Proceedings of the IEEE，1979，67（5）：773－785.

［6］Vincent L，Soille P.Watersheds in digital spaces：an efficient algorithm based on immersion simulations［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，13（6）：583－598.

［7］Reese L J.Intelligent paint：region－based interactive image segmentation［D］.Provo，UT：Brigham Young University，1999：1－20.

［8］Mortensen E N，Barrett W A.Interactive segmentation with intelligent scissors［J］.Graphical Models and Image Processing，1998，60（5）：349－384.

［9］Greig D M，Porteous B T，Seheult A H.Exact maximum a posteriori estimation for binary images［J］.Journal of the Royal Statistical Society：Series B（Methodological），1989，51（2）：271－279.

［10］Boykov Y Y，Jolly M P.Interactive graph cuts for optimal boundary and region segmentation of objects in N－D images［C］／／Proceedings of the Eighth IEEE International Conference on Computer Vision.Vancouver，BC，Canada：IEEE Computer Society，2001：105－112.

［11］Rother C，Kolmogorov V，Blake A.Grabcut：interactive foreground extraction using iterated graph cuts［J］.ACM Transactions on Graphics，2004，23（3）：309－314.

［12］McDonald J B.Application of the Hough transform to lane detection and following on high speed roads［C］／／Proceedings of the Irish Machine Vision and Image Processing Conference.Maynooth，Ireland：National University of Ireland，2001：1－9.

［13］Satzoda R K，Sathyanarayana S，Srikanthan T，et al.Hierarchical additive Hough transform for lane detection［J］.IEEE Embedded Systems Letters，2010，2（2）：23－26.

［14］雷 濤，樊養(yǎng)余，王小鵬，等.基于形態(tài)學(xué)結(jié)構(gòu)元素建模的車道線檢測算法［J］.計算機應(yīng)用，2009，29（2）：440－443.

［15］Vezhnevets V，Konouchine V.“GrowCut”：Interactive multi－label N－D image segmentation by cellular automata［C］／／Proceedings of the GraphiCon.Novosibirsk Akademgorodok.Russia：Russian A－cademy of Sciences，2005：150－156.

［16］Von Neumann J.Theory of self－reproducing automata［M］.Champaign，IL，USA：University of Illinois Press，1966.

Fast Lane Detection Algorithm Based on GrowCut

LI Ming1， JI Chunlei1， ZHANG Hongzhou2
（1.School of Electronics and Information，Shanghai Dianji University，Shanghai 200240，China；2.The Third Research Institute of Ministry of Public Security，Shanghai 201204，China）

A fast GrowCut－based lane detection algorithm is proposed to improve efficiency and robustness of the lane detection algorithms used in intelligent transportation.An image is captured with a surveillance camera and the initial seeds are marked on it.The GrowCut algorithm is then applied to segment the image.After median filtering，edge extraction，splitting and curve fitting，clear lanes can be obtained.The proposed algorithm is compared with the watershed method.The results show that the proposed approach has better performance and robustness than traditional algorithms.The algorithm can be applied to intelligent transportation and public security.

lane detection；image segmentation；intelligent transportation

TP 391.41

A

2095－0020（2011）03－0187－06

2011－05－10

上海市教育委員會科研創(chuàng)新項目資助（11YZ270）；上海市高校選拔培養(yǎng)優(yōu)秀青年教師科研專項基金項目資助（sdj10001）

黎 明（1979－），男，講師，博士，專業(yè)方向為圖像處理、機器學(xué)習(xí)，E－mail：ming.lmhost＠gmail.com