### Paper Menu >>

### Journal Menu >>

Journal of Software Engineering and Applications, 2011, 4, 191-194 doi:10.4236/jsea.2011.43022 Published Online March 2011 (http://www.SciRP.org/journal/jsea) Copyright © 2011 SciRes. JSEA 191 A Model of Representing Extension and Shrinking for Spatial Relations Shan Zhong1, Junpeng Wan2 1School of Computer Science and Engineering, Changshu Institute of Technology, Changshu, China; 2School of Computer Science and Telecommunication Engineering, Jiangsu University, Zhenjiang, China. Email: sunshine-620@163.com, ccecwan@163.com Received March 8th, 2011; revised March 16th, 2011; accepted March 18th, 2011. ABSTRACT Aiming at region connection calculus (RCC) can only roughly represent spatial topological relations, and have diffi- culty in representin g the distance, direction and so on. Therefore, based on RCC theory, Region Extension and Shrink- ing Calculus are proposed, and then a formalized metrization method using region as a basic unit is introduced. Based on RESC theory, taking the advantage su ch as applica tion simplicity and easy realization of g ird area method. The ex- periment proves the spatial relations can be easily obtained by Grid-Region method, and it is an effective way to repre- sent spatial relations. Keywords: RCC, Spatial Extension, Qualitative, Topolog ical 1. Introduction SR [1] (Spatial Reasoning) is an important subfield of AI (Artificial Intelligence), usually us ing the technology and method of AI to model, describe and represent about the spatial objects. Research in SR is motivated by a wide variety of possible application areas including GIS (Geo- graphic Information System), robotic navigation, and high level vision, spatial propositional semantics of natural languages, engineering design, and common-sense reas o n - ing about physical systems. The qualitative spatial relation s mainly include topolo- gical, direction and distance relations. The topological re- lation is the most important basic relation of spatial rela- tion. The model can be divided to region topology and point set topology. The direction relation describes the sequence relation among spatial relations, and its main describing methods are based on cone and projection. The distance relation is some metrization relation among spatial objects. Clementine d ivided the distance to differ- ent layers such as near, middle and far layers, and com- bing the cone direction model and distance relation, then introduced position calculus method. Spatial reasoning usually needs to combine various spatial relations, but still so far no unified model can for- mally describes the topological, directional and the dis- tance spatial relations based on the same theory. Based on solving the above problems, a new model named ESFR for region extension and shrinking is pro- posed. The model takes advantage of the novel metriza- tion method to define the topological, directional and the distance relation. And at the meantime, based on the pro- perties of easily realization of the grid area method, it is used to verify the formal model of spatial relations based on spatial region extension and shrinking. 2. Region Extension and Shrinking In order to unify the spatial topological, qualitative dis- tance relation and qualitative direction relation, the spa- tial representing model is constructed. So the notion of extension and shrinking of region is defined. The notion of Region ex tension and shrinking is based on sum of region (namely sum region). Now, there are a lot of forms of region [2,4]. Tiansi [5] introduced how to recognize a spatial environment when the spatial rela- tions are changed . The literature [2] defined the sum of x and y: ,,,, s umxyz wCwzCwxCwy (1) To generalize the definition, the region x and y are modified to the sum of some region satisfied with some condition, the definition of the modified sum region is defined as follows: ,,sumxywC wyvvC wv (2) A Model of Representing Extension and Shrinking for Spatial Relations Copyright © 2011 SciRes. JSEA 192 Especially, for the region A and E, if the predicate x equals ,,CGxECA x, in which ,CGx E repre- sents x equals E, and then the region satisfied with the predicate is: ,,, ,,,sumCGxEC AxywCwyvCGvEC AxCwv (3) If the predicate x equals ,, P EXx EA, and P is the partial relations of RCC-8, then the sum region satis- fied predicate is: ,,,,, ,sumPEXxEAywCwyvPEXvEACw v (4) 2.1. Region Extension Given the region A and E, then the extending region from A to E is the sum region satisfied predicate ,,CGx ECA x, namely, ,EXA E, and ,,,EXA EsumCGx ECA x, in which A is the base region, E is the metrization region of A. A is extended by n from A, denoted by ,EXA E, namely, ,,,, n EXA EEXEXEXA EEE (5) 0,EXA EA (6) 2.2. Region Shrinking Given the region A and E, then the shrinking region from A to E is the sum region satisfied the predicate ,, P EXxEA, namely, ,SHRA E, namely, ,,,SHRA EsumPEXx EA, A is the base re- gion, E is the metrization region. A is shrinking from A for n times shrinking, namely , n SHRAE. ,,,, n SHRA ESHRSHRSHRA EEE (7) 0,SHRAEA (8) When A and B are fixed, the max value of n in , n SHRAE can be denoted as _ , m SHRMaxA E, which is the center of A, or the centre region. Using the region as the spatial primitive, C(x,y) and congruence relation CG(x,y) as the original spatial rela- tion, and adding the metrization function of region ex- tension, the spatial relations such as topology, distance, direction, position and move can be formalized. 3. Spatial Relation 3.1. Topology Relation In the model of topology of RCC-8, DC(x, y) represents x is apart from y. In the application, the apart degree should be considered. Therefore, based on the region extension, DC can be separated to,nE DC . Definition 5 Apart degree. Given the region A and B, if there exits a region E and the positive integer n, A is not connected to B thr ough E by n-1 times extensio n, but A is connected to B thro ugh E by n times extension, then the apart agree of A and B can be represented as ,, nE DCA B, namely, shown as the Equation (9): , 1 , ,,,,, nE nn DCA B nEDC EXAEBC EXAEB (9) The predicate ,, nE DCA B is known as “The apart degree between A and B is n*E”. The Figure 1 can be represented the apart degree of A and B is n*E, the sur- round region of A represented by the n times extension using as n dashed circle. According the definition 2, the Equation (10) can be obtained: ,, ,, nE nE DCA BDCBA (10) The predicate of ,, nE DCA B represented the apart degree of A and B is measured by n and E, and the gra- nularity of metrization is depended on E. When E is con- firmed, the bigger is the variable of n, and the bigger is the apart degree. 3.2. Direction Relation A and B is two regions, A. East, A. South, A. West and A. North is fo ur borde rl ine s o f the region o f region A . 1, , ,,.,, .,, nS nS EastABnSSSCETTA EastSBCETTA EastSB (11) The other direction relations can be defined as West (A,B), South( A, B ), North(A,B), etc. 1, , 1, , 1, , ,,.,, .,, ,,.,, .,, ,,.,,.,, nS nS nS nS nS nS WestABnSSSCETTAWest SBCETTAWest SB SouthA BnSSSCETTASouth SBCETTASouth SB NorthABnSSSCETTANorthSBCETTANorth SB (12) A Model of Representing Extension and Shrinking for Spatial Relations Copyright © 2011 SciRes. JSEA 193 Figure 1. Apart degree. For example, when the region calculus is got on the object B, and the extending region ,ETTB S from B is firstly intersection with A. East, so we say the object B is in the east of object A is shown as East(B,A), and the Figure 2 is showed as follows: 4. Grid Region Method Grid region method has th e properties of easy application and realization. If some part of A accounts for some grid, then all the grids accounting the region can be represen- ted as the predicate S(A). The grid region is extended based on the RESC theory, using the grid unit as the me- trization region, and the metrization region can be ex- tended as Figure 3. The algorism for grid region extension is as follows: 1) Choose the region need to be extended 2) Read the region grid coordinate of the selective re- gion 3) According to the mark of the read grid unit, justify whether the grid unit is the outer grid unit, if it is the outer grid unit, then executing (4). If it not the outer grid unit, then execute (5). 4) Extension according to the coordinate obtained from (3). Firstly, fetch three grid units such as the top left, top, top right corners, and justify whether the mark is the free grid unit. If it is the free grid unit, change the value of the mark (the counts of the extension). After that, fetch the right bottom corner, bottom and the left bottom corners to do the same justify. Finally, fetch the left and right grid unit to do the same justify. After the justifica- tion is finished, execute (3). 5) Go on read the grid coordinate of the next region, execute (3). 5. Application Instance Based on the introduction of the above RESC, grid re- gion method realizes qualitative spatial representing sys- tem. Figure 2. Direction representing. Figure 3. Grid region extension. Figure 4. Application instance. The system has three modules such as topology rela- tion reasoning module, direction relation module, dis- tance relation module. The space is firstly grid, then giv- en the region 1 and 2, and the given region is grid, the grid unit is as the extending region to extend the region S(1), according RESC theory, the topology relation of S(1) and S(2) is shown as apart (DC), and the apart de- gree is 3 grid degree, direction relation is S(2) is in the north of S(1), the distance relation is the absolute dis- tance between A and B is 3 grid unit distance, namely, the distance relation is 3,1, 2 s Dist ,in which S is the grid unit, the distance between them is 3 grid unit, the direction relation is South(1,2),namely, the region 2 is in the south of the region 1, which is showed as Figure 4. A Model of Representing Extension and Shrinking for Spatial Relations Copyright © 2011 SciRes. JSEA 194 REFERENCES [1] TBITTNER, B. Smith, “Granular Spatio-Temporal On- tologies,” AAA I Spring Symposium on, Foundations and Applications of Spatio-Temporal Reasoning (FASTR), AAA I Press, MenloPark, 2003, pp. 12217. [2] D. Randell, Z. Cui and A. G. Cohn, “A Spatial Logic Based on Regions and Connection,” Proceedings of the 3rd International Conference on Knowledge Representa- tion and Reasoning, Morgan Kaufmann, 1992, pp. 165-176. [3] A. G. Cohn, B. Bennett, J. Gooday and N. M. Gotts, “Qualitative Spatial Representation and Reasoning with the Region Connection Calculus,” GeoInformatica, Vol. 1, No. 1, 1997. pp. 1- 44. [4] T. S. Dong, “SNAPVis and SPANVis: Ontologies for Re- cognizing Variable Vista Spatial Environments,” In Christian Freksa, et al. Eds., Spatial Cognition IV, LNAI 3343, Springer-Verlag, Berlin Heidelberg, 2005, pp. 344-365 [5] B. Bennett, A. G. Cohn, P. Torrini and S. M. Hazarika, “A Foundation for Region-Based Qualitative Geometry,” Proceedings of the 14th European Conference on AI (ECAI-2000), IOS Press, Berlin, 2000, pp. 204-208. |