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

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

前言

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

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

針對RANSAC算法的上述問題，本文中提出一種實時性強、魯棒性高的改進RANSAC算法。

1 改進RANSAC算法

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

(1)假設特征提取后右車道線存在區(qū)域的所有特征點構成集合P，利用圖2(b)所示的掩模對該區(qū)域進行濾波，令濾波后的右車道線區(qū)域的所有特征點構成集合P*，則顯然有P*?P。

(2)在集合P*中隨機抽取n個特征點(本文各工況取n=2)構成集合S，并用S初始化右車道線模型Modr。

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

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

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

(6)在集合P*中重新隨機抽取n個特征點構成新的集合S并初始化右車道線參數(shù)，重復步驟(3)～(5)。

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

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

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

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

對式(2)求導可得

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

利用上述方法，同理可求出對應于左車道線的參數(shù)。

2 實驗結果與分析

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

2.1 復雜和正常工況下的實驗結果

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

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

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

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

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

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

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

表3 復雜工況d i=1時車道線參數(shù)及刪除后剩余點數(shù)

表4 復雜工況d i=2時車道線參數(shù)及刪除后剩余點數(shù)

d o=19 刪除點過多無法計算參數(shù) 0.796 7 80.25 － 51.7

表5 復雜工況d i=3時車道線參數(shù)及刪除后剩余點數(shù)

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

2.2 實驗結果分析與對比

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

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

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

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

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

2.3 其它工況的實驗結果

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

3 結論

針對特征提取后車道線特征點較少、干擾點多或特征點分布很不規(guī)則的光照變化、破損、陰影遮擋、天氣變化和污跡覆蓋等路況，提出改進的RANSAC算法進行車道線特征點擬合。通過對不同工況下所進行的大量實驗，結果表明:改進的RANSAC算法無論對于復雜工況還是正常工況下的直線或曲線道路均能實現(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．