焦健

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

基于層次菱形塊的球面DEM數(shù)據(jù)組織

焦健?

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

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

菱形塊；球面DEM；數(shù)據(jù)組織；空間索引

1 引 言

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

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

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

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

2 基于菱形塊的層次數(shù)據(jù)庫結(jié)構(gòu)

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

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

圖1 八面體對應(yīng)的四個四分體

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

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

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

圖3 基于四叉樹菱形塊的DEM數(shù)據(jù)分層分塊組織

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

圖4 層次結(jié)構(gòu)的數(shù)據(jù)庫體系

3 橢球面三角格網(wǎng)DEM的數(shù)據(jù)結(jié)構(gòu)

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

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

采用這種格式不僅結(jié)構(gòu)簡單，占用存儲空間少，而且還可以借助其他簡單的柵格數(shù)據(jù)處理方法進行進一步的數(shù)據(jù)壓縮處理，如自適應(yīng)行程編碼、四叉樹方法、多級格網(wǎng)法等。

圖5 三角格網(wǎng)點在存儲單元中的存儲次序

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

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

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

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

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

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

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

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

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

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

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

[7] 王晏民，李德仁，龔健雅.一種多比例尺GIS方案及其數(shù)據(jù)模型[J].武漢大學(xué)學(xué)報(信息科學(xué)版)，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的數(shù)字高程模型可視化管理模式[J].系統(tǒng)仿真學(xué)報，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數(shù)據(jù)處理工作。