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

李 健，廖夢蘭，溫長吉

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

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

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

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

1.1 擴展4-交集矩陣

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

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

1.2 12-交集模型

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

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

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

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

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

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

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

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

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

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

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

圖3 對應實例Fig.3 Corresponding example

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

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

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

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

即0-1矩陣應滿足:

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

算法的基本思想如下:

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

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

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

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

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

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

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

綜上所述，本文基于RCC5，定義了擴展4-交集矩陣，進而給出12-交集模型，對帶單洞區(qū)域與兩個簡單區(qū)域間的拓撲關系進行了表示，并給出了帶單洞區(qū)域與兩個簡單區(qū)域間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.(歐陽繼紅，霍琳琳，劉大有，等.能表達帶洞區(qū)域拓撲關系的擴展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.(郭濼，杜世宏，王橋.基于方向關系的不確定區(qū)域拓撲關系推理［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.