王磊 郭清菊 姜晗
摘要:近年來利用三維激光掃描技術(shù)進(jìn)行的國(guó)內(nèi)各地城市數(shù)字化發(fā)展迅速,隨著硬件技術(shù)的升級(jí)和掃描范圍的逐漸擴(kuò)大,獲得的相應(yīng)的三維數(shù)據(jù)可達(dá)TB級(jí)。因此,如何合理的建立點(diǎn)云索引管理機(jī)制,是解決海量點(diǎn)云數(shù)據(jù)組織和管理的關(guān)鍵問題。本文首先對(duì)傳統(tǒng)八叉樹數(shù)據(jù)結(jié)構(gòu)的索引方法進(jìn)行了優(yōu)化,然后對(duì)三維點(diǎn)云分塊,建立八叉樹索引數(shù)據(jù)文件,同時(shí)用LOD方法對(duì)其進(jìn)行分層抽稀操作,通過建立改進(jìn)的八叉樹與LOD方法相結(jié)合的索引,來降低內(nèi)存的消耗、提高查詢的效率,最后根據(jù)屏幕顯示范圍與視角變化實(shí)時(shí)讀取釋放點(diǎn)云索引數(shù)據(jù),從而實(shí)現(xiàn)海量點(diǎn)云數(shù)據(jù)的可視化。
關(guān)鍵詞:海量點(diǎn)云;八叉樹索引;細(xì)節(jié)層次模型;可視化
中圖分類號(hào):000000 文獻(xiàn)標(biāo)識(shí)碼:A DOI:10.3969/j.issn.1003-6970.2016.04.026
0 引言
近年來,城市數(shù)字化工作在國(guó)內(nèi)各線城市中開展,在對(duì)城市的三維空間信息的采樣獲取過程中,逐漸實(shí)踐和總結(jié)出了多種快速有效的手段。其中,使用三維掃描技術(shù)對(duì)被測(cè)目標(biāo)采集真實(shí)空間坐標(biāo)數(shù)據(jù)的方法被廣泛采用并應(yīng)用到采集工作中,三維激光掃描技術(shù)所依托的軟件硬件在近些年來得到了迅速的發(fā)展,掃描目標(biāo)場(chǎng)景的不斷增大和場(chǎng)景復(fù)雜度的不斷升高,都對(duì)掃描設(shè)備的存儲(chǔ)量和掃描算法的運(yùn)算效率提出了挑戰(zhàn)。例如,廣泛裝備于汽車的激光掃描設(shè)備,其工作原理就是使用數(shù)個(gè)激光掃描器對(duì)三維點(diǎn)云數(shù)據(jù)進(jìn)行采集,最終獲取的掃描數(shù)據(jù)量接近TB級(jí),由此看來,處理數(shù)據(jù)的算法亟待優(yōu)化和改進(jìn)。為了更好的將采集到的海量點(diǎn)云數(shù)據(jù)應(yīng)用到三維重建與快速輔助生成地形圖等實(shí)際應(yīng)用中來,需要對(duì)海量點(diǎn)云數(shù)據(jù)的管理算法進(jìn)行不斷的優(yōu)化。在管理海量點(diǎn)云數(shù)據(jù)時(shí),最為常用的管理方法是利用索引管理點(diǎn)云數(shù)據(jù),索引的好壞直接關(guān)系到點(diǎn)云數(shù)據(jù)處理的效率,因此如何完善現(xiàn)有的索引算法,建立更高效的海量點(diǎn)云索引,是近幾年相關(guān)方向的研究重點(diǎn)之一。
目前,實(shí)現(xiàn)海量點(diǎn)云數(shù)據(jù)快速顯示的有效方法是構(gòu)建索引樹,常用的索引樹主要包括R樹、K-D樹、四叉樹和八叉樹等。其中,R樹具有較強(qiáng)的靈活性和調(diào)節(jié)性,但由于中間節(jié)點(diǎn)允許重疊,在查找速度、動(dòng)態(tài)操作性能方面仍存在一些不足;四叉樹和八叉樹結(jié)構(gòu)簡(jiǎn)單,對(duì)于精確匹配點(diǎn)的查找性能較高,但樹的動(dòng)態(tài)性較差,樹的平衡性不好,以至于影響點(diǎn)云顯示的交互性。針對(duì)上述問題,國(guó)內(nèi)外研究者相繼提出了一系列改進(jìn)的方法。Beckmmann等在R樹的基礎(chǔ)上提出了R*樹,相比于R樹,R*樹的優(yōu)越性體現(xiàn)在查找方式和節(jié)點(diǎn)操作的多樣性,并且它同時(shí)支持點(diǎn)和空間數(shù)據(jù)的索引,但是R*樹的索引構(gòu)建時(shí)間比R樹略高。支曉棟等提出的一種改進(jìn)四叉樹算法可以快速完成索引樹的構(gòu)建,但是該算法構(gòu)建的索引樹的樹高減小,降低了數(shù)據(jù)的查詢速度。
相較于傳統(tǒng)方法在處理點(diǎn)云數(shù)據(jù)時(shí),內(nèi)存占用率高,執(zhí)行效率低等問題,本文提出了一種新的方法,該方法以優(yōu)化后的八叉樹數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ),對(duì)可視化過程中需要的海量點(diǎn)云數(shù)據(jù)進(jìn)行有效的組織。由于本文對(duì)海量點(diǎn)云數(shù)據(jù)同時(shí)進(jìn)行八叉樹結(jié)構(gòu)的索引創(chuàng)建操作和LOD抽稀采樣操作,并對(duì)傳統(tǒng)的八叉樹數(shù)據(jù)結(jié)構(gòu)經(jīng)過了優(yōu)化,所以,在索引創(chuàng)建與檢索過程中,可以實(shí)時(shí)降低內(nèi)存的消耗、提高查詢效率。最終根據(jù)顯示范圍查找索引讀取對(duì)應(yīng)數(shù)據(jù)塊,從而實(shí)現(xiàn)海量的點(diǎn)云數(shù)據(jù)更加高效的可視化瀏覽。
1 改進(jìn)的八叉樹索引算法與LOD技術(shù)
1.1 改進(jìn)的八叉樹索引算法
八叉樹結(jié)構(gòu)是一種用來描述三維空間的數(shù)據(jù)結(jié)構(gòu),八叉樹中任一節(jié)點(diǎn)的子節(jié)點(diǎn)均為八個(gè),各節(jié)點(diǎn)分別指向下一個(gè)八叉樹節(jié)點(diǎn)。對(duì)一定的三維空間做基于三維坐標(biāo)軸方向的分割,可以得到相應(yīng)的八個(gè)小立方體,各小立方體被稱為體元,每個(gè)體元中存儲(chǔ)相應(yīng)的屬性數(shù)據(jù),這就是八叉樹結(jié)構(gòu)。通過對(duì)經(jīng)典八叉樹算法分析可知,如果將經(jīng)典八叉樹數(shù)據(jù)結(jié)構(gòu)直接應(yīng)用于海量點(diǎn)云數(shù)據(jù)的管理,其各節(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)上存在冗余,比如,為提高檢索速度,相鄰指針和父指針會(huì)被存儲(chǔ)在節(jié)點(diǎn)之間,但是相應(yīng)的內(nèi)存空間會(huì)增大。如圖1.1所示,指向父節(jié)點(diǎn)的指針我們?cè)谶@里使用m parent命名,相應(yīng)的,定義孩子節(jié)點(diǎn)指針為m_child,使用m_pointsNum保存數(shù)據(jù)塊ID,另外,m_points表示當(dāng)前指針。
雖然在設(shè)計(jì)時(shí)對(duì)八叉樹的結(jié)構(gòu)考慮的各方面都非常細(xì)致,但是在點(diǎn)云數(shù)據(jù)管理的應(yīng)用中其中的某些屬性信息并沒有保存的必要。為了降低程序在運(yùn)行時(shí)的內(nèi)存占用率,本文分以下幾步對(duì)八叉樹數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化:首先對(duì)以上的存儲(chǔ)結(jié)構(gòu)中的非必需字段進(jìn)行刪除,以釋放內(nèi)存容量,降低存儲(chǔ)冗余。比如可以將節(jié)點(diǎn)的父指針入棧,使用基于棧的相關(guān)操作方法來完成對(duì)其父節(jié)點(diǎn)指針的查找操作,因此各節(jié)點(diǎn)不需要為父節(jié)點(diǎn)指針作單獨(dú)的存儲(chǔ)。其次,優(yōu)化結(jié)構(gòu)以節(jié)省存儲(chǔ)空間。由于點(diǎn)云一般都是采集現(xiàn)實(shí)區(qū)域中的數(shù)據(jù),比如學(xué)校、村莊、高速公路等,因其地理位置的不定性,在采集空間數(shù)據(jù)時(shí),只有一部分區(qū)域會(huì)生成點(diǎn)云,相應(yīng)在進(jìn)行存儲(chǔ)時(shí)就會(huì)有很大的空閑空間。在存儲(chǔ)八叉樹的線性鏈表中,各節(jié)點(diǎn)是否有子節(jié)點(diǎn)直接決定了該節(jié)點(diǎn)是否需要進(jìn)行下一步分割處理?;诖?,可以定義一個(gè)指針指向所有的子樹。1個(gè)字節(jié)有8個(gè)比特,恰好對(duì)應(yīng)八個(gè)子節(jié)點(diǎn),即可以用每個(gè)比特作為標(biāo)識(shí),來表示當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)是否存在。
依據(jù)上文中的分析,優(yōu)化后的八叉樹數(shù)據(jù)結(jié)構(gòu)如圖1.2所示:
其中m_child指向了第一個(gè)孩子。m_allChilds表示孩子的狀態(tài),即依次標(biāo)示每個(gè)節(jié)點(diǎn)的8個(gè)孩子是否存在。顯而易見,相較于經(jīng)典的八叉樹,這樣的編碼方式在運(yùn)行時(shí)的內(nèi)存占用率有了很大降低。尤其在程序運(yùn)行時(shí),相應(yīng)索引的建立和檢索操作大大降低了內(nèi)存占用率,提高了執(zhí)行效率。
1.2 LOD可視化技術(shù)
這里提到的LOD技術(shù),其英文全稱為level ofdetails,簡(jiǎn)稱LOD,字面意思可以理解為“多層次(展現(xiàn))細(xì)節(jié)”技術(shù),在該技術(shù)的作用下,渲染資源會(huì)依據(jù)模型各區(qū)域的重要程度進(jìn)行重分配,從而對(duì)提高渲染效率。例如,視角靠近物體的時(shí)候,就選擇精細(xì)的、高分辨率的模型來進(jìn)行實(shí)時(shí)渲染,而當(dāng)視角遠(yuǎn)離的時(shí)候,就選擇低分辨率的、粗糙的模型來進(jìn)行渲染;根據(jù)視角的變化來實(shí)時(shí)地進(jìn)行顯示模型的切換,從而快速繪制顯示圖形、實(shí)現(xiàn)海量數(shù)據(jù)的實(shí)時(shí)交互。
經(jīng)典的基于規(guī)則格網(wǎng)構(gòu)建LOD模型的方法是Lindstrom等人提出的,基于視點(diǎn)的連續(xù)細(xì)節(jié)層次(Continuous LOD,簡(jiǎn)稱CLOD)算法。將一個(gè)正方體的點(diǎn)云區(qū)域均等分割成八個(gè)小正方體點(diǎn)云區(qū)域,而被分割出來的正方體均為要構(gòu)造的八叉樹的一個(gè)節(jié)點(diǎn),在這些節(jié)點(diǎn)中存有對(duì)應(yīng)區(qū)域的點(diǎn)云數(shù)據(jù),依據(jù)所掃描的區(qū)域的具體情況,越復(fù)雜的點(diǎn)云所分割的精細(xì)度就更大,從而得到的精確度就更高。本文基于該方法,自頂向下遞歸地對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行劃分,并建立了對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu),同時(shí),根據(jù)屏幕顯示的覆蓋范圍,決定什么時(shí)候、加載哪些節(jié)點(diǎn)存儲(chǔ)的點(diǎn)云數(shù)據(jù),來進(jìn)行LOD模型的動(dòng)態(tài)更新。
本文根據(jù)LOD算法的基本思想,使用八叉樹數(shù)據(jù)結(jié)構(gòu)對(duì)該模型分層重構(gòu)。首先根據(jù)原始點(diǎn)云數(shù)據(jù)量的大小,得到原始數(shù)據(jù)的范圍,即Xmin,Xmax,Ymin,Ymax,Zmin,Zmax,根據(jù)總體數(shù)據(jù)的Zmax、Zmin與實(shí)際需要來確定分割深度N。然后,依據(jù)本文提出的改進(jìn)的八叉樹方法對(duì)獲得的數(shù)據(jù)進(jìn)行點(diǎn)云分塊,這種分塊操作的順序是自頂向下的。如,首先對(duì)第N層深度的點(diǎn)云進(jìn)行等間距抽稀,每隔2N個(gè)點(diǎn)進(jìn)行采樣,生成的數(shù)據(jù)使用八叉樹結(jié)構(gòu)存儲(chǔ),作為第N層的節(jié)點(diǎn),存儲(chǔ)到八叉樹結(jié)構(gòu)中去;然后繼續(xù)對(duì)N-l層的點(diǎn)云數(shù)據(jù)采用相同處理,此時(shí)抽稀間距為2N-l,并排除掉已經(jīng)在八叉樹中存儲(chǔ)的(即抽稀間距為2N的點(diǎn)云數(shù)據(jù)),這些作為八叉樹的第N-1層的節(jié)點(diǎn),存儲(chǔ)到八叉樹結(jié)構(gòu)中去,持續(xù)分割,直到N=1,當(dāng)N=1時(shí),不再需要抽稀,直接將該區(qū)域范圍內(nèi)未存儲(chǔ)到八叉樹結(jié)構(gòu)中的點(diǎn)存儲(chǔ)到該層對(duì)應(yīng)節(jié)點(diǎn)即可。
至此,數(shù)據(jù)索引構(gòu)建完成。在瀏覽的過程中,根據(jù)當(dāng)前視角的坐標(biāo)來計(jì)算需要顯示的點(diǎn)云塊的范圍,根據(jù)視角遠(yuǎn)近比例來計(jì)算顯示深度,即可在保證運(yùn)行效率的前提下實(shí)現(xiàn)動(dòng)態(tài)的點(diǎn)云渲染。
2 實(shí)驗(yàn)與分析
本文利用c++與vtk實(shí)現(xiàn)了海量點(diǎn)云數(shù)據(jù)的索引快速建立與動(dòng)態(tài)調(diào)度,并實(shí)現(xiàn)了渲染與繪制,實(shí)驗(yàn)數(shù)據(jù)為某地區(qū)的點(diǎn)云掃描數(shù)據(jù),實(shí)驗(yàn)環(huán)境為intel corei7處理器,8G內(nèi)存。
如圖2.1與圖2.2中所示為實(shí)驗(yàn)過程中海量激光點(diǎn)云數(shù)據(jù)的實(shí)現(xiàn)效果。表2.1將本文方法與傳統(tǒng)構(gòu)建八叉樹索引處理方式進(jìn)行了比較。對(duì)于兩種方法對(duì)同一組點(diǎn)云數(shù)據(jù),在海量數(shù)據(jù)索引的構(gòu)建、內(nèi)存占用情況、節(jié)點(diǎn)存儲(chǔ)文件大小等數(shù)據(jù)信息做了對(duì)比與分析。
經(jīng)過對(duì)表2.1中的數(shù)據(jù)進(jìn)行分析我們可以得到,使用本文中的算法對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行處理時(shí),所消耗的時(shí)間和點(diǎn)云的體積是有著類似線性相關(guān)性的。傳統(tǒng)方法對(duì)點(diǎn)云數(shù)據(jù)的處理步驟為:先對(duì)原始點(diǎn)云做八叉樹分塊處理,再進(jìn)行LOD抽稀,即分層抽稀操作需要等到前一步(分塊處理)完成后再進(jìn)行,而本文中提到的算法思想為:對(duì)點(diǎn)云數(shù)據(jù)的分塊操作與LOD抽稀同時(shí)進(jìn)行,所以本方法在生成索引文件的過程中所消耗的時(shí)間與傳統(tǒng)方法相比要短得多,并且,為了降低八叉樹索引操作在運(yùn)行時(shí)的內(nèi)存消耗,本文還對(duì)傳統(tǒng)的八叉樹數(shù)據(jù)結(jié)構(gòu)進(jìn)行了優(yōu)化。另外,本文方法的最大優(yōu)勢(shì),就是在創(chuàng)建索引時(shí),就通過抽稀分層實(shí)現(xiàn)了LOD算法,因此在實(shí)時(shí)瀏覽時(shí),直接調(diào)用八叉樹,即實(shí)現(xiàn)了LOD算法,不需要在顯示時(shí)二次構(gòu)建渲染分層模型,節(jié)省了大量?jī)?nèi)存。
實(shí)驗(yàn)數(shù)據(jù)表明:本文方法較傳統(tǒng)方法相比更適合應(yīng)用于海量點(diǎn)云數(shù)據(jù)的實(shí)時(shí)呈現(xiàn)。本文對(duì)傳統(tǒng)的八叉樹的數(shù)據(jù)結(jié)構(gòu)進(jìn)行了優(yōu)化,使其在對(duì)點(diǎn)云數(shù)據(jù)的處理中有著更高的運(yùn)行效率。改進(jìn)后的方法首先對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行索引分塊,在對(duì)數(shù)據(jù)進(jìn)行LOD抽稀的同時(shí),使用優(yōu)化后的八叉樹數(shù)據(jù)結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)管理,節(jié)省了存儲(chǔ)空間,降低了內(nèi)存占用率。
3 結(jié)語
綜上,本文提出的對(duì)點(diǎn)云數(shù)據(jù)的處理方法相較于經(jīng)典算法在執(zhí)行渲染操作時(shí),顯示效率更高,更能滿足實(shí)際海量點(diǎn)云數(shù)據(jù)可視化的需求。通過對(duì)比數(shù)據(jù)表明,本文的算法是值得進(jìn)一步研究與應(yīng)用的。此外,為了提高點(diǎn)云渲染效率,需要進(jìn)一步研究如何與GPU渲染方法相結(jié)合,從而取得更好的顯示效果。