{'fraction_non_alphanumeric': 0.02820730671197961, 'fraction_numerical': 0.012192013593882754, 'mean_word_length': 4.627779105904853, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 5, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Novel Feature Extraction Algorithm for Outdoor Mobile Robot Localization

Navigation is one of the basic problems for autonomous mobile robots. Its history can be traced back to long time ago. Today, navigation is a well-understood quantitative science, used routinely in maritime and aviation applications [Adams, 1999]. Given this, the question must be asked as to why robust and reliable autonomous mobile robot navigation remains such a difficult problem. The core of the problem is the reliable acquisition or extraction of information about navigation beacons from sensor information and the automatic correlation or correspondence of these with some navigation map [Guivant et al., 2000]. Many navigation systems use artificial beacons to realize their navigation task, but the approach may not be realistic in applications such as exploration of jungles or other unknown environments. In this situation, one needs to utilize naturally occurring structure of typical environments to achieve a similar performance. Hence, fast and reliable algorithms capable of extracting features from a large set of noisy data are important in such applications. Some of the early efforts in this direction have focused on extracting line features in an indoor environment based on the information provided by sonar and laser sensors. In [Crowley, 1985], a least-squares line fitting technique was applied to extract edges from ultrasonic sensor data. In [Taylor & Probert, 1996], a recursive line fitting system is used to extract line segments under polar coordinates and an ellipse fitting method is also implemented for data from a laser sensor. In [Vandorpe et al., 1996], line segments are detected using a regression least-squares parameter estimation method whereas the center and radius of a circle feature are estimated based on the average value of the measurements of the circle from a 2D range scanner. Later, a two-layer Kalman filter was used to calculate the parameters of a line by an on-line method in [Roumeliotis & Bekey, 2000]. Observe that the aforementioned articles are focused on indoor applications and are mainly concerned with line extraction. For an outdoor environment, the problem of feature selection and detection is more challenging. In our view, in most typical semi-structured outdoor environments, such as campuses, parks and suburbs, tree trunks and tree-like objects, such as pillars, are relatively stable, regular and naturally occurring features that can provide very useful information for mobile robot navigation. Recently, some research on the use of these kinds of geometrical features has been carried out in [Guivant et al., 2002]. Also, [Guivant et al., 2002; Bailey, 2002] addressed the problem of extracting tree trunks from laser scan data where the centre and radius of a circle are estimated by averaging the measurements. This method can be

Navigation is one of the basic problems for autonomous mobile robots. Its history can be traced back to long time ago. Today, navigation is a well-understood quantitative science, used routinely in maritime and aviation applications [Adams, 1999]. Given this, the question must be asked as to why robust and reliable autonomous mobile robot navigation remains such a difficult problem. The core of the problem is the reliable acquisition or extraction of information about navigation beacons from sensor information and the automatic correlation or correspondence of these with some navigation map [Guivant et al., 2000]. Many navigation systems use artificial beacons to realize their navigation task, but the approach may not be realistic in applications such as exploration of jungles or other unknown environments. In this situation, one needs to utilize naturally occurring structure of typical environments to achieve a similar performance. Hence, fast and reliable algorithms capable of extracting features from a large set of noisy data are important in such applications. Some of the early efforts in this direction have focused on extracting line features in an indoor environment based on the information provided by sonar and laser sensors. In [Crowley, 1985], a least-squares line fitting technique was applied to extract edges from ultrasonic sensor data. In [Taylor & Probert, 1996], a recursive line fitting system is used to extract line segments under polar coordinates and an ellipse fitting method is also implemented for data from a laser sensor. In [Vandorpe et al., 1996], line segments are detected using a regression least-squares parameter estimation method whereas the center and radius of a circle feature are estimated based on the average value of the measurements of the circle from a 2D range scanner. Later, a two-layer Kalman filter was used to calculate the parameters of a line by an on-line method in [Roumeliotis & Bekey, 2000]. Observe that the aforementioned articles are focused on indoor applications and are mainly concerned with line extraction. For an outdoor environment, the problem of feature selection and detection is more challenging. In our view, in most typical semi-structured outdoor environments, such as campuses, parks and suburbs, tree trunks and tree-like objects, such as pillars, are relatively stable, regular and naturally occurring features that can provide very useful information for mobile robot navigation. Recently, some research on the use of these kinds of geometrical features has been carried out in [Guivant et al., 2002]. Also, [Guivant et al., 2002;Bailey, 2002] addressed the problem of extracting tree trunks from laser scan data where the centre and radius of a circle are estimated by averaging the measurements. This method can be susceptible to outliers which can significantly affect the accuracy of the center and radius estimates. In this paper, we shall address the problem of extracting edge and circle features for semistructured outdoor mobile robot navigation. We classify features into edges, circles and random clutter and propose an approach for their extraction. First, a model based data segmentation method is applied which divides the collected data into groups that are possibly associated with different features of the environment. The extended Kalman filter or other filtering techniques can be applied for segmentation. Edges are also detected during segmentation. We then give a procedure to identify the type of features with which a given group of data is associated. For a circle feature, a modified Gauss-Newton optimization is proposed to obtain estimates of its centre and radius. Several experiments are carried out to demonstrate the feasibility and effectiveness of the proposed feature extraction method. In the experiments, the data association method proposed in [Zhang et al. 2005] is used to enhance the robustness of features. The results show that our method for feature extraction is implementable in real-time and outperforms existing methods such as that in [Bailey, 2002]. The structure of the paper is as follows: Section 2 presents our feature extraction algorithm, and section 3 shows the experimental results using the proposed algorithm in several outdoor environments. Conclusions are drawn in Section 4.

Feature Extraction Algorithm
We observe that in many semi-structured outdoor environments, planes such as building walls and cylindrical surfaces such as tree trunks or tree-like objects are often encountered. We consider two kinds of features for these semi-structured environments. Observe that in most outdoor environments, trees or tree trunks can be very useful features for mobile robot navigation. In [Guivant et al., 2002;Bailey, 2002], the problem of extracting circle features was addressed by averaging their measurements. Here, we shall propose an algorithm which is able to extract edges and tree trunks with a higher accuracy. The essential components of this algorithm include two parts: the first is the segmentation of the scan data and the second is the parameter acquisition.

Segmentation and Edge Detection
Segmentation is a process of aiming to classify a set of scan data into several groups, each of which possibly associates with different structures of the surroundings. The segmentation process is realized through the EKF [Adams, 1999;Zhang et al. 2003;Zhang et al. 2004a] or other filtering techniques. At each time instant the range estimate is compared to the range measurement based on their statistics in order to decide if an edge has been detected. When the difference between the measured range and the predicted range is beyond a certain threshold, we consider that an edge has been detected. This can be achieved by using a validation gate during the prediction process with the EKF.

Planar Model
Let us first introduce a mathematical framework for a planar surface. Consider a vertical plane shown in Fig. 1 and the corresponding sensed data points from a perfect 3D line of the sight sensor. Similar to the description in [Adams, 1999] where γ is the constant angle between successive samples of the sensor as it rotates about its vertical axis. Note that the relationship given in equation (1) is independent of the elevation angle α .  (1) can be fully defined by the state space equations: is the process noise which reflects possible imperfection of the surface. We assume that v is a white noise with variance () k Q . Clearly, a small variance () k Q implies that the surface is close to be perfect. In the experiments in this paper, we set (2) represents a system model which will be used to predict the next range value from the sensor before the actual range measurement is recorded. Similar to [Adams, 1999], our observation model is: and () k w is a zero mean Gaussian noise with a known variance 2 r σ . The EKF is used to realize the prediction and validation process. Note that if the degenerate case (almost parallel) is detected, we suggest that these measurements can be rejected.

Extended Kalman Filter and Validation Gate
Based on the above system model, an extended Kalman filter is used to implement the prediction and update. In order to identify if a measurement is associated with a new edge (large discontinuity), certain criterion needs to be established. Use the innovation (1 ) k ν + and the innovation variance (1 ) k + s to define: Note that since ν is a Gaussian random variable, d is a random variable following the 2 χ distribution. The smaller the (1 ) dk+ , the higher the probability that the measurement (1 ) zk+ is obtained from the same planar surface. Thus, a validation gate, δ , is used to decide whether the measurement (1 ) zk+ is a close enough match to the predicted data point to continue the filter update. If the measurement is such that (1 ) dk δ +> , a discontinuity is found. From the 2 χ distribution table, we know that if the observation is from the same planar surface, then (1 ) 6 6 3 dk+< . with a probability of 099 . . If a small δ is selected, there will be more edges found. Here we set 663 δ =. .
After the data segmentation process, we need to decide if each segment of data is associated with a line or a circle (note that the laser sensor data points only form an arc which is part of a circle, here we call it a circle feature) or a clutter. For a line, the average error between the observation and the EKF prediction at each point should be very small. Note that the prediction error (innovation) sequence {} ν of (5) is a Gaussian white noise and its covariance is given by () k s . Assume that the number of points of the segment is M . Then the sequence {} ν is of the length 2 M − (note that the first two pints are used to initialize the filter). The average prediction error and its covariance are then given by . A threshold for the average prediction error can be chosen as associated with a line, otherwise, it is associated with a circle or a clutter. It is noted that if a circle shape clutter is detected as a circle feature after several successive scans, the circle shape clutter is the same as a circle feature. If after several successive scans, we can't detect the circle feature that is found in the previous scans, the feature detected should be a circle shape clutter. For a circle, we shall need to estimate its parameters such as the center and the radius of the circle so that future measurements of the circle may be used for robot navigation. In the following, the modified Gauss-Newton method [Dennis & Schnabel, 1983] is applied.

Parameter Acquisition
A circle can be defined by the equation This is equivalent to performing the least-squares process using the equations The equation (7) is not linear about the unknown parameters 0 x , 0 y , and r, therefore it is a nonlinear least-squares problem. We propose to use the modified Gauss-Newton optimization method [Dennis and Schnabel, 1983] to solve the problem. In our case the Jacobian matrix for the modified Gauss-Newton algorithm is with m g as defined in (7). At the k -th step, using the modified Gauss-Newton method to search the solution according to the following equation: at the k -th iteration. We set the initial value 0 001 λ =. and carry out the following iterations for calculating a suboptimal p : Step 1: Calculate k p using equation (9); Step 2: Calculate the sum error () kk Ep p + by equation (6); www.intechopen.com Step 3: Compare with the sum error of last step ()  and go back to Step 1 until the algorithm converges.
The convergence condition can be defined by the sum of the error square and the number of iterations.
Observe that a starting guess for these parameters is required. We use the first three points ()1 2 3 ii xy i ,= , , and (7) to compute an estimated initial value of 00 () x yr ,, . The more accurate the initial value is, the faster the algorithm converges. Remark 1. Note that the Hough transform is commonly used for parameter acquisition and segmentation [Iocchi & Nardi, 2002]. The transform is implemented by quantizing the Hough parameter space into finite accumulator cells. As the algorithm runs, each point is transformed into a discretized curve and the number of intersections of the accumulator cells is counted. However, the problem of how to decide the number of the cells in the parameter space remains unsolved. If the Hough transform is applied for fitting a circle, the parameter space is of three dimensions, which makes the problem more difficult. And with the increased dimension of the parameter space, the Hough transform method becomes more complex and slower. Hence, we use the modified Gauss-Newton method instead of the Hough transform for parameter acquisition. Remark 2. In our algorithm, since each group of data is formed after data segmentation, any outlier of measurements has been removed since an outlier produces a large discontinuity in segmentation. On the other hand, in complex outdoor environments, features extracted by the above proposed method may become unstable. In order to use these features for navigation, the correspondence between a current feature extracted by the above method and a feature in the map built thus far has to be established. This is the so-called data association problem. In this paper, we apply the data association algorithm proposed in [Zhang et al. 2005;Zhang et al. 2004b] where the problem is formulated as a (0,1) integer programming one and solved by a combined linear programming and iterative heuristic greedy rounding (IHGR) method. The details can be found in [Zhang et al. 2004b] and will not be repeated here. Remark 3. For the proposed algorithm, if the angular uncertainty is considered, the feature detection algorithm results will be improved.

Experimental Results
The laser sensor used in the following experiments is Sick PLS200. The field of view is 180 degrees in front of the robot and up to 50 meters of distance. To obtain a 360 degree scene, we use 2 back to back Sick sensors. The range samples are spaced every half a degree, all within the same plane.
In the first experiment, data is collected outdoors as shown in Fig. 2 (a) where there are 10 pillars labeled from a to j , and the surroundings are building walls and low balusters with small shrubs at a long distance. In this figure, the six cross points represent the six positions at which the robot scans the surroundings. The laser scanner is placed on the top of a mobile robot at approximately 1.2 meters above the ground. At this level, the sensor can see the object outside the balusters. In Fig. 2 (b), we show the real data from one scan of the www.intechopen.com environment. The origin is the place at which the robot is located. Because the distance is very near to the sensor around the origin, the points here are not very regularly distributed. We have done the feature extraction for all the 6 scans. Here we show the feature extraction results at two different positions. The results are given in Fig. 3 to Fig. 4. Fig. 3 (a) and Fig. 3 (b) show the feature extraction results at position 2 using the proposed method of the last section. Zoomed views of the regions inside the dashed box of Fig. 3(a) are given in Fig. 3(b) where the extracted features can be seen clearly. In these figures, the detected edges are denoted by crosses. Similarly, the feature detection results at position 4 are shown in Fig. 4.   Fig. 3 (a) www.intechopen.com Figure 4(a). Circles and edges extracted from data scanned at position 4 (the normal view) Figure 4 (b). A zoomed view of the region inside box C in Fig. 4(a) www.intechopen.com

b). A zoomed view of the region inside box A in
To give an indication of the accuracy of the algorithm, we compare our method with some existing method. In the work by Bailey [Bailey, 2002], navigation methods are presented which use circular features from trees. We calculate the relative errors of the estimated center coordinates and radius of each pillar as follows:  Table 1. A comparison of the error CE of the four circle features between the proposed method and the method in [Bailey, 2002] pillar d pillar e pillar f pillar g  Table 2. A comparison of the error RE of the four circle features between the proposed method and the method in [Bailey, 2002] From the above tables, we can see that the proposed method is more accurate than the method in [Bailey, 2002]. In order to test the feature extraction method for localization, the outdoor experiment has also been carried out for simultaneous localization and map building using the proposed feature extraction algorithm. The experimental environment is shown in Figure 6. There are 8 tall trees and building walls and some bushes which constitute the semi-structured outdoor environment. For this semi-structured environment, the main features for localization are tree trunks. The proposed feature extraction algorithm is applied for extracting the features. The vehicle used in the experiment is Cycab, a car-like vehicle, as shown in Figure 5. It is equipped with a laser range sensor, Sick LMS 200, with dead reckoning capabilities. There are four encoders fixed on the wheels of the vehicle. A DGPS with up to 2cm accuracy is used as a reference to give the ground truth of the vehicle pose to get the estimation error. In the experimental environment, the vehicle moves along the path as shown in Figure 7 where the stars denote the trees of the environment which are detected, the dashed line indicates the real pose of the vehicle and the solid line means the estimated path using the simultaneous localization and mapping algorithm with the proposed feature extraction method. The data association method in the implementation is the same as that in [Zhang et www.intechopen.com al. 2005]. Figure 8 shows a typical laser scanner frame. The dashed line box A indicates the region whose clearer view is shown in Figure 9. In these two figures, we can find that there are lines, arcs and edges (point features). However, in the experiment, we only use circle features from the tree trunks for localization. The 8 features are all detected during the SLAM process after the continuous observation. It should be noted that there are additional features that are detected in some scans, but they haven't been used for the SLAM more than 3 times, we didn't draw them in the map. To make a comparison on feature extraction performance, we also implement the method in [Bailey, 2002]. Figure 10 shows the range and bearing innovations of the measurements when we apply the feature extraction method in [Bailey, 2002] and our method during the SLAM and their 3σ bounds. The dash-dot line in the middle of each sub-figure is the result of the localization using our proposed feature detection method whereas the solid one in the middle is the result of the localization by the feature detection method in [Bailey, 2002].  Table 3 below.
Proposed method Method in [Bailey, 2002] x Δ We also test the detectability of the features by these two methods. We calculated 4 different scan sets' feature extraction false detection rate (the ratio of the number of false features to the total number of detected features in a scan) as shown in Table 4.  Table 4. A comparison of the false detection rate between the proposed method and the method in [Bailey, 2002]    From the table, we know that the detectability of the method in [Bailey, 2002] is a little better than our method. However, in both algorithms, the features can be mostly detected for the localization purpose. From this point of view, Bailey's approach is more general than ours for the irregular circles' detection in some cases. However, the false detection rates of both the two algorithms are considered to be low. It should be noted that there are false features that are detected in some scans, but they have not been used for the SLAM more than 3 times. Hence, we did not draw them in the map.

Conclusions
In this paper a new algorithm for feature detection in semi-structured outdoor environments has been presented. It can be used for the extraction of planar surfaces, tree trunks or tree-like objects and edges in semi-structured outdoor environments for mobile robot navigation. Experimental results show that the proposed method can extract features for navigation purposes successfully. In this book, new results or developments from different research backgrounds and application fields are put together to provide a wide and useful viewpoint on these headed research problems mentioned above, focused on the motion planning problem of mobile ro-bots. These results cover a large range of the problems that are frequently encountered in the motion planning of mobile robots both in theoretical methods and practical applications including obstacle avoidance methods, navigation and localization techniques, environmental modelling or map building methods, and vision signal processing etc. Different methods such as potential fields, reactive behaviours, neural-fuzzy based methods, motion control methods and so on are studied. Through this book and its references, the reader will definitely be able to get a thorough overview on the current research results for this specific topic in robotics. The book is intended for the readers who are interested and active in the field of robotics and especially for those who want to study and develop their own methods in motion/path planning or control for an intelligent robotic system.

How to reference
In order to correctly reference this scholarly work, feel free to copy and paste the following: