海量3D點(diǎn)云數(shù)據(jù)壓縮與空間索引技術(shù)

趙爾平，劉 煒，黨紅恩

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

0 引言

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

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

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

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

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

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

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

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

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

(1)

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

(2)

(3)

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

1.2 Morton碼排序

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

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

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

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

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

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

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

fan=Vdisk/Vrecord

(4)

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

1.4 計(jì)算鄰點(diǎn)差值

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

1.5 鄰點(diǎn)差值漸進(jìn)壓縮

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

li+1=li+rangei×li+1

(5)

hi+1=li+rangei×hi+1

(6)

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

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

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

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

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

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

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

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

圖2 R樹與窗口查詢交叉

2.3 基于R樹點(diǎn)云查詢

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

算法1 基于R樹點(diǎn)云查詢算法。

輸入：查詢窗口Wi點(diǎn)云模型D。

輸出：滿足條件點(diǎn)云數(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點(diǎn)云數(shù)據(jù)查詢函數(shù)。

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 壓縮性能比較

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

表1 APDPC方法壓縮性能

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

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

3.3 平均查詢性能

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

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

圖4 不同方法查詢性能對(duì)比

3.4 冗余分析

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

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

4 結(jié)語

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

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

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ù)多尺度表達(dá)的R樹索引結(jié)構(gòu)[J].計(jì)算機(jī)學(xué)報(bào)，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代價(jià)研究[J].軟件學(xué)報(bào)，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.