Qualitative Representation of Moving Entities

Get Complete Project Material File(s) Now! »

Qualitative Orientation Relations

Qualitative orientation relations describe how two spatial entities are placed one relative to the other. They can be defined in terms of three basic concepts: the primary object, reference object and frame of reference (Clementini et al. 1997). Orientation relations are important complementary qualitative relations because topological relations alone are insufficient in many situations as they cannot encompass all the semantics of a given spatial configuration.
Orientation relations can be defined as absolute orientations (e.g., cardinal) or relative orientations. By applying directional abstractions (e.g., North, Northeast, East, Southeast, South, Southwest, West, and Northwest), Frank (1991, 1992) divides the 2D space around a reference object into cone-shaped areas (Figure I.2a) or 4 partitions using a projection-based approach (Figure I.2b). Moreover a neutral zone, which is an area around the reference object where no direction is defined, can be added to divide the neighboring space into 9 areas (Figure I.2c). Then Frank (1996) compared the three representations and showed that the projection-based representation with a neutral zone was more efficient than the others in terms of spatial reasoning capabilities. Similar to the projection-based approach with a neutral zone, the direction-relation matrix (Goyal and Egenhofer, 2001) approximates the reference object by its minimum bounding rectangle and defines 9 regions around it. A 3×3 matrix (Equation I.3) is used to calculate the intersection of the primary region with the 9 regions.

Conceptual Neighbourhoods

Under the assumption of continuous change, the term of conceptual neighbourhood is defined as: “A set of relations between pairs of events forms a conceptual neighbourhood if its elements are path-connected through conceptual neighbor relations” (Freksa 1992a). A Conceptual neighborhood diagram (CND), whose alternative names are conceptual neighbourhood graphs, transition graphs, and continuity network, is a diagram in which spatial or temporal relations (or potentially any set of concepts in a certain domain) are “networked” according to their conceptual closeness, like the one shown in Figure I.9 for the set of RCC8 relations between regions. Each node corresponds to a relation and each link connects a pair of conceptual neighbors in a CND. If one relation holds at a particular time, then there are some continuous changes possible to lead to another relation in its neighborhood. All the intermediate relations must be passed through while changing from any relation to another one in the CND. Taking the quantity space {−, 0, +} as an example, a variable cannot transit from ‘+’ to ‘−’ without passing through the intermediate value 0. Research on qualitative spatial and temporal reasoning often considers the construction and utilization of various kinds of CNDs. Most of the qualitative spatial and temporal calculi introduced in this chapter have also derived CNDs. To the best of our knowledge, the FROB program introduced in (Forbus 1982) was the first program to use a transition graph that combines spatial continuity constraints with dynamic constraints for reasoning about the movement of point objects in space. A well-known CND is the one applied by Freksa (1991) to interval relations as defined in (Allen 1983). Further examples of conceptual neighborhood diagrams applied to spatio-temporal relations have been applied to cyclic temporal interval relations (Hornsby et al. 1999), topological relations between regions (Egenhofer and Al-Taha 1992), lines and regions (Egenhofer and Mark 1995), and directed lines (Kurata and Egenhofer 2006).
The novel knowledge that can be derived from conceptual neighbourhoods of some given JEPD relations can be used to evaluate the possible changes of a relation or to measure the similarity among some relations (Schwering 2007). CNDs have also been applied to build a qualitative spatial simulator (Cui et al. 1992) and to movement-based reasoning (Egenhofer and Al-Taha 1992; Rajagopalan 1994; Van de Weghe 2004; Noyon et al. 2007; Glez-Cabrera et al. 2013).

Qualitative Movement Modelling

Instead of describing how objects are moving quantitatively, i.e. by lists of many precise positions, modelling movement in a qualitative way can formalize our common-sense view of the world. As topological, orientation, and distance relations between some spatial entities are likely to change over time, the formal models of spatial relations introduced above are not sufficient as such to represent the spatio-temporal behaviour of these spatial entities. The notion of movement closely associated to a given spatial entity is a fundamental concept that can model and embed its behaviour in space and time. This can also denote the notion of spatial change associated to a given spatial entity. Such changes intuitively perceived by humans as qualitative processes and have been elsewhere studied by Naive Physics in an absolute space to formalize common sense human beings knowledge of physical world (Hayes 1979). Several formal approaches have been then developed such as the Qualitative Process Theory (Forbus 1982, 1983), Qualitative Kinematics (Forbus et al. 1987; Faltings 1990), and Region-Based Geometry (Bennett et al. 2000). Most of these qualitative models focus on how entities move one in relation to the others. This section reviews current approaches oriented to qualitative and relative movement descriptions, those being translation-, rotation- and scale-invariant. A few key factors that differentiate those modelling approaches are as follows:
• Whether they consider dimensionless points or regions as primitive objects, either in time, space or in space and time.
• Whether they are based on discrete or continuous times.
• Whether they represent the space and time domains separately or homogeneously. We classified those modelling approaches into two groups: one denotes approaches which represent two separated domains for space and time, and the other approaches which integrate a primitive and integrated space-time domain.

Primitive DL-RE Topological Relations

Topological invariants qualify the spatial relations that emerge from a set of regions distributed in a given scene (Deng et al. 2007). The completeness of primitive Directed Line REgion (DL-RE) topological relations can be illustrated according to the distribution of the boundary of L , that is, the two endpoints of L with respect to a region. A point has three possible topological relations with respect to a region: either in the exterior, boundary, or interior of a region. Overall, there are six cases regarding the topological relations of the two endpoints of L and a region:
• both of the endpoints of L are either in the exterior (Figure II.2a).
• in the interior of the region (Figure II.2b).
• one endpoint of L is in the boundary of the region and the other is in the exterior of the region (Figure II.2c).
• one endpoint of L is in the boundary of the region and the other is in the interior of the region (Figure II.2d).
• one endpoint of L is in the interior of the region and the other is in the exterior of the region (Figure II.2e).
• both of the endpoints of L are in the boundary of the region (Figure II.2f).
At the coarse level, the line-region topological relations corresponding to each case in Figure II.2 are: disjoint, contained-by, meet, covered-by, cross and on-boundary (Deng 2008). When considering the direction of L : reverse configurations are valid for cases 1c, 1d and 1e (i.e., meet, covered-by, and cross), this leading to 9 primitives.

Boundary-based Movement Pattern between one Directed Line and a Region

The movement of an object with respect to any area of interest can be modelled as a spatial relation between a directed line and a region. Topological relations can reveal how an object crosses the border or moves between inside and outside a given region. These cases are important when people conceptualize the phenomenology of a movement. In order to derive the movement patterns that emerge between a directed line and a region from topological relations, let us make a difference between the configurations that emerge from a point that moves inside the region, across the boundary or the exterior of that region.
More formally the intersection between the directed line L and the boundary of a region A gives a set O of non-connected spatial entities with the properties of cardinality and dimension, which also characterize the possible configurations. The DL-RE topological relations are classified according to the properties: m#(O)#(LA) , d H dim(O) max(dim(L A)) , and the values of the intersections of the neighbouring discs [Vba ck,Vleft ,Vfr ont,Vr ight] ofO .

More than One Intersection

The approach is flexible enough to generate different sets of configurations depending on the chosen criteria. One can for example restrict the configurations to m=1 and d=1 and find the complete configurations shown in Figure II.6. Several of these configurations can be derived from other configurations. For example, S15 can be composed by S3 and S14, S23 is made up of S5, S13 and S4. If there are more than one intersections (m>1), the DL-RE topological relations can be composed according to the dimension sequence ofO .
The possible topological configurations and movements that emerge from the topological configurations between a directed line and a region can be relative large. As a matter of fact, there should be an infinite number of possible DL-RE topological relations in a 2-dimensional Euclidean space when not limiting the number of 0- or 1-dimensional intersections. Although the model developed can potentially represent a high number of intersection points and then complex movements, a composition of DL-RE movements can be also applied.

Table of contents :

CHAPTER I: Related Work
I.1 Introduction
I.2 Qualitative Spatial and Temporal Representations
2.1 Qualitative Topological Relations
2.2 Qualitative Orientation Relations
2.3 Qualitative Distance Relations
2.4 Qualitative Temporal Relations
I.3 Qualitative Spatio-Temporal Reasoning
3.1 Conceptual Neighbourhoods
3.2 Composition Tables
I.4 Qualitative Movement Modelling
4.1 Space + Time Approaches
4.2 Integrated Space-Time Approaches
I.5 Movement Semantics
I.6 Discussion
CHAPTER II: Movement Patterns
II.1 Introduction
II.2 Modelling Principles
2.1 Primitive DL-RE Topological Relations
2.2 Dimensionality and Cardinality
2.3 Dimension Sequence of an Ordered Set of Spatial Entities
2.4 Neighbouring Discs on Intersection Points
II.3 Boundary-based Movement Pattern between One Directed Line and a Region.
3.1 No Intersection
3.2 One 0-dimensional Intersection Point
3.3 One 1-dimensional Intersection Line
3.4 More than One Intersection
II.4 Orientation-based Movement Pattern between Two Directed Lines
II.5 Conclusion
CHAPTER III: Qualitative Representation of Moving Entities
III.1 Introduction
III.2 Spatio-Temporal Primitives
2.1 Temporal Primitives
2.2 Topological Primitives
2.3 Distance Primitives
III.3 Towards a Region-Region Movement Representation
3.1 Movement outside a Reference Entity
3.2 Movement on the Boundary of a Reference Entity
3.3 Movement inside a Reference Entity
III.4 Towards a Trajectory-Region Movement Representation
4.1 No Intersection
4.2 One 0-dimensional Intersection Point
4.3 One 1-dimensional Intersection line
III.5 Discussion
CHAPTER IV: Qualitative Reasoning on Moving Entities
IV.1 Introduction
IV.2 Continuous Transitions of Movements
2.1 CND for Region-Region Movements
2.1.1 Interpreting the CND
2.1.2 Similarity between Region-Region Movements
2.2 CND for Trajectory-Region Movements
IV.3 Composition Tables
3.1 A Composition Table for Region-Region Movements
3.2 Case Studies
3.2.1 Case study 1
3.2.2 Case study 2
3.2.3 Case study 3
IV.4 Conclusion
CHAPTER V: Experimental Applications
V.1 Introduction
V.2 Application to Air Transportation
2.1 Analysis of Flight Trajectories
2.2 Flight Trajectory Reasoning
V.3 Application to Maritime Transportation
3.1 Maritime Trajectory Patterns
3.2 Maritime Trajectory Reasoning
V.4 Conclusion
CHAPTER VI: Conclusions & Perspectives
VI.1 Outline
VI.2 Main Research Findings
VI.3 Perspectives
APPENDIX A: Résumé étendu de la thèse
A.1 Introduction
A.2 Patrons de Mouvements
2.1 Principes de Modélisation
2.2 Patrons de Mouvements Orientés Frontière entre une Ligne Orientée et une Région
2.3 Patrons de Mouvements Basés sur des Relations d’Orientations entre deux Lignes Orientées
A.3 Représentation Qualitative de Mouvement d’Entités
3.1 Primitives Spatio-temporelles
3.2 Vers une Représentation de Mouvements Région-Région
3.3 Vers une Représentation d’une Trajectoire-Région
A.4 Raisonnement Qualitatif sur des Entités Mobiles
4.1 Transitions Continues de Mouvements
4.2 Tables de Composition
A.5 Applications Expérimentales
5.1 Application au Transport Aérien
5.2 Application au Transport Maritime
A.6 Conclusion
APPENDIX B: List of Publications
APPENDIX C: Short Curriculum Vitae
REFERENCES .

GET THE COMPLETE PROJECT