自動駕駛感知-稀疏3D鐳射點雲的高效線上分割

作者：由 Unixon 發表于收藏時間：2020-06-18

標題：Efficient Online Segmentation for Sparse 3D Laser Scans

作者：Igor Bogoslavskyi Cyrill Stachniss

原創不易，歡迎個人轉發朋友圈；

其他機構或自媒體如需轉載請留言申請授權

作為自動駕駛感知的開篇，今天為大家帶來的文章是——-Efficient Online Segmentation for Sparse 3D Laser Scans

本文提出一種高效的地面濾除+場景分割的方法，資料集上結果表明效果好於PCL點雲庫歐式聚類模組，且地面可以具有輕微的曲率，不一定必須完全平坦

。

論文目前相關程式碼已開源，有需要私信留言。

摘要

本文提出了一種有效的方法，首先從掃描影象中去除地面，然後將點雲圖像中的三維資料分割成不同的目標。工作的重點是確保可以幾百Hz速率快速執行。該實現對計算的要求很小，可在大多數移動系統上線上執行。明確避免3D點雲的計算，而是直接在2。5D範圍影象上進行操作，從而可以對每個3D掃描進行快速分割。該方法還可以很好地處理稀疏3D資料。在C ++和ROS中實現了所提出的方法，並使用不同的3D掃描器對其進行了全面測試，並將釋出實現的原始碼。該方法可以以比感測器高得多的幀速率執行，同時僅使用移動CPU的單核併產生高質量的分割結果。

主要貢獻

本文的貢獻是提出了一種將地面與場景的其餘部分分開的可靠方法，為了實現最終的分割，首先進行魯棒的地面分割，以便快速可靠地檢測地面。與別的方法相比，本文方法所適用的地面可以具有輕微的曲率，並且不一定必須完全平坦。且不必使用任何型別的子取樣，而是為距離影象的每個畫素（做判斷，以便）確定它是否屬於地面。下圖描繪了該方法去除地面的分割示例，其中使用Velodyne VLP-16掃描器的資料正確分割了人和汽車。

圖1 Velodyne VLP-16稀疏三維資料生成的物體（如人、車和樹）的分割。顏色對應不同的部分。

演算法流程

本文所提出的演算法分為兩大步驟：

1 地面濾除

2 場景分割

下面詳細說一說。

1 地面濾除

在進行場景聚類分割之前，首先得移除地面（點雲）。移除地面的標準方法是丟棄所有低於車輛的3D點（假設我們知道感測器在機器人上的安裝位置）。此方法可在簡單的場景中起作用，但如果車輛的俯仰角或側傾角不等於0或地面不是理想的平面，該方法將失敗。使用基於RANSAC的平面擬合可改善這種情況，但是非零曲率平面的擬合效果仍然很垃圾（很耗時）。因此，該文采用了不同的方法。

大多數Lidar以每個鐳射束的單個距離讀數的形式提供原始資料，並帶有時間戳和光束方向。因此可以直接將資料轉換為距離影象（range image）。影象中的行數由垂直方向上的鐳射束的個數定義，如Velodyne Lidar的鐳射束數有16，32，64線的，則影象行數分別是16，32，64。

列數

由Lidar旋轉360°範圍的讀數個數給出（與Lidar水平解析度、視場角有關）。這種虛擬影象的每個畫素都儲存了從Lidar到物體的測量距離。為加快計算速度，甚至可以將水平方向的多個讀數合併為一個畫素。

該方法使用上述所說的距離影象，並直接從Lidar的原始測量結果構建該距離影象，而不是計算3D點雲。

為了確定地平面，先做出

三個假設。1

，我們假設感測器大致水平安裝在移動基座/機器人上（這個假設可以放寬，但說明會變得更加複雜）。

，我們假設地面的曲率很低。

，我們假設機器人/車至少在距離影象最低行的某些畫素中觀察到地平面（對應於靠近機器人的接近地面的鐳射束掃描）。（

即Lidar在該次掃描中最靠下的鐳射束一定掃描到了地面

）。

有了這些假設，我們首先將距離影象R的

每一列

c轉換為一堆角的集合

$\alpha_{r-1, c}^{r}$

，其中每個角都代表了連線兩個點A和B的直線的傾斜角度，而A，B點是源自於距離影象R中相鄰兩行r-1、r的兩個距離讀數

$R_{r-1, c}$

和

$R_{r, c}$

（

同一列c的相鄰兩行

）。如下圖所示：

圖2 左上圖部分是距離影象。中左圖是由不同α角生成的影象。底部左圖示由應用了Savitsky-Golay平滑濾波α後生成的圖。右上圖說明了α角度。底部左圖說明了左圖中是如何平滑α列。

知道垂直連續的單個鐳射束的兩個距離讀數，我們可以使用如下三角規則計算角度α ：

其中

$\xi_{a}$

和

$\xi_{b}$

是對應於行r-1、r的鐳射束的垂直角度（與圖中x軸的夾角）。

注意，為了計算每個α我們需要知道2個距離讀數（

每2個距離確定一個α

），所以α角的個數必定小於距離影象R的行數。然後，我們將所有這些α角視為一個矩陣

$M_{\alpha}=\left[\alpha_{r-1, c}^{r}\right]$

其中r和c是距離影象中相應距離讀數的行和列標。

不幸的是，諸如Velodyne HDL-64之類的Lidar感測器在距離測量中

會產生大量異常值

，Leonard等人的工作對此進行了詳細討論。這會影響上圖2所說的α的計算，所以需要採用一種消除異常值的方法，Weinmann和Jutzi透過在距離影象的每個畫素的

小區域性鄰域

上計算

特徵以檢測讀數是否可以視為可靠

來解決此問題。這種方法可以濾除不可靠的讀數，還可以濾除物件邊界上的點。由於這些點（是否異常值的點）對於執行分割非常重要，因此我們改為從所有可用資料點計算相應的角度（α），然後平滑計算的角度。為了實現這種平滑，我們將Savitsky-Golay濾波應用於

$M_{\alpha}$

的每一列。該濾波器執行最小二乘法最佳化，以將給定視窗大小的區域性多項式擬合到資料。Savitzky和Golay在他們的工作中表明，可以避免多項式的顯式最小二乘擬合，並依靠預先計算的係數來計算有效的近似值，從而可以提高計算效率。

將Savitsky-Golay濾波器應用到用於地面標記的矩陣

$M_{\alpha}$

的每一列之後，從我們預期屬於地面的行開始，並使用廣度優先搜尋將相似的元件標記到一起（

標記是否為地面行

）。廣度優先搜尋（BFS）是一種流行的圖形搜尋或遍歷演算法。它從圖的給定節點開始，先探索直接相鄰的節點，然後再移動到下一個相鄰層。在我們的方法中，考慮在網格上的N4鄰域上計算α的差異，以來決定矩陣

$M_{\alpha}$

的兩個相鄰元素是否應該被判定為一體（

together，即是否來自同一目標物

）。為此選擇一個閾值

$\Delta a$

並設定為5°。

首先將最低

行

的每個元素標記為地面（如果相應的

$\alpha_{0, c}^{1}$

小於預定義的角度，本例中為45°）。我們不標記任何幾乎垂直的物件，例如牆。令集合G為第一行中所有我們標記為地面的

列

索引的集合。↓↓↓↓

下圖3顯示了用該演算法檢測到地面的點雲示例（淺藍標記）。

圖3 示例場景俯檢視，地面用淺藍色標出

2 場景分割

場景分割的重點是線上快速處理3D距離資料分割，感測器（Lidar）的垂直解析度會影響分割問題的難度。對於每一對相鄰點來說，必須判定鐳射束是否由同一物體反射。

在下圖4概述的方法中，沒有顯式建立3D點雲，並使用鐳射距離影象執行計算。這有兩個優點：1，可以直接在距離影象中利用清晰定義的鄰域關係，這使分割問題變得更加容易。2，避免生成3D點雲，這使整體方法的計算速度更快。

圖4 方法說明。A：來自velodyne Lidar的點雲圖，僅用於說明。B：不考慮地平面點所建立起的距離影象。C：在距離影象上直接執行場景分割。D：為不同的分割片段提供小點雲。不同的物體以隨機顏色顯示。

提出了一種易於實現且計算速度快但有效的方法來查詢屬於同一個物件的元件（判斷點是否來自同一個物件）。為了回答兩個鐳射測量值是否屬於同一物體的問題，使用基於角度的測量方法，該方法在下圖5中進行了說明。

圖5 左邊有兩個行人，一個騎腳踏車的人和一輛汽車的場景。中間假設感測器在O點，而OA和OB線代表兩束鐳射束，點A和B生成一條同於判斷是否屬於同一物件的線，並根據β的角度來判斷。如果β&；amp；gt；θ，其中θ是一個預定義的閾值，則認為A、B是來自同一物件的兩點。右：從示例場景看行人的頂檢視。

假設A和B的座標位於以O為中心的座標系中，並且y軸沿兩個鐳射束中的較長者取向（此處為OA）。定義角度β表示鐳射束OA與AB的之間的角度。實踐證明，角度β也確實能確定點A和B是否屬於同一物體。

由Lidar性質，可以知道OA、OB分別對應第一、二次掃描返回的距離值。在此分別記為d1、d2。且可以由下式計算β：

其中

$\psi$

是已知的相鄰兩個鐳射束的平移角度（一般在Lidar文件說明書中提供，與水平解析度、角解析度有關）。注意我們透過（距離影象中的）

相鄰行

、或者

相鄰列

都可以獲取

兩個點

來帶入上式

計算β值

。在本例中是透過相鄰行的角度增量

$\psi$

來計算β，其他情況下使用相鄰列的兩束鐳射增量角度（Lidar的垂直解析度）也可以來計算β。

直覺上來說，對於大多數情況而言這個角度β是比較大的，並且在

給定的距離影象下相鄰兩點間的深度差>其在影象平面中的位移

（Lidar水平方向角解析度）

時β才比較小

。基於此，我們可以預定義一個引數

作為β的閾值，這個

可以

用於判斷

兩個點是來自同一個目標物，還是來自不同的目標物（即可用來

場景分割

）。如果β<θ，則認為深度變化太大，這兩個點被視為不同的部分，反之，則視為來自同一部分。

這種設定閾值的方法顯然是一種啟發式的方法，但是在實際中卻表現的很好。不過也有些許故障情況，例如遇到牆壁或者障礙物幾乎平行於LIdar鐳射束的情況，在這些情況下，β很小，所以目標物可能會被分成多段（過分割），

這也意味著若β<θ，很難確定兩個點是來自不同的物體or來自牆壁（同一物體：牆壁）

。不過沒關係，一來這種情況較少發生，再者也只會導致過於傾斜的物體被過度分割而已。

下面重點來了

，考慮閾值引數θ，並且考慮了矩陣網格上的N4鄰域的點。

即，如果點B是來自點A的N4鄰域上的點，且A、B的β>θ，則仍然認為A，Bl來自同一物件

。演算法如下：

Algorithm2描述如何發現點/碎片是相聯通的（來自同一物體）。用了複雜度O（N）的直通濾波變體，其中N是畫素個數，即掃描的每一幀距離影象的距離讀數（點的個數）。該演算法保證至少將距離影象中的點遍歷兩次。

且注意，所有在algorithm1中被標記為地面的點，在algorithm2中都會被置為0，且不參與algorithm2的處理。

Algorithm2從（掃描的每一幀的）距離影象的左上角開始，自上到下，從左到右遍歷每一個畫素（line3-4），當遇到未標記的畫素（line5），便從此畫素處用廣度優先搜尋BFS（line6），其目的是標記該元件上的每一個畫素。基於此，BFS搜尋用了由上下左右構成N4鄰域的佇列（來儲存資料）（line11，12，13）。然後遍歷鄰域，距離大的記為d1、距離小的記為d2（line14，15），並計算β後與θ比較（line16），判斷該畫素（點）的取捨（line17，18）。

主要實驗結果

實驗展示了

1 所有計算都可快速執行，移動單核70 HzCPU

2 將典型3D資料分割為有意義的段

3 該方法在稀疏資料（16線Velodyne Lidar資料）上表現良好

還提供了與Behley等人使用的Teichman和Thrun（2012）提出的基於網格的分割方法的比較。以及在

點雲庫PCL

中歐幾里得聚類的方法。

在所有實驗中，都使用預設引數θ = 10°。

兩種計算裝置對比：

1 i5 5200U 2。2 GHz CPU Acer膝上型電腦

2 i7 4770K 3。5 GHz CPU 臺式計算機