結合拓撲和方位的定性空間推理方法

摘 要：空間區域的拓撲關系和方位關系是空間推理的重要研究內容，以往的工作集中在單一的空間方面， 這不能滿足實際應用領域的需要。基于主方位模型給出了主方位關系的形式化定義，考慮到拓撲與方位間的相互依賴關系，提出了結合拓撲和方位的定性表示與推理算法，能夠處理多方面空間信息，在空間數據庫和機器人導航等領域具有實際應用價值。

關鍵詞：定性空間推理; 約束滿足問題; 拓撲; 方位

中圖法分類號：TP18文獻標識碼：A

文章編號：1001—3695(2007)02—0057—03

1 引言

空間推理目前是AI的一個活躍的研究方向，是運用人工智能技術和方法對空間對象進行建模、描述和表示，并對其空間關系進行處理和分析的過程。它在地理信息系統，機器人導航，圖形、圖像處理，模式識別和自然語言理解等方面有廣泛的應用[1—5]。

空間推理以往的工作涉及到不同的空間關系，包括拓撲[3—5]、方位[6—8]、形狀[9]、尺寸、距離和位置[11]。然而，大多數的定性空間推理研究集中在單一的空間方面，而現實世界的應用經常需要處理多空間方面，并且由于不同空間方面相互間并不獨立，單獨地處理單一空間方面不滿足實際應用的需要。結合多空間方面的研究已得到廣泛的認同，但這部分研究工作的進展緩慢：1997年，Climentini等人[11]研究了結合方向和距離的定性空間表示與推理；2002年，Renz等人[4]提出集成拓撲和距離的空間表示與推理方法，并研究了推理算法的時間代價；2004年，我們提出了結合時間和位置的時空表示與推理方法[12]。本文研究了定性主方位關系的表示，以及它與拓撲信息結合時兩者的相互依賴關系。

本文以Goyal[6]和Skiadopoulos[7]的主方位模型為基礎，研究了主方位關系的表示及推理。考慮到主對象及參考對象在水平軸和垂直軸上的投影關系恰與Allen[13]的區間代數中的13種區間關系一致，因此采用主對象與參考對象的投影關系對描述方位信息，形式化定義主方位關系。

現有的空間區域間的拓撲關系模型中，最具有代表性的是Randell等人[5]提出的RCC理論。研究者們圍繞該理論進行了大量的研究工作，但在實際應用領域中，僅有拓撲信息是不夠的。方位關系是另一個重要的空間方面，拓撲關系與方位關系的結合能夠表示空間對象間的位置信息，描述空間場景。CSP(約束滿足問題)是空間推理中一個重要的研究內容，單獨的拓撲或方位關系的推理算法在處理相應的約束滿足問題時都很有效，但這兩類算法都不能發現拓撲和方位約束結合時所產生的不相容約束。本文提出的算法考慮了拓撲和方位間的依賴關系，能夠處理結合RCC—8和方位約束的約束滿足問題。

2 拓撲關系模型——區域連接演算RCC—8

本文中的區域是R²空間中的閉合連通區域。

目前空間推理的拓撲關系模型中，RCC模型是研究得最廣泛和深入的模型。RCC—8包含八個JEPD（Jointly Exhaustive and Pairwise Disjoint，互不相交且無遺漏）關系，這八個關系被稱為基本關系(圖1)，分別是不連接（DC）、外部連接（EC）、部分交迭（PO）、相等（EQ）、正切真部分（TPP）、非正切真部分（NTPP）、反正切真部分（TPPI）和反非正切真部分（NTPPI）。

復合關系是定性空間推理的基本操作，它能夠由兩個已知關系生成一個新的關系，并能依此類推。它是進行約束滿足等推理的基礎。本文研究的復合是基于一致性的復合，定義如下：

3 主方位關系模型

方位關系是另一個重要的空間方面，在空間表示和推理中具有重要地位。方位關系描述空間某對象相對于另一對象的位置。目前具有代表性的方位關系模型有基于點的模型和基于區域的模型。基于點的模型把空間對象看成一個點，以該點為原點將空間劃分成一些互不相交的部分，包括圓錐模型和雙十字模型。Abdelmoty的基于區域的方位模型擴展了拓撲關系的4-交集模型，按照區域的最小邊界矩形的四個頂點發出的四條射線，將區域外的空間分成四個半無限區域。Goyal的主方位關系模型也是基于區域的，按照區域的最小邊界矩形將空間劃分成九個部分。目前對主方位關系模型的研究工作較多，該模型可以應用于處理不確定性、相似性查詢等方面。

主方位關系模型以參考對象為中心，按參考對象的最小邊界矩形（MBR）的四條邊將空間劃分成九個部分(圖2)，記為S，SW，W，NW，N，NE，E，SE，CO，分別對應地理空間中的南、西南、西、西北、北、東北、東、東南和中心區域。通過主對象與這九個部分的交互結果描述主對象相對于參考對象的方位關系。

根據對象在x軸（y軸）的投影關系，形式化定義主方位模型中的基本方位關系。令A是R2空間中的封閉區域，A在x軸(y軸)上的投影記為Projx(A)(Projy(A))，兩個對象A，B在x軸（y軸）的投影關系如圖3所示，與Allen區間代數中的13種區間關系相對應。

這13種關系分別為b，m，o，fi，di，si，e，s，d，f，oi，mi，bi (圖4)。例如，若主對象A和參考對象B的方位關系為A W B，則它們在x軸上的投影關系為b，在y軸上的投影關系為d，則用投影關系對A(b，d) B表示兩個對象間的方位關系。為了更清晰地表示方位關系，將這13種關系分為六個等價類：

4 綜合拓撲和主方位關系

空間對象間的拓撲關系和方位關系并不是相互獨立的。拓撲關系是結合方位信息的，如區域A，B間的拓撲關系若為“包含于”關系，可以推斷出A，B的方位關系為CO。同樣，方位關系有時也提供了拓撲信息，若A，B的方位關系為W，則其之間的拓撲關系為DC或EC。拓撲關系與方位關系相結合，可以更清楚地表達空間對象間的位置關系，如若有兩個約束A W B和A DC B，就可知道A在B的西面，且A和B不接觸。

表1給出了由基本RCC—8關系得到的基本主方位關系，表2給出了由原子主方位關系得到的拓撲關系。Dirset（T）是由拓撲關系T得出的最強的主方位關系，Topset（D）是由原子主方位關系D得出的最強的拓撲關系。

由表1和表2可以看出，由DC，EC，EQ，TPP，NTPP得出的方位關系是原子主方位關系，而其余的拓撲關系得出的基本主方位關系是非原子的；反過來，由原子主方位關系得出的拓撲關系包含DC，EC，EQ，TPP，NTPP，其他的基本拓撲關系是由非原子主方位關系得出的。由于篇幅所限，本文不詳細列舉。

約束滿足問題是空間推理及很多空間和時空領域的研究重點，空間關系可以視為對空間對象的約束。RSAT問題是關系的約束滿足問題。空間推理所面臨的主要推理問題是RSAT，其定義如下:

定義4 給定集合Θ是形如xRy的空間約束集合，x，y是區域變量，R是空間關系如拓撲或方位關系，確定Θ是否相容的問題稱為RSAT。

5 結論

本文研究了基于投影區間的主方位關系表示方法，以及它與拓撲關系相結合時的一些問題，拓撲與方位結合可以用于小規模空間的場景描述；提出了一個解決包含拓撲和方位約束集合的RSAT算法Consistency_TopDic，該算法在形式上類似于經典的路徑相容算法，除了考慮約束的傳遞性外，還考慮到約束間的依賴性；能夠處理包含拓撲和方位關系的RSAT問題，在基于GIS的系統中具有實際應用價值。下一步的工作是結合時間、拓撲和方位信息進行定性時空推理。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。