譚玉玲

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

0 引言

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

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

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

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

1 算法設(shè)計(jì)

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

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

2.1 定義

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

2.2 基本操作

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

2.2.1 判斷沿某個(gè)坐標(biāo)軸方向是否為頭(尾)節(jié)點(diǎn)

(1)確定一個(gè)坐標(biāo)軸方向；

(2)沿這個(gè)坐標(biāo)軸方向判斷該坐標(biāo)點(diǎn)的前驅(qū)是否為空，后繼是否為空；

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

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

2.2.2 判斷某個(gè)元素沿某個(gè)坐標(biāo)軸是否有前驅(qū)(后繼)節(jié)點(diǎn)

(1)確定一個(gè)坐標(biāo)軸方向；

(2)沿這個(gè)坐標(biāo)軸方向判斷該坐標(biāo)點(diǎn)的前驅(qū)是否為空，后繼是否為空；

(3)若前驅(qū)不為空，則該坐標(biāo)點(diǎn)有前驅(qū)節(jié)點(diǎn)；

(4)若后繼不為空，則該坐標(biāo)點(diǎn)有后繼節(jié)點(diǎn)。

2.2.3 添加一個(gè)元素

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

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

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

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

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

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

2.2.4 刪除一個(gè)元素

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

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

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

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

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

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

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

圖3 三維十字鏈表八叉樹成功刪除點(diǎn) 圖4三維十字鏈表八叉樹失敗刪除點(diǎn)

2.2.5 迭代遍歷

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

圖5 迭代遍歷 圖6 插入點(diǎn)的效率對(duì)比

3 試驗(yàn)分析

3.1 試驗(yàn)平臺(tái)

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

3.2 試驗(yàn)結(jié)果分析

3.2.1 分析測(cè)試插入點(diǎn)的效率

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

3.2.2 對(duì)比實(shí)驗(yàn)

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

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

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

圖7 插入點(diǎn)的對(duì)比(8層) 圖8 插入點(diǎn)的對(duì)比(10層)

圖9 插入點(diǎn)的對(duì)比(12層)

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

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

圖10 查找點(diǎn)的對(duì)比(8層) 圖11 查找點(diǎn)的對(duì)比(10層)

圖12 查找點(diǎn)的對(duì)比(12層)

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

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

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

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

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

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

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

圖13 刪除點(diǎn)的對(duì)比(8層) 圖14 刪除點(diǎn)的對(duì)比(10層)

圖15 刪除點(diǎn)的對(duì)比(12層)

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

4 結(jié)論

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