Line Extraction with IR sensor/servo scanner

[airuno2l]

Feature extraction is commonly used in SLAM applications. It is useful because it reduces the amount of data that has to be processed by the mapping functions. Some applications extract lines and curves from the scan data and sends it to a global map, then during later scans, if the same feature is recognized, the amount of movement of the robot can be calculated. Feature extraction is usually only used on robots that are going to be operating in structured environments (indoors, office spaces, homes etc.) as opposed to unstructured environment (with trees, and bushes around). This is because homes and offices have walls that are lines. I have even seen some applications that take advantage of the Cartesian worlds we construct around us even farther by correcting the lines they extract by assuming all corners are 90 degrees, and it seems to work great in office settings.    

Unfortunately, this process requires very dense scan data, therefore LIDAR sensors are usually used.I'm trying to find out if it is feasible to use a IR sensor mounted to a servo to do line extraction of scan data. I have the sensor and servo hooked up to a project board (Freescale HCS12 MCU) which sends the data to the PC where Matlab takes over.

I messed around with a few different line extraction methods, but Split and Merge seemed to do the best (as opposed to hough transform which takes a significant amount more processing time). I learned about the different algorithms from a paper by Roland  Siegwart titled "A Comparison of Line Extraction Algorithms using 2D Laser Rangefinder for Indoor Mobile Robotics" (http://infoscience.epfl.ch/record/97571/files/nguyen_2005_a_comparison_of.pdf)

I did some desktop tests and I don't like the results very much. The problem is that the scan data is just too sparse to do anything with. I posted a video that shows it working where objects are within a foot of the sensor, but once they are farther away (>2 ft), the data is too messy and there is no way of getting valuable information from it.

My goal is to utilize SLAM on a cheap robot, hopefully using this sensor setup, encoders, and maybe another one or two rangers (IR or sonar). Next up on my list, I'm going to try scan matching. This process takes two consecutive scans, and figures out how to translate and rotate one scan onto the other, by doing this you know how much the robot has moved. I'm was hoping to do this by matching lines from one scan to the next, but the line extraction thing didn't work out to well so I will be using raw scan data. the method I'm going to use is called metric based Iterative Closest Point (mdICP), it's describe in a paper titled "Metric-based scan matching algorithms for mobile robot displacement estimation" by Javier Minguez ( http://webdiis.unizar.es/~jminguez/MbICP_ICRA.pdf )  

[youtube]4b_KEZP5Avg[/youtube]

[robots-in-brighton]

That was an interesting read, thanks. I don't think you should abandon it too quickly, maybe just adjust your expectations about what can be achieved with cheaper/more limited sensors. That first paper says a laser rangefinder is a good choice of sensor because "... it provides dense and more accurate range measurements, it has high sampling rate, high angular resolution, good range distance and resolution."

In their sample data the angle between successive scans was 0.5 degrees so the points are very closely spaced (at their max range of 7m, that could pick up points from features down to 6cm), and they combined 100 scans each of over 700 samples. With coarser sensors, even with the smaller scale of the table top I think you would need more data points for a fair comparison.

They also mentioned a pre-process of dropping consecutive points that looked unlikely (farther apart than some threshold) to help keep the noise level down. Anyway, thanks again for sharing.

[airuno2l]

Thanks for the feedback. I think I will continue to mess with this a little, but probably not with the intention of using SLAM, maybe someone will see this and come up with a different application for it (I haven't seen anyone doing this yet).

The pre-processing you mentioned is included in the algorithm that is used in the video, it helps a little. One thing I am doing that I will change is making lines from the two endpoints in a range of data, instead of using the least squares line fitting method mentioned in a paper (they also talk about doing it the way I am). I tried to do the least squares way briefly, but this simpler method seemed to give better results, which is counter intuitive. Also, the least squares method seemed to get hung up sometimes, mainly if one of the endpoints is the farthest point from the line, it would just iterate on that line over and over, this isn't a problem with my current method since the endpoints are on the line. I believe I can mess with the least squares line fitting method and get it to work better (e.g. not including the endpoints in the search for the farthest point). Also, I might tweak the hardware a little to see if I can reduce some of the noise, some say to mount those IR sensors vertically to get better results, also, this web site suggests adding and cap and resistor in parallel on the data line from the sensor to reduce noise...I might try both of those.

I'll post again if I have any break throughs, thanks for your interest.