Data merging and sorting method based on discrete contour evolution with application on slam.

Luca, Razvan ; Troester, Fritz ; Simion, Carmen 等

1. INTRODUCTION

Collecting data for further processing of algorithms used for fully autonomous driving represents a procedure based on specific application in the field of Simultaneous Localisation and Mapping. The real time processing of the data is considered a main premise for the project to reach the second layer of the development, the implementation on a scaled vehicle driven by a PC-104 system. We hereby present a method of data merging and sorting by simulating a SICK LD 1000 laser scanner. Our goal defines data reduction and sorting for the on-line incremental map building procedure.

The project application is relying on the capability of the designed system to be able to accomplish specific tasks that allows a driverless car to fully autonomously execute, for example, parking procedures on standard parking lots.

2. RELATED WORK

A very used approach to fit geometric primitives to range data acquired with mobile vehicles is the extraction of poly-lines. (Latecki & Lakamper, 1998) use a convexity approach to build line models. Their approach considers the uncertainty in the measurements when clustering points into linear segments. The approach developed by (Gonzales et al., 1994) computes point clusters based on the minimum distance between consecutive points. Linear regression is applied to fit lines to these clusters and iteratively combine lines to a global map.

Several approaches apply the well-known iterative end-point fit or split and merge algorithm for fitting lines to scans. (MacKenzie & Dudek, 1994) use a clustering strategy to associate measurements that arise from the same object. Then recursively subdivide these clusters to obtain subsets with good linear approximations. (Gonzalez-Banos & Latombe, 2000) extract poly-lines from range scans by exploiting the order of the individual beams given by the range scanner and applying a variant of iterative endpoint fit algorithm. A stochastic map approach is detailed as basic of introduction to autonomous mobile robots by (Siegwart & Nourbakhsh, 2004)

3. PROBLEM DELIMITATION

The modelling of the interfaces between the components of the system is done by considering an interchangeable data transfer by simply replacing the sensor modules simulated. In this sense the laser sensor data interface becomes equal to the interface of the ultrasonic sensors. In example a system of defined sensors can be attached to the virtual vehicle, capable of scanning the environment and delivering same data for further processing of the SLAM algorithms.

4. DATA MERGING AND SORTING

The Simulation environment created in Matlab/Simulink includes set up blocks representing the vehicle cinematic and control, a path-planning and a SLAM module. A function allows a transformation of the incoming sensor based data (detected points) from the local to the global reference coordinate system. The sensor data simulated comes out as an array of coordinates and is written using pointers to dynamically increase the array dimensions (1). The array is structured as following: DS1= [n, [x.sub.1], [y.sub.1] ... [x.sub.n], [y.sub.n]], where n is the number of points generated from the sensor by scanning the environment. Because of the applicability in the domain of vision, the Discrete Contour Evolution algorithm needs the input preprocessed by a Data Merging and Sorting Method (2). Within this we are considering two procedures. The first procedure is related to the number of scans which are acquired. In this sense we define a variable number of scans (n) and build up an array of points sorted rising by angle counterclockwise. After completing the n scans a trigger is sensed and data are further processed in the SLAM algorithm (3) as shown in figure 1. The output DS2 becomes a clustered matrix containing the poly-line information used in DCE.

The second procedure is based on applying the SLAM algorithm on a predefined number of points (m). In this case a buffer is created. The available points are merged and sorted (4) by angle, similar as described in the first procedure. The clustering begins directly after sorting by calculating the distance between successive points. Trough the triggered block (5) the values are sent to the SLAM processing block (6). The process stops when there is no object in the scanning range. The block structure is presented in figure 2.

[FIGURE 1 OMITTED]

[FIGURE 2 OMITTED]

5. POLY-LINES CREATION

The SLAM block consists of an implemented DCE algorithm able to compute poly-lines after clustering points by lowest distance criteria. The direction criterion of the lines is based on the convexity of shapes. The tested environment is a virtually generated parking place where the objects are represented simplified (A). The car like vehicle (B) is scanning by moving on a predefined path, relayed to the actual phase of the simulation development. A real time incremental map building is simulated. Figure 3 indicates the results of the poly-line formation.

The green marked circles on the object edges are points generated by the intersection of the sensor with the objects. These are unified by a red poly-line if the distance criterion is accomplished. Each poly-line represents a separate cluster. Separate points representing a higher distance then the one defined in the algorithm represent separate clusters and are not unified by poly-lines in this phase. The right order of joining points into lines and reducing the irrelevant mapping data becomes very important because of firstly reduced processing time and a correct shape construction. Considering shape information obtained by a range sensor, scanning the same object prom different position generates the effect of doubled data, which requires a merge and sorting before the poly-line creation.

The reduction of data becomes consistent when clustering points into linear segments. Only the beginning and ending points of the segments are held for further processing of the map. The defined structure of the map at this moment has the following data structure, each indexed row of the matrix defining a poly-line consisting on variable number of points (n, r) indicated at the beginning of the poly-line:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

[FIGURE 3 OMITTED]

The map data is being updated with new indexing poly-lines, when the scanning procedure starts over. The data output is defined as DS2 in our simulation environment and consists the input for the scan matching procedure.

6. CONCLUSION

Merging and sorting of data for line extraction originated from computer vision. The presented method was successfully implemented on a 2D simulation environment developed for autonomous vehicle systems. The data structure delivered by the method uses further application in the DCE algorithm with application on SLAM. However, we exploit even more context information than represented by a single poly-line considering shape as a structure of poly-lines.

7. FURTHER RESEARCH

The developed method of data merging and sorting applied on a DCE algorithm in the simulation environment brings benefit for further implementation of the second development layer, a scaled vehicle capable of dealing with laser and ultrasonic sensors for scanning an unknown environment. Further algorithms are to be implemented for map construction and poly-lines processing (i.e. linear regression) for simplification and matching of shapes.

Based on an estimation of the vehicle's position in its map, the shape perceivable according to it is computed. To localize the robot and update its map, parts perceived by the sensor need to be matched against those extracted from the map. (I.e.: iterative closest point algorithm).

The real time processing of data has to be considered while the implementation on a PC-104 system. The variety of perceivable shapes in a simulated scenario yields a reliable matching. At the same time, we are interested to construct a compact representation for an arbitrary environment by maintaining the parking lots characteristics.

Further, we are looking to integrate an algorithm responsible for object avoidance and for the calculation of the shortest path by including potential fields of the mapped objects.

The implementation of the SLAM algorithms is further important for the path-planning module because of the use of the same data.

8. REFERENCES

Gonzalez-Banos, H. & Latombe J.-C. (2000). Robot navigation for automatic model construction using safe regions, Available from: http://ai.stanford.edu/~latombe/papers/iser00/paper.pdf Accessed: 2009-01-20

Gonzales, J.; Ollero A. & Reina A. (1994). Map building for a mobile robot equipped with a 2d laser rangefinder, Available from: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber =351183&isnumber=8081 Accessed: 2009-02-11

Latecki, J. L. & Lakamper R. (1998). Convexity Rule for Shape Decomposition Based on Discrete Contour Evolution, Available from: http://www. cis.temple.edu/~latecki/Papers/cviu99.pdf Accessed: 2008-11-20

MacKenzie, P. & Dudek G. (1994). Precise positioning using model-based maps, Available from: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber =351359&isnumber=8081 Accessed: 2009-02-18

Siegwart, R. & Nourbakhsh, I. R. (2004). Introduction to Autonomous Mobile Robots, the MIT Press, ISBN 0-262-19502-X, Cambridge, Massachusetts