林啟惠 郭 暉

(1.秦皇島職業(yè)技術(shù)學(xué)院思政部 秦皇島 066100)(2.海軍工程大學(xué)電子工程學(xué)院 武漢 430033)

?

MGIS中地圖柵格數(shù)據(jù)組織模型研究*

林啟惠1郭 暉2

(1.秦皇島職業(yè)技術(shù)學(xué)院思政部 秦皇島 066100)(2.海軍工程大學(xué)電子工程學(xué)院 武漢 430033)

研究瓦片金字塔模型和四叉樹技術(shù)基礎(chǔ)上,提出了一種地理地圖柵格數(shù)據(jù)模型,該模型將地圖柵格數(shù)據(jù)的使用分為獲取、組織和索引三個(gè)步驟,并分析研究各步驟主要技術(shù)和方法,并利用瓦片金字塔模型和四叉樹技術(shù)完成柵格數(shù)據(jù)組織。該模型能夠高效完成柵格數(shù)據(jù)的組織和其他操作,具有高效實(shí)用特點(diǎn)。

MGIS; 瓦片金字塔; 四叉樹; 地圖柵格數(shù)據(jù)

Class Number TP391

1 引言

軍事地理信息系統(tǒng)(military geographic information system,MGIS)是利用計(jì)算機(jī)系統(tǒng),運(yùn)用系統(tǒng)工程和信息科學(xué)的理論和方法,分析利用軍事地理環(huán)境信息的軍事空間信息系統(tǒng),是數(shù)字化戰(zhàn)場建設(shè)的基本技術(shù),是數(shù)字化戰(zhàn)場建設(shè)的信息平臺(tái),是基于信息系統(tǒng)作戰(zhàn)能力建設(shè)的重要方面[1]。在MGIS系統(tǒng)中,如何高效、準(zhǔn)確地進(jìn)行地理地圖的組織和顯示是一項(xiàng)重要基礎(chǔ)性工作。

文章主要對(duì)MGIS系統(tǒng)中地理柵格數(shù)據(jù)的組織模型進(jìn)行研究,構(gòu)建了獲取、組織和索引的三步完成地圖組織,其中地理數(shù)據(jù)組織具體利用四叉樹方法建立地圖瓦片金字塔模型,實(shí)現(xiàn)系統(tǒng)中地圖數(shù)據(jù)的高效和準(zhǔn)確組織。

2 瓦片金字塔模型

在地理信息圖形數(shù)據(jù)的組織和管理模式設(shè)計(jì)中,為了提高系統(tǒng)地形地圖的直觀顯示能力,主要采用更加適用于模擬空間場的柵格數(shù)據(jù)[2]。

瓦片金字塔模型是進(jìn)行柵格數(shù)據(jù)組織的重要模型,并得到廣泛應(yīng)用。瓦片地圖金字塔模型是一種多分辨率層次模型,從瓦片金字塔的底層到頂層,分辨率越來越低,但表示的地理范圍不變[3]。瓦片地圖金字塔模型在GIS系統(tǒng)中地形地圖構(gòu)建中柵格數(shù)據(jù)組織中有廣泛應(yīng)用。瓦片地圖是指將固定范圍的某一比例尺下的地圖按照指定的尺寸(通常為128*128像素或256*256像素)切成若干行和列的正方形柵格圖片,切圖獲得的正方形柵格圖片即為瓦片地圖。按照金字塔的思想,采用倍率方法構(gòu)建一個(gè)多分辨率的層次模型,金字塔每一層的柵格數(shù)據(jù)切割為一定大小的瓦片,每層都由大小相同瓦片矩陣構(gòu)成。

假設(shè)一個(gè)倍率為r,總層數(shù)為m的瓦片金字塔,那么第N層瓦片與第N+1層瓦片像素相同,第N層的分辨率為第N+1層的r倍,第M層分辨率為g,那么第0層瓦片即最底層的分辨率為

g0=gm×rm

該公式可以推廣到一般層次,一個(gè)倍率為2的,總層為2的瓦片圖片金字塔如圖1所示。

圖1 一個(gè)典型的瓦片金字塔

地圖瓦片拓?fù)潢P(guān)系是指地圖瓦片與其他地圖瓦片在滿足拓?fù)鋷缀螌W(xué)原理的空間數(shù)據(jù)間相互關(guān)系,具體來說就是圖形元素間相互空間上的連接、鄰接關(guān)系,而并不考慮元素的具體位置。

作為一個(gè)倍率為2的瓦片地圖金字塔,其地圖瓦片拓?fù)潢P(guān)系主要包括同一層間的鄰接關(guān)系,上下冊(cè)間的雙親和孩子關(guān)系。其中,鄰接關(guān)系主要是東、南、西、北四個(gè)方向的鄰接瓦片,而雙親和孩子的關(guān)系包括東南、西南、西北、東北四個(gè)派生瓦片。

可以發(fā)現(xiàn),該拓?fù)潢P(guān)系與數(shù)據(jù)結(jié)構(gòu)中四叉樹描述非常相似,唯一不同是瓦片地圖金字塔中鄰接和派生關(guān)系都有方向性,而在普通的四叉樹中派生或鄰接結(jié)點(diǎn)(葉子)是等價(jià)的。對(duì)四叉樹引入更多信息描述,通過對(duì)四叉樹的分析實(shí)現(xiàn)對(duì)瓦片地圖金字塔的分析和研究。

3 線性四叉樹

3.1 線性四叉樹的構(gòu)建

四叉樹結(jié)構(gòu)是樹形結(jié)構(gòu)的一種,它的每個(gè)子節(jié)點(diǎn)最多只有四個(gè)分子[4],能夠?qū)崿F(xiàn)空間遞歸分解的層次數(shù)據(jù)結(jié)構(gòu),所以可以利用瓦片地圖金字塔建立到線性四叉樹的映射完成線性四叉樹的構(gòu)建,一個(gè)n層瓦片地圖金字塔與四叉樹的映射圖如圖2所示。

其具體的映射步驟為:

1) 對(duì)m層瓦片金字塔,建立一個(gè)層次D=m的線性四叉樹,確保瓦片地圖金字塔的第i層和線性四叉樹的第n-i層瓦片和結(jié)點(diǎn)對(duì)應(yīng);

圖2 金字塔與四叉樹對(duì)應(yīng)關(guān)系

2) 對(duì)頂層的瓦片地圖金字塔不進(jìn)行分割,直接與四叉樹根結(jié)點(diǎn)對(duì)應(yīng);

3) 除頂層外每層瓦片地圖進(jìn)行分割,從第m-1層金字塔開始,將該曾瓦片地圖按照派生拓?fù)潢P(guān)系分解為東南、西南、西北、東北四個(gè)瓦片地圖,對(duì)應(yīng)于根結(jié)點(diǎn)上的四個(gè)兒子結(jié)點(diǎn);

4) 依照3)方法對(duì)各層進(jìn)行分割,直到第0層。

3.2 線性四叉樹的編碼

對(duì)線性四叉樹進(jìn)行編碼是為了提高線性四叉樹的索引效率,從而提高瓦片地圖金字塔的存在便利性,這里介紹一種最常見的編碼方式。用00,01,10,11分別表示西南、西北、東南、東北四個(gè)方向,每一層次較上一層次在編碼尾部增加兩位編碼表示該瓦片是上層結(jié)點(diǎn)哪個(gè)方位方向派生而來的,具體步驟如圖3所示。

圖3 四叉樹編碼步驟

采用這種編碼方式可以攜帶充分信息量,同時(shí)具備以下特征:

1) 對(duì)應(yīng)特征。線性四叉樹深度為n的結(jié)點(diǎn)與[0,4n-1]內(nèi)的二進(jìn)制值間是互相映射的,且若一個(gè)結(jié)點(diǎn)A的編碼比其父結(jié)點(diǎn)少尾部兩位。

2) 位置特征。根據(jù)派生方向與編碼的對(duì)應(yīng)關(guān)系,提取該二進(jìn)制編碼奇數(shù)位編碼和偶數(shù)位編碼稱為(Mo,Me),以及其對(duì)應(yīng)的十進(jìn)制數(shù)值(i,j),根據(jù)分析可以知道Mo、i代表結(jié)點(diǎn)瓦片地圖在平面內(nèi)由南向北的順序位置,Me、j則表示結(jié)點(diǎn)瓦片地圖在平面內(nèi)由西向東的順序位置,即Mo對(duì)應(yīng)的是結(jié)點(diǎn)瓦片位置的南北向分解后的位置編碼,Me對(duì)應(yīng)的是結(jié)點(diǎn)瓦片位置的東西向分解后的位置編碼,空間編碼與位置編碼的對(duì)應(yīng)關(guān)系如圖4所示。

圖4 空間編碼與位置編碼對(duì)應(yīng)關(guān)系

3) 存在特征。某瓦片地圖結(jié)點(diǎn)的不同尺寸鄰域存在,那與其相同尺寸的鄰域必然存在。

4) 鄰域特征。某瓦片地圖結(jié)點(diǎn)的相同尺寸的鄰域存在,則該瓦片地圖結(jié)點(diǎn)與其相鄰結(jié)點(diǎn)存在數(shù)學(xué)運(yùn)算關(guān)系。

在完成瓦片地圖空間編碼的同時(shí),根據(jù)不同的應(yīng)用類型和方向,可以加入其他信息編碼,例如深度信息編碼,分辨率編碼,尺寸編碼和區(qū)域編碼等。

3.3 線性四叉樹的操作

在瓦片地圖金字塔模型中可以將針對(duì)地形地圖的操作轉(zhuǎn)化為對(duì)應(yīng)線性四叉樹的操作,由于對(duì)地形地圖操作一般不會(huì)涉及到刪除、添加等,主要集中在查看、平移等,對(duì)于四叉樹來說,主要就是實(shí)現(xiàn)對(duì)四叉樹的索引,四叉樹索引包括Skyline[5]等諸多算法,這里簡要介紹地形地圖操作和四叉樹索引對(duì)應(yīng)操作的關(guān)系。

1) 地圖平移。地圖在平移過程中,其分辨率不變,主要是地圖的中心點(diǎn)發(fā)生改變,那么對(duì)于四叉樹主要進(jìn)行四叉樹同層間結(jié)點(diǎn)的查找,以及鄰接域的確定。

2) 地圖縮放。地圖在縮放過程中,其中心點(diǎn)不變,主要完成分辨率變化,根據(jù)縮放比例大小,確定四叉樹層間切換,以及中心結(jié)點(diǎn)的確定。

3) 地圖補(bǔ)邊。當(dāng)?shù)貓D顯示不能充分時(shí),特別對(duì)于邊緣不能充分填充,應(yīng)當(dāng)采用四叉樹中鄰域的求解方法。

4 地理柵格數(shù)據(jù)組織模型

地理柵格數(shù)據(jù)組織模型主要利用瓦片金字塔模型和四叉樹技術(shù),從地圖數(shù)據(jù)組織,數(shù)據(jù)組織和數(shù)據(jù)操作三個(gè)方面著手,一是基礎(chǔ)數(shù)據(jù)獲取,主要包括基礎(chǔ)地圖柵格數(shù)據(jù)的獲取和存儲(chǔ)模式,二是數(shù)據(jù)組織方式,主要介紹瓦片地圖數(shù)據(jù)的四叉樹編碼和相關(guān)信息的存儲(chǔ),三是地圖操作設(shè)計(jì),主要包括四叉樹索引技術(shù)。

4.1 地理柵格數(shù)據(jù)的獲取

地理數(shù)據(jù)是地理信息系統(tǒng)重要部分,其數(shù)據(jù)獲取工作占有重要地位。為了提高工作效率,降低成本,有效利用已有空間數(shù)據(jù),需要利用不同來源數(shù)據(jù)。目前,在地理信息圖形數(shù)據(jù)的組織和管理模式設(shè)計(jì)中,空間數(shù)據(jù)模型主要分矢量數(shù)據(jù)和柵格數(shù)據(jù)兩種[6]。矢量數(shù)據(jù)描述地理要素的空間特點(diǎn)是通過離散的位置坐標(biāo)來表示的,利用歐幾里德幾何學(xué)中的點(diǎn)、線、面及其組合體表示地理實(shí)體的空間分布。柵格數(shù)據(jù)模型是指將空間分割成有規(guī)則的網(wǎng)格,在各個(gè)網(wǎng)格上給出相應(yīng)的屬性來表示空間實(shí)體的數(shù)據(jù)組織形式。為了提高系統(tǒng)地形地圖的直觀顯示能力,主要采用更加適用于模擬空間場的柵格數(shù)據(jù)。

柵格數(shù)據(jù)從來源可以分為各種遙感數(shù)據(jù)、航測(cè)數(shù)據(jù)、航空雷達(dá)數(shù)據(jù)等,從類型分為索引圖,分類圖,雙字節(jié)圖等,這里系統(tǒng)使用來自Google Earth的地理柵格數(shù)據(jù),它是Google公司于2005年6月向全球退出的免費(fèi)衛(wèi)星影像軟件[7],以各種分辨率的衛(wèi)星影像為最基礎(chǔ)數(shù)據(jù),數(shù)據(jù)格式采用JPEG的透明真彩色疊加圖。系統(tǒng)通過使用專業(yè)軟件獲取Google Earth的地理柵格數(shù)據(jù)包括JPEG格式的瓦片圖片和包含高程、經(jīng)度和維度的信息數(shù)據(jù)。

4.2 地理柵格數(shù)據(jù)的組織

圖像數(shù)據(jù)分塊和分層技術(shù)是提高地圖數(shù)據(jù)讀取的有效辦法,柵格數(shù)據(jù)處理是典型的分塊技術(shù),分層技術(shù)是對(duì)圖形進(jìn)行抽象形成多分辨率的圖像層數(shù)據(jù)。金字塔模型是一種典型的柵格數(shù)據(jù)組織模型,而柵格數(shù)據(jù)存儲(chǔ)主要分為數(shù)據(jù)庫和文件兩種存儲(chǔ)方式[8]。

柵格數(shù)據(jù)組織的金字塔模型主要包括瓦片金字塔模型,小波金字塔模型,多金字塔模型,非一致分層分塊金字塔模型和三重金字塔模型等[9]。瓦片金字塔模型在上節(jié)已經(jīng)作了詳細(xì)介紹,這里簡要介紹另外四種金字塔模型。小波金字塔模型的基本思想是將小波變換與金字塔相結(jié)合,一張高分辨率的圖像經(jīng)過一次小波變換后分為近似的子圖和三種高分辨率的子圖,而近似子圖繼續(xù)進(jìn)行小波變換,繼續(xù)迭代到結(jié)束構(gòu)建小波金字塔。多金字塔模型是對(duì)原主體金字塔模型進(jìn)行分割為多個(gè)子模型,每個(gè)子模型代表的地理數(shù)據(jù)邏輯范圍是主體金字塔某曾中一個(gè)瓦片所占的邏輯范圍,從而實(shí)現(xiàn)子模型各層瓦片與主體金字塔瓦片的無縫連接。非一致分層分塊金字塔模型各層之間不采用固定分辨率,根據(jù)原始數(shù)據(jù)的分辨率構(gòu)建金字塔,各層瓦片大小非一致,采用緩存交替工作、多線程預(yù)讀圖像塊方法。三重金字塔模型是由根據(jù)命名規(guī)則建立的柵格文件構(gòu)建的一重金字塔,索引圖層根據(jù)命名規(guī)則建立關(guān)聯(lián)字段構(gòu)建的一重金字塔和文件內(nèi)部借助ArcGIS自動(dòng)生成的一重金字塔共同構(gòu)建。

作為MGIS系統(tǒng)由于軍事保密需要,大多在單機(jī)運(yùn)行或在小型局域網(wǎng),且地形地圖相對(duì)固定,主要集中于中國沿海海區(qū)或某些戰(zhàn)區(qū),地理信息量相對(duì)較少,所以基于上述應(yīng)用要求,采用瓦片金字塔模型進(jìn)行地形地理柵格數(shù)據(jù)組織。

地形地理柵格數(shù)據(jù)的管理和存儲(chǔ)主要基于文件和基于數(shù)據(jù)庫兩種類型,基于文件的方式主要針對(duì)小數(shù)據(jù)量設(shè)計(jì),數(shù)據(jù)存儲(chǔ)在本地文件中,不涉及數(shù)據(jù)庫操作,具有結(jié)構(gòu)簡單、維護(hù)費(fèi)用少、技術(shù)相對(duì)承受、在小數(shù)據(jù)量應(yīng)用效率較高等優(yōu)勢(shì),采用順序文件、索引文件、直接文件等多種方式,適用于存儲(chǔ)更新周期快而對(duì)數(shù)據(jù)本身操作少的情況?；跀?shù)據(jù)庫柵格存儲(chǔ)方式采用多個(gè)獨(dú)立柵格目錄、若干柵格數(shù)據(jù)集和若干金字塔數(shù)據(jù)層的三層存儲(chǔ)組織結(jié)構(gòu),具有良好的安全措施和數(shù)據(jù)恢復(fù)機(jī)制,還提供對(duì)連續(xù)的柵格數(shù)據(jù)的快速訪問、支持事務(wù)處理和并發(fā)控制,安全機(jī)制。系統(tǒng)采用基于數(shù)據(jù)庫的柵格數(shù)據(jù)存儲(chǔ)模式。

4.3 地理柵格數(shù)據(jù)的索引

地理空間索引是依據(jù)地理要素(或?qū)ο?的空間位置、形狀或地理對(duì)象之間的某種空間關(guān)系,按一定的順序排列的一種數(shù)據(jù)結(jié)構(gòu),包括地理對(duì)象的標(biāo)識(shí)、外接矩形和指向地理對(duì)象的指針等三個(gè)部分。地理信息對(duì)象采用柵格數(shù)據(jù)格式,基于數(shù)據(jù)庫存儲(chǔ)方式,需要完成對(duì)存儲(chǔ)數(shù)據(jù)檢索查詢。

對(duì)于地理信息對(duì)象柵格數(shù)據(jù)的常見空間索引方法包括R樹和四叉樹。其中,R樹最早由GutTman在1984年提出[10],后逐步形成由R樹,R+樹、R3樹、Hibert R樹、SR樹組成的R樹系列空間索引,它直接對(duì)地理空間中占據(jù)一定范圍的地理要素進(jìn)行索引,又具備一般滿二叉樹B樹特點(diǎn),具有很強(qiáng)的靈活性、可調(diào)節(jié)性、無需預(yù)知整個(gè)空間對(duì)象所處空間范圍,同時(shí)具備B樹相似結(jié)構(gòu)和特征,從而能很好支持?jǐn)?shù)據(jù)庫的事務(wù)、滾回和并發(fā)功能。四叉樹屬于基于空間劃分組織索引結(jié)構(gòu)的一類索引機(jī)制,將已知范圍的空間化成四個(gè)相等的子空間,并類似繼續(xù)逐層劃分,四叉樹特點(diǎn)是可以用順序存儲(chǔ)的線性表表示索引,較小內(nèi)存需求量,插入和刪除更加簡單。在基于通過ODBC或ADO外掛在現(xiàn)有關(guān)系數(shù)據(jù)庫上的,一般采用查詢速度快、結(jié)構(gòu)相對(duì)簡單的四叉樹索引。

對(duì)于瓦片金字塔模型的四叉樹構(gòu)建的步驟為:

1) 對(duì)于n層瓦片金字塔,建立一個(gè)D=n的線性四叉樹,使得瓦片金字塔的第i層Li與線性四叉樹的第n-i層像元對(duì)應(yīng);

2) 對(duì)瓦片金字塔的頂層圖像不進(jìn)行分割,使其直接與線性四叉樹的根節(jié)點(diǎn)對(duì)應(yīng);

3) 對(duì)頂層之外各層圖像進(jìn)行瓦片分割,按照第2節(jié)要求從西南SW、西北NW、東南SE、東北NE四個(gè)方向進(jìn)行劃分切割;

4) 按照上述方法分割到第0層。

假設(shè)四叉樹中任一層i的節(jié)點(diǎn)編碼H為H1H2…Hi-1Hi,其中Hi∈{SiWiSiEiNiWiNiEi},SW,SE,NW,NE分別用00,01,10,11表示,每層劃分的子層節(jié)點(diǎn)編碼應(yīng)當(dāng)附上上層父親節(jié)點(diǎn)編碼。這種編碼方式能夠較好顯示該節(jié)點(diǎn)的深度信息、分辨率信息、區(qū)域信息和位置信息。具體來說,應(yīng)有:

1) 深度信息:假設(shè)頂層節(jié)點(diǎn)編碼為00,那么四叉樹的任一節(jié)點(diǎn)編碼H的層次深度D=length(H)/2-1;

2) 分辨率信息:假設(shè)根節(jié)點(diǎn)像元的分辨率為R0,那么四叉樹第i層對(duì)應(yīng)像元分辨率為Ri=2Di×R0;

3) 區(qū)域信息:節(jié)點(diǎn)編碼H為H1H2…Hi-1Hi,那么其父節(jié)點(diǎn)編碼為H1H2…Hi-1,依次類推得到任一級(jí)父親節(jié)點(diǎn)編碼;

3) 位置信息:按照上節(jié)四叉樹節(jié)點(diǎn)編碼的規(guī)定進(jìn)行編碼奇數(shù)偶數(shù)分解,得到相應(yīng)西東和南北方向相對(duì)位置。

5 結(jié)語

本文提出了一種MGIS系統(tǒng)中的地理地圖柵格數(shù)據(jù)模型,該模型將地圖柵格數(shù)據(jù)的使用分為獲取、組織和索引三個(gè)步驟,并分析研究各步驟主要技術(shù)和方法,重點(diǎn)研究了地圖柵格數(shù)據(jù)組織中的瓦片金字塔模型和四叉樹技術(shù)。該模型能夠高效完成柵格數(shù)據(jù)的組織和其他地圖操作,具有高效實(shí)用特點(diǎn)。

[1] 王家耀.軍事地理信息系統(tǒng)(MGIS)在現(xiàn)代化戰(zhàn)爭中的作用及其發(fā)展[J].信息工程大學(xué)學(xué)報(bào),2000,1(4):102-105.

[2] 李玉陽,晉朝勃,笪良龍,等.MGIS技術(shù)在海軍信息戰(zhàn)中的應(yīng)用[J].指揮控制與仿真,2007,29(3):117-120.

[3] 王家耀.地理信息系統(tǒng)的發(fā)展及其在信息戰(zhàn)中的應(yīng)用[J].信息工程大學(xué)學(xué)報(bào),2004,5(2):103-107.

[4] 李啟清,等.一種可擴(kuò)展四叉樹結(jié)構(gòu)及其先序遍歷算法[J].計(jì)算機(jī)工程與應(yīng)用,2003(28):22-41.

[5] Scott T. Shipley, Ira A. Graffman, Joseph K. Ingram. GIS Applications in Climate and Meteorology[J]. 2000(1):56-59.

[6] Paul A. Longley. The academic success of GIS in geography: Problems and prospects[J]. Journal of Geographical System,2000:231-238.

[7] 嚴(yán)寒冰,鄭加成,等.GIS的空間數(shù)據(jù)模型[J].浙江工程學(xué)院學(xué)報(bào),1999,2(8):113-115.

[8] 張宏.地理信息系統(tǒng)算法基礎(chǔ)[M].北京:科學(xué)出版社,2001:50-55.

[9] 徐開明.地理信息公共服務(wù)平臺(tái)建設(shè)與現(xiàn)代測(cè)繪服務(wù)模式[J].地理信息世界,20114(3):23-27.

[10] 汪璟玢.一種結(jié)合空間聚類算法的R樹優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2014(5):112-115.

Research on the Model of Map Raster Data Organization in MGIS

LIN Qihui1GUO Hui2

(1. Department of Ideological and Political, Qinhuangdao Vocational and Technical College, Qinhuangdao 066100) (2. College of Electronics Engineering, Naval University of Engineening, Wuhan 430033)

On the base of the research of tile pyramid model and the quad-tree technology, a geographic map raster data model is proposed, which uses the map of raster data with three steps that capture, organize and index, and each step of major techniques and methods is analyzed, and tile pyramid model and quadtree technology are used to complete raster data organization. The model can efficiently complete raster data organization and other operations, is efficient and practical.

MGIS, tile pyramid, quadtree, map raster data

2014年10月14日,

2014年11月21日

林啟惠,女,助教,研究方向:網(wǎng)絡(luò)及數(shù)據(jù)庫技術(shù)。郭暉,女,講師,研究方向:計(jì)算機(jī)應(yīng)用技術(shù)。

TP391

10.3969/j.issn1672-9730.2015.04.027