A comparison of line extraction algorithms using 2D laser rangefinder for indoor mobile robotics
Published 1 January 2005Open access
Văn Đức Nguyễn, Agostino Martinelli, N. Tomatis, Roland Siegwart
Citations324
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Six popular algorithms in mobile robotics and computer vision are selected and tested, and several comparison criteria are proposed and discussed to highlight the advantages and drawbacks of each algorithm, including speed, complexity, correctness and precision.
Abstract
This paper presents an experimental evaluation of different line extraction algorithms on 2D laser scans for indoor environment. Six popular algorithms in mobile robotics and computer vision are selected and tested. Experiments are performed on 100 real data scans collected in an office environment with a map size of 80m /spl times/ 50m. Several comparison criteria are proposed and discussed to highlight the advantages and drawbacks of each algorithm, including speed, complexity, correctness and precision. The results of the algorithms are compared with the ground truth using standard statistical methods.
Keywords
Environmental ScienceEngineeringPhysics and Astronomy
Communications of the ACMRandom sample consensus
25,463 Citations1981Martin A. Fischler, Robert C. Bolles
New results are derived on the minimum number of landmarks needed to obtain a solution, and algorithms are presented for computing these minimum-landmark solutions in closed form that provide the basis for an automatic system that can solve the Location Determination Problem under difficult viewing.
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
Computer Vision: A Modern Approach
3,741 Citations2002David Forsyth, Jean Ponce
Comprehensive and up-to-date, this book includes essential topics that either reflect practical significance or are of theoretical importance and describes numerous important application areas such as image based rendering and digital libraries.
IEEE Transactions on Robotics and AutomationBlanche-an experiment in guidance and navigation of an autonomous robot vehicle
588 Citations1991Ingemar J. Cox
Blanche's position estimation system consists of a priori map of its environment and a robust matching algorithm that estimates the precision of the corresponding match/correction that is then optimally combined with the current odometric position to provide an improved estimate of the vehicle's position.
IEEE Transactions on ComputersSegmentation of Plane Curves
543 Citations1974T. Pavlidis, Steven L. Horowitz
A new fast algorithm is proposed which allows for a variable number of segments iniecewise approximation as a way of feature extraction, data compaction, and noise filtering of boundaries of regions of pictures and waveforms.
Robot pose estimation in unknown environments by matching 2D range scans
411 Citations1994Feng Lu, Evangelos Milios
Two new iterative algorithms to register a range scan to a previous scan so as to compute relative robot positions in an unknown environment, that avoid the above problems.
Journal of Intelligent & Robotic SystemsLine Extraction in 2D Range Images for Mobile Robotics
291 Citations2004Geovany A. Borges, M.J. Aldon
Qualitative and quantitative comparisons using simulated and real images illustrate the main characteristics of the framework when using different methods for breakpoint and line detection and illustrate the characteristics of each estimator, which can be exploited according to the platform computing power and the application accuracy requirements.
An experimental comparison of localization methods
263 Citations2002J.-S. Gutmann, Wolfram Burgard +2 more
This experimental study compares two methods for localization of indoor mobile robots: Markov localization, which uses a probability distribution across a grid of robot poses; and scan matching, which using Kalman filtering techniques based on matching sensor scans.
AMOS: comparison of scan matching approaches for self-localization in indoor environments
238 Citations2002J.-S. Gutmann, Christian Schlegel
This paper describes results from evaluating different self-localization approaches in indoor environments for mobile robots based on 2D laser scans and an odometry position estimate and shows that the position error can be kept small enough to perform navigation tasks.
Robotics and Autonomous SystemsRobox at Expo.02: A large-scale installation of personal robots
228 Citations2003Roland Siegwart, Kai O. Arras +13 more
Robox is a fully autonomous mobile platform with unique multi-modal interaction capabilities, a novel approach to global localization using multiple Gaussian hypotheses, and a powerful obstacle avoidance.
Weighted line fitting algorithms for mobile robot map building and efficient data representation
201 Citations2004S.T. Pfister, Stergios I. Roumeliotis +1 more
An algorithm to find the line-based map that best fits sets of two-dimensional range scan data via maximum likelihood formalism, which weights each point's influence on the fit according to its uncertainty, which is derived from sensor noise models.
Robotics and Autonomous SystemsHybrid simultaneous localization and map building: a natural integration of topological and metric
165 Citations2003Nicola Tomatis, Illah Nourbakhsh +1 more
The metric and topological paradigms are integrated in a hybrid system for both localization and map building, allowing a compact environment model, which does not require global metric consistency and permits both precision and robustness.
Line segment based map building and localization using 2D laser rangefinder
149 Citations2002L. Zhang, Bijoy K. Ghosh
A new closed line segment (CLS) map is introduced which consists of only line segments and defines a closed and connected region and it is argued that the CLS map provides an efficient mobile robot exploration scheme.
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE<title>Feature extraction and scene interpretation for map-based navigation and map building</title>
144 Citations1998Kai O. Arras, Roland Siegwart
A scheme for extracting environment features from 1D range data and their interpretation is presented and a compact scene model is obtained in the form of a weighted symbolic description preserving topology information and reflecting the main characteristics of a local observation.
Exact dynamic map building for a mobile robot using geometrical primitives produced by a 2D range finder
127 Citations2002J. Vandorpe, H. Van Brussel +1 more
In this paper a new mathematically exact algorithm is described for dynamic map building with geometrical primitives for a mobile robot using a 2D range finder mounted on the mobile robot LiAS which is navigating in the environment.
IFAC Proceedings VolumesAn Optimized Segmentation Method for a 2D Laser-Scanner Applied to Mobile Robot Navigation
79 Citations1997A. Siadat, Axel Kaske +3 more
A system for segmentation the data of a laser scanner on board a mobile robot should have good real-time capability to be able to integrate the information of the laser-scanner into the navigation algorithms of the mobile robot.
Real-time self-localization in unknown indoor environment using a panorama laser range finder
49 Citations2002Tobias Einsele
This paper deals with self-localization of a mobile robot on the condition that no a-priori knowledge about the environment is available and a robust localization module is employed.
Uncertainty of Line Segments Extracted from Static SICK PLS Laser Scans
41 Citations2003Albert Diosi, Lindsay Kleeman
Range finding and feature extraction by segmentation of images for mobile robot navigation
32 Citations2002Rhiannon Taylor, P.J. Probert
A line fitting system which recursively fits points to line segments, given range and bearing information, and correctly accounts for the sensors error sources is presented, and passes on unfitted points to the ellipse fitter.
Laser based position acquisition and tracking in an indoor environment
32 Citations1998Patric Jensfelt, Henrik Vie Christensen
Robotics and Autonomous SystemsFeature extraction and tracking for scanning range sensors
23 Citations2000Nick Pears
A solution to the problem of simultaneously extracting and tracking a piecewise-linear range representation of a mobile robot’s local environment is presented and the algorithm presented is immune to vehicle motion and active sensor reorientation during the finite capture time of the range scan.