顧及尺度差異的復合空間對象方向相似度定量計算模型

陳占龍，龔　希，吳　亮，安曉亞

1. 中國地質大學(武漢)信息工程學院,湖北 武漢430074; 2. 地理信息工程國家重點實驗室,陜西 西安710054; 3. 西安測繪研究所,陜西 西安 710054

?

顧及尺度差異的復合空間對象方向相似度定量計算模型

陳占龍1,2，龔希1，吳亮1，安曉亞2,3

1. 中國地質大學(武漢)信息工程學院,湖北 武漢430074; 2. 地理信息工程國家重點實驗室,陜西 西安710054; 3. 西安測繪研究所,陜西 西安 710054

decomposition

Foundation support： The National Natural Science Foundation of China(Nos.41401443;41201469); The National Key Technology Research and Development Program of the Ministry of Science and Technology of China (No.2011BAH06B04); Open Research Fund of State Key Laboratory of Geography Information Engineering (No.SKLGIE2013-Z-4-1); Open Research Fund of State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing(No.13I02); Research Funds for the Central Universities Basic Special Projects (No.CUGL130260)

摘要：介紹了一種顧及尺度差異的復合空間對象的方向關系表達模型，及基于該模型的方向相似度度量方法。該方向關系模型對方向關系矩陣模型進行改進，根據(jù)空間對象的形狀定量描述空間對象之間的方向關系。采用分解思想，借鑒平衡傳輸問題的優(yōu)化方法計算復合方向矩陣間最小轉換代價，即方向矩陣間的距離，從而量化方向對間的差異，最終獲得不同尺度下的復合對象的方向相似度并對其進行比較。對不同尺度復合空間對象的方向相似性的試驗表明，該方法簡單可行且不失精度，結果符合人類認知。

關鍵詞：多尺度；復合空間對象；方向相似度；方向關系矩陣；分解

在地圖制圖綜合中常將大比例尺地圖轉換為小比例尺地圖，盡管尺度發(fā)生變化，但其所表達的信息應該保持一定的相似性，空間相似性可用來評判綜合結果是否合理。文獻[1]將多尺度地圖空間相似關系分為圖像相似和屬性相似兩大類，而方向關系相似是圖形相似中重要的組成部分，因此方向關系間的相似度可作為制圖綜合結果的評判因子。

現(xiàn)階段很多學者對方向關系模型進行了研究，既有表示方向關系的定性模型[2-8]，亦有用于相似度評估的定量模型，以及既為定性模型亦為定量模型的方向矩陣模型[9-10]。如文獻[2]提出用三角模型，通過質心替代對象進行方向關系判斷；文獻[3]提出一維間隔模型用間隔表示了13種獨立的關系；文獻[4]將二維對象投影到x軸和y軸再分別運用一維間隔模型從而得到了二維間隔模型；文獻[5—6]將一維模型擴展到二維空間，得到描述四邊平行于平面直角坐標的空間對象的矩形代數(shù)模型。文獻[7]提出二維串模型用標志圖及空間目標網(wǎng)格來表示空間關系；文獻[8]提出MBR模型并用于空間目標間拓撲關系的檢索；文獻[9—10]提出既為定性模型亦為定量模型的方向矩陣模型，還有在此基礎上進行改進得到一系列可應用于柵格數(shù)據(jù)或解決分區(qū)線與對象重合等問題的模型，如文獻[11]提出SK主方向關系模型并設計了相容性復合方法，文獻[12—13]利用柵格數(shù)目比例作為量化信息來表達柵格數(shù)據(jù)對象間的方向關系，文獻[14]采用縮小中心分區(qū)的方法改進了該模型；此外，根據(jù)不同的應用情況產(chǎn)生了各種側重點不同的方向關系模型，如文獻[15]建立基于Voronoi圖的空間方向關系形式化描述模型；文獻[16—18]依次提出一種能表達與參照對象外接矩形內部有關信息細節(jié)的定性方向關系表達模型，一種模糊的描述空間關系的方法以及一種方向關系粗糙、變精度粗糙表達方法并將其應用到方向關系的粗糙推理方法中；文獻[19]提出了方向關系描述的分層多級處理方法并建立了方向描述的3層模式結構；文獻[20]在基于Cobb的空間拓撲關系模型的基礎上建立了拓撲關系矩陣和方向關系矩陣；文獻[21]提出4種不同情況下基于同一參照系的定性方向推理方法。

上述的方向關系模型中定性模型無法進行相似性度度量,且同大部分定量模型一樣,都是基于簡單空間對象，對復合對象之間的方向關系表達和度量能力不足，因而不能對復合對象之間的方向關系相似度進行度量。而實際應用中，存在大量的復合對象，如由高校校區(qū)經(jīng)常是由多個區(qū)構成的多區(qū)對象，在河流交匯處由多條河流構成的多線對象，十字路口處是由多條道路構成的多線對象等。同時實際應用中數(shù)據(jù)繁雜多源，進行相似性比較的數(shù)據(jù)也常是異源多尺度，如大比例尺中的面對象在小比例尺中變?yōu)辄c對象。而現(xiàn)有的方法大多考量同維幾何實體間的方向相似度。因此，本文將顧及空間尺度差異，研究復合空間對象的方向關系表達及其方向相似度度量方法。

1復合空間對象及其方向關系描述

1.1復合對象

如圖1所示，復合對象由單一類型的對象構成，有3種類型的復合對象(圖1)：復合點對象、復合線對象、復合面對象，它們分別由n(n≥1)個點、線、區(qū)構成，點之間、線之間、區(qū)之間均不重合，線之間可相交或相鄰、區(qū)之間不可相交可相鄰，即A={A1∪A2∪…∪An}。

圖1　復合對象Fig.1　Composite geometric objects

1.2復合空間對象的方向關系矩陣

本文通過一種格網(wǎng)下的方向關系矩陣來表示單對象之間的方向關系。該方法首先通過參考對象最小外包矩形邊所在直線將空間劃分成9個分區(qū){N,S,E,W, NE, SE, SW, NW, same}，分別對應3×3矩陣的9個元素，再將地圖上所涉及的區(qū)域劃分為固定大小的網(wǎng)格，9個元素值分別為對象在該分區(qū)所占的網(wǎng)格數(shù)目比例，如式(1)所示

(1)

本文方法是在方向關系矩陣上的改良，可簡化關系矩陣的計算。方法規(guī)定單個點對象所占的網(wǎng)格數(shù)記為1，當參考對象為點時以該點所在網(wǎng)格的延長線進行分區(qū)。在此基礎上,本文結合分解思想，使復合對象間的方向關系也能通過方向格網(wǎng)關系矩陣表示。根據(jù)參考對象A和目標對象B是否為復合對象，本文分為3種情況對復合空間對象的格網(wǎng)方向關系矩陣進行介紹。

1.2.1參考對象為復合對象

當參考對象A為由n個單對象組成的復合對象時，則分別以這n個單對象為參考對象，求取每個單參考對象與目標對象的方向關系矩陣，然后按照這n個單對象所占網(wǎng)格數(shù)目與對象A所占的網(wǎng)格數(shù)目的比值分配權重，將n個單對象與目標對象的關系矩陣相加(式(2))，便得到復合對象與目標對象的方向關系矩陣，式中dir(Ai,B)為復合參考對象中第i個單對象與目標對象的方向關系矩陣，pi為復合參考對象中第i的單對象所占的格網(wǎng)數(shù)目比例

dir(A,B)=p1×dir(A1,B)+p2×dir(A2,B)+…+

pi×dir(At,B)+…+pn×dir(An,B)

(2)

1.2.2目標對象為復合對象

當目標對象B為有m個單對象組成的復合對象時，則分別以這m個單對象為目標對象，求取參考對象與每個單目標對象的方向關系矩陣，然后按照這m個單對象所占網(wǎng)格數(shù)目與對象B所占的網(wǎng)格數(shù)目的比值分配權重，將參考對象與這m個目標對象的關系矩陣相加(式(3))，便得到參考對象與復合目標對象的方向關系矩陣，式中dir(A,Bj)是參考對象A與復合目標對象中第j的單對象的方向關系矩陣，qj為復合目標對象中第j的單對象所占的格網(wǎng)數(shù)目比例

dir(A,B)=q1×dir(A,B1)+q2×dir(A,B2)+…+

qj×dir(A,Bj)+…+qm×dir(A,Bm)

(3)

1.2.3參考對象和目標對象都為復合對象

當參考對象A與目標對象B分別為n個和m個單對象組成的復合對象時，將參考對象劃分為n個對象，逐個以n個單對象為參考對象，求參考對象與復合目標對象的方向關系矩陣，同時將復合目標對象B劃分為m個單目標對象后逐個計算當前參考對象與目標對象間的方向關系矩陣，最后將求得的n個單參考對象與復合目標對象之間的方向關系矩陣按單參考對象網(wǎng)格數(shù)目的權重值相加，即為最終復合參考對象與復合目標對象之間的方向關系矩陣

dir(A,B)=p1×dir(A1,B)+p2×dir(A2,B)+…+pi×dir(Ai,B)+…+pn×dir(An,B)=

p1×(q1×dir(A1,B1)+q2×dir(A1,B2)+…+qi×dir(A1,Bj)+…+qm×dir(A1,Bm))+

p2×(q1×dir(A2,B1)+q2×dir(A2,B2)+…+qj×dir(A2,Bj)+…+qm×dir(A2,Bm))+…+

pj×(q1×dir(Aj,B1)+q2×dir(Aj,B2)+…+qj×dir(Aj,Bj)+…+qm×dir(Aj,Bm))+…+

pn×(q1×dir(An,B1)+q2×dir(An,B2)+…+qj×dir(An,Bj)+…+qm×dir(An,Bm))

(4)

式中，dir(Ai,Bj)為復合參考對象A的第i個單對象與復合目標對象B的第j個單對象的方向關系矩陣，pi為A的第i個對象所占的網(wǎng)格比，qj為B的第j個對象所占的網(wǎng)格比。

2方向相似性度量方法

方向關系可通過方向關系矩陣表達，兩個方向關系之間的相似度即可通過其對應的方向關系矩陣之間的相似度來反映。如圖2所示，計算方向關系之間的相似度s首先需計算方向關系矩陣之間的距離d，然后將d轉換為相異度δ，最后通過δ求相似度s，如下式

(5)

s(D0,D1)=1-δ(D0,D1)

(6)

式中，D為方向關系矩陣；dmax為鄰域圖的最大距離。相似度取值范圍為[0,1]，取值越大表示兩個方向關系越相似，1表示兩個方向關系完全相同。本文將任意兩個方向關系矩陣之間的距離定義為從源方向矩陣D0轉換成目的方向矩陣D1的最小代價，該轉換通過將D0中的非零元素從原來的位置沿著鄰域圖的路徑移動到D1中非零元素的位置來實現(xiàn)。距離d的計算需分兩種情況討論：單元素矩陣間的距離與多元素矩陣間的距離。單元素方向矩陣只有一個非零元素，多元素方向關系矩陣中存在多個非零元素，單元素矩陣可看作一種特殊的多元素矩陣。

2.1單元素方向關系矩陣間的距離

單元素方向矩陣對應九種不同單元素方向關系。單元素矩陣間的最小距離與鄰域圖有關。在9方向分區(qū)上建立合適的鄰域圖有利于提高距離的計算精確度。鄰域圖分為4鄰域圖和8鄰域圖，4鄰域圖和8鄰域圖中各頂點之間的最小距離不同(圖3)。若采用4鄰域圖，式(2)中dmax取值為4，若采用8鄰域圖則其取值為2。

圖2　求解相似度的具體過程Fig.2　Process for assessing similarity

圖3　4鄰域圖(左側值)和8鄰域圖(右側值)的單元素方向關系矩陣間距離Fig.3　4-neighbor distances (left) and 8-neighbor distances (right) between cardinal direction

2.2多元素方向關系矩陣間的距離

這種情況亦分為兩種情形，一是從多元素矩陣轉換為單元素矩陣；二是從多元素矩陣轉換為多元素矩陣。

2.2.1多元素矩陣轉換為單元素矩陣

從多元素矩陣轉換為單元素矩陣，即將多元素的非零元素移入目的矩陣中唯一的非零元素中，需計算多元素矩陣中每個非零元素按其權重與單元素矩陣中非零元素的距離之和

(7)

式中，D0i表示源矩陣D0中的元素值，D1des表示目的矩陣D1中的非零元素，d(D0i,D1des)表示兩個元素之間的距離，即兩個對應位置非零的單元素矩陣之間的距離。由于距離是對稱的，單元素源矩陣與多元素目的矩陣的距離可通過計算目的矩陣到源矩陣的距離獲得。

2.2.2多元素矩陣轉換為多元素矩陣

由于這種情況下不能明確源多元素矩陣各非零元素轉入目的多元素矩陣各非零元素的比例，本文利用方向矩陣間轉換的最小代價計算距離。首先，了解幾個與矩陣相關的概念。

定義1：矩陣D0和D1的共性矩陣C01(式(8))的每個元素的值取D0和D1相應位置上兩個元素的較小值。同理，D1和D0的共性矩陣C10元素的值亦取兩個矩陣中元素的較小值，因而C01=C10

(8)

定義2：矩陣D0與D1的非對稱相異矩陣R01(式(9))為矩陣D0與共性矩陣之差，同理，矩陣D1與D0的非對稱相異矩陣R10為矩陣D1與共性矩陣之差

(9)

定義3：矩陣D0與D1的方向相異矩陣Δ01(式(10))定義為兩個非對稱相異矩陣的差值

Δ10:=R01-R10

(10)

用式(9)中的值替換到式(10)中，即可用D0與D1表示Δ01(式(11))，Δ01元素的值范圍為[-1,1]

Δ01:=D0-D1

(11)

由于方向關系矩陣間的轉換與平衡傳輸問題有一定的共性，借用平衡傳輸問題的解決方法可求解矩陣間轉換的最小代價。

2.2.3多元素矩陣轉換為多元素矩陣

首先了解普通的平衡傳輸問題及其求解思想。平衡傳輸表(balance transportation tableau,BTT)如圖4所示，已知倉庫Wi能供給的貨物量為si，市場Mj的需求量為dj，cij為從Wi到Mj運送單位貨物的成本，已知倉庫的總供給量等于市場的總需求量。如何分配貨物才能使得運輸成本最低，即平衡運輸問題。

圖4　平衡傳輸表Fig.4　The balance transportation tableau

假設最終解決方案中從Wi運送到Mj的貨物為xij。問題演變成確定特定的x，使得代價z最小，且x需滿足倉庫供給量和市場需求量的約束(式(12))

(12)

一種求解xij的方法為Northwest-Corner方法：從平衡傳輸表的左上方開始，先清空一個倉庫或填滿一個市場，將實際運輸量記下，并從相應的行列中減去運輸量，然后刪除已空的倉庫(行)或已滿的市場(列)，如果兩者同時滿足且該行不是剩下的唯一行，則優(yōu)先去掉行，直到所有的行列都刪除，否則繼續(xù)回到新表的左上方重新開始，每次記下的運輸量即為最終xij的解。

方向關系矩陣間的轉換與從倉庫(源矩陣非零元素對應的分區(qū))運輸貨物(非零元素)到市場(目的矩陣非零元素對應的分區(qū))類似，兩矩陣若在同一位置都有非零元素，那么部分非零元素(兩者中值較小的元素值)是不需運送的，即兩者的共性矩陣中的非零元素無須運送，因此非零元素的運送實質是在兩個非對稱相異矩陣中進行。本文采用的算法對普通簡易平衡傳輸算法結果的優(yōu)化，以期得到最優(yōu)結果。該方法需要通過平衡傳輸表T的子集循環(huán)表C來實現(xiàn)，且每一個行列不含有或有且僅有2個C的單元格。

3算例分析

如圖5所示，圖5(a)為大比例尺下的點復合參考對象A和面復合目標對象B，而圖5(b)、(c)為(a)進行綜合后的小比例尺地圖，其中點復合參考對象A保持點狀態(tài)不變，但是圖5(a)中的面復合目標對象B在圖5(b)、(c)中變?yōu)榱它c復合目標對象B；圖5(b)、(c)的不同之處在于點復合目標對象的單個點對象間的位置略有差別。先對圖5(b)、(c)進行比較，計算兩者與圖5(a)之間的相似度。

圖5　大比例下點和面轉為小比例尺下點和點Fig.5　Collapsing a composite point and a composite region at large scale to a pair of point at small scale

3.1復合參考對象的方向關系矩陣表示

首先，需表示出3種情形下參考對象與目標對象的方向關系矩陣，以圖5(a)為例。如圖6，按照分解的思想，先將復合參考對象A劃分為3個單參考對象(圖6(b)—(d))分別求取參考對象與復合目標對象之間的方向關系矩陣。

圖6　劃分復合參考對象AFig.6　Split the composite reference object A

以劃分后的A1參考對象為例，再將復合目標對象B為3個單目標對象(圖7)。

圖7　劃分復合目標對象BFig.7　Split the composite target object B

求得單參考對象A1與3個單目標對象的方向關系矩陣如下式

(13)

根據(jù)目標對象所占網(wǎng)格的權重比值可得A1與目標對象之間的方向關系矩陣如下式

(14)

同樣的方法可求得單參考對象A2、A3與目標對象之間的方向關系矩陣如式(14)。再通過各單參考對象的所占的網(wǎng)格比例權重，可計算得到復合參考對象A與復合目標對象B之間的方向關系矩陣如式(15)

(15)

同理，可得圖6(b)、(c)的方向關系矩陣為

(16)

(17)

3.2復合參考對象方向關系相似度計算

由于圖5(a)、(b)、(c)的方向關系矩陣均為多元素矩陣，因此通過平衡傳輸優(yōu)化算法進行相似度的計算；即首先通過西北角算法得到初始解后再通過傳輸算法進行優(yōu)化。以圖5(a)、(b)間的方向相似度計算為例。

首先，得到圖5(a)、(b)與圖5(a)、(c)之間方向關系矩陣的方向相異矩陣(式(18))。得到圖5(a)、(b)之間平衡傳輸表如圖8，通過西北角算法得到解為：x11=21、x21=11、x11=4

(18)

圖8　實例中的平衡傳輸表Fig.8　TTB in the example

將這3個解所處的單元格標記為基本單元格(圖9)，開始通過傳輸算法進行優(yōu)化，首先給所有a、b值賦值；賦值后用cij-ai-bj替代cij；非基本單元格中有負值存在，則還需繼續(xù)優(yōu)化，取最小值-4所在單元格為“獲取”單元格。

圖9　優(yōu)化算法Fig.9　Optimum algorithm

圖9中基本單元格和“獲取”單元格所在的單元格不能構成循環(huán)表，最后兩行行都只有1個可以形成循環(huán)表C的單元格，而非0或者2個。因此，當前的解集已是最優(yōu)。所以圖5(a)、(b)之間的運輸代價z1=(3×21+2×11+2×4)/342=0.271 929 825,相似度為s1=1-0.271 929 828/4=0.932 017 543 859 649;

同理，對圖5(a)、(c)的傳輸表(圖8)進行優(yōu)化，如圖10先找到基本表的組成單元格；然后對所有的a、b進行賦值；再替換所有的c值；最后找到最小的c值所在的單元格框住作為“獲取”單元格并其他基本單元格中找到與該“獲取”格可組成循環(huán)表的單元格，并找到這些選中的基本單元格中最小的作為選定的“給予”格，將剩余的兩個單元格交錯的賦為“獲取”和“給予”格；最后根據(jù)所賦予的符號加上或減去選定的“給予”的解值，并將框格圈入基本格中，將選定的“給予”格剔出基本格中，將最初的c值替換回。

圖10　優(yōu)化算法——找到基本表Fig.10　Optimum algorithm

計算得出圖5(a)、(c)之間的運輸代價z2=(3×4+1×6+1×34+1×17+1×32)/342=0.295 321 637 426 9,相似度為s2=1-0.295 321 637 426 9/4=0.926 169 590 643 275

而s1=0.932大于s2=0.926 2，亦即圖5(a)、(b)之間的方向相似度大于圖5(a)、(c)之間的方向相似度，結果表明圖5(a)、(b)之間的方向相似度略高于圖5(a)、(c)之間的方向相似度。圖5(a)、(b)中B2都在A1的東北方向，而在圖5(c)中B2在A1的正東方向。因此就這一點而言，從人的主觀視覺上判斷，圖5(a)、(b)之間的方向相似度也應該是高于圖5(a)、(c)之間的方向相似度的。就圖5(b)、(c)與(a)相似度相關問題，隨機對256人進行問卷調查，調查表如表1所示。從圖11可看出，受訪人員給圖5(a)、(b)之間的相似度的打分集中在8～10分，給圖5(a)、(c)之間相似度打分集中在6～8分；調查結果表明，92.58%的受訪人員認為圖5(a)、(b)之間的相似度更高，試驗結果符合人的認知。

表1　調查表

圖11　調查結果Fig.11　Results of questionnaire

3.3復合參考對象穩(wěn)定性度評估

對上面實例進一步擴展，圖12(a)的場景中參考對象和目標對象均為復合面對象，將圖12(a)中目標對象中的兩個單對象B2、B3的位置圍繞復合對象A進行順時針旋轉，分別得到圖12(b)和(c)狀態(tài)。

圖12　旋轉目標對象中的部分單對象Fig.12　Rotate parts of the complex target object B

先求出圖12中(a)、(b)、(c)三者的方向矩陣(式(19))，從而得到圖12(a)、(b)與(a)、(c)間的方向相異矩陣(式(20))

(19)

(20)

通過優(yōu)化交通平衡傳輸算法可以得到圖12(a)、(b)與(a)、(c)傳輸最小代價以及相似度如下，z1=(1×28+1×6+1×1)/114=0.307 017 543 859 649 1,相似度為s1=1-0.271 929 828/4=0.923 245 614 035 087 7;z2=(4×15+3×7+2×6+1×4)/114=0.850 877 192 982 5,相似度為s1=1-0.271 929 828/4=0.787 280 701 754;由于圖12(b)相較圖12(c)，相對圖12(a)旋轉的角度較小，因此可以通過視覺直觀地判斷出圖12(a)、(b)之間的相似度更高，而計算結果s1大于s2，與人的認知一致?，F(xiàn)對參考對象進行調整，改變單個參考對象的面積(圖13)，先求得圖13(a)、(b)、(c)的方向矩陣(式(21))。

圖13　改變參考對象面積比例Fig.13　Change the area rate of the complex reference object A

(21)

再求得圖13(a)、(b)與(a)、(c)間的方向相異矩陣(式(22))

(22)

通過優(yōu)化交通平衡傳輸算法可以得到圖13(a)、(b)與(a)、(c)傳輸最小代價以及相似度。z1=649/798=0.813 283 208 020 050 1，相似度為s1=0.796 679 197 994 987 5;z2=1086/798=1.360 902 255 639 098，相似度為s1=0.659 774 436 090 225 6。

由此可見，即使改變參考對象的面積分布，使圖13(a)、(b)與圖13(a)、(c)之間的相似度更接近，本文提出的計算方法仍能準確地判斷出正確地方向關系。

4總結

本文通過方向關系矩陣間的相似度來評判制圖綜合后復合空間對象結果的合理性。利用方向關系矩陣量化模型的特點，計算多尺度復合空間場景中方向對間的相似度，從而進行比較和評判。

本文模型直接通過網(wǎng)格數(shù)目比例分布得到方向關系矩陣，并計算復合對象的方向相似度，簡單直觀易計算，同時在計算多元素方向關系矩陣間的距離時，采用了傳輸算法對傳統(tǒng)的西北角算法進行優(yōu)化，使得計算結果更精確。本文的方法解決了復合對象方向關系間的相似性度量問題。下一步工作將優(yōu)化網(wǎng)格計數(shù)方法，顧及多尺度復合對象各個組成部分的幾何形狀特征優(yōu)化其計算權重，以提高復合空間對象方向相似度的計算準確度。

參考文獻：

[1]閆浩文,褚衍東.多尺度地圖空間相似關系基本問題研究[J]. 地理與地理信息科學, 2009, 25(4): 42-44, 48.

YANHaowen,CHUYandong.OntheFundamentalIssuesofSpatialSimilarityRelationsinMulti-scaleMaps[J].GeographyandGeo-InformationScience, 2009, 25(4): 42-44, 48.

[2]HAAR R. Computational Models of Spatial Relations[R]. Technical Report: TR-478, MSC-72-03610, Computer Science, University of Maryland, College Park, MD, 1976.

[3]ALLEN J F. Maintaining Knowledge about Temporal Intervals[J]. Communications of the ACM, 1983, 26(11): 832-843.

[4]GUESGEN H W.Spatial Reasoning Based on Allen’s Temporal Logic[R]. Technical Report: TR-89-049, International Computer Science Institute, Berkley, CA, 1989.

[5]BALBIANI P, CONDOTTA J F, CERRO L F D. A new Tractable Subclass of the Rectangle Algebra[C]∥IJCAI ’99 Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann Publishers Inc., 1999: 442-447.

[6]BALBIANI P, CONDOTTA J. A Model for Reasoning about Bidimensional Temporal Relations[C]∥Proceedings of Principles of Knowledge Representation and Reasoning (KR). Trento: [s.n.], 1998, 124-130.

[7]CHANG Shikuo, SHI Qingyun, Yan Chengwen. Iconic Indexing by 2-D Strings[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1987, 9(3): 413-428.

[8]PAPADIAS D, SELLIS T, THEODORIDIS Y, et al. Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-Trees[C]∥Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1995: 92-103.

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

[10]GOYAL R K, EGENHOFER M J. Similarity of Cardinal Directions[M]∥JENSEN C S, SCHNEIDER M, SEEGER B, et al. Advances in Spatial and Temporal Databases: Lecture Notes in Computer Science. Berlin Heidelberg: Springer, 2001: 36-55.

[11]SKIADOPOULOS S,KOUBARAKIS M.Composing Cardinal Direction Relations[J]. Artificial Intelligence, 2004, 152(2): 143-171.

[12]丁虹. 空間相似性理論與計算模型的研究[D]. 武漢:武漢大學, 2004.

DING Hong. A Study on Spatial Similarity Theory and Calculation Model[D]. Wuhan: Wuhan University, 2004.

[13]郭慶勝, 丁虹. 基于柵格數(shù)據(jù)的面狀目標空間方向相似性研究[J]. 武漢大學學報(信息科學版), 2004, 29(5): 447-450.

GUO Qingsheng, DING Hong. Similarity for Spatial Directions between Areal Objects in Raster Data[J]. Geomatics and Information Science of Wuhan University, 2004, 29(5): 447-450.

[14]安曉亞. 空間數(shù)據(jù)幾何相似性度量理論方法與應用研究[D]. 鄭州: 信息工程大學, 2011.

AN Xiaoya.Research on Theory,Methods and Applications of Geometry Similarity Measurement for Spatial Data[D]. Zhengzhou: The PLA Information Engineering University,

2011.

[15]閆浩文, 郭仁忠. 空間方向關系形式化描述模型研究[J]. 測繪學報, 2003, 32(1): 42-46.

YAN Haowen, GUO Renzhong. Research on Formal Description Model of Directional Relationships[J]. Acta Geodaetica et Cartographica Sinica, 2003, 32(1): 42-46.

[16]杜世宏, 王橋, 楊一鵬. 一種定性細節(jié)方向關系的表達模型[J]. 中國圖象圖形學報, 2004, 9(12): 1496-1503.

DU Shihong, WANG Qiao, YANG Yipeng. A Qualitative Description Model of Detailed Direction Relations[J]. Journal of Image and Graphics, 2004, 9(12): 1496-1503.

[17]杜世宏, 王橋, 楊一鵬, 等. 空間方向關系模糊描述[J]. 計算機輔助設計與圖形學報, 2005, 17(8): 1744-1751.

DU Shihong, WANG Qiao, YANG Yipeng, et al. Fuzzy Description of Spatial Direction Relations[J]. Journal of Computer-aided Design & Computer Graphics, 2005, 17(8): 1744-1751.

[18]杜世宏, 王橋, 魏斌, 等. 空間方向關系粗糙推理[J]. 測繪學報, 2003, 32(4): 334-338.

DU Shihong, WANG Qiao, WEI Bin, et al. Spatial Orientational Relations Rough Reasoning[J]. Acta Geodaetica et Cartographica Sinica, 2003, 32(4): 334-338.

[19]曹菡, 陳軍, 杜道生. 空間目標方向關系的定性擴展描述[J]. 測繪學報, 2001, 30(2): 162-167.

CAO Han, CHEN Jun, DU Daosheng. Qualitative Extention Description for Cardinal Directions of Spatial Objects[J]. Acta Geodaetica et Cartographica Sinica, 2001, 30(2): 162-167.

[20]何建華, 劉耀林. GIS中拓撲和方向關系推理模型[J]. 測繪學報, 2004, 33(2): 156-162.

HE Jianhua, LIU Yaolin. An Integrated Model for Topology & Direction Relation Reasoning[J]. Acta Geodaetica et Cartographica Sinica, 2004, 33(2): 156-162.

[21]吳靜, 程朋根, 陳斐, 等. 空間目標的方向關系定性推理[J]. 測繪學報, 2006, 35(2): 160-165.

WU Jing,CHENG Penggen,CHEN Fei,et al. Qualitative Reasoning for Direction Relation of Spatial Objects[J]. Acta Geodaetica et Cartographica Sinica, 2006, 35(2): 160-165.

(責任編輯：宋啟凡)

A Quantitative Calculation Method of Composite Spatial Direction Similarity Concerning Scale Differences

CHEN Zhanlong1,2，GONG Xi1，WU Liang1，AN Xiaoya2,3

1. Department of Information Engineering, China University of Geosciences, Wuhan 430074, China; 2. State Key Laboratory of Geography Information Engineering, Xi’an 710054, China; 3. Xi’an Research Institute of Surveying and Mapping, Xi’an 710054, China

Abstract：This article introduces a new model for direction relations between multiple spatial objects at multiple scales and a corresponding similarity assessment method. The model is an improvement of direction relation matrix, which quantitatively models direction relations on object scale, and by the idea of decomposition and means of the optimum solution of the transportation problem to solve the minimum conversion cost between multiple direction matrices, namely distance between a pair of matrices, thus quantified the difference between a pair of directions, finally obtain the similarity values between arbitrary pairs of multiple spatial objects and compare the results. Experiments on calculating similarity between objects at different scales show that the presented method is efficient, accurate, and capable of obtaining results consistent with human cognition.

Key words：multi-scales; multiple spatial objects; direction similarity; direction relation matrix;

基金項目：國家自然科學基金(41401443；41201469)；國家科技支撐計劃(2011BAH06B04)；地理信息工程國家重點實驗室開放基金(SKLGIE2013-Z-4-1)；測繪遙感信息工程國家重點實驗室資助項目(13I02)；中央高?；究蒲袠I(yè)務費專項(CUGL130260)

中圖分類號：P208

文獻標識碼：A

文章編號：1001-1595(2016)03-0362-10

Corresponding author：WU Liang

通信作者：吳亮

作者簡介：第一 陳占龍 (1980—)，男，博士，副教授，主要研究方向為空間分析算法、空間推理、地理信息系統(tǒng)軟件開發(fā)與應用。

收稿日期：2015-02-16

引文格式：陳占龍，龔希，吳亮，等.顧及尺度差異的復合空間對象方向相似度定量計算模型[J].測繪學報，2016,45(3)：362-371. DOI:10.11947/j.AGCS.2016.20150099.

CHEN Zhanlong，GONG Xi，WU Liang，et al.A Quantitative Calculation Method of Composite Spatial Direction Similarity Concerning Scale Differences[J]. Acta Geodaetica et Cartographica Sinica,2016,45(3):362-371. DOI:10.11947/j.AGCS.2016.20150099.

修回日期： 2015-12-15

First author： CHEN Zhanlong(1980—)，male， PhD，associate professor，majors in spatial analysis algorithms，spatial reasoning，geographic information system software application and development.

E-mail： wuliang133@189.cn