基于KDTree樹和歐式聚類的越野環境下行人識別的研究*

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

（1.北方工業大學，城市道路交通智能控制技術北京重點實驗室，北京 100144；2.國汽（北京）智能網聯汽車研究院有限公司，北京 100176； 3.清華大學，汽車安全與節能國家重點實驗室，北京 100084）

前言

行人識別作為環境感知技術的重要組成部分，可為自動駕駛車輛的決策和路徑規劃提供準確的邊界約束條件輸入。越野環境下的行人識別，是實現班組伴隨自動駕駛車輛的基本前提，這也給行人識別算法的設計和實施提出了更高的要求。

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

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

1 系統構成

基于KDTree和歐式聚類的越野環境行人識別系統構成如圖1所示。

圖1 行人識別系統構成

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

2 方法設計

2.1 VoxelGrid體素濾波器下采樣

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

VoxelGrid體素濾波器主要思路如下：根據點云數據的特點建立最小三維體素柵格，選取小立方柵格的邊長，根據邊長將三維體素柵格劃分成m×n×l個小柵格，并將點云數據填充至對應的小柵格中，每個小柵格中，用該小柵格的質心來近似顯示體素中的其他點。這種方法簡潔高效，無須建立較為復雜的拓撲結構即可達到簡化點云數量的目的，同時滿足三維點云曲面快速重構的需求。每個小柵格中，質心的計算公式為

式中h為小三維柵格中點云的數目。用小三維柵格的質心來近似顯示體素中的其他點，實現點云的下采樣過程。

VoxelGrid濾波器下采樣效果如圖2所示。圖2中，VoxelGrid濾波器中三維柵格為邊長等于30 cm的正方體，濾波前后點云的輪廓形狀基本保持不變，濾波之前點的數量為24 722，濾波之后點的數量為7 577，點的數量大大減少，節省了大量的計算資源。使用VoxelGrid濾波器過程中，可根據實際情況來調節VoxelGrid濾波器中三維柵格的邊長大小，在減少點云數量和保持點云輪廓形狀之間達到平衡。

圖2 VoxelGrid濾波器下采樣效果

2.2 KDTree對象創建

KDTree是由二分搜索樹演變而來的用于大規模高維度數據查找場景當中的索引樹形結構，主要用于最近鄰查找和近似最近鄰查找的場景。在圖像識別領域的主要功能是比對和查找高維特征向量。

二分搜索樹是一種二分樹，具有以下特點：

式中：Tl_sub為左子樹；Tl_root為左子樹Tl_sub的根節點；Tr_sub為右子樹；Tr_root為右子樹Tr_sub的根節點。

對于激光雷達產生的三維點云數據，普通的二分樹已無法滿足存儲需求，此時須利用KDTree的數據結構。KDTree本質上仍然是一種二分搜索樹，每一次對點云數據空間的劃分均建立在某一維度的基礎上，劃分完成后的左右子空間數據量應盡可能保證數目相等，其構建流程如下。

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

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

③將閾值設置為步驟②中得到的中值m，得到兩個集合Ksub_low和Ksub_high，并創建一個用于存儲的樹節點。集合滿足式（5）的要求。

④對步驟③得到的兩個子集合重復進行上述操作，直到所有的子集合都不能再進行劃分為止；若某子集合不能再進行劃分時，將該子集合中的數據保存到沒有子節點的葉子節點中。

在建立KDTree數據結構后，一般情況下只須在其子節點和父節點中查找鄰近點，即可大大減少搜索鄰近點所帶來的額外計算量，提高搜索效率。KDTree數據結構如圖3所示。

圖3 KDTree數據結構

2.3 歐式聚類

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

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

圖4 KDTree最近鄰點查詢

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

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

圖5 歐式聚類流程

圖5 中對于歐式聚類來說，距離判斷準則為前文提到的歐式距離。對于空間某點P，通過KDTree近鄰搜索算法找到k個離P點最近的點，這些點中距離小于設定閾值的便聚類到集合Q中。如果Q中元素的數目不再增加，整個聚類過程便結束；否則須在集合Q中選取除P點以外的點，重復上述過程，直到Q中元素的數目不再增加為止。

2.4 行人幾何約束

激光雷達原始點云數據經過VoxelGrid體素濾波器、KDTree對象創建和歐式聚類后，會得到一系列離散的點云集合。這些點云集合可能包含不同類別的物體，如轎車、貨車、摩托車和行人等等，須結合行人的幾何物理特征對感興趣的行人目標進行篩選。

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

一般來講，行人的厚度相對于行人的寬度和高度基本可以忽略不計。假定z方向為行人高度方向，則行人應滿足：

式中：hhigh，hlow分別為高度的上下限值；rhigh，rlow分別為高寬比的上下限值。行人的高度和高寬比均應在合理的閾值范圍內，通過該法則可提高行人提取的準確率。

3 試驗驗證

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

圖6 履帶式車輛驗證平臺

通過履帶式車輛驗證平臺搭載的激光雷達采集越野環境下的原始點云數據，并運用前文所述的算法進行聚類運算，分別針對單人和多人的場景進行驗證，統計結果顯示行人識別準確率可達95%以上，數據處理速度在24 fps以上，滿足實時運行的需要。

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

圖7 單人工況識別效果

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

圖8 多人工況識別效果

4 結論

針對班組伴隨自動駕駛系統對于越野環境下行人識別的需求，將激光雷達作為環境感知元件，設計了一種結合KDTree數據結構、歐式聚類和人體幾何約束的行人識別算法，并在越野環境下通過履帶式車輛平臺進行試驗驗證，結果表明所設計的算法是有效的，并得到以下結論。

（1）所設計的行人識別算法能準確識別激光雷達原始點云數據中的行人，且在越野環境下具備良好的識別率。

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

（3）KDTree數據結構可大幅減少近鄰搜索的計算量，對于歐式聚類有明顯的加速效果。

試驗中發現，單純激光雷達的可視化效果相對較差，今后擬引入攝像頭，對照圖像數據和激光雷達數據，以提升整體的可視化效果。