田澤宇,門朝光,湯亞楠

(哈爾濱工程大學(xué)計算機科學(xué)與技術(shù)學(xué)院,黑龍江哈爾濱 150001)

?

基于形狀及空間關(guān)系的場景相似性檢索

田澤宇,門朝光,湯亞楠

(哈爾濱工程大學(xué)計算機科學(xué)與技術(shù)學(xué)院,黑龍江哈爾濱 150001)

為解決空間數(shù)據(jù)檢索效率低、準確性差的問題,本文提出由空間對象形狀描述模型、空間關(guān)系描述模型、場景相似性自適應(yīng)計算模型構(gòu)成的場景相似性檢索方法.空間對象形狀描述模型精準檢索滿足樣例對象形狀約束的數(shù)據(jù)庫對象,提高空間對象形狀的識別精度.空間關(guān)系描述模型檢索滿足樣例場景關(guān)系約束的數(shù)據(jù)庫場景,提高空間關(guān)系的描述精度.場景相似性自適應(yīng)計算模型對滿足形狀及關(guān)系約束的完全匹配、局部匹配場景進行打分、排序,增加檢索結(jié)果相似性打分的合理性.模擬場景、真實場景的實驗表明本場景相似性檢索方法具有良好的檢索性能.

空間數(shù)據(jù)檢索;形狀描述;空間關(guān)系描述;場景相似性

電子學(xué)報URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.08.018

1 引言

隨著空間數(shù)據(jù)獲取技術(shù)的迅速發(fā)展,空間數(shù)據(jù)規(guī)模呈爆炸增長趨勢,在海量空間數(shù)據(jù)中快速檢索出需要的信息是目前空間數(shù)據(jù)管理的瓶頸.傳統(tǒng)的空間數(shù)據(jù)檢索方法主要有基于位置和關(guān)鍵字的檢索、Spatial SQL查詢語言和可視化空間數(shù)據(jù)檢索,這些方法很難表達復(fù)雜的拓撲、方向關(guān)系,而且語法復(fù)雜、描述模糊,極易出錯.為了解決這些問題,使用基于草圖、基于樣例等更直觀、更符合人類認知的檢索方式,進行更精準的場景相似性檢索.Egenhofer首次提出了基于草圖的空間數(shù)據(jù)檢索,并設(shè)計了拓撲關(guān)系、方向關(guān)系和拓撲關(guān)系的概念鄰域圖等模型[1,2].以拓撲關(guān)系為基礎(chǔ),文獻[3]研究了拓撲關(guān)系相似性度量方法,并使用獨立成分分析和模糊支持向量機進行空間數(shù)據(jù)檢索.以方向關(guān)系為基礎(chǔ),文獻[4]研究了確定區(qū)域間方向關(guān)系的度量方法,文獻[5]給出了不確定區(qū)域間方向關(guān)系的相似性度量方法.以拓撲和方向關(guān)系為基礎(chǔ),文獻[6]給出了草圖的一階鄰近關(guān)系和相應(yīng)的前項檢查檢索方案,文獻[7]通過草圖空間關(guān)系的定性表達和校準,將草圖信息整合到GIS系統(tǒng)中.以上相似性度量方法均沒有考慮空間對象形狀對相似性檢索的影響,而且在檢索結(jié)果的相似性打分、排序上沒有給出詳盡的方案.文獻[8,9]設(shè)計了組件相似性、匹配完整性等場景相似性打分機制,但沒有設(shè)定自適應(yīng)的相似性權(quán)重參數(shù),也沒有考慮對象的形狀.

為了提高場景相似性檢索的精度,使用了空間對象形狀相似性度量方法.現(xiàn)有空間對象形狀相似性研究主要有多級弦長描述法[10]、彎曲度半徑描述法[11]、正切空間描述法[12]等.但這些方法描述能力不強,不能兼顧形狀的邊界和區(qū)域信息.

針對現(xiàn)有場景相似性檢索的缺陷,本文提出基于形狀及空間關(guān)系的場景相似性檢索方法.本檢索方法通過空間對象形狀描述模型精準檢索滿足樣例對象形狀相似性約束的數(shù)據(jù)庫對象,通過空間關(guān)系描述模型定性、定量地檢索滿足樣例場景關(guān)系約束的數(shù)據(jù)庫場景,通過場景相似性自適應(yīng)計算模型對檢索到的數(shù)據(jù)庫場景進行打分、排序,得到與樣例場景相似的所有完全匹配、局部匹配場景,提高空間對象形狀及關(guān)系的檢索識別精度,增加場景檢索結(jié)果相似性打分的合理性.

2 空間對象形狀描述模型

本文提出的空間對象形狀描述模型通過計算空間對象形狀的主方向,利用與主方向平行的若干條直線分割空間對象,計算同一分割線上對象分割段之間的順序特征描述量f,記錄所有分割線上的順序特征描述量{f1,f2……fn},形成空間對象的形狀特征描述量F={f1,f2……fn}.

空間對象的形狀主方向由空間對象的形狀特征決定,是空間對象形狀的最小慣性軸.主方向位于通過重心且傾角為θ的直線上,傾角θ公式為[13]:

(1)

其中,u11,u02,u20為空間對象區(qū)域的p+q階中心矩.空間對象形狀主方向如圖1中帶箭頭的直線所示.

求出與主方向平行且與空間對象最外側(cè)相交的兩條邊界線,如圖1中的兩條實線所示.利用與主方向平行的n條直線將兩條邊界線之間的部分平均分割為n+1等份,如圖1中的9條虛線將實線之間的部分平均分割為10等份.

某一條分割線與空間對象相交于m段(m≥1),如圖1中分割線L1與空間對象相交于ab、cd兩段,分割線L2與空間對象相交于mn一段,分割線L3與對象相交于三段.同一條分割線上的對象分割段均為直線,不存在形狀差異,但對象分割段之間有前后順序.假定分割線為一維坐標軸,可任意規(guī)定該一維坐標軸的正方向,但所有分割線的正方向必須相同,如圖1中規(guī)定主方向的箭頭方向為正方向.圖1中分割線L1的對象分割段cd領(lǐng)先于分割段ab,即段cd中任一點u均領(lǐng)先于段ab中任一點v,設(shè)函數(shù)φ(u-v)描述點u、v的順序關(guān)系,公式為:

(2)

則段ab與段cd之間所有點的順序關(guān)系描述即順序特征描述量f可表示為:

(3)

其中,x、z分別為線段cd、ab的長度.y為點c與點b坐標值之差.當點c領(lǐng)先于點b時,y>0;當點c與點b重合時,y=0;當點b領(lǐng)先于點c時,y<0.

更一般的,假設(shè)一條分割線上的對象分割段為I1、I2,則公式(3)可表示為:

(4)

其中,x為段I2的長度,z為段I1的長度.y為段I2的起點坐標與段I1的終點坐標之差.u為段I2上的點,v為段I1上的點.

當一條分割線上的對象分割段多于兩段時,如圖1中分割線L3與空間對象相交于三段.假設(shè)該條分割線上的對象分割段為I1、I2……In,n為大于2的整數(shù),則該條分割線上的順序特征描述量f為:

(5)

當一條分割線上只有1個對象分割段時,如圖1中分割線L2上的段mn.此時可以看做兩個長度為x的段mn、m′n′完全重合,根據(jù)公式(4)可得:

(6)

即分割線上只有一個對象分割段I時,公式(6)為:

(7)

其中,x為分割段I的長度,u和v為段I上的點.

(8)

(9)

則兩個對象vi、uj的形狀相似度為:

Svertex=1-dvertex

(10)

本文的空間對象形狀描述模型可以精確描述空間對象形狀的整體特征和細節(jié)信息,兼顧了邊界和區(qū)域信息,具有平移、旋轉(zhuǎn)、翻轉(zhuǎn)、尺度不變性,對形狀的輕微形變具有魯棒性,并且可以通過調(diào)節(jié)分割線數(shù)量對空間對象形狀進行多級描述.

3 空間關(guān)系描述模型

本文利用維度擴展9交模型(DE-9IM)[14],提取樣例場景和數(shù)據(jù)庫場景中面空間對象間的拓撲關(guān)系,在數(shù)據(jù)庫場景中檢索與樣例場景拓撲關(guān)系一致的場景.當樣例場景中兩個對象間的拓撲關(guān)系為相離或相交時,需要引入定量度量機制對相離、相交關(guān)系進行細化.

當場景中兩個對象A、B的拓撲關(guān)系為相離時,通過空間對象形狀相似性的計算可知空間對象的重心位置和主方向上所有對象分割段的長度之和.設(shè)相離空間對象A、B各自主方向上所有分割段的長度之和分別為Da、Db,兩個相離空間對象的重心距離為Dc,相對于空間對象A的相離關(guān)系定量度量為DIS1,相對于空間對象B的相離關(guān)系定量度量為DIS2.DIS1、DIS2可表示為:

(11)

在進行場景相似性匹配時,設(shè)樣例場景空間對象vi、vk之間相離關(guān)系的定量度量為DIS1(v)、DIS2(v),數(shù)據(jù)庫場景空間對象uj、ul之間相離關(guān)系的定量度量為DIS1(u)、DIS2(u),樣例場景相離關(guān)系和對應(yīng)數(shù)據(jù)庫場景相離關(guān)系的差異度為:

(12)

則樣例場景和對應(yīng)數(shù)據(jù)庫場景的相離關(guān)系相似度Sedge可表示為:

(13)

當場景中兩個對象A、B的拓撲關(guān)系為相交時,設(shè)對象A、B的面積分別為area(A)、area(B),相交部分A∩B的面積為area(A∩B),相對于空間對象A的相交關(guān)系定量度量為LAP1,相對于空間對象B的相交關(guān)系定量度量為LAP2.LAP1,LAP2公式為:

(14)

在進行場景相似性匹配時,設(shè)樣例場景空間對象vi、vk之間相交關(guān)系的定量度量為LAP1(v)、LAP2(v),數(shù)據(jù)庫場景空間對象uj、ul之間相交關(guān)系的定量度量為LAP1(u)、LAP2(u),樣例場景相交關(guān)系和對應(yīng)數(shù)據(jù)庫場景相交關(guān)系的差異度為:

(15)

則樣例場景和對應(yīng)數(shù)據(jù)庫場景的相交關(guān)系相似度Sedge可表示為:

(16)

DE-9IM不能描述對象間的方向關(guān)系,本文基于方向關(guān)系矩陣模型[4],計算目標對象在參考對象9個方向片內(nèi)的部分占自身的比例,忽略對方向關(guān)系影響不大的部分.

4 空間場景相似性檢索

在空間對象形狀描述模型與空間關(guān)系描述模型的基礎(chǔ)上,提取樣例場景中每個對象的形狀描述量、對象間的拓撲關(guān)系和方向關(guān)系,利用每個樣例對象的形狀描述量檢索數(shù)據(jù)庫場景中形狀相似的對象,判斷檢索到的數(shù)據(jù)庫對象是否滿足樣例對象間的拓撲關(guān)系和方向關(guān)系.根據(jù)形狀相似度、拓撲中相離關(guān)系和相交關(guān)系的相似度以及檢索到場景的完整性,對獲得的數(shù)據(jù)庫場景進行相似性打分和排序.設(shè)樣例場景為S、數(shù)據(jù)庫場景為D,樣例場景S包含n個空間對象{v1,v2,……vn},數(shù)據(jù)庫場景D包含m個空間對象{u1,u2,……um}.樣例場景S如圖2(a)所示,數(shù)據(jù)庫場景D如圖2(b)所示.

4.1 建立關(guān)聯(lián)圖

計算樣例場景S中空間對象vi的形狀描述量與數(shù)據(jù)庫場景D中空間對象uj的形狀描述量的相似度,當兩個對象的形狀相似度在閾值范圍內(nèi)時,生成關(guān)聯(lián)圖Ga的頂點aij,記錄空間對象vi和空間對象uj的形狀匹配相似度.

計算關(guān)聯(lián)圖Ga中任意兩個頂點aij、akl之間是否有邊相連,需要判斷數(shù)據(jù)庫場景空間對象uj、ul之間的拓撲關(guān)系和方向關(guān)系是否滿足樣例場景空間對象vi、vk之間的拓撲關(guān)系和方向關(guān)系.若滿足,則關(guān)聯(lián)圖中兩個頂點aij、akl之間建立邊相連接,并記錄空間關(guān)系的相似度為1.0;否則,不建立邊.當拓撲關(guān)系為相離關(guān)系或相交關(guān)系時,需要計算樣例場景和對應(yīng)數(shù)據(jù)庫場景的相離關(guān)系相似度或相交關(guān)系相似度.判斷相離關(guān)系相似度、相交關(guān)系相似度是否在閾值范圍內(nèi),若在范圍內(nèi),則建立邊并記錄相離、相交關(guān)系相似度.圖2的樣例場景和數(shù)據(jù)庫場景的關(guān)聯(lián)圖如圖3所示.

4.2 提取關(guān)聯(lián)圖的極大團

提取關(guān)聯(lián)圖Ga中的所有極大團,檢索出與樣例場景完全匹配、局部匹配的所有數(shù)據(jù)庫場景.其中,最大團對應(yīng)場景的完全匹配,極大團對應(yīng)場景的局部匹配.本文以極大團提取算法ELS[15]為基礎(chǔ),根據(jù)空間場景相似性檢索的特點,對關(guān)聯(lián)圖Ga進行優(yōu)化,降低關(guān)聯(lián)圖的復(fù)雜度,提高極大團提取的效率,提高場景相似性檢索的效率.

在空間場景相似性檢索中,數(shù)據(jù)庫場景D的對象數(shù)目通常遠大于樣例場景S的對象數(shù)目,有可能導(dǎo)致樣例場景S中的空間對象有很多形狀相似的數(shù)據(jù)庫對象,但這些形狀相似的數(shù)據(jù)庫對象都很難完全滿足樣例場景S中空間關(guān)系的約束,最終會導(dǎo)致關(guān)聯(lián)圖中出現(xiàn)大量的孤立點或度為1的頂點,這些頂點可以在執(zhí)行算法ELS前去除,降低關(guān)聯(lián)圖的復(fù)雜度,提高極大團的提取效率.

在建立關(guān)聯(lián)圖Ga={V,E}過程中,將每個頂點v的度和鄰接點集合Γ(v)記錄在該頂點v中,并記錄所有孤立點和度為1的頂點.關(guān)聯(lián)圖Ga極大團提取算法的實現(xiàn)步驟如下:

(1)將孤立點從關(guān)聯(lián)圖中去除,并將去除的孤立點作為極大團,記為樣例場景的匹配,利用公式(17)至(21)計算其場景相似性.

(2)將度為1的頂點從關(guān)聯(lián)圖中去除,其鄰接頂點Γ(v)的度均減1,并將該頂點和其鄰接頂點作為極大團,記為樣例場景的匹配,利用公式(17)至(21)計算其場景相似性.去除該頂點之后,繼續(xù)判斷該頂點的鄰接頂點的度.如果度為0,則直接去除;如果度為1,則重復(fù)步驟2;如果大于1,則停止.

(3)利用算法ELS提取經(jīng)步驟1、2優(yōu)化后的關(guān)聯(lián)圖Ga1的極大團,將提取出的極大團記為樣例場景的匹配,利用公式(17)至(21)計算其場景相似性.

設(shè)關(guān)聯(lián)圖Ga有w個頂點,經(jīng)步驟1、2優(yōu)化后的關(guān)聯(lián)圖Ga1為有N個頂點的d-退化圖.關(guān)聯(lián)圖Ga極大團提取算法步驟1、2的線性時間復(fù)雜度為O(w-N),步驟3的時間復(fù)雜度為O(d*N*3d/3)[15].因關(guān)聯(lián)圖Ga中存在大量的孤立點和度為1的頂點,優(yōu)化關(guān)聯(lián)圖Ga,可以進一步減少ELS算法的執(zhí)行時間,提高場景相似性檢索的效率.

圖3中的關(guān)聯(lián)圖先通過步驟1將孤立點{C,6}去除,將該點記為樣例場景的局部匹配,計算該點的相似性.通過步驟2將度為1的頂點{A,7}{B,8}去除,將頂點{A,7}{B,8}記為樣例場景的局部匹配,計算該局部匹配的相似性.通過步驟3檢索出優(yōu)化關(guān)聯(lián)圖的最大團{A,1}{B,2}{C,3}和最大團{A,4}{B,2}{C,3},將兩個最大團分別記為樣例場景的完全匹配,計算完全匹配的相似性.

4.3 空間場景相似性自適應(yīng)計算模型

利用對象組件相似性、關(guān)系組件相似性、場景匹配完整性等機制,設(shè)計新的場景相似性自適應(yīng)權(quán)重參數(shù),提出空間場景相似性計算模型,對得到的匹配場景進行打分、排序.

4.3.1 組件相似性

在極大團中,根據(jù)每個頂點記錄的樣例場景和數(shù)據(jù)庫場景中匹配對象的形狀相似性Svertex,計算整個匹配場景的空間對象組件相似性SObj,公式為:

(17)

其中,M表示極大團的頂點個數(shù)即匹配場景的對象個數(shù);Svertexi表示極大團中第i個頂點記錄的形狀相似性;mi表示極大團的第i個匹配對象對中構(gòu)成樣例空間對象的點數(shù),m表示樣例場景中所有已匹配空間對象的點數(shù).wOi表示極大團中第i個頂點的權(quán)重,為第i個已匹配樣例對象的點數(shù)占樣例場景中所有已匹配對象的點數(shù)的比.樣例場景中構(gòu)成對象的頂點數(shù)越多代表該對象形狀越復(fù)雜,越容易在數(shù)據(jù)庫場景中找到匹配的對象,其在場景中的權(quán)重wOi也越大.

在極大團中,根據(jù)每條邊記錄的樣例場景和數(shù)據(jù)庫場景中對應(yīng)空間關(guān)系的相似性Sedge,計算整個匹配場景的空間關(guān)系組件相似性SRel,公式如下:

(18)

其中,M表示極大團的頂點個數(shù);Sedgei表示極大團中第i條邊記錄的空間關(guān)系相似性;wRi表示極大團中第i個關(guān)系的權(quán)重.本文所有關(guān)聯(lián)關(guān)系的權(quán)重均相同,取值為1.

4.3.2 場景完整性

依據(jù)人類對空間場景的主觀認知,完全匹配場景的相似性分值比局部匹配場景的相似性分值高,因此局部匹配中未匹配的樣例空間對象對該局部匹配的相似性分值有負面影響.本文用空間場景完整性Scomp反映場景匹配的程度,公式如下:

(19)

4.3.3 空間場景相似性計算

空間場景相似性的計算利用了對象組件相似性SObj、關(guān)系組件相似性SRel和空間場景完整性Scomp的計算結(jié)果,其計算公式為:

(20)

其中,wObj表示對象組件相似性所占的權(quán)重,wRel表示關(guān)系組件相似性所占的權(quán)重.

本文通過形狀描述模型檢索空間對象,當空間對象形狀復(fù)雜時,形狀的辨識度要高于空間關(guān)系的辨識度.空間對象最簡單的形狀為三角形,當空間對象的形狀全為三角形時,權(quán)重wObj=wRel;當空間對象的形狀不全為三角形時,權(quán)重wObj>wRel.通常情況下對象組件相似性的權(quán)重wObj高于關(guān)系組件相似性的權(quán)重wRel,權(quán)重公式如下:

(21)

其中,n表示樣例場景中已匹配對象的數(shù)目,m表示樣例場景中已匹配對象的頂點數(shù)目.

5 實驗及結(jié)果分析

本實驗分為兩個部分,先使用通過真實建筑構(gòu)建的形狀數(shù)據(jù)集和北京大學(xué)矢量地圖驗證空間對象形狀描述模型的有效性,再利用文獻1中的模擬場景數(shù)據(jù)庫和清華大學(xué)矢量地圖驗證整體檢索方案的有效性.

5.1 空間對象形狀描述模型實驗

使用從OpenStreetMap中獲取的北京大學(xué)約1400個建筑的地圖作為實驗數(shù)據(jù),如圖4所示.本實驗僅使用空間對象形狀描述模型,在地圖中任選3個建筑作為樣例對象,檢索結(jié)果只顯示相似度最高的3個建筑,檢索結(jié)果如圖5所示.從檢索結(jié)果中可以看出,三組實驗均準確地檢索出了樣例對象本身,其形狀相似性均為1.0.本實驗表明了空間對象形狀描述模型可以精準識別空間對象的形狀,對形狀的輕微形變具有魯棒性.

從真實地圖中選取70個形狀各異的建筑物,如圖6中上方圖所示;對每一個建筑物分別縮放0.49、0.7、1.37倍,得到3個建筑物,如圖6中下方圖第一行從左至右依次是原始建筑、縮放0.49倍建筑、縮放0.7倍建筑、縮放1.37倍建筑.對原始建筑和3個縮放建筑分別旋轉(zhuǎn)45度、135度、225度得到12個建筑,如圖6中下方圖第二行、第三行、第四行的建筑分別為第一行建筑旋轉(zhuǎn)45度、135度、225度.對原始建筑進行四種仿射變換,得到4個建筑,如圖6中下方圖第五行所示.對每個建筑共進行了19次變換,得到了19個建筑,加上原始建筑,構(gòu)成了一類相似建筑的20種形變.70個原始建筑共形成了70類,每類20個相似建筑,共1400個建筑的形狀數(shù)據(jù)集.

對形狀數(shù)據(jù)集中的每個建筑均進行一次檢索,共進行1400次檢索實驗.在每次實驗檢索出的前40個建筑中,計算檢索建筑的相似建筑個數(shù),相似建筑個數(shù)與該類相似建筑總數(shù)20的比值為該建筑的檢索率,所有建筑檢索率的平均值為平均檢索率.文獻10、11和本文空間對象形狀描述法的平均檢索率如表1所示.本文對象形狀描述法的平均檢索率高于其他2個形狀描述法,具有更強的對象形狀描述能力,具有平移、旋轉(zhuǎn)、翻轉(zhuǎn)和尺度不變性,對因仿射變換造成的形狀形變具有一定的魯棒性.

表1 三種空間對象形狀描述法的平均檢索率

5.2 空間場景相似性檢索實驗

文獻[1]中的模擬場景數(shù)據(jù)庫共有1000個場景,每個場景由6個面區(qū)域組成.從模擬場景數(shù)據(jù)庫中選取30個不同類的場景作為樣例進行檢索實驗,檢索結(jié)果的例子如圖7所示.兩個例子中所有檢索結(jié)果的對象形狀、拓撲關(guān)系和方向關(guān)系均滿足樣例場景的要求,所有檢索結(jié)果的場景完整性Scomp均為1,影響檢索結(jié)果相似性分數(shù)的只為對象形狀和相離關(guān)系的相似度.通過實驗,30個不同場景檢索的查準率和查全率均為100%,樣例場景本身的相似性分數(shù)均最高為1.0.

繪制文獻1模擬場景數(shù)據(jù)庫中60個不同類場景的草圖,進行檢索實驗.文獻6與本相似性檢索方案的查準率和查全率如表2所示.本檢索方案的查準率、查全率均高于文獻6方案,這是因為本檢索方案加入了空間對象的形狀約束,形狀描述模型的精準識別提高了檢索準確率.

表2 查準率和查全率

以從OpenStreetMap中獲取的清華大學(xué)約1100個建筑的地圖為實驗數(shù)據(jù),通過程序提供的草圖繪圖功能,繪制要檢索的樣例場景,如圖8所示,實驗結(jié)果如圖9所示.圖8右側(cè)繪制形狀較為復(fù)雜的清華大學(xué)圖書館(最下方建筑)、新齋(最上方建筑)等四個建筑物為樣例場景,由于圖書館、新齋這兩個建筑形狀過于復(fù)雜、特殊,形狀描述模型可以準確找到對應(yīng)的匹配對象,而中間兩個形狀簡單的建筑卻可以找到很多形狀相似的匹配對象.通過相離關(guān)系的定量度量和方向關(guān)系的描述識別,形成了草圖的完全匹配和中間兩個建筑的部分匹配.

從實驗結(jié)果看出,完全匹配的相似度很高為0.906802,中間兩個建筑的部分匹配相似度很低.因為樣例場景中圖書館、新齋兩個建筑的形狀復(fù)雜、辨識度高,這兩個建筑的重要性遠大于中間兩個建筑,所以中間兩個建筑部分匹配的場景完整性Scomp很低小于0.19,導(dǎo)致部分匹配的場景相似度低.

6 結(jié)論

本文提出了基于形狀及空間關(guān)系的場景相似性檢索方法,并給出了空間對象形狀描述模型、空間關(guān)系描述模型、場景相似性自適應(yīng)計算模型,提高了空間對象形狀的識別精度、空間關(guān)系的描述精度和場景相似性檢索的精度,增加了場景檢索結(jié)果相似性打分的合理性,為復(fù)雜空間場景提供了更直觀、精度更高的相似性檢索方法.

[1]Egenhofer M J.Query processing in spatial-query-by-sketch[J].Journal of Visual Languages and Computing,1997,8(4):403-424.

[2]Egenhofer M J.Qualitative spatial relation reasoning for design[A].Studying Visual and Spatial Reasoning for Design Creativity [C].Netherlands:Springer Netherlands,2015.153-175.

[3]袁貞明,吳飛,等.基于草圖內(nèi)容的空間拓撲數(shù)據(jù)檢索方法[J].浙江大學(xué)學(xué)報(工學(xué)版),2006,40 (10):1663-1669.

Yuan Zhen-ming,Wu Fei,et al.Spatial topological data retrieval based on sketch content[J].Journal of Zhejiang University (Engineering Science),2006,40 (10):1663-1669.(in Chinese)

[4]Goyal R K.Similarity assessment for cardinal directions between extended spatial objects[D].Maine:University of Maine,2000.36-49.

[5]孫偉,歐陽繼紅,等.不確定區(qū)域間方向關(guān)系的相似性度量方法[J].電子學(xué)報,2014,42(3):597-601.

Sun Wei,Ouyang Ji-hong,et al.Similarity assessment of approximate direction relations[J].Acta Electronica Sinica,2014,42(3):597-601.(in Chinese)

[6]申世群,劉大有,等.基于草圖的空間數(shù)據(jù)檢索研究[J].電子學(xué)報,2010,38(8):1819-1824.

Shen Shi-qun,Liu Da-you,et al.Research on spatial data retrieval based on sketch[J].Acta Electronica Sinica,2010,38(8):1819-1824.(in Chinese)

[7]Jan S,Schwering A,et al.Qualitative representations of extended spatial objects in sketch maps[A].Proceedings of International AGILE′2014 Conference[C].Spain:Springer International Publishing,2014.37-54.

[8]Nedas K A,Egenhofer M J.Spatial scene similarity queries[J].Transactions in GIS,2008,12(6):661-681.

[9]He B,Wang D,Chen C.A novel method for mineral prospectivity mapping integrating spatial-scene similarity and weights-of-evidence[J].Earth Science Informatics,2015,8(2):393-409.

[10]安曉亞,孫群,等.一種形狀多級描述方法及在多尺度空間數(shù)據(jù)幾何相似性度量中的應(yīng)用[J].測繪學(xué)報,2011,40(4):495-508.An Xiao-ya,Sun Qun,et al.A Shape multilevel description method and application in measuring geometry similarity of multi-scale spatial data[J].Acta Geodaetica et Cartographica Sinica,2011,40(4):495-508.(in Chinese)

[11]付仲良,逯躍鋒.利用彎曲度半徑復(fù)函數(shù)構(gòu)建綜合面實體相似度模型[J].測繪學(xué)報,2013,42(1):145-151.Fu Zhong-liang,Lu Yue-feng.Establishment of the comprehensive model for similarity of polygon entity by using the bending radius complex function[J].Acta Geodaetica et Cartographica Sinica,2013,42(1):145-151.(in Chinese)

[12]Fan H,Zipf A,et al.Quality assessment for building footprints data on openstreetmap[J].International Journal of Geographical Information Science,2014,28(4):700-719.

[13]Zunic J,Rosin P L,et al.On the orientability of shapes[J].IEEE Transactions On Image Processing,2006,15(11):3478-3487.

[14]Strobl C.Dimensionally extended nine-intersection model (DE-9IM)[A].Encyclopedia of GIS[C].New York:springer-Verlag,2008.240-245.

[15]Eppstein D,Strash D.Listing all maximal cliques in large sparse real-world graphs[A].Proceedings of the 10th International Conference on Experimental Algorithms[C].Berlin:Springer Verlag,2011.364-375.

田澤宇 男,1987年生,黑龍江佳木斯人,哈爾濱工程大學(xué)博士生,主要研究方向為空間數(shù)據(jù)檢索、圖像處理.

E-mail:tianzeyu @hrbeu.edu.cn

門朝光 男,1963年生,黑龍江哈爾濱人,哈爾濱工程大學(xué)教授,主要研究方向為信息安全、空間數(shù)據(jù)檢索、圖像處理.

E-mail:menchaoguang@hrbeu.edu.cn

Spatial-Scene Similarity Retrieval Based on Shape and Spatial Relation

TIAN Ze-yu,MEN Chao-guang,TANG Ya-nan

(CollegeofComputerScienceandTechnology,HarbinEngineeringUniversity,Harbin,Heilongjiang150001,China)

To solve the problem of low efficiency and poor accuracy on spatial data retrieval,this paper proposes a scene similarity retrieval method based on spatial object shape description model,spatial relationship description model and adaptive scene similarity computing model.Spatial object shape description model can accurately retrieve database objects satisfied with the sample object shape constraints,and improve the space object shape recognition accuracy.Spatial relationship description model can retrieve database scenes satisfied with relationship constraints of the sample scene,and improve the spatial relationship description precision.Adaptive scene similarity computing model can mark and sequence complete or incomplete matching scenes satisfied with shape and relationship constraints,improve the rationality of similarity scores on retrieval results.Experiments of simulative and real scenes show the scene similarity retrieval has a good retrieval performance.

spatial data retrieval;shape description;spatial relation description;spatial-scene similarity

2015-07-30;

2015-10-11；責(zé)任編輯：藍紅杰

TP391.3

A

0372-2112 (2016)08-1892-07