海量3D點云數據壓縮與空間索引技術

趙爾平，劉 煒，黨紅恩

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

0 引言

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

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

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

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

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

1 點云數據壓縮

1.1 3D模型空間剖分及點云數據除噪

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

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

(1)

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

(2)

(3)

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

1.2 Morton碼排序

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

圖1 八叉樹葉節點數據莫爾頓碼排序示意圖

1.3 有序數據分塊

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

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

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

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

fan=Vdisk/Vrecord

(4)

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

1.4 計算鄰點差值

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

1.5 鄰點差值漸進壓縮

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

li+1=li+rangei×li+1

(5)

hi+1=li+rangei×hi+1

(6)

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

2 點云數據空間索引

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

2.1 創建索引結構

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

2.2 裁剪重疊區域的冗余處理技術

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

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

圖2 R樹與窗口查詢交叉

2.3 基于R樹點云查詢

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

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

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

輸出：滿足條件點云數據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點云數據查詢函數。

3 實驗結果與分析

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

3.1 壓縮性能比較

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

表1 APDPC方法壓縮性能

3.2 創建索引開銷

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

3.3 平均查詢性能

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

圖3 兩種方法創建索引時間對比

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

3.4 冗余分析

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

圖5 不同查詢方法數據冗余率對比

4 結語

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

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

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] 鄧紅艷，武芳，翟仁健,等.一種用于空間數據多尺度表達的R樹索引結構[J].計算機學報，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].軟件學報，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.