基于3D LiDAR點云的圖分割算法

朱麗娟

摘 要：隨著無人車應用領域的不斷擴大以及激光雷達掃描技術的飛速發展，針對3D激光雷達點云數據處理技術研究對于人車領域的發展有重要意義.環境感知作為無人車系統的重要組成部分，對整車起著至關重要的作用.針對無人車基于激光雷達點云的環境感知中障礙物檢測問題進行研究，提出了一種基于3D激光雷達點云的檢測算法.該算法使用了基于圖的點云分割方法.該方法可以對激光雷達點云進行快速分割，高效的將點云分割出障礙物點.針對城市道路中的車輛、行人等障礙物的實驗效果表明，該方法對這類障礙物有良好的分割效果.該算法具有高的實時性，能夠滿足無人車的需求.

關鍵詞：激光雷達；環境感知；障礙物檢測；點云分割；圖分割

1 引言

中國是全球最大的汽車產銷國，2016年中國汽車產量和銷量分別超過2800萬輛，連續八年穩居全球第一.汽車的智能化和電動化是歷史送給中國汽車人的天賜良機，適逢其會，無人駕駛技術的應用必將引起產業的重大顛覆.更為了減少交通事故，提高運輸效率，減輕駕駛員勞動負荷，無人車自動駕駛技術應運而生.無人車是一個復雜的系統性工程，涉及環境感知、行為預測、規劃控制、智能互聯、車載硬件、人機交互等多項自動駕駛相關的核心技術，涵蓋了模式識別、圖像處理、控制與決策、傳感器等多個學科的科研成果.

作為無人駕駛流程中最為底層也最重要的感知層對無人駕駛技術發展起著至關重要的作用.目前，無人車感知方法使用的傳感器大致可分為視覺傳感器、激光傳感器、微波傳感器等.其中激光雷達能夠獲取車身周圍百米內的三維環境，通過對激光點云的處理能夠準確的進行場景分割.激光雷達的優點在于精度高，能夠直接獲取物體的三維空間信息.對光照環境的變換不敏感，能夠全天候使用.障礙物檢測是激光雷達最基本的環境感知能力.激光雷達能夠準確定位障礙物位置并能從三維場景中提取出障礙物信息.

本文使用點云分割方法對障礙物進行檢測.分割是將三維空間中的點劃分成更小的、連貫和連接的子集過程.經過分割后，具有相似屬性的點歸為一類.分割后的結果應該得到一系列我們感興趣的對象，如城市道路中車輛、行人、樹木等.點云分割將點云自動劃分為特征單一且互不重疊的區域.

1999年 Jain指出著名的圖論分割聚類算法的主要思想是：構造一棵關于數據的最小生成樹（minimal spanning tree，簡稱MST），通過刪除最小生成樹的最長邊來形成類.基于圖的圖像分割算法是圖像中經典的分割算法，本文參考這一算法的思想將其應用到3D點云分割中，實現對3D點云數據的快速有效自動分割.

本文第2節給出算法的詳細描述.第3節結合具體例子將本文算法與人工分割結果進行實驗比較和分析.第4節給出結論.

2 圖分割算法

2.1 圖的定義

我們使用基于圖的方法分割3D點云.圖是由頂點集V和邊集E組成，表示為G=（V，E），頂點v∈V，在本文中頂點集V是點云中點的集合，這些點將會被分割為區域；一對頂點的邊，表示為（νi，νj）∈E，每條邊有權值w（νi，νj），本文中權值是一個非負數，表示νi，νj頂點之間的差異性.權值w設為一對頂點間的歐式距離，我們用歐式距離來衡量兩點之間的差異性（即非相似度）.算法思想是把頂點集V中相似的點分割成區域C，區域中的點屬于一類.設點云分割后的結果為分割集S，C是分割集S的一部分，表示為C∈S， 并且分割區域C也是一個圖G`=（V，E`），E`∈E.我們希望在一個區域內點是相似的，區域間點是非相似的.這意味著在區域內的兩點之間的邊權值差異性是相對低的，區域間邊權值差異性是高的.

2.2 區域的定義

我們定義D，來判斷兩個區域間是否存在邊界.首先我們定義一個區域的類內差異Int（C），表示為一個區域內部最大的差異值，它的取值是區域最小生成樹MST（C，E）的最大邊權值.直觀上我們可以用此值代表一個區域.

（1）

我們定義兩個區域中類間差異Diff（c1，c2），表示為兩個區域最相似的地方的差異值，它的取值為連接兩個區域所有的邊中權值最小的.如果兩個區域之間沒有邊相連，則Diff（c1，c2）=∞.

（2）

由以上兩個定義，我們可以判斷兩個區域間是否存在邊界.如果存在邊界，則兩個區域的類內差異Diff（c1，c2）至少比這兩個區域的類內差異要大.

（3）

（4）

2.3 自適應閾值

在公式（4）中引入自適應閾值函數τ（C），從而實現動態調節閾值，使得分割結果不會過分割或欠分割.

（5）

其中k是常量，控制所形成區域的大小，即表示分割的粒度，k值越大對應的分割區域越大.|C|表示區域內點的個數.

2.4 算法主要步驟

基于圖的3D點云分割算法

輸入：點云的圖G=（V，E），設點云中有n個頂點，m條邊.

輸出：分割區域的集合S=（c1，c2...，cr）.

1）計算每個點與其8領域點的邊權值，即非相似度，由此得到邊集E.

2）邊集E排序.將邊按非相似度從小到大排序.

3）初始化分割集S0.S0集合中的區域元素由每一個點組成.

4）從Sq-1構建Sq，對當前選中的第q條邊進行合并判斷.

1>假設第q條邊由νi，νj兩點連接，如果νi，vj在Sq-1中不屬于同一個區域，即Sq-1中兩個區域ciq-1和cjq-1，νi∈ciq-1，vj∈cjq-1，并且（ciq-1≠cjq-1）

2>這條邊的權重w（oq）區域間的非相似度不大于區域內的非相似度，即 ，則執行5），否則執行6）.

5）將中兩個區域和，并更新閾值

.

6） ，如果q，按邊集順序選擇下一條邊轉到4），否則執行7）.

7）得到分割結果，即分割集 .

2.5 算法實現技術

為了實現更好的分割效果以及加快分割效率，我們對輸入的點云進行預處理操作，我們將點云分割出前景點云和背景點云，其中背景點云為地面點云，通過PCL中提供的平面模型RANSAC檢查去除點云中的地面；前景點云為算法輸入的點云.

算法第一步，需要計算每點的8領域邊權值，為了快速查找領域采用最近鄰搜索，在K為半徑的空間中尋找最近點.這一步算法的復雜度從 降低到 ，其中N為邊集的邊數目.

算法第五步，需要查找兩點是否在同一區域，以及合并兩個區域的操作.本文中采用并查集的數據結構存儲區域.通過這個數據結構提供的兩種操作：

Find操作： 確定頂點屬于哪個區域，從而確定頂點是否屬于同一個區域.

Union操作：將兩個區域合并為一個區域.

第五步算法的復制度為

綜上所述算法時間復雜度為 ，可以做到快速點云分割

3 實驗結果與分析

本文實驗數據采用64線LiDAR，每秒鐘輸出10幀點云，每幀點云在10萬個點以上.實驗中對比1萬幀點云人工標注結果與本文算法分割結果.點云在60米范圍內準確率如表1所示.表中距離表示點云中點距離采集原點的距離.單幀的平均準確率為85.75%，滿足后續環境感知分類需求.在windows平臺，單幀運行時間為72ms，滿足無人車需求.本文算法綜合考慮了空間區域的邊緣和區域鄰接關系特征，分割結果比較有效的將不同區域物體分割開.自適應閾值的使用，保證了當兩個區域有較大的差異，但兩個區域相鄰的比較近時，也能夠分割開.

5 結論

通過對3D點云分割算法的實驗和實驗分析對比，我們認為本文提出的分割算法對于3D點云具有良好的分割效果，其中自動適應閾值有助于動態調節閾值更好的控區域合并的規則.實驗分割結果與人工分割結果具有良好的一致性，其分割結果可用于無人車環境感知的基于區域的障礙物檢測、基于區域的障礙物分類等.

在未來的工作中，可以將3D點云激光反射值的特征融入算法中，使得分割性能得到進一步的提高，也增加算法的魯棒性.

參考文獻

[1]X Guo. Research of automatic vehicle identification and loading system[J]： Industry &Mine Automation，2014.

[2]Dominic Zeng Wang， Ingmar Posner ， Paul Newman. What Could Move？ Finding Cars， Pedestrians and Bicyclists in 3D Laser Data： IEEE International Conference on Robotics & Automation， 2012，20（10）：4038-4044

[3]J Strom ， A Richardson ， E Olson：Graph-based segmentation for colored 3D laser point clouds.IEEE/RSJ International Conference on Intelligent Robots & Systems（IROS）， 2013 ， 25 （1） ：2131-2136

[4]朱德海，郭浩，蘇偉.點云庫PCL學習教程.北京航空航天大學出版社出版發行， 2012，10（1）.227-253