基于八叉樹編碼的點云鄰域搜索算法

丁彩紅，張 耀

(東華大學 機械工程學院，上海 201620)

0 引 言

近年來，激光掃描技術發展迅速，但激光點測量系統采集到的點通常呈散亂狀態。在實際應用中，如果此時直接用點云數據對模型表面進行重建，會大量占用計算機內存，給后續工作帶來很大困難。一般情況下，要先對離散點云建立拓撲結構，使相鄰K個點之間產生聯系，這樣，后續工作的效率將會大大提高。通常，要求得點云中某個點K個鄰域點集的方法是，先求出該點與點云中其余各點的歐氏距離，然后對所得距離進行升序排列，得到K個與采樣點距離最近的點。隨著計算機運算速度的提高，該方法在點云數量較少時能取得較滿意的效果，當點云數量巨大時，頻繁的距離計算，耗時驚人。查閱2000年后與點云鄰域搜索相關文獻發現，算法主要有3類：Voronoi圖法、樹層次法和空間分塊法。通過Voronoi圖建立點云K鄰域關系，首先要構建點集的Voronoi圖，此時，需進行較多的浮點運算，運算量較大[1]。M Muja等對K-D Tree進行了改進，通過確定最優鄰域算法參數和最佳搜索路徑進行K鄰域搜索，但對于不同的數據集，算法中要重新設定參數和路徑，此方法通用性欠佳[2]。文獻[3]基于“凡在同一區域的采樣點，它們鄰域的搜索范圍有著一定的重疊”的思想，利用多個相鄰的子空間逐步縮小搜索范圍，方法較新穎，但算法的穩定性不太理想。另外，研究者們提出了對海量數據進行空間劃分的方法，此類方法在求某點K近鄰時，目的在于縮小搜索范圍，僅在其所設定的網格中搜索，但如果該點不在網格的中心位置，可能導致搜索結果不完整[4-6]。針對這種情況，本文提出一種空間快速分塊策略以及對分割后空間的編號方法。通過空間編號對該空間內的點集建立索引號，再由目標立方體大小和點集的范圍，在編號方法和搜索終止準則上進行改進，給出最佳分層次數，提高了對目標點K個近鄰點的搜索速度。然后給出一種方法：包圍盒偏移法，對數據點進行再編碼，提高搜索結果的可靠性[7]。

1 本文算法

本文根據點云所在空間大小，利用樹的層次結構將該空間逐步分成大小相同的子空間，然后將點云中的每個點歸入到相應的子空間內，并給出索引號，最后利用目標點索引號信息，在其所在的立方塊及周圍立方塊中進行K個最近鄰域點搜索。

1.1 數據空間分塊方法

對點云所在空間立方體的分割時，先在每個維度上進行二分均等劃分，即取立方體3個垂直中分面剖切立方體，每層劃分3次，得到8個均等的子立方體，稱其為8個體元。對已劃分的8個體元用上述方法再次分割，形成空間樹層次結構[7]。這里對名稱做一些規定，在某三層樹結構中，最上層表示的體元在樹結構中稱為祖先結點，三層內所有結點都由祖先結點分割而來。在中間層中，規定被劃分的體元稱為父結點，劃分后的8個體元稱為子節點。當兩個體元屬于同一個父結點的子結點，稱為其關系為兄弟結點(關系)。當兩個體元在同一層次，但父結點不同，稱其關系為堂兄弟結點(關系)。形成的樹層次結構如圖1所示，依照此規則直到最小體元邊長達到給定的值Lz(mm)時分割終止[8]，分層次數計算如式(1)所示

n=[log10(Lc/Lz)/log102]

(1)

式中：[·]表示向上取整符號，Lc為單方向總長度，Lz為單方向上的給定值。

1.2 數據點編號方法

數據點的索引號也是通過樹的層次結構建立的。樹是一種非線性數據結構，它是數據元素(在樹中稱為結點)按分支關系組織起來的層次結構。樹的一種常用表示方法是子鏈表表示法。這種表示法會存儲樹的每個結點信息，形成的表稱為結點表。對每個結點建立一個子結點表。在本算法中樹的結點是分割后的體元，結點表中存儲著該體元的位置信息。子結點由父結點劃分而來，體積小于父結點。在對點云中每個點建立索引號時，首先要對劃分完的體元編號，在對體元編號過程中，子節點體元在父節點體元中按由下至上，由左到右，由后到前，依次由0到7編號，如圖1(b)所示。父結點比子節點少劃分一次，其編號位數就比子節點少一位。

圖1 子立方體編號方法

1.3 算法實現步驟

本次處理中首先由點云所有數據所在空間確定最小長方體包圍盒[xmin，xmax][ymin，ymax][zmin，zmax]，然后計算出子立方體的最大邊長Lc(mm)，再根據最小體元邊長Lz(mm)，由式(1)所示確定劃分層數n。在空間網格塊劃分完成并建立其編號基礎上，對每個數據點建立索引號。對每個點p(i)建立索引號，算法具體步驟如下：

步驟1 讀入點云文件，確定最小長方體包圍盒[xmin，xmax][ymin，ymax][zmin，zmax]；

步驟2 計算每個方向的中值xmiddle，ymiddle，zmiddle，定義計數變量i，并令i=1；

步驟3 比較候選點p(i)坐標，若xP[i]

步驟4 比較候選點坐標，若yP[i]

步驟5 比較候選點坐標，若zP[i]

步驟6i=i+1，若i

步驟7 按式(2)確定每個體元的分層編號N[i]，將N[i]的每個元素從左向右排列

N[i]=20xnum[i]+21ynum[i]+22znum[i]

(2)

步驟8 輸出每個點編號信息{N[1]，N[2]，…，N[i]}，作為每個點的索引號。

算法運行結束后會給點云中每個點建立了索引號。在后續點云鄰域搜索過程中，通過索引號僅在目標點所在體元及相鄰體元內進行搜索，這樣就大幅度縮小了搜尋范圍從而提高了搜索效率[9]。

2 鄰域搜索策略

為了加快點鄰域的搜索速度，將點的搜索范圍控制在很小的立方體內。在尋找目標點的K個近鄰時，不必與所有數據點計算距離。若目標點靠近其所在最小體元的邊界時，鄰域點可能在其緊鄰的體元內，且涉及的體元個數不一，如圖2所示。對固定的搜索半徑R所占體元個數m如式(3)所示

(3)

式中：[·]表示向上取整符號，n是分層的次數。

圖2 相鄰子空間

在三維空間中，體元之間有6個面即面相鄰、12條邊即邊相鄰和8個頂點即頂點相鄰3種方式，即一個體元有26個鄰體元，這些鄰體元都有各自的編號[8]。為了提高搜索結果的可靠性，這些鄰體元中的數據點在對目標點鄰域搜索時也需要考慮。鄰體元與目標點所在體元在樹結構中可能是兄弟結點關系，也可能是堂兄弟結點關系，亦或其最近的公共結點在兩層以上。要準確找到目標點所在體元的相鄰體元編號，一個基礎算法是從該結點體元沿已建立好的八叉樹結構向上搜索，直至找到與鄰體元最近的公共祖先結點，然后再從這個共同祖先結點向下即可找到相鄰體元的編號，但此算法結果容易發散，穩定性不佳。為了找到與目標點所在體元相鄰體元的共同祖先并得到相鄰體元的編號，這里給出一種新的方法:包圍盒定向偏移法。先將點云的包圍盒分別向X，Y，Z方向偏移一個八叉樹最底層體元的長度Lz，具體算法步驟如下：

步驟1 對點云中每個點按上一節算法建立索引號，記為索引號一；

步驟2 將包圍盒向X方向偏移一個X方向上最小體元長度Lz，確定新長方體包圍盒[xmin-Lz，xmax-Lz][ymin，ymax][zmin，zmax]；

步驟3 按新的包圍盒范圍對每個點重新編號，記為索引號二；

步驟4 從左向右比對索引號一與索引號二相同位數記為m，計算n-m，即為X方向上此點所在體元與其相鄰體元公共祖先在八叉樹結構中相差的層數；

步驟5 替換X為Y，轉步驟2；

步驟6 輸出索引號二信息。

以三層樹結構X方向為例，如圖3所示。假設點落在第四區域，其偏移前的編碼為011偏移后的編碼為100，n-m等于3，則第四區域所表示的體元和其右鄰體元的公共祖先結點在三層之前。第四區域所表示體元的右鄰體元的編號，只需將其后三位的編碼按位取反即可(011按位取反為100)。然后將包圍盒向XYZ這3個方向移動方式進行排列組合，移動一次時有6個位置，如圖4(a)所示。移動兩次時有12個位置，如圖4(b)所示。移動3次有8個不同的位置，如圖4(c)所示。各代表6個面與面相鄰體元、12條邊與邊相鄰體元和8個頂點與頂點相鄰體元[9,10]。

圖3 三層樹結構單方向編號

圖4 包圍盒相鄰體元

對于三維空間而言，每個體元對應六組二進制代碼，分別表示不同方向的偏移，將其按上述偏移方向進行組合得到目標點在其周圍體元的編號。求目標點的K近鄰點時，搜索目標點所在體元及其在偏移后體元內編號所包含的點，依次計算出各點與目標點的歐氏距離，從小到大排列取前K個即為K近鄰點。

3 實驗驗證

3.1 實驗過程

實驗中的點云數據分別是由激光掃描得到的汽車輪轂、汽車座椅、車模型點云坐標數據，點數分別為290 416、80 831、400 256將其坐標以散點圖顯示，如圖5所示。

圖5 實驗模型數據點

以實驗1汽車輪轂點云數據為例，用本文算法進行K個近鄰點查找。首先分別對包圍盒在XYZ方向上進行二分劃分并進行二進制編號。以輪轂點云其中一點為例，其坐標值為(122.36，213.18，-48.35)，編號結果見表1。每個坐標后，從左到右每個數字表示包含該坐標點的體元在其父節點體元中的相對位置，其中0表示在中點左邊，1表示在中點右邊。

表1 例點分割編號

按式(2)關系求得該點所在體元的編號同時也是該點的索引號。偏移前為76 153，X正方向偏移后為77 042。則其它5個面即面相鄰體元的編號分別為：76 171，76 157，76 152，76 151，76 117。遍歷編號為這些體元內的所有點，根據距離函數如式(4)所示，求出距離，進行升序排序

(4)

由此得到目標點的K近鄰點集(這里取K=15)。搜索結果見表2。

3.2 實驗結果分析

以實驗1汽車輪轂點云數據為例，測量分塊及建立索引號的總時間。研究不同的Lz值對總時間的影響，實驗結果如圖6所示。

表2 鄰域搜索結果

圖6 最小體元邊長Lz與時間關系

由圖6中曲線走勢可以看出對于分散程度均勻的點云。當數據量較小時，隨著Lz取值增大，索引號建立的時間減少，且呈指數下降，但變化率較小。當數據量較大時，點云所占空間范圍變大，子空間分割次數相應增多，耗時增多。實驗2汽車座椅的點云文件，如圖5(b)所示，其數據點分布不均勻，主要集中在立方體包圍盒一側，隨著Lz取值增大，索引號建立完成時間依然呈指數下降。實驗3的小車點云模型，如圖5(c)所示，數據量多而集中，而建立其點云索引號耗時沒有明顯增多。由此得出結論:該算法對點云文件建立索引號時，每個點計算次數與點云模型分散程度無關聯性。對于比較分散集中的點云數據，建模完成后，用本文算法進行鄰域搜索時，效率較高。實驗時間結果見表3。

表3 不同點云數據算法實驗結果(耗時/s)

針對不同的點云文件，分別用文獻[3]算法、文獻[4]算法、文獻[11]算法和本文算法，取Lz=10 mm分別測出不同K值對分塊和搜索所需要的時間，所有參與測試的算法,在主頻為3.6 GHz，內存8 GB的PC機上用Matlab2015a進行實驗，點云分塊和鄰域搜索時間各算法對比時間分別見表4、表5[11]。由實驗數據可知，本文所采用的算法在包圍盒定向偏移時需要重新編號時，所以分塊時間相比其它算法優勢不明顯，但點云索引號建立完成之后的K鄰域搜索過程中，本文算法搜索速度具有較明顯的優勢。

表4 點云空間分塊時間

表5 點云鄰域搜索時間

4 結束語

本文對點云數據處理的過程中，利用樹的層次結構，對點云所在的空間分層劃分，并對劃分后的子空間編號，再將每個點歸入其所在的子空間，將子空間的編號作為每個數據點索引號。在搜索點的近鄰時，僅需根據點的索引號在該點所在的子空間及其鄰近子空間中進行搜索，而這些點的數據量相對于整個數據集的數據量是非常小的，這樣就提高了搜索的效率。隨著計算機主頻的提升、內存的擴大和硬件之間數據傳輸速度的提高，處理小規模點云數據的速度已經滿足要求，但對海量點云數據處理速度仍有很大的提升空間。本文方法使對近鄰點的搜索時的搜尋范圍大大縮小。同時，又提出包圍盒定向偏移法提高了搜索結果的可靠性。在激光掃描提取信息技術發展迅速的今天，往往采集到的點都在數十萬以上，而且K鄰域的待求點數目也不止一個,本文的算法具有很好的實用性。