三維十字鏈表八叉樹的高效檢索實現(xiàn)

譚玉玲

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

0 引言

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

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

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

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

1 算法設(shè)計

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

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

2.1 定義

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

2.2 基本操作

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

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

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

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

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

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

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

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

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

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

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

2.2.3 添加一個元素

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

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

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

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

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

圖1 當(dāng)前三維十字鏈表八叉樹 圖2 三維十字鏈表八叉樹添加點

2.2.4 刪除一個元素

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

(2)將每個維度上的該元素的前驅(qū)、后繼關(guān)系均設(shè)為nullptr；

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

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

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

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

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

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

2.2.5 迭代遍歷

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

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

3 試驗分析

3.1 試驗平臺

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

3.2 試驗結(jié)果分析

3.2.1 分析測試插入點的效率

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

3.2.2 對比實驗

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

本文通過對三維點云空間中領(lǐng)點數(shù)據(jù)結(jié)構(gòu)的高效檢索情況的研究，發(fā)現(xiàn)傳統(tǒng)的三維八叉樹的數(shù)據(jù)結(jié)構(gòu)對數(shù)據(jù)信息保存存在一定的問題，并且三維八叉樹的數(shù)據(jù)結(jié)構(gòu)對點云的領(lǐng)點查找速度也有待提高?；谶@些問題，本文提出通過設(shè)計三維十字鏈表八叉樹的數(shù)據(jù)結(jié)構(gòu)去實現(xiàn)三維點云空間中領(lǐng)點數(shù)據(jù)結(jié)構(gòu)的高效檢索。本文設(shè)計了三維八叉樹和三維十字鏈表八叉樹在插入、刪除、查找三個方面的檢索效率的試驗。通過試驗得出，三維十字鏈表八叉樹在稀疏空間中的優(yōu)勢更加明顯。