Wall Line Extraction

name: wall-line-extraction description: 'Extract wall lines from lidar data. Use when detecting walls, fitting lines to scan segments, or building geometric maps.'

Wall Line Extraction

Purpose

Extracting wall lines from LaserScan data enables higher-level reasoning: room boundary detection, door identification, map feature extraction, and navigation reference alignment. Raw scan points are noisy and unstructured; line extraction produces clean geometric primitives.

Algorithms

Split-and-Merge

Recursive line fitting. Fast and simple, well-suited for structured indoor environments.

Algorithm:

function SplitAndMerge(points, threshold):
    if len(points) < 2:
        return []

    # Fit a line from first to last point
    line = Line(points[0], points[-1])

    # Find the point farthest from the line
    max_dist = 0
    split_idx = -1
    for i in range(1, len(points) - 1):
        d = perpendicular_distance(points[i], line)
        if d > max_dist:
            max_dist = d
            split_idx = i

    if max_dist > threshold:
        # Recursively split
        left = SplitAndMerge(points[0:split_idx+1], threshold)
        right = SplitAndMerge(points[split_idx:], threshold)
        return left + right
    else:
        # All points fit the line within threshold
        return [line]

After splitting, a merge pass combines collinear adjacent segments whose gap is below a threshold.

Tuning: threshold (perpendicular distance) controls sensitivity. Indoor walls: 0.02-0.05m. Larger values produce fewer, longer segments.

Hough Transform

Voting-based method. Each scan point votes for all lines that could pass through it, parameterized in (r, θ) space where r = x·cos(θ) + y·sin(θ).

Steps:

1. Discretize (r, θ) parameter space into an accumulator array
2. For each point (x, y), increment all cells (r, θ) satisfying the line equation
3. Find peaks in the accumulator — each peak is a line
4. Group points belonging to each line and extract endpoints

Pros: Robust to outliers and gaps. Finds lines even with missing segments. Cons: Discrete resolution limits accuracy. Computationally heavier than Split-and-Merge. Difficult to extract exact endpoints.

RANSAC (Random Sample Consensus)

Steps:

1. Randomly select 2 points, fit a line
2. Count inliers (points within distance threshold of the line)
3. Repeat K times, keep the line with the most inliers
4. Refine the best line using all its inliers (least squares)
5. Remove inliers from the point set, repeat for the next line

Pros: Very robust to outliers. Produces accurate line parameters. Cons: Non-deterministic. May miss short segments. Requires tuning: number of iterations K, distance threshold, minimum inliers.

Comparison

laser_line_extraction ROS Package

The laser_line_extraction package implements line extraction from LaserScan messages and publishes visualization_msgs/MarkerArray for RViz and a custom LineSegmentList message.

Parameters

line_extraction_node:
  ros__parameters:
    frequency: 25.0
    frame_id: "laser_frame"
    scan_topic: "/scan"
    min_line_length: 0.5      # meters — ignore very short segments
    min_line_points: 9         # minimum points to form a line
    max_line_gap: 0.4          # meters — merge lines with gaps smaller than this
    min_range: 0.15            # ignore readings closer than this
    max_range: 10.0            # ignore readings farther than this
    min_split_dist: 0.05       # split threshold for Split-and-Merge (meters)
    outlier_dist: 0.05         # distance to exclude outlier points from line fitting
    bearing_var: 1.0e-5        # measurement bearing variance
    range_var: 0.012           # measurement range variance

Output Topics

Launch

Node(
    package='laser_line_extraction',
    executable='line_extraction_node',
    name='line_extraction',
    parameters=[line_extraction_params],
    remappings=[('scan', '/scan')],
),

Applications

Door Detection

Doors appear as gaps between collinear wall segments. Detect doors by finding pairs of line segment endpoints that are:

• Close together (gap < door width, typically 0.7-1.0m)
• From segments that are approximately collinear (angle difference < 10°)

Room Segmentation

Connected wall lines form closed or semi-closed polygons. Room detection groups lines into rooms based on enclosure analysis.

Navigation Reference

Align the robot to detected wall lines for precise corridor-following. Compute the robot's lateral offset and yaw relative to the nearest wall segment, and feed this to a controller.

Implementation Notes

• Filter the scan before line extraction (remove chassis hits, speckle noise)
• Line extraction works best with dense, low-noise scans (e.g., Hokuyo, SICK)
• For sparse LIDAR (e.g., LD19 with 4000 points/360°), increase min_line_points to reduce false segments
• Run line extraction at scan frequency or lower; it is computationally cheap
• Lines are in the LIDAR frame; transform endpoints to map frame via TF for map-level reasoning