MGIS中地圖柵格數據組織模型研究*

林啟惠 郭 暉

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

?

MGIS中地圖柵格數據組織模型研究*

林啟惠1郭 暉2

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

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

MGIS; 瓦片金字塔; 四叉樹; 地圖柵格數據

Class Number TP391

1 引言

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

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

2 瓦片金字塔模型

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

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

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

g0=gm×rm

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

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

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

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

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

3 線性四叉樹

3.1 線性四叉樹的構建

四叉樹結構是樹形結構的一種,它的每個子節點最多只有四個分子[4],能夠實現空間遞歸分解的層次數據結構,所以可以利用瓦片地圖金字塔建立到線性四叉樹的映射完成線性四叉樹的構建,一個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]內的二進制值間是互相映射的,且若一個結點A的編碼比其父結點少尾部兩位。

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

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

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

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

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

3.3 線性四叉樹的操作

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

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

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

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

4 地理柵格數據組織模型

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

4.1 地理柵格數據的獲取

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

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

4.2 地理柵格數據的組織

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

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

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

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

4.3 地理柵格數據的索引

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

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

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

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

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

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

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

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

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

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

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

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

5 結語

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

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

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

[3] 王家耀.地理信息系統的發展及其在信息戰中的應用[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的空間數據模型[J].浙江工程學院學報,1999,2(8):113-115.

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

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

[10] 汪璟玢.一種結合空間聚類算法的R樹優化算法[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日

林啟惠,女,助教,研究方向:網絡及數據庫技術。郭暉,女,講師,研究方向:計算機應用技術。

TP391

10.3969/j.issn1672-9730.2015.04.027