一類帶單洞區域與兩個簡單區域間拓撲關系的表示

李 健，廖夢蘭，溫長吉

(吉林農業大學信息技術學院，長春130118)

空間推理［1-2］在地理信息系統(GIS)［3］、圖像數據庫、模式識別、機器人導航、高級視覺、自然語言理解、工程設計、物理位置的常識推理、空間數據庫［4］等方面應用廣泛.目前，人們已提出了一些基本模型，如9-交模型［5］、D9-交集模型［6］、區域連接演算［7］和區域間拓撲關系的層次表達法［8］等，這些模型主要用于描述兩個區域間的拓撲關系，即僅包含簡單區域或僅包含非簡單區域，而對于多個區域間(即同時包含簡單區域與非簡單區域)拓撲關系的研究較少，但實際應用中很多時候需要同時考慮多個區域間的相互關系，因而建立適用于多個區域間拓撲關系的模型十分必要.

本文建立了帶單洞區域與兩個簡單區域間拓撲關系的表示模型，基于RCC5定義了擴展4-交矩陣，進而給出12-交集模型，并給出了帶單洞區域與兩個簡單區域間的161種拓撲關系圖和概念鄰域圖.

1 擴展4-交集矩陣、12-交集模型及帶單洞區域與兩個簡單區域間的約束條件

1.1 擴展4-交集矩陣

通過考察擴展4-交集矩陣中每個位置集合的空與非空描述RCC5關系，RCC5關系集的矩陣表示列于表1.

表1 RCC5關系集的矩陣表示Table 1 Matrix representation of RCC5 relations

1.2 12-交集模型

擴展4-交集矩陣只能表示兩個區域間的拓撲關系，對兩個以上區域間的拓撲關系無法表示.為此，基于擴展4-交集模型，本文給出了可以對帶單洞區域與兩個簡單區域間拓撲關系進行表示的12-交集模型.

定義1 取圓A內部一個圓B，將圓B稱為圓A的洞，如圖1所示.

定義2 若有區域A包含簡單區域B，即滿足RCC5關系集中的PPI(A，B)，同時簡單區域C與簡單區域D相離，即滿足RCC5關系集中的DR(C，D)，則稱區域A，B，C，D共同構成一類帶單洞區域與兩簡單區域，如圖2所示.

圖1 一個簡單的帶洞區域Fig.1 A simple region with a hole

圖2 帶單洞區域與兩簡單區域Fig.2 A simple region with a hole and two simple regions

對擴展4-交集矩陣進行進一步擴展，可得到16-交集模型［9］.對16-交集模型進行研究表明，在16-交集矩陣中有些位置的元素是確定的.對于本文的帶單洞區域與兩簡單區域，區域A與區域B的拓撲關系為PPI(A，B)，即如下等式成立:

由于A1∩B0=0，所以其再與其他的任一部分取交集，其結果也必然為0，因此在16-交集矩陣中如下等式確定:

因此，無論簡單區域C和簡單區域D的位置如何變動，區域A和區域B間的拓撲關系不影響區分模型表示.

根據上述分析，可將16-交集模型進行改進，進而得到如下12-交集矩陣:

對于任意的帶單洞區域與兩個簡單區域，本文可用上述12-交集矩陣表示它們之間的拓撲關系，即每個12-交集矩陣都對應一個A，B，C，D之間的拓撲關系，如圖3所示.

1.3 帶單洞區域與兩個簡單區域間的約束條件

圖3 對應實例Fig.3 Corresponding example

為了得到所有可實現的12-交集矩陣，本文對帶單洞區域與兩個簡單區域進行進一步研究，給出如下3個約束條件.

約束條件1 一個12-交集矩陣能對應一個可實現的6組拓撲關系，必須滿足所有的兩兩關系屬于RCC5關系集.

約束條件2 對于簡單區域有界區域，必須滿足A1∩B1∩C1∩D1非空，即M1111=1.

約束條件3 由于帶單洞區域與兩個簡單區域間的4個部分A，B，C，D，有簡單區域C與簡單區域D相離，所以可得如下表達式:

即0-1矩陣應滿足:

2 帶單洞區域與兩個簡單區域間拓撲關系的算法及表示

算法的基本思想如下:

1)每個12-交集矩陣以(a1，a2，…，a12)的行向量形式給出，先生成理論上的212種12-交集矩陣，即生成一個由212個行向量構成的矩陣A;

2)依次掃描A的每行，標記矩陣A中所有滿足約束條件的行向量;

3)將矩陣A中所有滿足條件的行向量保存到矩陣B中，并輸出，其結果即為所求.

根據該算法，可得到161種12-交集矩陣，經驗證這161個12-交集矩陣都能唯一對應一個可實現的帶單洞區域與兩個簡單區域間的拓撲關系，這161種拓撲關系如圖4所示.

定理1 所有由12-交集模型給出的帶單洞區域與兩個簡單區域間可實現的161種拓撲關系是兩兩互斥且完備的.

證明:因為由12-交集模型給出的帶單洞區域與兩個簡單區域間的212種拓撲關系(包括可實現的和不可實現的)是兩兩互斥且完備的，所以只需說明其中可實現的拓撲關系有且僅有161種.約束條件1和約束條件2是拓撲關系可實現的必要條件，通過這兩個約束可得到161種可能實現的拓撲關系，而圖4表明可以對這161種拓撲關系找到相應的具體情形實現，因此單洞區域與兩個簡單區域間可實現的拓撲關系有161種，而且是兩兩互斥且完備的.

圖4 161種可實現的拓撲關系Fig.4 161 topological relations and their schematics

綜上所述，本文基于RCC5，定義了擴展4-交集矩陣，進而給出12-交集模型，對帶單洞區域與兩個簡單區域間的拓撲關系進行了表示，并給出了帶單洞區域與兩個簡單區域間161種拓撲關系的示意圖.

［1］WANG Sheng-sheng，LIU Da-you.Knowledge Representation and Reasoning for Qualitative Spatial Change［J］.Knowledge-Based Systems，2012，30:161-171.

［2］WANG Sheng-sheng，LIU Da-you.An Efficient Method for Calculating Qualitative Spatial Relations［J］.Chinese Journal of Electronics，2009，18(1):42-46.

［3］Scott J，Lee L H，Arends J，et al.Designing the Low-Power M*CORE Architecture［C］//IEEE Power Driven Microarchitecture Workshop.Haifa，Israel:IEEE Computer Society，1998:29-33.

［4］LI San-jiang，YING Ming-sheng.Region Connection Calculus:Its Models and Composition Table［J］.Artif Intell，2003，145(1/2):121-146.

［5］CHANG Ning-san，FU King-sun.Query by Pictorial Example［C］//IEEE Transactions on Software Engineering.Piscataway:IEEE Press，1980:519-524.

［6］OUYANG Ji-hong，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.(歐陽繼紅，霍琳琳，劉大有，等.能表達帶洞區域拓撲關系的擴展9-交集模型［J］.吉林大學學報:工學版，2009，39(6):1595-1600.)

［7］GUO Luo，DU Shi-hong，WANG Qiao.Deriving Topological Relations between Uncertain Regions from Direction Relations［J］.Acta Scientiarum Naturalium Universitatis Pekinensis，2009，45(2):339-349.(郭濼，杜世宏，王橋.基于方向關系的不確定區域拓撲關系推理［J］.北京大學學報:自然科學版，2009，45(2):339-349.)

［8］Clarke B L.A Calculus of Individuals Based on“Connection”［J］.Notre Dame Journal of Formal Logic，1981，22(3):204-218.

［9］LI Jian，OUYANG Ji-hong，WANG Zhen-xin.Representation for Topological Relations of Four Simple Regions［C］//The 2012 9th International Conference on Fuzzy Systems and Knowledge Discovery(FSKD’12).Piscataway:IEEE Press，2012:2961-2965.