移動點與參考地物時空關系的自然語言描述方法研究

張 彩 麗，吳 靜，鄧 敏

(中南大學地球科學與信息物理學院，湖南 長沙 410083)

?

移動點與參考地物時空關系的自然語言描述方法研究

張 彩 麗，吳 靜，鄧 敏

(中南大學地球科學與信息物理學院，湖南 長沙 410083)

基于分解-組合的思想，首先對移動點的運動軌跡進行細化，并分別對移動點與參考地物目標的時空拓撲關系進行描述，在此基礎上綜合考慮它們之間的方向關系和距離關系，并對自然語言時空關系進行定義和集成描述。最后，通過實例對移動點運動軌跡進行了自然語言描述和應用分析。文中實現的移動對象運動軌跡的形式化描述方法，可廣泛應用于導航系統中，對時空查詢、時空分析及時空推理等諸多問題的研究具有重要意義。

移動對象；時空關系；自然語言

0 引言

移動對象是空間與時間耦合框架下的統一體，大致分為兩類：位置隨時間不斷發生變化的移動點對象；形狀隨時間不斷發生變化的移動面對象，其中移動點對象(如汽車、行人、颶風眼等)在交通控制、運輸管理、車輛導航、移動位置服務等領域廣受關注。在日常交流中，人們經常使用自然語言描述社會活動中各種空間對象之間的空間位置關系，尋找并確定相應的服務對象，因而對時空關系進行更高層次的自然語言描述可以設計更友好的人機交互界面，幫助人們快速查詢，使得任何人能在任何時候、任何地點享受地理信息的服務。與靜態對象的空間關系描述類似，移動對象間的時空關系可劃分為時空拓撲關系、時空方向關系和時空距離關系。目前對于時空拓撲關系的研究成果較多[1-4]，但與拓撲關系相比，方向關系和距離關系則更貼近人們生活、用途更為廣泛，是時空數據庫中數據和自然語言的一種有效連接手段[5]。

高勇等[6]將路徑信息服務視為城市交通指揮系統、導航系統等信息系統中最為關鍵的內容，并對移動點-參考地物空間拓撲關系進行建模，將其表示為“變化前觀測時刻”、“突變時刻”、“變化后觀測時刻”的三元組：R=(Rts,Rtm,Rte)；Naet等[7]將移動對象的運動軌跡表達為線，擴展空間線與面之間的19種拓撲關系，并用來描述足球的運動模式；Kurata等[8]用有向線表達移動點的軌跡，基于9+-intersection矩陣區分了26種有向線與面目標之間的拓撲關系。但以上3種模型均不能區分軌跡直接穿過邊界或沿著邊界穿出等一些細節關系，且這些模型均側重拓撲關系的研究，而未考慮方向關系和距離關系。在采用自然語言對移動對象軌跡進行描述時，通常不是某一種類型的時空關系(如“穿過”、“進入”、“中東部”、“遠離”等)，而是多種類型時空關系的組合，如“穿過中東部”、“從東部邊界進入”、“遠離某城市”、“靠近某城郊西”等[9]。因此，單獨使用時空拓撲關系、方向關系或距離關系無法描述這種復雜的自然語言時空關系。針對上述問題，本文對移動點的運動軌跡進行細化，綜合考慮拓撲關系、方向關系與距離關系，并對移動點對象與參考地物的自然語言時空關系進行定義及形式化描述。

1 基于分解-組合的時空拓撲關系建模

1.1 移動點與參考地物時空拓撲關系表達

由文獻[10-12]可知，復合關系可視為由多個基本關系組成，在時間段I=[t0,tn-1](?t0,t1,…,tn-1∈I且t0

表1 移動點與參考地物的基本空間/時空拓撲關系

Table 1 The basic spatial /spatio-temporal topological relations between a moving point and a reference feature

移動點/參考點移動點/參考線移動點/參考面空間拓撲關系disjointmeetdisjointmeetdisjointmeetinside時空拓撲關系DisjointMeetDisjointMeetDisjointMeetInside

對于參考面A，移動點B特征軌跡點集和特征軌跡段集LS的建立步驟為：1)將時間段I內移動點B的起始點記為(t0,p0)并記入到特征軌跡點集PS中；2)隨時間進行跟蹤掃描，將移動點與參考面邊界的交點分別記為(t1,p1),(t2,p2),…,(tn-2,pn-2)，依次將這些交點及移動點B的終點(tn-1,pn-1)記入到PS，并將(ti,pi),(ti+1,pi+1)之間的特征軌跡段記為(Ii,fi(x,y,t))，依次記入特征軌跡段集LS；3)依次對特征軌跡段(Ii,fi(x,y,t))進行掃描判斷，如果fi-1??A∧fi??A，則從PS、LS中分別去掉(ti,pi),(Ii,fi(x,y,t))，并分別將PS、LS中的下標i+1,…,m減1，直到LS中的軌跡段掃描判斷完為止。對于移動點與參考點/線，將步驟2中移動點與參考面邊界的交點改為移動點與參考點/線的交點。對于移動點與參考點，步驟3可省略。圖1為移動點軌跡細化實例。

圖1 移動點軌跡細化實例

Fig.1 A detailed illustration of moving point trajectory

記特征軌跡點(ti,pi)(0≤i≤n-1)與參考地物A的基本空間拓撲關系為top(A,ti)，特征軌跡段(Ii,fi(x,y,t))(0≤i≤n-2)與參考地物A的基本時空拓撲關系為top(A,Ii)，則時間段I內移動點B與參考地物A的時空拓撲關系可以表達為時間段I內移動點B軌跡細化片段與參考地物A拓撲關系的集成：Top(A,B,I)=(top(A,t0),top(A,I0),…,top(A,tn-2),top(A,In-2),top(A,tn-1))。

1.2 移動點與參考地物的復合時空拓撲關系定義

理論上，時間段I內移動點與參考地物的時空拓撲關系有許多種，基于上述方法本文給出了一些常見復合時空拓撲關系的定義，根據移動點與參考點、線、面定義的相同與不同列于表2。為便于區分，這里用P表示移動點，p、l、r分別表示參考點、線、面。其中“→”表示拓撲關系發生變化的先后順序，“←”表示某時空拓撲關系的逆。

表2 移動點與參考點、線、面復合時空拓撲關系定義

Table 2 Definitions of composite spatio-temporal topological relationships between a moving point and a reference point (or a reference line or a reference region)

定義1P(p，l，r)≡-Arrival≡disjoint→Disjoint→meet定義2Pr?Enter≡disjoint→Disjoint→meet/Meet→Inside定義3P(p，l)?Leave≡P(p，l)?Arrival←Pr?Leave≡Pr?Enter←定義4Pr?Go?away?from≡Pr?Arrival←定義5Pp?Cross≡Pp?Arrival→Pp?Leave Pr?Cross≡Pr?Enter→Pr?Leave定義6Pp?Return≡meet→Disjoint→meet定義7Pr?In?touch≡Inside→meet→Inside定義8Pr?Out?touch≡disjoint→Disjoint→meet→Disjoint→disjoint定義9Pr?Bypass≡disjoint→Disjoint→Meet→Disjoint→disjoint

根據以上思想，圖1a、圖1c中時間段I內移動點B與參考地物A的時空拓撲關系分別表達為：Top(A,B,I)=(disjoint,Disjoint,meet,Disjoint,disjoint)、(disjoint,Disjoint,meet)，相應的復合關系為：Pp-Cross、Pr-Arrival。

2 集成方向、距離的復雜時空關系定義及描述

由空間認知可知拓撲關系是實現各類空間信息集成描述的基礎，而方向關系和距離關系是對空間目標相對位置關系的進一步約束。因此需根據不同類型的參考地物，在時空拓撲關系的基礎上描述局部方向關系和距離關系。

2.1 集成方向的復雜時空關系定義及描述

2.1.1 移動點/參考點 移動點與參考點方向關系的自然語言描述大多只考慮起始及終止特征軌跡點，考慮到投影模型不能提供人們常用的東南西北的方位關系，Frank通過比較得出基于錐體模型在方向描述上較優的結論，本文采用8方向錐形模型判斷起始與終止特征軌跡點與參考點的方向關系。

定義1Pp-Start-d(A,B)≡(top(A,t0)=disjoint)∧dir(A,t0)，其中d∈(N,S,W,E,NW,NE,SW,SE)?移動點B從參考點A的d方向出發。

定義2Pp-End-d(A,B)≡(top(A,t0)=disjoint)∧dir(A,tn-1)，其中d∈(N,S,W,E,NW,NE,SW,SE)?移動點B到達參考點A的d方向。

2.1.2 移動點/參考線 移動點與參考線方向關系的描述大多只考慮起始特征軌跡點及與參考線時空拓撲關系為Meet的特征軌跡段，考慮到對于線參考地物(河流、道路)通常不會使用所有絕對方向謂詞(例如，汽車沿著湘江從南往北行駛，在某時刻該汽車位于湘江東或湘江西；或者汽車沿著五一大道從西往東行駛，在某時刻位于五一大道東或西)，本文采用文獻[14]的方法根據參考線的走向對空間方向關系進行劃分。

定義1Pl-Start-d(A,B)≡(top(A,t0)=disjoint)∧dir(A,t0)，其中d∈(N,S,W,E)?移動點B從參考線A的d方向出發。

定義2Pl-End-d(A,B)≡(top(A,tn-1)=disjoint)∧dir(A,tn-1)，其中d∈(N,S,W,E)?移動點B到達參考線A的d方向。

定義3Pl-Along-d(A,B)≡(top(A,Ii)=Meet)∧(dir(ti,ti+1)=d)，其中特征點間方向關系采用四方向錐形模型，d∈(N,S,W,E,O)?移動點B沿著參考線A向d運動。

2.1.3 移動點/參考面 對于參考面，方向關系的描述需同時考慮特征軌跡點和特征軌跡段,其方向關系可以根據杜世宏等[10]提出的細節方向關系模型進行判斷。

定義1Pr-Start-d(A,B)≡(top(A,t0)=disjoint)∧dir(A,t0)，其中d∈(N,S,W,E,NW,NE,SW,SE,O)?移動點B從參考面A的d方向出發。

定義2Pr-Start-d(A,B)≡(top(A,t0)=(top(A,t0)=inside)∧dir(A,t0)，其中d∈(NP,SP,WP,EP,NWP,NEP,SWP,SEP,O)?移動點B從參考面A的d部出發。

定義3Pr-Start-d(A,B)≡(top(A,t0)=meet)∧dir(A,t0)，其中d∈(NL,SL,WL,EL,NWL,NEL,SWL,SEL,O)?移動點B從參考面A的d邊界出發。

定義4Pr-End-d(A,B)≡(top(A,t0)=disjoint)∧dir(A,t0)，其中d∈(N,S,W,E,NW,NE,SW,SE,O)?移動點B到達參考面A的d方向。

定義5Pr-End-d(A,B)≡(top(A,t0)=inside)∧dir(A,t0)，其中d∈(NP,SP,WP,EP,NWP,NEP,SWP,SEP,O)?移動點B到達參考面A的d部。

定義6Pr-End-d(A,B)≡(top(A,t0)=meet)∧dir(A,t0)，其中d∈(NL,SL,WL,EL,NWL,NEL,SWL,SEL,O)?移動點B達到參考面A的d邊界。

定義7Pr-Enter_d(A,B)≡(top(A,Ii)=Disjoint)∧(top(A,Ii+1)=Inside)∧(dir(A,ti+1)=d)或(top(A,Ii)=Meet)∧(top(A,II+i)=Inside)∧(dir(A,ti+1)=d)，其中d∈(NL,NWL,WL,SWL,SL,SEL,EL,NEL)?移動點B從參考面A的d邊界進入。

定義8Pr-Leave_d(A,B)≡(top(A,Ii)=Inside)∧(top(A,Ii+1)=Disjoint)∧(dir(A,ti+1)=d)或(top(A,Ii)=Meet)∧(top=(A,Ii+1)=Disjoint)∧(dir(A,ti+1)=d)，其中d∈(NL,NWL,WL,SWL,SL,SEL,EL,NEL)?移動點B從參考面A的d邊界離去。

定義9Pr-In-touch_d(A,B)≡(top(A,Ii)=Inside)∧(top(A,Ii+1)=Inside)∧(dir(A,ti+1)=d)，其中d∈(NL,NWL,WL,SWL,SL,SEL,EL,NEL)?移動點B內切參考面A的d邊界。

定義10Pr-Out-touch_d(A,B)≡(top=Disjoint)∧(top(A,Ii+1)=Disjoint)∧(dir(A,ti+1)=d)，其中d∈(NL,NWL,WL,SWL,SL,SEL,EL,NEL)?移動點B外切參考面A的d邊界。

定義11Pr-Alongside_d(A,B)≡(top(A,Ii)=Meet)∧(dir(A,Ii)=d)，其中d為8方向邊界方向關系NL,NWL,WL,SWL,SL,SEL,EL,NEL或4方向邊界方向關系NL4,SL4,EL4,WL4?移動點B沿著參考面A的d邊界運動。

定義12Pr-Cross-d(A,B)≡(top(A,I)=Cross)∧(top(A,Ii)=Inside)∧(dir(A,Ii)=d)，其中d∈面目標A內部的復合方向(NP4,WP4,SP4,EP4,CPNS,CPEW,CPSW-NE,CPNW-SE,CP)?移動點B穿過參考面A的d部。

2.2 集成距離的復雜時空關系定義及描述

移動點與參考地物的時空距離關系與特征軌跡段中移動軌跡點與參考地物的距離有關，于是，根據特征軌跡段與參考地物的時空拓撲關系可得相應的描述規則。

特征軌跡段與參考地物的時空拓撲關系為3種：Disjoint、Inside、Meet，而特征軌跡段與參考地物時空拓撲關系為Meet時，這一軌跡段內移動軌跡點與參考地物的距離均為0，故不考慮距離也能描述移動點沿著參考地物運動，本文集成Disjoint、Inside這兩種時空拓撲關系與距離關系對移動點與參考地物的復雜時空關系進行定義(圖2)。

對于參考地物為面的情況，定義d(?A,ti)為軌跡點pi到參考面A邊界的最小距離，dmin(?A,Ii)為特征軌跡段li中各軌跡點到參考面A邊界最小距離的最小距離，dmax(?A,Ii)為特征軌跡段li中各軌跡點到參考面A邊界最小距離的最大距離，d(?A,ti+1)為軌跡點pi+1到參考面A邊界的最小距離。

(1)特征軌跡段與參考面相離(Disjoint)。

定義1Pr-OutApproach≡d(?A,ti)>=dmax(?A,Ii)>dmin(?A,Ii)>=d(?A,ti+1)?移動點B逐步靠近參考面A。

定義2Pr-OutGo-away-from≡d(?A,ti)<=dmin(?A,Ii)

定義3Pr-OutAround≡d(?A,ti)≈dmin(?A,Ii)≈dmax(?A,Ii)≈d(?A,ti+1)?移動點B圍著參考面A運動。

定義4Pr-OutApproach-Away≡d(?A,ti)>dmin(?A,Ii)

定義5Pr-OutAway-Approach≡d(?A,ti)d(?A,ti+1)?移動點B逐步遠離參考面A然后靠近。

(2)特征軌跡段被參考面包含(Inside)。

定義6Pr-InApproach≡d(?A,ti)>=dmax(?A,Ii)>dmin(?A,Ii)>=d(?A,ti+1)?移動點B逐步靠近參考面A內部邊界。

定義7Pr-InGo-away-from≡d(?A,ti)<=dmin(?A,Ii)

定義8Pr-InAround≡d(?A,ti)≈dmin(?A,Ii)≈dmax(?A,Ii)≈d(?A,ti+1)?移動點B圍著參考面A內部運動。

定義9Pr-InApproach-Away≡d(?A,ti)>dmin(?A,Ii)

定義10Pr-InAway-Approach≡d(?A,ti)d(?A,ti+1)?移動點B逐步遠離參考面A內部邊界然后靠近。

圖2 移動點與面目標時空距離關系實例

Fig.2 An example of spatio-temporal distance relationships between a moving point and a reference region

當參考地物為點/線時，特征軌跡段與其時空拓撲關系為Disjoint，時空距離關系的定義與移動點/面的第一種情況相同。其中，d(?A,ti)為軌跡點pi到參考點/線A的最小距離，dmin(?A,Ii)為特征軌跡段li中各軌跡點到參考點/線A最小距離的最小距離，dmax(?A,Ii)為特征軌跡段li中軌跡點到參考點/線A最小距離的最大距離，d(?A,ti+1)為軌跡點pi+1到參考點/線A的最小距離。

根據以上集成方向和距離的復雜時空關系定義，圖1b可以描述為：移動點B從參考線A的北方向出發，逐步靠近參考線A，沿著參考線A向東運動，逐步遠離參考線A，最終到達參考線A南方向。

3 實驗分析

根據上述集成方向的復雜時空關系描述方法，基于Microsoft公司的Visual Studio 2008平臺，采用C#編程語言，使用ESRI公司的ArcEngine組件庫，對圖3a中移動點的軌跡進行描述，如圖3b。

根據本文提出的思想在實際應用中可以根據移動用戶請求，進行出行規劃生成最優路徑，最后對該路徑用自然語言進行描述，實現圖文轉換，并將結果通過移動通訊網絡對移動用戶提供服務。如果在導航應用中需要對行駛距離進行定性描述，可以根據上述集成距離的復雜時空關系描述方法進行描述；如果需要對行駛距離進行定量描述，只需對特征軌跡段長度進行計算即可。

圖3 實驗分析

Fig.3 A test for moving point trajectory

不僅如此，根據上述定義還可以對移動軌跡進行快速的定位查詢，這不僅可以應用于LBS、軍事領域，還有助于正確掌握臺風、氣旋等各種風暴所造成的災害方位，進行快速救災處理。時空數據庫的查詢語言為STQL，可進行一些復雜時空分析操作，設有模式如下：

Countries(id:integer,name:string,geometry:region)

Planes(id:integer,name:string,route:mpoint)

查詢1 查詢在我方領空西北邊界逗留的敵機

SELECT p.name

FROM Planes,Countries

WHERE Countries.name="China" ANDAlongside_NWL(Countries.geometry,p.route)

查詢2 查詢逐步靠近我方領空的敵機

SELECT p.name

FROM Planes,Countries

WHERE Countries.name="China" ANDPr-OutApproach(Countries.geometry,p.route)

4 結論

本文根據移動點對象的特性，基于分解-組合的思想對移動點與參考目標的時空拓撲關系進行表達。該方法不僅解決了現有模型存在的移動點軌跡內部與參考地物相交的一些細節關系區分問題，而且綜合考慮方向、距離關系對復雜自然語言時空關系進行了定義及描述，對時空查詢及推理具有一定的研究意義。本文移動對象運動軌跡的形式化描述方法可廣泛應用于導航系統中，下一步將結合時空推理的方法，對移動對象的運動軌跡進行預測。

[1] 高勇,張晶,朱曉禧,等.移動對象時空拓撲關系模型[J].北京大學學報(自然科學版),2007,43(4):468-473.

[2] CLARAMUNT C,BIN J.An integrated representation of spatial and temporal relationships between evolving regions[J].Geographical Systems,2001,3(4):411-428.

[3] HALLOT P,BILLEN R.Spatio-temporal configurations of dynamics points in a 1D space[A].Behaviour Monitoring and Interpretation BMI[C].2007.77-90.

[4] ERWIG M,SCHNEIDER M.Spatio-temporal predicates[J].IEEE Transactions on Knowledge and Data Engineering,2002,14(4):881-901.

[5] SCHNEIDER M,TAO C,VISWANATHAN G,et al.Cardinal directions between complex regions[J].ACM Transactions on Database Systems,2012,37(2):1-45.

[6] 高勇,劉瑜,鄔倫,等.移動點對象與參考地物空間拓撲關系[J].計算機工程,2007,33(22):57-59.

[7] NAET K S,KONG H,CHO M,et al.Multimedia information retrieval based on spatiotemporal relationships using description logics for the semantic web[J].International Journal of Intelligent Systems ,2006,21:679-92.

[8] KURATA Y,EGENHOFER M J.The 9+-Intersection for Topological Relations between a Directed Line Segment and a Region[C].BMI,2007.62-76.

[9] 杜世宏,王橋,李治紅.GIS 中自然語言空間關系定義[J].武漢大學學報(信息科學版),2005,30(6):533-538.

[10] 鄧敏,馬杭英.線與面目標間拓撲關系的層次表達方法[J].測繪學報,2008,37(4):507-513.

[11] 杜清運.空間信息的語言學特征及其自動理解機制研究[D].武漢:武漢大學,2001.

[12] 黃雪萍,鄧敏,吳靜,等.線面目標自然語言空間關系集成表達與描述方法研究[J].武漢大學學報(信息科學版),2013,38(2):230-234.

[13] GüTING R H,B?HLEN M H,ERWIG M,et al.A foundation for representing and querying moving objects[J].ACM Transactions on Database Systems,2000,25(1):881-901.

[14] 黃雪萍.基于地名信息的空間查詢方法研究[D].長沙:中南大學,2012.

Natural-Language Description of Spatio-temporal Relationships between Moving Points and Reference Features

ZHANG Cai-li,WU Jing,DENG Min

(SchoolofGeosciencesandInfo-Physics,CentralSouthUniversity,Changsha410083,China)

Modeling spatio-temporal relationships between moving objects is of great significance for spatio-temporal queries,spatio-temporal analysis and reasoning.Based on the slice representation of moving point′s trajectory,a novel method is proposed to describe the spatio-temporal topological relationships between a moving point and reference feature.At the same time,an integrated framework is presented for the representation of spatio-temporal relationships between moving points and reference features according to the description rules of natural language,where the topological,directional and distance relations between moving points and reference features are considered together.Finally,a case study is provided to demonstrate the application and feasibility of the proposed method in this paper.

moving objects;spatio-temporal relationships;natural language

2014-09-17；

2014-12-28

國家自然科學基金項目(41171351、40871180)：中南大學中央高校基本科研業務費專項資金資助項目(2012zzts008)

張彩麗(1989-)，女，碩士研究生，主要研究移動對象時空關系自然語言描述與智能查詢。E-mail：renlisi888@126.com

10.3969/j.issn.1672-0504.2015.03.003

P208

A

1672-0504(2015)03-0012-05