三維十字鏈表八叉樹的高效檢索實現

譚玉玲

(1.羅定職業技術學院 信息工程系，廣東 羅定 527200；2.北京師范大學 教育技術學院，北京 100082)

0 引言

三維激光掃描技術是測繪領域出現的一個新的技術。點云(point cloud)是在同一個空間的參考系下描述現在目標空間的分布和現在目標的表面特征的大量點的集合[1]。三維激光掃描技術能夠給出掃描物體表面所有三維點云的信息，所以可以用其獲得精確、高分辨率的數字地形模型[2]。

空間數據結構在早期主要用于空間數據庫及地理信息系統，將其用于三維點云數據結構的研究時，可以明顯地提高點云數據的查詢效率[3]。在空間數據結構技術研究中，出現了大量不同的算法，其中包括KD樹、八叉樹等[4-5]。如何提高三維點云信息數據的查詢、檢索效率是三維點云信息系統數據架構的關鍵問題。

現有的 KD 樹、八叉樹可以在二維空間中取得理想效果[6]，但是將其拓寬到更高層次的維度空間后，就很難完全滿足高維度空間組織和管理的需求[7]。另外，在基于空間的數據結構計算算法中，KD 樹、八叉樹等基于空間結構計算的方式通常都是針對某一類物體，不具備該算法的應用廣泛性，應用范圍也就有所限制[8]。因此，面對這種情況，運用其中一種數據架構難以滿足點云數據快速發展的需要。

本文提出了構建三維十字鏈表八叉樹的高維度數據結構的方案。在八叉樹的基礎上，利用十字鏈表，將三個維度方向的葉子節點鏈接起來，這樣可以有效地縮短查找點的時間以及減少時間復雜度；通過對三維八叉樹和三維十字鏈表八叉樹比較分析后發現，該算法提高了三維點云的數據查詢和檢索效率。

1 算法設計

用于表示物體表面信息的點云具有“稀疏性”[9]，即點云空間中絕大部分沒有點。在使用基于坐標的八叉樹數據結構描述的點云空間中，存在“空體素”，而深度學習遍歷算法的計算時要求逐個遍歷相鄰空間組。而八叉樹本身的樹形結構決定了其無法直接訪問兄弟節點，即無法以O(1)的時間復雜度直接訪問同級“體素”。進一步來說，基于坐標的八叉樹數據結構也無法在訪問“體素”前確認當前體素內是否有點，即無法做到直接跳過“空體素”。如果不對此做優化而直接使用基于坐標的八叉樹數據結構描述點云空間，那么在遍歷點云空間時，點云的“稀疏性”就會導致大量的時間浪費在詢問“點云是否為空”等操作上，而真正有效的計算操作比例卻非常低。因此，需要借用十字鏈表的思想，將沿著每個維度坐標方向的“非空”體素首尾相接，方便點云算法直接略過所有“空體素”，以期提升訪問點云的效率。

2 三維十字鏈表八叉樹的定義及基本操作

2.1 定義

三維十字鏈表八叉樹是一種用于描述三維空間的樹狀數據結構，其中的每個節點表示1個正方體的體積元素，每個節點有8個子節點，將8個子節點所表示的體積元素加在一起就等于父節點的體積[11]?！笆帧笔侵溉我鈨蓚€維度間互不相干，使用線性代數表達為線性無關。 “鏈表”是指每個維度方向上兩個相鄰元素的關聯方式為鏈表。使用鏈表的好處是可以跳過相鄰元素間的空白空間，以O(1)的時間復雜度訪問當前元素的相鄰元素。

2.2 基本操作

三維十字鏈表八叉樹的基本操作分為以下五個步驟。

2.2.1 判斷沿某個坐標軸方向是否為頭(尾)節點

(1)確定一個坐標軸方向；

(2)沿這個坐標軸方向判斷該坐標點的前驅是否為空，后繼是否為空；

(3)若前驅為空，后繼不為空，則該坐標點是頭節點；

(4)若前驅不為空，后繼為空，則該坐標點是尾節點。

2.2.2 判斷某個元素沿某個坐標軸是否有前驅(后繼)節點

(1)確定一個坐標軸方向；

(2)沿這個坐標軸方向判斷該坐標點的前驅是否為空，后繼是否為空；

(3)若前驅不為空，則該坐標點有前驅節點；

(4)若后繼不為空，則該坐標點有后繼節點。

2.2.3 添加一個元素

(1)判斷這個元素是否存在，若存在則進入下一步；

(2)若添加的元素為某一維度上的第一個節點，則將該節點的前驅設為空，該節點的后繼為之前的第一個節點，并且將之前的第一個節點的前驅設為現在新添加的節點；

(3)若添加的元素是中間節點，則該節點的前驅是添加位置的前一個結點，該節點的后繼是添加位置的后一個節點，前一個結點的后繼是該節點，后一個結點的前驅是該結點；

(4)若添加的元素是最后一個節點，則該節點的前驅為之前的最后一個節點，該節點的后繼為空。

如圖1所示，在圖中添加一個點C，變成圖2。首先判斷點C不存在于圖1中，然而確是圖2中點B第二維度方向上的第一個節點，所以將點C的前驅設為空，該節點的后繼為點B節點，而且將點B的前驅設為新添加的點C節點。

圖1 當前三維十字鏈表八叉樹 圖2 三維十字鏈表八叉樹添加點

2.2.4 刪除一個元素

(1)判斷這個元素是否存在，若存在則進入下一步；

(2)將每個維度上的該元素的前驅、后繼關系均設為nullptr；

(3)若刪除的元素是某一維度的第一個節點，則將頭節點修改為該維度上的下一個節點；

(4)若刪除的元素是某一維度的中間節點，則該節點的前驅節點是該節點的后繼節點的前驅，該節點的后繼節點是該節點前驅節點的后繼；

(5)若刪除的元素是某一維度的最后一個節點，則該節點的前驅節點的后繼設為空。

在圖2中刪除存在的點C，結果如圖3所示。首先判斷點C存在于圖2中，然后將每個維度上的點C的前驅、后繼關系均設為nullptr。刪除的點C是點B的第二維度上的第一個節點，頭節點需要修改為該維度上的點B節點。

在圖4中刪除不存在的點D，結果如下圖所示。在圖2中首先判斷不存在點D，然后拋出異常。

圖3 三維十字鏈表八叉樹成功刪除點 圖4三維十字鏈表八叉樹失敗刪除點

2.2.5 迭代遍歷

使用32個點在深度為4的三維十字鏈表八叉樹中進行迭代遍歷訪問。訪問過程中，以第三維度(z)為準進行迭代順序訪問。如圖5所示，三維十字鏈表八叉樹中存在3個點，分別是點A、點B、點C。在迭代遍歷訪問中，依據上述迭代遍歷描述具體過程，首先訪問點A(5，7，9)，然后訪問點C(5，8，10)，最后再訪問點B(6，8，10)。

圖5 迭代遍歷 圖6 插入點的效率對比

3 試驗分析

3.1 試驗平臺

該試驗是通過讀取PLY文件獲得點云的數據[12]，主要是在Windows10 64位操作系統上進行的。設備的配置信息：處理器是Intel Core i5-8250U，GPU是UHD，內存8 G，實驗中使用Ubuntu 20.04 LTS、Clion。試驗中使用了300萬個點。

3.2 試驗結果分析

3.2.1 分析測試插入點的效率

從圖6可以看出：(1)隨著點數的增大，耗時的基本規律是：8層>10層>12層；點數越大，不同層的耗時越多；8層的均值波動最??；層數越多，均值耗時越少。(2)均值圖上有幾個點比較突出，剩余的基本都是線性增長。其原因在于：C++自帶的標準庫的容器不是用一個開一個空間，而是先開一部分空間，然后連續往里存，用完了以后再開空間，所以開空間比較耗時。(3)層數越多，均值耗時越少。原因在于：層數越多意味著空間就越大，點不變的情況下，平均密度就越低，點所在體素重復概率就越低。

3.2.2 對比實驗

下面對本文提出的三維十字鏈表八叉樹和三維八叉樹[13-15]的效率進行對比。其中，黑色實線條表示三維十字鏈表八叉樹，而黑色虛線條表示三維八叉樹。

(1)插入數據的效率對比

試驗結果如圖7至圖9所示。在深度為8插入點時，隨著點數的增加，總體來說，三維十字鏈表八叉樹比三維八叉樹耗時短，不過，其中有一段它們的耗時一樣；在深度為10和12插入點時，隨著點數的增加，總體來說，三維十字鏈表八叉樹比三維八叉樹耗時短。試驗結果表明，隨著點數的增加，在不同深度的情況下，三維十字鏈表八叉樹的插入數據的效率比三維八叉樹更好。

圖7 插入點的對比(8層) 圖8 插入點的對比(10層)

圖9 插入點的對比(12層)

(2)查找數據的效率對比

試驗結果如圖10至圖12所示。在深度為8查找點時，隨著點數的增加，總體來說，三維十字鏈表八叉樹比三維八叉樹的耗時短；但是其中有兩個特別的點值得關注，它們分別是：當點數增加到30萬查找點時，三維八叉樹的耗時比三維十字鏈表八叉樹的短；當點數增加到大約100萬查找點時，三維十字鏈表八叉樹和三維八叉樹的耗時一樣。

圖10 查找點的對比(8層) 圖11 查找點的對比(10層)

圖12 查找點的對比(12層)

在深度為10查找點時，隨著點數的增加，總體來說，三維十字鏈表八叉樹比三維八叉樹的耗時短；但是有一個特殊的時間段，當點數增加到75萬至95萬這個區域時，三維八叉樹的耗時比三維十字鏈表八叉樹的短。

在深度為12查找點時，隨著點數的增加，有兩個特殊的時間段，分別是：當點數增加到32萬至47萬這個區域時，三維八叉樹的耗時比三維十字鏈表八叉樹更短；當點數增加到75萬至100萬這個區域時，三維八叉樹的耗時比三維十字鏈表八叉樹更短。其他的地方都是三維十字鏈表八叉樹比三維八叉樹耗時短。

試驗結果表明，隨著點數的增加，在不同深度的情況下，總體來說，三維十字鏈表八叉樹查找數據的效率比三維八叉樹好，但是也會有特殊的時間段出現了三維八叉樹的耗時更短的情況。

(3)刪除數據的效率對比

試驗結果如圖13至圖15所示。在深度為8刪除點時，隨著點數的增加，總體來說，三維十字鏈表八叉樹和三維八叉樹的耗時幾乎一樣。

在深度為10刪除點時，隨著點數的增加，只有在點數為20萬至40萬這個區域時，三維十字鏈表八叉樹比三維八叉樹耗時短，其他的地方均是三維八叉樹的耗時更短。

在深度為12刪除點時，隨著點數的增加，當點數到達50萬之后，三維十字鏈表八叉樹比三維八叉樹的耗時更短。

圖13 刪除點的對比(8層) 圖14 刪除點的對比(10層)

圖15 刪除點的對比(12層)

總體而言，試驗數據證實，隨著點數的增加，在不同深度的情況下，當深度越深，點數達到一定條件時，三維十字鏈表八叉樹的刪除數據的效率比三維八叉樹更好。這也說明三維十字鏈表八叉樹更適合稀疏空間的情況。

4 結論

本文通過對三維點云空間中領點數據結構的高效檢索情況的研究，發現傳統的三維八叉樹的數據結構對數據信息保存存在一定的問題，并且三維八叉樹的數據結構對點云的領點查找速度也有待提高?；谶@些問題，本文提出通過設計三維十字鏈表八叉樹的數據結構去實現三維點云空間中領點數據結構的高效檢索。本文設計了三維八叉樹和三維十字鏈表八叉樹在插入、刪除、查找三個方面的檢索效率的試驗。通過試驗得出，三維十字鏈表八叉樹在稀疏空間中的優勢更加明顯。