一種球面點投影關(guān)系的推理方法

歐陽繼紅，馬 玲

（1.吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，長春 130012；2.吉林大學(xué) 符號計算與知識工程教育部重點實驗室，長春 130012）

空間推理可以應(yīng)用到地理信息系統(tǒng)，機器人導(dǎo)航等許多領(lǐng)域。目前，多數(shù)模型都是針對二維或三維空間關(guān)系的研究［1］。由于實際應(yīng)用中有時需要直接處理球面上的空間信息［2］，如全球變暖的氣象分析，全球疾病傳播的研究，而二維或三維的空間關(guān)系模型以及在此基礎(chǔ)上得到的改進模型［3］無法直接應(yīng)用到球面上，因此，將已有研究推廣到球面上建立球面模型，日益受到關(guān)注。2005年，Egenhofer［4］將描述拓撲關(guān)系的傳統(tǒng)9交集模型擴展到球面上。然而，單一的拓撲關(guān)系無法較詳細地描述空間關(guān)系，因此，2006年和2010年Clementini構(gòu)建了可以同時描述拓撲和方向關(guān)系的平面投影關(guān)系模型［5］，并給出基于此模型的推理系統(tǒng)［6］。2008年，Clementini在此基礎(chǔ)上將球面上的空間物體抽象成點，建立了球面點投影關(guān)系模型［7］（Projective relations among points on the sphere），簡稱為 PRPS 模型。但是，Clementini只給出了模型的形式表示，未給出推理算法。

為了完善PRPS模型，本文給出了基于PRPS模型的推理算法，通過此推理算法可以由給出的球面投影關(guān)系得到未知的球面投影關(guān)系。

1 球面屬性與PRPS模型

球面異于平面的特性有很多，例如球面上沒有直線，可以用大圈來代替，大圈是球面被經(jīng)過球心的平面截得的圓。對跖點是指兩個大圈的交點，有無數(shù)個大圈經(jīng)過。球面上除對跖點外，其他任意兩點可以唯一確定一個大圈。

定義1 三元關(guān)系指物體A關(guān)于物體B和C的關(guān)系，用r（A，B，C）來表示。其中B、C為參考物體，A為目標物體，B、C在關(guān)系表示中的位置有嚴格的順序限制［5］。

定義2 已知三個物體A、B和C經(jīng)過任意次投影后仍保持共線，則稱此三個物體具有共線性［5］。

定義3 投影關(guān)系是一種三元空間關(guān)系，其中三個物體具有共線性［5］。

投影關(guān)系可以描述成“右面”、“之間”、“包圍”等。例如，“某城市在北京與上海之間”，“某湖被眾山包圍”，“某車在交通燈的右邊”等。投影關(guān)系是一種可以同時描述拓撲與方向關(guān)系的空間關(guān)系［5］。

1.1 平面點投影關(guān)系表達及推理模型

Clementini構(gòu)建的平面點投影關(guān)系模型根據(jù)參考點P2、P3的位置關(guān)系，將模型分為兩種情況：P2、P3是相同點時，將平面分成inside與outside兩部分；P2、P3是不同點時，將平面分為rightside，leftside，before，after，between五部分，如圖1所示。

Clementini針對平面投影關(guān)系模型建立了一個推理系統(tǒng)，類似二元空間關(guān)系的逆與復(fù)合運算，將其用于構(gòu)建服務(wù)于空間查詢的推理系統(tǒng)。因此平面投影關(guān)系研究逆、翻轉(zhuǎn)、復(fù)合3種運算，具體定義如下［6］：

圖1 平面投影關(guān)系模型Fig.1 Projective relations model on the plane

定義4 令r（P1，P2，P3）為P1關(guān)于P2、P3的投影關(guān)系，r1（P1，P3，P2）為P1關(guān)于P3、P2的投影關(guān)系，稱r1（P1，P3，P2）為r（P1，P2，P3）的逆關(guān)系，簡稱為“逆”，記作r︶（P1，P3，P2）。

定義5 令r（P1，P2，P3）為P1關(guān)于P2、P3的投影關(guān)系，r1（P3，P1，P2）為P3關(guān)于P1、P2的投影關(guān)系，稱r1（P3，P1，P2）為r（P1，P2，P3）的翻轉(zhuǎn)關(guān)系，簡稱為“翻轉(zhuǎn)”，記作r︵（P3，P1，P2）。

定義6 令r1（P1，P2，P3）為P1關(guān)于P2、P3的投影關(guān)系，r2（P2，P3，P4）為P2關(guān)于P3、P4的投影關(guān)系，r0（P1，P3，P4）為P1關(guān)于P3、P4的投影關(guān)系，稱r0為r1和r2的復(fù)合關(guān)系，記作r1?r2（P1，P3，P4）。

投影關(guān)系r的逆關(guān)系與翻轉(zhuǎn)關(guān)系合稱為r的置換關(guān)系。

1.2 PRPS模型

Clementini提出的PRPS模型的定義如下［7］：

（1）P2，P3是同一點時

球面被分成兩部分，即：點P2（用in（inside）表示）與球面上除點P2的所有范圍（用out（outside）表示）。如圖2（a）所示。

（2）P2，P3是對跖點時

球面被分成兩部分，即：點P2、P3（用in＿a（in＿antipodal）表示）與球面上除了點P2、P3的所有范圍（用out＿a（out＿antipodal）表示）。如圖2（b）所示。

（3）P2，P3是不同點且不為對跖點時

球面被P2、P3所確定的大圈分成兩個半球面，將P2P3所在的較短的弧規(guī)定為向量P—2P→3，較長弧為 P—3P→2、沿著 P—2P→3上半球面為ls（leftside），下半球面為rs（rightside），所示的弧以及P2和P3兩點為bt（between），所示的弧稱為notbt（notbetween），如圖2（c）所示。

PRPS模型包含8種投影關(guān)系：bt，notbt，rs，ls，in，out，in＿a，out＿a，此關(guān)系集合是互斥完備的。

圖2 PRPS模型Fig.2 PRPS model

2 基于PRPS模型的推理算法

根據(jù)Clementini構(gòu)建的球面投影關(guān)系模型，下面給出基于此模型的推理算法，用于實現(xiàn)由球面物體間已知的投影關(guān)系推理出未知的投影關(guān)系。

2.1 球面推理與平面推理的異同

與平面推理［6］一樣，球面推理也是將對象點用坐標來表示，平面點采用二維坐標（x，y）表示，球面點采用三維坐標（x，y，z）表示。同樣根據(jù)參考點的連線來劃分平面或球面區(qū)域，考慮目標點的坐標在某個劃分后的區(qū)域來確定三點之間的投影關(guān)系。

由于球面是一個封閉的面，球面點的投影關(guān)系較平面點的投影關(guān)系復(fù)雜，所以，球面推理與平面推理不同，具有一定的特殊性：

（1）球面上存在對跖點，所以模型需包含參考點為對跖點的情況，推理方法也需考慮此種情況。

（2）當參考點是不同點時，平面所劃分的區(qū)域除bt外，其他4個區(qū)域均為開放區(qū)域，而球面所劃分的區(qū)域都是彼此相連接的，即bt、notbt在同一個大圈上，ls、rs則由一個大圈來連接且區(qū)分。

2.2 球面推理算法

推理可以理解成從已有的判斷與事實得到新的判斷。本文的球面推理過程可以表示為如下過程：

其中P1、P2、P3和P4為球面點，存在的投影關(guān)系為r1（P1，P2，P3）與r2（P2，P3，P4）；CONVERSE算法、ROTATE算法和COMPOSE算法為推理算法，分別用于求解球面點投影關(guān)系的逆關(guān)系、翻轉(zhuǎn)關(guān)系和復(fù)合關(guān)系。經(jīng)過推理算法可以得到P1關(guān)于P3、P2的投影關(guān)系，P3關(guān)于P1、P2的投影關(guān)系，以及P1關(guān)于P3、P4的投影關(guān)系等未知的投影關(guān)系。

推理算法的共用子算法為CPRP（Computing the projective relations between points），功能為計算球面三點間投影關(guān)系。

下面給出推理算法的主要思想及ADL語言描述。首先作如下說明：球面坐標原點為球心O，球半徑為R。球心O、P2、P3確定平面m：z＝f（x，y），m 與球面的交線為大圈s：x2＋y2＋f2（x，y）＝R2。point［n］元素為隨機球面點。

CPRP算法的主要思想為：

①確定P2、P3的位置關(guān)系，查看屬于PRPS模型的哪種情況，用type標識。

②根據(jù)type的值不同，分別計算P1與P2、P3的球面投影關(guān)系，用r來記錄。

CPRP算法的ADL語言描述：

CPRP（P1，P2，P3.r）／＊P1，P2，P3為球面上三點，r為它們的投影關(guān)系＊／

C1［確定P2，P3的位置關(guān)系］

C2［計算P1與P2，P3的球面投影關(guān)系r］

CONVERSE算法的主要思想為：

①計算投影關(guān)系ri（P1，P2，P3）和ri0（P1，P3，P2）。

②將投影關(guān)系ri0記作投影關(guān)系ri的逆關(guān)系。

CONVERSE算法的ADL語言描述：

CONVERSE（r.r︶）／＊r為球面點投影關(guān)系，r︶為r的逆關(guān)系＊／

ROTATE算法的主要思想及具體實現(xiàn)過程與CONVERSE算法類似。

COMPOSE算法的主要思想為：

① 計 算 ri1（P1，P2，P3），ri2（P2，P3，P4），ri0（P1，P3，P4）。

②將ri0記作ri1和ri2的復(fù)合關(guān)系。

COMPOSE算法的ADL語言描述：

2.3 推理結(jié)果

通過CONVERSE算法和ROTATE算法，得到球面點的投影關(guān)系r（P1，P2，P3）的逆關(guān)系與翻轉(zhuǎn)關(guān)系，其置換關(guān)系如表1所示。

表1 r的置換關(guān)系Table 1 Permutation table for projective relations

下面舉一個具體例子來說明表1。

圖3 in＿a（P1，P2，P3）的逆關(guān)系及翻轉(zhuǎn)關(guān)系Fig.3 Converse and rotation of in＿a（P1，P2，P3）

通過 COMPOSE 算法，得到r1（P1，P2，P3）和r2（P2，P3，P4）的復(fù)合關(guān)系r1?r2（P1，P3，P4），如表2所示。

表2 r1和r2的復(fù)合關(guān)系Table 2 Composition table for projective relations between points

表2中的某些項為imp，是指不存在r1和r2復(fù)合的結(jié)果，以out（P1，P2，P3）?notbt（P2，P3，P4）為例，由前者可知P2等于P3，由后者可知P2在P3、P4較長的弧上，P2一定不等于P3，得到矛盾結(jié)果，因此這種復(fù)合結(jié)果一定不存在。

下面舉一個例子來說明表2。

例2 r1＝ls，r2＝rs，其復(fù)合的結(jié)果是｛rs，ls，notbt｝（P1，P3，P4）。這是因為P2在P3、P4的rs方向，P1在P2、P3的ls方向，當P1處在球面上不同的位置（例如在的上半球面上，且在的下半球面上，在的上半球面且在的上半球面上，在P3、P4所在的弧上）時，P1相對P3、P4的位置關(guān)系則不同。因此，P1關(guān)于P3、P4的投影關(guān)系或是rs或是ls，或是notbt，如圖4所示。

圖4 ls和rs的復(fù)合結(jié)果Fig.4 The composition of ls and rs

2.4 推理性質(zhì)

對推理算法得到的兩個表格進行分析與歸納，可得到如下3個定理。

定理1 ｛in，in｝，｛out，out｝，｛in＿a，in＿a｝，｛out＿a，out＿a｝，｛bt，bt｝，｛notbt，notbt｝，｛ls，rs｝為7組互逆關(guān)系。

證明 由PRPS模型的定義與球面的對稱性可以得到。

定理2 已知投影關(guān)系r1（P1，P2，P3），通過置換運算，可得到P1，P2，P3中任意一點關(guān)于其他兩點的投影關(guān)系。

證明 若已知r1（P1，P2，P3），那么r2（P1，P3，P2）即為r1的逆關(guān)系，r3（P3，P1，P2）為r1的翻轉(zhuǎn)關(guān)系，r4（P3，P2，P1）為r3的逆關(guān)系，r5（P2，P3，P1）為r3的翻轉(zhuǎn)關(guān)系，r6（P2，P1，P3）為r2的翻轉(zhuǎn)關(guān)系，因此經(jīng)過置換運算，由r1（P1，P2，P3）可推出P1，P2，P3之間所有投影關(guān)系，即可推理出－1個投影關(guān)系。

定理3 已知投影關(guān)系r1，r2和r1?r2，其中r1?r2為r1，r2的復(fù)合結(jié)果，則r1?r2所屬的模型情況與r2的情況相同。

證明 r1表示P1關(guān)于P2、P3的投影關(guān)系，所屬的模型根據(jù)P2、P3確定；r2表示P2關(guān)于P3、P4的投影關(guān)系，所屬的模型根據(jù)P3、P4確定；r1?r2表示P1關(guān)于P3、P4的投影關(guān)系，所屬的模型根據(jù)P3、P4確定。因此r1?r2所屬的模型情況與r2的情況相同。

由定理1、2和3分別可得到如下3個推理性質(zhì)。

推理性質(zhì)1 PRPS模型中投影關(guān)系集合｛bt，notbt，rs，ls，in，out，in＿a，out＿a｝中存在互逆關(guān)系。

推理性質(zhì)2 置換運算可推理出三點間的任意投影關(guān)系。

推理性質(zhì)3 復(fù)合結(jié)果具有傳遞性。

給出投影關(guān)系r1（P1，P2，P3）和r2（P2，P3，P4），經(jīng)過復(fù)合運算，可以得到其復(fù)合關(guān)系r1?r2（P1，P3，P4），即得到P1關(guān)于P3、P4的投影關(guān)系，從而將P1、P3和P4間的投影關(guān)系聯(lián)系起來，因此復(fù)合推理起到傳遞的作用，復(fù)合結(jié)果具有一定的規(guī)律可循。

由以上性質(zhì)可以得出如下結(jié)論：PRPS模型中的投影關(guān)系集合元素之間存在一定的互逆關(guān)系；僅通過置換與復(fù)合這兩個運算，就能夠推理出球面點間的全部投影關(guān)系；由于復(fù)合具有規(guī)律性，根據(jù)推理算法得到的結(jié)果符合規(guī)律，即可知推理結(jié)果正確。

2.5 推理應(yīng)用

PRPS模型可以表達球面對象投影關(guān)系，但在某些實際應(yīng)用的情況下，不能提供進一步指導(dǎo)分析或是推論。例如，在航線部署、災(zāi)害預(yù)報中經(jīng)常需要根據(jù)一組或兩組目標關(guān)系，推斷出更多對象間的復(fù)雜關(guān)系，用以指導(dǎo)人類活動，本文的推理算法可以輔助相關(guān)部門進行計劃部署。

本文推理算法還可以應(yīng)用到數(shù)據(jù)庫的查詢中。類似于二元拓撲關(guān)系查詢來說，通常已知物體A與B的關(guān)系，通過推理算法可以得知物體B與A的關(guān)系，而不用再次通過計算獲得兩者關(guān)系。而針對三元物體關(guān)系的查詢來說，應(yīng)用本文的推理算法，通過推理性質(zhì)2和3，得到三者間或更多的物體間的任意投影關(guān)系，避免了重復(fù)計算。這遵循了建立數(shù)據(jù)庫原則：不用計算物體間的所有完備關(guān)系，只需設(shè)定一些必要的關(guān)系作為主要屬性，剩余的關(guān)系可以由這些主要屬性推導(dǎo)得到，從而節(jié)省空間與計算時間。因此，通過前文推理性質(zhì)及定理可以發(fā)現(xiàn)，構(gòu)建投影關(guān)系推理算法是指導(dǎo)實踐的重要基礎(chǔ)。

3 結(jié)束語

針對Clementini建立的PRPS模型僅有表示卻無法推理的問題，本文給出了PRPS的推理算法，在理論上使該模型得到完善，在實際應(yīng)用中可以為進行數(shù)據(jù)庫查詢、處理全球氣候變化以及為數(shù)字地球、飛機導(dǎo)航等做基礎(chǔ)理論。推理算法主要有3個，其中CONVERSE算法和ROTATE算法可以計算出球面任意點的投影關(guān)系的置換關(guān)系，得到置換表。已知一點關(guān)于其他兩點的投影關(guān)系，通過查置換表，可知三點間所有（共6種）投影關(guān)系；用COMPOSE算法可以計算出球面點的復(fù)合關(guān)系，得到8×8項的復(fù)合表，通過查表可以由已知的球面投影關(guān)系推導(dǎo)出未知的投影關(guān)系。并以數(shù)據(jù)庫查詢?yōu)槔f明了推理算法為此模型在實際問題中的應(yīng)用奠定了基礎(chǔ)。本文的主要工作是將球面上物體抽象成點并進行推理。下一步擬將球面上物體抽象成區(qū)域?qū)ο螅砑有螤钚畔ⅲo出針對區(qū)域的球面投影關(guān)系的推理算法。

［1］歐陽繼紅，孫偉，劉大有，等.方向關(guān)系矩陣的復(fù)合［J］.吉林大學(xué)學(xué)報：工學(xué)版，2010，40（4）：1048－1053.Ouyang Ji－h(huán)ong，Sun Wei，Liu Da－you，et al.Com－position of direction relation matrix［J］.Journal of Jilin University（Engineering and Technology Edition），2010，40（4）：1048－1053.

［2］Tobler W.Global spatial analysis［J］.Computers，Environment，and Urban Systems，2002，26：493－500.

［3］歐陽繼紅，霍林林，劉大有，等.能表達帶洞區(qū)域拓撲關(guān)系的擴展9－交集模型［J］.吉林大學(xué)學(xué)報：工學(xué)版，2009，39（6）：1595－1600.Ouyang Ji－h(huán)ong，Huo Lin－lin，Liu Da－you，et al.Extended 9－intersection model for description of topological relations between regions with holes［J］.Journal of Jilin University（Engineering and Technology Edition），2009，39（6）：1595－1600.

［4］Egenhofer M J.Spherical topological relations［J］.Journal on Data Semantics III，2005，2：25－49.

［5］Clementini Eliseoc，Billen Roland.Modeling and computing ternary projective relations between regions［J］.IEEE Transactions on Knowledge and Data Engineering，2006，18（6）：799－814.

［6］Clementini Eliseo，Skiadopoulos Spiros，Roland Billen，et al.A reasoning system of ternary projective relations［J］.IEEE Transactions on Knowledge and Data Engineering，2010，22（2）：161－178.

［7］Clementini Eliseo.Projective relations on the sphere［C］∥Proc Second Int＇1Workshop Semantic and Conceptual Issues in GIS（SeCoGIS＇08）.Berlin Heidelberg：Springer－Verlag，2008.