導讀：簡單來說，激光雷達(LiDAR)的原理是通過發射單元發射激光束，遇到障礙物后進行反射，并被接收單元捕獲，通過測量每束激光飛行時間(TOF，TimeofFlight)來確定障礙物的距離，并且構建點云。
當激光雷達的質量(價格)非常高時，每秒可以發射多達200萬激光束，意味著有200多萬個點云，點云代表3D世界，因為激光雷達獲取的是每撞擊點的準確三維坐標(X,Y,Z)。從而構建豐富的環境3D場景。
激光雷達的缺點是什么？
1. 激光雷達不能直接估計速度。他們需要計算兩次連續測量之間的差異才能做到這一點。
2. 激光雷達在惡劣的天氣條件下無法正常工作。在有霧的情況下，激光可以擊中它并混淆場景。類似于雨滴或泥土。
3．激光雷達在尺寸方面很笨重——它們不能像相機或雷達那樣隱藏起來。
4. 激光雷達的價格雖然在下降，但仍然很高。
激光雷達有哪些優勢？
1．激光雷達可以準確估計障礙物的位置。到目前為止，我們還沒有更準確的方法來做到這一點。
2.如果我們看到車輛前面的激光雷達生成的點云，即使障礙物檢測系統沒有檢測到任何東西，我們也可以停下來。
使用 LiDAR 進行“對象檢測”有兩種主要方法：
1．用無監督機器學習技術
2．使用3D深度學習
下面主要介紹第一種方法，該方法主要有4個步驟：
1.點云處理；
2.點云分割；
3.障礙物聚集；
4.編輯框擬合；
一、點云處理——體素網格
體素網格是一個 3D 立方體,通過每個立方體只留下一個點來過濾點云。
立方體越大，點云的最終分辨率越低。最后，我們可以將云的采樣從 100000點降低到只有幾千點。對點云就行采樣處理完后，就可以進行分割、聚類和邊界框的實現。
二、3D云分割——RANSAC(隨機抽樣一致性算法)
點云分割的任務是將障礙物從場景中區分出來。
RANSAC（隨機抽樣一致性算法）
一種非常流行的用于分割的方法稱為RANSAC(隨機抽樣一致性算法)，該算法的目標是識別一組點中的異常值。點云的輸出一般代表一些形狀。有些形狀代表障礙物，有些則簡單地代表地面上的倒影。RANSAC 的目標是識別這些點并通過擬合平面或線將它們與其他點分開。
為了擬合一條線，我們可以考慮線性回歸。但是有這么多的異常值，回歸會試圖平均結果并錯過這條線。與線性回歸相反，這里的算法將識別這些異常值。
我們可以將這條線視為場景的目標路徑（即道路），將異常值視為障礙物。
它是如何工作的？
過程如下：
1、隨機選擇2個點
2、將線性模型擬合到這些點
3、計算每隔一個點到擬合線的距離。如果距離在定義的距離容差范圍內，我們將該點添加到內層列表中。因此它需要一個參數：距離容差。最后，選擇內層數最多的迭代作為模型;其余的都是異常值。這樣，我們就可以把每一個內線都看作是道路的一部分，把每一個異常值都看作是障礙的一部分。
RANSAC 也適用于 3D。在這種情況下，3 點之間的平面是算法的基礎。然后計算點到平面的距離。
下圖是點云上的 RANSAC 算法的結果。紅色區域代表車輛，而地面為綠色。
RANSAC 是一種非常強大且簡單的點云分割算法。它試圖找到屬于同一形狀的點，以及不屬于同一形狀的點。然后，它可以分離云。
三、聚類-歐氏與KD樹
RANSAC的輸出是一個障礙點列表，一個道路點列表。由此，我們可以為每個障礙定義獨立的簇。聚類是一種根據點的距離將一組點分開的技術。考慮到上面的圖像，我們有一些可見的障礙，我們需要算法本身來理解實際上有多輛車，并為每個障礙設置一種顏色。
它是如何工作的？
聚類是一系列機器學習算法，包括：k-means（最流行的）、DBScan、HDBScan 等我們可以簡單地使用歐幾里得聚類并計算點之間的歐幾里得距離。
過程如下：
1、選擇 2 個點，一個目標和一個當前點。
2、如果目標與當前點之間的距離在距離容差范圍內，則將當前點添加到集群中。
3、如果沒有，請選擇另一個當前點并重復。
聚類算法將距離容差、最小聚類大小和最大聚類大小作為輸入。這樣，我們可以過濾“幽靈障礙物”（無緣無故地在空間中的一點上的一個點云）并定義封閉障礙物的距離。
計算和 KD 樹
上述技術的問題在于，一個 LiDAR 傳感器可以輸出 100,000 個點云。這將意味著 100,000 次歐幾里得距離計算。為了避免計算每個點的距離，我們可以使用 KD 樹。
KD樹是一種搜索算法，它將根據點在樹中的XY位置進行排序。一般的想法是，如果一個點不在一個定義的距離公差內，那么其x或y更大的點肯定不會在這個距離內。這樣，我們就不用計算所有的點。
以上面的這種情況為例，底部的橙色點不低于距離容差閾值。我們可以刪除這個橙色點右側的每個點，因為我們確信它們也不會在容差閾值內。然后我們可以取另一個點，計算距離，然后依次重復。
KD 樹非常適合計算——歐幾里得使得計算量大大減少。再加上聚類算法，它們是有效獲取獨立障礙物的強大工具。
四、邊界框
最終目標是在每個集群周圍創建一個 3D 邊界框。這部分不是特別難，但它對障礙物的大小做出了假設。由于我們沒有進行任何分類，我們必須將邊界框與點相匹配。一種可以幫助擬合邊界框的算法是主成分分析 (PCA)。使用 PCA，我們可以繪制一個與點云完全對應的邊界框。
通過結合上面討論的所有 3 種技術，我們有一個基于 LiDAR 點云的障礙物檢測算法！其結果如下所示。
LiDAR是一種非常強大且可靠的傳感器，在機器人技術中得到了廣泛應用。一段時間以來，LiDAR技術因其笨重的尺寸和價格而飽受詬病，使其成為精英傳感器。隨著價格的下降，甚至獨立開發者也可以使用它。
隨著 LiDAR 的可用性，獲得使用該傳感器的技能將成為工程師的真正優勢！傳感器融合也是一個引人入勝的話題，只有掌握了 LiDAR + 攝像頭或 LiDAR + RADAR 檢測才有意義。
來源：汽車ECU開發 作者：eng2mot
