Building Fuzzy Elevation Maps from a Ground-based 3D Laser Scan for Outdoor Mobile Robots

Building Fuzzy Elevation Maps from a Ground-based 3D Laser Scan for Outdoor Mobile Robots Anthony Mandow, Tomás J. Cantador, Antonio J. Reina, Jorge L. Martínez, Jesús Morales, and Alfonso García-Cerezo Universidad de Málaga – Andalucía Tech Departamento de Ingeniería de Sistemas y Automática, 29071 Málaga, Spain. Email: amandow[@]uma.es Abstract - The paper addresses terrain modeling for mobile robots with fuzzy elevation maps by improving computational speed and performance over previous work on fuzzy terrain identification from a three-dimensional (3D) scan. To this end, spherical sub-sampling of the raw scan is proposed to select training data that does not filter out salient obstacles. Besides, rule structure is systematically defined by considering triangular sets with an unevenly distributed standard fuzzy partition and zero order Sugeno-type consequents. This structure, which favors a faster training time and reduces the number of rule parameters, also serves to compute a fuzzy reliability mask for the continuous fuzzy surface. The paper offers a case study using a Hokuyo-based 3D rangefinder to model terrain with and without outstanding obstacles. Performance regarding error and model size is compared favorably with respect to a solution that uses quadric-based surface simplification (QSlim). Keywords: Elevation maps, mobile robots, 3D scanners, fuzzy modeling ___________________________________________________________________________________________________ This is a self-archiving copy of the author’s accepted manuscript. The final publication is available at Springer via http://link.springer.com/book/10.1007/978-3-319-27149-1. Citation Information: Mandow, A; Cantador, T.J.; Reina, A.J.; Martínez, J.L.; Morales, J.; García-Cerezo, A. "Building Fuzzy Elevation Maps from a Ground-based 3D Laser Scan for Outdoor Mobile Robots," (2016) Advances in Intelligent Systems and Computing, vol. 418.   @ARTICLE{Mandow:2016, author={Mandow, A and Cantador, T.J. and Reina, A.J. and Martínez, J.L. and Morales, J. and García-Cerezo, A.}, title={Building Fuzzy Elevation Maps from a Ground-based {3D} Laser Scan for Outdoor Mobile Robots}, journal={Advances in Intelligent Systems and Computing}, year={2016}, volume={418}, } __________________________________________________________________________________________ © 2015 by the authors. Building Fuzzy Elevation Maps from a Ground-based 3D Laser Scan for Outdoor Mobile Robots Anthony Mandow, Tom´as J. Cantador, Antonio J. Reina, Jorge L. Mart´ınez, Jes´us Morales, and Alfonso Garc´ıa-Cerezo Universidad de M´alaga, Andaluc´ıa Tech Dpto. Ingenier´ıa de Sistemas y Autom´atica, 29071 M´alaga, Spain [email protected];http://www.uma.es/isa Abstract. The paper addresses terrain modeling for mobile robots with fuzzy elevation maps by improving computational speed and performance over previous work on fuzzy terrain identification from a threedimensional (3D) scan. To this end, spherical sub-sampling of the raw scan is proposed to select training data that does not filter out salient obstacles. Besides, rule structure is systematically defined by considering triangular sets with an unevenly distributed standard fuzzy partition and zero order Sugeno-type consequents. This structure, which favors a faster training time and reduces the number of rule parameters, also serves to compute a fuzzy reliability mask for the continuous fuzzy surface. The paper offers a case study using a Hokuyo-based 3D rangefinder to model terrain with and without outstanding obstacles. Performance regarding error and model size are compared favorably with respect to a solution that uses quadric-based surface simplification (QSlim). Keywords: Elevation maps, mobile robots, 3D scanners, fuzzy modeling 1 Introduction Environment mapping is a key issue in mobile robots targeted to unstructured terrains [1, 2]. In this sense, three-dimensional (3D) laser scans provide valuable information for applications such as planetary exploration [3–5] or urban search and rescue [6, 7]. However, as point clouds require coping with a huge amount of spatial data, a simplified and compact representation of navigable terrain is necessary for both motion planning [8] and tele-operation [9]. Elevation maps offer a compact 2.5-dimensional model of terrain surface. In robotics, elevation has been generally represented by regular grids [10–12] or by irregular triangular meshes [4, 13]. Removal of artifacts and mesh simplification algorithms, like mesh decimation [14] and quadric-based polygonal surface simplification (QSlim) vertex clustering [15], can improve the compactness and reliability of these maps [8]. Nevertheless, as tesselated models have limitations in the face of incomplete and uncertain sensor data, some works have proposed 2 A. Mandow et al. using tools that can model elevation in a more robust and natural way. In geographic information systems (GIS), fuzzy logic has been applied to elevation maps for incorporating height uncertainty [16] and assessing visibility between pairs of points [17]. In mobile robotics, elevation grids have been processed with fuzzy rules to assess traversability [18, 19]. Gaussian processes have also been proposed to model terrain from uncertain and incomplete sensor data [20]. Adaptive Network-based Fuzzy Inference Systems (ANFIS) [21] has been employed to recognize objects like trees and buildings from aerial stereo images [22]. Moreover, ANFIS was preliminarily proposed to obtain fuzzy elevation maps of natural terrain from ground-based 3D data [23]. These elevation maps have been already employed for assessing traversability and local path planning [24]. The main contribution of this paper is extending [23] to improve computational speed and performance. To this end, two major modifications have been introduced: i) spherical sub-sampling [25] is used to select proper training data from a raw point cloud, and ii) rule parameters have been systematically defined by considering triangular sets with standard fuzzy partition [26] as well as zero order Sugeno-type inference. Furthermore, the capability to model a salient obstacle on the terrain surface has been considered in a case study using a 3D Hokuyo-based range-finder. Besides, performance regarding error and computation time are compared with a solution based on the QSlim algorithm. Following this introduction, section II presents the fuzzy terrain modeling method. Then, section III describes the experiments including comparisons with QSlim. Finally, Section IV offers conclusions and future work. 2 Fuzzy terrain modeling method The proposed fuzzy terrain modeling method is outlined in Fig. 1. The input is a range image from a single 3D scan. It is assumed that the local frame of the 3D rangefinder has its Yand Zaxes pointing forwards and upwards, respectively (see Fig. 2). The goal of the method is producing a local elevation map in which ground surface can be represented as a function z=H(x, y), where xand yare the Cartesian coordinates on the XY plane and zis the corresponding elevation. The following subsections develop the major parts of this algorithm. Reduced 3D Point Cloud Binary Occupancy Matrix Fuzzy Elevation Map Fuzzy Reliability Mask Raw 3D Range Image Spherical Subsampling ANFIS Training ANFIS Training Reliable Fuzzy Region Fig. 1. Fuzzy point cloud terrain modeling algorithm. Building Fuzzy Elevation Maps from a Ground-based 3D Laser Scan 3 2.1 Point sub-sampling The purpose of point sub-sampling is to produce a reduced set of representative training points in Cartesian coordinates (x, y, z). The reason for sub-sampling is twofold: improving the speed of fuzzy identification and homogenizing the spatial distribution of training data. In [23], sub-sampling was performed by selecting the highest point within grid cells of a sufficiently high resolution. This approach provides a representative set of points for a smooth terrain but is not so effective to model salient obstacles, such as tree trunks or rocks, which can be filtered by the fuzzy identification method when represented by a small number of samples. Furthermore, finding the maximum value within each cell entails the computational load of processing all scan points in Cartesian coordinates. Alternatively, spherical sub-sampling [25] performs a fast range-independent data reduction for 3D rangefinders that combine a 2D scan with an additional rotation, as usually found in mobile robots [27]. Moreover, by equalizing the measure-direction density, spherical sub-sampling maintains a proportion of measurements accumulated by salient obstacles, so their contribution can be relevant when adjusting a fuzzy surface. Thus, Cartesian coordinates are only computed for sub-sampled points. The field of view of the 3D sensor is defined by the scope of both scan angles: Φfor the 2D scan and Ψfor the additional rotation, as shown in Fig. 2(left). Then, angular resolution is given by Δφ and Δψ for the first and second rotations, respectively. The amount of data reduction of spherical sub-sampling is established by an equalization factor 0 <p≤1. The equalized angular resolution of the sub-sampled scan (see Fig. 2(right)) is given by Δθsas: Δθs=max(Δψ, Δφ) p.(1) In this way, by setting p= 1, the measure-direction density is equalized with the coarsest resolution (either Δφ or Δψ) actually provided by the sensor. Z < ) X Y Z < ) 'T s X Y Fig. 2. Measure-direction density. Left: raw scan; right: spherical point sub-sampling. 4 A. Mandow et al. 2.2 Neuro-Fuzzy Training The set of sub-sampled Cartesian points is used to adjust a fuzzy model z= H(x, y). Particularly, neuro-fuzzy ANFIS modeling [21] is adopted to identify a fuzzy model with Sugeno inference. ANFIS yields the rule consequents for a given fuzzy structure where membership functions (MFs) have to be specified for each input variable. The definition of MFs has an impact on the model size; i.e., on the number of parameters. One interesting property of the standard fuzzy partition (SPF) is that triangular or trapezoidal MFs share parameter values with neighbor MFs [26]. In an SPF, the ith MF Fidefined for a given variable uin the universe U is convex, normal, and it only overlaps with its neighboring fuzzy sets, in such a way that: ∀u∈U,  ∀i Fi(u)=1.(2) When defining the fuzzy structure, a greater number of MFs improves terrain adjustment at the cost of processing a greater number of rules. This conflict can be coped with by considering that higher detail is more important for the regions that are closest to the robot. Thus, an uneven membership function distribution can provide an appropriate fuzzy structure if the density of MFs for variables x and yis specified depending on the distance to the sensor [23]. Let us define the universe Ux=[−umax,u max] for variable x,andUy= [0,u max]fory, which corresponds to a 2umax ×umax rectangular area in the forward direction of the sensor. Then, uneven SPF MFs can be defined by computing the peak parameter fiof each triangular MF Fi(i.e., Fi(fi) = 1) as: fi=sign(i)r|i|−1 rk−1umax (3) where r>1 is the expansion ratio and i=−k, ..., 0,1, ..., k for the xvariable and i=0,1, ..., k for y. This definition yields (2k+1) MFsforxand (k+1) MFs for y. This means (2k+1)×(k+ 1) rules. Furthermore, the order of Sugeno inference affects training time as well as the number of rule parameters. In [23], first-order consequents Giwere considered for every rule ias: Gi(x, y)=ai+bix+ciy, (4) where three parameters (ai,b i,c i) per rule had to be identified. Alternatively, using zero-order Sugeno consequents: Gi(x, y)=ai(5) requires just one parameter per rule, as bi=ci= 0. First order Sugeno can be useful for ome applications, like interpolating between piecewise linear controllers, but zero-order consequents can provide good accuracy when approximating nonlinear functions [28]. Furthermore, the output of a zero-order Sugeno model is smooth as long as neighboring MFs in the antecedents are overlapped, as in SPF [29]. Therefore, zero-order Sugeno consequents are proposed as an effective solution for this application. Building Fuzzy Elevation Maps from a Ground-based 3D Laser Scan 5 2.3 Fuzzy Reliability Mask ANFIS renders a fuzzy surface that can be evaluated for any (x, y)pairinthe universe of discourse. This surface filters sensor noise and interpolates missing data from small shadowed areas but can provide erroneous estimations in larger regions with no input data. Since shadowed regions are frequent in groundbased scans of natural terrain proper use of the elevation map requires reliability assessment, which is a fuzzy concept in itself. A fuzzy reliability mask is proposed as a continuous function v=V(x, y), where v∈[0,1] for inputs x∈Uxand y∈Uy. This function can be trained with ANFIS with the same fuzzy structure as in the elevation map. For this purpose, an occupancy binary matrix is computed from the sub-sampled points. This matrix represents an XY grid with a uniform resolution δ,whereones and zeroes are assigned to cells with or without points, respectively. Then, the training data consists of the set of all matrix values with the corresponding cell center XY coordinates. In the resulting fuzzy model, values of v=V(x, y)close to one indicate high reliability of H(x, y), whereas values close to zero mean unreliable regions. 3 Experimental results 3.1 Experimental Setup This section discusses the application of fuzzy elevation modeling using 3D range images from a natural terrain —see Fig. 3(left). Four different scans obtained from the same sensor pose are considered: without obstacles, and with a person standing at three different positions with respect to the sensor frame: close-front, at a distance of 2.94 m with approximate XY coordinates (0.05m,2.94m); closeside,at3.94 m with (3.49m,1.83m); and far,at7.26 m with (−0.14m,7.26m). Computations have been performed by a QuadCore Intel Core i7 at 2.2GHz under the Matlab environment, whose Fuzzy Toolbox includes ANFIS. Range images have been obtained with a 3D laser scanner built by pitching a Hokuyo UTM-30LX 2D rangefinder [30] —see Fig. 3(right). This device has the following specifications: 270◦×135◦field of view; measurable ranges between Fig. 3. Experimental setup. Left: outdoor scene; right: 3D laser rangefinder. 6 A. Mandow et al. 0.1 m and 30 m; horizontal resolution Δφ =0.25◦; and vertical resolution Δψ is adjustable from 0.067◦to 4.24◦. The scan times at minimum and maximum resolution are 1.54 s and 95.75 s, respectively. In particular, 3D scans have been obtained with Δψ =0.278◦, which is similar to Δφ, with the sensor standing 1.0 m above the ground. This configuration produces range images with a maximum of 505036 points in 12.43 s. 3.2 Fuzzy Performance Evaluation Performance of the proposed method has been studied for different rule numbers and sub-sampling rates. Two different fuzzy rule structures are considered by using (3) with r=1.3 and a universe of discourse umax = 10 m: First, k=7 yields 15 ×8 rules, and second, k= 3 results in 7 ×4 rules. As for training data, several pvalues are compared for spherical sub-sampling. Besides, Cartesian points whose coordinates fall out of the 20 m ×10 m rectangular area have been discarded. Fig. 4 illustrates training data for the close-front obstacle case with no sub-sampling and with p=0.5. The root mean squared error (RMSE) given in Table 1 has been computed from the difference between the Zvalue of all raw scan points within the universe of discourse and the corresponding fuzzy model elevation. As expected, the RMSE for the 15 ×8 rulebase is better than the 7 ×4 model. Besides, fuzzy surfaces improve RMSE for smooth terrain, i.e., with no close salient obstacles. On Table 1. Effect of spherical sub-sampling on ANFIS performance. ObspTraining No. RMSE Time ObspTraining No. RMSE Time tacle points of rules (m2)(s)tacle points of rules (m2)(s) None - 186767 15 ×8 0.0237 176.00 Far - 185673 15 ×8 0.0369 174.00 7×4 0.0413 116.00 7×4 0.0558 117.00 1 115423 15 ×8 0.0237 83.63 1 114768 15 ×8 0.0369 80.84 7×4 0.0420 50.63 7×4 0.0563 47.84 0.75 65019 15 ×8 0.0238 43.33 0.75 64666 15 ×8 0.0369 41.32 7×4 0.0421 21.33 7×4 0.0564 20.32 0.5 28916 15 ×8 0.0238 22.07 0.5 28770 15 ×8 0.0370 21.12 7×4 0.0421 9.07 7×4 0.0564 9.12 0.1 1180 15 ×8 0.2568 11.90 0.1 1168 15 ×8 0.4484 10.96 7×4 0.0451 5.90 7×4 0.0642 5.96 Close - 187600 15 ×8 0.0951 177.00 Close - 189688 15 ×8 0.0871 174.00 -side 7×4 0.1283 115.00 -front 7×4 0.1259 119.00 1 115525 15 ×8 0.0955 80.87 1 117941 15 ×8 0.0879 87.65 7×4 0.1295 48.87 7×4 0.1262 50.65 0.75 65122 15 ×8 0.0955 40.33 0.75 66465 15 ×8 0.0872 44.26 7×4 0.1295 20.33 7×4 0.1262 21.26 0.5 28939 15 ×8 0.0956 21.07 0.5 29554 15 ×8 0.0872 23.05 7×4 0.1295 9.07 7×4 0.1262 10.05 0.1 1174 15 ×8 0.1580 10.89 0.1 1206 15 ×8 0.1568 11.19 7×4 0.1305 4.89 7×4 0.1495 5.19 Building Fuzzy Elevation Maps from a Ground-based 3D Laser Scan 7 − 10 −9 −8 −7 −6 −5 −4 −3 −2 −1 012345678910 0 1 2 3 4 5 6 7 8 9 10 −3 −2 −1 0 1 x(m) y(m) z(m) − 10 −9 −8 −7 −6 −5 −4 −3 −2 −1 012345678910 0 1 2 3 4 5 6 7 8 9 10 −3 −2 −1 0 1 x(m) y(m) z(m) Fig. 4. Training points of the close-front obstacle scene. Top: raw scan points; Bottom: spherical sub-sampling with p=0.5. the other hand, the sub-sampling rate has an important effect on computation time, but it does not generally produce important RMSE differences within the same rule structure and scene. This indicates that spherical sub-sampling gives a representative subset of the complete scan. The only exception to these results is with 15 ×8 rules and sub-sampling factor 0.1, where the 120-rule fuzzy model is overadjusted to a small data sample (around 1200 points, which is only about 0.6% of the raw data set). From this analysis, if fast rough terrain model is needed, the 7×4rulemodel with 0.1 sub-sampling could offer an appropriate solution. For a compromise between acceptable model accuracy and computation time, good results are given by the 15 ×8 rule model with 0.5 sub-sampling (see Fig. 5). 3.3 Comparison with QSlim The proposed method has been compared with a QSlim-based solution. QSlim [15] performs mesh surface simplification by iterative contraction of vertex pairs using plane-based error quadrics. QSlim has been employed for terrain simplification of topographical maps [31, 32]. However, QSlim cannot be directly applied to the Delaunay mesh corresponding to raw ground-based scans because of artifacts due to shadows and salient objects [8]. Therefore, preprocessing is necessary to produce a proper surface to start with. In this paper, a proper Delaunay mesh is built from the XY coordinates of the maximum height points within grid cells of resolution δ=0.1 m. The resulting mesh has been fed to the QSlim algorithm to produce models with both 100 and 1000 faces, as illustrated by Fig. 6. 8 A. Mandow et al. Table 2 compares results obtained with the proposed method, the solution proposed in [23], and the QSlim approach. QSlim is an efficient method, so most of the computation time corresponds to preprocessing. As this preprocessing is −10 −9 −8 −7 −6 −5 −4 −3 −2 −1 012345678910 0 1 2 3 4 5 6 7 8 9 10 −3 −2 −1 0 1 x(m) y(m) z(m) −10 −9 −8 −7 −6 −5 −4 −3 −2 −1 012345678910 0 1 2 3 4 5 6 7 8 9 10 −3 −2 −1 0 1 x(m) y(m) z(m) Fig. 5. Fuzzy elevation maps of the close-front obstacle scene. Top: p=0.1and7×4 rules; bottom: p=0.5and15×8rules. −10 −9 −8 −7 −6 −5 −4 −3 −2 −1 012345678910 0 1 2 3 4 5 6 7 8 9 10 −3 −2 −1 0 1 x(m) y(m) z(m) −10 −9 −8 −7 −6 −5 −4 −3 −2 −1 012345678910 0 1 2 3 4 5 6 7 8 9 10 −3 −2 −1 0 1 x(m) y(m) z(m) Fig. 6. QSlim maps of the close-front obstacle. Top: 100 faces; bottom: 1000 faces.