車道線的GrowCut快速檢測(cè)算法

黎 明， 計(jì)春雷， 張鴻洲

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

車道線的GrowCut快速檢測(cè)算法

黎 明1， 計(jì)春雷1， 張鴻洲2

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

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

車道線檢測(cè)；圖像分割；智能交通

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

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

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

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

1 GrowCut圖像分割

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

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

當(dāng)前一時(shí)步的鄰近元胞狀態(tài)已知時(shí)，局部轉(zhuǎn)移函數(shù)可用于計(jì)算下一時(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是一個(gè)三元組（lp，θp，Cp），其中l(wèi)p為p 的標(biāo)記；θp為p 的力量，θp∈［0，1］；Cp為元胞特征向量。

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

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

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

2 車道線檢測(cè)

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

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

2.1 關(guān)鍵幀選取

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

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

2.2 邊緣提取

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

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

2.3 車道線分半處理

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

2.4 車道線擬合

利用多項(xiàng)式對(duì)車道邊緣進(jìn)行曲線擬合，得到最終車道線。該多項(xiàng)式為

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

3.1 單車道檢測(cè)

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

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

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

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

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

3.2 多平道檢測(cè)

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

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

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

4 結(jié) 語(yǔ)

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

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

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