基于KDTree樹(shù)和歐式聚類的越野環(huán)境下行人識(shí)別的研究*

范晶晶，王 力，褚文博，羅禹貢

（1.北方工業(yè)大學(xué)，城市道路交通智能控制技術(shù)北京重點(diǎn)實(shí)驗(yàn)室，北京 100144；2.國(guó)汽（北京）智能網(wǎng)聯(lián)汽車研究院有限公司，北京 100176； 3.清華大學(xué)，汽車安全與節(jié)能國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100084）

前言

行人識(shí)別作為環(huán)境感知技術(shù)的重要組成部分，可為自動(dòng)駕駛車輛的決策和路徑規(guī)劃提供準(zhǔn)確的邊界約束條件輸入。越野環(huán)境下的行人識(shí)別，是實(shí)現(xiàn)班組伴隨自動(dòng)駕駛車輛的基本前提，這也給行人識(shí)別算法的設(shè)計(jì)和實(shí)施提出了更高的要求。

程?。?］和Kidono等［2］基于行人簡(jiǎn)單幾何特征，采用SVM分類器對(duì)行人進(jìn)行識(shí)別，但SVM分類器的輸出并不穩(wěn)定。胡順璽［3］通過(guò)提取點(diǎn)云中行人的幾何和形狀特征，設(shè)計(jì)線性分類器，實(shí)現(xiàn)行人識(shí)別，但識(shí)別效果魯棒性不高。Nagashima等［4］針對(duì)激光雷達(dá)的每一條掃描光束分別獨(dú)立計(jì)算行人識(shí)別結(jié)果，然后再進(jìn)行集成，得到最終的行人識(shí)別效果，但當(dāng)其中某一條掃描光束的識(shí)別效果出錯(cuò)時(shí)，整個(gè)結(jié)果均會(huì)受到影響。Sato等［5］結(jié)合GPS數(shù)據(jù)將激光雷達(dá)點(diǎn)云映射到網(wǎng)格地圖上，通過(guò)占用網(wǎng)格法、卡爾曼濾波和全局最近鄰的方法進(jìn)行行人識(shí)別，具有較好的效果，但由于增加了GPS設(shè)備，成本有所提高。Yamamoto等［6］基于激光雷達(dá)的點(diǎn)云數(shù)據(jù)提出了一種針對(duì)行人的似然估計(jì)方法，該方法雖有效，但計(jì)算繁瑣，僅適合離線計(jì)算。Li等［7］針對(duì)稀疏行人點(diǎn)云的工況，提出了一種新的密度增強(qiáng)方法，用于提高行人識(shí)別效果，但該方法對(duì)密度正常的行人點(diǎn)云效果并不明顯。Mokni等［8］結(jié)合慣性傳感器和測(cè)距激光雷達(dá)，對(duì)室內(nèi)行人的運(yùn)動(dòng)跟蹤進(jìn)行了研究，該方法增加了慣性傳感器，對(duì)成本影響較大。Tang等［9］利用距離感知擴(kuò)展方法將三維點(diǎn)云映射到二維平面上，提取二維輪廓和特征，達(dá)到行人識(shí)別目的，但三維點(diǎn)云映射到二維平面涉及復(fù)雜的坐標(biāo)系映射，增加了標(biāo)定的工作量。Ogawa等［10］和Premebida等［11］在擁擠的城市交通環(huán)境中基于Lidar的特征提取用于行人檢測(cè)的信息，設(shè)計(jì)了高魯棒性和強(qiáng)跟蹤能力的行人識(shí)別算法，但并未針對(duì)復(fù)雜的越野環(huán)境進(jìn)行適應(yīng)性設(shè)計(jì)和研究。Oliveira等［12］針對(duì)常規(guī)滑動(dòng)窗口方法的固有缺陷，在非獨(dú)立同分布概率框架內(nèi)，提出了一種基于關(guān)聯(lián)部件的行人檢測(cè)方法，取得了優(yōu)異性能，但實(shí)時(shí)性較差。Szarvas等［13］基于CNN神經(jīng)網(wǎng)絡(luò)研究了激光雷達(dá)對(duì)于行人的識(shí)別，但在實(shí)時(shí)運(yùn)行速率上存在明顯短板。Benedek［14］則利用旋轉(zhuǎn)激光雷達(dá)對(duì)三維人體數(shù)據(jù)進(jìn)行檢測(cè)和建模，但在聚類算法加速方面并沒(méi)有研究。

本文中針對(duì)班組伴隨自動(dòng)駕駛系統(tǒng)對(duì)于越野復(fù)雜環(huán)境下行人識(shí)別的需求，將激光雷達(dá)作為環(huán)境感知傳感器，在聚類思想的基礎(chǔ)上，設(shè)計(jì)了基于KDTree和歐式聚類方法的行人識(shí)別算法，并結(jié)合人的幾何物理特征加以約束，提高行人識(shí)別算法的準(zhǔn)確度。在理論分析與計(jì)算的基礎(chǔ)上，通過(guò)小型履帶式車輛平臺(tái)，在越野環(huán)境下進(jìn)行實(shí)車測(cè)試。結(jié)果表明，所設(shè)計(jì)的激光雷達(dá)行人識(shí)別算法能準(zhǔn)確識(shí)別激光雷達(dá)點(diǎn)云數(shù)據(jù)中的行人，在越野環(huán)境下有良好的識(shí)別率。本文有兩點(diǎn)創(chuàng)新：一是搭建了小型履帶式車輛驗(yàn)證平臺(tái)進(jìn)行越野復(fù)雜環(huán)境下的行人識(shí)別驗(yàn)證；二是設(shè)計(jì)了一種基于加速搜索方法的點(diǎn)云聚類算法，提升了行人識(shí)別的效率和準(zhǔn)確度。

1 系統(tǒng)構(gòu)成

基于KDTree和歐式聚類的越野環(huán)境行人識(shí)別系統(tǒng)構(gòu)成如圖1所示。

圖1 行人識(shí)別系統(tǒng)構(gòu)成

圖1 中通過(guò)Ubuntu 16.04下的Ros系統(tǒng)和網(wǎng)口連接，采集得到rosbag格式的激光雷達(dá)點(diǎn)云數(shù)據(jù)，通過(guò)技術(shù)手段將rosbag格式轉(zhuǎn)換成PCL（point cloud learning）庫(kù)可以識(shí)別的PCD格式，作為整個(gè)行人識(shí)別系統(tǒng)的原始輸入。點(diǎn)云數(shù)據(jù)首先通過(guò)VoxelGrid體素濾波器進(jìn)行下采樣，此操作可在保持點(diǎn)云主要形狀特征的基礎(chǔ)上減少點(diǎn)的數(shù)量和點(diǎn)云數(shù)據(jù)量，可提高配準(zhǔn)、曲面重建和形狀識(shí)別的計(jì)算速度。隨后創(chuàng)建KDTree對(duì)象，該對(duì)象是由二分搜索樹(shù)（binary search tree，BST）演變而來(lái)的一種高維度索引樹(shù)形結(jié)構(gòu)，一般用在大規(guī)模的高維數(shù)據(jù)查找的場(chǎng)景中。在此基礎(chǔ)上應(yīng)用歐幾里得算法對(duì)激光雷達(dá)點(diǎn)云進(jìn)行歐式分割，得到若干個(gè)點(diǎn)云簇。針對(duì)若干個(gè)點(diǎn)云簇再使用行人幾何物理特征進(jìn)行約束，便可得到最終的行人聚類識(shí)別效果。

2 方法設(shè)計(jì)

2.1 VoxelGrid體素濾波器下采樣

通過(guò)激光雷達(dá)采集的原始點(diǎn)云數(shù)據(jù)量較大，且與激光雷達(dá)的線數(shù)直接相關(guān)，線數(shù)越大，激光雷達(dá)數(shù)據(jù)輸出量就越大。為避免大的數(shù)據(jù)量對(duì)后面的處理算法造成較大的計(jì)算壓力，須尋找一種合適的濾波器算法來(lái)對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行下采樣，從而在保證點(diǎn)云主要特征的前提下，盡可能減少點(diǎn)云的數(shù)據(jù)量。

VoxelGrid體素濾波器主要思路如下：根據(jù)點(diǎn)云數(shù)據(jù)的特點(diǎn)建立最小三維體素柵格，選取小立方柵格的邊長(zhǎng)，根據(jù)邊長(zhǎng)將三維體素柵格劃分成m×n×l個(gè)小柵格，并將點(diǎn)云數(shù)據(jù)填充至對(duì)應(yīng)的小柵格中，每個(gè)小柵格中，用該小柵格的質(zhì)心來(lái)近似顯示體素中的其他點(diǎn)。這種方法簡(jiǎn)潔高效，無(wú)須建立較為復(fù)雜的拓?fù)浣Y(jié)構(gòu)即可達(dá)到簡(jiǎn)化點(diǎn)云數(shù)量的目的，同時(shí)滿足三維點(diǎn)云曲面快速重構(gòu)的需求。每個(gè)小柵格中，質(zhì)心的計(jì)算公式為

式中h為小三維柵格中點(diǎn)云的數(shù)目。用小三維柵格的質(zhì)心來(lái)近似顯示體素中的其他點(diǎn)，實(shí)現(xiàn)點(diǎn)云的下采樣過(guò)程。

VoxelGrid濾波器下采樣效果如圖2所示。圖2中，VoxelGrid濾波器中三維柵格為邊長(zhǎng)等于30 cm的正方體，濾波前后點(diǎn)云的輪廓形狀基本保持不變，濾波之前點(diǎn)的數(shù)量為24 722，濾波之后點(diǎn)的數(shù)量為7 577，點(diǎn)的數(shù)量大大減少，節(jié)省了大量的計(jì)算資源。使用VoxelGrid濾波器過(guò)程中，可根據(jù)實(shí)際情況來(lái)調(diào)節(jié)VoxelGrid濾波器中三維柵格的邊長(zhǎng)大小，在減少點(diǎn)云數(shù)量和保持點(diǎn)云輪廓形狀之間達(dá)到平衡。

圖2 VoxelGrid濾波器下采樣效果

2.2 KDTree對(duì)象創(chuàng)建

KDTree是由二分搜索樹(shù)演變而來(lái)的用于大規(guī)模高維度數(shù)據(jù)查找場(chǎng)景當(dāng)中的索引樹(shù)形結(jié)構(gòu)，主要用于最近鄰查找和近似最近鄰查找的場(chǎng)景。在圖像識(shí)別領(lǐng)域的主要功能是比對(duì)和查找高維特征向量。

二分搜索樹(shù)是一種二分樹(shù)，具有以下特點(diǎn)：

式中：Tl_sub為左子樹(shù)；Tl_root為左子樹(shù)Tl_sub的根節(jié)點(diǎn)；Tr_sub為右子樹(shù)；Tr_root為右子樹(shù)Tr_sub的根節(jié)點(diǎn)。

對(duì)于激光雷達(dá)產(chǎn)生的三維點(diǎn)云數(shù)據(jù)，普通的二分樹(shù)已無(wú)法滿足存儲(chǔ)需求，此時(shí)須利用KDTree的數(shù)據(jù)結(jié)構(gòu)。KDTree本質(zhì)上仍然是一種二分搜索樹(shù)，每一次對(duì)點(diǎn)云數(shù)據(jù)空間的劃分均建立在某一維度的基礎(chǔ)上，劃分完成后的左右子空間數(shù)據(jù)量應(yīng)盡可能保證數(shù)目相等，其構(gòu)建流程如下。

①按式（3）計(jì)算K維數(shù)據(jù)集合中每一維度的方差，并從中選取具有最大方差的維度k。

②將維度k上的數(shù)據(jù)從小到大進(jìn)行排列，得到數(shù)據(jù)集合｛K1，K2，K3，…，KNk｝，其中K1＜K2＜K3＜…＜KNk，Nk為維度k上數(shù)據(jù)的個(gè)數(shù)。按式（4）計(jì)算維度k上的中值m：

③將閾值設(shè)置為步驟②中得到的中值m，得到兩個(gè)集合Ksub_low和Ksub_high，并創(chuàng)建一個(gè)用于存儲(chǔ)的樹(shù)節(jié)點(diǎn)。集合滿足式（5）的要求。

④對(duì)步驟③得到的兩個(gè)子集合重復(fù)進(jìn)行上述操作，直到所有的子集合都不能再進(jìn)行劃分為止；若某子集合不能再進(jìn)行劃分時(shí)，將該子集合中的數(shù)據(jù)保存到?jīng)]有子節(jié)點(diǎn)的葉子節(jié)點(diǎn)中。

在建立KDTree數(shù)據(jù)結(jié)構(gòu)后，一般情況下只須在其子節(jié)點(diǎn)和父節(jié)點(diǎn)中查找鄰近點(diǎn)，即可大大減少搜索鄰近點(diǎn)所帶來(lái)的額外計(jì)算量，提高搜索效率。KDTree數(shù)據(jù)結(jié)構(gòu)如圖3所示。

圖3 KDTree數(shù)據(jù)結(jié)構(gòu)

2.3 歐式聚類

歐式聚類算法是一種基于歐式距離度量的聚類算法。三維空間中，點(diǎn)（x1，y1，z1）與點(diǎn)（x2，y2，z2）之間的歐式距離定義為

基于KDTree的最近鄰查詢算法是加速歐式聚類過(guò)程的前提，其流程如圖4所示。

圖4 KDTree最近鄰點(diǎn)查詢

圖4 中對(duì)于給定的查詢數(shù)據(jù)點(diǎn)P，須從KDTree的根節(jié)點(diǎn)開(kāi)始進(jìn)行比較，其中P（k）為當(dāng)前節(jié)點(diǎn)劃分維度k上數(shù)據(jù)點(diǎn)P對(duì)應(yīng)的值，m為當(dāng)前節(jié)點(diǎn)劃分的閾值。若P（k）＜m，則訪問(wèn)左子樹(shù)；否則訪問(wèn)右子樹(shù)，直至到達(dá)葉子節(jié)點(diǎn)Q。此時(shí)Q就是當(dāng)前最近鄰點(diǎn)，而P與Q之間的距離就是當(dāng)前最小距離Dc，min。隨后沿著原搜索路徑往上回退至根節(jié)點(diǎn)，若此過(guò)程中發(fā)現(xiàn)和P之間距離小于Dc，min的點(diǎn)，則須將未曾訪問(wèn)過(guò)的子節(jié)點(diǎn)均納入搜索范疇，并及時(shí)更新最近鄰點(diǎn)，直至所有的搜索路徑都為空，整個(gè)基于KDTree結(jié)構(gòu)的最近鄰點(diǎn)查詢過(guò)程便告完成。

歐式聚類的流程如圖5所示。

圖5 歐式聚類流程

圖5 中對(duì)于歐式聚類來(lái)說(shuō)，距離判斷準(zhǔn)則為前文提到的歐式距離。對(duì)于空間某點(diǎn)P，通過(guò)KDTree近鄰搜索算法找到k個(gè)離P點(diǎn)最近的點(diǎn)，這些點(diǎn)中距離小于設(shè)定閾值的便聚類到集合Q中。如果Q中元素的數(shù)目不再增加，整個(gè)聚類過(guò)程便結(jié)束；否則須在集合Q中選取除P點(diǎn)以外的點(diǎn)，重復(fù)上述過(guò)程，直到Q中元素的數(shù)目不再增加為止。

2.4 行人幾何約束

激光雷達(dá)原始點(diǎn)云數(shù)據(jù)經(jīng)過(guò)VoxelGrid體素濾波器、KDTree對(duì)象創(chuàng)建和歐式聚類后，會(huì)得到一系列離散的點(diǎn)云集合。這些點(diǎn)云集合可能包含不同類別的物體，如轎車、貨車、摩托車和行人等等，須結(jié)合行人的幾何物理特征對(duì)感興趣的行人目標(biāo)進(jìn)行篩選。

針對(duì)任意一個(gè)篩選出來(lái)的點(diǎn)云集合，首先須找到x，y，z 3個(gè)維度上的最大值和最小值，假設(shè)它們分別為xmin，xmax，ymin，ymax，zmin和zmax，則三維點(diǎn)云集合的邊界尺寸為

一般來(lái)講，行人的厚度相對(duì)于行人的寬度和高度基本可以忽略不計(jì)。假定z方向?yàn)樾腥烁叨确较?，則行人應(yīng)滿足：

式中：hhigh，hlow分別為高度的上下限值；rhigh，rlow分別為高寬比的上下限值。行人的高度和高寬比均應(yīng)在合理的閾值范圍內(nèi)，通過(guò)該法則可提高行人提取的準(zhǔn)確率。

3 試驗(yàn)驗(yàn)證

為驗(yàn)證所設(shè)計(jì)的算法對(duì)于越野環(huán)境下行人識(shí)別的效果，首先搭建了履帶式車輛驗(yàn)證平臺(tái)，如圖6所示。圖6中履帶式車輛驗(yàn)證平臺(tái)搭載的激光雷達(dá)為16線雷達(dá)Velodyne VLP-16，它可提供360°的橫向視角和30°的縱向視角，在水平／方位角方向可提供0.1°的角分辨率和5 Hz的旋轉(zhuǎn)頻率或0.4°的角分辨率和20 Hz的旋轉(zhuǎn)頻率，每秒可獲取288 000個(gè)數(shù)據(jù)點(diǎn)，完全滿足本文對(duì)于行人點(diǎn)云數(shù)據(jù)采集的要求。

圖6 履帶式車輛驗(yàn)證平臺(tái)

通過(guò)履帶式車輛驗(yàn)證平臺(tái)搭載的激光雷達(dá)采集越野環(huán)境下的原始點(diǎn)云數(shù)據(jù)，并運(yùn)用前文所述的算法進(jìn)行聚類運(yùn)算，分別針對(duì)單人和多人的場(chǎng)景進(jìn)行驗(yàn)證，統(tǒng)計(jì)結(jié)果顯示行人識(shí)別準(zhǔn)確率可達(dá)95%以上，數(shù)據(jù)處理速度在24 fps以上，滿足實(shí)時(shí)運(yùn)行的需要。

單人識(shí)別效果如圖7所示。由圖7可見(jiàn)，上半部分原始點(diǎn)云數(shù)據(jù)中成分較復(fù)雜，包含各種各樣的目標(biāo)物體數(shù)據(jù)，而下半部分的行人點(diǎn)云聚類提取效果圖中僅包含當(dāng)前環(huán)境下存在的行人目標(biāo)，此過(guò)程中VoxelGrid體素濾波器減少了約70%數(shù)目的點(diǎn)。提取到的行人點(diǎn)云簇的高度為1.80 m，高寬比在4.5左右，完全符合行人的幾何特征。結(jié)果表明本文所設(shè)計(jì)的行人識(shí)別算法具有較好的識(shí)別效果，達(dá)到了預(yù)期的設(shè)計(jì)目標(biāo)。

圖7 單人工況識(shí)別效果

多人工況識(shí)別效果如圖8所示。由圖可見(jiàn)，上半部分點(diǎn)云數(shù)據(jù)較為復(fù)雜，除3個(gè)行人目標(biāo)外還包含大量干擾目標(biāo)，而下半部分僅包含提取出來(lái)的3個(gè)行人目標(biāo)點(diǎn)云聚類結(jié)果，此過(guò)程中Voxel Grid體素濾波器減少了約70%數(shù)目的點(diǎn)。3個(gè)行人目標(biāo)點(diǎn)云簇的高度均在1.70～1.80 m之間，高寬比均在4.5左右，完全符合行人的幾何特征。結(jié)果表明，所設(shè)計(jì)的算法在多人工況下仍有較好的效果。

圖8 多人工況識(shí)別效果

4 結(jié)論

針對(duì)班組伴隨自動(dòng)駕駛系統(tǒng)對(duì)于越野環(huán)境下行人識(shí)別的需求，將激光雷達(dá)作為環(huán)境感知元件，設(shè)計(jì)了一種結(jié)合KDTree數(shù)據(jù)結(jié)構(gòu)、歐式聚類和人體幾何約束的行人識(shí)別算法，并在越野環(huán)境下通過(guò)履帶式車輛平臺(tái)進(jìn)行試驗(yàn)驗(yàn)證，結(jié)果表明所設(shè)計(jì)的算法是有效的，并得到以下結(jié)論。

（1）所設(shè)計(jì)的行人識(shí)別算法能準(zhǔn)確識(shí)別激光雷達(dá)原始點(diǎn)云數(shù)據(jù)中的行人，且在越野環(huán)境下具備良好的識(shí)別率。

（2）VoxelGrid體素濾波器可在保持點(diǎn)云輪廓基本不變的情況下大幅減少點(diǎn)云的數(shù)量，顯著縮減計(jì)算量。

（3）KDTree數(shù)據(jù)結(jié)構(gòu)可大幅減少近鄰搜索的計(jì)算量，對(duì)于歐式聚類有明顯的加速效果。

試驗(yàn)中發(fā)現(xiàn)，單純激光雷達(dá)的可視化效果相對(duì)較差，今后擬引入攝像頭，對(duì)照?qǐng)D像數(shù)據(jù)和激光雷達(dá)數(shù)據(jù)，以提升整體的可視化效果。