面向地理對象多尺度表達(dá)的剖分編碼方法研究

楊宇博,程承旗,宋樹華

(1.北京大學(xué)遙感與地理信息系統(tǒng)研究所,北京100871;2.北京大學(xué)城市與環(huán)境學(xué)院,北京100871)

面向地理對象多尺度表達(dá)的剖分編碼方法研究

楊宇博1,2,程承旗1,宋樹華1

(1.北京大學(xué)遙感與地理信息系統(tǒng)研究所,北京100871;2.北京大學(xué)城市與環(huán)境學(xué)院,北京100871)

現(xiàn)有模型對影像數(shù)據(jù)中的地理對象進(jìn)行多尺度表達(dá)很困難,鑒于全球剖分模型在對地理對象表達(dá)時所具備的全球唯一性、層次性、多尺度性、編碼具有地學(xué)含義等特點(diǎn),提出了面向地理對象多尺度表達(dá)的剖分編碼方法,目的是對地理對象賦予統(tǒng)一的剖分編碼,使編碼具有地學(xué)含義和多尺度特性。實(shí)驗(yàn)證明,面向地理對象多尺度表達(dá)的剖分編碼方法可以滿足地理對象多尺度剖分化表達(dá)的需要,為新一代 GIS解決地理信息“尺度鴻溝”問題,向用戶提供“連續(xù)”、“自適應(yīng)”的表達(dá)尺度奠定了基礎(chǔ)。

GIS;全球剖分模型;EMD模型;多尺度表達(dá);剖分編碼

0 引言

尺度從技術(shù)上影響地理數(shù)據(jù)的內(nèi)容,也影響著空間信息的表達(dá)、分析并最終影響人類認(rèn)知,因此可以說尺度問題滲透在地理信息科學(xué)的各個方面。盡管目前GIS不論在技術(shù)上還是在應(yīng)用上都取得很大的進(jìn)步,但由于 GIS領(lǐng)域本身缺少有效地對地理信息進(jìn)行多尺度處理的理論與方法[1],使得多尺度問題成為GIS領(lǐng)域的瓶頸問題之一。隨著地理信息技術(shù)應(yīng)用的日趨廣泛,解決地理信息“尺度鴻溝”的要求也越來越迫切。

作為一種視覺化 IT產(chǎn)品,GIS應(yīng)為用戶提供“連續(xù)”、“自適應(yīng)”的表達(dá)尺度,即具有多尺度、多分辨率空間表達(dá)與應(yīng)用的能力[2]。國內(nèi)外許多學(xué)者對地理信息多尺度表達(dá)進(jìn)行了深入研究,但大都沒有擺脫傳統(tǒng)矢量方法在多尺度表達(dá)上的先天缺陷。全球剖分模型[3]的產(chǎn)生為地理對象多尺度組織與表達(dá)提供了一個全新的解決思路,本文以其為基礎(chǔ),提出多尺度剖分編碼是地理對象多尺度表達(dá)的基礎(chǔ)這一概念,并研究設(shè)計了一套面向地理對象多尺度表達(dá)的高效、簡潔的多尺度一體化編碼方法。通過本方法可以使新一代GIS具備管理與表達(dá)不同應(yīng)用層次的、不同詳細(xì)程度的、任意尺度的地理對象的能力。

1 全球剖分模型

全球剖分模型(Global Subdivision Grid,GSG)主要研究如何將球面剖分為等面積和等形狀的層次狀面片,具有基于全球、多分辨率、支持尺度變換、空間位置分布均勻、融合空間索引機(jī)制等優(yōu)點(diǎn),國內(nèi)外學(xué)者提出了多種 GSG[4-10]。本文采用基于地圖分幅拓展的全球剖分模型(Extended Model based on M apping Division,EMD)[11],以基本比例尺地圖分幅為基礎(chǔ),利用經(jīng)緯度間隔實(shí)現(xiàn)對于全球數(shù)據(jù)無縫、多尺度、動態(tài)連續(xù)的遞歸剖分。圖1為EMD模型1～3級剖分方案,4～7級剖分按照地形圖分幅的劃分規(guī)則進(jìn)行,7級以上采用遞歸四分的方法剖分。在深度剖分層次下,其剖分面片的幾何精度能夠滿足對空間實(shí)體的表達(dá)要求,這使得地理對象多尺度剖分化組織及表達(dá)具備了可能性。

圖1 EMD模型1～3級剖分方案Fig.1 EMD model of the 1st to 3rd subdivision levels

2 地理對象多尺度編碼

面向地理對象多尺度表達(dá)的剖分編碼方法以EMD剖分模型為基礎(chǔ),對地理對象剖分面片集進(jìn)行多尺度一體化編碼,使編碼中包含地理對象的多尺度的空間位置、形狀等信息,從而支持地理對象多尺度表達(dá)(圖2)。本編碼方法為新一代GIS表達(dá)不同應(yīng)用層次、不同詳細(xì)程度、任意尺度的地理對象奠定了基礎(chǔ)。

圖2 地理對象剖分化表達(dá)Fig.2 Subdivided expression of geographic objects

地理對象指定層剖分面片集流程[12]如圖3所示。根據(jù)EMD剖分模型與經(jīng)緯度的映射關(guān)系,可以確定特定地理對象的最小外包面片(M inimum Boundary Cell,MBC)[13],即可完全容納目標(biāo)對象的最小一級剖分面片。對地理對象進(jìn)行剖分編碼的過程實(shí)際上集中在MBC內(nèi)部,在MBC之上依然采用EMD剖分編碼方式,根據(jù)不同需要在MBC內(nèi)可采用直接編碼或壓縮編碼方法。

圖3 獲取地理對象剖分面片集流程Fig.3 The flow chart of getting the subdivision meshes of geographical objects

2.1 直接編碼

沿用EMD編碼方式對含有地理對象的剖分面片逐一編碼。每個面片的編碼值由面片具體位置決定,而面片級別決定了編碼長度。特定地理對象的編碼由多個編碼組合而成,可以通過增加索引或在編碼間設(shè)置間隔符的方式將多個編碼區(qū)分開。

編碼時采用先對Lmax層(預(yù)先設(shè)定的MBC內(nèi)最大剖分層級)編碼然后逐層向上迭代編碼的由下至上的編碼方式。表1列出了對圖2中地理對象進(jìn)行多尺度編碼(Lmax=3)的結(jié)果?？梢钥闯?三層編碼都遵循剖分表達(dá)原則,使用哪一層編碼可視地理對象的表達(dá)精度要求而定,依據(jù)不同層編碼的剖分級數(shù)可以映射到影像金字塔[14]的相應(yīng)層提取遙感影像表達(dá)地理對象。

表1 剖分面片多尺度編碼集Table 1 M ulti-scale encoding set of subdivision meshes

2.2 壓縮編碼

本文提出在MBC內(nèi)部采用基于四叉樹的遞歸編碼方法對地理對象剖分面片集編碼。本方法使用一個編碼表示地理對象指定尺度下的剖分面片集合,目的是將地理對象的空間位置和區(qū)域(形狀)信息融合成一個統(tǒng)一編碼,通過計算多個尺度下的編碼形成多尺度編碼集合,從而支持對空間實(shí)體的多尺度剖分化表達(dá)。在指定尺度下計算壓縮編碼的具體算法是按左上、右上、左下、右下的順序定義當(dāng)前面片B的4個子面片 C0、C1、C2、C3。MBC內(nèi)部針對目標(biāo)對象進(jìn)行四叉樹迭代編碼的步驟如下:1)置當(dāng)前面片B的層級LB=1,Lmax為預(yù)先設(shè)置的最大剖分層級。2)建立對應(yīng)于B的四位編碼,首先判斷B面片包含的全部Lmax層子面片是否全為目標(biāo)。若全為目標(biāo),則B的編碼為0000,且不再進(jìn)行步驟3的操作,對面片B的編碼完畢;若不全為目標(biāo),依次判斷B的4個子面片 C0、C1、C2、C3是否含有目標(biāo),若Cn含有目標(biāo),則對應(yīng)于B的四位編碼的第n位置1,否則置0。3)對B的含目標(biāo)的子面片編碼:依次判斷B的4個子面片(所在層LC=LB+1)對應(yīng)位編碼是否為1,有如下兩種情況:a)Cn被置1。若LB< Lmax,則將 Cn設(shè)為當(dāng)前面片B,LB=LC,對 B進(jìn)行與步驟2、3相同的操作,否則不操作。b)Cn被置0,不操作。

使用壓縮編碼方法對圖2中地理對象Lmax層編碼結(jié)果如下:

1111 0111 0111 0101 0000 0000 1101 0101 0000 1101 1111 0000 1010 0000 1000

3 實(shí)驗(yàn)和討論

在對地理對象進(jìn)行編碼時,隨著尺度的不同,面片的數(shù)量和編碼長度都有所不同,為了進(jìn)一步對比兩種編碼方法的優(yōu)缺點(diǎn),并研究編碼與剖分層級的關(guān)系,本文在預(yù)先設(shè)定的MBC內(nèi)部選取了1 000個隨機(jī)生成的面狀地理對象,將 Lmax設(shè)置為7,對這1 000個地理對象進(jìn)行2～7層多尺度編碼。圖4為通過兩種編碼方式產(chǎn)生的編碼在不同尺度下編碼長度的概率分布圖,可以看出,壓縮編碼的編碼度普遍小于直接編碼方法,且分布更加集中。

表2中列出了兩種編碼方法在不同層編碼和最終多尺度編碼的情況。表達(dá)特定地理對象所用的平均面片數(shù)和兩種編碼方法的平均碼長都隨著L的增加而增加;平均面片覆蓋率的遞減則說明剖分層級越高,剖分化表達(dá)越趨于精細(xì)。通過回歸分析計算的壓縮編碼方法相對于直接編碼方法的壓縮倍數(shù)表明,當(dāng)L=3時,壓縮倍數(shù)出現(xiàn)一個較低值,當(dāng)L>3時,壓縮倍數(shù)隨著L的增加而增加。因?yàn)閱我粚哟a長隨著L的增加而增加,因此總的來說多尺度編碼的壓縮倍數(shù)主要由Lmax層壓縮倍數(shù)決定;同時由均方差可以看出,壓縮編碼方法的編碼長度更加穩(wěn)定。

直接編碼方法繼承了EMD編碼體系,編碼間相互獨(dú)立,可以直接使用,剖分面片級別可以由碼長確定,但是編碼相對較長,且編碼間需要設(shè)置間隔符或增加索引;壓縮編碼方法編碼相對較短,編碼總長度相對穩(wěn)定,不需設(shè)置間隔符,且剖分級別越高,壓縮效果越明顯,并有效地減少了線狀地物的編碼長度,但由于是遞歸編碼,必須解譯整條編碼才能得到剖分面片集。

圖4 編碼長度概率分布Fig.4 Probability distribution of encoding length

表2 不同剖分層級下的編碼情況Table 2 Encoding results on different levels

4 結(jié)論

本文以剖分的方法組織和管理地理對象的剖分面片集,在地理對象MBC內(nèi)部采用直接編碼方法或壓縮編碼方法對地理對象賦予多尺度剖分編碼,使編碼具有地學(xué)含義。雖然多尺度編碼使地理對象的剖分編碼長度有所增加,但其優(yōu)勢在于只計算和傳輸一次編碼,就可以根據(jù)不同的表達(dá)精度要求,使用不同層的剖分面片集提取剖分影像金字塔中不同分辨率的影像數(shù)據(jù)表達(dá)地理對象。同時多尺度剖分編碼獨(dú)立于具體的影像數(shù)據(jù),只包含空間位置和區(qū)域(形狀)等信息,影像表達(dá)可以從多來源、多尺度、多時相的遙感影像動態(tài)生成。

地理對象的剖分編碼不僅是建立一套編碼規(guī)則,更重要的是通過剖分方法賦予剖分編碼空間特征內(nèi)涵,使其成為剖分理論、地學(xué)和計算機(jī)間的橋梁。實(shí)驗(yàn)證明,面向地理對象多尺度表達(dá)的剖分編碼方法可以滿足地理對象多尺度剖分化表達(dá)的需要,為新一代GIS解決地理信息“尺度鴻溝”問題,向用戶提供“連續(xù)”、“自適應(yīng)”的表達(dá)尺度奠定了基礎(chǔ)。今后還需研究如何基于剖分四叉樹模型對地理對象進(jìn)行高效索引和查詢。

[1] 孫慶先,李茂堂,路京選,等.地理空間數(shù)據(jù)的尺度問題及其研究進(jìn)展[J].地理與地理信息科學(xué),2007,23(4):53-56.

[2] 艾廷華,成建國.對空間數(shù)據(jù)多尺度表達(dá)有關(guān)問題的思考[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2007,30(5):377-382.

[3] 宋樹華,程承旗,關(guān)麗,等.全球空間數(shù)據(jù)剖分模型分析[J].地理與地理信息科學(xué),2008,24(4):20-23.

[4] OTTOSON P,HAUSKA H.Ellipsoidal quadtrees for indexing of global geographical data[J].Geographical Information Science,2002,16(3):213-226.

[5] DUTTON G.A Hierarchical Coordinate System for Geoprocessing and Cartography[M].Berlin:Springer-Verlag,1999.

[6] 李德仁,肖志峰,朱欣焰,等.空間信息多級網(wǎng)格的劃分方法及編碼研究[J].測繪學(xué)報,2006,35(1):52-56.

[7] 袁文.地理格網(wǎng)STQ IE模型及原型系統(tǒng)[D].北京大學(xué),2004.

[8] 龔健雅.GIS矢量柵格一體化數(shù)據(jù)結(jié)構(gòu)的研究[J].測繪學(xué)報, 1992,21(4):259-266.

[9] 楊世仁,GOODCHILD M F,DUTTON G.空間數(shù)據(jù)的三角形四叉樹結(jié)構(gòu)及其基本操作[J].環(huán)境遙感,1995,10(4):269-278.

[10] 趙學(xué)勝.基于QTM的球面Voronoi數(shù)據(jù)模型[M].北京:測繪出版社,2004.

[11] 冉令輝.全球空間信息剖分編碼模型研究[D].北京大學(xué),2008.

[12] 官小波.面向遙感影像感興趣目標(biāo)表達(dá)的剖分?jǐn)?shù)據(jù)模型研究[D].北京大學(xué),2009.

[13] 程承旗,郭輝.基于剖分?jǐn)?shù)據(jù)模型的影像信息表達(dá)研究[J].測繪通報,2009(10):12-14.

[14] 萬元嵬,程承旗,宋樹華.大數(shù)據(jù)量遙感影像快速顯示剖分組織方法研究[J].地理與地理信息科學(xué),2009,25(3):33-36.

Abstract:The traditional GIS lack theories and methods inmulti-scale p rocessing of spatial data.A new generation of GIS should have the capabilitiesof multi-scale,multi-resolution exp ression and app lication of geographic objects.The emergence of Global Subdivision Grid(GSG)offers a new insight fo r multi-scale encoding and the exp ression of geographic objects.Based on GSG, a new multi-scale exp ression oriented subdivisional encoding method is p roposed,aiming to give the geographic object an integrated subdivisional code,w hich has geographicalmeaning as well asmulti-scale feature.Experimental results demonstrate that subdivisional code based on GSG can efficiently o rganize and management geographic objects,and therefore can be utilized for the m ulti-scale exp ression of geographic objects.

Key words:GIS;Global Subdivision Grid(GSG);EMD model;multi-scale exp ression;subdivisional code

A Research on M ulti-scale Expression Oriented Subdivisional Encoding Method

YANG Yu-bo1,2,CHENG Cheng-qi1,SONG Shu-hua1
(1.Institute of Remote Sensing and GIS,Peking University,Beijing 100871; 2.College of U rban and Environmental Sciences,Peking University,Beijing 100871,China)

P208

A

1672-0504(2010)05-0033-04

2010-04-17;

2010-06-11

國家重點(diǎn)基礎(chǔ)研究發(fā)展計劃(973)項(xiàng)目

楊宇博(1985-),男,碩士研究生,主要從事地理信息系統(tǒng)研究與工程應(yīng)用。E-mail:rechardyyb@gmail.com