車道線的GrowCut快速檢測算法

黎 明， 計春雷， 張鴻洲

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

車道線的GrowCut快速檢測算法

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

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

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

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

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

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

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

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

1 GrowCut圖像分割

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

其中，S為非空狀態集，N 為鄰域系統，δ：SN→S表示從SN映射到S的一個局部轉移函數。

當前一時步的鄰近元胞狀態已知時，局部轉移函數可用于計算下一時步的元胞狀態。常用的鄰域系統有馮·諾依曼領域和摩爾領域兩種。

（1）馮·諾依曼鄰域

（2）摩爾鄰域

式中，p為當前元胞；q為鄰域元胞；Zn為圖像像素空間，n為空間維數；?p∈P?Zn，P為元胞空間。

元胞狀態Sp是一個三元組（lp，θp，Cp），其中lp為p 的標記；θp為p 的力量，θp∈［0，1］；Cp為元胞特征向量。

對于一幅圖像，初始元胞狀態為

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

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

2 車道線檢測

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

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

2.1 關鍵幀選取

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

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

2.2 邊緣提取

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

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

2.3 車道線分半處理

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

2.4 車道線擬合

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

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

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

3 實驗結果及分析

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

3.1 單車道檢測

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

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

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

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

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

3.2 多平道檢測

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

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

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

4 結 語

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

［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準則及圖像熵的閾值分割算法［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］雷 濤，樊養余，王小鵬，等.基于形態學結構元素建模的車道線檢測算法［J］.計算機應用，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

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

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