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

丁彩紅，張 耀

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

0 引 言

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

1 本文算法

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

1.1 數(shù)據(jù)空間分塊方法

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

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

(1)

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

1.2 數(shù)據(jù)點編號方法

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

圖1 子立方體編號方法

1.3 算法實現(xiàn)步驟

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

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

步驟2 計算每個方向的中值xmiddle，ymiddle，zmiddle，定義計數(shù)變量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]}，作為每個點的索引號。

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

2 鄰域搜索策略

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

(3)

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

圖2 相鄰子空間

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

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

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

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

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

步驟5 替換X為Y，轉(zhuǎn)步驟2；

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

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

圖3 三層樹結(jié)構(gòu)單方向編號

圖4 包圍盒相鄰體元

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

3 實驗驗證

3.1 實驗過程

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

圖5 實驗?zāi)Ｐ蛿?shù)據(jù)點

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

表1 例點分割編號

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

(4)

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

3.2 實驗結(jié)果分析

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

表2 鄰域搜索結(jié)果

圖6 最小體元邊長Lz與時間關(guān)系

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

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

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

表4 點云空間分塊時間

表5 點云鄰域搜索時間

4 結(jié)束語

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