基于實(shí)體模型索引的海量激光點(diǎn)云分塊存儲研究與應(yīng)用

宋　楊,李長輝,宋　爽

(1.廣州市城市規(guī)劃勘測設(shè)計研究院,廣東 廣州 510060;2.武漢大學(xué) 測繪遙感信息工程國家重點(diǎn)實(shí)驗(yàn)室,湖北 武漢 430079)

?

基于實(shí)體模型索引的海量激光點(diǎn)云分塊存儲研究與應(yīng)用

宋楊1,李長輝1,宋爽2

(1.廣州市城市規(guī)劃勘測設(shè)計研究院,廣東 廣州 510060;2.武漢大學(xué) 測繪遙感信息工程國家重點(diǎn)實(shí)驗(yàn)室,湖北 武漢 430079)

摘要：三維激光掃描技術(shù)的日益進(jìn)步推動了點(diǎn)云數(shù)據(jù)量級的不斷攀升，給海量點(diǎn)云的高效管理及優(yōu)化處理帶來新的挑戰(zhàn)。文中針對在大范圍點(diǎn)云場景中快速調(diào)度局部詳細(xì)點(diǎn)云的實(shí)際應(yīng)用需求,借鑒空間格網(wǎng)結(jié)構(gòu)的數(shù)據(jù)組織思路，優(yōu)化并提出可變長度的海量點(diǎn)云分層分條帶存儲的工作機(jī)制，結(jié)合數(shù)據(jù)庫管理,實(shí)現(xiàn)了基于實(shí)體模型索引的激光點(diǎn)云及三維模型的快速調(diào)度及聯(lián)動顯示?；谘邪l(fā)的點(diǎn)云專家科研系統(tǒng)實(shí)踐，推動了海量點(diǎn)云數(shù)據(jù)集約化管理水平，具有一定的科研及實(shí)用價值。

關(guān)鍵詞：點(diǎn)云；分層分塊；實(shí)體模型；快速調(diào)度；空間格網(wǎng)

三維激光掃描技術(shù)是一種新興的數(shù)據(jù)采集技術(shù),起源于20世紀(jì)80年代,經(jīng)過近10年飛速發(fā)展已經(jīng)在電力、公路、地形圖測繪、古建筑保護(hù)、工業(yè)制造等廣泛的行業(yè)領(lǐng)域都得到應(yīng)用。隨著三維激光掃描技術(shù)的日臻成熟,其有效掃描距離、精度和分辨率的不斷提高,所獲取的三維激光點(diǎn)云數(shù)據(jù)量也極具增大。如何高效存儲、管理、顯示及分析海量點(diǎn)云數(shù)據(jù)，對其進(jìn)行特征提取、場景分割、模式識別及三維重構(gòu)存在諸多技術(shù)瓶頸有待突破。

索引機(jī)制的建立可實(shí)現(xiàn)將空間散亂分布的海量點(diǎn)云數(shù)據(jù)進(jìn)行結(jié)構(gòu)化的管理，也是點(diǎn)云數(shù)據(jù)優(yōu)化處理中的有效措施，目前流行的點(diǎn)云索引方式包括八叉樹結(jié)構(gòu)、 空間格網(wǎng)結(jié)構(gòu)；存儲方法包括基于外存文件、數(shù)據(jù)庫、以及云存儲等模式。本文針對古建筑三維激光掃描測量形成的海量點(diǎn)云數(shù)據(jù)的集約化管理及快速調(diào)度的應(yīng)用需求，借鑒并優(yōu)化空間格網(wǎng)結(jié)構(gòu)的思路，建立了海量激光點(diǎn)云分層、變長分塊存儲工作機(jī)制，結(jié)合數(shù)據(jù)庫的索引表，實(shí)現(xiàn)了對目標(biāo)對象三維激光點(diǎn)云及三維模型的快速調(diào)度及聯(lián)動顯示。

1海量激光點(diǎn)云分層分塊存儲機(jī)制

1.1八叉樹結(jié)構(gòu)及空間格網(wǎng)結(jié)構(gòu)

目前，代表性的點(diǎn)云數(shù)據(jù)索引方式八叉樹結(jié)構(gòu)和空間格網(wǎng)結(jié)構(gòu)的適用性包括：

1)八叉樹結(jié)構(gòu)：適合大型場景的漫游、多分辨率模型LOD動態(tài)調(diào)度；適合點(diǎn)云大場景漫游、宏觀展示。八叉樹索引通常只保留數(shù)據(jù)地址而數(shù)據(jù)本身仍是混雜的，非結(jié)構(gòu)化的，因此在數(shù)據(jù)讀取過程中文件指針需不停地跳轉(zhuǎn)，對于海量點(diǎn)云數(shù)據(jù)，磁盤跳轉(zhuǎn)尋道的時間開銷將大大降低數(shù)據(jù)訪問的效率。

2)空間格網(wǎng)結(jié)構(gòu)：適合點(diǎn)云小場景的顯示和快速加載，與數(shù)據(jù)本身無序的八叉樹結(jié)構(gòu)相比，空間格網(wǎng)結(jié)構(gòu)對網(wǎng)格化劃分的過程中完成了數(shù)據(jù)的結(jié)構(gòu)化整理，更利于點(diǎn)云數(shù)據(jù)庫擴(kuò)充或多時相點(diǎn)云數(shù)據(jù)的疊加。

1.2基于點(diǎn)云分層分塊的索引存儲

對于從大范圍場景的點(diǎn)云數(shù)據(jù)中提取、顯示其中某一局部區(qū)域點(diǎn)云，為滿足細(xì)部點(diǎn)云查看形象性及準(zhǔn)確性要求,要求點(diǎn)云分塊需具備較小的粒度。常規(guī)的空間格網(wǎng)結(jié)構(gòu)存儲機(jī)制將點(diǎn)云規(guī)則大小分塊，并直接將分塊點(diǎn)云存儲在一個個文件中,勢必產(chǎn)生大量分散的分塊文件，極大降低了點(diǎn)云數(shù)據(jù)索引的效率。以一組文件大小為116 G的點(diǎn)云實(shí)驗(yàn),其數(shù)據(jù)空間體積約為65 370 m3,如按1 m×1 m×1 m的空間格網(wǎng)分塊，將產(chǎn)生65 000余個分塊文件,每個文件大小介于1～2 048 MB之間。由于分塊文件數(shù)量巨大，尤其當(dāng)涉及多個分塊文件需要同時讀取時，磁頭跳轉(zhuǎn)到MFT主文件表再跳轉(zhuǎn)回對應(yīng)分塊文件所產(chǎn)生的時間開銷將是不容忽視的。

圖1　點(diǎn)云塊分割

為避免基于大量分塊文件進(jìn)行點(diǎn)云數(shù)據(jù)索引而產(chǎn)生的性能損失，本文研究提出：對點(diǎn)云數(shù)據(jù)整體首先按點(diǎn)云數(shù)據(jù)的高程信息進(jìn)行分層，并將分層結(jié)果存儲于不同文件，每個分層文件內(nèi)部再按條帶劃分。如圖1所示，對一個點(diǎn)云區(qū)域按照如0.1 m的高程間隔、1 m的北方向間隔分割為點(diǎn)云條塊，將每一個點(diǎn)云條塊存儲為一個二進(jìn)制文件，并將其條塊索引寫入SQL數(shù)據(jù)庫。

如圖2所示,每個分層文件內(nèi)部的點(diǎn)云空間劃分為寬高一定的立方條帶，一般選擇點(diǎn)云覆蓋區(qū)域的短邊作為條帶方向的，以避免條帶內(nèi)包含過多數(shù)據(jù)分塊。當(dāng)點(diǎn)云區(qū)域范圍較大時，也可采用整體分塊的方法，對現(xiàn)有點(diǎn)云條帶按其垂直方向拆分如圖2所示的虛線分割區(qū)域A和B，是否分割與分割數(shù)量的多少與點(diǎn)云區(qū)域?qū)挾?、點(diǎn)云密度、機(jī)器性能均有關(guān)，可根據(jù)實(shí)際情況調(diào)節(jié)，實(shí)現(xiàn)由整體到局部，分層分塊的點(diǎn)云存儲機(jī)制。

圖2　分層分塊的點(diǎn)云存儲機(jī)制

本文算法選擇按“條帶”存儲的而不采用傳統(tǒng)的規(guī)則單元網(wǎng)格存儲的一個重要原因在于,“條帶”相當(dāng)于可變分塊，更有利于多時相點(diǎn)云數(shù)據(jù)的疊加與查詢。如圖3所示,黃色部分為部分更新的點(diǎn)云數(shù)據(jù),條帶存儲優(yōu)勢在于可靈活的切割和組合多時相的數(shù)據(jù),一定程度上減小了數(shù)據(jù)融合產(chǎn)生的空隙,這也是八叉樹結(jié)構(gòu)存儲方式所無法比擬的。

圖3　多時相點(diǎn)云數(shù)據(jù)融合

經(jīng)過條塊處理后的點(diǎn)云分塊，利用兩個表存儲其索引信息，以實(shí)現(xiàn)數(shù)據(jù)庫有序管理,需要存儲于數(shù)據(jù)表內(nèi)的信息包括時相庫信息與分塊信息，如表1、表2所示。

表1　PCDDATE表結(jié)構(gòu)

表2　PCDINDEX表結(jié)構(gòu)

2基于實(shí)體模型索引的點(diǎn)云調(diào)度

基于海量激光點(diǎn)云分層分塊存儲機(jī)制以及索引信息的表格化管理，已實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)庫的構(gòu)建。應(yīng)用程序直接向點(diǎn)云數(shù)據(jù)庫管理系統(tǒng)發(fā)送包含坐標(biāo)范圍、時相標(biāo)記和最大點(diǎn)云上限信息的請求并接受經(jīng)過抽稀處理的點(diǎn)云顯示在窗口中，以完成面向?qū)嶓w對象的點(diǎn)云數(shù)據(jù)的快速讀取及調(diào)度，具體調(diào)度過程如圖4所示。

圖4　點(diǎn)云數(shù)據(jù)庫管理系統(tǒng)工作示意圖

點(diǎn)云數(shù)據(jù)庫管理系統(tǒng)接收到應(yīng)用程序請求的坐標(biāo)范圍與允許最大點(diǎn)云數(shù)量，以坐標(biāo)范圍和勾選的時相庫為查詢條件從索引數(shù)據(jù)庫中提取分塊信息，經(jīng)過時相分塊融合、調(diào)整，從分塊指向的數(shù)據(jù)塊地址從點(diǎn)云數(shù)據(jù)庫中提取坐標(biāo)數(shù)據(jù)。在此過程中，應(yīng)用動態(tài)抽稀技術(shù)，即在讀取過程中判斷數(shù)據(jù)大小，壓縮已讀入的數(shù)據(jù)并根據(jù)新的抽稀級別繼續(xù)讀取。最后，點(diǎn)云數(shù)據(jù)庫管理系統(tǒng)負(fù)責(zé)將抽稀后的坐標(biāo)數(shù)組與實(shí)際使用的抽稀級別返回給調(diào)用程序。

以三維激光掃描技術(shù)應(yīng)用于古建筑園林?jǐn)?shù)字保護(hù)領(lǐng)域?yàn)槔紥呙璧狞c(diǎn)云是最重要的數(shù)字記憶檔案成果，除此之外其它成果形式還包括如圖5所示的基于點(diǎn)云測制的古建筑現(xiàn)狀測繪圖，以及圖6所示的在古建筑現(xiàn)狀測繪圖上進(jìn)一步制作的具有可量測精度的三維實(shí)體模型。與一般三維仿真模型不同,圖5所示的古建筑三維模型與其對應(yīng)的三維激光掃描點(diǎn)云配準(zhǔn)于同一坐標(biāo)系下,并且模型經(jīng)過了粒度細(xì)化處理，模型的每個部件為一個獨(dú)立對象Object，有助于分部件的數(shù)據(jù)調(diào)度分析以及古建筑結(jié)構(gòu)的拆分模擬、查看。

圖5　古建筑現(xiàn)狀測繪圖

圖6　實(shí)體模型

本文研究基于Qt及OpenGL開發(fā)“古建筑園林三維激光專家科研系統(tǒng)”，在模型視圖中用戶可以選擇一組模型部件，根據(jù)選擇部件的包圍盒的坐標(biāo)，在表1 PCDINDEX塊索引數(shù)據(jù)表中檢索到對應(yīng)點(diǎn)云所在的點(diǎn)文件，根據(jù)表中記錄的起始偏移量OFFSET快速找到點(diǎn)云，并在點(diǎn)云視圖中加載顯示,如圖7所示。

圖7　基于實(shí)體模型索引快速調(diào)度點(diǎn)云

3實(shí)驗(yàn)與結(jié)論

本文研究基于上述海量激光點(diǎn)云分塊存儲及實(shí)體模型索引，自主研發(fā)了“古建筑園林三維激光專家科研系統(tǒng)”，實(shí)現(xiàn)海量點(diǎn)云數(shù)據(jù)的有序管理與快速調(diào)度。系統(tǒng)在Qt 4.8.4(MinGW)編譯環(huán)境下結(jié)合OpenGL研發(fā)實(shí)現(xiàn)，主要硬件配置條件為Intel Core2 P8600 2.40 GHz CPU,4 G內(nèi)存,500 GB機(jī)械硬盤,Nvidia Quadro NVS 160 M顯卡。

實(shí)驗(yàn)點(diǎn)云數(shù)據(jù)由奧地利RIEGL VZ-400長距離脈沖式激光掃描儀采集，掃描對象為廣東清代四大名園之一的東莞市可園博物館古建筑群。掃描面積約2 200 m2，掃描設(shè)站738個，利用GDCORS-RTK布設(shè)控制點(diǎn)11個、測量站心點(diǎn)135個和特征點(diǎn)216個。入庫點(diǎn)云總點(diǎn)數(shù)為52億，總?cè)萘繛?16 G。

隨機(jī)選擇了10組基于實(shí)體模型的點(diǎn)云數(shù)據(jù)樣本，進(jìn)行快速調(diào)度的效率測試，測試結(jié)果如表3所示。

表3　點(diǎn)云調(diào)度效率測試結(jié)果

根據(jù)表3測試結(jié)果，本文提出的基于實(shí)體模型索引的海量激光點(diǎn)云分塊存儲工作機(jī)制在所研發(fā)的“古建筑園林三維激光專家科研系統(tǒng)”的點(diǎn)云調(diào)度中具有良好表現(xiàn)，其簡潔的數(shù)據(jù)結(jié)構(gòu)有助于點(diǎn)云調(diào)度時省去了構(gòu)建復(fù)雜搜索樹的過程，尤其對于小范圍、高密度的點(diǎn)云調(diào)度任務(wù)表現(xiàn)極佳。

三維激光掃描技術(shù)的日益進(jìn)步帶動了點(diǎn)云數(shù)據(jù)量級的不斷攀升，也給點(diǎn)云數(shù)據(jù)管理及優(yōu)化處理不斷帶來新的挑戰(zhàn)。本文研究提出了針對海量激光點(diǎn)云數(shù)據(jù)的分層存儲與塊索引的數(shù)據(jù)庫管理方法，基于研發(fā)的點(diǎn)云專家科研系統(tǒng)的實(shí)踐，推動了古建筑園林海量點(diǎn)云數(shù)據(jù)集約化管理水平，具有一定的科研及實(shí)用價值。

參考文獻(xiàn)：

[1]張毅,閆利.地面激光點(diǎn)云強(qiáng)度噪聲的三維擴(kuò)散濾波方法[J].測繪學(xué)報,2013,42(4):568-580.

[2]王晏民，郭明.大規(guī)模點(diǎn)云數(shù)據(jù)的二維與三維混合索引方法[J].測繪學(xué)報,2012,41(4):605-612.

[3]龔俊，柯勝男，朱慶，等.一種八叉樹和三維R樹集成的激光點(diǎn)云數(shù)據(jù)管理方法[J].測繪學(xué)報,2012,41(4):597-604.

[4]龔俊，朱慶，張葉廷，等.顧及多細(xì)節(jié)層次的三維樹索引擴(kuò)展方法[J].測繪學(xué)報,2011,40(2):249-255.

[5]吳靜，靳奉祥，王健.基于三維激光掃描數(shù)據(jù)的建筑物三維建模[J].測繪工程，2007，16(10)：57-60.

[6]劉旭春，丁延輝.三維激光掃描技術(shù)在古建筑保護(hù)中的應(yīng)用[J].測繪工程，2006，15(1):48-49.

[7]張芯，李廣云，王力，等.基于HDFS的海量激光點(diǎn)云數(shù)據(jù)分塊存儲方法研究[J].測繪通報,2014(3):21-24.

[8]曹啟華，鄧雪清.基于金字塔模型的規(guī)則格網(wǎng)數(shù)據(jù)可視化交互編輯[J].測繪科學(xué)技術(shù)學(xué)報,2007,24(6):427-431.

[9]張巧英,陳浩,朱爽.密度聚類算法在連續(xù)分布點(diǎn)云去噪中的應(yīng)用[J].地理空間信息,2011,9(6):101-104.

[10] 曹彤，劉臻.用于建立三維的八叉樹編碼壓縮算法[J].中國圖象圖形學(xué)報,2002,7(1):50-54.

[11] 路明月，何永健.三維海量點(diǎn)云數(shù)據(jù)的組織與索引方法[J].地球信息科學(xué),2008,10(2):190-194.

[12] 謝洪，吳博義，趙展.一種新的海量點(diǎn)云數(shù)據(jù)管理方法研究[J].遙感信息,2013,28(6):26-32．

[責(zé)任編輯：劉文霞]

On the big data laser point cloud block storage based on object model index

SONG Yang1，LI Changhui1,SONG Shuang2

(1.Guangzhou Urban Planning Design and Survey Research Institute，Guangzhou 510060,China;2.State Key Laboratory of Information Engineering in Surveying,Mapping and Remote Sensing,Wuhan University,Wuhan 430079,China)

Abstract：Three-dimensional laser scanning technology has become more progressive,bringing new challenges to efficiently handle massive point cloud.In this paper,how to quickly dispatch point cloud from the big scene,by referencing the idea of space grid structure,it proposes a massive point cloud stratification variable length,slitting tape storage mechanism,achieving a rapid scheduling model based on entity indexes laser point clouds and three-dimensional model.

Key words：point cloud；layered；object model；quick dispatch；space grid

中圖分類號：TP391.41

文獻(xiàn)標(biāo)識碼：A

文章編號：1006-7949(2016)04-0007-04

作者簡介：宋楊(1979-),女，高級工程師，注冊測繪師，博士.

基金項(xiàng)目：廣州市測繪與地理信息重點(diǎn)工程技術(shù)研究開發(fā)中心(11G0041)

收稿日期：2015-03-13;修回日期：2015-04-21