點云庫在兼容系統中的編譯及鄰域搜索

董路通 朱留存 張恒艷

（揚州大學信息工程學院 江蘇省揚州市 225127）

三維激光掃描技術源自于上世紀九十年代，它采用高速激光掃描測量方式，大面積高分辨率地快速獲取被測對象表面的三維坐標數據（點云數據），可以快速、大量的采集空間點位信息，較傳統單點測量方法，它速度更快精度更高抗干擾性更強。隨著社會的發展，利用三維激光掃描儀快速高效獲取目標物體的點云數據集越來越龐大，但所采集的數據集中通常無明顯的幾何拓撲信息。由于數據集的龐大，所以提前建立點云拓撲關系，高效的有組織的管理點云，是對海量點云數據處理的前提。

在處理眾多點云數據時，我們需要對某一點進行鄰域查找，我們首先應該對原始的散亂的點云建立一定的拓撲關系，準確的建立鄰域拓撲關系后不僅在目標點的搜索查找范圍會縮小，而且更為后期的有效壓縮配準提供了保障。基于K-D 樹的近鄰搜索是二進制空間分割樹的特殊的情況，且具有有很高的搜索效率，K-D 樹可以使用在多種應用場合，如多維鍵值搜索、K 近鄰搜索，該數據結構建樹速度快，可以很快地知道目標物體在3D 場景中的位置，或偵測目標節點是否在可視范圍內。本文結合PCL 開源庫，針對海量點云數據建立K-D 樹數據結構，實現點云的快速鄰域搜索。

1 PCL

PCL 是在吸收前輩點云相關研究的基礎上建立起來的大范圍、獨立的、跨平臺的開源C++編程庫，主要用于二維或三維的圖像和點云處理，可以在Windows、Linux、Android 和部分嵌入式實時系統上運行。PCL 起初主要應用于機器人研究，后來與全球3D 信息獲取、處理的研究者們一起，組建了強大的開發維護團隊，發展異常迅速。如同OpenCV 在2D 信息處理的地位一樣，PCL 主要運用在3D 信息的獲取與處理[1]。

為了簡化開發，PCL 被分成一系列較小的代碼庫，這些代碼庫可以單獨編譯。這種模塊化對于在計算或者大小限制較少的平臺上發布PCL 非常重要。如圖1所示。

圖1：PCL 功能模塊

2 Windows系統

在PCL 官網中列出的在Windows 下安裝PCL 教程分為兩步：安裝PCL 依賴庫和編譯PCL 文件，介于操作的復雜性，也同時便于初學者安裝，暫不采用此方法安裝。本文介紹的編譯環境是Visual Studio 2019，操作系統為64 位 Windows 10。

2.1 PCL安裝包的下載

在Github 中下載PCL 最新版本的PCL-1.12.0-AllInOnemsvc2019-win64.exe 和pcl-1.12.0-rc1-pdb-msvc2019-win64.zip， 下載完成后安裝.exe 文件。pdb 文件是程序的數據庫文件，是VS 編譯的生成文件，要想正常運行PCL 文件必須要有pdb 文件。將pdb文件解壓后的文件移動到PCL 安裝目錄中的bin 文件中，如圖2所示。

圖2：配置PCL 文件

2.2 配置環境變量

右鍵此電腦，找到高級系統設置中的環境變量。如圖3所示。

圖3：環境變量

首先配置在環境變量中系統變量的Path 變量，將以下路徑添加到Path 變量中后確定。如圖4所示。

圖4：Path 變量

2.3 包含目錄配置和庫目錄

在VS2019 中新建空項目，在其配置屬性界面中找到包含目錄，將第三方包含目錄和庫目錄分別添加到相應目錄中。包含目錄的意思就是在編譯的過程中引用的頭文件一定要被工程所包含，否則的話是無法確定頭文件的位置，所以我們需要在目標地址中包含我們安裝好的庫的頭文件。庫目錄就是動態鏈接庫所存在路徑，如圖5、圖6所示。

圖5：包含目錄

圖6：庫目錄

2.4 輸入附加依賴項

在“配置屬性-鏈接器-輸入”中編輯路徑，將本文安裝的幾個第三方依賴庫靜態鏈接庫名稱全部添加進去，此庫目錄可以在相應的安裝目錄下找到[1]。部分靜態鏈接庫如圖7所示。

圖7：部分靜態鏈接庫

2.5 運行測試代碼

此時在VS2019 中新建C++文件，在Github 官網中獲取一段代碼添加到VS 中即可運行。

3 Linux系統

本文的Linux 安裝平臺為Ubuntu 20.0，運行在虛擬機中，和Windows 系統一樣，我們首先去Github 官網中下載PCL 安裝包，根據PCL 官網安裝教程，我們下載的PCL 安裝包版本為pcl-1.11.0，格式為tar.gz。首先打開下載的安裝包界面的終端界面，輸入命令，將其解壓。如圖8所示。

圖8：解壓命令

3.1 安裝依賴庫

在Ubuntu 中安裝PCL 時需要大量依賴庫，為了保證能正常安裝PCL，我們首先下載所需要的各種依賴庫。在Ubuntu 系統中輸入圖9 命令并順利完成后，即可繼續完成后續操作。如圖9所示。

圖9：PCL 外部依賴庫

3.2 運行cmake ..

在解壓后的文件夾中新建build 文件夾，可以通過執行mkdir build 命令來完成操作。根據官網提示，接下來運行cmake 命令，cmake 是make system 的一個指令，編譯他的上一級到我們當前的目錄里面，然后在新建完成的build 終端下執行 cmake..命令，運行完成后如圖10所示。

圖10：運行完成的cmake

3.3 運行 make-j4

在虛擬中運行速度比較慢，所以在編譯的過程中需要點時間，圖11 是運行此命令常見的錯誤，此錯誤的解決辦法只需要將虛擬機的內存配置更大一下，就完美解決，命令運行完畢如圖12。

圖11：運行過程中出現的錯誤

圖12：運行完成

3.4 安裝PCL庫

在build 終端中輸入命令 make-j4 install，如果沒有改變PCL安裝位置的變量的話可能沒有權限，則需要運行sudo make-j4 install 命令，使用管理員身份進行安裝。安裝完成后，我們所需要的PCL 在Linux 系統中的平臺已經搭建完成。

相較于在Windows 中，在Ubuntu 下的搭建操作更為簡單，用戶如果在初級學習PCL 階段可以安裝虛擬機Linux 系統，但由于虛擬機中的顯卡是虛擬出來的，所以運行一寫代碼速度相對比較慢，內存占用比較多。如果是在高級學習階段或者相關職業從事者建議使用雙系統或者雙機獨立系統。

4 近鄰搜索

在點云配準或其它點云處理過程中，有時需要以點云中的某個點為中心，尋找它的鄰域，所以我們需要對原始的散亂無序的點云建立一定的拓撲關系，方便我們對其鄰域的搜索。現階段常用的建立點云拓撲關系的方法有許多，如Octree 法、K-D 樹法和三維柵格法，其中基于K-D 樹的方法由于其高效的搜索性能和良好的儲存空間被廣泛應用。

4.1 構建K-D樹

K-D 樹是一種樹狀數據結構，將實例點存儲在k 維空間中，便于快速檢索，主要應用于多維空間關鍵數據的搜索（如：范圍搜索和最近鄰搜索）。K-D 樹是二進制空間分割樹的特殊的情況，其基本原理是根據某一維度的值確定的超平面將原k 維空間分割成兩個k 維子空間，而這兩個子空間里的點分別構成根節點的兩棵子樹[2]，K-D 樹的三維空間構建模型如圖13所示。

圖13：K-D 三維空間模型

圖中紅色線部分就是沿著紅色線軸做個垂直分割面，同理，綠色和藍色也是根據其顏色線做垂直分割面，其實K-D 樹就是在三維平面XYZ 三個軸上輪流做了一次二叉樹。

K-D 樹建樹過程為：

（1）首先建立一個根節點；

（2）在X,Y,Z 三個軸上找出方差最大的值，其所在維度就作為分割數據的參考維度，這樣就可以將所在維度的數據點分散開來，可以最大程度的保證K-D 樹的平衡；

（3）將全部的數據點根據上述步驟中設置的參考維度進行排列，并選擇位于中間的點，然后將中間點作為根節點，與分裂維度上所有的數據進行比較，比中值小的點劃為左子樹，比中值大的點劃為右維度；

（4）構成的左子樹和右子樹中的數據點按照上述步驟分別再進行劃分，直到所有數據都被建立到K-D 樹的節點上為止。

自此，一個K-D 樹就建立完成。

4.2 搜索最鄰域

建立完K-D 樹后，對于確定已知的數據目標點，我們利用K-D樹來完成鄰域搜索[3]。我們首先拿到根節點S1，因為目標節點的X值小于根節點，所以們搜索左邊部分，來到S2 區域，目標節點的Y 值大于S2 故繼續搜索S4 區域，我們一直搜索，直到找到最末端節點。此時最末點節點為g，我們以目標節點為圓心，以節點g 為半徑畫一個圓，此時我們已經找到了一個節點g，此節點為目標節點的最快距離，正是因為最快節點的存在所以我們可以直接跳過一些區域，提高運算效率，圓內的區域為最快區域。因為圓內與S4區域有交集，所以繼續尋找S4 區域，S4 區域存在園內點e，且比最快距離要小，所以有可能是最近距離，故將圓半徑變為e，此時的圓與S5 左邊區域已無交集，故不在此區域進行搜索直接丟棄。來到S1 右邊區域，直接搜索S6 部分，但交集部分無最末端節點，搜索結束。如圖14、圖15所示。

圖14：K-D 樹圖

圖15：最近距離圖

利用K-D 樹查找最近距離的流程為：

（1）在構建好的K-D 樹中找出包含目標點的葉節點：從根結點出發，遞歸地向下訪問K-D 樹。若目標點當前維的坐標小于切分點的坐標，則移動到左葉子結點，否則移動到右葉子結點，直到子節點為葉節點為止；

（2）以目標點為圓心，以目標點到葉子節點樣本實例的距離為半徑，得到一個超球體，最近鄰的點一定在這個超球體內部；

（3）歸地向上進行回溯操作，在每個結點進行查詢，檢查另一個子節點包含的超矩形體是否和超球體相交，如果相交就到這個子節點尋找是否有更加近的近鄰，如果有則以該實例點為“當前最近點”；

（4）持續查找，直到搜尋完所有節點。

本文利用基于半徑查找最鄰近的點，此方法半徑是可以隨著距離的變化而變化，所以比KNN 更容易實現。

5 結束語

本文針對不同平臺搭建PCL 所需要的運行平臺，結合配置中出現的錯誤提出了相對應的解決方法，給廣大點云學者們提供了有效的數據參考。也針對海量數據集，結合開源C++點云庫創建了K-D樹的空間數據結構，實現了快速的鄰域搜索。