基于改進(jìn)RANSAC算法的車(chē)道線(xiàn)識(shí)別方法*

樊 超，狄 帥，侯利龍，徐靜波

(河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院，鄭州 450001)

前言

車(chē)道線(xiàn)的正確識(shí)別是智能車(chē)輛實(shí)現(xiàn)自主導(dǎo)航和一些安全輔助駕駛系統(tǒng)(如車(chē)道偏離預(yù)警系統(tǒng)等)正常工作的基本前提。目前，已經(jīng)提出了一些在復(fù)雜路況下的車(chē)道線(xiàn)識(shí)別方法［1－5］。其中隨機(jī)抽樣一致(random sample consensus，RANSAC)算法［6］由于不需要訓(xùn)練過(guò)程或匹配道路模型，相對(duì)于Hough變換和模板匹配等方法，更能適應(yīng)復(fù)雜路況下車(chē)道線(xiàn)特征點(diǎn)擬合，因此近年來(lái)在車(chē)道線(xiàn)識(shí)別中得到廣泛應(yīng)用［7－10］。

當(dāng)?shù)缆仿访娼Y(jié)構(gòu)不均勻、光照變化、陰影遮擋、破損、污跡覆蓋、天氣變化和其它車(chē)輛的存在等使道路圖像變得復(fù)雜時(shí)，提取出的特征點(diǎn)中不僅包括有效點(diǎn)，還會(huì)存在大量異常點(diǎn)(即干擾點(diǎn))，且其分布很不規(guī)則。異常點(diǎn)的出現(xiàn)使正確計(jì)算車(chē)道線(xiàn)參數(shù)變得非常困難，原因主要有兩點(diǎn):一方面，RANSAC算法在初始化模型時(shí)所選取的特征點(diǎn)是完全隨機(jī)的，并沒(méi)有一定的約束規(guī)則，導(dǎo)致算法的實(shí)時(shí)性降低;另一方面，由于RANSAC算法迭代過(guò)程彼此之間并不相互獨(dú)立，即前一個(gè)模型中所用到的特征點(diǎn)有可能被應(yīng)用到計(jì)算下一個(gè)新的車(chē)道線(xiàn)模型中，造成某些特征點(diǎn)的重復(fù)使用，嚴(yán)重影響了算法的實(shí)時(shí)性和魯棒性。

針對(duì)RANSAC算法的上述問(wèn)題，本文中提出一種實(shí)時(shí)性強(qiáng)、魯棒性高的改進(jìn)RANSAC算法。

1 改進(jìn)RANSAC算法

本文中提出的改進(jìn)算法適用于各種車(chē)道線(xiàn)模型，為了描述方便，采用直線(xiàn)模型?？紤]到RANSAC算法的特點(diǎn)和實(shí)時(shí)性要求，對(duì)左、右車(chē)道線(xiàn)進(jìn)行獨(dú)立、并行的識(shí)別，這里以右車(chē)道線(xiàn)的識(shí)別為例，其流程圖如圖1所示，算法步驟如下。

(1)假設(shè)特征提取后右車(chē)道線(xiàn)存在區(qū)域的所有特征點(diǎn)構(gòu)成集合P，利用圖2(b)所示的掩模對(duì)該區(qū)域進(jìn)行濾波，令濾波后的右車(chē)道線(xiàn)區(qū)域的所有特征點(diǎn)構(gòu)成集合P*，則顯然有P*?P。

(2)在集合P*中隨機(jī)抽取n個(gè)特征點(diǎn)(本文各工況取n=2)構(gòu)成集合S，并用S初始化右車(chē)道線(xiàn)模型Modr。

(3)選取閾值容限di，并令余集Sc=PS中與右車(chē)道線(xiàn)模型Modr的距離小于di的點(diǎn)構(gòu)成集合Q，Q和S構(gòu)成一致內(nèi)點(diǎn)集S*。

(4)若集合S*中內(nèi)點(diǎn)的個(gè)數(shù)大于t(本文中各工況取t=12)，則認(rèn)為得到正確的右車(chē)道線(xiàn)參數(shù)，并利用集合S*中的點(diǎn)采用最小二乘法計(jì)算出新的右車(chē)道線(xiàn)模型Modr*;否則，轉(zhuǎn)到步驟(2)執(zhí)行。

(5)選取另一個(gè)刪除容限do，并且do≥di，如圖3所示。刪除構(gòu)成集合S*的所有內(nèi)點(diǎn)，和與模型Modr*的距離大于di小于do的全部特征點(diǎn)——最內(nèi)層外點(diǎn)，并存儲(chǔ)已計(jì)算出的模型Modr*參數(shù)。

(6)在集合P*中重新隨機(jī)抽取n個(gè)特征點(diǎn)構(gòu)成新的集合S并初始化右車(chē)道線(xiàn)參數(shù)，重復(fù)步驟(3)～(5)。

(7)完成K次抽取后，若未找到一致集則算法失敗;否則，選取特征點(diǎn)個(gè)數(shù)最多的S*內(nèi)點(diǎn)集合——S*max中的點(diǎn)計(jì)算出的車(chē)道線(xiàn)參數(shù)作為最終右車(chē)道線(xiàn)參數(shù)。

抽樣次數(shù)K的確定取決于集合S中n個(gè)特征點(diǎn)之間相關(guān)性的強(qiáng)弱。在實(shí)際應(yīng)用中很難精確地推算出K的取值，但可以在已知先驗(yàn)概率的情況下，計(jì)算出K的統(tǒng)計(jì)均值E(K)。若令w表示選中的n個(gè)特征點(diǎn)中任一特征點(diǎn)都滿(mǎn)足某一車(chē)道線(xiàn)模型的概率，則有

其中:b=wn;a=1－b

由冪級(jí)數(shù)性質(zhì)可知:

對(duì)式(2)求導(dǎo)可得

比較式(1)和式(3)可得

利用上述方法，同理可求出對(duì)應(yīng)于左車(chē)道線(xiàn)的參數(shù)。

2 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證改進(jìn)RANSAC算法的有效性，分別對(duì)各種路況下采集到的大量道路圖像進(jìn)行分析測(cè)試。因篇幅所限，同時(shí)為使實(shí)驗(yàn)結(jié)果更具代表性，下面僅給出兩種典型工況的識(shí)別結(jié)果:(1)復(fù)雜工況——特征點(diǎn)較少且分布不規(guī)則;(2)正常工況——特征點(diǎn)較多且分布規(guī)則。

2.1 復(fù)雜和正常工況下的實(shí)驗(yàn)結(jié)果

圖4(a)和圖4(b)為原始道路圖像，圖4(a)中的車(chē)道線(xiàn)被路旁樹(shù)木等造成的陰影嚴(yán)重遮擋，同時(shí)車(chē)道線(xiàn)被大面積的污跡覆蓋且部分標(biāo)識(shí)已破損。圖4(c)、圖4(d)為車(chē)道線(xiàn)特征點(diǎn)提取結(jié)果，由于陰影遮擋、污跡覆蓋和破損等原因使圖4(c)中提取出的左車(chē)道線(xiàn)特征點(diǎn)很少，且左、右車(chē)道線(xiàn)特征點(diǎn)的分布很不規(guī)則。圖4(e)、圖4(f)分別是圖4(c)、圖4(d)的左、右車(chē)道線(xiàn)存在區(qū)域分別經(jīng)圖2中對(duì)應(yīng)掩模進(jìn)行濾波的結(jié)果。

設(shè)圖4(c)中左、右車(chē)道線(xiàn)區(qū)域(即 A1、A2區(qū)域)的特征點(diǎn)總數(shù)分別為AL、AR，其中屬于左、右車(chē)道線(xiàn)上(即在圓形或梯形區(qū)域內(nèi))的特征點(diǎn)個(gè)數(shù)為aL和aR。圖4(e)中對(duì)特征提取結(jié)果進(jìn)行濾波后左、右車(chē)道線(xiàn)區(qū)域的特征點(diǎn)總數(shù)分別為ALF、ARF，其中屬于左、右車(chē)道線(xiàn)上的特征點(diǎn)個(gè)數(shù)為aLF和aRF。則可得上述數(shù)值及其相關(guān)比值如表1所示。

表1 復(fù)雜工況特征提取與濾波后的特征點(diǎn)數(shù)目對(duì)比

由表 1 可見(jiàn):ALF/AL、aLF/aL和 ARF/AR、aRF/aR的值較濾波前均變小，這意味著在特征提取結(jié)果的基礎(chǔ)上進(jìn)行濾波后，無(wú)論噪聲點(diǎn)還是車(chē)道線(xiàn)特征點(diǎn)均大幅減少，導(dǎo)致算法隨機(jī)抽取初始化模型的特征點(diǎn)所需的時(shí)間相應(yīng)地下降，算法的實(shí)時(shí)性得到很大提高;另外 aL/AL、aLF/ALF的值相差甚微、aR/AR、aRF/ARF的值雖然有差距但aRF/ARF的值仍在50%以上，由此說(shuō)明濾波后在較大提升算法實(shí)時(shí)性的同時(shí)魯棒性也能得到有效保證。

正常工況下特征提取點(diǎn)與濾波后的特征點(diǎn)數(shù)目對(duì)比如表2所示，表中符號(hào)含義同表1。

由表 2 可見(jiàn):ALF/AL、aLF/aL和 ARF/AR、aRF/aR的值相比復(fù)雜道路工況變得更小，這是由于正常工況下車(chē)道線(xiàn)上的特征點(diǎn)排列比較規(guī)則，因此算法隨機(jī)抽取初始化模型的特征點(diǎn)所需的時(shí)間將會(huì)更少，算法的實(shí)時(shí)性更好。

表2 正常工況特征提取與濾波后的特征點(diǎn)數(shù)目對(duì)比

表3 復(fù)雜工況d i=1時(shí)車(chē)道線(xiàn)參數(shù)及刪除后剩余點(diǎn)數(shù)

表4 復(fù)雜工況d i=2時(shí)車(chē)道線(xiàn)參數(shù)及刪除后剩余點(diǎn)數(shù)

d o=19 刪除點(diǎn)過(guò)多無(wú)法計(jì)算參數(shù) 0.796 7 80.25 － 51.7

表5 復(fù)雜工況d i=3時(shí)車(chē)道線(xiàn)參數(shù)及刪除后剩余點(diǎn)數(shù)

對(duì)特征提取后的復(fù)雜工況應(yīng)用改進(jìn)算法對(duì)其車(chē)道 線(xiàn)進(jìn)行識(shí)別，當(dāng)分別取di=1、2、3，在do取不同值時(shí)得到的車(chē)道線(xiàn)參數(shù)和正確識(shí)別參數(shù)情況下對(duì)應(yīng)左、右車(chē)道線(xiàn)區(qū)域所剩余的特征點(diǎn)占總特征點(diǎn)數(shù)百分比PL和PR的部分實(shí)驗(yàn)結(jié)果分別如表3～表5所示。其中 kl、bl和 kr、br分別對(duì)應(yīng)左、右車(chē)道線(xiàn)模型y=kx+b的兩個(gè)參數(shù)，由于車(chē)道標(biāo)識(shí)線(xiàn)自身具有一定的寬度和RANSAC算法抽樣的隨機(jī)性，導(dǎo)致表3～表5中在能正確擬合車(chē)道線(xiàn)情況下，參數(shù)bl、br在一定范圍內(nèi)變化。使用相似的方法可以得到正常工況下的參數(shù)識(shí)別結(jié)果。為了更好地研究算法的魯棒性，將復(fù)雜和正常工況參數(shù)的識(shí)別結(jié)果進(jìn)行了比較，如圖5所示。為繪圖方便而又不改變?cè)紨?shù)據(jù)所表征的含義，圖5中將車(chē)道線(xiàn)參數(shù)分別除以各自相應(yīng)的常數(shù)k0和b0，圖中位于最頂端的參數(shù)標(biāo)識(shí)表示由于刪除的特征點(diǎn)過(guò)多而無(wú)法識(shí)別，位于最底端的參數(shù)標(biāo)識(shí)則表示隨著do的增加而出現(xiàn)的車(chē)道線(xiàn)誤識(shí)別。根據(jù)識(shí)別出的參數(shù)，車(chē)道線(xiàn)擬合結(jié)果如圖6所示，其中虛線(xiàn)表示誤識(shí)別車(chē)道線(xiàn)，實(shí)線(xiàn)表示do取不同值時(shí)識(shí)別出的正確車(chē)道線(xiàn)。

2.2 實(shí)驗(yàn)結(jié)果分析與對(duì)比

(1)無(wú)論正常還是復(fù)雜路況，當(dāng)do在一定范圍內(nèi)變化時(shí)，車(chē)道線(xiàn)均能正確識(shí)別，并且隨著do的增大，刪除的特征點(diǎn)數(shù)量增加(復(fù)雜和正常工況最多可分別刪掉特征點(diǎn)總數(shù)的1/2和2/3)，算法的實(shí)時(shí)性提高，而魯棒性并沒(méi)有明顯降低。例如圖5(a)中do≤9以?xún)?nèi)，隨著do的增加，識(shí)別出的參數(shù)變化范圍在0.9～1.1之間。因此，在保證正確識(shí)別前提下，可適當(dāng)增加do以提高實(shí)時(shí)性，但do值不能取得過(guò)大以避免漏檢測(cè)更佳的車(chē)道線(xiàn)參數(shù)。大量實(shí)驗(yàn)驗(yàn)證和統(tǒng)計(jì)分析的結(jié)果表明:對(duì)于復(fù)雜工況do取值為7～9為宜;正常工況do取值為5～7較好。

同時(shí)，在do取值相同的情況下，由于正常工況下刪除的特征點(diǎn)數(shù)更多，導(dǎo)致余下的特征點(diǎn)之間的相關(guān)性減弱，從而造成識(shí)別出參數(shù)的不確定性更大。例如，圖5(c)中的左車(chē)道線(xiàn)在do=3、5時(shí)，正常工況都出現(xiàn)誤識(shí)別而復(fù)雜工況卻均能正確識(shí)別，然而當(dāng)do≥7時(shí)，由于正常工況下刪除的特征點(diǎn)較多，導(dǎo)致有時(shí)能正確識(shí)別而有時(shí)卻誤識(shí)別，而與其不同的是，復(fù)雜工況卻一直是由于刪除點(diǎn)過(guò)多而無(wú)法識(shí)別。

(2)di的選取對(duì)于兩種路況下車(chē)道線(xiàn)參數(shù)的識(shí)別影響并不顯著，例如對(duì)于復(fù)雜路況下的左車(chē)道線(xiàn)識(shí)別而言，當(dāng)di分別取1和2時(shí)，do分別取到7和9以后車(chē)道線(xiàn)無(wú)法識(shí)別，而當(dāng)di=3時(shí)，do只取到5以后便無(wú)法識(shí)別。因此改進(jìn)RANSAC算法的識(shí)別準(zhǔn)確性并不隨di的增加而提高。究其原因不難發(fā)現(xiàn)，參數(shù)di用于選取構(gòu)成一致集中的內(nèi)點(diǎn)，增加di會(huì)使內(nèi)點(diǎn)數(shù)量增多，但會(huì)降低它們之間的相關(guān)性，顯然，此種情形下的特征點(diǎn)增多并不利于算法魯棒性的增強(qiáng)，因此在使用該算法時(shí)，di值取1或2即可。

(3)當(dāng)do取不同值時(shí)，在正確識(shí)別車(chē)道線(xiàn)情況下，各參數(shù)位置總體都在某一定值附近上下波動(dòng)，變化范圍大約在10%以?xún)?nèi)，由此說(shuō)明算法實(shí)時(shí)性提高不以犧牲算法的魯棒性為代價(jià)。

(4)另外，從查閱的國(guó)內(nèi)外文獻(xiàn)來(lái)看，目前評(píng)價(jià)擬合結(jié)果的量化準(zhǔn)則主要是與已知的現(xiàn)實(shí)路面信息或仿真的虛擬道路進(jìn)行對(duì)比［11－12］;然而在車(chē)輛高速行駛情況下，現(xiàn)實(shí)路面精確信息的獲取并非易事。但是，從識(shí)別算法在車(chē)道偏離預(yù)警系統(tǒng)的應(yīng)用而言，提取車(chē)道線(xiàn)內(nèi)側(cè)更利于系統(tǒng)的實(shí)時(shí)性和可靠性。而當(dāng)使用圖2所示的掩模對(duì)特征提取結(jié)果進(jìn)行濾波后，恰恰能較多地提取出車(chē)道線(xiàn)的內(nèi)邊緣特征點(diǎn)，從而使擬合出的車(chē)道線(xiàn)是內(nèi)邊緣線(xiàn)的概率變大，為建立一個(gè)實(shí)時(shí)、有效的量化準(zhǔn)則奠定基礎(chǔ)。

2.3 其它工況的實(shí)驗(yàn)結(jié)果

為了進(jìn)一步驗(yàn)證改進(jìn)算法的可靠性和適用性，對(duì)多種工況進(jìn)行了實(shí)驗(yàn)研究，因限于篇幅，圖7僅給出了一些典型場(chǎng)景。結(jié)果表明對(duì)于路況較差的雨天、陰影遮擋、破損、夜晚車(chē)道線(xiàn)，無(wú)論是車(chē)道線(xiàn)曲率變化較小的直線(xiàn)道路或是曲率變化大的彎道，改進(jìn)的RANSAC算法均能準(zhǔn)確識(shí)別出車(chē)道線(xiàn)，具有較好的魯棒性。同時(shí)由于算法在迭代過(guò)程中能不斷刪除特征點(diǎn)，使算法的實(shí)時(shí)性也得到顯著提高。

3 結(jié)論

針對(duì)特征提取后車(chē)道線(xiàn)特征點(diǎn)較少、干擾點(diǎn)多或特征點(diǎn)分布很不規(guī)則的光照變化、破損、陰影遮擋、天氣變化和污跡覆蓋等路況，提出改進(jìn)的RANSAC算法進(jìn)行車(chē)道線(xiàn)特征點(diǎn)擬合。通過(guò)對(duì)不同工況下所進(jìn)行的大量實(shí)驗(yàn)，結(jié)果表明:改進(jìn)的RANSAC算法無(wú)論對(duì)于復(fù)雜工況還是正常工況下的直線(xiàn)或曲線(xiàn)道路均能實(shí)現(xiàn)車(chē)道線(xiàn)的正確識(shí)別，因此具有較好的魯棒性。同時(shí)，由于算法引入了刪除容限，使迭代過(guò)程彼此之間幾乎相互獨(dú)立，這樣不僅大大提高了算法的實(shí)時(shí)性，而且有利于得到最佳車(chē)道線(xiàn)參數(shù)。

［1］ Bertozzi M，Broggi A．GOLD:a Parallel Real-time Stereo Vision System for Generic Obstacle and Lane Detection［J］．IEEE Transactions on Image Processing，1998，7(1):62 －81．

［2］ Wang Y，Teoh E K，Shen D．Lane Detection and Tracking Using B-Snake［J］．Image Vision Compute，2004，22(4):269 －280．

［3］ Danescu R，Nedevschi S．Probabilistic Lane Tracking in Difficult Road Scenarios Using Stereovision［J］．IEEE Transactions on Intelligent Transportation Systems，2009，10(2):272 －282．

［4］ Cheng H Y，Yu C C，Tseng C C，et al．Environment Classification and Hierarchical Lane Detection for Structured and Unstructured Roads［J］．IET Computer Vision，2010，4(1):37 －49．

［5］ Borkar A，Hayes M，Smith M．A Novel Lane Detection System with Efficient Ground Truth Generation［J］．IEEE Transactions on Intelligent Transportation Systems，2012，13(1):365 －374．

［6］ Fischler M A，Bolles R C．Random Sample Consensus:a Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography［J］．Communications of the ACM，1981，24(6):381－395．

［7］ Lopez A，Serrat J，Lumbreras F，et al．Detection of Lane Markings Based on Ridgeness and RANSAC［C］．Proce．of IEEE Intelligent Transportation Systems，2005，254 －259．

［8］ Kim Z W．Robust Lane Detection and Tracking in Challenging Scenarios［J］．IEEE Transactions on Intelligent Transportation System，2008，9(1):16 －26．

［9］ Lopez A，Serrat J，Lumbreras F，et al．Robust Lane Markings Detection and Road Geometry Computation［J］．International Journal of Automotive Technology，2010，11(3):395 －407．

［10］ Mastorakis G，Davies E R．Improved Line Detection Algorithm for Locating Road Lane Markings［J］．IET Electronics Letters，2011，47(3):183 －184．

［11］ Mccall J C，Trivedi M M．Video-based Lane Estimation and Tracking for Driver Assistance:Survey，System，and Evaluation［J］．IEEE Transactions on Intelligent Transportation Systems，2006，7(1):20 －37．

［12］ Veit T，Tarel JP，Nicolle P，et al．Evaluation of Road Marking Feature Extraction［C］．Proc．of IEEE Intelligent Transportation Systems，2008，12－15．