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

楊宇博,程承旗,宋樹華

(1.北京大學遙感與地理信息系統研究所,北京100871;2.北京大學城市與環境學院,北京100871)

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

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

(1.北京大學遙感與地理信息系統研究所,北京100871;2.北京大學城市與環境學院,北京100871)

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

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

0 引言

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

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

1 全球剖分模型

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

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

2 地理對象多尺度編碼

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

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

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

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

2.1 直接編碼

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

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

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

2.2 壓縮編碼

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

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

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

3 實驗和討論

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

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

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

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

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

4 結論

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

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

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

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

[3] 宋樹華,程承旗,關麗,等.全球空間數據剖分模型分析[J].地理與地理信息科學,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] 李德仁,肖志峰,朱欣焰,等.空間信息多級網格的劃分方法及編碼研究[J].測繪學報,2006,35(1):52-56.

[7] 袁文.地理格網STQ IE模型及原型系統[D].北京大學,2004.

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

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

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

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

[12] 官小波.面向遙感影像感興趣目標表達的剖分數據模型研究[D].北京大學,2009.

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

[14] 萬元嵬,程承旗,宋樹華.大數據量遙感影像快速顯示剖分組織方法研究[J].地理與地理信息科學,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

國家重點基礎研究發展計劃(973)項目

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