趙爾平，劉 煒，黨紅恩

(西藏民族大學(xué) 信息工程學(xué)院，陜西 咸陽 712082)(*通信作者電子郵箱xdzep@163.com)

0 引言

真實旅游總會涉及體力運動、昂貴花費、煩心事情及危險[1]，虛擬旅游可以避免這些情況發(fā)生，人們足不出戶就能漫游、沉浸和體驗世界各地風(fēng)景名勝，近年在國內(nèi)外逐漸興起。三維激光掃描技術(shù)作為一項成熟技術(shù)在很多領(lǐng)域被廣泛應(yīng)用，能夠快速采集復(fù)雜、大型物體外表面數(shù)據(jù)，這些數(shù)據(jù)是由離散矢量距離點構(gòu)成，俗稱點云數(shù)據(jù)。點云數(shù)據(jù)實現(xiàn)物體重建是當(dāng)前應(yīng)用研究熱點，并被廣泛應(yīng)用于建筑設(shè)計、虛擬旅游、城市規(guī)劃、事故監(jiān)測等領(lǐng)域[2]。虛擬旅游建模大都采用三維激光掃描儀采集不同場景表面大量密集點的三維坐標(biāo)、激光反射強度、法線和顏色等信息，然后利用軟件把它們重建為3D點云模型。旅游景點空間都比較大，而且一次大范圍掃描運動產(chǎn)生出數(shù)十億點樣[3]，一個景點3D點云模型頂點數(shù)目一般可達百億到萬億數(shù)量級，海量點云數(shù)據(jù)空間索引與壓縮已成為大數(shù)據(jù)時代一個研究熱點。

隨著三維激光掃描技術(shù)在虛擬旅游、數(shù)字城市、地理信息系統(tǒng)領(lǐng)域廣泛應(yīng)用，海量點云大數(shù)據(jù)日益成倍增長，對其壓縮變得越來越重要，壓縮可以從源頭減少數(shù)據(jù)總量，緩解系統(tǒng)資源瓶頸。雖然網(wǎng)格模型三維數(shù)據(jù)壓縮技術(shù)已經(jīng)比較成熟，但是3D點云模型數(shù)據(jù)壓縮卻是一個新研究領(lǐng)域，多數(shù)網(wǎng)格模型壓縮算法不能直接用于點云數(shù)據(jù)壓縮，然而一些壓縮思想已被點云模型借鑒，例如平面抽取方法是從3D點云模型中檢測并抽取若干平面，將屬于某個平面的所有點按顏色相近劃分若干群，然后提取每個群邊界點構(gòu)成凸殼，對凸殼進行德洛涅三角剖分，這些三角形中的點及顏色信息被最終保留[4]。Smith等[5]用移動立方體算法重構(gòu)八叉樹節(jié)點曲面，通過把低曲率面或扁平面冗余點進行修剪來壓縮八叉樹，其余重構(gòu)面利用三角形三個點到子節(jié)點曲面的距離進行編碼來進一步壓縮八叉樹節(jié)點重構(gòu)面數(shù)據(jù)，文獻[4-5]都借鑒了網(wǎng)格模型壓縮思想，把點云數(shù)據(jù)形成的曲面進行剖分、重構(gòu)后刪除冗余點，壓縮剩余點信息，它們都是有損壓縮方法，它們在構(gòu)建點云模型拓撲結(jié)構(gòu)時增加額外開銷。文獻[6]利用八叉樹迭代劃分物體點云空間，每一層節(jié)點位置信息用所有子節(jié)點位置幾何中心近似表示，節(jié)點的屬性(法線和顏色)信息用子節(jié)點屬性的平均值近似表示，該方法是一個無損漸進壓縮方法。文獻[7]根據(jù)特征分布把八叉樹分成三個部分，每個部分按初始預(yù)給的概率模型進行獨立壓縮。Cohen等[8]利用八叉樹按預(yù)設(shè)最小分辨率來劃分點云模型，利用圖像和視頻編碼技術(shù)的3D塊預(yù)測和變換編碼壓縮點云屬性方法。把點云數(shù)據(jù)三維坐標(biāo)轉(zhuǎn)化成莫頓碼表示，計算相鄰點莫頓碼差值，對差值取以8為底對數(shù)來近似表示點坐標(biāo)，直接減少莫頓碼長度實現(xiàn)壓縮[9]。Song等[10]采用最小二乘法的曲率估計算法計算八叉樹模型中所有點曲率，如果某個點曲率變化小于閾值則刪除相鄰某點,達到數(shù)據(jù)壓縮目的，但是八叉樹迭代造成其中間層數(shù)據(jù)冗余，壓縮率有限，不適合大規(guī)模虛擬旅游點云數(shù)據(jù)壓縮。R樹索引的3D點云數(shù)據(jù)壓縮中間層不存在數(shù)據(jù)冗余，已有研究成果較少。Chovanec等[11]提出R樹索引的可變長編碼(Variable-Length Codes， VLC)無損壓縮方法，對點的坐標(biāo)和屬性數(shù)據(jù)采用可變長編碼壓縮，但是VLC不適合大規(guī)模數(shù)據(jù)壓縮。數(shù)據(jù)規(guī)模變大查詢性能會大幅度降低，空間索引是解決它的有效途徑。

R樹是支持范圍查詢的多維空間索引結(jié)構(gòu)，它的每個節(jié)點獨占一個磁盤頁面[12]，其中非葉節(jié)點索引記錄為：(MBR, Child-Pointer)，葉節(jié)點索引記錄為：(MBR, tuple-identifier)，MBR是節(jié)點擁有點數(shù)據(jù)的最小外接矩形(可擴展到高維空間)，Child-Pointer為指向孩子指針，tuple-identifier是空間對象標(biāo)識。除根節(jié)點外每個節(jié)點最大索引記錄個數(shù)稱扇出(fan)。R樹在對數(shù)級時間復(fù)雜度內(nèi)支持窗域、鄰域和最近鄰域等的范圍查詢[13]，但是不能支持按點查詢，因為R樹僅維護多維數(shù)據(jù)邊界框和指向?qū)嶋H數(shù)據(jù)的指針[14]。它是B樹在多維空間擴展的高度平衡樹，是基于空間區(qū)域匹配原理向下逐層搜索，最終獲取葉節(jié)點外接立方體包圍的空間對象，且被廣泛應(yīng)用于空間索引。

聚類排序R樹(Clustered Sorting R-Tree， CSR-Tree)[15]和R樹森林(R-Tree Forests， R-Forests)[16]都是基于不同方法在R樹上改進的索引結(jié)構(gòu)，目的是解決R樹兄弟節(jié)點空間區(qū)域重疊造成多路查詢問題，但是這兩種索引結(jié)構(gòu)更新、刪除操作空間代價太高。基于維諾圖R樹(Voronoi diagrams R-Tree， VoR-Tree)[17]索引結(jié)構(gòu)首先預(yù)構(gòu)空間數(shù)據(jù)維諾圖，R樹每個葉節(jié)點存儲這些維諾圖，并存儲該維諾圖最近鄰居指針，縮短最近鄰域搜索時間，基于哈希索引R樹(Perfect Hash base R-tree， PHR-Tree)[18]把兩級哈希表集成到R樹每個節(jié)點上，并為節(jié)點內(nèi)部的點建立哈希索引，PHR-Tree既能按范圍索引又能按點查詢。不管是通過維諾圖實現(xiàn)最近鄰域搜索還是兩級哈希表實現(xiàn)點云查詢，由于輔助索引結(jié)構(gòu)空間復(fù)雜度太高不適合海量點云數(shù)據(jù)。三維R樹(3 Dimensional R-Tree， 3DRTree)[19]和空間數(shù)據(jù)多尺度R-Tree(Spatial Data Multi-scale R-Tree, SDMR)[20]利用R樹不同層實現(xiàn)空間對象細節(jié)層次(Level Of Detail， LOD)索引，它們都缺乏數(shù)據(jù)冗余控制。

綜上所述，八叉樹管理的3D點云數(shù)據(jù)壓縮雖然都是漸進壓縮算法，但是在樹的中間層形成不同分辨率的大量數(shù)據(jù)冗余，給本來海量的點云數(shù)據(jù)雪上加霜；大部分基于八叉樹壓縮方法都是有損壓縮，對壓縮率方面考慮較多，對數(shù)據(jù)精度與查詢效率方面考慮較少；以上各種在R樹基礎(chǔ)上改進的索引結(jié)構(gòu)由于自身或輔助索引結(jié)構(gòu)復(fù)雜，數(shù)據(jù)精度損失過大，缺乏有效控制數(shù)據(jù)冗余，都不適合在無拓結(jié)構(gòu)、離散、高精度、海量虛擬旅游3D數(shù)據(jù)中應(yīng)用。本文針對虛擬旅游3D點云數(shù)據(jù)龐大特征和虛擬漫游特點提出R樹管理的3D點云數(shù)據(jù)壓縮與索引技術(shù)，即鄰點數(shù)據(jù)差值漸進壓縮方法和基于裁剪重疊區(qū)域進行冗余處理的R樹空間索引技術(shù)。塊內(nèi)保存相鄰點差值，以塊為單位漸進壓縮，從而實現(xiàn)流式傳輸，本次查詢借助上次查詢位置及區(qū)域直接從該區(qū)域邊界開始在R樹葉節(jié)點搜索，這樣處理減少了數(shù)據(jù)源端輸出數(shù)據(jù)總量和查詢時間，再加之流式傳輸方式能夠緩解虛擬漫游網(wǎng)絡(luò)帶寬壓力。

1 點云數(shù)據(jù)壓縮

1.1 3D模型空間剖分及點云數(shù)據(jù)除噪

3D模型中的點云噪聲點是由于激光掃描儀在掃描過程中由于外界因素或在三維重建過程中造成少量稀疏離散點。噪聲點之間距離或與非噪聲點之間距離比較大，造成數(shù)據(jù)空間范圍虛大，容易造成壓縮結(jié)果失真和R樹兄弟節(jié)點重疊，所以點云數(shù)據(jù)壓縮前要清洗噪聲點，使得R樹葉節(jié)點包圍盒邊界較規(guī)整，點數(shù)據(jù)分布較均勻、密集，壓縮率與精度較高，降低空間區(qū)域重疊概率。歐氏距離是歐氏空間中兩點之間距離[21]，在八叉樹葉節(jié)點局部空間利用點與其相鄰各點歐氏距離期望值大于閾值δ的方法除噪,閾值δ是指立方體內(nèi)所有點之間距離的均值，用八叉樹葉節(jié)點立方體邊長除以它所包含的點云總數(shù)計算，由于外包立方體可以用左上角(Xmin，Ymin，Zmin)和右下角(Xmax，Ymax，Zmax)坐標(biāo)表示，δ值計算公式為：

δ=(Xmax-Xmin+Ymax-Ymin+Zmax-Zmin)/(3w)

(1)

其中：w表示外包立方體管理點云個數(shù)。點與其相鄰點歐氏距離及期望值計算公式為：

(2)

(3)

為了避免R樹兄弟節(jié)點空間區(qū)域重疊，引入八叉樹對虛擬旅游模型進行空間剖分，八叉樹剖分優(yōu)勢在于其快速收斂性，剖分結(jié)束條件為八叉樹葉節(jié)點點云個數(shù)不大于R樹葉節(jié)點管理的點云個數(shù)。3D點云模型被八叉樹剖分后，點云數(shù)據(jù)按空間區(qū)域分布在不同葉節(jié)點立方體中，逐個讀取八叉樹葉節(jié)點數(shù)據(jù)，用式(1)計算該節(jié)點閾值δ，用式(2)、式(3)計算某點與鄰域各點歐氏距離期望值，若E(D)遠大于δ作為噪聲點去除，以葉節(jié)點為單位的局部空間除噪能保證除去噪聲點的準(zhǔn)確性。

1.2 Morton碼排序

一個3D點云由X、Y、Z浮點類型坐標(biāo)和反射強度(Intensity)數(shù)據(jù)及整型顏色數(shù)據(jù)等組成，沒有描述層次的語義信息，而且點云數(shù)據(jù)具有雜亂、無序特征，給數(shù)據(jù)壓縮和空間索引帶來極大挑戰(zhàn)。文中壓縮算法思想是借助相鄰點云位置及特征具有相似性，對其數(shù)據(jù)差值進行壓縮能夠提高壓縮率。壓縮前需要對點數(shù)據(jù)進行排序，排序結(jié)果既要保證相鄰點云數(shù)據(jù)線性有序而且空間位置相鄰關(guān)系不能被破壞。由于位置坐標(biāo)是三維數(shù)據(jù)，所以不能直接把它們作為關(guān)鍵詞排序，但可以使用它們的莫爾頓編碼(Morton)排序。莫爾頓碼排序能將多維數(shù)據(jù)唯一映射到一維空間，不但把三維數(shù)據(jù)按線性關(guān)系排序而且能保留點云原始空間相鄰關(guān)系[22]。莫爾頓編碼通過把X、Y、Z坐標(biāo)二進制數(shù)據(jù)每個bit位交叉組合實現(xiàn)編碼。由于3D點云數(shù)據(jù)坐標(biāo)是浮點類型，所以先要把浮點型轉(zhuǎn)化為二進制表示，然后再進行編碼排序，文中用Morton對每個八叉樹葉節(jié)點內(nèi)數(shù)據(jù)進行單獨排序，使得虛擬旅游模型點云數(shù)據(jù)在局部空間內(nèi)唯一有序。利用莫爾頓碼對八叉樹葉子節(jié)點管理的點云數(shù)據(jù)排序結(jié)果如圖1所示，很顯然莫爾頓碼能使3D點數(shù)據(jù)按線性關(guān)系有序且保留了數(shù)據(jù)空間位置相鄰關(guān)系。本文壓縮算法是借助數(shù)據(jù)相鄰關(guān)系對點云原始數(shù)據(jù)差值進行無損壓縮，所以排序后的點坐標(biāo)依然采用浮點數(shù)據(jù)類型表示。

圖1 八叉樹葉節(jié)點數(shù)據(jù)莫爾頓碼排序示意圖

1.3 有序數(shù)據(jù)分塊

虛擬旅游3D點云數(shù)據(jù)海量，如果采用單分辨率壓縮算法進行整體壓縮，客戶端就必須接收完整體數(shù)據(jù)后才能解壓、渲染，這樣壓縮率不管有多高，網(wǎng)絡(luò)資源也無法滿足漫游時客戶忍耐極限。若采用漸進壓縮方法勢必額外增加大量冗余數(shù)據(jù)，這種空間換時間的做法也不適合體積本來龐大3D數(shù)據(jù)，采用折中辦法對海量點云數(shù)據(jù)按空間區(qū)域分成小塊，按塊進行壓縮，以塊數(shù)據(jù)流傳輸和解壓。另一方面，點云數(shù)據(jù)分布在R樹每個葉節(jié)點的若干個外接立方體中管理，葉節(jié)點通過索引記錄管理外接立方體，間接管理點云數(shù)據(jù)，所以分塊也便于為3D模型構(gòu)建R樹索引結(jié)構(gòu)，但是分塊后有可能重新造成某些塊間空間區(qū)域重疊，影響R樹查詢性能，所以分塊后必須進行去除塊間區(qū)域重疊，運用定理1和推論1進行去重。

定理1 空間去重。V1，V2，…，Vi為立方體，任意二個Vi，Vj若存在Vi∩Vj≠?，則必須合并操作，即Vi∪Vj=V′(其中1

推論1 空間去重。假設(shè)任意多個立方體存在Vi∩Vi+1≠?，Vi+1∩Vi+2≠?，…，則進行合并操作，即Vi∪Vi+1∪Vi+2=Vi′(其中1≤i≤fan)。

將1.2節(jié)已排序的每個八叉樹葉節(jié)點均勻分塊，分塊結(jié)束條件為塊數(shù)不大于R樹扇出fan，由于R樹每個節(jié)點獨占一個磁盤頁面，扇出fan計算公式為：

fan=Vdisk/Vrecord

(4)

其中：Vdisk為磁盤頁面容量；Vrecord為葉節(jié)點一條索引記錄所占字節(jié)數(shù)。計算每塊數(shù)據(jù)覆蓋區(qū)域最小立方體范圍MBR1，MBR2，…，MBRi，MBR立方體范圍用其左上角(Xmin，Ymin，Zmin)和右下角(Xmax，Ymax，Zmax)坐標(biāo)表示，它們將作為R樹葉節(jié)點外接立方體。這些分塊可能存在空間區(qū)域重疊，需要利用定理1消除重疊，顯而易見，由推論1可知，最壞情況下這些分塊空間區(qū)域全部重疊，重新合并為一塊，但是這種情況十分罕見。

1.4 計算鄰點差值

文中采用算術(shù)編碼方法壓縮，算術(shù)編碼是無損的熵編碼方法。它把整個輸入信息編碼為一個小數(shù)n，n滿足(0≤n<1.0)，適合于由相同的重復(fù)序列組成的數(shù)據(jù)，即被壓縮符號中相同符號概率越高編碼越短，壓縮率越高，可以達到理論熵值[23]。物體局部特征相似性原理可知3D點云模型某個局部區(qū)域點的三維坐標(biāo)、反射強度和顏色信息高度近似。由1.2節(jié)可知點云數(shù)據(jù)Morton碼排序后沒有破壞它們局部相鄰關(guān)系，即局部特征相似性，表示它們空間位置的三維坐標(biāo)、反射強度和顏色等數(shù)據(jù)都非常接近，差值數(shù)據(jù)中“0”出現(xiàn)頻率較高。差值數(shù)據(jù)指Morton序列中相鄰兩個點的坐標(biāo)、反射強度和顏色數(shù)據(jù)作差運算，即每個立方體除第一個點外其余點分別存儲它們與前面點的坐標(biāo)、反射輕度、顏色數(shù)據(jù)差值。由局部相似性原理可知差值數(shù)據(jù)中“0”出現(xiàn)頻率較高，非常符合算術(shù)編碼特點。由于Morton排序僅能保證局部點嚴(yán)格相鄰，個別點存在跨空間區(qū)域現(xiàn)象，個別前、后相鄰兩個點在實際3D模型中空間位置并不相鄰，如圖1中的A點和B點在Morton排序中是前、后相鄰關(guān)系，實際卻處在3D模型中不同區(qū)域，那么B點和A點數(shù)據(jù)差值有可能比原數(shù)據(jù)大，包含“0”字符可能不會增加，但是下一個點與B點在Morton排序中相鄰，也在模型空間相鄰，而且從圖1看到跨區(qū)域點僅占少數(shù)，不會影響整體壓縮性能，利用算術(shù)編碼對位置相鄰兩點數(shù)據(jù)差值壓縮能使點云模型整體壓縮率有較大提高?；谝陨显虮疚奶岢鲟忺c差值漸進壓縮(Adjacent Point Difference Progressive Compression, APDPC)方法。

1.5 鄰點差值漸進壓縮

虛擬旅游3D模型不僅數(shù)據(jù)量龐大而且空間區(qū)域跨度也特別大，網(wǎng)絡(luò)帶寬和系統(tǒng)資源的限制不允許一次性加載完數(shù)據(jù)再進行渲染、漫游。顯然基于順序流式傳輸方式是最佳選擇，只需等待幾秒鐘加載數(shù)據(jù)就能解壓、漫游，但是流式傳輸方式要求數(shù)據(jù)采用漸進壓縮方式進行。3D模型所有漸進壓縮算法都是典型的以數(shù)據(jù)冗余換取網(wǎng)絡(luò)響應(yīng)時間，先傳輸?shù)拇植谀Ｐ投际侨哂鄶?shù)據(jù)，對于海量3D點云數(shù)據(jù)不是長久之計，但是算術(shù)編碼又是單分辨率壓縮方式，要用單分辨率編碼算法實現(xiàn)漸進壓縮就必須把巨大3D模型拆分為許多較小獨立塊壓縮，以1.3節(jié)中每個立方體塊為單位編碼壓縮，這樣只要一個立方體塊數(shù)據(jù)傳輸結(jié)束就可以解壓、渲染，同時傳輸下一塊數(shù)據(jù)，周而復(fù)始實現(xiàn)漸進壓縮算法的流式傳輸效果，并且無需增加額外冗余數(shù)據(jù)。逐個取每個立方體內(nèi)點差值數(shù)據(jù)作為輸入信源符號序列，設(shè)算術(shù)編碼初始區(qū)間[LH)=[0 1)，當(dāng)前區(qū)間為[lihi)，當(dāng)前區(qū)間長度為rangei=hi-li，則符號編碼公式為：

li+1=li+rangei×li+1

(5)

hi+1=li+rangei×hi+1

(6)

如果序列中某個符號出現(xiàn)頻率越高，那么算術(shù)編碼就越短，壓縮效果就越好，由于差值數(shù)據(jù)中“0”符號出現(xiàn)概率非常大，鄰點差值漸進壓縮方法大幅度提高3D點云數(shù)據(jù)壓縮率，而且能實現(xiàn)以塊為單位流式傳輸，從數(shù)據(jù)源頭解決海量虛擬旅游3D點云數(shù)據(jù)網(wǎng)絡(luò)瓶頸問題。

2 點云數(shù)據(jù)空間索引

3D點云模型數(shù)據(jù)量特別龐大而查詢數(shù)據(jù)集又相對特別小，查詢效率不高一直困擾3D點云數(shù)據(jù)廣泛應(yīng)用，建立空間索引是提高查詢效率關(guān)鍵，空間索引是按照對象位置、形狀和空間關(guān)系的某種排列管理數(shù)據(jù)。有了索引查詢就能依據(jù)查詢條件(如立方體)快速搜索與查詢區(qū)域相交的空間對象。眾所周知R樹是工業(yè)界常用的多維空間索引結(jié)構(gòu)，例如Oracle數(shù)據(jù)庫的企業(yè)版2007年實現(xiàn)基于R樹的空間索引[24]，所以本文給虛擬旅游模型選擇R樹作為空間索引結(jié)構(gòu)有理論和實踐依據(jù)。

2.1 創(chuàng)建索引結(jié)構(gòu)

虛擬旅游3D點云數(shù)量海量，為了減少時間開銷采用靜態(tài)批量加載方法構(gòu)建R樹索引結(jié)構(gòu)。以八叉樹葉節(jié)點數(shù)據(jù)作為批量加載單元，即批量有序讀取1.5節(jié)數(shù)據(jù)塊，計算它們對應(yīng)空間最小立方體范圍MBR1，MBR2，…，MBRi，利用它們構(gòu)造R樹葉節(jié)點每個外接立方體索引記錄(MBR, tuple-identifier)。創(chuàng)建R樹葉節(jié)點t，將所有索引記錄批量有序插入葉節(jié)點t，若t中索引記錄個數(shù)不大于fan/2，則這些數(shù)據(jù)塊與八叉樹下一個葉節(jié)點數(shù)據(jù)合并處理，數(shù)據(jù)批量插入前還要檢查t的索引記錄上線數(shù)是否大于扇出fan，若大于fan則先分裂葉節(jié)點t，然后在批量插入到新分裂的葉節(jié)點中。若t中索引記錄個數(shù)大于fan/2，則將讀取的所有數(shù)據(jù)批量插入磁盤數(shù)據(jù)區(qū)，為它們建立引用標(biāo)識tuple-identifier，計算葉節(jié)點t的立方體范圍MBRt，構(gòu)造葉節(jié)點t的索引記錄并插入其父節(jié)點。同樣方法創(chuàng)建父節(jié)點、祖父節(jié)點……，同理也要進行索引記錄數(shù)上、下限檢查，這樣既可保證R樹兄弟節(jié)點空間不重疊又能保證磁盤頁面使用率在1/2以上，如此重復(fù)，直到整棵R樹創(chuàng)建完。利用八叉樹對點云數(shù)據(jù)進行空間剖分、分塊等預(yù)處理后再創(chuàng)建索引，既保證了R樹兄弟節(jié)點空間區(qū)域不重疊，提高了查詢性能，又保證點云數(shù)據(jù)能實現(xiàn)漸壓縮，使其能按流式傳輸。

2.2 裁剪重疊區(qū)域的冗余處理技術(shù)

定理2 查詢重疊區(qū)域裁剪。假設(shè)W1、W2為任意相鄰兩次查詢請求窗口，且W1優(yōu)于W2執(zhí)行，其中W1∩W2=W，W2-W1∩W2=W′，若W≠?則按W′在R樹搜索空間區(qū)域交叉的子節(jié)點；否則按W2范圍搜索R樹子節(jié)點。

R樹索引的查詢是從根節(jié)點開始自上而下遞歸搜索與查詢窗口交叉的子樹節(jié)點，在葉節(jié)點上獲取所有重疊外接立方體包圍的空間對象[25]，下一次查詢同理。由于在實際虛擬旅游或數(shù)字城市漫游過程中相鄰兩次漫游請求的查詢窗口存在重疊是大概率事件，如果兩次查詢都按原窗口范圍搜索空間對象必定會產(chǎn)生大量冗余數(shù)據(jù)，再次將這些冗余數(shù)據(jù)傳輸?shù)娇蛻舳吮貙⒃黾泳W(wǎng)絡(luò)和客戶端硬件資源開銷，對網(wǎng)絡(luò)帶寬本來就緊缺的虛擬漫游系統(tǒng)無益有害。由于查詢算法開銷主要取決于訪問I/O代價[26]，所以重疊區(qū)域查詢會額外增加磁盤I/O開銷，重疊區(qū)域必將造成查詢效率低、冗余數(shù)據(jù)造成網(wǎng)絡(luò)帶寬開銷等弊端。本文提出裁剪重疊區(qū)域的冗余處理技術(shù)，即利用上次查詢范圍，本次查詢時首先根據(jù)定理2判斷本次查詢與上次查詢是否存在重疊區(qū)域，若存在重疊區(qū)域，則通過空間運算進行裁剪，計算本次查詢有效范圍，去除重疊區(qū)域，然后按本次有效查詢范圍在R樹搜索空間區(qū)域交叉的子節(jié)點，利用這些索引子節(jié)點定位到對應(yīng)磁盤文件，獲取本次查詢的數(shù)據(jù)；若相鄰兩次查詢窗口不存在重疊區(qū)域，則直接利用R樹查詢。查詢結(jié)束時利用本次查詢請求窗口值作更新上次范圍，作為后續(xù)查詢時窗口重疊判斷依據(jù)。如圖2所示相鄰兩次查詢窗口A和窗口B，其中窗口A優(yōu)先于窗口B執(zhí)行，由定理2可知兩次查詢存在重疊區(qū)域為R23和R24，它們所包圍的對象為冗余數(shù)據(jù)，查詢時需要去除。裁剪重疊區(qū)域的冗余處理技術(shù)能夠在索引樹上獲取有效索引，從而減少了查詢時的I/O訪問次數(shù)，如圖2所示，相鄰兩次查詢情況利用文中的冗余處理技術(shù)可以減少2次I/O訪問，不但提高查詢效率而且減輕了網(wǎng)絡(luò)傳輸壓力。

圖2 R樹與窗口查詢交叉

2.3 基于R樹點云查詢

由1.2節(jié)3D點云排序、1.3節(jié)分塊和去重疊處理、2.1節(jié)構(gòu)建索引結(jié)構(gòu)可知，R樹葉節(jié)點每個立方體包圍數(shù)據(jù)是有序的、空間區(qū)域相鄰，并且漫游過程中相鄰兩次漫游窗口存在區(qū)域重疊是大概率事件，所以查詢時要進行冗余查詢處理，查詢實現(xiàn)過程算法描述如下。

算法1 基于R樹點云查詢算法。

輸入：查詢窗口Wi點云模型D。

輸出：滿足條件點云數(shù)據(jù)Di。

W←Wi-1

while (Wi≠?) do

{W′ ←W∩Wi

if(W′≠?)

{W′ ←Wi-W∩Wi

Di← Query(W′RD)}

else

Di← Query(WiRD)

endif

W←Wi}

endwhile

outputDi

算法中的Query(WiRD)為基于R樹3D點云數(shù)據(jù)查詢函數(shù)。

3 實驗結(jié)果與分析

利用TrimbleVX激光掃描儀采集不同場景3D點云數(shù)據(jù)，通過三維重建軟件構(gòu)建3D模型。實驗環(huán)境是機器內(nèi)存為8 GB，CPU 1.7 GHz，存盤頁面為8 KB。主要測試壓縮率、創(chuàng)建索引代價、查詢性能、數(shù)據(jù)冗余率。實驗效果與文獻[11]基于R樹的可變長編碼(VLC)無損壓縮方法和索引方法進行比較，因為VLC方法與本文提出鄰點差值漸進壓縮APDPC方法都是基于R樹管理的點云數(shù)據(jù)壓縮，且索引機制都是基于R樹實現(xiàn)，具有可比性。

3.1 壓縮性能比較

壓縮率可以相對減少數(shù)據(jù)傳輸總量，因而可以緩解虛擬漫游網(wǎng)絡(luò)傳輸瓶頸。隨著近幾年硬盤容量成倍增加，壓縮目的主要是相對減少網(wǎng)絡(luò)傳輸數(shù)據(jù)量，很少考慮硬盤空間利用率，所以把服務(wù)器端輸出有效數(shù)據(jù)量作為數(shù)據(jù)壓縮評價指標(biāo)。壓縮性能通過與文獻[11]可變長編碼VLC無損壓縮方法比較，壓縮性能測試結(jié)果如表1所示。本文的APDPC方法壓縮率明顯高于VLC方法，壓縮率平均提高了26.61個百分點。由于本文APDPC方法是對立方體內(nèi)相鄰點云數(shù)據(jù)差值進行算術(shù)編碼壓縮，根據(jù)物體局部相似性原理和Morton碼排序結(jié)果可知相鄰點的三維坐標(biāo)、屬性數(shù)據(jù)值非常接近，所以它們差值中“0”字符出現(xiàn)概率相當(dāng)大，此特性正是算術(shù)編碼算法優(yōu)勢所在，VLC方法壓縮前沒有對3D點云數(shù)據(jù)進行分塊、排序、計算差值等處理，直接壓縮原始3D數(shù)據(jù)，所以APDPC方法比VLC方法有較高壓縮率。由于不規(guī)則物體相鄰兩點數(shù)據(jù)逆值情況較多，如圖1中A、B兩點情況，所以壓縮率低于規(guī)則物體。APDPC方法幾乎不受數(shù)據(jù)量大小影響，VLC方法對數(shù)據(jù)規(guī)模較敏感，也正暴露可變長編碼不適合大規(guī)模點云數(shù)據(jù)壓縮弱點。

表1 APDPC方法壓縮性能

3.2 創(chuàng)建索引開銷

對于海量點云數(shù)據(jù)而言創(chuàng)建索引時間是一項重要性能指標(biāo)，如果創(chuàng)建索引時間太長超出人們承受范圍，再好的索引結(jié)構(gòu)也無濟于事，創(chuàng)建時間如圖3所示。本文方法創(chuàng)建索引時間花費高于VLC方法，原因是為了防止R樹兄弟節(jié)點空間重疊，創(chuàng)建索引前用八叉樹對3D模型進行了空間剖分、Morton碼排序、分塊、計算鄰點差值，壓縮差值并構(gòu)建R樹，VLC方法直接壓縮點云數(shù)據(jù)后就創(chuàng)建R樹，所以本文創(chuàng)建索引結(jié)構(gòu)時間開銷大。圖3顯示創(chuàng)建索引時間會隨數(shù)據(jù)量增大而增加，但是增加幅度不是跳躍式劇增而是在可承受范圍內(nèi)。創(chuàng)建這兩種索引實質(zhì)都是創(chuàng)建R樹，只是創(chuàng)建過程中數(shù)據(jù)前期處理和組織方式不同而已，最終導(dǎo)致時間開銷不同。

3.3 平均查詢性能

平均查詢性能是衡量一個索引結(jié)構(gòu)最重要、最直觀的指標(biāo)，本文提出的裁剪重疊區(qū)域冗余處理技術(shù)目的在于減少查詢時訪問I/O次數(shù)，是對特定應(yīng)用領(lǐng)域查詢方式改進和優(yōu)化，而文獻[11]的方法完全是傳統(tǒng)R樹查詢方式。實驗設(shè)計Q1、Q2、Q3、Q4三類查詢，測試平均查詢性能，每次實驗的三類查詢選擇相同區(qū)域，即MBR(Q1)=MBR(Q2)=MBR(Q3)=MBR(Q4)，但它們查詢方式不同：Q1為一次窗口查詢請求完成，Q2、Q3、Q4設(shè)計兩次窗口查詢請求完成，并且Q2、Q3兩次查詢窗口有重疊區(qū)域，Q3窗口重疊區(qū)域大于Q2，Q4兩次查詢窗口不相交，查詢平均性能如圖4所示，本文索引結(jié)構(gòu)使平均查詢性能提高了35.44%。圖4顯示在Q1查詢中本文方法略優(yōu)于文獻[11]方法，原因是Q1查詢是單窗口查詢，本文方法與文獻[11]方法都使用R樹索引，但是本文構(gòu)建索引前對數(shù)據(jù)進行空間劃分、去除兄弟節(jié)點重疊、排序、分塊等處理，3D模型在R樹中分布均勻且數(shù)據(jù)壓縮率高，所以查詢開銷小于文獻[11]方法。Q2、Q3屬于相鄰二次窗口查詢情況，由本文裁剪重疊區(qū)域的冗余處理技術(shù)可知Q2、Q3查詢時先要進行冗余處理，使得Q3的查詢代價大幅度減少，在文獻[11]中Q2、Q3相鄰查詢開銷和Q2、Q3分別獨立查詢開銷幾乎等價，所以文獻[11]中Q2、Q3查詢開銷遠大于本文方法。裁剪重疊區(qū)域冗余處理技術(shù)目的是剔除二次查詢的重疊區(qū)域，最終減少訪問磁盤I/O開銷，即使Q3比Q2重疊區(qū)域大，重疊區(qū)域一樣被裁剪，它們實際訪問磁盤塊數(shù)幾乎是一樣的，所以實驗結(jié)果顯示Q3與Q2查詢時間幾乎相等，實驗證明相鄰兩次查詢窗口不管重疊多少都能有效裁剪冗余查詢，但是在實際漫游中重疊區(qū)域越大兩次查詢獲得有效數(shù)據(jù)就越少，漫游越慢。Q4為無重疊窗口相鄰兩次查詢，等價于Q1查詢，但兩次查詢比一次查詢開銷要高，文獻[11]方法也同理。在實際漫游中，請求窗口是否重疊，重疊區(qū)域大小因人而異。

圖3 兩種方法創(chuàng)建索引時間對比

圖4 不同方法查詢性能對比

3.4 冗余分析

對于龐大3D模型，查詢方法的數(shù)據(jù)冗余也是重要性能指標(biāo)。本文裁剪重疊區(qū)域冗余處理技術(shù)目的不僅是減少查詢的I/O次數(shù)而且還控制查詢時的數(shù)據(jù)冗余，創(chuàng)建R樹前的空間剖分、局部Morton碼排序、分塊等處理都起到控制數(shù)據(jù)冗余作用，從數(shù)據(jù)源端緩解網(wǎng)絡(luò)傳輸壓力。按查詢窗口重疊和不重疊兩種情況測試，查詢方法的數(shù)據(jù)冗余率為多次實驗結(jié)果平均值，數(shù)據(jù)冗余率=I/O數(shù)據(jù)量-原數(shù)據(jù)量/原始數(shù)據(jù)量，測試結(jié)果如圖5所示，本文方法查詢時數(shù)據(jù)冗余平均減少了16.49%。兩種情況下本文方法數(shù)據(jù)冗余率都非常低，進一步說明本文索引方法性能較高。漫游窗口不重疊時文獻[11]方法數(shù)據(jù)冗余率也相對較低，但遠高于本文方法，這是因為文獻[11]方法構(gòu)建R索引樹前沒有對3D模型空間剖分、分塊和去除兄弟節(jié)點重疊預(yù)處理，重疊節(jié)點產(chǎn)生數(shù)據(jù)冗余較多。相鄰兩次窗口重疊情況下本文用了裁剪重疊區(qū)域冗余處理技術(shù)查詢，而該方法裁剪了重疊窗口區(qū)域數(shù)據(jù)，幾乎杜絕冗余數(shù)據(jù)產(chǎn)生，而文獻[11]方法把重疊窗口區(qū)域查詢了2次，所以數(shù)據(jù)冗余率明顯大；而且數(shù)據(jù)冗余率總體趨勢隨重疊窗口增加而變大，但是非線性增大，這也說明虛擬旅游3D模型非均勻分布在R樹空間，兄弟節(jié)點重疊情況也不均勻。

圖5 不同查詢方法數(shù)據(jù)冗余率對比

4 結(jié)語

網(wǎng)絡(luò)帶寬有限和3D點云數(shù)據(jù)海量制約著虛擬旅游暢通漫游和廣泛發(fā)展，解決辦法除了改進網(wǎng)絡(luò)技術(shù)增加網(wǎng)絡(luò)帶寬外還可以利用本文提出的鄰點差值漸進壓縮方法和冗余處理技術(shù)從數(shù)據(jù)源頭減少數(shù)據(jù)傳輸總量，并能支持按流式傳輸，可以從數(shù)據(jù)源端緩解帶寬壓力；利用本文提出的索引方法在查詢時能有效減少非葉節(jié)點I/O訪問次數(shù)，有效控制數(shù)據(jù)冗余，從而提高查詢速度，縮短數(shù)據(jù)傳輸時間，但是系統(tǒng)運行中要不斷維護上次查詢信息，占用少量系統(tǒng)開銷。實驗證明本文提出壓縮方法和索引結(jié)構(gòu)非常高效，非常適合于虛擬旅游、數(shù)字城市等3D模型中的海量點云數(shù)據(jù)。

由于3D模型點云數(shù)據(jù)非常龐大，如果集中部署在一臺機器上，即使對其采取優(yōu)化措施，系統(tǒng)性能還是相對較低，如果將數(shù)據(jù)分塊部署在多臺機器上并行處理性能會更優(yōu)。下一步研究工作將R樹索引結(jié)構(gòu)與分布式系統(tǒng)結(jié)合，例如與Hadoop或Spark平臺結(jié)合把點云模型合理分塊后分別部署在不同工作節(jié)點上，實現(xiàn)并行處理和多細節(jié)層次索引,提高點云數(shù)據(jù)查詢與加載速度將是今后研究重點。

References)

[1] MIRK D, HLAVACS H. Virtual tourism with drones: experiments and lag compensation [C]// Proceedings of the First Workshop on Micro Aerial Vehicle Networks, Systems, and Applications for Civilian Use. New York: ACM, 2015: 40-45.

[2] NING X J, ZHANG X P, WANG Y H, et al. Segmentation of architecture shape information from 3D point cloud [C]// VRCAI09: Proceedings of the 8th International Conference on Virtual Reality Continuum and Its Applications in Industry. New York: ACM, 2009: 127-132.

[3] MERRY B, GAIN J, MARAIS P. Fast in-place binning of laser range-scanned point sets [J]. ACM Journal on Computing and Cultural Heritage, 2013, 6(3): 1-19.

[4] MORELL V, ORTS S, CAZORLA M, et al. Geometric 3D point cloud compression [J]. Pattern Recognition Letters, 2014, 50(2014):55-62.

[5] SMITH J, PETROVA G, SCHAEFER S. Full progressive encoding and compression of surfaces generated from point cloud data [J]. Computers & Graphics, 2012, 36(5):341-348.

[6] HUANG Y, PENG J L, KUO J, et al. A generic scheme for progressive point cloud coding [J]. IEEE Transactions on Visualization & Computer Graphics, 2008, 14(2): 440-453.

[7] CAI K Y, JIANG W F, MA T, et al. Probability model-adaptive coding of point clouds with octree decomposition [C]// Proceedings of SIGGRAPH Asia 2011 Posters. New York: ACM, 2011: Article No. 33.

[8] COHEN R A, TIAN D, VETRO A. Point cloud attribute compression using 3-D intra prediction and shape-adaptive transforms [C]// DCC’16: Proceedings of 2016 Data Compression Conference. Piscataway, NJ: IEEE, 2016: 141-150.

[9] DAI C Q, CHEN M, FANG X Y. Compression algorithm of 3D point cloud data based on octree [J]. The Open Automation and Control Systems Journal, 2015, 7(8): 879-883.

[10] SONG W W, CAI S L, YANG B, et al. A reduction method of three-dimensional point cloud [C]// BMEI2009: Proceedings of the 2009 2nd International Conference on Biomedical Engineering and Informatics. Piscataway, NJ: IEEE, 2009: 1-4.

[11] CHOVANEC P, KRATKY M, WALDER J. Lossless R-tree compression using variable-length codes[C]// Proceedings of the 5th International Conference for Internet Technology and Secured Transactions. Piscataway, NJ: IEEE, 2010: 1-8.

[12] GUTTMAN A. R-trees: a dynamic index structure for spatial searching [C]// SIGMOD’84: Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1984: 47-57.

[13] CHALLA J S, GOYAL P, NIKHIL S. A concurrentk-NN search algorithm for R-tree [C]// Proceedings of the 8th Annual ACM India Conference. New York: ACM, 2015: 123-128.

[14] PATEL P, GARG D. Perfect hashing base R-tree for multiple queries [C]// Proceedings of 2014 IEEE International Advance Computing Conference. Piscataway, NJ: IEEE, 2014: 636-640.

[15] HE Z W, WU C L, WANG C. Clustered sorting R-tree: an index for multi-dimensional spatial objects [C]//ICNC2008: Proceedings of 2008 Fourth International Conference on Natural Computation. Piscataway, NJ: IEEE, 2008: 348-351.

[16] NOLEN M, LIN K I. Approximate high-dimensional nearest neighbor queries using R-forests [C]// Proceedings of the 17th International Database Engineering & Applications Symposium. New York: ACM, 2013: 48-57.

[17] SHARIFZADEH M, SHAHABI C. VoR-tree: R-trees with Voronoi diagrams for efficient processing of spatial nearest neighbor queries [C]// Proceedings of the 36th International Conference on Very Large Data Bases. Singapore: VLDB Endowment, 2010: 1231-1242.

[18] PATEL P, GARG D D. Perfect hashing base R-tree for multiple queries [C]// IACC2014: Proceedings of the 2014 IEEE International Advance Computing Conference. Piscataway, NJ: IEEE, 2014: 636-640.

[19] GONG J, ZHANG H W. A method for LOD generation of 3D city model based on extended 3D Rtree index [C]// FSKD2011: Proceedings of the 2011 Eighth International Conference on Fuzzy Systems and Knowledge Discovery. Piscataway, NJ: IEEE, 2011: 2004-2008.

[20] 鄧紅艷，武芳，翟仁健,等.一種用于空間數(shù)據(jù)多尺度表達的R樹索引結(jié)構(gòu)[J].計算機學(xué)報，2009,32(1):177-184.(DENG H Y, WU F, ZHAI R J, et al. R-tree index structure for multi-scale representation of spatial data [J]. Chinese Journal of Computers, 2009,32(1): 177-184.)

[21] DRAISMA J, HOROBE E, OTTAVIANI G. The Euclidean distance degree [C]// Proceedings of the 2014 Symposium on Symbolic-Numeric Computation. New York: ACM, 2014: 9-16.

[22] LEE K C, LE W C, ZHENG B H, et al. Z-SKY: an efficient skyline query processing framework based on Z-order [J]. The VLDB Journal, 2010, 19(3): 333-362.

[23] WITTEN I H, NEAL R M, CLEARY J G. Arithmetic coding for data compression [J]. Communications of the ACM, 1987, 30(6): 520-540.

[24] ZHANG R, QI J Z, STRADLING M, et al. Towards a painless index for spatial objects [J]. ACM Transactions on Database Systems, 2014, 39(3): 19-41.

[25] YI K. The priority R-tree [J]. SIGSPATIAL Special, 2012, 4(2): 8-12.

[26] 宋杰，李甜甜，朱志良，等.MapReduce連接查詢的I/O代價研究[J].軟件學(xué)報，2015,26(6):1438-1456.(SONG J, LI T T, ZHU Z L, et al. Research on I/O cost of MapReduce join [J]. Journal of Software, 2015, 26(6): 1438-1456.)

This work is partially supported by the National Natural Science Foundation of China (61762082), the Natural Science Foundation of Tibet (12KJZRYMY07).

ZHAOErping, born in 1976, M. S., associate professor. His research interests include database, data fusion.

LIUWei, born in 1978, Ph. D., associate professor. His research interests include database, geographic information system.

DANGHong’en, born in 1978, M. S., lecturer. His research interests include database.