林啟惠 郭 暉

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

?

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

林啟惠1郭 暉2

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

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

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

Class Number TP391

1 引言

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

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

2 瓦片金字塔模型

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

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

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

g0=gm×rm

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

圖1 一個典型的瓦片金字塔

地圖瓦片拓撲關系是指地圖瓦片與其他地圖瓦片在滿足拓撲幾何學原理的空間數(shù)據(jù)間相互關系,具體來說就是圖形元素間相互空間上的連接、鄰接關系,而并不考慮元素的具體位置。

作為一個倍率為2的瓦片地圖金字塔,其地圖瓦片拓撲關系主要包括同一層間的鄰接關系,上下冊間的雙親和孩子關系。其中,鄰接關系主要是東、南、西、北四個方向的鄰接瓦片,而雙親和孩子的關系包括東南、西南、西北、東北四個派生瓦片。

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

3 線性四叉樹

3.1 線性四叉樹的構建

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

其具體的映射步驟為:

1) 對m層瓦片金字塔,建立一個層次D=m的線性四叉樹,確保瓦片地圖金字塔的第i層和線性四叉樹的第n-i層瓦片和結點對應;

圖2 金字塔與四叉樹對應關系

2) 對頂層的瓦片地圖金字塔不進行分割,直接與四叉樹根結點對應;

3) 除頂層外每層瓦片地圖進行分割,從第m-1層金字塔開始,將該曾瓦片地圖按照派生拓撲關系分解為東南、西南、西北、東北四個瓦片地圖,對應于根結點上的四個兒子結點;

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

3.2 線性四叉樹的編碼

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

圖3 四叉樹編碼步驟

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

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

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

圖4 空間編碼與位置編碼對應關系

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

4) 鄰域特征。某瓦片地圖結點的相同尺寸的鄰域存在,則該瓦片地圖結點與其相鄰結點存在數(shù)學運算關系。

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

3.3 線性四叉樹的操作

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

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

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

3) 地圖補邊。當?shù)貓D顯示不能充分時,特別對于邊緣不能充分填充,應當采用四叉樹中鄰域的求解方法。

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

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

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

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

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

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

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

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

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

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

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

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

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

對于瓦片金字塔模型的四叉樹構建的步驟為:

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

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

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

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

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

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

2) 分辨率信息:假設根節(jié)點像元的分辨率為R0,那么四叉樹第i層對應像元分辨率為Ri=2Di×R0;

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

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

5 結語

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

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

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

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

[4] 李啟清,等.一種可擴展四叉樹結構及其先序遍歷算法[J].計算機工程與應用,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] 嚴寒冰,鄭加成,等.GIS的空間數(shù)據(jù)模型[J].浙江工程學院學報,1999,2(8):113-115.

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

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

[10] 汪璟玢.一種結合空間聚類算法的R樹優(yōu)化算法[J].計算機工程與應用,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)絡及數(shù)據(jù)庫技術。郭暉,女,講師,研究方向:計算機應用技術。

TP391

10.3969/j.issn1672-9730.2015.04.027