王立君,富 倩

(1. 長春工業(yè)大學(xué) 信息傳播工程學(xué)院,長春 130012;2. 吉林大學(xué) 地球科學(xué)學(xué)院,長春 130061)

空間推理[1]就是運(yùn)用空間理論與人工智能技術(shù)和方法對空間對象進(jìn)行建模、 描述和表示,并對其空間關(guān)系進(jìn)行分析和處理的過程. 它在地理信息系統(tǒng)(GIS)、 圖形圖像處理、 模式識別、 機(jī)器人導(dǎo)航和空間數(shù)據(jù)庫等領(lǐng)域應(yīng)用廣泛[2-3]. 空間關(guān)系模型研究是空間推理的基本內(nèi)容,其中大多數(shù)為拓?fù)潢P(guān)系模型研究[4-8]. 現(xiàn)有空間拓?fù)潢P(guān)系模型大多數(shù)針對簡單對象和確定性對象,對于現(xiàn)實(shí)世界中普遍存在的復(fù)雜對象及不確定性對象的處理能力較弱. 本文針對二維空間中的平面區(qū)域,基于空間拓?fù)潢P(guān)系模型中經(jīng)典的區(qū)域連接演算(RCC)理論,提出一種凹形區(qū)域和寬邊界區(qū)域間的拓?fù)潢P(guān)系表示模型,能對復(fù)雜對象和不確定性對象中較簡單情況進(jìn)行有效處理.

1 凹形區(qū)域

定義1[9]取平面區(qū)域P中任意兩點(diǎn)做連線,若連線上的任意點(diǎn)總在區(qū)域P中,則稱P為凸形區(qū)域.

定義2[9]取平面區(qū)域P中任意兩點(diǎn)做連線,若連線上存在某一點(diǎn)不在區(qū)域P中,則稱P為凹形區(qū)域.

定義3[4]平面內(nèi)包含區(qū)域P的最小凸形區(qū)域,稱為P的凸殼,記為Pch.

定義4[4]凹形區(qū)域P的凸殼與P自身做差得到的部分,稱為P的內(nèi)側(cè),記為Pi.

如圖1所示,Pi為凹形區(qū)域P的內(nèi)側(cè),P∪Pi即為P的凸殼.

2 寬邊界區(qū)域

寬邊界區(qū)域[10-12]是一種用于處理不確定性對象的表示方法. 寬邊界區(qū)域通常由內(nèi)、 外區(qū)域組成,內(nèi)區(qū)域表示寬邊界一定存在的范圍,外區(qū)域表示寬邊界可能存在的范圍. 內(nèi)、 外區(qū)域之差即為寬邊界,它具有一定的寬度和面積.

定義5令A(yù)為寬邊界區(qū)域,由兩個(gè)簡單區(qū)域A1和A2組成,且滿足A1?A2,則A1稱為A的內(nèi)區(qū)域,A2稱為A的外區(qū)域,內(nèi)、 外區(qū)域之差即為A的寬邊界,記為ΔA=A2-A1.

如圖2所示,A為寬邊界區(qū)域,A1,A2分別為A的內(nèi)、 外區(qū)域,ΔA為A的寬邊界.

圖1 Pi為凹形區(qū)域P的內(nèi)側(cè)Fig.1 Pi inside concave region P

圖2 寬邊界區(qū)域A及其各組成部分Fig.2 Broad boundary region A and its composite parts

3 凹形區(qū)域和寬邊界區(qū)域的拓?fù)潢P(guān)系表示模型

3.1 空間區(qū)域劃分 令X,Y分別為二維空間中的凹形區(qū)域和寬邊界區(qū)域,考慮X,Y的4個(gè)組成部分,即X的內(nèi)側(cè)、X自身和Y的內(nèi)、 外區(qū)域,分別記為Xi,X,Y1,Y2,如圖3所示.

圖3 凹形區(qū)域X和寬邊界區(qū)域Y的空間劃分Fig.3 Space partitions of concave region X and broad boundary region Y

令X為凹形區(qū)域,Y為簡單寬邊界區(qū)域,則X,Y間的拓?fù)潢P(guān)系可通過考慮各子部分間的相交情況進(jìn)行描述,形式化表示為如下的4×4交集矩陣：

若每項(xiàng)的交集非空,則取值為1；否則,若每項(xiàng)的交集為空,則取值為0. 取遍所有不同的0/1組合,共有216個(gè)不同的矩陣. 考慮到現(xiàn)實(shí)世界中的空間對象,216個(gè)矩陣中包含了許多實(shí)際不存在的情況. 為了去掉這些實(shí)際不存在的拓?fù)潢P(guān)系,下面將給出拓?fù)潢P(guān)系生成的約束條件.

3.3 拓?fù)潢P(guān)系生成的約束條件 下面給出3個(gè)約束條件,用于得到凹形區(qū)域和簡單寬邊界區(qū)域間所有實(shí)際存在的拓?fù)潢P(guān)系.

約束條件1對于凹形區(qū)域X和簡單寬邊界區(qū)域Y的4個(gè)部分Xi,X,Y1,Y2,每部分的外部必相交,即XOO∩YOO= 1.

因?yàn)閄i,X,Y1,Y2的外部均為無限區(qū)域,而無限區(qū)域之間交集必非空,因而約束條件1合理.

由定義4可知,凹形區(qū)域的內(nèi)部與其內(nèi)側(cè)的內(nèi)部必不相交,凹形區(qū)域的外部與其內(nèi)側(cè)的內(nèi)部必相交,凹形區(qū)域的內(nèi)部與其內(nèi)側(cè)的外部必相交,因而約束條件2合理.

由定義5可知,簡單寬邊界區(qū)域的內(nèi)、 外區(qū)域,它們的內(nèi)部必相交,內(nèi)區(qū)域的內(nèi)部和外區(qū)域的外部必不相交,內(nèi)區(qū)域的外部和外區(qū)域的內(nèi)部必相交,從而約束條件3合理.

3.4 拓?fù)潢P(guān)系表示 根據(jù)上述3個(gè)約束條件,從216個(gè)不同矩陣中刪掉二維平面中實(shí)際不存在的情況,最終得到凹形區(qū)域和簡單寬邊界區(qū)域間的67種拓?fù)潢P(guān)系,并給出每種關(guān)系對應(yīng)的示意圖,如圖4所示.

綜上所述， 本文針對空間中一類較簡單的復(fù)雜區(qū)域和不確定區(qū)域， 基于交集矩陣表示方法， 提出了一種凹形區(qū)域和簡單寬邊界區(qū)域間的拓?fù)潢P(guān)系表示模型， 給出了約束條件， 通過去掉二維平面中所有不可實(shí)現(xiàn)的情況， 最終得到實(shí)際存在的67種拓?fù)潢P(guān)系， 并給出了其拓?fù)潢P(guān)系示意圖. 該模型可用于空間查詢等應(yīng)用領(lǐng)域， 在一定程度上增強(qiáng)了對復(fù)雜區(qū)域和不確定區(qū)域的處理能力.

[1] Cohn A G,Hazarika S M. Qualitative Spatial Representation and Reasoning: An Overview [J]. Fundamental Informatics,2001,46(1/2): 1-29.

[2] LIU Ya-bin,LIU Da-you. A Review on Spatial Reasoning and Geographic Information System [J]. Journal of Software,2000,11(12): 1598-1606. (劉亞彬,劉大有. 空間推理與地理信息系統(tǒng)綜述 [J]. 軟件學(xué)報(bào),2000,11(12): 1598-1606.)

[3] LIU Da-you,HU He,WANG Sheng-sheng,et al. Research Progress in Spatio-Temporal Reasoning [J]. Journal of Software,2004,15(8): 1141-1149. (劉大有,胡鶴,王生生,等. 時(shí)空推理研究進(jìn)展 [J]. 軟件學(xué)報(bào),2004,15(8): 1141-1149.)

[4] Clementini E,Billen R. Modeling and Computing Ternary Projective Relations between Regions [J]. IEEE Transactions on Knowledge and Data Engineering,2006,18(6): 799-814.

[5] Roussopoulos N,Faloutsos C,Sellis T. An Efficient Pictorial Database System for PSQL [J]. IEEE Transactions on Software Engineering,1988,14(5): 639-650.

[6] Cohn A G,Bennett B,Gooday J,et al. Qualitative Spatial Representation and Reasoning with the Region Connection Calculus [J]. GeoInformatica,1997,1(3): 275-316.

[7] LI San-jiang. A Complete Classification of Topological Relations Using the 9-Intersection Method [J]. International Journal of Geographical Information Science,2006,20(6): 589-610.

[8] Roy A J,Stell J G. Spatial Relations between Indeterminate Regions [J]. International Journal of Approximate Reasoning,2001,27(3): 205-234.

[9] Egenhofer M J,Vasardani M. Spatial Reasoning with a Hole [C]//Conference on Spatial Information Theory (COSIT-07). Berlin: Springer,2007: 303-320.

[10] 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.)

[11] OUYANG Ji-hong,FU Qian,LIU Da-you. A Model for Representing Topological Relations between Simple Concave Regions [J]. Journal of Jilin University: Science Edition,2007,45(3): 427-431. (歐陽繼紅,富倩,劉大有. 一種簡單凹形區(qū)域間拓?fù)潢P(guān)系的表示模型 [J]. 吉林大學(xué)學(xué)報(bào): 理學(xué)版,2007,45(3): 427-431.)

[12] Clementini E,DiFelice P. An Algebraic Model for Spatial Objects with Indeterminate Boundaries [C]//Geographic Objects with Indeterminate Boundaries. London: Taylor &Francis,1996: 155-169.