Multiple Line Estimation

Question

Background:

I am working on a design in which an autonomous RC car implements a LIDAR sensor to navigate a course.

The primary LIDAR sensor returns a 270 array of points, scanning in a line like fashion, each representing the distance at a particular angle. These can easily be converted from polar to cartesian coordinates.

Question:

Given a set of points how would you estimate the number of lines that exist within this plot and the slope of each line. An explanation for a simple linear regression is not required, an explanation on how to detect discontinuities between the data is helpful.

Answer 1

You can start by using split-and-merge segmentation algorithm.

There are many algorithms available A Comparison of Line Extraction Algorithms using 2D Laser Rangefinder for Indoor Mobile Robotics.

If you want to refer the code, A ROS package is available here and below picture is the result from it.

Answer 2

From technical point of view I would refer you to this pcl tutorial

From you description I guess that you want to navigate the car between lines. Looking a one scan and detecting the line is quite crude, a more complex approach would be to merge the LIDAR info with odometry info and use a SLAM algorithm to at the same time build a map of the environment and localize your vehicle inside. This way the points from your LIDAR are aggregate other time and it might be easier to extract features as they are composed of more point.

Also a practical thing I would recommend you not to have the LIDAR plane parallel to the floor but with a couple of degree tilting so that in your point cloud you also get information about the ground.