董路通 朱留存 張恒艷

（揚(yáng)州大學(xué)信息工程學(xué)院 江蘇省揚(yáng)州市 225127）

三維激光掃描技術(shù)源自于上世紀(jì)九十年代，它采用高速激光掃描測(cè)量方式，大面積高分辨率地快速獲取被測(cè)對(duì)象表面的三維坐標(biāo)數(shù)據(jù)（點(diǎn)云數(shù)據(jù)），可以快速、大量的采集空間點(diǎn)位信息，較傳統(tǒng)單點(diǎn)測(cè)量方法，它速度更快精度更高抗干擾性更強(qiáng)。隨著社會(huì)的發(fā)展，利用三維激光掃描儀快速高效獲取目標(biāo)物體的點(diǎn)云數(shù)據(jù)集越來(lái)越龐大，但所采集的數(shù)據(jù)集中通常無(wú)明顯的幾何拓?fù)湫畔ⅰＳ捎跀?shù)據(jù)集的龐大，所以提前建立點(diǎn)云拓?fù)潢P(guān)系，高效的有組織的管理點(diǎn)云，是對(duì)海量點(diǎn)云數(shù)據(jù)處理的前提。

在處理眾多點(diǎn)云數(shù)據(jù)時(shí)，我們需要對(duì)某一點(diǎn)進(jìn)行鄰域查找，我們首先應(yīng)該對(duì)原始的散亂的點(diǎn)云建立一定的拓?fù)潢P(guān)系，準(zhǔn)確的建立鄰域拓?fù)潢P(guān)系后不僅在目標(biāo)點(diǎn)的搜索查找范圍會(huì)縮小，而且更為后期的有效壓縮配準(zhǔn)提供了保障?；贙-D 樹(shù)的近鄰搜索是二進(jìn)制空間分割樹(shù)的特殊的情況，且具有有很高的搜索效率，K-D 樹(shù)可以使用在多種應(yīng)用場(chǎng)合，如多維鍵值搜索、K 近鄰搜索，該數(shù)據(jù)結(jié)構(gòu)建樹(shù)速度快，可以很快地知道目標(biāo)物體在3D 場(chǎng)景中的位置，或偵測(cè)目標(biāo)節(jié)點(diǎn)是否在可視范圍內(nèi)。本文結(jié)合PCL 開(kāi)源庫(kù)，針對(duì)海量點(diǎn)云數(shù)據(jù)建立K-D 樹(shù)數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)點(diǎn)云的快速鄰域搜索。

1 PCL

PCL 是在吸收前輩點(diǎn)云相關(guān)研究的基礎(chǔ)上建立起來(lái)的大范圍、獨(dú)立的、跨平臺(tái)的開(kāi)源C++編程庫(kù)，主要用于二維或三維的圖像和點(diǎn)云處理，可以在Windows、Linux、Android 和部分嵌入式實(shí)時(shí)系統(tǒng)上運(yùn)行。PCL 起初主要應(yīng)用于機(jī)器人研究，后來(lái)與全球3D 信息獲取、處理的研究者們一起，組建了強(qiáng)大的開(kāi)發(fā)維護(hù)團(tuán)隊(duì)，發(fā)展異常迅速。如同OpenCV 在2D 信息處理的地位一樣，PCL 主要運(yùn)用在3D 信息的獲取與處理[1]。

為了簡(jiǎn)化開(kāi)發(fā)，PCL 被分成一系列較小的代碼庫(kù)，這些代碼庫(kù)可以單獨(dú)編譯。這種模塊化對(duì)于在計(jì)算或者大小限制較少的平臺(tái)上發(fā)布PCL 非常重要。如圖1所示。

圖1：PCL 功能模塊

2 Windows系統(tǒng)

在PCL 官網(wǎng)中列出的在Windows 下安裝PCL 教程分為兩步：安裝PCL 依賴庫(kù)和編譯PCL 文件，介于操作的復(fù)雜性，也同時(shí)便于初學(xué)者安裝，暫不采用此方法安裝。本文介紹的編譯環(huán)境是Visual Studio 2019，操作系統(tǒng)為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 文件是程序的數(shù)據(jù)庫(kù)文件，是VS 編譯的生成文件，要想正常運(yùn)行PCL 文件必須要有pdb 文件。將pdb文件解壓后的文件移動(dòng)到PCL 安裝目錄中的bin 文件中，如圖2所示。

圖2：配置PCL 文件

2.2 配置環(huán)境變量

右鍵此電腦，找到高級(jí)系統(tǒng)設(shè)置中的環(huán)境變量。如圖3所示。

圖3：環(huán)境變量

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

圖4：Path 變量

2.3 包含目錄配置和庫(kù)目錄

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

圖5：包含目錄

圖6：庫(kù)目錄

2.4 輸入附加依賴項(xiàng)

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

圖7：部分靜態(tài)鏈接庫(kù)

2.5 運(yùn)行測(cè)試代碼

此時(shí)在VS2019 中新建C++文件，在Github 官網(wǎng)中獲取一段代碼添加到VS 中即可運(yùn)行。

3 Linux系統(tǒng)

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

圖8：解壓命令

3.1 安裝依賴庫(kù)

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

圖9：PCL 外部依賴庫(kù)

3.2 運(yùn)行cmake ..

在解壓后的文件夾中新建build 文件夾，可以通過(guò)執(zhí)行mkdir build 命令來(lái)完成操作。根據(jù)官網(wǎng)提示，接下來(lái)運(yùn)行cmake 命令，cmake 是make system 的一個(gè)指令，編譯他的上一級(jí)到我們當(dāng)前的目錄里面，然后在新建完成的build 終端下執(zhí)行 cmake..命令，運(yùn)行完成后如圖10所示。

圖10：運(yùn)行完成的cmake

3.3 運(yùn)行 make-j4

在虛擬中運(yùn)行速度比較慢，所以在編譯的過(guò)程中需要點(diǎn)時(shí)間，圖11 是運(yùn)行此命令常見(jiàn)的錯(cuò)誤，此錯(cuò)誤的解決辦法只需要將虛擬機(jī)的內(nèi)存配置更大一下，就完美解決，命令運(yùn)行完畢如圖12。

圖11：運(yùn)行過(guò)程中出現(xiàn)的錯(cuò)誤

圖12：運(yùn)行完成

3.4 安裝PCL庫(kù)

在build 終端中輸入命令 make-j4 install，如果沒(méi)有改變PCL安裝位置的變量的話可能沒(méi)有權(quán)限，則需要運(yùn)行sudo make-j4 install 命令，使用管理員身份進(jìn)行安裝。安裝完成后，我們所需要的PCL 在Linux 系統(tǒng)中的平臺(tái)已經(jīng)搭建完成。

相較于在Windows 中，在Ubuntu 下的搭建操作更為簡(jiǎn)單，用戶如果在初級(jí)學(xué)習(xí)PCL 階段可以安裝虛擬機(jī)Linux 系統(tǒng)，但由于虛擬機(jī)中的顯卡是虛擬出來(lái)的，所以運(yùn)行一寫代碼速度相對(duì)比較慢，內(nèi)存占用比較多。如果是在高級(jí)學(xué)習(xí)階段或者相關(guān)職業(yè)從事者建議使用雙系統(tǒng)或者雙機(jī)獨(dú)立系統(tǒng)。

4 近鄰搜索

在點(diǎn)云配準(zhǔn)或其它點(diǎn)云處理過(guò)程中，有時(shí)需要以點(diǎn)云中的某個(gè)點(diǎn)為中心，尋找它的鄰域，所以我們需要對(duì)原始的散亂無(wú)序的點(diǎn)云建立一定的拓?fù)潢P(guān)系，方便我們對(duì)其鄰域的搜索?，F(xiàn)階段常用的建立點(diǎn)云拓?fù)潢P(guān)系的方法有許多，如Octree 法、K-D 樹(shù)法和三維柵格法，其中基于K-D 樹(shù)的方法由于其高效的搜索性能和良好的儲(chǔ)存空間被廣泛應(yīng)用。

4.1 構(gòu)建K-D樹(shù)

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

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

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

K-D 樹(shù)建樹(shù)過(guò)程為：

（1）首先建立一個(gè)根節(jié)點(diǎn)；

（2）在X,Y,Z 三個(gè)軸上找出方差最大的值，其所在維度就作為分割數(shù)據(jù)的參考維度，這樣就可以將所在維度的數(shù)據(jù)點(diǎn)分散開(kāi)來(lái)，可以最大程度的保證K-D 樹(shù)的平衡；

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

（4）構(gòu)成的左子樹(shù)和右子樹(shù)中的數(shù)據(jù)點(diǎn)按照上述步驟分別再進(jìn)行劃分，直到所有數(shù)據(jù)都被建立到K-D 樹(shù)的節(jié)點(diǎn)上為止。

自此，一個(gè)K-D 樹(shù)就建立完成。

4.2 搜索最鄰域

建立完K-D 樹(shù)后，對(duì)于確定已知的數(shù)據(jù)目標(biāo)點(diǎn)，我們利用K-D樹(shù)來(lái)完成鄰域搜索[3]。我們首先拿到根節(jié)點(diǎn)S1，因?yàn)槟繕?biāo)節(jié)點(diǎn)的X值小于根節(jié)點(diǎn)，所以們搜索左邊部分，來(lái)到S2 區(qū)域，目標(biāo)節(jié)點(diǎn)的Y 值大于S2 故繼續(xù)搜索S4 區(qū)域，我們一直搜索，直到找到最末端節(jié)點(diǎn)。此時(shí)最末點(diǎn)節(jié)點(diǎn)為g，我們以目標(biāo)節(jié)點(diǎn)為圓心，以節(jié)點(diǎn)g 為半徑畫一個(gè)圓，此時(shí)我們已經(jīng)找到了一個(gè)節(jié)點(diǎn)g，此節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)的最快距離，正是因?yàn)樽羁旃?jié)點(diǎn)的存在所以我們可以直接跳過(guò)一些區(qū)域，提高運(yùn)算效率，圓內(nèi)的區(qū)域?yàn)樽羁靺^(qū)域。因?yàn)閳A內(nèi)與S4區(qū)域有交集，所以繼續(xù)尋找S4 區(qū)域，S4 區(qū)域存在園內(nèi)點(diǎn)e，且比最快距離要小，所以有可能是最近距離，故將圓半徑變?yōu)閑，此時(shí)的圓與S5 左邊區(qū)域已無(wú)交集，故不在此區(qū)域進(jìn)行搜索直接丟棄。來(lái)到S1 右邊區(qū)域，直接搜索S6 部分，但交集部分無(wú)最末端節(jié)點(diǎn)，搜索結(jié)束。如圖14、圖15所示。

圖14：K-D 樹(shù)圖

圖15：最近距離圖

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

（1）在構(gòu)建好的K-D 樹(shù)中找出包含目標(biāo)點(diǎn)的葉節(jié)點(diǎn)：從根結(jié)點(diǎn)出發(fā)，遞歸地向下訪問(wèn)K-D 樹(shù)。若目標(biāo)點(diǎn)當(dāng)前維的坐標(biāo)小于切分點(diǎn)的坐標(biāo)，則移動(dòng)到左葉子結(jié)點(diǎn)，否則移動(dòng)到右葉子結(jié)點(diǎn)，直到子節(jié)點(diǎn)為葉節(jié)點(diǎn)為止；

（2）以目標(biāo)點(diǎn)為圓心，以目標(biāo)點(diǎn)到葉子節(jié)點(diǎn)樣本實(shí)例的距離為半徑，得到一個(gè)超球體，最近鄰的點(diǎn)一定在這個(gè)超球體內(nèi)部；

（3）歸地向上進(jìn)行回溯操作，在每個(gè)結(jié)點(diǎn)進(jìn)行查詢，檢查另一個(gè)子節(jié)點(diǎn)包含的超矩形體是否和超球體相交，如果相交就到這個(gè)子節(jié)點(diǎn)尋找是否有更加近的近鄰，如果有則以該實(shí)例點(diǎn)為“當(dāng)前最近點(diǎn)”；

（4）持續(xù)查找，直到搜尋完所有節(jié)點(diǎn)。

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

5 結(jié)束語(yǔ)

本文針對(duì)不同平臺(tái)搭建PCL 所需要的運(yùn)行平臺(tái)，結(jié)合配置中出現(xiàn)的錯(cuò)誤提出了相對(duì)應(yīng)的解決方法，給廣大點(diǎn)云學(xué)者們提供了有效的數(shù)據(jù)參考。也針對(duì)海量數(shù)據(jù)集，結(jié)合開(kāi)源C++點(diǎn)云庫(kù)創(chuàng)建了K-D樹(shù)的空間數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)了快速的鄰域搜索。