一種八叉樹和三維R樹集成的激光點(diǎn)云數(shù)據(jù)管理方法

龔 俊，柯勝男，朱 慶，鐘若飛

1.江西師范大學(xué)軟件學(xué)院，江西南昌330022；2.武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北武漢430079；3.首都師范大學(xué)資源環(huán)境與旅游學(xué)院，北京100048

一種八叉樹和三維R樹集成的激光點(diǎn)云數(shù)據(jù)管理方法

龔 俊1，柯勝男1，朱 慶2，鐘若飛3

1.江西師范大學(xué)軟件學(xué)院，江西南昌330022；2.武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北武漢430079；3.首都師范大學(xué)資源環(huán)境與旅游學(xué)院，北京100048

車載激光掃描點(diǎn)云數(shù)據(jù)已經(jīng)成為數(shù)字城市和危機(jī)管理等領(lǐng)域越來(lái)越重要的三維空間信息源，針對(duì)大規(guī)模點(diǎn)云數(shù)據(jù)高效管理的技術(shù)瓶頸，提出一種八叉樹和三維R樹集成的空間索引方法——3DOR樹，充分利用八叉樹的良好收斂性創(chuàng)建R樹葉節(jié)點(diǎn)，避免逐點(diǎn)插入費(fèi)時(shí)過(guò)程，同時(shí)R樹平衡結(jié)構(gòu)保證良好的數(shù)據(jù)檢索效率。并還擴(kuò)展R樹結(jié)構(gòu)生成多細(xì)節(jié)層次（LOD）點(diǎn)云模型，提出一種支持緩存的多細(xì)節(jié)層次點(diǎn)云數(shù)據(jù)組織方法。試驗(yàn)證明，該方法具有良好的空間利用率和空間查詢效率，支持多細(xì)節(jié)層次描述能力和數(shù)據(jù)緩存機(jī)制，可應(yīng)用于大規(guī)模點(diǎn)云數(shù)據(jù)的后處理與綜合應(yīng)用。

八叉樹；三維R樹；激光掃描；點(diǎn)云；數(shù)據(jù)管理

1 引 言

歐洲空間數(shù)據(jù)研究組織EuroSDR指出三維城市建模能力需要具備高覆蓋度、高逼真度和高更新率，意味著對(duì)三維城市建模技術(shù)提出更好、更快、更廉價(jià)和更智能的要求，而這恰恰是傳統(tǒng)三維建模手段的弱項(xiàng)［1］。三維激光掃描技術(shù)和多角度攝影測(cè)量密集匹配技術(shù)為三維建模旺盛需求和有限人力物力資源間的沖突提供解決方案。RIEGL的VMX－250、TopCon的IP－S2和Optech的Lynx已是實(shí)際運(yùn)行的移動(dòng)測(cè)圖系統(tǒng)［2］。最新的移動(dòng)測(cè)圖系統(tǒng)裝備多個(gè)激光掃描儀，動(dòng)態(tài)獲取厘米級(jí)密度的海量三維激光點(diǎn)云，精度可達(dá)5cm［3］。移動(dòng)測(cè)圖系統(tǒng)的原始數(shù)據(jù)采集率為360GB／h，假設(shè)以30～40km／h行駛，每千米道路數(shù)據(jù)采集量為10GB，一個(gè)小城區(qū)的數(shù)據(jù)采集量可能高達(dá)若干TB，前所未有的數(shù)據(jù)采集速度和高分辨率要求對(duì)三維激光點(diǎn)云數(shù)據(jù)高效管理面臨更為嚴(yán)峻的挑戰(zhàn)［4］。

隨著高分辨率車載激光掃描系統(tǒng)的普及應(yīng)用，大量散亂點(diǎn)云數(shù)據(jù)的快速處理成為國(guó)際研究的焦點(diǎn)。點(diǎn)云數(shù)據(jù)后處理如簡(jiǎn)化濾波、語(yǔ)義分割和特征提取等交互操作受限于數(shù)據(jù)管理和可視化的性能，極大地制約了快速獲取點(diǎn)云數(shù)據(jù)的綜合應(yīng)用能力［5－6］。在計(jì)算機(jī)圖形學(xué)領(lǐng)域，發(fā)展了多種專門的數(shù)據(jù)組織方法加速繪制效率和質(zhì)量，但多關(guān)注單個(gè)目標(biāo)的點(diǎn)云數(shù)據(jù)，難以有效處理復(fù)雜場(chǎng)景的地物目標(biāo)數(shù)據(jù)。由于點(diǎn)云數(shù)據(jù)量大且分辨率高，一種有效的處理策略是顧及細(xì)節(jié)層次的自適應(yīng)可視化。Surfels［7］和Qsplat［8］是多細(xì)節(jié)層次點(diǎn)表達(dá)模型的兩個(gè)最具代表性的實(shí)現(xiàn)方法，它們的預(yù)處理過(guò)程均很費(fèi)時(shí)，不平衡的樹狀結(jié)構(gòu)容易導(dǎo)致樹深過(guò)高進(jìn)而致使查詢效率惡化。之后，計(jì)算機(jī)圖形領(lǐng)域的絕大多數(shù)方法基本是上述兩種方法的改進(jìn)，如采用并行處理方法和圖形處理器提高繪制效率，或者實(shí)現(xiàn)外存緩存機(jī)制等［9］。

在空間信息科學(xué)領(lǐng)域，文獻(xiàn)［10］提出基于順序四叉樹的數(shù)據(jù)組織方法管理機(jī)載激光點(diǎn)云，采用分段文件映射技術(shù)隨機(jī)抽取不同細(xì)節(jié)的點(diǎn)云，并關(guān)聯(lián)到相應(yīng)層的節(jié)點(diǎn)中，很好地實(shí)現(xiàn)了自適應(yīng)點(diǎn)云繪制，然而隨機(jī)抽取方式不能保證對(duì)車載激光點(diǎn)云也具有良好簡(jiǎn)化結(jié)果，過(guò)深樹高引發(fā)頻繁迭代計(jì)算也是影響管理效率的隱患。文獻(xiàn)［11］的方法與之類似，它們?nèi)匀皇且环N二維數(shù)據(jù)管理方法，難以最好地支持視錐體裁剪等可視化算子。文獻(xiàn)［12］采用八叉樹和平衡二叉樹的嵌套結(jié)構(gòu)管理海量點(diǎn)云，顧及了樹狀結(jié)構(gòu)的平衡性問(wèn)題，但是采用單一維度作為二叉樹剖分依據(jù)沒(méi)有顧及三維空間特性。文獻(xiàn)［13］采用空間數(shù)據(jù)分布方法將海量點(diǎn)云分配至多個(gè)服務(wù)器，采用并行訪問(wèn)技術(shù)提高數(shù)據(jù)管理效率，是利用計(jì)算機(jī)集群管理點(diǎn)云的有益嘗試。

三維R樹可以根據(jù)目標(biāo)數(shù)據(jù)自適應(yīng)地調(diào)整索引結(jié)構(gòu)，目標(biāo)分布狀態(tài)對(duì)其影響較小，是一種有前途的三維空間索引方法［14－15］。理論上，三維R樹的動(dòng)態(tài)更新和自適應(yīng)調(diào)整能力非常適合分布散亂、密度不均的三維點(diǎn)云應(yīng)用。然而，由于算法復(fù)雜、點(diǎn)云數(shù)量龐大等諸多原因，至今未見(jiàn)R樹成功管理點(diǎn)云的文獻(xiàn)發(fā)表。

本文利用八叉樹的快速收斂能力，提出一種八叉樹和R樹集成的新三維索引方法—3DOR樹，顯著提升大規(guī)模點(diǎn)云的R樹索引創(chuàng)建效率，并采用一種顧及多細(xì)節(jié)層次的三維R樹索引擴(kuò)展結(jié)構(gòu)高效生成多細(xì)節(jié)層次點(diǎn)云模型，支持大規(guī)模車載激光點(diǎn)云的高效管理和自適應(yīng)可視化。本文研究?jī)?nèi)容可以描述如圖1。

圖1 本文研究框架Fig.1 The framework of this study

2 集成八叉樹和R樹的三維空間索引模型3DOR樹

R樹索引能夠很好地適應(yīng)空間數(shù)據(jù)分布特點(diǎn)，且能提供穩(wěn)健高效的空間查詢能力［16］。R樹索引生成方法分為動(dòng)態(tài)方法和靜態(tài)方法，動(dòng)態(tài)生成方法更符合空間數(shù)據(jù)管理要求，但是每個(gè)點(diǎn)均要經(jīng)過(guò)節(jié)點(diǎn)選擇和節(jié)點(diǎn)分裂等復(fù)雜操作才能插入到索引結(jié)構(gòu)中，對(duì)于數(shù)以億計(jì)的點(diǎn)云數(shù)據(jù)來(lái)說(shuō)并不現(xiàn)實(shí)，需要尋求一種更高效的索引創(chuàng)建方法，本文采用一種動(dòng)靜結(jié)合的方式構(gòu)建三維R樹索引結(jié)構(gòu)，兼具靜態(tài)方法的高效率和動(dòng)態(tài)方法的自適應(yīng)性。

下面是結(jié)合三維R樹和八叉樹（octree）的索引創(chuàng)建算法（3DOct－Rtree，簡(jiǎn)稱3DOR樹）描述，圖2是3DOR樹創(chuàng)建流程圖。給三維R樹設(shè)定扇出（fanout）參數(shù)，即每個(gè)節(jié)點(diǎn)允許包含最大元組數(shù)目和最小元組數(shù)目，采用八叉樹剖分三維空間，節(jié)點(diǎn)收斂條件是每個(gè)葉節(jié)點(diǎn)中的點(diǎn)數(shù)目小于等于最大元組數(shù)目。八叉樹分裂過(guò)程中，滿足扇出參數(shù)條件的子節(jié)點(diǎn)將重新計(jì)算范圍，以葉節(jié)點(diǎn)身份插入到三維R樹中。點(diǎn)數(shù)小于扇出參數(shù)最小值的子節(jié)點(diǎn)中的點(diǎn)輸出至數(shù)組，按順序重組為滿足扇出參數(shù)的葉節(jié)點(diǎn)逐一插入到R樹，過(guò)程中不對(duì)數(shù)組中的點(diǎn)重新空間排序，原因是這些點(diǎn)相對(duì)鄰近，重新排序代價(jià)高且意義不大。對(duì)于無(wú)法保證滿足扇出參數(shù)的情況，添加其中的點(diǎn)到全局點(diǎn)數(shù)組中，待八叉樹剖分結(jié)束后，以單點(diǎn)身份逐一插入R樹。

算法描述：點(diǎn)云的空間索引創(chuàng)建算法。

算法輸入：點(diǎn)元組集合，R樹扇出參數(shù)為［imin，imax］。

算法輸出：三維R樹索引結(jié)構(gòu)。

步驟1：計(jì)算包含所有點(diǎn)集的最小包圍盒（minX，minY，minZ，maxX，maxY，maxZ），并以（minX，minY，minZ）為起算點(diǎn)，計(jì)算包含所有點(diǎn)集的最小立方體范圍，作為八叉樹根節(jié)點(diǎn)范圍，全部點(diǎn)均是節(jié)點(diǎn)node中的元組，并創(chuàng)建兩個(gè)點(diǎn)數(shù)組Array1和Array2。

步驟2：如果元組數(shù)目大于imax，則將空間均勻分為8個(gè)子節(jié)點(diǎn)Childi（i＝0，1，…，7），并將點(diǎn)分配至對(duì)應(yīng)的子節(jié)點(diǎn)，進(jìn)入步驟3；如果node中元組數(shù)目小于等于imax，則停止分裂。

步驟3：清空Array1，逐一遍歷子節(jié)點(diǎn)Childi，如果Childi中的點(diǎn)數(shù)目小于imin，將其中的點(diǎn)加入Array1中，令A(yù)rray1中的點(diǎn)數(shù)目為iPt－ Num，進(jìn)入步驟4。

圖2 3DOR樹創(chuàng)建流程圖Fig.2 Flow chart of the 3DOR－Tree construction procedure

步驟4：如果iPtNum小于imin，將數(shù)組中所有點(diǎn)逐一插入Array2中；如果iPtNum大于等于imin且小于等于imax，則將數(shù)組中所有點(diǎn)打包為葉節(jié)點(diǎn)插入R樹中；如果iPtNum大于imax且小于等于2imax，將點(diǎn)均分為兩個(gè)葉節(jié)點(diǎn)，插入R樹中；如果iPtNum大于2imax，k為iPtNum／imax取整，將數(shù)組前（k－1）imax個(gè)點(diǎn)，均分（k－1）個(gè)葉節(jié)點(diǎn)插入R樹，剩余點(diǎn)數(shù)iRestNum為iPtNum－（k－1）imax，如果iRestNum等于imax，則將其作為一個(gè)葉節(jié)點(diǎn)插入到R樹，如果大于imax（必然小于2imax），則將其均分為兩個(gè)葉節(jié)點(diǎn)，插入R樹中。

步驟5：逐一遍歷子節(jié)點(diǎn)Childi，如果Childi中的點(diǎn)數(shù)目大于imax，則令node為Childi，進(jìn)入步驟2。

步驟6：逐一遍歷子節(jié)點(diǎn)Childi，如果Childi中的點(diǎn)數(shù)目大于等于imin且小于等于imax，則將節(jié)點(diǎn)中的點(diǎn)組成葉節(jié)點(diǎn)插入R樹。

步驟7：所有八叉樹分支分裂結(jié)束后，將Array2中的點(diǎn)以元組身份逐一插入R樹。

步驟8：退出。

本方法利用八叉樹分配鄰近點(diǎn)至相同或相鄰節(jié)點(diǎn)中，通過(guò)以節(jié)點(diǎn)為插入單元的策略批量插入點(diǎn)，避免了逐點(diǎn)插入的費(fèi)時(shí)操作，顯著地提高索引生成效率，同時(shí)仍然采用動(dòng)態(tài)生成方法構(gòu)建R樹，使得樹形結(jié)構(gòu)具有很好的空間適應(yīng)性，保證平衡樹狀結(jié)構(gòu)和良好空間利用率。圖3是某點(diǎn)云數(shù)據(jù)的八叉樹葉節(jié)點(diǎn)層（分裂參數(shù)為100，即大于100個(gè)點(diǎn)要分裂節(jié)點(diǎn)）和3DOR樹結(jié)構(gòu)葉節(jié)點(diǎn)層（扇出參數(shù)為40和100）。

圖3 八叉樹和3DOR樹的葉節(jié)點(diǎn)層Fig.3 Leaf nodes in Octree and 3DOR－tree

3 顧及多細(xì)節(jié)層次的3DOR樹擴(kuò)展結(jié)構(gòu)

對(duì)于車載激光點(diǎn)云測(cè)圖應(yīng)用需要高效交互性能來(lái)說(shuō)，啟用多細(xì)節(jié)層次策略成為合理甚至必須的選擇，即根據(jù)視距和軟硬件性能實(shí)時(shí)選擇合適細(xì)節(jié)層次表示點(diǎn)云場(chǎng)景。關(guān)于R樹和多細(xì)節(jié)層次場(chǎng)景結(jié)合的已有研究均試圖采用R樹的天然層次結(jié)構(gòu)實(shí)現(xiàn)目標(biāo)查詢和細(xì)節(jié)層次查詢的雙重功能［17－19］。然而，應(yīng)用R樹節(jié)點(diǎn)包圍盒作為低細(xì)節(jié)層次描述，忽略單個(gè)目標(biāo)的LOD（level of details）描述需求，也不能滿足可視化精度要求。

傳統(tǒng)R樹索引方法僅在葉節(jié)點(diǎn)中管理目標(biāo)模型，本文擴(kuò)展結(jié)構(gòu)使得中間節(jié)點(diǎn)也能管理目標(biāo)模型。葉節(jié)點(diǎn)層管理全部和最精細(xì)的目標(biāo)，從每個(gè)子節(jié)點(diǎn)按照某種規(guī)則挑選一個(gè)最有代表性的目標(biāo)作為較粗層次目標(biāo)模型集合存于父節(jié)點(diǎn)中，因此上層節(jié)點(diǎn)中的目標(biāo)數(shù)目和子節(jié)點(diǎn)數(shù)目相等。舉例說(shuō)明，從每個(gè)子節(jié)點(diǎn)中選擇一個(gè)距離目標(biāo)集合重心最近的目標(biāo)作為上層節(jié)點(diǎn)的目標(biāo)。

本文方法借助R樹的層次結(jié)構(gòu)，葉節(jié)點(diǎn)代表最高的細(xì)節(jié)層次，中間節(jié)點(diǎn)代表中等的細(xì)節(jié)層次，根節(jié)點(diǎn)代表最低的細(xì)節(jié)層次。每層被設(shè)置一個(gè)適用范圍，包括最近距離和最遠(yuǎn)距離，相鄰層的適用范圍無(wú)縫拼接。同層中所有節(jié)點(diǎn)的適用范圍相同，當(dāng)視點(diǎn)和節(jié)點(diǎn)的距離落于該范圍內(nèi)，即訪問(wèn)節(jié)點(diǎn)中的點(diǎn)模型。在全景描繪時(shí)，只需訪問(wèn)根節(jié)點(diǎn)中的點(diǎn)模型，隨著視點(diǎn)接近，視域逐漸減小，關(guān)注細(xì)節(jié)逐漸提高，從根節(jié)點(diǎn)訪問(wèn)其子節(jié)點(diǎn)，根節(jié)點(diǎn)中的點(diǎn)僅是其子節(jié)點(diǎn)中的重要目標(biāo)，因此關(guān)注的目標(biāo)集合有所增加，細(xì)節(jié)層次增強(qiáng)。LOD選取距離原則的詳細(xì)解釋可以參考文獻(xiàn)［20］。圖4是點(diǎn)云的多細(xì)節(jié)層次描述效果。

圖4 點(diǎn)云的多細(xì)節(jié)層次描述Fig.4 LOD representation of point clouds

4 基于3DOR樹的點(diǎn)云數(shù)據(jù)高效組織方法

由于文件大小的限制，大規(guī)模點(diǎn)云工程采用工程－點(diǎn)云－點(diǎn)層次模式組織點(diǎn)云數(shù)據(jù)。車載激光點(diǎn)云采集過(guò)程中，每隔幾百萬(wàn)個(gè)點(diǎn)分段為單個(gè)點(diǎn)云，單個(gè)點(diǎn)云的原始文本文件數(shù)據(jù)量為數(shù)百兆字節(jié)，某個(gè)應(yīng)用中的點(diǎn)云集合即為點(diǎn)云工程，一個(gè)小型城鎮(zhèn)的點(diǎn)云工程可能高達(dá)數(shù)十GB。本文采用自定義的文件結(jié)構(gòu)組織大規(guī)模車載激光點(diǎn)云，目的是為了提高數(shù)據(jù)管理效率，其方法也可實(shí)現(xiàn)于商業(yè)數(shù)據(jù)庫(kù)管理系統(tǒng)。

以自定義文件系統(tǒng)方式為例，點(diǎn)云工程是包含眾多點(diǎn)云的目錄，點(diǎn)云是單個(gè)二進(jìn)制數(shù)據(jù)文件，圖5是本文數(shù)據(jù)組織方法描述。每個(gè)點(diǎn)云包括頭部分和實(shí)體部分，頭部分包括點(diǎn)云的整體信息，如版本號(hào)、總數(shù)據(jù)量、R樹扇出參數(shù)（子節(jié)點(diǎn)數(shù)目的最大最小值）、總點(diǎn)數(shù)、R樹總層數(shù)、空間范圍、中心點(diǎn)坐標(biāo)、壓縮標(biāo)志以及根節(jié)點(diǎn)地址等。點(diǎn)坐標(biāo)是實(shí)際點(diǎn)坐標(biāo)減去中心點(diǎn)坐標(biāo)的差值，這樣坐標(biāo)可以采用較少有效位數(shù)表示，有利于采用4字節(jié)單精度浮點(diǎn)類型表示點(diǎn)坐標(biāo)，另外，如果空間范圍在各坐標(biāo)軸上的長(zhǎng)度小于655.35m且精度要求在厘米級(jí)（車載激光掃描數(shù)據(jù)精度可達(dá)到厘米級(jí)），將坐標(biāo)值乘以100然后用2字節(jié)短整數(shù)類型表示點(diǎn)坐標(biāo)，數(shù)據(jù)量減少75%。

圖5 點(diǎn)云工程數(shù)據(jù)組織方法Fig.5 Data organization method of point cloud project

點(diǎn)云的實(shí)體部分采用三維R樹索引結(jié)構(gòu)管理點(diǎn)數(shù)據(jù)，R樹索引結(jié)構(gòu)包括根節(jié)點(diǎn)、中間節(jié)點(diǎn)和葉節(jié)點(diǎn)。本文的多細(xì)節(jié)層次生成方法中，上層節(jié)點(diǎn)從每個(gè)子節(jié)點(diǎn)中選取一個(gè)點(diǎn)作為低細(xì)節(jié)層次描述，為避免重復(fù)存儲(chǔ)和處理，選取點(diǎn)將從子節(jié)點(diǎn)移出至上層節(jié)點(diǎn)，這樣中間節(jié)點(diǎn)和葉節(jié)點(diǎn)中的點(diǎn)數(shù)目要減1。為了實(shí)現(xiàn)緩存機(jī)制，即根據(jù)視域條件動(dòng)態(tài)調(diào)度數(shù)據(jù)，父節(jié)點(diǎn)記錄子節(jié)點(diǎn)的首地址，即子節(jié)點(diǎn)相對(duì)文件起始位置的偏移量。R樹存儲(chǔ)結(jié)構(gòu)可以分為按廣度遍歷存儲(chǔ)順序和按深度遍歷存儲(chǔ)順序組織。廣度遍歷存儲(chǔ)順序指按節(jié)點(diǎn)層的次序存儲(chǔ)節(jié)點(diǎn)數(shù)據(jù)，從根節(jié)點(diǎn)開(kāi)始，將節(jié)點(diǎn)按層順序依次記錄到文件中，負(fù)面影響是父節(jié)點(diǎn)和子節(jié)點(diǎn)無(wú)法集中存儲(chǔ)；深度遍歷存儲(chǔ)順序指從根節(jié)點(diǎn)開(kāi)始，然后記錄其各個(gè)子樹，負(fù)面影響是中間層的兄弟節(jié)點(diǎn)無(wú)法集中存儲(chǔ)。圖6（a）和（b）分別是廣度遍歷存儲(chǔ)和深度遍歷存儲(chǔ)的原理。

圖6 廣度和深度遍歷存儲(chǔ)原理描述Fig.6 Principal description of breadth and depth traversal storage

點(diǎn)云工程數(shù)據(jù)規(guī)模通常很大，超出主存容量和圖形繪制硬件處理能力，一般打開(kāi)工程時(shí)僅調(diào)度上面數(shù)層節(jié)點(diǎn)中的點(diǎn)數(shù)據(jù)以描述全景，當(dāng)視點(diǎn)逼近局部場(chǎng)景時(shí)，將通過(guò)父節(jié)點(diǎn)依次訪問(wèn)子節(jié)點(diǎn)直至葉節(jié)點(diǎn)，因此廣度優(yōu)先存儲(chǔ)和深度優(yōu)先存儲(chǔ)方式均不能完全滿足高效調(diào)度的要求。本文采用二者混合方案來(lái)最大限度提升數(shù)據(jù)調(diào)度效率。以葉節(jié)點(diǎn)層為第0層，例如全景顯示第2層及以上節(jié)點(diǎn)中的點(diǎn)數(shù)據(jù)時(shí)，將第2層及以上層采用廣度優(yōu)先存儲(chǔ)，最下兩層按照深度優(yōu)先存儲(chǔ)，至于具體以第幾層為分界線，將根據(jù)總數(shù)據(jù)量決定，如果數(shù)據(jù)量小可以下調(diào)，如果數(shù)據(jù)量大可以上調(diào)。圖7是本文方法的原理描述，其中第2層是分界線。本文方法采用文件映射技術(shù)訪問(wèn)點(diǎn)云文件，每個(gè)父節(jié)點(diǎn)記錄所有子節(jié)點(diǎn)地址，采用類似于訪問(wèn)內(nèi)存方法根據(jù)節(jié)點(diǎn)地址訪問(wèn)節(jié)點(diǎn)外存數(shù)據(jù)。本文方法將極有可能連續(xù)訪問(wèn)的節(jié)點(diǎn)數(shù)據(jù)集中存儲(chǔ)，有利于提高外存訪問(wèn)效率。

圖7 混合存儲(chǔ)方式原理描述Fig.7 Principal description of mixed storage

單點(diǎn)數(shù)據(jù)內(nèi)容包括三維坐標(biāo)、顏色以及強(qiáng)度等信息，可以根據(jù)應(yīng)用需要擴(kuò)展單點(diǎn)結(jié)構(gòu)。如果采取壓縮方式存儲(chǔ)，三維坐標(biāo)值采用2字節(jié)短整型表示，相對(duì)于雙精度浮點(diǎn)型表示，數(shù)據(jù)量減少75%，可以顯著減少數(shù)據(jù)調(diào)度量，提升外存訪問(wèn)效率。另外，為最大限度提升三維可視化效率，點(diǎn)數(shù)據(jù)應(yīng)當(dāng)按照?qǐng)D形繪制硬件特點(diǎn)進(jìn)行組織，例如，采用OpenGL繪制引擎時(shí)，可以將節(jié)點(diǎn)中的點(diǎn)數(shù)據(jù)組織成VBO頂點(diǎn)緩沖形式，直接送入繪制管線處理。

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

本試驗(yàn)采用測(cè)試數(shù)據(jù)是車載激光掃描移動(dòng)測(cè)圖系統(tǒng)采集的真實(shí)數(shù)據(jù)，是中國(guó)某小型城鎮(zhèn)的真彩色三維點(diǎn)云數(shù)據(jù)。車輛行駛耗費(fèi)20min掃描該鎮(zhèn)全部道路，獲取詳細(xì)的街道、房屋立面、樹木以及電線等點(diǎn)模型。原始數(shù)據(jù)包含92個(gè)點(diǎn)云文件，每個(gè)點(diǎn)云文件包含200多萬(wàn)個(gè)點(diǎn)，總數(shù)據(jù)量約為14.6GB（包含坐標(biāo)、顏色、時(shí)間等數(shù)據(jù)），總點(diǎn)數(shù)為2.2億。測(cè)試環(huán)境配置如下：筆記本電腦，CPU Intel Duo T7500，內(nèi)存1GB。

5.1 索引創(chuàng)建效率測(cè)試

索引創(chuàng)建效率關(guān)系到應(yīng)用成敗，如果索引創(chuàng)建需要十幾個(gè)小時(shí)甚至更長(zhǎng)，即使查詢效率滿足交互要求，也不能適應(yīng)實(shí)際應(yīng)用需要。由于格網(wǎng)索引的格網(wǎng)尺寸難以確定，且大量空格網(wǎng)容易導(dǎo)致空間利用率極低，本文不予比較測(cè)試。本文分別對(duì)八叉樹、三維動(dòng)態(tài)R樹和3DOR樹生成算法進(jìn)行效率測(cè)試。其中，八叉樹參數(shù)為100，即節(jié)點(diǎn)中點(diǎn)數(shù)目小于等于100時(shí)停止分裂，三維R樹的扇出參數(shù)為40和100，而3DOR樹中，八叉樹分裂參數(shù)為100，R樹扇出參數(shù)為40和100。

采用一份包含2 426 454個(gè)點(diǎn)的點(diǎn)云數(shù)據(jù)測(cè)試索引創(chuàng)建效率，表1中有八叉樹、3DOR樹以及三維動(dòng)態(tài)R樹的創(chuàng)建效率對(duì)比。八叉樹深度不平衡，葉節(jié)點(diǎn)樹深從1到17不等。3DOR樹深度平衡，樹深為4。三維動(dòng)態(tài)R樹深度平衡，樹深為5。從測(cè)試數(shù)據(jù)可知，本文的3DOR索引方法創(chuàng)建效率滿足準(zhǔn)實(shí)時(shí)要求，樹深平衡，并且樹深比另兩種方法小。原因是，3DOR樹本質(zhì)上仍是R樹索引結(jié)構(gòu)，且葉節(jié)點(diǎn)基本是滿負(fù)荷，從而節(jié)點(diǎn)數(shù)目減少和深度減小。較小的樹深直接減少迭代運(yùn)算層數(shù)，有利于顯著改善算法效率。本文對(duì)總數(shù)據(jù)量14.6GB的點(diǎn)云工程創(chuàng)建索引，總耗費(fèi)時(shí)間約為40min。

5.2 空間利用率測(cè)試

相對(duì)于CPU計(jì)算和主存訪問(wèn)效率，外存訪問(wèn)效率低兩個(gè)數(shù)量級(jí)以上且改善空間有限，數(shù)據(jù)量大小直接關(guān)系到后續(xù)外存數(shù)據(jù)調(diào)度效率，進(jìn)而影響用戶體驗(yàn)。點(diǎn)云工程數(shù)據(jù)量往往大于主存容量，動(dòng)態(tài)調(diào)度和數(shù)據(jù)緩存機(jī)制成為必須采用的策略。本文通過(guò)中心點(diǎn)平移方法將雙精度浮點(diǎn)型數(shù)據(jù)轉(zhuǎn)化為單精度浮點(diǎn)型，進(jìn)一步將單精度浮點(diǎn)型轉(zhuǎn)化為短整型，并清除冗余點(diǎn)（距離小于1cm視為冗余點(diǎn)），數(shù)據(jù)量壓縮顯著，表1中有文本格式、Pointools商業(yè)格式和本文結(jié)構(gòu)的數(shù)據(jù)量對(duì)比。不難看出，原始文本數(shù)據(jù)轉(zhuǎn)化為本文數(shù)據(jù)格式，壓縮率超過(guò)全球業(yè)界領(lǐng)先者Pointools。

表1 空間索引重要指標(biāo)對(duì)比Tab.1 Comparison of key criteria for spatial index

5.3 數(shù)據(jù)調(diào)度與可視化效率測(cè)試

如果用戶打開(kāi)和全景顯示工程的等待時(shí)間過(guò)長(zhǎng)，將嚴(yán)重影響用戶體驗(yàn)。采用Pointools商業(yè)平臺(tái)將試驗(yàn)數(shù)據(jù)轉(zhuǎn)化為其特有POD格式并組織成為工程后，試驗(yàn)環(huán)境打開(kāi)工程耗時(shí)超過(guò)4min。由于是商業(yè)平臺(tái)，無(wú)法測(cè)算其效率瓶頸。值得指出的是，當(dāng)工程打開(kāi)后，該商業(yè)平臺(tái)可以保證后續(xù)交互操作的流暢性。

本文方法中，點(diǎn)云工程包含2億多個(gè)點(diǎn)，扇出參數(shù)為40和100，第2層及以上點(diǎn)云模型不會(huì)超過(guò)10萬(wàn)個(gè)點(diǎn)（2×108／（40×40）），因此打開(kāi)工程只需調(diào)度第2層及以上的點(diǎn)云模型。第2層以上按照廣度優(yōu)先遍歷方法進(jìn)行存儲(chǔ)，后續(xù)訪問(wèn)時(shí)按照廣度優(yōu)先遍歷順序即可將所需節(jié)點(diǎn)外存數(shù)據(jù)依次讀取，不會(huì)出現(xiàn)跳躍訪問(wèn)，最大限度地提高數(shù)據(jù)訪問(wèn)效率，試驗(yàn)結(jié)果表明耗時(shí)僅需4s，圖8是點(diǎn)云工程的全景圖。另外，本文設(shè)計(jì)試驗(yàn)測(cè)試深度優(yōu)先存儲(chǔ)方法的訪問(wèn)效率，節(jié)點(diǎn)數(shù)據(jù)重新按照深度優(yōu)先遍歷方式存儲(chǔ)，打開(kāi)整個(gè)工程耗時(shí)3min，相比于本文方法，效率下降明顯。

圖8 點(diǎn)云工程全景Fig.8 Full scene of point cloud project

本試驗(yàn)環(huán)境允許的數(shù)據(jù)緩存容量不超過(guò)200兆，單幀繪制點(diǎn)數(shù)不超過(guò)500萬(wàn)個(gè)，如果超過(guò)容許值將自動(dòng)清理緩沖區(qū)。當(dāng)視點(diǎn)落于場(chǎng)景中近距離瀏覽地物目標(biāo)時(shí)，自適應(yīng)可視化機(jī)制下最高細(xì)節(jié)層次作用范圍的最遠(yuǎn)距離一般保持在15m左右，即使顯著改變視點(diǎn)位置，所需調(diào)度數(shù)據(jù)量也不會(huì)超過(guò)10MB，調(diào)度時(shí)間不超過(guò)2s。試驗(yàn)采用多線程機(jī)制調(diào)度數(shù)據(jù)，并不影響主線程繪制任務(wù)，實(shí)現(xiàn)點(diǎn)云場(chǎng)景多細(xì)節(jié)層次描述效果。

5.4 空間查詢效率測(cè)試

車載激光掃描平臺(tái)的一項(xiàng)重要任務(wù)是三維測(cè)圖，捕捉三維點(diǎn)成為應(yīng)用成敗的關(guān)鍵。如果不借助空間索引功能，從場(chǎng)景中數(shù)以億計(jì)的點(diǎn)集中搜索目標(biāo)點(diǎn)將會(huì)效率極低。本文借助三維R樹索引能力，捕捉目標(biāo)點(diǎn)沒(méi)有明顯停頓，符合交互測(cè)圖要求。試驗(yàn)過(guò)程測(cè)試多個(gè)環(huán)節(jié)，如捕捉點(diǎn)、場(chǎng)景移動(dòng)和連線等功能，均能實(shí)現(xiàn)流暢交互操作。圖9是本試驗(yàn)平臺(tái)的測(cè)圖結(jié)果，其中包括天線和建筑物墻面等測(cè)圖成果。

圖9 試驗(yàn)平臺(tái)三維測(cè)圖效果Fig.9 3Dmapping in experimental platform

6 結(jié) 論

大規(guī)模點(diǎn)云管理和可視化是阻礙點(diǎn)云應(yīng)用的難題，本文采用一種集成八叉樹和三維R樹的新方法，借助八叉樹細(xì)粒度地劃分點(diǎn)云的三維空間，通過(guò)將八叉樹葉節(jié)點(diǎn)組織為R樹葉節(jié)點(diǎn)的策略，避免了海量點(diǎn)云的逐點(diǎn)插入操作，顯著提升索引創(chuàng)建效率，由于依然采用動(dòng)態(tài)插入方法創(chuàng)建三維R樹，保證了深度平衡的樹狀結(jié)構(gòu)，實(shí)現(xiàn)良好的空間查詢效率。基于R樹的天然層次結(jié)構(gòu)，本文還提出了一種點(diǎn)云場(chǎng)景多細(xì)節(jié)層次模型生成方法和點(diǎn)云數(shù)據(jù)層次組織結(jié)構(gòu)。本文研究不僅為大規(guī)模點(diǎn)云自適應(yīng)可視化提供管理支持，同時(shí)也為激光點(diǎn)云深度利用提供理論和方法支持。

當(dāng)前單點(diǎn)包含4～6個(gè)屬性值，隨著傳感器技術(shù)的發(fā)展，未來(lái)極可能翻倍甚至更多，通過(guò)自動(dòng)分類和目標(biāo)提取還可以產(chǎn)生更加豐富的語(yǔ)義信息，也給點(diǎn)云管理帶來(lái)新挑戰(zhàn)。語(yǔ)義可以視為點(diǎn)云的另一種細(xì)節(jié)層次，后續(xù)研究將面向數(shù)據(jù)融合和語(yǔ)義管理的點(diǎn)云管理方法，實(shí)現(xiàn)同全景影像、矢量圖形以及語(yǔ)義信息的集成應(yīng)用。

［1］ NEBIKER S，BLEISCH S，GüLCH E.EuroSDR Online Survey on Virtual Globes［R］.The 114th EuroSDR Steering Committee Meeting，Paris：［s.n.］，2009.

［2］ BARBER D，MILLS J，SMITH－VOYSEY S.Geometric Validation of a Ground Based Mobile Laser Scanning System［J］.ISPRS Journal of Photogrammetry and Remote Sensing，2008，63（1）：128－141.

［3］ HAALA N，PETER M，KREMER J，et al.Mobile LiDAR Mapping for 3DPoint Cloud Collection in Urban Areas—A Performance Test［C］∥Proceedings of XXI ISPRS Congress.［S.l.］：ISPRS，2008.

［4］ NEBIKER S，BLEISCH S，CHRISTEN M.Rich Point Clouds in Virtual Globes——A New Paradigm in City Modeling？［J］Computer，Environment ＆Urban System，2010，34（6）：508－517.

［5］ YANG Bisheng，WEI Zheng，LI Qingquan，et al.A Classification－oriented Method of Feature Image Generation for Vehicle－borne Laser Scanning Point Clouds［J］.Acta Geodaetica et Cartographica Sinica，39（5）：540－545.（楊必勝，魏征，李清泉，等.面向車載激光掃描點(diǎn)云快速分類的點(diǎn)云特征圖像生成方法［J］.測(cè)繪學(xué)報(bào)，2010，39（5）：540－545.）

［6］ HUANG Xianfeng，LI Hui，WANG Xiao，et al.Filter Algorithms of Airborne LiDAR Data：Review and Prospects［J］.Acta Geodaetica et Cartographica Sinica， 2009，38（5）：466－469.（黃先鋒，李卉，王瀟，等.機(jī)載Li－DAR數(shù)據(jù)濾波方法評(píng)述［J］.測(cè)繪學(xué)報(bào)，2009，38（5）：466－469.）

［7］ PFISTER H，ZWICKER M，VAN BAAR J，et al.Surfels：Surface Elements as Rendering Primitives［C］∥Proceedings of ACM SIGGRAPH 2000.New York：ACM Press，2000：335－342.

［8］ RUSINKIEWICZ S，LEVOY M.QSplat：A Multiresolution Point Rendering System for Large Meshes［C］∥Proceedings of ACM SIGGRAPH 2000.New York：ACM Press，2000：343－352.

［9］ WAND M，BERNER A，BOKELOH M，et al.Processing and Interactive Editing of Huge Point Clouds from 3D Scanners［J］.Computer ＆Graphics，2008，32（2）：204－220.

［10］ HUANG Xiangfeng.Research on 3DBuilding Model Extraction from Airborne LIDAR Data［D］.Wuhan：Wuhan University，2006.（黃先鋒.利用機(jī)載LiDAR數(shù)據(jù)重建3D建筑物模型的關(guān)鍵技術(shù)研究［D］.武漢：武漢大學(xué)，2006.）

［11］ ZHI Xiaodong，LIN Zongjian，SU Guozhong，et al.Research on Organization of Airborne LiDAR Points Cloud Based on Improved Quadtree Algorithm［J］.Computer Engineering and Applications，2010，46（9）：71－74.（支曉棟，林宗堅(jiān)，蘇國(guó)中，等.基于改進(jìn)四叉樹的LiDAR點(diǎn)云數(shù)據(jù)組織研究［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（9）：71－74.）

［12］ LU Mingyue，HE Yongjian.Organization and Indexing Method for 3DPoints Cloud Data［J］.Geo－information Science，2008，10（2）：190－194.（路明月，何永健.三維海量點(diǎn)云數(shù)據(jù)的組織與索引方法［J］.地球信息科學(xué)，2008，10（2）：190－194.）

［13］ MA H，WANG Z.Distributed Data Organization and Parallel Data Retrieval Methods for Huge Scanner Point Clouds［J］.Computer ＆Geoscience，2011，37（1）：193－201.

［14］ ZHU Q，GONG J，ZHANG Y T.An Efficient 3DR－tree Spatial Index Method for Virtual Geographic Environments［J］.ISPRS Journal of Photogrammetry and Remote Sensing，2007，62（3）：217－224.

［15］ GONG Jun，ZHU Qing，ZHANG Yeting，et al.An Efficient 3DR－tree Extension Method Concerned with Levels of Detail［J］.Acta Geodaetica et Cartographica Sinica，2011，40（2）：249－255.（龔俊，朱慶，張葉廷，等.顧及多細(xì)節(jié)層次的三維R樹索引擴(kuò)展方法［J］.測(cè)繪學(xué)報(bào)，2011，40（2）：249－255.）

［16］ MANOLOPOULOS Y，NANOPOULOS A，PAPADOPOULOS A N，et al.R－Trees：Theory and Applications［M］.Germany：Springer Press，2005.

［17］ KOFLER M.R－trees for Visualizing and Organizing Large 3DGIS Databases［D］.Graz：Graz University of Technology，1998.

［18］ ZLATANOVA S.3DGIS for Urban Development［D］.Enschede：ITC，2000.

［19］ LI Jun，JING Ning，SUN Maoyin.A Mechanism of Implementing Visualization with Level of Detail at Multi－Scale［J］.Journal of Software，2002，13（10）：2037－2043.（李軍，景寧，孫茂印.多比例尺下細(xì)節(jié)層次可視化的實(shí)現(xiàn)機(jī)制［J］.軟件學(xué)報(bào)，2002，13（10）：2037－2043.）

［20］ GONG Jun，ZHU Qing，ZHANG Hanwu，et al.An Adaptive Control Method of LoDs for 3DScene Based on R－tree Index［J］.Acta Geodaetica et Cartographica Sinica，2011，40（4）：531－534.（龔俊，朱慶，章漢武，等.基于R樹索引的三維場(chǎng)景細(xì)節(jié)層次自適應(yīng)控制方法［J］.測(cè)繪學(xué)報(bào)，2011，40（4）：531－534.）

E－mail：gongjunbox＠gmail.com

An Efficient Management Method for Point Cloud Data Based on Octree and3D R－tree

GONG Jun1，KE Shengnan1，ZHU Qing2，ZHONG Ruofei3
1.Department of Software，Jiangxi Normal University，Nanchang330022，China；2.State Key Laboratory of Information Engineering in Surveying，Mapping and Remote Sensing，Wuhan University，Wuhan 430079，China；3.Capital Normal University，College of Resources，Environment and Tourism，Beijing100048，China

Vehicle－borne laser point cloud data has become key 3D spatial information source in fields such as digital city and crisis management.Aiming at technical bottleneck of large－scale point cloud data management，a new spatial index method－3DOR－tree is presented，which integrates octree and3D R－tree.This method utilizes octree to forbid point－by－point insertion and generates leaf nodes of R－tree efficiently.R－tree structure is extended to present levels of detail（LOD）generation algorithm of point cloud models.Finally，a data organization approach is put forward for large－scale point cloud，which easily uses file mapping technique to accelerate data access.Experiments prove that this approach has fine space utilization and spatial query efficience with LOD representation capability and data cache mechanism，which lays a solid foundation for post－processing and comprehensive practices of large－scale point cloud data.

octree；3D R－tree；laser－scanning；point cloud；data management

GONG Jun（1978—），PhD，associate professor，majors in multi－dimension GIS and LiDAR.

GONG Jun，KE Shengnan，ZHU Qing，et al.An Efficient Management Method for Point Cloud Data Based on Octree and 3DR－tree［J］.Acta Geodaetica et Cartographica Sinica，2012，41（4）：597－604.（龔俊，柯勝男，朱慶，等.一種八叉樹和三維R樹集成的激光點(diǎn)云數(shù)據(jù)管理方法［J］.測(cè)繪學(xué)報(bào)，2012，41（4）：597－604.）

P208

A

1001－1595（2012）04－0597－08

國(guó)家自然科學(xué)基金（41001222）；國(guó)家973計(jì)劃（2010CB731801；2011CB302306）；國(guó)家863計(jì)劃（SS2012AA121001）；江西師范大學(xué)青年英才培育資助計(jì)劃；江西省教育廳科技項(xiàng)目（GJJ12188）

雷秀麗）

2011－04－11

2012－02－29

龔?。?978—），博士，副教授，從事多維地理信息系統(tǒng)和三維激光點(diǎn)云數(shù)據(jù)處理的理論與應(yīng)用研究。