唐雪華,秦 昆,孟令奎

武漢大學遙感信息工程學院,湖北武漢 430079

基于拓撲參考的定性方向關(guān)系矩陣描述模型

唐雪華,秦 昆,孟令奎

武漢大學遙感信息工程學院,湖北武漢 430079

定性方向關(guān)系描述是空間關(guān)系推理、空間關(guān)系語義匹配、模糊空間關(guān)系查詢、面向?qū)ο筮b感影像處理等的基礎(chǔ)。針對現(xiàn)有定性方向關(guān)系模型存在的MBR區(qū)域描述缺陷,本文提出一種基于拓撲參考的定性方向關(guān)系描述模型,基于拓撲劃分進行方向區(qū)域劃分,定義拓撲參考反映不同拓撲劃分中方向參考的變化,并以此為基礎(chǔ)建立分層定性方向關(guān)系矩陣。新模型能夠反映不同拓撲劃分區(qū)域方向關(guān)系參考的變化,實現(xiàn)MBR區(qū)域定性方向關(guān)系的精確描述,能有效提高定性方向關(guān)系描述的精確性及準確性。

定性方向關(guān)系;MBR區(qū)域;拓撲劃分;方向關(guān)系拓撲參考;分層方向關(guān)系描述矩陣

1 引 言

空間關(guān)系描述模型反映地理目標空間結(jié)構(gòu)和布局方向特征,是人類空間認知習慣在空間數(shù)據(jù)庫中的反映及描述,是空間查詢和存儲的基礎(chǔ)[1-2]。方向關(guān)系描述空間目標在空間上的順序或位置關(guān)系,反映了兩個空間目標間的指向關(guān)系[3],是最常用的相對定位方法。在地理信息科學研究中,方向關(guān)系理論被廣泛應(yīng)用于空間數(shù)據(jù)建模、空間查詢及推理、空間分析、決策支持、面向?qū)ο蟮倪b感影像處理、智能空間信息處理等領(lǐng)域[1,3-7]。例如,利用已知的方向關(guān)系條件進行模糊方向關(guān)系語義查詢和定位,是智能空間信息處理的重要研究內(nèi)容之一。在遙感圖像檢索研究中,將方向關(guān)系等空間關(guān)系特征作為空間相似度匹配依據(jù),可有效提高影像檢索的精度和效率[7]。

方向關(guān)系描述模型實現(xiàn)了方向關(guān)系約束的定量描述,是提取方向關(guān)系語義特征的關(guān)鍵。方向關(guān)系描述模型包括定量和定性描述兩大類[3],由于空間問題所固有的復(fù)雜性和不確定性,方向關(guān)系表達和推理普遍采用定性描述模型[1,8-9]?，F(xiàn)有定性方向關(guān)系描述模型根據(jù)其方向區(qū)域的劃分方式,可劃分為錐形模型、投影模型及基于Voronoi圖模型等[8]。錐形模型及其擴展模型將參考目標抽象為一個點,無法反映線/面參考目標形狀和大小的影響,其描述精度較差,適用于點參考目標方向關(guān)系描述。投影模型將目標投影到特定的坐標軸上,由參考目標及源目標投影間的關(guān)系定義方向關(guān)系,對目標形狀和大小較敏感,在一定程度上克服了錐形模型描述缺陷。基于Voronoi圖模型通過參考目標的Voronoi圖與源目標的相交關(guān)系來描述方向關(guān)系,在模型的適用性等方面存在優(yōu)勢[9]。但由第2節(jié)的分析可以得知,現(xiàn)有投影模型和基于Voronoi圖模型用幾何近似替代參考目標的真實邊界,無法準確描述幾何近似范圍內(nèi)的定性方向關(guān)系。針對這些問題,本文提出一種基于拓撲參考的定性方向關(guān)系矩陣模型,將拓撲參考引入方向關(guān)系描述,在拓撲劃分基礎(chǔ)上重新進行方向區(qū)域劃分,從根本上解決MBR區(qū)域定性方向關(guān)系描述問題,實現(xiàn)復(fù)雜拓撲關(guān)系目標定性方向關(guān)系描述。

2 現(xiàn)有方向關(guān)系定性描述模型分析

方向關(guān)系的形式化描述主要包括3個基本要素,即源目標(待確定方向的目標)、參考目標(確定源目標方向的參考物體)及方向參考體系[3]。因此,定性方向關(guān)系描述精度取決于描述模型對源目標及參考目標形狀和大小的敏感程度及方向參考定義的合理性。

錐形模型利用參考目標指向線將空間目標及其周圍區(qū)域劃分為帶有方向性的互斥的若干個錐形區(qū)域(4個或8個),通過源目標與方向區(qū)域的相交情況來描述方向關(guān)系[8],對點參考目標的方向區(qū)域劃分符合方向認知習慣。但由于將線/面參考目標抽象為一個點,當空間目標之間的距離相對于自身大小較近的時候,可能出現(xiàn)描述錯誤。針對原錐形模型的描述缺陷,文獻[10]基于參考目標的MBR范圍重新劃分方向關(guān)系區(qū)域;文獻[11]提出四半?yún)^(qū)域模型,以參考目標MBR相鄰頂點的4條方向線及其交點的連線為參考,將參考目標的外部空間劃分為4個半無限區(qū)域,將面參考目標抽象為一根連接線,在一定程度上提高了描述精度,但無法根除其描述缺陷。

投影模型將空間目標投影到特定的坐標軸上,根據(jù)目標投影(正射投影或斜率投影)間的關(guān)系來定義方向關(guān)系[12],代表性模型包括2DString投影模型[13-14]、MBR模型[10,15]及方向關(guān)系矩陣模型[1]等。2DString及其擴展模型利用空間目標在X軸和Y軸方向的投影字符串定義方向關(guān)系,將二維空間方向關(guān)系特征轉(zhuǎn)換為一維空間方向關(guān)系表達,其方向分辨能力有限。MBR模型以參考目標和源目標的MBR范圍替代參考目標和源目標,對目標的形狀和大小敏感度較差。方向關(guān)系矩陣模型以參考目標MBR區(qū)域為參考中心劃分方向區(qū)域,利用源目標與9個方向區(qū)域相交的3×3矩陣定義方向關(guān)系,對源目標的形狀和大小敏感。但由于以MBR擬合參考目標,如圖1(a)所示,方向關(guān)系矩陣模型無法分辨MBR區(qū)域內(nèi)的方向關(guān)系。針對原方向關(guān)系矩陣模型的描述缺陷,文獻[16]提出細節(jié)方向關(guān)系矩陣模型, 將MBR區(qū)域細分為參考目標的邊界、內(nèi)部和環(huán)部,利用MBR中心點及指定高寬矩形的延長線將MBR區(qū)域劃分為9個矩形區(qū)域,提高了模型的描述精度。但由于忽略了不同拓撲區(qū)域中方向參考中心的變化,如圖1(b)所示,當參考目標為凹多邊形時,細節(jié)模型對于其中心區(qū)的定義可能位于參考目標外部,與認知習慣不一致。

圖1 方向關(guān)系矩陣及細節(jié)方向關(guān)系矩陣對MBR的描述Fig．1 Description of MBR based on direction-relation matrix and detailed direction-relation matrix

基于Voronoi圖的模型通過參考目標的Voronoi圖與源目標的關(guān)系來描述和定義方向關(guān)系。其代表模型包括:文獻[9]用參考目標MBR 與Voronoi區(qū)域邊界線之間的關(guān)系來定義方向關(guān)系;文獻[3]通過建立與空間目標間指向線的法線比較近似的方向Voronoi圖來描述空間目標間的方向關(guān)系。Voronoi模型在模型適用性等方面存在優(yōu)勢,但Voronoi多邊形同樣是目標的幾何擬合,無法避免描述精度缺陷。

考慮到其他空間關(guān)系對于方向關(guān)系描述的相互約束關(guān)系,一些學者研究方向關(guān)系與拓撲關(guān)系、度量關(guān)系等其他空間關(guān)系的組合及細化模型[17-19],通過增加約束條件提高描述模型的表達精度。但是,現(xiàn)有大多數(shù)模型是方向關(guān)系與拓撲關(guān)系在表達模型層次上的組合,并沒有考慮拓撲關(guān)系對于方向關(guān)系定義的影響。例如,文獻[6]在方向關(guān)系矩陣的基礎(chǔ)上,利用源目標與9個方向區(qū)域邊界線之間的拓撲關(guān)系來細化方向關(guān)系描述。但是,拓撲細化模型僅考慮了源目標與方向關(guān)系區(qū)域邊界線的拓撲關(guān)系,沒有考慮源目標與參考目標的拓撲關(guān)系對于方向關(guān)系描述的影響,難以區(qū)分MBR區(qū)域內(nèi)不同拓撲關(guān)系目標的方向關(guān)系。

綜上所述,現(xiàn)有定性方向關(guān)系描述模型主要存在問題包括:①用點、線、MBR范圍擬合參考目標,對于目標的形狀和大小敏感度較差,大大限制了描述模型精度;②現(xiàn)有組合和細化模型沒有考慮拓撲關(guān)系對方向關(guān)系參考定義的影響,無法從根本上解決復(fù)雜拓撲關(guān)系目標的方向關(guān)系描述問題。

3 基于拓撲參考的定性方向關(guān)系矩陣模型

由第2節(jié)的分析可得知,錐形模型、投影模型及基于Voronoi圖模型都存在由簡化目標邊界導致的描述缺陷,解決關(guān)鍵在于保留原目標真實邊界,對不同拓撲劃分空間定義合理的方向關(guān)系參考,提高模型描述精度。

3．1 空間目標定義

鑒于地理空間目標的特點及復(fù)雜性,文獻[17]以組合拓撲為工具,提出了拓撲胞腔(topological cell)理論,奠定了空間數(shù)據(jù)模型的數(shù)學基礎(chǔ)。隨后,拓撲胞腔理論的發(fā)展逐漸形成了現(xiàn)有GIS空間數(shù)據(jù)模型標準。文獻[18]對代數(shù)拓撲學中的單純形(simplex)及單純復(fù)形(simplicial complex)概念進行拓展,將單純形的凸集約束放寬,定義了胞腔(cell)及胞腔復(fù)形(simplicial complexes),并給出不同維數(shù)的空間目標及其基本操作定義。文獻[19]在此基礎(chǔ)上給出拓撲意義上的簡單空間目標(n維胞腔A)的閉包、邊界、內(nèi)部及外部的定義,將胞腔及胞腔復(fù)形定義應(yīng)用于空間目標的定義中,分別定義了GIS中的點、線、面目標,即:①點為二維空間中的一個單獨的0維胞腔;②線為由相互連接的,不相交且無閉合回路的1維胞腔復(fù)形構(gòu)成的序列;③面是二維空間中的一個內(nèi)部不為空的二維胞腔復(fù)形[19]。

3．2 基于拓撲參考的方向區(qū)域劃分

拓撲關(guān)系對于方向關(guān)系的約束主要表現(xiàn)為不同拓撲劃分中方向關(guān)系參考的變化。因此,方向區(qū)域劃分首先要在空間目標定義基礎(chǔ)上進行拓撲劃分,然后對不同的拓撲劃分空間定義拓撲參考,將其與原有方向區(qū)域劃分方法綜合,最后得到基于拓撲參考的方向區(qū)域劃分。

現(xiàn)有拓撲關(guān)系描述模型可劃分為基于目標分解和基于目標整體的模型兩大類[11]?；谀繕朔纸馔負潢P(guān)系模型的代表性模型4交模型將空間目標看作是邊界點和內(nèi)部點的集合,9交模型對4交模型進行拓展,將拓撲空間進一步劃分為內(nèi)部、邊界及外部3個部分。4交模型及9交模型在空間數(shù)據(jù)存儲、空間分析等領(lǐng)域得到了廣泛的應(yīng)用,但是,“補”的定義一方面存在無限性、重疊大、空間實體定義不足、不能表達空間鄰近關(guān)系等缺陷[12,20],另一方面,二維空間中線段的拓撲劃分會出現(xiàn)內(nèi)部與外部直接相接的問題,違背了拓撲學中基本的約旦定理[21]。基于目標整體的RCC模型及2DString模型,在區(qū)分能力及復(fù)雜性描述方面存在不足。針對這些問題,文獻[21]提出一種基于目標整體的描述方法,利用空間目標及目標的Voronoi區(qū)域之間的交、并、被差、差、對稱差等算子實現(xiàn)拓撲關(guān)系表達,克服了分解模型拓撲不一致性缺陷;文獻[22—23]在此基礎(chǔ)上,將空間目標看作一個整體,提出一種基于目標整體交/差、歐拉數(shù)的地籍實體拓撲關(guān)系計算方法,用空間目標間的交、差兩種集合操作算子來描述其拓撲關(guān)系,克服了原有基于Voronoi區(qū)域模型的非同時性目標間拓撲關(guān)系表達缺陷。

方向區(qū)域劃分方面,基于投影的方向關(guān)系矩陣模型的方向區(qū)域劃分與方向認知習慣一致,且具有以下優(yōu)點:①與基于經(jīng)緯度的地球定位結(jié)構(gòu)一致[24];②與錐形模型相比,投影模型具有更高的方向分辨精度[5];③對于空間數(shù)據(jù)庫而言,由于方向關(guān)系矩陣模型的方向區(qū)域劃分是矩形的,與錐形模型相比更容易實現(xiàn)[1];④從數(shù)學的角度來看,在二維空間中,其方向區(qū)域劃分是完備的。因此,本文以方向關(guān)系矩陣模型的方向區(qū)域劃分為基礎(chǔ),將其與拓撲劃分進行結(jié)合,定義新的方向區(qū)域劃分。

綜合以上分析,如圖2所示,新的方向區(qū)域劃分首先基于參考目標整體,將整個拓撲空間劃分為外部及目標整體兩大區(qū)域,將其與方向關(guān)系矩陣模型的9個方向區(qū)域進行相交,得到10個區(qū)域。其中,外部的8個區(qū)域與原有方向關(guān)系矩陣模型區(qū)域一致,增加的2個區(qū)域?qū)嵸|(zhì)上是對原有MBR區(qū)域的拓撲細分。

圖2 MBR區(qū)域的拓撲劃分Fig．2 The topological division of MBR

在拓撲劃分的基礎(chǔ)上,給出新的方向區(qū)域定義。

外部的8個方向區(qū)域采用外部拓撲參考,由于離參考目標較遠,外部拓撲參考將MBR區(qū)域整體作為中心,其方向區(qū)域定義與原方向關(guān)系矩陣模型一致。

MBR外部區(qū)域離參考目標較近,因此,其方向關(guān)系定義主要受到參考目標局部邊界影響。根據(jù)認知習慣,該區(qū)域方向關(guān)系由參考目標方向指向決定,若某個區(qū)域為兩個方向指向的重疊區(qū)域,則為復(fù)合方向區(qū)域。如圖3所示,北方向區(qū)域為參考目標北方向指向區(qū)域(圖3(a)),東方向區(qū)域為參考目標東方向指向區(qū)域(圖3(b)),東北方向區(qū)域為北方向和東方向指向重疊區(qū)域(圖3(c))。在實際計算中,由方向的自反性,可以源目標到參考目標上的投影距離DN、DE、DS及DW作為判斷參數(shù)。

圖3 MBR區(qū)域外部方向區(qū)域Fig．3 The exterior direction tiles of MBR

目標整體區(qū)域采用目標整體拓撲參考,其定義關(guān)鍵在于確定線/面目標的參考中心。若將參考中心定義為線/面目標的內(nèi)心(記作C),根據(jù)認知習慣,須滿足兩個約束條件:①位于參考目標內(nèi)部;②位于參考目標分布的中心區(qū)域,能反映參考目標的面積及形狀分布。線目標分布通常以長度為衡量指標,因此,將線目標的中點定義為其內(nèi)心。面目標分布主要以面積為衡量指標,通常以形心作為中心。但凹多邊形的形心可能位于目標外部,不滿足第一個約束條件。因此,本文參考地圖注記中心點多邊形骨架線中點定義,采用文獻[25]提出的基于約束Delaunay三角網(wǎng)結(jié)構(gòu)的形心方法定義面目標的內(nèi)心,其計算流程如圖4所示。將面目標邊界離散為邊界離散點,以三角形不能穿越面邊界為約束條件建立Delaunay三角網(wǎng),把得到的三角形分為3類:Ⅰ類三角形,三角網(wǎng)中的邊界節(jié)點,其頂點中有一個頂點為骨架線的端點;Ⅱ類三角形,三角網(wǎng)中跨接三角形;Ⅲ類三角形,位于骨架分支的交匯處的三角形。其中,凸度為任意多邊形面積與該多邊形凸殼面積的比值,即

圖4 內(nèi)心的計算流程Fig．4 The computational procedure of incenter

中心參考點確定后,采用8方向劃分,可以得到如圖5所示的方向區(qū)域劃分。

圖5 線/面參考目標整體方向區(qū)域劃分Fig．5 The direction tiles of whole line/area reference object

3．3 分層方向關(guān)系矩陣模型

對應(yīng)新的方向區(qū)域劃分,將原有方向關(guān)系矩陣模型拓展為外部方向關(guān)系矩陣、MBR外部方向關(guān)系矩陣及目標整體方向關(guān)系矩陣等3個方向關(guān)系矩陣,具體定義如下。

定義1:外部方向關(guān)系矩陣描述參考目標MBR外部區(qū)域的方向關(guān)系,記作dire(R,P),定義為

如圖6所示,3個方向關(guān)系矩陣中心元素的層次包含關(guān)系反映了方向區(qū)域劃分的連續(xù)性和完整性。

圖6 層次方向關(guān)系矩陣中心元素的包含關(guān)系Fig．6 The relationships between the cores of hierarchical direction-relation matrixes

為了提高計算效率,新模型采用分級計算策略,如圖7所示,按照外部、MBR外部、目標整體的順序來進行方向關(guān)系矩陣計算,每個方向矩陣計算完后,根據(jù)其中心元素的取值來決定是否繼續(xù)計算:中心元素值若為空,停止計算;反之,繼續(xù)計算。

圖7 層次方向關(guān)系矩陣的計算流程Fig．7 The flow of hierarchical matrixes

與原方向關(guān)系矩陣模型及細節(jié)方向關(guān)系矩陣模型相比,新模型在拓撲劃分基礎(chǔ)上建立不同拓撲區(qū)域的方向參考,實現(xiàn)了MBR區(qū)域內(nèi)復(fù)雜拓撲關(guān)系目標定性方向關(guān)系的精確描述。

4 試驗分析

4．1 與MBR模型及方向關(guān)系矩陣模型的比對試驗

由于新模型保留了參考目標的原有邊界,并對MBR區(qū)域進行拓撲細分,能夠克服MBR模型及方向關(guān)系矩陣模型的MBR描述缺陷。對3個模型的描述能力進行比對試驗,如圖8所示,選擇MBR內(nèi)不同拓撲關(guān)系的3個源目標,其中,A與R相交,B與R相離,C位于R的內(nèi)部,分別用3個模型對其進行方向關(guān)系描述,描述結(jié)果如表1所示。從試驗結(jié)果不難看出:①MBR模型和方向關(guān)系矩陣模型對3個目標的描述結(jié)果相同,無法區(qū)分MBR區(qū)域內(nèi)的方向;②新模型不僅能分辨不同目標的方向關(guān)系,且反映了目標所在的拓撲劃分,實現(xiàn)了復(fù)雜拓撲關(guān)系目標的方向關(guān)系描述。

圖8 MBR內(nèi)不同拓撲關(guān)系目標Fig．8 Objects of different topological relations in MBR

表1 與MBR模型及方向關(guān)系矩陣模型比對結(jié)果Tab．1 Comparison with MBR and direction-relation matrix model

4．2 與拓撲細化描述模型及細節(jié)方向關(guān)系矩陣模型的比對試驗

拓撲細化描述模型僅考慮了MBR外部區(qū)域中源目標與9個方向區(qū)域延長線的拓撲關(guān)系,無法分辨MBR內(nèi)不同拓撲關(guān)系目標的方向關(guān)系。如圖9(a),細節(jié)方向關(guān)系矩陣模型雖能分辨MBR內(nèi)的目標,但對于凹面目標中心定義可能與認知習慣不符。如圖9(b),新模型考慮了不同拓撲劃分中方向關(guān)系參考中心的變化,描述結(jié)果更加接近認知習慣。3個模型對圖9的空間目標方向關(guān)系描述結(jié)果如表2所示。

圖9 凹多邊形方向區(qū)域劃分Fig．9 The direction tiles of concave polygon

表2 與拓撲細化模型及細節(jié)模型的比較Tal．2 Comparison with topological refined and detailed model

從試驗結(jié)果不難發(fā)現(xiàn),拓撲細化模型無法分辨兩個目標的方向關(guān)系差異。細節(jié)模型雖然能區(qū)分兩個目標的方向,但其將MBR區(qū)域的中心直接作為MBR外部區(qū)域(環(huán)部)的中心,不考慮局部邊界對方向的影響,其描述結(jié)果與認知習慣不符。新模型考慮了局部邊界對源目標方向的影響,更加貼近方向認知習慣。

5 結(jié) 論

針對現(xiàn)有定性方向關(guān)系描述模型對于MBR的描述缺陷,將拓撲參考引入方向關(guān)系定義,提出了基于拓撲參考的定性方向關(guān)系矩陣模型。試驗結(jié)果表明,新模型具備以下特點:①能夠分辨MBR區(qū)域的不同拓撲劃分,從根本上解決了復(fù)雜拓撲關(guān)系目標方向關(guān)系描述問題,提高了模型的準確性和精確性;②根據(jù)認知習慣,新模型對于不同拓撲區(qū)域建立方向關(guān)系拓撲參考,解決了凹多邊形的參考中心定位問題;③采用分級計算策略,計算量由目標拓撲關(guān)系而定,在提高描述精度同時,有效控制了計算量。

定性方向關(guān)系描述模型是定性模糊概念定量描述的基礎(chǔ),本文所提出的新模型雖然改進了原有模型的方向關(guān)系區(qū)域劃分及描述,但尚未解決定性描述與定量描述間轉(zhuǎn)換問題,因此,下一步的研究將集中在以下方面:①將定性描述模型與定量描述模型相結(jié)合,建立定性到定量間的轉(zhuǎn)換模型;②將確定性空間目標拓展到模糊目標,研究模糊目標方向關(guān)系特征描述模型;③將新模型應(yīng)用于空間查詢及檢索等應(yīng)用領(lǐng)域,驗證和改進模型的性能。

[1] GOYAL R K．Similarity Assessment for Cardinal Directions between Extended Spatial Objects[D]．Maine:The University of Maine,2000．

[2] LI Deren,ZHU Qing,ZHU Xinyan,et al．Task-based Remote Sensing Information Focus Service[M]．Beijing:Science Press,2011．(李德仁,朱慶,朱欣焰,等．面向任務(wù)的遙感信息聚焦服務(wù)[M]．北京:科學出版社,2011．)

[3] YAN Haowen,GUO Renzhong．Theorization of Directional Relationship Description Based on Voronoi Diagram[J]．Geomatics and Information Science of Wuhan University, 2002,27(3):306-310．(閆浩文,郭仁忠．用Voronoi圖描述空間方向關(guān)系的理論依據(jù)[J]．武漢大學學報:信息科學版,2002,27(3):306-310．)

[4] KULIK L,KLIPPEL A．Reasoning about Cardinal Directions Using Grid as Qualitative Geographic Coordinates [C]∥Spatial Information Theory-cognitive and Computational Foundations of Geographic Information Science COSIT'99．[S．l．]:COSIT,1999:205-220．

[5] FRANK．Qualitative Spatial Reasoning:Cardinal Directions as an Example[J]．International Tree-an Intelligent Graphical Zoom,Computers&Graphics,1996,18(6):823-829．

[6] CAO Han,CHEN Jun,DU Daosheng．Qualitative Extention Description for Cardinal Directions of Spatial Object [J]．Acta Geodaetica et Cartographica Sinica,2001,30 (2):162-167．(曹菡,陳軍,杜道生．空間目標方向關(guān)系的定性擴展描述[J]．測繪學報,2001,30(2):162-167．)

[7] CHENG Qimin．Remote Sensing Image Retrieval Technologies [M]．Wuhan:Wuhan University Press,2011:16．(程起敏．遙感圖像檢索技術(shù)[M]．武漢:武漢大學出版社,2011:16．)

[8] XIA Yu,ZHU Xinyan,LIN Deren,et al．Research on Spatial Directional Relation Description Model[J]．Science of Surveying and Mapping,2007,32(5):94-97．(夏宇,朱欣焰,李德仁,等．GIS空間方向關(guān)系形式化描述模型分析[J]．測繪科學,2007,32(5):94-97．)

[9] LI Chengming,ZHU Yinghao,CHEN Jun．Directional Relation Description and Determination Based on Voronoi Diagram in GIS[J]．Journal of the PLA Institute of Surveying and Mapping,1998,19(2):117-120．(李成名,朱英浩,陳軍．利用Voronoi圖形式化描述和判斷GIS中的方向關(guān)系[J]．解放軍測繪學院學報,1998,19(2):117-120．)

[10] PEUQUET D,ZHAN C X．An Algorithm to Determine the Directional Relationship between Arbitrary-Shape Polygons in the Plane[J]．Pattern Recognition,1987,20 (1):65-74．

[11] ABDELMOTY A I,WILLIAMS M H．Approaches to the Representation of Qualitative Spatial Relationship for Geographic Database[C]∥Proceedings of Advanced Geographic Data Modeling．[S．l．]:Netherlands Geodetic Commission,1994:204-216．

[12] CHEN Jun,ZHAO Renliang．Spatial Relations in GIS:a Survey on Its Key Issues and Research Progress[J]．Acta Geodaetica et Cartographica Sinica,1999,28(2):95-102．(陳軍,趙仁亮．GIS空間關(guān)系的基本問題與研究進展[J]．測繪學報,1999,28(2):95-102．)

[13] CHANG S K,SHI Q S,YAN C W．Iconic Indexing by 2-D String[J]．IEEE Transactions on Pattern Analysis and Machine Intelligence,1987,9(6):413-428．

[14] CHANG S K,JURGERT E．Symbolic Projection for Image Information Retrieval and Spatial Reasoning[M]．London:Academic Press,1996．

[15] MUKERJEE A,JOE G．A Qualitative Model for Space [C]∥Proceedings of Eighth National Conference on Artificial Intelligence．Boston:[s．n．],1990:721-727．

[16] DU Shihong．Research on Theoretics and Methods of Fuzzy Description and Composite Reasoning of Spatial Relations [D]．Beijing:Graduate University of Chinese Academy of Sciences,2004．(杜世宏．空間關(guān)系模糊描述及組合推理的理論和方法研究[D]．北京:中國科學院研究生院,2004．)

[17] CORBETT J P．Topological Principles of Cartography[R]．[S．l．]:Bureau of the Census,1979．

[18] FRANK A．Cell Graph:A Provable Correct Method for the Storage of Geometry[C]∥Proceedings of Second International Symposium on Spatial Data Handling．Seattle:[s．n．],1986．

[19] EGENHOFER M,HERRING J．A Mathematical Framework for the Definitions of Topological Relationships[C]∥Proceedings of the 4th International Symposium on Spatial Data Handling．[S．l．]:SDH,1990．

[20] LI Chengming,CHEN Jun．The Nine-intersection Model for Describing Spatial Relation[J]．Journal of Wuhan Technical University of Surveying and Mapping,1997,22 (3):207-211．(李成明,陳軍．空間關(guān)系描述的9-交模型[J]．武漢測繪科技大學學報,1997,22(3):207-211．)

[21] LI Z L,ZHAO R,CHEN J．A Voronoi-based Spatial Algebra for Spatial Relations[J]．Progress in Natural Science, 2002,12:528-536．

[22] ZHOU Xiaoguang,CHEN Jun,LI Zhilin,et al．Computation of Topological Relations between Cadastral Objects Based on Euler-number[J]．Acta Geodaetica et Cartographica Sinica,2006,35(3):291-298．(周曉光,陳軍,李志林,等．基于歐拉數(shù)的地籍拓撲關(guān)系計算與應(yīng)用[J]．測繪學報, 2006,35(3):291-298．)

[23] ZHOU Xiaoguang,CHEN Jun,ZHAN F,et al．A Eulernumber-based Topological Computation Model for Land Parcel Database Updating[J]．International Journal of Geographical Information Science,2013,51(5):23-27．

[24] KULIK L,KLIPPEL A．Reasoning about Cardinal Directions Using Grid as Qualitative Geographic Coordinates[C]∥Proceedings of Spatial Information Theory-cognitive and Computational Foundations of Geographic Information Science COSIT'99．Stade:[s．n．],1999:205-220．

[25] CHEN Tao,AI Tinghua．Automatic Extraction of Skeleton and Center of Area Feature[J]．Geomatics and Information Science of Wuhan University,2004,29(5):443-446．(陳濤,艾延華．多邊形骨架線與形心自動搜尋算法研究[J]．武漢大學學報:信息科學版,2004,29(5):443-446．)

(責任編輯:宋啟凡)

A Qualitative Matrix Model of Direction-relation Based on Topological Reference

TANG Xuehua,QIN Kun,MENG Lingkui
School of Remote Sensing and Information Engineering,Wuhan University,Wuhan 430079,China

Directional relationship is one of the fundamental characters of spatial reasoning, spatial semantics matching,fuzzy query of spatial relationship and object-oriented image analysis etc．A new qualitative direction-relation model based on topological reference is proposed to overcome the problems of description in the MBR region of reference object．Based on the topological division,topological reference is defined to reflect the alteration of directional reference among different topological tiles．The new model overcomes the description difficulty of directional relations in the MBR and improves the accuracy and veracity of model．

qualitative direction-relation;minimum bounding rectangle;topological division; topological reference for direction-relation;hierarchical direction-relation matrix model

TANG Xuehua(1977—),female,PhD, lecturer,majors in the research of the theory of spatial relations and its application in remote sensing imagerecognition and retrieval．

QIN Kun

P208

A

1001-1595(2014)04-0396-08

2012-08-16

唐雪華(1977—),女,博士,講師,主要研究方向為空間關(guān)系理論及其在遙感影像識別和檢索中的應(yīng)用。

E-mail:tangxuehua＠whu．edu．cn

秦昆

E-mail:qink＠whu．edu．cn

TANG Xuehua,QIN Kun,MENG Lingkui．A Qualitative Matrix Model of Direction-relation Based on Topological Reference [J]．Acta Geodaetica et Cartographica Sinica,2014,43(4):396-403．(唐雪華,秦昆,孟令奎．基于拓撲參考的定性方向關(guān)系矩陣描述模型[J]．測繪學報,2014,43(4):396-403．)

10．13485/j．cnki．11-2089．2014．0059

國家973計劃(2012CB719903);高等學校博士學科點專項科研基金(20120141120089)

修回日期:2013-09-03