重磅乾貨，第一時間送達
本文轉自：AI演算法與影象處理
本文討論的重點跟蹤演算法如何應用在車道線應用中，即從得到車道線檢測結果開始，到連續穩定地車道線跟蹤的過程。包含車道線模型、魯棒的擬合方法和跟蹤。
車道線檢測和跟蹤是自動駕駛中必不可少的功能，LDW（車道偏離預警）、LKA（車道保持輔助）等功能模組都依賴於連續穩定的車道線檢測和跟蹤。（多）目標跟蹤演算法已經得到充分研究，而且相關演算法解析和綜述網上已經有很多了，也可以在計算機視覺life相關文章中找到，不再贅述。但是以上跟蹤的分析，大多針對點目標，而此處我們關注跟蹤演算法如何應用在車道線應用中。一般來說跟蹤和檢測需要分開實施，如果有端到端一步實現檢測+跟蹤的方法，煩請不吝賜教。
本文先簡單介紹車道線檢測結果和問題，然後建立車道線的多項式模型，以及獲得模型引數需要的魯棒的擬合算法。接著介紹常見的跟蹤演算法，以Kalman濾波為主。最後是車道線相關資源乾貨分享。
獲得車道線檢測結果
車道線跟蹤前提是拿到車道線檢測結果。車道線檢測的傳統影象處理方法有：梯度+顏色資訊、引數空間投票、邊緣檢測+Hough變換及其變形、k-means聚類和利用影象特徵檢測等方法。傳統的車道檢測方法需要高度定製化，包括許多手工特徵提取和後處理方法。當測試環境改變時，常常需要大量調參工作，甚至需要更換後處理方法。很多時候需要在鳥瞰圖上利用車道線空間相互關係進行處理。
近兩年（從2017年開始）開始出現了許多基於深度學習的方法，如SCNN，VPGNET，Lanenet，甚至是影象分割（可通行區域）等，實現了端到端的檢測，在原圖上很好的利用了環境資訊，提高穩定性。
除了檢測出存在曲線和位置，還要區分出不同車道的車道線，通常需要提供左左，左，右，右右共四條車道線，即能區分出三條車道。
這裡檢測結果應包括點座標、顏色、線型、置信度等資訊。當然也有研究把線型的確定稱為車道線識別。
當狀況良好的時候，僅靠車道線檢測就能連續輸出車道線，例如網上廣為流傳的Udacity提供的開源專案［8］，僅靠梯度+顏色資訊的檢測方法，就能檢測出幾乎所有幀裡的車道線，沒有明顯遺漏。因此後處理只需要對車道檢測出來的點進行擬合併延伸到滅點即可，無需更多跟蹤過程。如下圖所示，當前車道線被紅色線標記出來。
但是幾乎所有實際路況，或多或少存在路面有修補、有積水、有陰影、車道線被遮擋、汙損等情況以及車輛顛簸、上下坡等更極端的工況。下面的動圖是LaneNet原始檢測結果（from Karol Majek），車道線檢測出的機率越高的地方顏色越亮。其中右側路沿綠色的檢測結果時斷時續，在進入陰影時，檢測失效，這是因為沒有用跟蹤進行結果穩定。因此，引入了車道線跟蹤很重要，根據歷史狀態和道路幾何關係，補充檢測丟失、錯誤的車道線，並使車道線在空間位置上更穩定。
建立車道線模型
跟蹤第一步，是要根據場景要求，合理地用較少引數準確描述出車道線，即把檢測結果抽象成模型引數。但直接用圖片畫素上的曲線建立模型並不理想，而是需要轉換到車體座標系下建立模型，這是因為車體座標系下模型引數的物理意義才更清晰。而且通常冗餘設計包含多個相機，多個相機也必須統一到車體座標系。通常使用逆透視變換把圖片座標轉化為車體座標。下圖左紅色座標系定義了車體座標系，座標系原點為車輛中心（根據不同標準車輛中心位置定義不同，不具體討論）。
假設路面水平，車道線模型可以用多項式
來表示，但是其中的多項式係數
的物理含義並不直觀。我們可以改寫成如下形式
其中
是車道線的位置即截距（
），
是車道線角度（
），
是車道線曲率（
），
是車道線曲率的變化率（
）。車道線曲率半徑為
（
），如上圖右上的Radius of Curvature的數值。以上所有引數都是在
處分析的，透過對
求多次導得到。需要說明的是，公式進行了必要的近似，只有車輛沿道路正常往前開或轉向不明顯——即
較小——時，角度
才近似於一階項係數
，曲率也才能近似於
的二階導數（可參考曲率的定義）。
另外，也有文獻用車道寬度、車中心偏離車道中心位置、車道線角度以及曲率四個引數來表徵車道線，如文獻［1］ 。還有文獻採用二次B條樣函式表示車道線模型。
作為一般討論，這裡用水平路面四個引數
表徵一條車道線，較簡潔，而且和真實物理量之間也有清晰的對應關係。
魯棒的曲線擬合
選定車道線模型後，需要利用車道線檢測結果（通常為散點，需要事先變換到車體座標下）擬合該模型的引數。這裡主要介紹兩種比較常用的方法，最小二乘法和RANSAC（隨機抽樣一致性），此處假設大家都大概瞭解這兩個演算法的原理。
最小二乘法是最小化殘差平方和的一種最最佳化方法，廣泛應用的原因之一是其平方和的形式，便於整理成矩陣相乘的形式，例如線性最小二乘容易得到閉合解
，其中
是包含
、
、
、
的矩陣。而且平方形式便於求導和泰勒展開，才能有後面的Gauss-Newton和LM最最佳化迭代演算法。
不過，最小二乘法的過擬合問題會顯著影響車道線擬合效果，造成泛化誤差增加。因為車道線引數在一定範圍內不會有特別大的突變，如很少曲率特別大的彎道等，所以車道線以低階多項式表達為主，根據經驗，二階形式能表示大部分情況。這種情況下如果有車道線檢測有誤差，會使得擬合曲線曲率異常，此時車道線模型中的三階項就會產生明顯的問題（此時三階項係數
可能會異常的大），如下圖所示。而且同一條線前後幀可能也會跳動劇烈，因為幀與幀之間的噪聲不同，擬合誤差大。解決辦法之一是直接降低擬合階數，不過最好能夠自適應地調節並切換模型階數，否則失去了該模型的意義。還可以採用帶正則項的最小二乘，閉合解為
，其中
是正則係數。因為正則化抑制了係數的異常變大，降低了噪聲的影響。下圖是直接最小二乘和帶正則項的最小二乘的擬合效果比較，可以看到後者在高階擬合時對噪聲不那麼敏感（此處擬合階數大於3階，只是為了展示問題）。
即便如此，最小二乘可能仍然不夠魯棒，因為最小二乘要用所有輸入的點來計算，異常點不可避免地影響到擬合效果。例如有較大誤差的噪聲訊號的情況（下圖左），或者有多條車道線結果被錯誤包含在一條車道線的結果中的情況（下圖右）。
RANSAC演算法提供了另一種魯棒性擬合的思路。RANSAC透過迭代演算法找到包含最多內點（實際有用的資料點）數量的擬合曲線。由於只用內點進行擬合，而噪聲或另一車道線的資料就會被當成外點，外點對擬合沒有任何貢獻。該演算法用隨機資料抽樣的資料來擬合，因此一定機率能找到最優擬合曲線。但是，當這個機率——擬合置信度
——很大時，如
，就可以認為找到的曲線近似等於實際的曲線。經實驗驗證，對於包含
%誤差的資料集，RANSAC的效果遠優於直接最小二乘法。
RANSAC演算法收斂的關鍵在於引數的選取，引數有：某個點是外點的機率（噪聲或者錯誤車道線）
，每次抽樣的點數
，抽樣次數
和演算法收斂設定的
閾值，這幾個引數的關係如下圖所示。下圖的表格為不同條件下
的選取。另外，還有一個引數是內點選取範圍距離
，該值與
和樣本點方差
有關，如
時，
。
當然RANSAC演算法在某些情況下也會擬合錯誤，還有其他的魯棒的演算法，如Least Median Squares （LMS）、Preemptive RANSAC、PROgressive Sample and Consensus （PROSAC）、M-estimator Sample and Consensus （MSAC） 等。
擬合後即可以得到車道線模型中的多項式係數
。
選擇車道線跟蹤方法
跟蹤需要完成的任務是對目標和其他狀態量（對於本研究為多項式係數
）進行增加、預測、更新和刪除四個操作。以下表格羅列了部分文獻的車道線跟蹤的方法。
比較常用的跟蹤方法之一是Kalman濾波及其變形，這種方法對於比較理想的車道線（中斷、遮擋或模糊等比較少）有較好的跟蹤效果。Kalman車道線跟蹤的過程如下：
（增加）剛開始增加車道線狀態量向量
作為初始化。之後，只要本時刻有新檢測結果輸入，而上一幀沒有對應的車道線資訊，即把新檢測到的車道線狀態量為
賦給
，即增加一條車道線。此處檢測量由測量方程決定，由於測量系統引數矩陣
為單位矩陣，計檢測到的
就是
，因此忽略測量方程。
（預測）首先需要透過上一時刻車輛狀態資訊
（車速和車輛角速度）和上一時刻狀態量
預測本時刻狀態量
，即狀態方程為
，其中
是和車速有關的矩陣，
是和角速度有關的矩陣，合起來代表以上一時刻車輛狀態為條件，對本時刻狀態量的預測。
（更新）如果本時刻某條預測好的車道線和本時刻檢測到的車道線滿足某種匹配規則，即可認為是同一條車道線，需要用Kalman增益
綜合利用預測和檢測的資訊來更新車道線狀態。具體做法：系統協方差矩陣更新為
，通常測試場景一定，假設系統噪聲協方差矩陣
為一個固定的對角方陣。隨後計算
此處測量協方差矩陣
為對角方陣，可以根據當前檢測結果的置信度而改變。最後得到更新的本時刻狀態為，更新的本時刻協方差矩陣為
。其中最關鍵的
是衡量更相信檢測結果的程度，或可理解為機率。當檢測抖動較大、車道線不清晰、遮擋嚴重等情況，檢測的置信度下降，
減小，更相信預測，因此起到穩定車道線的作用。
（刪除）如果某條車道線一直是預測得出的，並沒有匹配上新檢測的車道線進行更新，則當前時刻如果預測次數大於某一壽命閾值後，就刪除。
如果採用更復雜的模型，例如狀態方程或測量方程是非線性的，以上Kalman濾波不再使用，需要使用拓展Kalman濾波（EKF）。EKF是在把非線性關係透過泰勒級數展開（忽略高次項）轉化成（偽）線性關係基礎上的Kalman濾波。
近年來粒子濾波也廣泛運用在車道線檢測中，因為Kalman濾波基於噪聲高斯分佈的假設，而車道線噪聲分佈通常不符合這個分佈，因此粒子濾波一定程度上解決了噪聲任意分佈下的跟蹤問題。也有研究把Kalman濾波和粒子濾波結合起來，同時具備Kalman濾波穩定的優點和粒子濾波環境適應性強的優點。
至此，經過跟蹤處理，就能夠輸出空間上比較穩定、時間上比較連續的車道線模型引數了。利用這些模型引數，就可以把車道線結果重新投影到原圖上，把結果顯示出來。
資源分享
感覺分享些資源乾貨可以有效地提高流量，所以我也放了些覺得比較好的連結。
偏重於車道線跟蹤的文獻和綜述：
［1］ 2006-Video-based lane estimation and tracking for driver assistance Survey， System， and Evaluation
［2］ 2009-Probabilistic Lane Tracking in Difficult Road Scenarios Using Stereovision
［3］ 2013-Integrated Lane and Vehicle Detection， Localization and Tracking A Synergistic Approach
［4］ 2016-A REVIEW ON LANE DETECTION ANDTRACKING TECHNIQUES
［5］ 2006-Single Camera 3D Lane Detection and Tracking Based on EKF for Urban Intelligent Vehicle
［6］ 2006-Realtime lane tracking of curved local road
［7］ 2009-ROBUST LANE DETECTION AND TRACKING WITH RANSAC AND KALMAN FILTER
開源專案和專案分享：
［8］ Udacity自動駕駛專案。https：//github。com/udacity/CarND-Advanced-Lane-Lines，https：//zhuanlan。zhihu。com/p/52623916
［9］ 百度無人車車道線檢測挑戰賽。https：//github。com/gujingxiao/Lane-Segmentation-Solution-For-BaiduAI-Autonomous-Driving-Competition
［10］ galenballew/SDC-Lane-and-Vehicle-Detection-Tracking（https：//github。com/galenballew/SDC-Lane-and-Vehicle-Detection-Tracking）
［11］ 車道線檢測集錦，其中包括2017-2019年最新的文章、原始碼、blog和資料庫等（深度學習的檢測和分割內容較多，跟蹤內容較少）。https：//github。com/amusi/awesome-lane-detection
下載1：OpenCV-Contrib擴充套件模組中文版教程
下載2：Python視覺實戰專案52講
下載3：OpenCV實戰專案20講