-Within qualitative spatial reasoning, spatial objects having directions have been abstracted in different ways; directed line segments, oriented points etc. have been used. In certain applications, it becomes necessary to reason about directions of objects without focusing on the dimensionality of these objects. We present a framework for representation of and reasoning about directions in a qualitative way within an egocentric spatial reference frame. Qualitative direction has been separated from spatial location and dimensionality of spatial objects and as such, the formalism may be used to represent qualitative direction in a dimension-independent way. The formalism uses fewer numbers of base relations than existing formalisms. Further granularity can be refined easily. Qualitative direction relations separated from spatial location and dimensionality can be used to express spatio-temporal patterns of directional entities using a regular grammar.
INTRODUCTION
Everyday reasoning involving spatial and temporal
attributes is driven through qualitative abstractions rather than
complete quantitative knowledge. Qualitative abstractions are
an integral part of our conceptualization of space and time
[
Space, in our commonsense knowledge, is characterized by
many different attributes. Within Qualitative Spatial Reasoning
(QSR), spatial characteristics are abstracted in a qualitative
way. Aspects of space that have been treated in a qualitative
way are spatial orientation, distance, direction, shape and size
etc [
In QSR literature, different formalisms have been used
for representing directions of spatial objects in a qualitative
way. In some works, spatial objects have been abstracted as
directed dimensionless points. In others, directed line segments
have been used [
For the Qualitative Direction Algebra (QDA) proposed in this work, we separate qualitative direction from the issues of spatial location and dimensionality. We propose a direction model that does not use spatial location labels for representing qualitative direction. We have used angular measurements between directions for representing our qualitative direction relations. Direction relation labels, that we have proposed, are closer to our cognitive perception of object locomotion. A Jointly Exhaustive and Pairwise Disjoint (JEPD) set of binary qualitative relations has been proposed for representing and reasoning with qualitative directions. The issue of spatiotemporal continuity of these base relations has also been addressed. For constraint based reasoning, this set of relations needs to be closed under composition and converse. We have proposed algorithms for finding the converse of a single relation and also to find the composition of two base relations. An interesting characteristic of this formalism is that the granularity can be refined depending on requirement. In QSR, continuous input is discretized and qualitative abstractions are introduced. For example, let us consider distance as a spatial aspect. Distance of one object from another will have continuous numeric values. From a qualitative view point, we can discretize these values into three zones and label these as close, near and f ar. If necessity arises, we can further subdivide the close range and introduce two labels, namely, veryclose and close. In doing so, we are refining our granularity in such a way that finer changes in numerical distance can be represented. In a similar way, in the formalism proposed in this paper, it is possible to move to finer granularity so that smaller changes in angular direction can be represented. The algorithms proposed for finding converse and composition can handle refinement of granularity.
A spatial reference frame is a coordinate system with
respect to which the qualitative direction labels are defined.
Spatial reference frame is an important issue when we want
to represent qualitative direction. Tversky advocates that
people’s spatial mental models use only two basic perspectives
locating elements relative to one another from a point of view
or locating an element to a higher order environmental feature
or reference frame [
III.
In order to explain the qualitative direction relations, we need to introduce a few definitions. The direction in which an object is headed is specified by a straight line. In a two dimensional plane, the direction of this straight line expresses the direction of the object. This straight line, used for specifying the direction of an object, has been termed as a direction line. For finding binary qualitative direction relations, at first we need the direction lines for each object under consideration.
For convenience, we assume that the start point for all these direction lines is same. This can be done because the direction line represents the direction logically and translation of these lines do not change the direction of the object. Moreover, spatial locations of the objects are noway important to us. As an illustration, in Figure 2, we have shown two objects whose directions are indicated by arrowheads (part A). In part (B) of the same figure, two direction lines are drawn parallel to the direction of the two objects. We will use the notation dirA to mean the direction line of the spatial object A. When we make the direction lines originate at the same point, we have regions between two consecutive direction lines.
Definition. Direction Region : Let l1 and l2 be two direction lines having directions dir1 and dir2 respectively and having a point of intersection o. Let be the angle between dir1 and dir2 in an anticlockwise direction. Then, a direction region defines a set of direction lines that originate at o and the direction of any such line is bounded by the angle from dir1 in an anticlockwise direction.
The concept of direction regions will be used in algorithms
for finding composition and converse of base relations of the
qualitative direction algebra. We have the task for arriving
at a set of binary qualitative direction relations from the
angles measured between their direction lines. QSR discretizes
the continuous domain and introduces abstractions. We may
tend to think that QSR is same as fuzzy approximations; but
there is an important difference. Categories in fuzzy approach
are approximations of real values, while categories in QSR
depends on application requirement [
We start with four qualitative abstractions and name these as Same , Opposite , LR and RL. These abstractions are derived from the angular displacements between direction lines. Our qualitative relations for direction are binary. So, the direction of one of the objects is taken as the reference direction. The direction of the other object is taken as the primary direction and a qualitative relation expresses the relationship of the primary with respect to the reference.
Let A and B be two spatial objects. When we say A Same B, we mean that the angle between dirA and dirB is zero. For uniformity, we will measure all angles counterclockwise. Meaning of A Opposite B is that the angle between dirA and dirB is 180 degrees. When an object A moves along dirA in a two dimensional plane, its course of motion divides the plane equally into two parts. Assume that the direction line dirB, corresponding to some object B, intersects dirA at right angle in a left to right direction. Then, the resulting qualitative relation is named as LR. An identical case in the right to left direction is termed as RL. We have a set of four binary qualitative direction relations here. These relations are illustrated in Figure 3.
The level of granularity is too coarse and change in direction is represented when it crosses a threshold of 90 degrees. These are the major direction relations that we are going to refine further. Naturally, one would like to divide these right angles equally so that granularity is refined. An important aspect is to keep the angular span same for all relations. We identify two direction regions, namely, a + region and a region. The + region is direction region with an angular span of 45 degrees measured counterclockwise from one of the major direction relations introduced earlier. The region is direction region with an angular span of 45 degrees measured clockwise from one of the major direction relations. Since each major direction relation now will give rise to one + region and one region, we will have eight such direction regions in total. These can be considered as qualitative direction relations, because the direction line of the primary may fall along any of these. For naming these relations, we use a simple notation where we append a + or symbol to the name of a major direction label. For example, the major relation Same results in two relations, namely, Same+ and Same . Let A Same B and let B be the reference object. In the relation Same, we know that the angle between dirA and dirB is zero. In Same+, the direction line dirA lies within an angular span of 45 degrees measured counterclockwise from dirB. Similarly, in Same , the direction line dirA lies within an angular span of 45 degrees measured clockwise from dirB. These twelve base relations are enumerated in Table I. The angular spans for all the relations are listed. All these angles are measured in anticlockwise direction from the direction line of the reference object. In Figure 4, these relations are shown pictorially. There are eight equal divisions of the full angular span of 360 degrees. We choose to use this number of divisions to express the granularity of the algebra. So, the base relations enumerated in Table I are for a QDA with granularity eight. We denote this as QD8.
The twelve base relations listed in Table I, can record change in direction when the direction of the primary object crosses discrete boundaries at integral multiples of 45 degrees. In many applications, it may be necessary to record change at finer intervals. In our proposed formalism, this can be done very easily. In this section, we will show one level of refinement. The same process can be repeated to arrive at even finer granularity of base relations.
For refinement, we equally divide the + and direction regions. For example, if we divide the + region for which the angle range is ]0; 45], we obtain two direction regions of span 22.5 degrees each. The region [0; 22:5] is denoted by the symbol +1 and the region ]22:5; 45] is denoted by +2. As a result, we get twenty four base relations that are listed in Table II. This time, change in direction is noticed after a threshold of 22.5 degrees. The same thing can be done to the region and the resulting direction regions will be 1 and 2. These refined relations are shown in Figure 5. Now, there are 16 equal divisions of the full span of 360 degrees and accordingly, we have QD16.
Fig. 5. QD16: Direction relations one level refined.
In order to apply constraint based reasoning to a set of
spatial relations, we develop a partition scheme for the objects
in the domain under consideration [
For finding the direction relation that holds between directions of two spatial objects, one of these objects is considered as a reference. A direction line parallel to the direction of the reference object is drawn and this direction line can be designated as line 0. The direction relation wheel can now be drawn with respect to this line according to the granularity level under consideration. Then, the direction line corresponding to the direction of the primary object is drawn. The direction region in which this line falls tells us the direction relation of the primary with respect to the reference. All angles are measured counterclockwise and direction relations in terms of angle ranges have been listed before.
We present an algorithm for finding the converse of any qualitative direction relation. Let us assume that A dr B, where A and B are spatial objects and dr is the direction relation holding between their directions. Intuitively, for finding the converse of dr, we should know the number of rotations we should give to the direction line of A to get back to the direction line of B. This is because of the fact that the converse expresses the relation of B with respect to A. So, for finding the converse relation, the direction line of A will be taken as line 0. Moreover, we should know the relation that results after these many rotations. An algorithm is presented below for finding the converse of a qualitative direction relation.
be returned and m is the granularity
1.n:= Calc_Rot_Conv(R) 2.If (R==’Same’||R==’Opposite’||R==’LR’ || R==’RL’) Then
Function Calc Rot Conv returns the number of rotations needed to align the direction line of the primary object with that of the reference. The bottom and top lines for the relation are retrieved into local variables p and q. p denotes the index of the bottom line and q denotes the index of the top line. Since the function returns m p, we understand that the maximum required number of rotations is returned by the function. This returned value gets stored in the local variable n inside the function Converse. If the relation is one of Same , Opposite , LR or RL , then we know that the direction line of the primary will not fall in a direction region. It will align with one of the lines (at one of the angles 90 , 180 , 270 or 360 degrees measured counterclockwise )in the direction wheel. Then, it is easy to see that we will have to give m n number of rotations to the direction line of the primary object. For example, let us consider QD8 and let A Opposite B hold. Then, the direction line of the primary aligns with the line at an angle of 180 degrees in the direction wheel. The value of < p; q > will be < 4; 4 >. The value returned by Calc Rot Conv will be 4. Inside the function Converse, a call will be made as F ind Rel(8 4; 8 4). The relation whose bottom and top lines are (4; 4) is Opposite.
So, the converse of Opposite is computed as Opposite.
For a discussion of other type of relations, let us consider RL+. The bottom and top lines for this relation will be returned as < p; q > = < 2; 3 >. The value returned from Calc Rot Conv will be 8 2 i.e. 6. Inside the function Converse, Max rot will be 6 and Min rot will be 5. This time, there will be a call like F ind Rel(8 6; 8 5) i.e. F ind Rel(2; 3). The relation for which dirbottom is 2 and dirtop is 3 is RL+. So, the converse of RL+ is RL+. An outline of the Calc Rot Conv function is given below.
1. < p , q> := Get_Lines(Rel)
We assume that the function F ind Rel retrieves the appropriate relation from a hash table depending on the pair of integers passed to it . Every direction relation can be represented by a pair of integers (i; j) where i is the integer corresponding to dirbottom and j is the integer corresponding to dirtop. For example, when the pair (0; 0) is passed, the retrieved relation is Same , when (0; 1) is passed, the retrieved relation is Same+ and so on. An outline of the algorithm for the F ind Rel function is given below. The algorithm takes care of the fact that sometimes (while computing composition of relations) the second argument can be two more than the first and the local variables c and d are used to control this. The algorithm will return a quadruple of relations. Let us assume that this quadruple is of the form < R; Q; S; T >. In this quadruple, only non null entries are meaningful. For example, if we call F ind Rel(2; 2), then only one relation is returned and this is available in R. If the call is like F ind Rel(4; 5), then also a single relation is returned in R. The parameters Q , S and T become meaningful when max is min + 2. Algorithm Find_Rel( min , max) 1. c:=d:=-1 ; R:= Q := S := T := Null 2. If (min==max) Then 3. Begin 4. R := From_Hash(min,min) 5. Return <R,Q,S,T> 6. End 7. Else If (max==min+1) Then 8. Begin 9. R := From_Hash(min,max) 10. Return <R,Q,S,T> 11.Else If (max==min+2) Then 12.Begin 13. <a,b> := <min,min+1> 14. If <min+1==0 || min+1==2 15. || min+1==4 || min+1==6> Then 16. <c,d> := <min+1 , min+1> 17. <e,f> := <min+1 , max> 18. Q := Get_From_Hash(a,b) 19. If (c!=-1) Then 20. Begin 21. S := From_Hash(c,d) 22. T := From_Hash(e , f) 23. End 24. Return <R,Q,S,T>
For constraint based reasoning, composition of base relations is an important issue. An algorithm for composition of base relations is presented. Let A , B and C be three objects such that A Rel1 B and B Rel2 C hold. We want to find Rel1 Rel2, where denotes set theoretic composition. For this, direction relation wheel is drawn with respect to the direction of B. Since the relation of A to B is already known, we can identify the direction line or direction region for A. The remaining task is to fix C in the wheel. Rel2 is given. But that expresses the relation of B with respect to C. We take the converse of Rel2 and identify the direction line or region for C with respect to B. To find the composition we need to compute the number of rotations required to align direction of C with that of A and find the resulting relation. For any relation Rel, let us denote the lower line of its direction region as RelBottom and the corresponding upper line as RelTop. Then, any relation can be expressed as an ordered pairs of the form (RelBottom; RelTop). For example, in the Figure 4, the relation Opposite+ can be specified as (4; 5) and Same as (0; 0).
This algorithms computes composition of rel1 and rel2. m is the granularity 1. S:=Converse( Rel2 , m) 2. <p,q >:= Get_Lines(S) 3. <r,s>:= Get_Lines(Rel1) 4. <min,max>:=Calc_Rot_Comp(<p,q>,<r,s>)
Conceptual dependency of a spatial relation defines a set of relations that may hold after this relation whenever a change is recorded. For example, if at any point of time Same is the qualitative direction relation that holds between directions of two objects, then it is not possible that this relation will change to Opposite whenever change in direction is noted. After the relation Same , the possible relations that may hold can be either Same+ or Same . The relations that may hold after the current relation are termed as its conceptual neighbour(s). Conceptual neighbours dictate how one relation can or cannot change. This gives rise to a notion of spatio-temporal continuity which can be exploited in many applications. Conceptual neighbours are generally expressed by a graph where nodes represent relations and edges are drawn from a node to its conceptual neighbours. In Figure 6, conceptual dependency of 12 base relations for QD8 is shown.
IV.
Qualitative direction relations can be used to represent and reason about spatio-temporal patterns of directional entities. One such example is motion pattern analysis. For such applications, formalisms are required for representation and recognition of patterns in an input stream.
Fig. 7. Motion events of a set of directed points.
Figure 7 present a synthetic example where three objects are involved in a motion pattern recognition application. One of the objects is stationary and has a direction along its egocentric orientation. The other two objects are non stationery and changes in their egocentric headings. R is the stationery object and it is taken as the reference object. We want to represent the motion sequence of P and Q with respect to R. The motion sequence of P with respect to R can be expressed as Opposite; Opposite ; RL+; RL and that of Q can be stated as RL; RL ; Same+; Same. Such patterns can be expressed using a regular grammar and a parser can be used to recognize the pattern in an input stream.
Elsewhere a general technique has been developed to
combine QSR with formal grammars for recognition of motion
events among multiple spatial entities [
V.
In this paper, a qualitative direction algebra is proposed for representation and reasoning about directions of spatial objects in a dimension independent way. Qualitative spatial relations for QD8 and QD16 have been defined.
Existing formalisms combine dimensionality into definition of relations and as a result of this, such representation become unsuitable when dimension scales up. In the proposed formalism, it is easy to move to a finer granularity. This finer granularity is realized using fewer base relations than existing formalisms. A limitation of this approach might be the fact that it ascertains the directions in a deterministic way. At any point of time, it is assumed that we know the angles between the directions with certainty. Future work includes study of formal properties of these calculi.