空間方向相似性二元組模型度量方法

龔 希，謝 忠，周 林，何占軍

1. 中國(guó)地質(zhì)大學(xué)(武漢)地理與信息工程學(xué)院，湖北 武漢 430074; 2. 湖北第二師范學(xué)院計(jì)算機(jī)學(xué)院，湖北 武漢 430074; 3. 國(guó)家地理信息系統(tǒng)工程技術(shù)研究中心，湖北 武漢 430074

空間相似性度量對(duì)空間信息的檢索、融合與數(shù)據(jù)挖掘至關(guān)重要[1]。廣義上的空間相似性指根據(jù)特定內(nèi)容和比例尺對(duì)空間的匹配和排序，涉及空間對(duì)象幾何屬性、對(duì)象間的空間關(guān)系等多種因素[2]。其中，方向關(guān)系作為一類重要的空間關(guān)系，在空間相似性度量研究中引起廣泛關(guān)注[3-6]，方向關(guān)系的相似性度量不僅對(duì)矢量空間數(shù)據(jù)的檢索[7-8]、查詢[9-10]、匹配[11-12]、質(zhì)量評(píng)估[13]等任務(wù)提供重要依據(jù)，在遙感影像檢索[14-15]任務(wù)中也有應(yīng)用。

現(xiàn)階段方向關(guān)系模型可分為定性模型和定量模型兩大類。定性方向關(guān)系模型中，經(jīng)典的三角模型[16]、MBR模型[17]、一維間隔模型[18]等為早期空間推理提供重要支撐，其相關(guān)理論為后續(xù)定性方向關(guān)系模型的發(fā)展奠定了基礎(chǔ)，并產(chǎn)生了諸多改進(jìn)模型。文獻(xiàn)[19]在以點(diǎn)、線、面為參照目標(biāo)的空間目標(biāo)間建立方向關(guān)系描述的3層模式結(jié)構(gòu)，實(shí)現(xiàn)更細(xì)致準(zhǔn)確的方向關(guān)系描述。文獻(xiàn)[20]針對(duì)目標(biāo)對(duì)象與參照對(duì)象的外接矩形相交或位于其內(nèi)時(shí)的方向關(guān)系，提出了一種可表達(dá)與參照對(duì)象外接矩形內(nèi)部有關(guān)信息的細(xì)節(jié)方向關(guān)系表達(dá)模型。以上定性方向關(guān)系模型實(shí)現(xiàn)不同復(fù)雜程度的方向關(guān)系表達(dá)，對(duì)空間方向關(guān)系推理具有重要意義，但方向關(guān)系間的相似性度量依賴于定量方向關(guān)系模型完成，無(wú)法通過(guò)定性模型實(shí)現(xiàn)。定量方向關(guān)系模型中，文獻(xiàn)[21]通過(guò)方向關(guān)系矩陣表示對(duì)象在不同方向片區(qū)的分布，并利用平衡傳輸方法計(jì)算矩陣間距離從而實(shí)現(xiàn)方向關(guān)系的相似度度量。該模型具有較高的可比性，引起學(xué)者們的廣泛關(guān)注并產(chǎn)生諸多針對(duì)性的改進(jìn)方法。文獻(xiàn)[22]將方向關(guān)系矩陣拓展至面群間的方向關(guān)系表達(dá)及相似度計(jì)算。文獻(xiàn)[23]則提出基于柵格數(shù)據(jù)的面狀目標(biāo)空間方向矩陣，簡(jiǎn)化方向關(guān)系矩陣元素值和矩陣間距離的計(jì)算方法，極大降低了方向關(guān)系矩陣相似性度量方法的復(fù)雜度，證明了柵格單元作為基本對(duì)象計(jì)算空間關(guān)系相似值的可行性。文獻(xiàn)[24]在此基礎(chǔ)上提出了基于格網(wǎng)的方向關(guān)系矩陣，利用規(guī)律格網(wǎng)單元陣列劃分對(duì)象空間，快速完成對(duì)任意尺度對(duì)象間的方向關(guān)系的表達(dá)，解決了多尺度對(duì)象間的相似性度量問(wèn)題。文獻(xiàn)[25]采用分解思想，進(jìn)一步將格網(wǎng)方向關(guān)系矩陣應(yīng)用到多尺度復(fù)合對(duì)象間的方向關(guān)系表達(dá)，并優(yōu)化方向關(guān)系矩陣距離計(jì)算方法，實(shí)現(xiàn)對(duì)復(fù)雜多尺度對(duì)象群間的方向關(guān)系相似性度量。

上述方法針對(duì)經(jīng)典方向關(guān)系矩陣模型[21]的元素表達(dá)方式、距離計(jì)算方法、模型應(yīng)用范圍等方面進(jìn)行了針對(duì)性的改進(jìn)，取得一定成果，但仍存在以下問(wèn)題：①對(duì)同一方向片區(qū)內(nèi)的方向關(guān)系變化識(shí)別不足；②鄰域圖的定義與人類實(shí)際認(rèn)知有差異，且計(jì)算粒度較粗；③方向關(guān)系矩陣距離的計(jì)算廣泛借鑒運(yùn)籌學(xué)方法，但僅采用初始基作為最終解，其結(jié)果并非最優(yōu)解，一定程度上降低了相似性度量的準(zhǔn)確性。

上述基于經(jīng)典方向關(guān)系矩陣[21]改進(jìn)的模型中，文獻(xiàn)[24]提出的格網(wǎng)方向關(guān)系矩陣具有表達(dá)簡(jiǎn)單快速，粒度可調(diào)且可靈活應(yīng)用于多尺度對(duì)象等優(yōu)點(diǎn)。為進(jìn)一步探索對(duì)方向關(guān)系矩陣模型的高效改進(jìn)，本文以格網(wǎng)方向關(guān)系矩陣[24]為基礎(chǔ)，引入對(duì)象方向片區(qū)質(zhì)心角度表示對(duì)象的位置分布，建立可同時(shí)記錄目標(biāo)對(duì)象分布比例及分布位置信息的方向關(guān)系二元組，實(shí)現(xiàn)粒度更高的方向關(guān)系表達(dá)，區(qū)分目標(biāo)對(duì)象分布在同一方向片區(qū)內(nèi)的方向關(guān)系；同時(shí)結(jié)合人類空間認(rèn)知優(yōu)化鄰域圖，建立適用于任意方向間的基準(zhǔn)方向距離；并引入EMD(Earth mover 's distance)[26]距離計(jì)算方向關(guān)系矩陣間的最小轉(zhuǎn)化代價(jià)，實(shí)現(xiàn)對(duì)任意方向關(guān)系間相似度的精確度量。本文所提方向關(guān)系二元組模型亦可基于經(jīng)典方向關(guān)系模型進(jìn)行改進(jìn)。

1 方向關(guān)系矩陣二元組

1.1 格網(wǎng)方向關(guān)系矩陣

方向關(guān)系矩陣模型利用投影法將參考對(duì)象A所在空間劃分為{N,S,E,W,NE,SE,SW,NW,O}9個(gè)方向片區(qū)[21]，可通過(guò)3×3矩陣記錄目標(biāo)對(duì)象B在9個(gè)方向片區(qū)的分布情況。格網(wǎng)方向關(guān)系矩陣[24]引入規(guī)律格網(wǎng)單元將空間進(jìn)一步劃分，通過(guò)B在各方向片區(qū)所占格網(wǎng)單元數(shù)目比例，將A、B間的方向關(guān)系表示為

(1)

矩陣各元素的分子為B在各方向片區(qū)所占格網(wǎng)單元數(shù)目，分母NB為B所占格網(wǎng)單元總數(shù)，其中A、B對(duì)象不限尺度，點(diǎn)、線、面對(duì)象在各方向片區(qū)所占格網(wǎng)單元數(shù)目均可被快速計(jì)算出[24]。但目前不論是經(jīng)典方向關(guān)系矩陣模型，還是基于其改進(jìn)的各類模型，均無(wú)法區(qū)分同一方向片區(qū)內(nèi)的方向關(guān)系變化。圖1(a)中，場(chǎng)景2與場(chǎng)景3的方向關(guān)系更相似，但圖1(b)根據(jù)方向關(guān)系矩陣模型劃分場(chǎng)景空間后，場(chǎng)景1和場(chǎng)景2中B分布在同一方向片區(qū)，兩者方向關(guān)系矩陣相同，方向關(guān)系相似度為1，高于場(chǎng)景2與場(chǎng)景3間的方向關(guān)系相似度。這與人類的實(shí)際認(rèn)知有一定偏差，因此方向關(guān)系矩陣模型對(duì)方向關(guān)系的表示及相似性度量仍存在一定缺陷。

圖1 空間劃分前后的場(chǎng)景對(duì)比Fig.1 Scenes before and after partitioning the space

1.2 融入質(zhì)心方位角的方向關(guān)系二元組表達(dá)

當(dāng)目標(biāo)對(duì)象在同一方向片區(qū)內(nèi)變化時(shí)，可通過(guò)對(duì)象質(zhì)心方位角間的差異對(duì)方向關(guān)系加以區(qū)分。目標(biāo)對(duì)象的質(zhì)心方位角β∈[0,2π]為參考對(duì)象外心的指北方向線，按順時(shí)針?lè)较蛑猎擖c(diǎn)與目標(biāo)對(duì)象質(zhì)心連線的水平夾角。與方向關(guān)系矩陣類似，本文建立3×3的質(zhì)心方向矩陣，記錄目標(biāo)對(duì)象落在各方向片區(qū)內(nèi)子部分的質(zhì)心方位角，目標(biāo)對(duì)象B相對(duì)參考對(duì)象A的質(zhì)心方向關(guān)系矩陣表示為

(2)

圖2 基于格網(wǎng)單元求取目標(biāo)對(duì)象在不同方向片區(qū)內(nèi)的質(zhì)心方位角Fig.2 Obtaining centroid azimuth of grids

β∈[0,2π]

(3)

1.3 復(fù)合對(duì)象間的方向關(guān)系二元組表達(dá)

(4)

(1≤i≤n)

(5)

結(jié)合式(4)、式(5)，可得復(fù)合對(duì)象A與B間的格網(wǎng)方向關(guān)系矩陣為

(6)

(1≤i≤n)

(7)

(8)

2 基于方向關(guān)系二元組的方向關(guān)系相似性度量

方向關(guān)系二元組間的相似性度量同時(shí)考慮目標(biāo)對(duì)象在各方向片區(qū)內(nèi)分布比例及質(zhì)心方位角的變化，整體流程如圖3所示。傳統(tǒng)方向關(guān)系矩陣模型在計(jì)算矩陣距離時(shí)所使用的基準(zhǔn)方向距離粒度較粗，僅定義了9個(gè)方向片區(qū)間的距離，未能描述任意方向間的距離，且方向片區(qū)間距離定義與人類實(shí)際認(rèn)知存在部分偏差。本文先對(duì)傳統(tǒng)鄰域圖進(jìn)行改進(jìn)，提出符合人類認(rèn)知的綜合鄰域圖，并在此基礎(chǔ)上將其擴(kuò)展為適用于任意方向間距離計(jì)算的質(zhì)心方向距離，從而可通過(guò)質(zhì)心方向關(guān)系矩陣獲取不同對(duì)象分布間更精細(xì)的基準(zhǔn)方向距離，聯(lián)合格網(wǎng)方向關(guān)系矩陣記錄的對(duì)象分布比例差異，指導(dǎo)EMD距離計(jì)算方向關(guān)系二元組間的最小轉(zhuǎn)換代價(jià)即方向關(guān)系二元組間的距離，實(shí)現(xiàn)對(duì)方向關(guān)系相似性的評(píng)估。

圖3 本文方法Fig.3 The proposed method

兩個(gè)場(chǎng)景的相似度可量化為一個(gè)場(chǎng)景轉(zhuǎn)變?yōu)榱硪粓?chǎng)景所需的變化數(shù)目[4]，變化越少相似度越高。方向關(guān)系二元組模型通過(guò)二元組間的距離量化兩個(gè)方向關(guān)系間的變化量，距離越小方向關(guān)系相似度越高。式(9)表示任意場(chǎng)景對(duì)(s,t)的方向關(guān)系相似度，兩場(chǎng)景對(duì)應(yīng)的方向關(guān)系二元組間的距離dist(Ddir(s),Ddir(t))越小，它們之間的相似度S(s,t)∈[0,1]越大，反之亦然。式中dmax表示不同方向片區(qū)間的最大距離，其取值與方向片區(qū)間的基準(zhǔn)方向距離定義相關(guān)

(9)

2.1 基于鄰域圖的基準(zhǔn)方向距離定義

經(jīng)典方向關(guān)系矩陣模型[21]為9個(gè)方向片區(qū)定義了2種基準(zhǔn)方向距離，分別以4鄰域圖和8鄰域圖為向?qū)?，如圖4(a)、(b)所示。圖中連線表示距離1，兩方向片區(qū)間的距離定義為兩者間最短路徑經(jīng)過(guò)的連線數(shù)目。兩類鄰域圖的差別在于斜對(duì)角線方向片區(qū)間是否有連線，這使得兩者相同方向片區(qū)間的距離略有不同，如(SW,NE)的距離在兩者中都取得最大值，但在4鄰域圖中為4，在8鄰域圖中為2，因此兩類鄰域圖的dmax的值分別為4和2。

4鄰域圖和8鄰域圖為方向關(guān)系矩陣的距離計(jì)算提供重要依據(jù)，但兩者仍存在與實(shí)際認(rèn)知不完全相符的問(wèn)題。人類的方向認(rèn)知中，相對(duì)原始方向偏移角度更小的方向具有更高的方向相似度，偏移角度增大時(shí)相似度逐漸降低，當(dāng)偏移角增至180°時(shí)達(dá)到人類認(rèn)知中完全相反的方向，相似度最低。因此當(dāng)目標(biāo)對(duì)象圍繞參考對(duì)象旋轉(zhuǎn)180°時(shí)方向關(guān)系最不相似方向距離最大。4鄰域圖中斜對(duì)角方向如d4(NW,SE)=d4(NE,SW)=4滿足最大值，但正方向上相差180°方向片區(qū)間距離d4(N,S)=d4(W,E)=2，僅與對(duì)象旋轉(zhuǎn)90°后的距離相等；8鄰域圖滿足任意方向與相反方向的距離為其最大值2，如d8(NW,SE)=d8(N,S)=2，但它對(duì)方向變化不敏感，僅能區(qū)分{0,1,2} 3個(gè)程度的方向距離變化，導(dǎo)致有明顯差異的方向關(guān)系未被區(qū)分，如d8(N,NE)=d8(N,E)=1，NE到E的變化被忽視。綜上可見(jiàn)兩種鄰域圖的定義并未完全與人類實(shí)際認(rèn)知一致。

本文結(jié)合空間認(rèn)知提出圖4(c)所示的綜合鄰域圖，實(shí)線和虛線均表示距離1，規(guī)定方向片區(qū)間的最短路徑最多經(jīng)過(guò)1條虛線，可得方向片區(qū)間的基準(zhǔn)距離如圖5所示。中心片區(qū)到其他方向片區(qū)的距離均為1，其他8個(gè)方向片區(qū)中任意兩者的距離隨它們與中心片區(qū)外心連線夾角的增大呈現(xiàn)先增大后減小的趨勢(shì)，夾角為180°時(shí)，距離達(dá)到最大距離值4，如dc(N,E)=dc(SW,NE)=4；綜合鄰域圖對(duì)方向片區(qū)間的距離更具區(qū)分性，可識(shí)別{0,1,2,3,4} 5種方向距離變化。相較4鄰域圖和8鄰域圖，綜合鄰域圖對(duì)方向片區(qū)間的距離定義更符合人們對(duì)空間方向的實(shí)際認(rèn)知。

圖4 4鄰域圖、8鄰域圖及本文提出的綜合鄰域圖Fig.4 Conceptual graphs of 4-neighborhood, 8-neighborhood and comprehensive-neighborhood

圖5 綜合鄰域圖中方向片區(qū)間的距離Fig.5 Comprehensive-neighborhood distances between cardinal directions

2.2 任意方向關(guān)系間的基準(zhǔn)方向距離定義

鄰域圖定義了9個(gè)方向片區(qū)間的基準(zhǔn)方向距離，但相同方向片區(qū)間的方向距離為0，因此仍無(wú)法區(qū)分同一方向片區(qū)內(nèi)的變化。此時(shí)，目標(biāo)對(duì)象質(zhì)心方位角間的差異可有效區(qū)分兩個(gè)目標(biāo)對(duì)象間的方向變化。記場(chǎng)景對(duì)(s,t)中目標(biāo)對(duì)象的質(zhì)心方位角為βs和βt，將兩者的質(zhì)心方位角距離θ定義為式(10)，其中θ∈[0,2π]

θ=|βs-βt|

(10)

在綜合鄰域圖定義的方向片區(qū)間距離的基礎(chǔ)上，引入基于θ的質(zhì)心方向距離fd(θ)，如式(11)所示。fd(θ)將θ映射至綜合鄰域圖的值域范圍[0,4]內(nèi)，從而將基準(zhǔn)方向距離由9個(gè)方向片區(qū)間擴(kuò)展到任意方向關(guān)系間，獲取粒度更細(xì)的基準(zhǔn)方向距離。圖6為fd(θ)相對(duì)θ的分布變化，可發(fā)現(xiàn)兩個(gè)目標(biāo)對(duì)象質(zhì)心方位角間距離θ由0增至180°再至360°時(shí)，對(duì)應(yīng)質(zhì)心方向距離先單調(diào)遞增再單調(diào)遞減，并在180°時(shí)取得最大值，與人類認(rèn)知相符。質(zhì)心方向距離fd(θ)是定義在[0,2π]內(nèi)的連續(xù)函數(shù)，可反映任意方向間的距離，綜合鄰域圖定義的基準(zhǔn)方向距離為該基準(zhǔn)方向距離的子集，兩者最大方向距離值dmax均為4

圖6 質(zhì)心方向距離映射函數(shù)Fig.6 Mapping function for centroid direction distance

(11)

2.3 方向關(guān)系二元組間的EMD距離計(jì)算

方向關(guān)系二元組間的距離計(jì)算是以二元組中的格網(wǎng)方向關(guān)系矩陣為實(shí)施主體，因此其計(jì)算方法與格網(wǎng)方向關(guān)系矩陣的距離計(jì)算類似。根據(jù)矩陣中非零元素?cái)?shù)目的情況，格網(wǎng)方向關(guān)系矩陣的距離計(jì)算可分為如下3種[24]。

(1) 單元素格網(wǎng)方向關(guān)系矩陣間的距離。查詢鄰域圖獲取。

(2) 單元素與多元素格網(wǎng)方向關(guān)系矩陣的距離。將多元素方向關(guān)系矩陣拆分為多個(gè)單元素子矩陣后，依次計(jì)算它們與單元素方向關(guān)系矩陣的距離，再以各自的單元素值為權(quán)重加權(quán)求和獲得最終距離。

(3) 多元素方向關(guān)系矩陣間的距離。因不能明確元素在矩陣中轉(zhuǎn)移的情況，常借鑒運(yùn)輸問(wèn)題解決方法如西北角法[27]計(jì)算兩個(gè)矩陣間的最小耗費(fèi)作為距離。

同理，通過(guò)方向關(guān)系二元組中的格網(wǎng)方向關(guān)系矩陣計(jì)算方向關(guān)系二元組間的距離，但此時(shí)各元素間的距離不再通過(guò)鄰域圖定義的基準(zhǔn)距離表示，而是采用質(zhì)心方向距離fd(θ)表示，通過(guò)各元素在二元組中質(zhì)心方向關(guān)系矩陣的對(duì)應(yīng)位置元素值即可求取fd(θ)，從而完成更準(zhǔn)確的方向關(guān)系二元組距離計(jì)算。

特別地，在多元素方向關(guān)系矩陣間的距離計(jì)算中，西北角法由于簡(jiǎn)單易實(shí)施而被廣泛采用，但運(yùn)籌學(xué)中認(rèn)為它并未注意到運(yùn)輸成本的影響，計(jì)算結(jié)果往往并非最優(yōu)值[28]，這影響了方向關(guān)系相似性度量的準(zhǔn)確性。文獻(xiàn)[26]提出EMD距離表示不同分布間相互轉(zhuǎn)換的最小代價(jià)，并被廣泛應(yīng)用于視覺(jué)領(lǐng)域和自然語(yǔ)言領(lǐng)域中的特征相似性度量，本文將EMD距離引入方向關(guān)系二元組間最小轉(zhuǎn)換代價(jià)的計(jì)算中。

EMD距離源自運(yùn)輸模型。設(shè)有m個(gè)供應(yīng)者P={(p1,wp1),…,(pm,wpm)}和n個(gè)需求者Q={(q1,wq1),…,(qn,wqn)}，其中pi,wpi(1≤i≤m)為第i個(gè)供應(yīng)者及其供應(yīng)量，qj、wqj(1≤j≤n)為第j個(gè)需求者及其需求量。各供應(yīng)者到各需求者的運(yùn)輸距離及運(yùn)輸量分別通過(guò)m×n的運(yùn)輸距離矩陣C=[cij](1≤i≤m,1≤j≤n)和運(yùn)輸方案矩陣E=[eij](1≤i≤m,1≤j≤n)表示，可得總運(yùn)輸代價(jià)cost(P,Q)為{(q1,wq1),…,(qn,wqn)}

(12)

式中，運(yùn)輸方案矩陣的元素eij(1≤i≤m,1≤j≤n)為第i個(gè)供應(yīng)者運(yùn)往第j個(gè)需求者的貨物量，且滿足如下約束

eij≥0 1≤i≤m,1≤j≤n

(13)

(14)

(15)

(16)

EMD(Ddir(s),Ddir(t))=min(cost(Ddir(s),Ddir(t)))=

(17)

結(jié)合式(17)和式(9)，可得任意兩個(gè)方向關(guān)系二元組間的相似度

(18)

式中，dmax為質(zhì)心方向距離的最大值4。EMD的計(jì)算最終轉(zhuǎn)化為對(duì)運(yùn)輸問(wèn)題的求解，可通過(guò)運(yùn)輸單純形法高效計(jì)算，這是一種流線型單純形法，可充分利用約束矩陣的稀疏結(jié)構(gòu)降低運(yùn)算量。實(shí)施過(guò)程主要包括：①初始化獲取可行解；②最優(yōu)性檢驗(yàn)；③迭代獲取新的基可行解，具體過(guò)程可參考文獻(xiàn)[28]，其時(shí)間復(fù)雜度為O(n2)?，F(xiàn)階段EMD算法在視覺(jué)領(lǐng)域發(fā)展較為完善，通常利用Russell近似法[29]計(jì)算初始基可行解，它相較西北角法更易獲取最優(yōu)解且更易于在計(jì)算機(jī)上快速完成計(jì)算[28]。本文采用經(jīng)典的C語(yǔ)言EMD算法庫(kù)[30]完成方向關(guān)系二元組距離的計(jì)算。

3 試驗(yàn)與討論

以下分析方向關(guān)系二元組的表達(dá)能力、綜合鄰域圖和質(zhì)心方向距離的完備性以及EMD距離的可行性進(jìn)行分析，并探索本文模型在基于方向關(guān)系的制圖綜合結(jié)果評(píng)估、場(chǎng)景檢索等任務(wù)中的表現(xiàn)。

3.1 方向關(guān)系二元組模型基本可行性分析

3.1.1 方向關(guān)系二元組的表達(dá)能力分析

圖7為目標(biāo)對(duì)象B以NW片區(qū)為起點(diǎn)圍繞參考對(duì)象A平移，得到的12幅表現(xiàn)不同方向關(guān)系的場(chǎng)景。

圖7中場(chǎng)景1和場(chǎng)景2的目標(biāo)對(duì)象落在同一片區(qū)內(nèi)，兩者的方向關(guān)系二元組如式(19)和式(20)所示?？砂l(fā)現(xiàn)兩者的格網(wǎng)方向關(guān)系矩陣完全相同，而質(zhì)心方向關(guān)系矩陣同一位置的元素值分別為5.238和5.730，可明顯區(qū)分兩場(chǎng)景的差異，快速得到二元組間距離dist(Ddir(scene 1),Ddir(scene 2))=fd(5.730-5.238)=0.626，對(duì)比格網(wǎng)方向關(guān)系矩陣間的距離0，更符合人類實(shí)際認(rèn)知。

圖7 B圍繞A平移獲取的場(chǎng)景Fig.7 The scenes generated by moving object B clockwise with respect to object A

(19)

(20)

圖8對(duì)比了場(chǎng)景1與其他場(chǎng)景在方向關(guān)系二元組模型和格網(wǎng)方向關(guān)系矩陣模型中的方向關(guān)系相似度，兩種模型中均采用綜合鄰域圖定義的基準(zhǔn)距離。可發(fā)現(xiàn)兩種相似度結(jié)果都呈先降低后上升的形態(tài)，整體趨勢(shì)符合人類對(duì)方向關(guān)系的認(rèn)知，但具體到各場(chǎng)景可發(fā)現(xiàn)兩者區(qū)分度的差異。如場(chǎng)景1與場(chǎng)景2在格網(wǎng)方向關(guān)系矩陣模型中方向關(guān)系相似度Sgrid(scene 1,scene 2)=1，但在方向關(guān)系二元組模型中Stuple(scene 1,scene 2)=1-0.626/4=0.844，表明兩者的方向關(guān)系具有較高的相似度，但并非完全相同。逐個(gè)觀察圖8中的結(jié)果，可發(fā)現(xiàn)格網(wǎng)方向關(guān)系矩陣僅能體現(xiàn)方向片區(qū)間的差異，忽視了具體方向偏移角度間的差異，相比之下方向關(guān)系二元組對(duì)任意方向關(guān)系變化都有較好的識(shí)別和區(qū)分能力。

圖8 兩種模型下各場(chǎng)景與場(chǎng)景1的方向關(guān)系相似性度量結(jié)果對(duì)比Fig.8 Comparison of the cardinal similarity between scene1 and other scenes obtained by two different models

3.1.2 綜合鄰域圖區(qū)分能力分析

為驗(yàn)證綜合鄰域圖對(duì)基準(zhǔn)方向距離定義更完備且符合認(rèn)知，通過(guò)格網(wǎng)方向關(guān)系矩陣對(duì)比圖7中12個(gè)場(chǎng)景間在采用4鄰域圖、8鄰域圖、綜合鄰域圖這3種基準(zhǔn)方向距離定義時(shí)的方向距離。

如圖9所示，各分圖中距離值均在本場(chǎng)景附近取得較小值，沿著坐標(biāo)軸往兩側(cè)發(fā)散時(shí)，最初均呈遞增趨勢(shì)，整體上均滿足偏移角度越大距離越大，偏移角度越小距離越小的基本規(guī)律。對(duì)比圖中各類鄰域圖結(jié)果對(duì)應(yīng)柱體的值域，可發(fā)現(xiàn)表示8鄰域圖結(jié)果的柱體分布范圍及變化幅度最小，值域僅在[0,2]且走勢(shì)大多較為平穩(wěn)，如圖9(i)中場(chǎng)景9與場(chǎng)景1—7這7個(gè)場(chǎng)景間的距離均為2，這是不符合實(shí)際認(rèn)知的。4鄰域圖和綜合鄰域圖對(duì)方向變化的識(shí)別粒度有很大提升，圖中兩者值域均為[0,4]且走勢(shì)接近，差異主要體現(xiàn)在相反方向間的距離。如圖9(d)中場(chǎng)景4與場(chǎng)景8在4鄰域圖中的距離2，小于場(chǎng)景4與場(chǎng)景7間的距離3，即相較場(chǎng)景7，場(chǎng)景8與場(chǎng)景4更相似，這與空間認(rèn)知中相反方向最不相似的認(rèn)知相悖，而圖中綜合鄰域圖柱體的分布表明它對(duì)方向片區(qū)間的距離是隨著偏移角度變化規(guī)律增大或減小的，對(duì)不同方向角度變化的距離判斷均與人類空間認(rèn)知一致。相較4鄰域圖和8鄰域圖，綜合鄰域圖具有更完備更符合認(rèn)知的距離定義。

圖9 4鄰域、8鄰域和綜合鄰域圖下的格網(wǎng)方向關(guān)系矩陣距離分布Fig.9 Distances calculated by grid-based relation matrices with 4-neighborhood, 8-neighborhood and comprehensive-neighborhood

3.1.3 EMD距離最優(yōu)性分析

傳統(tǒng)方向關(guān)系矩陣模型[21，24]常采用西北角法[27]計(jì)算兩個(gè)矩陣間的最小耗費(fèi)，西北角法的每次迭代優(yōu)先計(jì)算平衡傳輸表的西北角即左上角元素，因此其計(jì)算結(jié)果會(huì)因表中行列位置不同而變化，往往并非最優(yōu)值[28]。以圖10為例，圖中兩個(gè)場(chǎng)景的方向關(guān)系二元組均由多元素方向關(guān)系矩陣組成。依次通過(guò)西北角法和EMD距離計(jì)算兩個(gè)場(chǎng)景在不同基準(zhǔn)方向距離下的格網(wǎng)方向關(guān)系矩陣距離和方向關(guān)系二元組距離，結(jié)果見(jiàn)表1?？砂l(fā)現(xiàn)不論采用何種方向表達(dá)模型及基準(zhǔn)方向距離定義，兩者間的EMD距離均小于或等于西北角法的計(jì)算結(jié)果。僅采用基于8鄰域圖的格網(wǎng)方向關(guān)系矩陣時(shí)兩種距離計(jì)算方法的結(jié)果相同，這也與8鄰域圖定義的基準(zhǔn)距離范圍小，不同方向片區(qū)間距離值變化不大有關(guān)。除此外，EMD距離值均更小，結(jié)果更優(yōu)。

圖10 目標(biāo)對(duì)象分布在多個(gè)方向片區(qū)的場(chǎng)景Fig.10 Scenes with target objects distributed in several cardinal directions

表1 西北角法計(jì)算距離和EMD距離對(duì)比

3.2 方向關(guān)系二元組模型的應(yīng)用能力分析

3.2.1 基于方向關(guān)系的制圖綜合結(jié)果評(píng)估

方向關(guān)系相似性是多尺度地圖空間相似關(guān)系的重要部分[2]，可作為制圖綜合結(jié)果的評(píng)價(jià)指標(biāo)之一[24]。方向關(guān)系二元組可表達(dá)多尺度對(duì)象間的方向關(guān)系，并可通過(guò)分解思想[25]應(yīng)用于復(fù)合對(duì)象。因此可通過(guò)方向關(guān)系二元組對(duì)制圖綜合前后多尺度對(duì)象間及復(fù)合對(duì)象間方向關(guān)系的理性進(jìn)行評(píng)估。如圖11中4個(gè)分圖分別展示了4個(gè)大比例場(chǎng)景的2種制圖綜合結(jié)果，通過(guò)本文模型和格網(wǎng)方向關(guān)系矩陣模型[24]計(jì)算制圖綜合前后場(chǎng)景的方向關(guān)系相似度，結(jié)果如表2所示。對(duì)比可發(fā)現(xiàn)格網(wǎng)方向關(guān)系矩陣僅能判斷圖11(a)中這類目標(biāo)對(duì)象明顯分布在不同方向片區(qū)綜合結(jié)果的優(yōu)劣，對(duì)圖11(b)、(c)的綜合結(jié)果無(wú)法做出準(zhǔn)確評(píng)估，而方向關(guān)系二元組可判斷出4個(gè)分圖中均為場(chǎng)景2的制圖綜合結(jié)果更合理。特別地，圖11(d)復(fù)合對(duì)象制圖綜合案例及相應(yīng)結(jié)果來(lái)自文獻(xiàn)[25]，方向關(guān)系二元組模型的判斷結(jié)果與其一致，即場(chǎng)景2更合理。

表2 兩種方法下的綜合制圖結(jié)果評(píng)估

3.2.2 基于方向關(guān)系的空間場(chǎng)景查詢

在空間場(chǎng)景的查詢與檢索任務(wù)中，方向關(guān)系相似度亦常作為場(chǎng)景相似度的計(jì)算因子，一定程度地影響整體場(chǎng)景的相似度評(píng)估，可通過(guò)方向關(guān)系相似度篩選具有類似方向分布的場(chǎng)景。圖12(a)是高德地圖采集的上海某區(qū)域建筑物地圖及3個(gè)檢索場(chǎng)景。在沒(méi)有對(duì)象幾何特征及其他空間關(guān)系約束的前提下，為簡(jiǎn)化對(duì)象匹配計(jì)算，限定候選場(chǎng)景中對(duì)象滿足Voronoi相鄰且對(duì)象數(shù)目與檢索場(chǎng)景中相同。通過(guò)方向關(guān)系二元組模型查詢出各檢索場(chǎng)景最相似的5個(gè)場(chǎng)景如圖12(b)所示。觀察可發(fā)現(xiàn)，每一個(gè)檢索場(chǎng)景都被檢出且為各自結(jié)果中相似度最高的，其他結(jié)果場(chǎng)景中對(duì)象的分布及對(duì)象間的方向關(guān)系也與檢索場(chǎng)景的高度相似，表明方向關(guān)系二元組模型可有效實(shí)現(xiàn)空間場(chǎng)景對(duì)象間的方向關(guān)系相似度評(píng)估，實(shí)現(xiàn)符合人類認(rèn)知的方向關(guān)系檢索。

圖12 基于方向關(guān)系的空間場(chǎng)景檢索Fig.12 Spatial scene retrieval based on direction relation

4 總 結(jié)

本文提出一種基于方向關(guān)系二元組的方向關(guān)系相似性度量方法，從方向關(guān)系特征表達(dá)、基準(zhǔn)方向距離定義、矩陣距離計(jì)算3個(gè)方面對(duì)方向關(guān)系矩陣模型進(jìn)行改進(jìn)與優(yōu)化，實(shí)現(xiàn)更高效準(zhǔn)確的方向關(guān)系表達(dá)及相似性度量。該方法首先通過(guò)方向關(guān)系二元組實(shí)現(xiàn)細(xì)粒度的方向關(guān)系表達(dá)；然后結(jié)合人類認(rèn)知優(yōu)化傳統(tǒng)鄰域圖，并在此基礎(chǔ)上建立方向距離定義更完備的質(zhì)心方向距離；最后利用EMD距離，完成對(duì)具有任意復(fù)雜度的方向關(guān)系二元組間距離的優(yōu)化計(jì)算。本文方法可有效識(shí)別同一方向片區(qū)內(nèi)的方向變化，更準(zhǔn)確地實(shí)現(xiàn)任意方向間的相似性的度量，獲取更符合人類認(rèn)知的度量結(jié)果。在制圖綜合結(jié)果評(píng)估、場(chǎng)景檢索等任務(wù)中亦有較好的表現(xiàn)，可快速應(yīng)用于多尺度對(duì)象及復(fù)合對(duì)象間的方向關(guān)系表達(dá)與相似度計(jì)算上，具有廣泛的適用性。本文模型建立在格網(wǎng)方向關(guān)系矩陣的基礎(chǔ)上，同樣可通過(guò)傳統(tǒng)方向關(guān)系矩陣實(shí)現(xiàn)本文方法以應(yīng)用到不同任務(wù)中。下一步工作將會(huì)進(jìn)一步探討不同格網(wǎng)密度下或基于不同類型方向關(guān)系模型的方向關(guān)系二元組的表達(dá)能力與適用場(chǎng)景。