朱麗娟

摘 要：隨著無(wú)人車應(yīng)用領(lǐng)域的不斷擴(kuò)大以及激光雷達(dá)掃描技術(shù)的飛速發(fā)展，針對(duì)3D激光雷達(dá)點(diǎn)云數(shù)據(jù)處理技術(shù)研究對(duì)于人車領(lǐng)域的發(fā)展有重要意義.環(huán)境感知作為無(wú)人車系統(tǒng)的重要組成部分，對(duì)整車起著至關(guān)重要的作用.針對(duì)無(wú)人車基于激光雷達(dá)點(diǎn)云的環(huán)境感知中障礙物檢測(cè)問(wèn)題進(jìn)行研究，提出了一種基于3D激光雷達(dá)點(diǎn)云的檢測(cè)算法.該算法使用了基于圖的點(diǎn)云分割方法.該方法可以對(duì)激光雷達(dá)點(diǎn)云進(jìn)行快速分割，高效的將點(diǎn)云分割出障礙物點(diǎn).針對(duì)城市道路中的車輛、行人等障礙物的實(shí)驗(yàn)效果表明，該方法對(duì)這類障礙物有良好的分割效果.該算法具有高的實(shí)時(shí)性，能夠滿足無(wú)人車的需求.

關(guān)鍵詞：激光雷達(dá)；環(huán)境感知；障礙物檢測(cè)；點(diǎn)云分割；圖分割

1 引言

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

作為無(wú)人駕駛流程中最為底層也最重要的感知層對(duì)無(wú)人駕駛技術(shù)發(fā)展起著至關(guān)重要的作用.目前，無(wú)人車感知方法使用的傳感器大致可分為視覺(jué)傳感器、激光傳感器、微波傳感器等.其中激光雷達(dá)能夠獲取車身周圍百米內(nèi)的三維環(huán)境，通過(guò)對(duì)激光點(diǎn)云的處理能夠準(zhǔn)確的進(jìn)行場(chǎng)景分割.激光雷達(dá)的優(yōu)點(diǎn)在于精度高，能夠直接獲取物體的三維空間信息.對(duì)光照環(huán)境的變換不敏感，能夠全天候使用.障礙物檢測(cè)是激光雷達(dá)最基本的環(huán)境感知能力.激光雷達(dá)能夠準(zhǔn)確定位障礙物位置并能從三維場(chǎng)景中提取出障礙物信息.

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

1999年 Jain指出著名的圖論分割聚類算法的主要思想是：構(gòu)造一棵關(guān)于數(shù)據(jù)的最小生成樹（minimal spanning tree，簡(jiǎn)稱MST），通過(guò)刪除最小生成樹的最長(zhǎng)邊來(lái)形成類.基于圖的圖像分割算法是圖像中經(jīng)典的分割算法，本文參考這一算法的思想將其應(yīng)用到3D點(diǎn)云分割中，實(shí)現(xiàn)對(duì)3D點(diǎn)云數(shù)據(jù)的快速有效自動(dòng)分割.

本文第2節(jié)給出算法的詳細(xì)描述.第3節(jié)結(jié)合具體例子將本文算法與人工分割結(jié)果進(jìn)行實(shí)驗(yàn)比較和分析.第4節(jié)給出結(jié)論.

2 圖分割算法

2.1 圖的定義

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

2.2 區(qū)域的定義

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

（1）

我們定義兩個(gè)區(qū)域中類間差異Diff（c1，c2），表示為兩個(gè)區(qū)域最相似的地方的差異值，它的取值為連接兩個(gè)區(qū)域所有的邊中權(quán)值最小的.如果兩個(gè)區(qū)域之間沒(méi)有邊相連，則Diff（c1，c2）=∞.

（2）

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

（3）

（4）

2.3 自適應(yīng)閾值

在公式（4）中引入自適應(yīng)閾值函數(shù)τ（C），從而實(shí)現(xiàn)動(dòng)態(tài)調(diào)節(jié)閾值，使得分割結(jié)果不會(huì)過(guò)分割或欠分割.

（5）

其中k是常量，控制所形成區(qū)域的大小，即表示分割的粒度，k值越大對(duì)應(yīng)的分割區(qū)域越大.|C|表示區(qū)域內(nèi)點(diǎn)的個(gè)數(shù).

2.4 算法主要步驟

基于圖的3D點(diǎn)云分割算法

輸入：點(diǎn)云的圖G=（V，E），設(shè)點(diǎn)云中有n個(gè)頂點(diǎn)，m條邊.

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

1）計(jì)算每個(gè)點(diǎn)與其8領(lǐng)域點(diǎn)的邊權(quán)值，即非相似度，由此得到邊集E.

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

3）初始化分割集S0.S0集合中的區(qū)域元素由每一個(gè)點(diǎn)組成.

4）從Sq-1構(gòu)建Sq，對(duì)當(dāng)前選中的第q條邊進(jìn)行合并判斷.

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

2>這條邊的權(quán)重w（oq）區(qū)域間的非相似度不大于區(qū)域內(nèi)的非相似度，即 ，則執(zhí)行5），否則執(zhí)行6）.

5）將中兩個(gè)區(qū)域和，并更新閾值

.

6） ，如果q，按邊集順序選擇下一條邊轉(zhuǎn)到4），否則執(zhí)行7）.

7）得到分割結(jié)果，即分割集 .

2.5 算法實(shí)現(xiàn)技術(shù)

為了實(shí)現(xiàn)更好的分割效果以及加快分割效率，我們對(duì)輸入的點(diǎn)云進(jìn)行預(yù)處理操作，我們將點(diǎn)云分割出前景點(diǎn)云和背景點(diǎn)云，其中背景點(diǎn)云為地面點(diǎn)云，通過(guò)PCL中提供的平面模型RANSAC檢查去除點(diǎn)云中的地面；前景點(diǎn)云為算法輸入的點(diǎn)云.

算法第一步，需要計(jì)算每點(diǎn)的8領(lǐng)域邊權(quán)值，為了快速查找領(lǐng)域采用最近鄰搜索，在K為半徑的空間中尋找最近點(diǎn).這一步算法的復(fù)雜度從 降低到 ，其中N為邊集的邊數(shù)目.

算法第五步，需要查找兩點(diǎn)是否在同一區(qū)域，以及合并兩個(gè)區(qū)域的操作.本文中采用并查集的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)區(qū)域.通過(guò)這個(gè)數(shù)據(jù)結(jié)構(gòu)提供的兩種操作：

Find操作： 確定頂點(diǎn)屬于哪個(gè)區(qū)域，從而確定頂點(diǎn)是否屬于同一個(gè)區(qū)域.

Union操作：將兩個(gè)區(qū)域合并為一個(gè)區(qū)域.

第五步算法的復(fù)制度為

綜上所述算法時(shí)間復(fù)雜度為 ，可以做到快速點(diǎn)云分割

3 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)數(shù)據(jù)采用64線LiDAR，每秒鐘輸出10幀點(diǎn)云，每幀點(diǎn)云在10萬(wàn)個(gè)點(diǎn)以上.實(shí)驗(yàn)中對(duì)比1萬(wàn)幀點(diǎn)云人工標(biāo)注結(jié)果與本文算法分割結(jié)果.點(diǎn)云在60米范圍內(nèi)準(zhǔn)確率如表1所示.表中距離表示點(diǎn)云中點(diǎn)距離采集原點(diǎn)的距離.單幀的平均準(zhǔn)確率為85.75%，滿足后續(xù)環(huán)境感知分類需求.在windows平臺(tái)，單幀運(yùn)行時(shí)間為72ms，滿足無(wú)人車需求.本文算法綜合考慮了空間區(qū)域的邊緣和區(qū)域鄰接關(guān)系特征，分割結(jié)果比較有效的將不同區(qū)域物體分割開.自適應(yīng)閾值的使用，保證了當(dāng)兩個(gè)區(qū)域有較大的差異，但兩個(gè)區(qū)域相鄰的比較近時(shí)，也能夠分割開.

5 結(jié)論

通過(guò)對(duì)3D點(diǎn)云分割算法的實(shí)驗(yàn)和實(shí)驗(yàn)分析對(duì)比，我們認(rèn)為本文提出的分割算法對(duì)于3D點(diǎn)云具有良好的分割效果，其中自動(dòng)適應(yīng)閾值有助于動(dòng)態(tài)調(diào)節(jié)閾值更好的控區(qū)域合并的規(guī)則.實(shí)驗(yàn)分割結(jié)果與人工分割結(jié)果具有良好的一致性，其分割結(jié)果可用于無(wú)人車環(huán)境感知的基于區(qū)域的障礙物檢測(cè)、基于區(qū)域的障礙物分類等.

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

參考文獻(xiàn)

[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]朱德海，郭浩，蘇偉.點(diǎn)云庫(kù)PCL學(xué)習(xí)教程.北京航空航天大學(xué)出版社出版發(fā)行， 2012，10（1）.227-253