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

1. 中國(guó)地質(zhì)大學(xué)(武漢)信息工程學(xué)院,湖北 武漢430074; 2. 地理信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室,陜西 西安710054; 3. 西安測(cè)繪研究所,陜西 西安 710054

?

顧及尺度差異的復(fù)合空間對(duì)象方向相似度定量計(jì)算模型

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

1. 中國(guó)地質(zhì)大學(xué)(武漢)信息工程學(xué)院,湖北 武漢430074; 2. 地理信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室,陜西 西安710054; 3. 西安測(cè)繪研究所,陜西 西安 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)

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

關(guān)鍵詞：多尺度；復(fù)合空間對(duì)象；方向相似度；方向關(guān)系矩陣；分解

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

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

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

1復(fù)合空間對(duì)象及其方向關(guān)系描述

1.1復(fù)合對(duì)象

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

圖1　復(fù)合對(duì)象Fig.1　Composite geometric objects

1.2復(fù)合空間對(duì)象的方向關(guān)系矩陣

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

(1)

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

1.2.1參考對(duì)象為復(fù)合對(duì)象

當(dāng)參考對(duì)象A為由n個(gè)單對(duì)象組成的復(fù)合對(duì)象時(shí)，則分別以這n個(gè)單對(duì)象為參考對(duì)象，求取每個(gè)單參考對(duì)象與目標(biāo)對(duì)象的方向關(guān)系矩陣，然后按照這n個(gè)單對(duì)象所占網(wǎng)格數(shù)目與對(duì)象A所占的網(wǎng)格數(shù)目的比值分配權(quán)重，將n個(gè)單對(duì)象與目標(biāo)對(duì)象的關(guān)系矩陣相加(式(2))，便得到復(fù)合對(duì)象與目標(biāo)對(duì)象的方向關(guān)系矩陣，式中dir(Ai,B)為復(fù)合參考對(duì)象中第i個(gè)單對(duì)象與目標(biāo)對(duì)象的方向關(guān)系矩陣，pi為復(fù)合參考對(duì)象中第i的單對(duì)象所占的格網(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目標(biāo)對(duì)象為復(fù)合對(duì)象

當(dāng)目標(biāo)對(duì)象B為有m個(gè)單對(duì)象組成的復(fù)合對(duì)象時(shí)，則分別以這m個(gè)單對(duì)象為目標(biāo)對(duì)象，求取參考對(duì)象與每個(gè)單目標(biāo)對(duì)象的方向關(guān)系矩陣，然后按照這m個(gè)單對(duì)象所占網(wǎng)格數(shù)目與對(duì)象B所占的網(wǎng)格數(shù)目的比值分配權(quán)重，將參考對(duì)象與這m個(gè)目標(biāo)對(duì)象的關(guān)系矩陣相加(式(3))，便得到參考對(duì)象與復(fù)合目標(biāo)對(duì)象的方向關(guān)系矩陣，式中dir(A,Bj)是參考對(duì)象A與復(fù)合目標(biāo)對(duì)象中第j的單對(duì)象的方向關(guān)系矩陣，qj為復(fù)合目標(biāo)對(duì)象中第j的單對(duì)象所占的格網(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參考對(duì)象和目標(biāo)對(duì)象都為復(fù)合對(duì)象

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

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)為復(fù)合參考對(duì)象A的第i個(gè)單對(duì)象與復(fù)合目標(biāo)對(duì)象B的第j個(gè)單對(duì)象的方向關(guān)系矩陣，pi為A的第i個(gè)對(duì)象所占的網(wǎng)格比，qj為B的第j個(gè)對(duì)象所占的網(wǎng)格比。

2方向相似性度量方法

方向關(guān)系可通過(guò)方向關(guān)系矩陣表達(dá)，兩個(gè)方向關(guān)系之間的相似度即可通過(guò)其對(duì)應(yīng)的方向關(guān)系矩陣之間的相似度來(lái)反映。如圖2所示，計(jì)算方向關(guān)系之間的相似度s首先需計(jì)算方向關(guān)系矩陣之間的距離d，然后將d轉(zhuǎn)換為相異度δ，最后通過(guò)δ求相似度s，如下式

(5)

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

(6)

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

2.1單元素方向關(guān)系矩陣間的距離

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

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

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

2.2多元素方向關(guān)系矩陣間的距離

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

2.2.1多元素矩陣轉(zhuǎn)換為單元素矩陣

從多元素矩陣轉(zhuǎn)換為單元素矩陣，即將多元素的非零元素移入目的矩陣中唯一的非零元素中，需計(jì)算多元素矩陣中每個(gè)非零元素按其權(quán)重與單元素矩陣中非零元素的距離之和

(7)

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

2.2.2多元素矩陣轉(zhuǎn)換為多元素矩陣

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

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

(8)

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

(9)

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

Δ10:=R01-R10

(10)

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

Δ01:=D0-D1

(11)

由于方向關(guān)系矩陣間的轉(zhuǎn)換與平衡傳輸問(wèn)題有一定的共性，借用平衡傳輸問(wèn)題的解決方法可求解矩陣間轉(zhuǎn)換的最小代價(jià)。

2.2.3多元素矩陣轉(zhuǎn)換為多元素矩陣

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

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

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

(12)

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

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

3算例分析

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

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

3.1復(fù)合參考對(duì)象的方向關(guān)系矩陣表示

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

圖6　劃分復(fù)合參考對(duì)象AFig.6　Split the composite reference object A

以劃分后的A1參考對(duì)象為例，再將復(fù)合目標(biāo)對(duì)象B為3個(gè)單目標(biāo)對(duì)象(圖7)。

圖7　劃分復(fù)合目標(biāo)對(duì)象BFig.7　Split the composite target object B

求得單參考對(duì)象A1與3個(gè)單目標(biāo)對(duì)象的方向關(guān)系矩陣如下式

(13)

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

(14)

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

(15)

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

(16)

(17)

3.2復(fù)合參考對(duì)象方向關(guān)系相似度計(jì)算

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

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

(18)

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

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

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

圖9中基本單元格和“獲取”單元格所在的單元格不能構(gòu)成循環(huán)表，最后兩行行都只有1個(gè)可以形成循環(huán)表C的單元格，而非0或者2個(gè)。因此，當(dāng)前的解集已是最優(yōu)。所以圖5(a)、(b)之間的運(yùn)輸代價(jià)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;

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

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

計(jì)算得出圖5(a)、(c)之間的運(yùn)輸代價(jià)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)之間的方向相似度，結(jié)果表明圖5(a)、(b)之間的方向相似度略高于圖5(a)、(c)之間的方向相似度。圖5(a)、(b)中B2都在A1的東北方向，而在圖5(c)中B2在A1的正東方向。因此就這一點(diǎn)而言，從人的主觀視覺(jué)上判斷，圖5(a)、(b)之間的方向相似度也應(yīng)該是高于圖5(a)、(c)之間的方向相似度的。就圖5(b)、(c)與(a)相似度相關(guān)問(wèn)題，隨機(jī)對(duì)256人進(jìn)行問(wèn)卷調(diào)查，調(diào)查表如表1所示。從圖11可看出，受訪人員給圖5(a)、(b)之間的相似度的打分集中在8～10分，給圖5(a)、(c)之間相似度打分集中在6～8分；調(diào)查結(jié)果表明，92.58%的受訪人員認(rèn)為圖5(a)、(b)之間的相似度更高，試驗(yàn)結(jié)果符合人的認(rèn)知。

表1　調(diào)查表

圖11　調(diào)查結(jié)果Fig.11　Results of questionnaire

3.3復(fù)合參考對(duì)象穩(wěn)定性度評(píng)估

對(duì)上面實(shí)例進(jìn)一步擴(kuò)展，圖12(a)的場(chǎng)景中參考對(duì)象和目標(biāo)對(duì)象均為復(fù)合面對(duì)象，將圖12(a)中目標(biāo)對(duì)象中的兩個(gè)單對(duì)象B2、B3的位置圍繞復(fù)合對(duì)象A進(jìn)行順時(shí)針旋轉(zhuǎn)，分別得到圖12(b)和(c)狀態(tài)。

圖12　旋轉(zhuǎn)目標(biāo)對(duì)象中的部分單對(duì)象Fig.12　Rotate parts of the complex target object B

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

(19)

(20)

通過(guò)優(yōu)化交通平衡傳輸算法可以得到圖12(a)、(b)與(a)、(c)傳輸最小代價(jià)以及相似度如下，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)，相對(duì)圖12(a)旋轉(zhuǎn)的角度較小，因此可以通過(guò)視覺(jué)直觀地判斷出圖12(a)、(b)之間的相似度更高，而計(jì)算結(jié)果s1大于s2，與人的認(rèn)知一致。現(xiàn)對(duì)參考對(duì)象進(jìn)行調(diào)整，改變單個(gè)參考對(duì)象的面積(圖13)，先求得圖13(a)、(b)、(c)的方向矩陣(式(21))。

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

(21)

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

(22)

通過(guò)優(yōu)化交通平衡傳輸算法可以得到圖13(a)、(b)與(a)、(c)傳輸最小代價(jià)以及相似度。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。

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

4總結(jié)

本文通過(guò)方向關(guān)系矩陣間的相似度來(lái)評(píng)判制圖綜合后復(fù)合空間對(duì)象結(jié)果的合理性。利用方向關(guān)系矩陣量化模型的特點(diǎn)，計(jì)算多尺度復(fù)合空間場(chǎng)景中方向?qū)﹂g的相似度，從而進(jìn)行比較和評(píng)判。

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

參考文獻(xiàn)：

[1]閆浩文,褚衍東.多尺度地圖空間相似關(guān)系基本問(wèn)題研究[J]. 地理與地理信息科學(xué), 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]丁虹. 空間相似性理論與計(jì)算模型的研究[D]. 武漢:武漢大學(xué), 2004.

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

[13]郭慶勝, 丁虹. 基于柵格數(shù)據(jù)的面狀目標(biāo)空間方向相似性研究[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 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ù)幾何相似性度量理論方法與應(yīng)用研究[D]. 鄭州: 信息工程大學(xué), 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]閆浩文, 郭仁忠. 空間方向關(guān)系形式化描述模型研究[J]. 測(cè)繪學(xué)報(bào), 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]杜世宏, 王橋, 楊一鵬. 一種定性細(xì)節(jié)方向關(guān)系的表達(dá)模型[J]. 中國(guó)圖象圖形學(xué)報(bào), 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]杜世宏, 王橋, 楊一鵬, 等. 空間方向關(guān)系模糊描述[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào), 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]杜世宏, 王橋, 魏斌, 等. 空間方向關(guān)系粗糙推理[J]. 測(cè)繪學(xué)報(bào), 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]曹菡, 陳軍, 杜道生. 空間目標(biāo)方向關(guān)系的定性擴(kuò)展描述[J]. 測(cè)繪學(xué)報(bào), 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中拓?fù)浜头较蜿P(guān)系推理模型[J]. 測(cè)繪學(xué)報(bào), 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]吳靜, 程朋根, 陳斐, 等. 空間目標(biāo)的方向關(guān)系定性推理[J]. 測(cè)繪學(xué)報(bào), 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.

(責(zé)任編輯：宋啟凡)

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;

基金項(xiàng)目：國(guó)家自然科學(xué)基金(41401443；41201469)；國(guó)家科技支撐計(jì)劃(2011BAH06B04)；地理信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金(SKLGIE2013-Z-4-1)；測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目(13I02)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(xiàng)(CUGL130260)

中圖分類(lèi)號(hào)：P208

文獻(xiàn)標(biāo)識(shí)碼：A

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

Corresponding author：WU Liang

通信作者：吳亮

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

收稿日期：2015-02-16

引文格式：陳占龍，龔希，吳亮，等.顧及尺度差異的復(fù)合空間對(duì)象方向相似度定量計(jì)算模型[J].測(cè)繪學(xué)報(bào)，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