基于改進RANSAC算法的車道線識別方法*

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

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

前言

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

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

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

1 改進RANSAC算法

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

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

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

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

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

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

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

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

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

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

由冪級數性質可知:

對式(2)求導可得

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

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

2 實驗結果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 實驗結果分析與對比

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

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

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

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

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

2.3 其它工況的實驗結果

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

3 結論

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

［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．