一類帶單洞區(qū)域與兩個(gè)簡單區(qū)域間拓?fù)潢P(guān)系的表示

李 健，廖夢蘭，溫長吉

(吉林農(nóng)業(yè)大學(xué)信息技術(shù)學(xué)院，長春130118)

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

本文建立了帶單洞區(qū)域與兩個(gè)簡單區(qū)域間拓?fù)潢P(guān)系的表示模型，基于RCC5定義了擴(kuò)展4-交矩陣，進(jìn)而給出12-交集模型，并給出了帶單洞區(qū)域與兩個(gè)簡單區(qū)域間的161種拓?fù)潢P(guān)系圖和概念鄰域圖.

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

1.1 擴(kuò)展4-交集矩陣

通過考察擴(kuò)展4-交集矩陣中每個(gè)位置集合的空與非空描述RCC5關(guān)系，RCC5關(guān)系集的矩陣表示列于表1.

表1 RCC5關(guān)系集的矩陣表示Table 1 Matrix representation of RCC5 relations

1.2 12-交集模型

擴(kuò)展4-交集矩陣只能表示兩個(gè)區(qū)域間的拓?fù)潢P(guān)系，對兩個(gè)以上區(qū)域間的拓?fù)潢P(guān)系無法表示.為此，基于擴(kuò)展4-交集模型，本文給出了可以對帶單洞區(qū)域與兩個(gè)簡單區(qū)域間拓?fù)潢P(guān)系進(jìn)行表示的12-交集模型.

定義1 取圓A內(nèi)部一個(gè)圓B，將圓B稱為圓A的洞，如圖1所示.

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

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

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

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

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

因此，無論簡單區(qū)域C和簡單區(qū)域D的位置如何變動，區(qū)域A和區(qū)域B間的拓?fù)潢P(guān)系不影響區(qū)分模型表示.

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

對于任意的帶單洞區(qū)域與兩個(gè)簡單區(qū)域，本文可用上述12-交集矩陣表示它們之間的拓?fù)潢P(guān)系，即每個(gè)12-交集矩陣都對應(yīng)一個(gè)A，B，C，D之間的拓?fù)潢P(guān)系，如圖3所示.

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

圖3 對應(yīng)實(shí)例Fig.3 Corresponding example

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

約束條件1 一個(gè)12-交集矩陣能對應(yīng)一個(gè)可實(shí)現(xiàn)的6組拓?fù)潢P(guān)系，必須滿足所有的兩兩關(guān)系屬于RCC5關(guān)系集.

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

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

即0-1矩陣應(yīng)滿足:

2 帶單洞區(qū)域與兩個(gè)簡單區(qū)域間拓?fù)潢P(guān)系的算法及表示

算法的基本思想如下:

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

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

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

根據(jù)該算法，可得到161種12-交集矩陣，經(jīng)驗(yàn)證這161個(gè)12-交集矩陣都能唯一對應(yīng)一個(gè)可實(shí)現(xiàn)的帶單洞區(qū)域與兩個(gè)簡單區(qū)域間的拓?fù)潢P(guān)系，這161種拓?fù)潢P(guān)系如圖4所示.

定理1 所有由12-交集模型給出的帶單洞區(qū)域與兩個(gè)簡單區(qū)域間可實(shí)現(xiàn)的161種拓?fù)潢P(guān)系是兩兩互斥且完備的.

證明:因?yàn)橛?2-交集模型給出的帶單洞區(qū)域與兩個(gè)簡單區(qū)域間的212種拓?fù)潢P(guān)系(包括可實(shí)現(xiàn)的和不可實(shí)現(xiàn)的)是兩兩互斥且完備的，所以只需說明其中可實(shí)現(xiàn)的拓?fù)潢P(guān)系有且僅有161種.約束條件1和約束條件2是拓?fù)潢P(guān)系可實(shí)現(xiàn)的必要條件，通過這兩個(gè)約束可得到161種可能實(shí)現(xiàn)的拓?fù)潢P(guān)系，而圖4表明可以對這161種拓?fù)潢P(guān)系找到相應(yīng)的具體情形實(shí)現(xiàn)，因此單洞區(qū)域與兩個(gè)簡單區(qū)域間可實(shí)現(xiàn)的拓?fù)潢P(guān)系有161種，而且是兩兩互斥且完備的.

圖4 161種可實(shí)現(xiàn)的拓?fù)潢P(guān)系Fig.4 161 topological relations and their schematics

綜上所述，本文基于RCC5，定義了擴(kuò)展4-交集矩陣，進(jìn)而給出12-交集模型，對帶單洞區(qū)域與兩個(gè)簡單區(qū)域間的拓?fù)潢P(guān)系進(jìn)行了表示，并給出了帶單洞區(qū)域與兩個(gè)簡單區(qū)域間161種拓?fù)潢P(guān)系的示意圖.

［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，F(xiàn)U 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.(歐陽繼紅，霍琳琳，劉大有，等.能表達(dá)帶洞區(qū)域拓?fù)潢P(guān)系的擴(kuò)展9-交集模型［J］.吉林大學(xué)學(xué)報(bào):工學(xué)版，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.(郭濼，杜世宏，王橋.基于方向關(guān)系的不確定區(qū)域拓?fù)潢P(guān)系推理［J］.北京大學(xué)學(xué)報(bào):自然科學(xué)版，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.