Acquisition of Qualitative Spatial Representation by Visual Observation

1 Introduction

In robotics and computer visiOn, acquisition of envi­ ronment maps, which represent landmark positions and sensor positions, and their utilization are important re­ search issues. Various quantitative and qualitative meth­ ods have been proposed so far. In general, quantita­ tive methods, which use triangulation, stereo techniques, ranging sensors and so on, are based on the accumula­ tion of accurate metrical information. That is, they are sensitive to sensor noise and accumulate error. In con­ trast, qualitative methods have been expected as meth­ ods which are not seriously affected by senor noise and enable us to navigate robots in a wide environment, for example.

Levitt and Lawton reported a qualitative method for landmark-based robot navigation in an outdoor environ­ ment [Levitt and Lawton, 1990]. The robot uses a map in which precise locations of landmarks are indicated. With the map, the robot can qualitatively know the lo­ cation. Besides this method, several works have been reported which utilize pre-defined qualitative maps and qualitatively utilize standard geometrical maps.

On the other hand, acquisition of the qualitative map itself is also necessary. It is often supposed that qualita­ tive landmark positions can be obtained from observed quantitative information (e.g. in the same way as trian­ gulation). However, it is not true especially in a large­ scale environment, since the sensor data is noisy. A method which acquires qualitative landmark positions from more raw and stable information would be useful, however, such a method has not been proposed so far.

Several methods have been proposed which acquire qualitative spatial representation by quantitative obser­ vations. Yeap developed a method for acquiring a cog­ nitive map based on 2~-D representation of local areas [Yeap, 1988]. The map is supposed to be acquired with range sensors. Kuipers and Byun proposed a method for acquiring qualitative representation by exploration of a robot [Kuipers and Byun, 1991]. The representation consists of corridors and intersections recognized from sensory input. These methods deal with an abstraction problem from perceptual information of a real world into qualitative representation, and discuss how to arrange local representations into a total representation.

In this paper, we propose a method for reconstructing qualitative positions of landmarks from qualitative in­ formation acquired by visual observation. The method utilizes motion directions of moving objects in an envi­ ronment observed from each landmark as shown in Fig­ ure 1(a). While the object moves around in the envi­ ronment, qualitative positions of the landmarks are re­ constructed with several rules based on geometrical con­ straints. Generally, we consider qualitative information is given by quantizing quantitative information. However, the correctness of the qualitative information obvi­ ously depends on the methods used for the measurement. We use the motion direction as the qualitative informa­ tion since it is often stably acquired by background sub­ traction and template matching. The template matching works well with a small search area, however, it is diffi­ cult to use for a wide search area. This paper supposes the template matching gives a correct motion direction with a limited small search area estimated by the back­ ground subtraction. Thus, compared with the previous acquisition methods, this paper focuses on how to ac­ quire qualitative positions of landmarks from raw, simple and stable information.

As an application of the method proposed in this pa­ per, we consider a distributed vision system (DVS) [Ishig­ uro, 1997]. The DVS consists of multiple vision sen­ sors embedded in an environment called vision agents as shown in Figure 2. The method can be applied to acquisition of qualitative positions of vision sensors in the DVS. However, the method is not only for the DVS. It can acquire qualitative rriaps of landmarks in general robot navigations. Suppose the robot has an omnidirec­ tional vision sensor [Ishiguro and Tsuji, 1996], observes motion directions of the landmarks in the omnidirec­ tional retina and identifies the landmarks with visual features as shown in Figure 1 (b) . The method proposed in this paper can reconstruct the qualitative positions of the landmarks with the observed qualitative motion directions. That is, the method solves one of the general and fundamental problems in robot navigation and map building.

2 Qualitative Representation and Qualitative Observation

2.1 Qualitative Spatial Model

In our method, the positions of points (in the remaining sections, we call landmarks as "points") are represented with relative positions with respect to lines passing over arbitrary two points as shown in the left of Figure 3. This representation is one of the most fundamental represen­ tation and various methods have been proposed in the field of qualitative spatial reasoning [Forbus et al., 1991; Freksa, 1992; Latecki and Rohrig, 1993]. Especially, this representation can be used for map-based robot naviga­ tion [Levitt and Lawton, 1990].

The qualitative positions as shown in the left of Fig­ ure 3 are formally represented based on relations among arbitrary three points as shown in the right of Figure 3. In general, the position of point Pi is represented as fol­ lows [Schlieder, 1995]:

PiPiPk = + if PiPiPk lies in counterclockwise

PiPiPk = - if PiPiPk lies in clockwise

where Pi and Pk are the two points connected with the lines as shown in the left of Figure 3. In the case of six points as shown in Figure 3, these m = 20 descriptions are needed to represent all positional relations of the points.

The purpose of this paper is to propose a method to acquire the qualitative spatial model formally rep­ resented as shown in the right of Figure 3 by qualitative observation described in the following subsection and to evaluate it with simulations.

2.2 Qualitative Observation

The qualitative spatial model is acquired by observing motion directions of moying objects from each points. In the case of Figure 1(a), for example, an instant mo­ tion direction of the moving object is observed from the points A, B, C and D. When a projection of moving ob­ ject moves clockwise in the omnidirectional retina of a vision sensor, the motion is qualitatively represented as "right," and when it moves counterclockwise, it is repre­ sented as "left." Note that the same information can be also acquired by opposite observation, i.e., when a mo­ bile robot observes motion directions of points as shown in Figure 1 (b).

With the observed motion directions, the points are classified into a spatially classified pair (SCP), which con­ sists of a pair of point sets labeled "left" and "right." In the case of Figure 1, a SCP "{ABD}, {C}" is acquired by the observation. By iterating the observations, vari­ ous SCPs are acquired except for inconsistent ones. For example, a SCP "{AD}, {BC}" is inconsistent with the configuration of the points as shown in Figure 1, since there exists no line which classifies the points into such aSCP.

3 Acquisition of the Qualitative Spatial Model

3.1 Overview

The SCPs represent geometrical constraints among points as described in the previous section. With the SCPs, the qualitative spatial model can be acquired. The process for acquiring the qualitative spatial model is as follows (see Figure 4):

1. Acquire a SCP by qualitative observation.
2. Acquire three point constroints (3PCs) from the SCP.
3. Classify the points into new SCPs based on the 3PCs, and acquire new 3PCs (constraint propaga­ tion).
4. Transform the 3PCs into a qualitative spatial model.

Step 2, 3 and 4 are discussed in the following subsections.

3.2 Acquisition of Three Point Constraints

In order to determine the qualitative positions of points, our method checks possible positions of the fourth points with respect to a triangle consisting of three points. Since a triangle is the minimum component to represent closed regions, we can represent relations of all points by combining the triangles.

Let A, B, C and X be the four points. The position of X is represented with one of the 7 regions defined with three lines AB, AC and BC and encoded as shown in Figure 5. Several constraints which limit possible re­ gions where X locates are acquired from SCPs based on geometrical constraints. Suppose A, B , C and X are classified into SCPs in various ways as shown in Figure 6. Considering positional symmetry of the points, the ge­ ometrical constraints are summarized into the following cases.

1. When A, B and C are in the same set (let this be P):

If X is also in P, there exists no constraint on the position of X. If X is in Q, which is the correspond­ ing set to P, X does not locate in the region 111 (see Figure 6(1)).

1. When A is in P, and B, Care in Q: If X is in P, X does not locate in the region 011 (see Figure 6(2)). If X is in Q, X does not locate in the region 100 (see Figure 6(3)).

We call these constraints three point constroints (3PCs). In general, there exist six different SCPs with respect to arbitrary four points as shown in Figure 7(a) . If motion directions of objects can be completely ob­ served from the points, the six SCPs are acquired by iter­ ative observation. Then, the SCPs are transformed into six 3PCs with respect to each point's position (see Fig­ ure 7(b)), which uniquely determine the region of each point. In the same way, qualitative positions among all points are determined if all possible SCPs are acquired by observation.

3.3 Constraint Propagation

Iterative observation provides various 3PCs, however, in practice there are some limitations in observation. For example, a vision sensor cannot observe an object lo­ cating in distance and over walls. In such cases, sufficient 3PCs for reconstructing a complete qualitative spatial model cannot be acquired by observation. How­ ever, more 3PCs can be acquired by referring to 3PCs which are already acquired.

By referring to the acquired 3PCs, the points are clas­ sified into new SCPs. This process can be considered as constraint propagation. A simple example of the con­ straint propagation is as follows. Suppose the positions of D and E are uniquely determined with twelve 3PCs with respect to A, Band Cas shown in Figure 8(a). For example, the points C, D and E are classified into the following SCP with line AB:

Furthermore, there exist four lines around the line AB which classify A and B as well as C , D and E into the following SCPs (the numbers correspond to the line num­ bers in Figure 8(a)):

There exist m = 10 lines which pass over two of A through E . Each line classifies the points into SCPs in the same way .. Consequently, the following seven SCPs are acquired:

{ABCD}, {E}

{ABCE}, {D} {AD}, {BCE}

{ABD} , {CE} {AE}, {BCD}

{ACD}, {BE}

Then, several 3PCs are acquired from these SCPs. For example, Figure 8(b) shows possible positions of B and C with respect to A, D and E acquired from the 3PCs.

3.4 Formalization of the Constraint Propagation

The process for acquiring new SCPs is as follows:

1. Acquire SCPs classified by the lines each of which passes over arbitrary two points (the example is the SCP (1) in the previous subsection).
2. Then, acquire SCPs including the two points (the example is the SCPs (2) in the previous subsection).

This can be formally summarized as follows.

Suppose regions where points locate are uniquely de­ termined with several 3PCs with respect to A, B and C . A line which passes over two of the points classi­ fies the other points into a SCP. Considering positional symmetry of the points, there exist 15 kinds of selection of the two points over which the classifying line passes as shown in Figure 9. In Figure 9, the circles indicate selected two points, and the points X and Y are clas­ sified into a SCP {X}, {Y} with the line. Figure 9 (1) corresponds to a case in which the selected points are two of A, B and C. (2) through (6) correspond to cases in which the selected points are one of A, B and C and one of the other points. (7), (8) and (9) correspond to cases in which the selected points locate in the same re­ gion. (10) through (15) correspond to cases in which the selected points locate in different regions. Note that no SCP can be acquired in the cases of (7), (8), (9) and (13) , and the SCP is {X}, {0} in the cases of (10) , (11) and (14) .

Next, SCPs including the points on the classifying line are considered. Suppose line AB classifies the points into a SCP {X}, {Y}. Although A and Bare not included in the SCP in the above discussion, there exist four lines which classify A and B as well as X and Y into the following SCPs (see Figure 10) :

{AX}, {BY} {ABX}, {Y}

T~us, new SCPs can be acquired by referring to the acqmred 3PCs, and new 3PCs are acquired from these SCPs as described in subsection 3.2. In the above dis­ cussion, the constraint propagation is performed when positions of the points are uniquely determined with 3PCs. However, even if the positions of the points are not uniquely determined, actually it can be performed with the rules shown in Figure 9 and 10. In the experi­ Il_lent_ations of the next section, the constraint propaga­ twn 1s performed under such a situation.

3.5 Transforming into the Qualitative Spatial Model

The 3PCs are transformed into the qualitative spatial model. For example, if the position of X with respect to A, B and C is determined with 3PCs as shown in Figure 11, then the order of BCX (B -+ C -+ X) is determined to be contrary to the order of ABC (A -+

B--+ C), that is, BCX =-if ABC=+ and BCX = + if ABC = - . If the order of ABC is given, then the order of BC X is uniquely determined. Consequently, if six 3PCs with respect to each point's position are acquired as described in subsection 3.2, the components of the qualitative spatial model, an example of which is given in Figure 3, are acquired.

4 Experimental Results

4.1 Verification with a Simple Environment

We have acquired a qualitative spatial model of positions of vision sensors by the proposed method with simula­ tions. First, we have verified the method with a simple environment. In the environment, there exist 10 vision sensors and a moving object in a lOmx 10m space as shown in Figure 12. Each vision sensor observes the ob­ ject in all directions at any distance and detects motions of the object as it randomly moves lm.

Figure 13 shows the averaged number of acquired com­ ponents of the qualitative spatial model over five runs. In this exrcerimentation, the total number of the compo­ nents is ( 3 °) = 120, and 80% of them have been acquired within 100 observations, and all components have been acquired within about 2,000 observations. The 2,000 ob­ servations provided 45 SCPs, which is equal to the num­ ber of possible SCPs with this configuration of the vision sensors. Since identical SCPs are frequently acquired by the observations, the number of the provided SCPs is far less than that of the observations. With this experimen­ tation, we could verify the proposed method.

4.2 Application to a Complex and Real Environment

Next, we have evaluated the method with a complex and real environment. The purpose of this experimentation is to evaluate practicality of the method. In the environ­ ment, there exist 35 vision sensors and 8 moving objects in a 30mx30m space as shown in Figure 14 (this en­ vironment is similar to the real environment as shown in Figure 2). The vision sensors can acquire omnidirec­ tional visual information. However, they cannot observe the objects at a distance of more than 10m and behind the walls indicated with white lines in Figure 14. The objects randomly move on the road indicated with gray regions in Figure 14.

In this .experimentation, the maximum number of the components of the qualitative spatial model is e35) = 6,545. However, all of the components cannot be ac­ quired, since visual range of the vision sensor is limited and the objects move only on the road. The number of components which are acquired without the constraint propagation is estimated at about 540 from the positions of the vision sensors.

Figure 15 shows the averaged number of acquired com­ ponents over five runs. With 2,000 observations of mo­ tions of 8 moving objects, 513 components have been ac­ quired in total without constraint propagation, which is almost equal to the estimated number of 540. With con­ straint propagation, 707 components have been acquired in total. In other words, about 200 components which represent the positions of the vision sensors in distant lo­ cations have been given by the constraint propagation.

Figure 16: Qualitative positions of the vision sensors

Figure 16 shows qualitative positions of the vision sen­ sors which is depicted based on the acquired 3PCs with 2,000 observations. The reason we have used the 3PCs in spite of the components of the qualitative spatial model is that all of the 3PCs cannot be transformed into the components and they include more constraints than the components. For obtaining Figure 16, we have first lo­ cated the vision sensors randomly, and then dynamically adjusted the positions with a kind of energy minimiza­ tion so as to satisfy the acquired 3PCs. Bycomparing Figure 16 with Figure 14, we can find that the estimated positions are topologically correct.

4.3 Observation Errors

The proposed method is based on geometrical con­ straints, so that the method acquires correct positions of points as long as observed motion directions of objects are correct. The motion directions are stable against sensor noise, however, errors may crop up in a real en­ vironment . In such a case, several incorrect SCPs and 3PCs are acquired, and inconsistency arises among ac­ quired point positions. However, some of them can be eliminated by a statistical method since incorrect 3PCs are acquired relatively less times than correct ones (each 3PC is acquired multiple times with iterative observa­ tion).

We have verified the eliminat ion method with the same environment as Figure 14. In this simulation, ob­ servation errors of directions to objects are purposely generated. The errors are less than ±3 degrees, and motion directions are detected with a threshold of 2 de­ grees. On the average over five runs, 1,108 components have been acquired with 2,000 observations of motion directions, and 406 incorrect components are included. By using the error elimination method, we have obtained 679 components and reduced the number of the incor­ rect components up to 148. Thus, the method can elim­ inate considerable incorrect components. Note that the number of acquired components without the elimination method is more than that of the experimentation in sub­ section 4.2. This is because various SCPs are acquired on account of observation errors.

5 Conclusion

This paper has proposed a method for acquiring a quali­ tative spatial representation from qualitative motion in­ formation of moving objects. Key points of this paper are:

• Qualitative positions of landmarks are acquired from motion directions of objects, which are purely qualitative information.
• With constraint propagation, the positions of land­ marks in distant locations can be acquired if sensors are partially observable.

We have presented that the method is actually valid with simulations of acquiring the qualitative positions of mul­ tiple vision sensors. The method solves one of general and fundamental problems in robot navigation and map building.

Our future work includes developing a method to cope with correspondence error of objects observed from the multiple vision sensors as well as motion direction er­ ror. A statistical method is used for eliminating errors in the experimentation. On the other hand, geometrical approaches such as triangle constraints [Kim, 1992] will be useful for more effective error elimination.