基于層次菱形塊的球面DEM數據組織

焦健

(蕪湖市勘察測繪設計研究院，安徽蕪湖 241000)

基于層次菱形塊的球面DEM數據組織

焦健?

(蕪湖市勘察測繪設計研究院，安徽蕪湖 241000)

如何對全球DEM進行有效的組織管理，是GIS乃至數字地球面臨的首要問題之一。本文采用四叉樹菱形分層分塊的結構進行橢球面的三角格網DEM數據組織，垂直方向上依據四叉樹劃分為不同分辨率的數據層，水平方向上以菱形塊為單位組織數據。各個菱形塊根據其空間分布位置，依據線性四叉樹進行Morton編碼和空間索引，實現了海量DEM數據的高效管理。

菱形塊；球面DEM；數據組織；空間索引

1 引 言

全球DEM高程數據的組織管理面對的是以GB甚至TB計算的海量數據。如何對這些數據進行有效的組織管理并在此基礎上提高系統的效率，是GIS乃至數字地球面臨的首要問題之一。數字高程模型數據組織的目的就是要將所有相關的DEM數據通過數據庫或文件系統有效地管理起來，并根據其地理分布建立統一的空間索引，進而可以快速調度數據庫中的任意范圍的數據，實現對整個研究區域DEM數據的無縫漫游。

當前，許多實用系統都是基于文件系統的管理方式實現較大數據量的地形數據動態調度[1，2]。基于文件系統的存儲方式也基本上可以滿足地形可視化和空間分析的需要。盡管基于文件管理的方式受到網絡環境下的多用戶并發操作的局限，但考慮到在數據建立后，可視化和空間分析階段幾乎不存在多用戶同時修改一塊數據，因此基于文件系統的數據庫管理方式仍為許多用戶使用。但是也有人認為基于文件管理的方式在數據組織和空間索引、數據動態更新、網絡環境下的多用戶操作諸多方面存在局限性，他們提倡采用關系型數據庫管理系統(RDBMS)實現對海量DEM數據的管理[3]。現階段以較成熟的RDBMS技術作保障，能夠實現存儲容量與訪問速度的平衡，部分提供基于標準的SQL語句的查詢、輸出，而且安全性能較好。但關系型數據庫相對于文件存儲方式來說，以BLOB字段存儲地形數據的方式在數據的獲取操作上，并沒有實質的進步。相反，在數據的讀取速度和塊內數據的定位上還不如數據文件快速和靈活[4]。而且它不支持對非結構化數據的標準SQL，用二進制大對象管理DEM也不夠靈活。對象關系數據庫(ORDB)的出現將會較好地解決這些存在的問題，通過抽象數據類型(AbstractDataType)或行類型(RowType)擴充管理DEM文本或二進制對象，支持對自定義柵格數據的標準SQL查詢[5]。但是現有的ORDB技術離成熟完善的產業化階段還有距離，因此不能采用。

從以上的分析可以看出，對于DEM數據，是采用關系數據庫還是文件系統還沒有一個統一的認識，正所謂仁者見仁、智者見智。作者認為，對一個多部門采用的大型系統來說，應該采用數據庫系統，但對于一些小型的系統尤其是實驗系統來說，采用文件系統管理DEM數據則更為方便。本文對基于關系數據庫的DEM數據管理進行研究，包括數據庫結構、數據塊內部數據的存儲方式、數據塊的編碼和索引等。

地球是一個非常復雜的開放的巨系統，隨著觀察視野的變化，我們希望空間地理信息比例尺也自動增減。由于地圖的自動綜合受諸多因素的影響，目前比較可行的是采用多尺度空間數據庫來達到此目的。所謂多尺度就是指系統內包含幾種不同比例尺(或分辨率)的空間數據，其目的是為了適度地反映系統所關心區域的空間地理信息，以避免地物信息的過粗、失真或地物信息的負載量過大而無法使用。多尺度空間數據庫現有多庫多版本、一庫多版本、一庫一版本和LOD等四種方案[2，6，7]。對基于橢球面的格網DEM，本文采用一種混合的方式進行組織存儲:即在對全球DEM進行菱形分層分塊(四分體——菱形塊——菱形子塊)的基礎上，建立LOD模型組織全球DEM數據。

2 基于菱形塊的層次數據庫結構

為了便于存儲管理，并充分利用QTM網格自身的特點，我們將“南北”相鄰的兩個QTM三角形合并成一個菱形塊，以固定大小的菱形塊為單元組織數據，并作為數據庫的一個基本存儲單元。其在數據庫中對應一條記錄(在文件系統下對應一個數據文件)，采用四叉樹空間索引結構進行索引查詢。

如圖1所示，我們將用于地球表面剖分的正八面體的8個三角形面按南北向相鄰兩兩合并，形成4個菱形，我們稱為四分體[8]。這樣，一個八面體(相當于一個地球表面)對應4個四分體。對八面體的每個面進行遞歸QTM細分，細分后的QTM格網經過“南北”合并，也可以看成是每個四分體四叉樹細分后的菱形塊格網，如圖2所示。

圖1 八面體對應的四個四分體

一個菱形塊剖分成四個菱形子塊，如圖2所示，完全類似于規則格網四叉樹剖分，唯一的不同是，這些格網實際上并不規則，是通過QTM剖分得來的，其頂點位于球面上，顯然不共面。但這對于數據的組織并沒什么影響。通過如此剖分，整個地球表面可以用一個四叉樹來表達，全球表面對應4個四分體，每個四分體分割成下一級的4個較小的菱形塊，如此遞歸，直到滿足一定的分辨率為止。

圖2 三層QTM遞歸剖分(左)與相應的菱形塊格網層次剖分

在數據組織時，我們以QTM三角形為基礎，采用菱形分塊的層次結構組織數據，如圖3所示。整個地球表面可以通過對應的4個初始菱形塊(四分體)，其進一步劃分成若干個菱形塊，而每個菱形塊又包括若干個菱形子塊，每個菱形子塊作為全球DEM組織管理的最基本的單元，相當于傳統管理上的一幅圖。每一子塊由經過若干層剖分的QTM格網組成，在數據庫中作為一條記錄存儲(在文件系統下對應一個數據文件)，其數據的存儲格式見后節介紹。每個菱形子塊地址用其所屬的四分體編碼和Morton編碼的組合來標識，可以方便地用四叉樹進行索引，而存儲于每個菱形塊內部的數據，可以通過行列結構索引。這樣，通過“四分體——菱形子塊——行列”結構的索引，就可以唯一確定全球范圍內任意位置的DEM值。

圖3 基于四叉樹菱形塊的DEM數據分層分塊組織

為了提高系統的交互效率，滿足大范圍大數據量的地形漫游及分析的要求，有必要建立多細節LOD模型，相應地，用多分辨率DEM數據庫進行存儲管理。本文采用對全球DEM進行菱形塊分層分塊(四分體——菱形塊——菱形子塊)的基礎上，建立LOD模型組織全球DEM數據。不同的LOD在數據庫中位于不同的層，其中，最底層的DEM為基本數據庫層，屬于原始數據，其分辨率最高，其余各層的DEM數據則可以視具體情況組織。本文首先通過原始數據構建較少的LOD層，再用這些基本的LOD層派生一些LOD分層，依此組建由遠到近、由小到大一系列不同詳細程度的LOD分層數據。這樣，不僅可以通過建立不同分辨率的數據庫層獲取數據庫級的LOD，還可以借助于快速處理算法實時地從高分辨率數據自動地抽取相鄰層次中間分辨率的數據。其數據庫的體系結構如圖4所示。

圖4 層次結構的數據庫體系

3 橢球面三角格網DEM的數據結構

對于規則格網DEM數據來說，目前多以行列矩陣的格式存儲，該格式在每個格網頂點只需存儲該點的高程值。對于基于橢球面三角格網DEM來說，由于其格網的規則性，任意一個格網頂點的坐標可以根據該頂點高程值的存儲位置計算出來，而且其與相鄰頂點之間的拓撲關系也隱含在它們的存儲位置中，因此完全可以采用類似于規則格網的存儲方式。具體到全球三角格網DEM，存儲時以菱形子塊作為數據存儲的基本單位，每個菱形子塊在數據庫中對應一條記錄，在文件系統下對應一個數據文件，菱形子塊的大小決定了數據文件的大小。對于每個菱形子塊(類似于一幅圖)，只需存儲元數據(包括格網角點的坐標、菱形格網的剖分層數、行列數、空間參考坐標系等)和高程值串即可。其中高程值串采用blob(Binary Large Object)字段存儲，一個菱形子塊對應一個大二進制blob文件。由于大多數關系數據庫都支持blob字段，因此，全球DEM數據可以使用大多數的關系數據庫和對象關系數據庫方便地進行存儲[9]。

在每一個菱形塊內，格網點的個數均為(2n＋1)× (2n＋1)，在高程值串中，格網點高程值的存儲順序采用如圖5所示的次序。

采用這種格式不僅結構簡單，占用存儲空間少，而且還可以借助其他簡單的柵格數據處理方法進行進一步的數據壓縮處理，如自適應行程編碼、四叉樹方法、多級格網法等。

圖5 三角格網點在存儲單元中的存儲次序

4 基于線性四叉樹的菱形塊索引及編碼

整個地球表面可以用一個線性四叉樹來表達，存儲時只需紀錄其葉結點的位置即可。其葉結點的位置用菱形塊編碼來標識，通過空間Z型填充曲線來索引，如圖6所示。

圖6 菱形塊的四進制Morton碼與其Z型空間索引曲線

每個基菱形塊遞歸細分成較小的菱形塊，由其所屬的一個四分碼和Morton碼來標識。菱形塊L的編碼表示為:L＝DM。其中D為該菱形塊所在基菱形塊的四分碼，M為該菱形塊的Morton碼。每個基菱形塊根據其所在位置由一個四分碼(0、1、2、3)來標識，其標識規則為:

對基菱形塊進行遞歸剖分，會產生4個新的較小的菱形塊，用Morton碼標識。對于每個基菱形塊來說，進行一次四叉樹分割，會產生4個新的小菱形塊，如圖6右所示分別用標號0、1、2、3來表示左、下、上、右4個小菱形塊(對應四個子象限)，每個小的菱形塊繼續遞歸細分，產生新的更小的菱形塊，通過增加標號位數來標識，這種標號即為四進制的Morton碼(用MQ表示)。Morton碼的每一位字數都是不大于3的四進制數，并且每經過一次分割，增加一位數字，分割的次數越多，所得到的子區域(菱形塊)越小，相應的Morton碼位數越大。最后小菱形塊的Morton碼是所有各位上相應象限值相加，即:

[1] 陳剛，萬剛，游雄.全球地形可視化方案的設計和實踐[J].系統仿真學報，2001，13增刊，P 282～285

[2] 郭建中，歐陽，魏海平等.基于文件與基于數據庫的格網索引[J].測繪學院學報，2002，19(3):P220～223

[3] 鐘正，朱慶.一種基于海量數據庫的DEM動態可視化方法[J].海洋測繪，2003，23(2):P9～19

[4] 郭建忠，安敏.GIS中多比例尺地理數據的管理和應用[J].解放軍測繪學院學報，1999，16(1):P47～49

[5] 李峻，邊馥苓，談曉軍.DEM及紋理圖像的集成數據庫研究[J].測繪科學，2000，25(3):P25～28

[6] 齊清，張安定.關于多比例尺GIS中數據庫多重表達的幾個問題的研究[J].地理研究，1999，18(2):P16～170

[7] 王晏民，李德仁，龔健雅.一種多比例尺GIS方案及其數據模型[J].武漢大學學報(信息科學版)，2003，28(4): P458～462

[8] White.D.，Global Grids From Recursive Diamond Subdivisions of The Surface of an Octahedron or Icosahedron.Environmental Monitoring and Assessment，2000，4(1):P93～103

[9] 王永君，龔健雅.一種基于COM的數字高程模型可視化管理模式[J].系統仿真學報，2001，13增刊:P32～35

Data Organization of Spherical DEM based on hierarchical Diamonds

Jiao Jian
(Wuhu Geotechnical and Survey Design Institute，Wuhu 241000，China)

One of the primary problems that GIS and even the Digital Earth were faced to is how to organize and manage global DEM effectively.In this paper，The Ellipsoidal Triangular Network blocks data are organized on the Diamonds quad－tree.Data in vertical direction are divided into different resolution levels according to quad－tree，and in horizontal direction，Diamonds are regarded as basic units.Each Diamonds is libelled and indexed using linear quadtree Morton code according to its location.Thus we achieve efficient management of massive DEM data.

Diamonds；Spherical DEM；Data Organization；spatial index

1672－8262(2011)02－40－03

P208

A

2010—07—30

焦健(1968—)，男，工程師，主要從事測繪與GIS數據處理工作。