Skip to content

Line Extraction

Jump to bottom
dcyoung edited this page Jun 5, 2017 · 6 revisions

Table of Contents

Pre-Processing

A few outliers in a data set can reduce the effectiveness of a line extraction algorithm. Often, pre-processing the data before extracting lines can yield better results. Too much processing and you risk distorting the data set such that the results aren't true to the underlying data. This will always be a balancing act.

The input data to the line extraction algorithm is a scan or a collection of sensor readings. Therefore, the pre-processor is concerned with a collection of sensor readings.

There are countless complex data processing techniques, but we'll keep things simple for this example. We will apply a median filter to the distance variable of the sensor readings, to help smooth the data and remove obvious outliers.

1D Median Filter

We'll apply a 1D Median Filter to the sensor readings of each scan before running our line extraction algorithm. We call the filter 1D (1 dimensional) because we apply it to only 1 dimension of the data. Each sensor reading has a few attributes or "dimensions", including distance, azimuth & signal strength. The dimension we'll be filtering is the distance attribute of each sensor reading.

You can think of a 1D Median Filter as a small window that slides over an array of values, stopping at each element to consider how it looks compared to its neighbors. If it is drastically different than its neighbors, we smooth the value to look more in-line with its neighbors. The basic process works like this:

  • slide the window such that it is centered over-top of an element (call this elemX)
  • consider the values (distance measurement) of all the elements visible in the window
  • calculate the median distance value among the visible elements in the window
  • replace the distance value of elemX with the median value calculated previously

The LineExtractionApp.Processing.Filtering sub-module provides a method called medianFilter1D which applies a 1D median filter to an array of sensor reading objects.

const _FILTERING = LineExtractionApp.Processing.Filtering;
let sensorReadings = ...
let filteredReadings = _FILTERING.medianFilter1D(sensorReadings);

By default this method will use the filter parameter values defined in LineExtractionApp.Processing.Filtering.FilterParameterDefaults. Optionally, you can provide a set of parameters to the method medianFilter1D like so:

let filterParams = {
	bPadBoundaries: false, // True-> assume discontiguous readings, False-> assume contiguous readings
	windowSize: 3
};
let filteredReadings = _FILTERING.medianFilter1D(sensorReadings, filterParams);
  • windowSize: Size of sliding filter window. Larger values will smooth the data, but lose detail. Should be odd and >= 3.
  • bPadBoundaries: Whether or not to pad the limits of the sensor reading array with the first and last readings. If true, the sliding filter window will be padded with the elements near the boundaries when the window is not completely overlapping the array. If false, the sliding filter window will wrap around to the other end of the array assuming that there is no boundary and that the sensor readings are contiguous. For a complete 360 degree scan, this should be false.

This pre-processing is used internally by the LineExtractor class outlined in the following section.

Line Extraction

There are many techniques for line extraction. For a simple comparison of various techniques, check out the article A comparison of line extraction algorithms using 2D laser rangefinder for indoor mobile robotics by Viet Nguyen published in 2005.

We'll be focusing on a simple and fast method called the Split Merge algorithm. For some basic basic pseudo code and a few helpful images, check out these helpful slide decks: here and here

The LineExtractionApp.Perception.PrimitiveExtraction sub-module provides a class LineExtractor which can be used to extract lines from a scan object.

const _EXTRACTION = LineExtractionApp.Perception.PrimitiveExtraction;
let scan = ...

let lineExtractor = new _EXTRACTION.LineExtractor();
let extractedLines = lineExtractor.extractLines(scan);

By default this class will use a pre-processor (for sensor readings) and post-processor (for lines) defined in the LineExtractionApp.Perception.PrimitiveExtraction module. Additionally, the line extraction parameters will default to those defined by LineExtractionApp.Perception.PrimitiveExtraction.LineExtractorParameterDefaults. Optionally, you can provide parameters for all of these things like so:

// Create the actual line extractor
this.lineExtractor = new _EXTRACTION.LineExtractor(
	// Line extraction method
	_EXTRACTION.LineExtractionTechniqueEnum.SPLIT_MERGE,
	// SPLIT-MERGE line extractor params
	{
		distanceThreshold: 20,
		collinearityThreshold: 2000,
		bUseIntermediateLineFitting: false
	},
	// Sensor Reading Pre-Processor Params
	{
		minRadius: 50,
		filter: _FILTERING.FilterTechniqueEnum.MEDIAN_1D,
		filterParams: {
			bPadBoundaries: false,
			windowSize: 3
		}
	},
	// Line Post-Processor Params
	{
		minSetSize: 5
	}
);

Split-Merge Line Extraction Parameters:

  • distanceThreshold: Max distance between a point and a line at which the point is to be considered a part of that line.
  • collinearityThreshold: Metric for how collinear two lines segments must be before they are merged into a single segment. Lower values are more strict, while higher values will attempt to merge lines that aren't as collinear.
  • bUseIntermediateLineFitting: Whether or not to use intermediate line fitting during the split portion of the split-merge line extraction algorithm. Otherwise iterative end-point is used (faster).

Sensor Reading Pre-Processor Params:

  • minRadius: The minimum radius for points to be considered in the line extraction. Sensor readings with a distance value less than this radius will be removed before the anything else.
  • filter: What type of filter to use (can be NO_FILTER).
  • filterParams: The parameters for the specified filter (can be an empty object if NO_FILTER)

Line Post-Processor Params:

  • minSetSize: The minimum number of points to produce a line. Lines made up of fewer points will not be removed.

Post-Processing

The output of the line extraction algorithm is a collection of lines. We can refine our results by processing the output lines, merging some and discarding others. Currently the post-processor simply discards the lines with too few sensor readings specified by a parameter. This post-processor is used inside of the LineExtractor class from before.

Clone this wiki locally