馬賢迪，常原飛，喬彥友

(中國科學院遙感與數(shù)字地球研究所，北京 100101)

?

矢量金字塔與R樹融合模型研究

馬賢迪，常原飛，喬彥友

(中國科學院遙感與數(shù)字地球研究所，北京 100101)

Research on a Vector Pyramid Model Fused R Tree Index

MA Xiandi，CHANG Yuanfei，QIAO Yanyou

摘要：主要圍繞如何在移動設備上快速顯示大數(shù)據(jù)量的面(線)狀矢量數(shù)據(jù)，結合多級空間索引和矢量數(shù)據(jù)壓縮提出了一種基于多尺度R樹的矢量數(shù)據(jù)模型，該模型可用于資源有限的移動設備。首先按照比例尺對矢量數(shù)據(jù)進行不同級別的壓縮，再將不同比例尺下的處理結果通過多尺度R樹索引組織存儲。通過這種方法可以達到在不同比例尺下顯示不同詳細程度的幾何對象。試驗采用湖南1∶10 000的林業(yè)資源小班數(shù)據(jù)來驗證該模型的可行性和效率。

關鍵詞：矢量數(shù)據(jù)模型；金字塔；R樹；移動GIS；多級空間索引

近年來，移動智能設備得到了快速發(fā)展和普及[1-2]，移動GIS[3-5]也成了當前GIS領域的一個重要研究方向。這種移動終端比較適合于土地、森林等行業(yè)相關數(shù)據(jù)的采集[6-8]，在這些領域移動GIS也得到了廣泛的研究。隨著移動GIS在各領域的不斷深入，現(xiàn)有GIS數(shù)據(jù)處理技術已經(jīng)不能滿足現(xiàn)代信息社會的需求，其中非常重要的原因就是移動GIS不能解決矢量數(shù)據(jù)隨比例尺變化產(chǎn)生的信息量增減問題[9-10]。典型的例子就是一個大比例尺單精度矢量數(shù)據(jù)在一定空間范圍內空間對象隨比例尺縮小而急劇增多，并相互覆蓋。而數(shù)據(jù)量增多會導致渲染速度過慢，影響用戶的操作體驗。

與影像金字塔類似，多尺度矢量數(shù)據(jù)組織和表達是減少參與顯示數(shù)據(jù)量的直接解決辦法。而傳統(tǒng)格網(wǎng)索引[11]或層級索引對數(shù)據(jù)對象多級顯示沒有給予足夠的支持；基于四叉樹[12]的多級顯示索引結構又因為其本身的限制，對于分布不均的空間對象檢索效率低下；即使是支持多尺度表達的R樹[13]各種變形[14]，又由于其設計時未考慮移動應用特點，造成顯示失真或效率低下，不能滿足移動設備需求。

移動GIS矢量數(shù)據(jù)快速可視化關鍵技術之一就是依據(jù)比例尺減少相應的數(shù)據(jù)量。針對目前移動GIS應用特點，本文將多級R樹索引和矢量壓縮算法相結合，提出一種適合當前移動應用的矢量數(shù)據(jù)金字塔結構，用于實現(xiàn)移動終端上無極比例尺大矢量數(shù)據(jù)的查詢和快速顯示。

一、數(shù)據(jù)與方法

1. 空間索引

空間對象多尺度表達已成為當前地理科學領域的前沿性問題，特別是在移動GIS領域這一研究還處于初級階段。下面從空間索引及多級空間索引在移動GIS中的應用來闡述相關研究進展。

(1) 空間索引在移動GIS中的應用

傳統(tǒng)空間索引主要有格網(wǎng)索引、樹狀索引及混合索引，樹狀索引主要有四叉樹和R樹及其變體：

1) 格網(wǎng)索引：將二維平面劃分為m×n網(wǎng)格，并用空間曲線建立格網(wǎng)一維索引，這種索引在空間對象分布不均時效率難以保證。

2) 四叉樹索引：該索引具有良好的節(jié)點插入和刪除效率，適合于動態(tài)空間數(shù)據(jù)，但是在空間對象密度不均時查詢效率低下。

3) R樹索引：插入和刪除節(jié)點效率較低，平均查找性能高，適合于矢量數(shù)據(jù)更新頻率低的移動GIS應用。

(2) 多級空間索引

傳統(tǒng)空間索引針對單尺度區(qū)域查詢，為了多尺度表達空間數(shù)據(jù)，需要建立多級空間索引。Reactive Tree[15]在R樹基礎上引入了對象實體權重，并按照權重將對象實體在索引樹不同層次上存儲，隨分辨率不同，低權重對象將被過濾，從而提供了多尺度表達空間實體的方法。在Multi-scale Hilbert R-tree[16]索引中，使用一種Douglas-Peuker[17]算法的變體對曲線和多邊形的頂點進行重要度計算，從而在不同尺度上顯示不同重要度的化簡體。

其他基于多尺度R樹及其變體的索引，大都采用上述選擇和化簡兩種思路來建立索引，類似的有多級Hilbert-R-Tree索引(HHRT，Hierarchical Hilbert-R-Tree)[18]、GAP-tree(Generalized Area Partitioning Tree)[14]、SDMR樹(Spatial Data Multi-representation R Tree)[19]等。

上述多級索引，都是將原始數(shù)據(jù)集A按某種規(guī)則劃分為多尺度數(shù)據(jù)集，并未建立A的多級簡體。這種方案雖然在空間上冗余不大，但每次訪問都需要從A中抽取非簇聚存儲的子集，由于抽取的也是原始精度的數(shù)據(jù)，在小比例尺顯示時精度和效率都有損失。這種方案適合于網(wǎng)絡上的漸進傳輸?shù)贿m合于移動GIS應用。本文中金字塔模型在第一層建立對象的簡體，僅研究一級簡體和多級簡化信息的結合，以后會研究多級簡體和多級簡化信息的結合。

2. 矢量金字塔模型創(chuàng)建

在創(chuàng)建矢量金字塔時，首先對原始矢量數(shù)據(jù)建立其某種R樹變體索引，其次將原始數(shù)據(jù)通過化簡壓縮成與R樹索引層數(shù)相同、分辨率依次降低的矢量數(shù)據(jù)集，最后將這些同一矢量數(shù)據(jù)在不同分辨率的集合體通過R樹索引組織成矢量金字塔。假設矢量數(shù)據(jù)集(面、線)V的維度為n(本文中取2)，矢量金字塔具體的建立步驟如下：

1) 對V建立R樹空間索引，R樹節(jié)點可包含孩子數(shù)有限([m，M]，m=M/2)，高度為Level(默認設置為8，可以通過調整m和M來實現(xiàn))，葉子節(jié)點為第0層。

2) 確定矢量數(shù)據(jù)的最大顯示比例尺(默認設置為1∶4000)和最小顯示比例尺(默認是1∶512 000)，比例尺依金字塔逐級縮小Ratio(默認為2)倍，默認建立8級金字塔。

3) 計算金字塔每層的壓縮算法參數(shù)。具體是：一個像素實際地理長度設置為該層壓縮算法參數(shù)。如在比例尺為1∶512 000、DPI(每英寸(2.54 cm)內的像素個數(shù))為96時，壓縮算法參數(shù)θMaxLevel計算方法為

θMaxLevel=512 000÷((96÷2.54)×100)≈135.47(m)

4) 建立金字塔的第1層數(shù)據(jù)簡體V0：以θ0作為壓縮算法參數(shù)對原始數(shù)據(jù)進行壓縮處理。

5) 建立金字塔其余各層的簡體(V1-VMaxLevel-1)。與第1層不同的是：其余各層建立的是V0中對象映射集合，并且記錄的是對象保留的坐標點在V0中的位置，其目的是減少金字塔數(shù)據(jù)大小，由此可以得到整個金字塔數(shù)據(jù)集VVPRD。

6) 對數(shù)據(jù)進行過濾，并建立其映射關系。首先將VL以θL為邊長進行格網(wǎng)劃分，依次統(tǒng)計Gij內完全包含的對象個數(shù)，如果大于1，則保留一個并刪除剩余的對象，同時建立保留對象和刪除對象之間的映射關系并保存到磁盤文件中(文件名.map)。

7) 將VL按照R樹進行存儲。V0按照R樹中第0層中的葉子順序存儲，保證每個葉子節(jié)點中包含的對象是連續(xù)存儲的；L﹥0時，VL按照R樹中第L層中的非葉子節(jié)點順序存儲，保證每個節(jié)點中包含對象的化簡信息是連續(xù)存儲的。

8) 將R樹存儲。R樹第L層某個節(jié)點中除記錄標準信息外，還存儲該節(jié)點在VL中的數(shù)據(jù)地址、包含對象(注：非節(jié)點)個數(shù)。

3. 矢量數(shù)據(jù)壓縮

矢量數(shù)據(jù)的壓縮方法目前有兩種途徑：一種是降低坐標存儲精度，另一種是過濾冗余點。國內有學者提出將雙精度浮點型坐標轉換為單精度或整形的坐標，這種方法可以減少一半左右的存儲空間[20-21]。后者是目前的主流數(shù)據(jù)化簡算法，有垂距法、Douglas-Peucker等算法[22-25]。文中討論的矢量金字塔模型采用的壓縮算法是Douglas-Peucker算法。

Douglas-Peucker是對線狀數(shù)據(jù)的化簡算法。而面狀數(shù)據(jù)是由線狀數(shù)據(jù)組成的，因此運用Douglas-Peucker算法簡化面狀幾何對象方法如圖1所示：分別處理面狀幾何對象的每一個環(huán)，將環(huán)的起點和終點連接作為一條線段(PsPe)，找出多邊形上距離線段最遠的點Pi將多邊形分成兩條線段，遞歸處理(PsPi)和(PiPe)線段直到滿足精度需求(最遠的點到PmPn的距離小于壓縮算法參數(shù))，化簡過程如圖1所示：原始多邊形由6個點組成，根據(jù)Douglas-Peucker算法計算出其在給定精度下應該保留的4個關鍵點，V0記錄實體坐標，VL(0

圖1　數(shù)據(jù)化簡過程

4. 幾何對象過濾

VL中每個格網(wǎng)大小為θL×θL，假設其中一個格網(wǎng)Gij如圖2所示，Gij內包含5個對象，刪除10、13、15、20這幾個對象，并且按照圖2右邊表格格式存儲到文件中。這一步的目的是去除屏幕上相互覆蓋的對象，以達到屏幕上一個像素空間(或給定精度的像素空間)僅顯示一個幾何對象的目的。對于跨格網(wǎng)的對象不作處理。

圖2　對象過濾圖

5. 模型的文件存儲結構

金字塔模型的文件存儲結構設計要保證目標信息能夠準確和快速地讀取。整個金字塔模型存儲到3個文件中：文件名.vprd、文件名.vpx、文件名.map。其中vprd文件存儲了壓縮后的整個矢量金字塔數(shù)據(jù)集(V0-MaxLevel)；vpx文件存儲了空間對象的索引和每個空間對象在vprd文件中的相對偏移量等相關信息；map文件存儲幾何對象的映射關系。在vprd文件中矢量對象VObject(葉子節(jié)點存儲矢量對象)或矢量對象的簡化信息VSimplifyInfo(非葉子節(jié)點)按照R樹索引順序排列使得屬于每個節(jié)點的VObject(VSimplifyInfo)得以連續(xù)存儲，其目的是為了一次IO便可以讀取一個節(jié)點內的所有矢量對象和其對應的簡化信息。原始對象唯一標識(ID)在每層對象中都相同。葉子節(jié)點中單個VObject格式見表1。

李凌扎實的法律功底以及謙虛好學的精神，得到了檢察院同事們的一致肯定，也堅定了李凌做好公訴工作的信心。自此之后，李凌跟著龔科長一起辦理了一系列大案要案，對檢察院的業(yè)務也逐漸變得熟稔起來。僅僅半年時間，李凌便開始像其他資深檢察員一樣，開始獨立辦理重大、疑難案件，從而被破格提拔為助理檢察員，三年之后便被任命為檢察員。

表1　面(線)狀目標的記錄內容

非葉子節(jié)點中單個VSimplifyInfo格式見表2。如圖1中的幾何對象其nVertices記錄為4，pPnt記錄為1、3、4、6。

map文件記錄了每層對象的過濾信息，分為文件信息頭和文件內容兩部分。信息頭的目的是區(qū)分每層過濾信息在map文件中的偏移。具體格式見表3和表4。

表2　幾何對象格式

表3　映射文件信息頭格式

表4　映射文件內容格式

在vpx文件中，多級R樹節(jié)點Node連續(xù)存儲。單個Node對象格式見表5。

表5　節(jié)點Node格式

在vpx文件中還存儲每層R樹在vprd文件中的起始偏移量、每個VObject(VSimplifyInfo)在vprd文件中的偏移量及金字塔第1層比例尺等輔助信息。

6. 模型的使用方法

1) 初始化R樹：讀取vpx文件，在內存中恢復R樹，建立節(jié)點數(shù)據(jù)在vprd文件中的偏移量和長度數(shù)組，并與R樹關聯(lián)。

3) 全圖顯示：計算比例尺ScaleF，若ScaleL1< ScaleF< ScaleL2則顯示VL2簡體，否則直接顯示VMaxLevel-1，具體細節(jié)在第4條。

4) 縮放：分為兩種情況。

固定比例尺，比例尺相對于1∶512 000放大RatioL倍(L為0～Level-1之間的整數(shù)，Ratio取2)：使用當前視口范圍矩形框變換后的地理坐標對R樹進行自頂向下的搜索，分別記錄搜索到的第L層和第0層節(jié)點集合SL和S0，根據(jù)對象映射表過濾S0，然后從vprd文件中讀取S0和SL的信息，用SL的信息對S0進行化簡并顯示到屏幕上。需要說明的是：SL中的ID集合是S0中ID集合的超集，因為VL存儲的只是V0中對象的化簡信息，相對來說數(shù)據(jù)量很小，此時減少IO次數(shù)可以提高IO效率，因此原始對象逐個讀取，而化簡信息R樹L層中一個節(jié)點一次性讀取(只有邊界部分會有冗余信息，但這些冗余信息會隨著漫游過程變成有用信息)，因此這種策略是可行并且有效的。

5) 漫游：與縮放過程類似，搜索得結果集后，與內存中當前顯示對象進行比較，只讀取差集。

6) 屬性查詢和其他分析功能：使用查詢點的地理坐標可查詢得到當前顯示對象FID值，這個值與原始對象中的是一致的，可通過該值訪問屬性或讀取原始坐標來作空間分析。

二、試驗與結果

為了測試模型效率，本文在QtCreator(Linux)下，采用C++語言，開發(fā)了相應的原型系統(tǒng)，系統(tǒng)測試機為三星N5100(Galaxy Note 8.0)，CPU為4核1.6 GHz主頻，系統(tǒng)內存2 GB，屏幕分辨率為1280×800像素，dpi為189，操作系統(tǒng)為Android 4.1；系統(tǒng)測試數(shù)據(jù)為SHP格式的多邊形矢量數(shù)據(jù)，原始數(shù)據(jù)大小為246 MB，包含47 566個幾何對象和15 577 152個頂點，橫坐標范圍：395 735.18～451 291.33，縱坐標范圍：3 089 567.36～3 172 370.04。按照M值取10、固定縮放倍率為2建立矢量金字塔后，VPRD文件大小為75.4 MB，VPX文件大小為5.1 MB，MAP文件大小為0.14 MB，金字塔高度為8層。表6為讀取全圖區(qū)域的不同層金字塔數(shù)據(jù)時的點數(shù)、時間等一些信息。

全圖顯示時比例尺為1∶516 736，因此顯示第8層金字塔數(shù)據(jù)?？梢钥闯鲋丿B的區(qū)域相比原始地圖明顯減少并且視覺上看不出明顯的縫隙，而IO速度提高了19倍左右，渲染速度提高了17倍左右。圖3為原始數(shù)據(jù)和金字塔模型在同一區(qū)域的顯示圖。

表6　矢量金字塔模型效果

圖3　渲染結果

三、結束語

本文基于矢量數(shù)據(jù)壓縮原理，使用多級R樹索引，將運行時需要的矢量數(shù)據(jù)預先處理成金字塔模型，有效提高了矢量數(shù)據(jù)顯示和查詢的性能。移動終端屏幕一般不大，因此顯示所需數(shù)據(jù)量有一定上限，通過數(shù)據(jù)壓縮，模型的實時讀取和顯示效率是可以得到保證的。在移動應用中，底圖往往是靜態(tài)或更新頻率低的準靜態(tài)，由于R樹是一棵高度平衡樹，其查詢效率相比同類索引高出很多，而索引可以在PC上生成移動端使用，因此R樹插入刪除的低效并不影響移動端的使用，故金字塔的性能是滿足要求的。

在隨后的工作中，將進一步對海量數(shù)據(jù)(如全省乃至全國林業(yè)資源數(shù)據(jù))的金字塔構建進行研究，從而提高模型的適用性，另外也會探討模型在空間分析方面的處理方法，擴大模型的使用范圍。

參考文獻：

[1]陳靜,吳信才,張發(fā)勇,等. 基于WebGIS的iPhone應用系統(tǒng)設計與實現(xiàn)[J].微計算機信息, 2009,25(11):140-142.

[2]王剛,韓振鏢. 面向Android智能移動終端的GIS設計與實現(xiàn)[J]. 測繪通報, 2013(8):77-80.

[3]王繼周,李成名. 嵌入式移動GIS研究[J]. 測繪科學,2005,30(4):48-50.

[4]郭峰林,胡鵬,徐小雙,等. 移動GIS中可視化技術研究[J]. 測繪科學,2007,32(6):74-76.

[5]康銘東,彭玉群. 移動GIS的關鍵技術與應用[J]. 測繪通報, 2008(9):50-53.

[6]孫貴博,宋偉東,張爍. Smart Client架構下的移動GIS數(shù)據(jù)采集研究[J]. 測繪科學,2011,36(4):188-190.

[7]余豐華,夏躍珍,楊克紅,等.移動GIS技術在地質災害數(shù)據(jù)采集領域的應用研究[J]. 中國地質災害與防治學報, 2006(2):102-106.

[8]李欣. 基于位置服務的移動GIS應用模式研究[J]. 測繪科學,2008,33(6):182-184.

[9]楊必勝,李清泉.World Wide Web(WWW)上矢量地圖數(shù)據(jù)的多分辨率傳輸算法[J].測繪學報,2005,34(4):355-360.

[10]楊必勝,李必軍.空間數(shù)據(jù)網(wǎng)絡漸進傳輸?shù)母拍?關鍵技術與研究進展[J].中國圖象圖形學報,2009(6):1018-1023.

[11]張小虎,鐘耳順,王少華,等. 多尺度空間格網(wǎng)數(shù)據(jù)的索引編碼研究[J]. 測繪通報,2014(7):35-38.

[12]閻超德,趙學勝. GIS空間索引方法述評[J]. 地理與地理信息科學,2004(4):23-26.

[13]GUTTMAN A. R-trees: A Dynamic Index Structure for Spatial Searching[C]∥Proceedings of the ACM SIGMOD International Conference on Management of Data. Boston:[s.n.]，1984: 47-54.

[14]程昌秀. 矢量數(shù)據(jù)多尺度空間索引方法的研究[J]. 武漢大學學報(信息科學版),2009(5):597-601.

[15]OOSTEROM P. The Reactive-Tree: a Storage Structure for a Seamless, Scaleless Geographic Database[C]∥Auto-Carto 10th Annual Convention. Baltimore:[s.n.]，1991.

[16]CHAN E P F, CHOW K K W. On Multi-scale Display of Geometric Objects[J]. Data&Knowledge Engineering,2002(40):91-119.

[17]DOUGLAS D H, PEUCKER T K. Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature[J].The Canadian Cartographer,1973,10(2):112-122.

[18]葉常春,周興銘. 一種支持多比例尺表示的地圖數(shù)據(jù)組織方法[J]. 計算機學報,2004(7):964-970.

[19]鄧紅艷,武芳,翟仁健,等. 一種用于空間數(shù)據(jù)多尺度表達的R樹索引結構[J]. 計算機學報,2009(1):177-184.

[20]李青元,劉曉東.WebGIS矢量空間數(shù)據(jù)壓縮方法探討[J].中國圖象圖形學報:A輯,2001,6(12):1225-1229.

[21]馮亮.面向大場景三維可視化的高精度地形數(shù)據(jù)組織[J].測繪科學,2012,37(5):119-120.

[22]彭認燦,董箭,鄭義東,等.垂距法與道格拉斯-普克法刪除冗余頂點效率的比較[J].測繪通報,2010(3):66-67.

[23]KOLESNIKOV A, FRANTI P. Data Reduction of Large Vector Graphics [J].Pattern Recognition, 2005, 38(3):381-394.

[24]RICHARDS N, WARE M. Ant Colony Optimization Applied to Map Generalization[C]∥13th Workshop of the ICA Commission on Generalisation and Multiple Representation.[S.l.]：ICA，2010.

[25]LI L, LI C, LIN Z. Data Structure of Sliced Saving Vector Data for PDA[J]. Acta Geodaetica et Cartographica Sinica，2002，31(2)：170-174.

中圖分類號：P208

文獻標識碼：B

文章編號：0494-0911(2016)02-0059-05

作者簡介：馬賢迪(1990—)，男，碩士生，研究方向為地理信息系統(tǒng)研究與應用。E-mail：madilong@163.com

基金項目：國家重大科技專項(21-Y30B05-9001-13/15)；國家863計劃(2008AA12Z203)

收稿日期：2014-12-08； 修回日期： 2015-04-08

引文格式： 馬賢迪，常原飛，喬彥友. 矢量金字塔與R樹融合模型研究[J].測繪通報，2016(2)：59-63.DOI:10.13474/j.cnki.11-2246.2016.0049.