焦健

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

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

焦健?

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

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

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

1 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[7] 王晏民，李德仁，龔健雅.一種多比例尺GIS方案及其數(shù)據(jù)模型[J].武漢大學(xué)學(xué)報(bào)(信息科學(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é)報(bào)，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—)，男，工程師，主要從事測(cè)繪與GIS數(shù)據(jù)處理工作。