Although intensive works have been devoted to spatiotemporal modeling during the last two decades, there are only a few models dedicated to relationships between two (or more) moving objects. This paper proposes a classification framework of spatiotemporal relationship models based on the ways spatiotemporal histories are analyzed. First, we discuss model conditions of application. Then we propose a classification of spatiotemporal relationship models based on a pyramidal representation of the quantity of extracted information, i.e. the nature and the complexity of provided information, from spatiotemporal histories. This classification aims helping users to choose adequate models for their purposes. The proposed spatiotemporal histories analysis method could lead to the development of new spatiotemporal relationship models.
reasoning, spaces,
Although intensive works have been devoted to spatiotemporal databases, spatiotemporal data model, physical storage structures and spatiotemporal representation during the last two decades, there are only a few models which focus on relationships between moving objects. Spatio-temporal relationship models give information about the relationships between two (or more) moving objects in time. First developments were based on the combination of spatial and temporal relationship logics. Recently, new models have been developed on the basis of spatio-temporal shape descriptions. Theses shapes are obtained from object’s movement over time. In this paper, we propose a classification framework of spatiotemporal relationship models. The aim is to help users selecting the most adequate models for their purposes (e.g. epidemiology, crime mapping, robot navigation, collisions analysis…).
Evolution of objects can be rather complex. Objects life and movement imply
changes in spatial and temporal dimensions [
Spatiotemporal relationships between two objects can be seen as the direct or indirect description of a relationship between two spatiotemporal histories. Indeed, most of the spatiotemporal relationship models can be described in temporal space frameworks. They focus on different spatiotemporal history properties such as connections, distances, slopes and projections on spatial or temporal axis… We will classify spatiotemporal relationship models depending on these kinds of properties. The proposed methodology is still valid when dealing with moving objects in 3D space.
Complete object’s life is often more complex than simple movement. Entire
object’s existence could not be represented with a continuous spatiotemporal history.
Indeed, there is always a period of time where the object did not exist yet and will not
exist anymore. Moreover, during the analysis, objects could leave the analyzed zone or
not be visible for operator for a while. This implies holes in spatiotemporal histories; a
key in a pocket is still existent but is not visible, a soccer player who is not on the field
exists but is not present, he could replace someone and then be present just for a certain
period, an employee who is in vacation is still existent but not present for the company,
etc. In [
The rest of the paper is structured as follows. First, we give a short reminder of selected spatiotemporal relationship models. Then we describe what we call the cooccurrence zone of objects life evolution. Using a collision example between two objects, each analyzed model is represented in temporal space framework. Finally, a pyramidal classification is proposed and we conclude.
The aim of this section is to briefly recall some important aspects of models studied in this paper; it is not a comprehensive state-of-the-art on spatiotemporal relationship models. We consider being spatiotemporal relationship models, models which describe relationships between two objects over space and time.
Qualitative Trajectory Calculus (QTC) proposed by Van de Weghe [
The double cross calculus (DCC) introduced by Freksa [
The relative representation of trajectories in geographical space defined by Noyon
and Claramunt [
Last model, the spatio-temporal generalized model (STGM), has been proposed by
Hallot and Billen [
Although projective relationships defined by Billen [12-13] have not been yet presented as spatiotemporal relationship models, we wish to point out here some interesting properties for our analysis. Projective relationships are based on projective geometry. This geometry can be seen as an extension of topological geometry. Projective relationships are able to describe advanced connection between objects refining boundaries connection between objects. Such relationships could be substituted by the topological relationships in the STGM.
Objects do not have an infinite existence. There is always an interval of time where
objects did not exist before their utility/existence/life and another period after that.
Considering huge data collections over long periods of time would imply to deal
sometimes (often) with non co-existent objects. Some of them will not exist anymore
during existence of other ones and vice versa. Most of spatiotemporal relationship
models can only deal with coexistent objects. Thus, spatiotemporal relationship cannot
be defined between them. Considering all the complexity of spatiotemporal
information, it is first necessary to select a co-occurrence zone of both analyzed
objects. In a previous work [
First model is the spatiotemporal generalized model (STGM). It only focuses on the topological connection between spatiotemporal histories. The analysis gives a topological relationship between two lines (see fig. 3). Although this model do not give complete information about movement of object A and B. It gives principal information about the connection of two objects. Information about collision is known. This model does not change if dealing with moving points in a 3D environment. Applications such as epidemiology, information transmission can be realized with this model.
Two objects meet at their born or at their death.
Projective space analysis gives more detailed information about connections between spatiotemporal histories. It can differentiate the two situations presented in figure 4. In a topological point of view, there is no difference between the two spatiotemporal situations presented. However, projective relationships differentiate the spatio-temporal history of A in the right part of figure 4. The orders which compose the geometrical shape in a projective point of view are different. The angle is of order 0 although right segment parts are of order 1 (see [13] for further explanation about object’s point order).
This model’s extension offers more information than with topological relationships only i.e. direction changes and particular connection can be retrieved from spatiotemporal analysis. This extension of STGM has not been formalized yet.
Although qualitative trajectory calculus (QTC) model has not been defined in terms of spatiotemporal history analysis, its basic form can be easily represented in temporal space framework. For two points moving in 2D or 3D space, the representation uses a 2D temporal space to symbolize the minimum distance between points over time. Figure 5 shows the two qualitative values used in QTC and their interpretation in temporal spaces. The distance evaluation between time point immediately before and immediately after QTC time is easy. Part 1 and 2 shows these two distances’ comparison with arrows. If first distance is higher than the second, qualitative value is -, if they are equal then the qualitative value is 0 and it is + if the second is higher than the first. QTC may also provide information about the relative speeds of moving objects. This could be represented in temporal spaces as well. The last QTC value (part 3 in figure 5) compares the slopes α and β respectively representing the speed of object A and B. The qualitative value is + if α > β, 0 if they are equal and - if α < β.
QTC analysis can be summarized as a qualitative distance and slope analysis of spatiotemporal histories. This analysis provides more information than topological or projective ones on spatiotemporal histories. However, QTC analysis has to be repeated many times to give complete information about spatiotemporal situation while others give relationship about complete situation.
Relative representation of trajectories provides similar analysis of spatiotemporal histories than QTC. Although this model is based on a relative reference system view, it can be represented through temporal space. Indeed, primitives used to define this model are the relative position and the relative speed. These information are available on temporal space representation. Figure 6 shows the relative representation of trajectories of the collision example.
Double Cross Calculus (DCC) could not be represented in 2D temporal space. Indeed it is not based on the distance between analyzed objects. 3D temporal space is necessary to represent double cross calculus. This one keeps all the 2D spatial information. In terms of spatiotemporal histories, DCC analyzes the projection of spatiotemporal histories on spatial plane and divides space with projection into several zones. Relationships give information about object membership to spatial division. Figure 7 (left) shows spatial projection of previous collision example and double cross spatial clustering. The right part gives an interpretation of clustering of spatiotemporal space with double cross (which becomes double plane crosses). Created planes are based on the spatiotemporal history of object A.
In terms of spatiotemporal history analysis, the Double Cross Calculus can be seen as an analysis of spatiotemporal space division. It gives information about the memberships of one object to defined zones. It would not be possible to represent this division for objects moving in a 3D space, although the method continues to be valid.
Previous analysis can be summarized through a pyramidal classification (see figure 8). The classification is based on the quantity of extracted information from spatiotemporal history analysis. The top of the pyramid is limited to co-occurrence zone. As explained before, presented models are limited to space and time zone in which analyzed objects are both existent, present and, for some models, disjoint. Models can be organized following their analysis of spatiotemporal histories.
First ones, Topological and Projective models focus on geometrical connection between spatiotemporal histories. Proposed spatiotemporal relationships describe entire object spatiotemporal configurations. They are easy to use and are valid when dealing with objects in a 3D environment. However, they do not give information about directions, velocity… This is why they are on the top of the pyramid. They can deal with applications requiring only connections and meetings such as crime mapping, epidemiology…
Second group is the double cross calculus which works with division of spatiotemporal space. It qualifies the membership of one object to several zones. This model offers information about directions, orientations. Deeper analysis can be realized to derive information about velocity. This models’ group deals with collisions and directions. They can be used for basic robot navigation, movement analysis, movement pattern recognition…
The last group of models is placed on the same pyramid stage because they are both based on qualitative distance and slope analysis. They give information about velocity, distance between objects. In this paper, QTC have been analyzed in its basic form. Some of their extensions combine kinds of double cross calculus and acceleration considerations. Relative representation of trajectories can offer complementary information from the absolute reference representation. These models offer more complex information for robot navigation, air-traffic control…
Spatiotemporal relationship models provide information about spatial and temporal relationships between two objects. Most of them are qualitatively based. Each spatiotemporal relationship model provides diverse information about spatiotemporal configurations. Our first analysis shows that most of the spatiotemporal relationship models can only be applied during a small subset of object life evolution. Indeed, most of spatiotemporal relationship models are available when objects are both existent, present, and even sometimes disjoint. During an object’s life there are several periods of time when objects are neither contemporary nor spatially visible. More general models exist and can help to select specific spatial and temporal zones in which more detailed spatiotemporal relationship models can be used.
A classification method is applied to the following selected models: the qualitative trajectory calculus, the relative representation of trajectories, the double cross calculus, topological and projective spatiotemporal relationship models. Although all these models are not entirely defined in terms of spatiotemporal relationships, they all provide information about relationships between two objects in regards of space and time. Models are classified on the basis of the kind of geometric analysis that could be applied to spatiotemporal histories in a temporal space. Topological and projective relationship models focus on spatiotemporal histories connections, double cross calculus highlights the division of spatiotemporal space and the QTC and relative representation of trajectories deals with the qualitative distance of temporal slices and the qualitative slopes of spatiotemporal histories. Based on this analysis, models are classified in a pyramidal representation. This pyramidal representation can be useful to help users to select the most appropriate models considering their needs. If they have to concentrate on collision, meeting between objects without taking into account the speed and direction, models such as the topological or projective analysis are sufficient. For example, in epidemiology, getting information about meeting between contagious and healthy person might be enough. Models such as QTC offer more information; it supports deeper analysis taking into account speed, direction, acceleration. Applications such as robot navigation, accident re-forming and air-traffic control can be performed with the relative representation of trajectories model.
The presented classification methodology allows classification, comparison and selection of spatiotemporal relationship models. We also believe that it could be a design framework for new prospective spatiotemporal relationship models. [12] Billen R, Kurata Y. Refining Topological Relations between Regions Considering Their Shapes. Geographic Information Science. 2008. p.20. [13] Billen R, Zlatanova S, Mathonet P, Boniver F. The Dimensional model: a framework to distinguish spatial relationships. 2002. p.285. [14] Hallot P, Billen R. Spatio-Temporal Configurations of Dynamics Points in a 1D Space. In: Gottfried B, editor. Behaviour Monitoring and Interpretation BMI'07. Osnabrück, Germany: Centre for Computing Technologies (TZI), University of Bremen, Germany, 2007. p.77.