Skip to the lesson
FixTheRobot Explore Robotics / Localization & SLAM / M3 Mapping and State Estimation / M3-T3

Localization & SLAM · Theory · M3

M3-T3 — Feature-Based Mapping

Reduce thousands of laser points to a handful of lines and corners that can be matched, stored and compared.

  • Lesson 3 of 8
  • Module 3: Mapping and State Estimation
  • Theory
  • About 8 minutes to read

A scan has hundreds of points, but a room needs only a few lines to describe it. Feature maps keep those lines and corners. They are compact, sharp and easy to match, and they fail in the places where the world has no straight walls. This lesson shows how to extract lines from a scan, how to describe them, and when to choose features instead of landmarks or grids.

Learning objectives

After this lesson, you should be able to:

  • Fit a line to scan points by total least squares and report it as (ρ, α).
  • Run split-and-merge to segment a scan into lines and find corners.
  • Compare feature, landmark and occupancy-grid maps by representation, cost and failure modes.
  • State when feature extraction fails (curved or cluttered scenes) and what to do.

The problem and the intuition

Describe your office in one sentence: “a rectangle about 4 by 6 metres with a door in the north wall.” You did not list every point. You gave features: four walls and a gap. A feature map does the same for the robot’s laser scan. The advantages are practical: a line has only two parameters, so comparing two maps becomes comparing a few numbers; a line averages out the noise of dozens of points; and a corner is a precise place where two lines meet.

A feature is a compact summary of many measurements that is stable enough to be found again.

Split and merge on an L-shaped scanScan points along two walls meeting at a corner. The first chord from the first to the last point misses the corner by a large distance, so the set splits at the farthest point, giving two line segments. chord d = 2.1 m Split: the farthest point from the chordis farther than a threshold (0.1 m). Recurse on both halves; stop when everypoint is within the threshold of its chord. Result: two lines and one corner feature.
Split-and-merge: find the point farthest from the chord between the endpoints, split there if it is too far, and repeat on each half.

The algorithm: lines from scan points

Problem. Given an ordered set of 2D points from a range scan, partition it into segments that each lie on a straight line, and describe each line and each corner where lines meet.

Assumptions. The environment is largely made of straight surfaces; the points are ordered by bearing (as in a laser scan), so neighbours in the list are neighbours in space; noise is small compared with the length of the walls.

Line fitting

A line is written with its distance ρ from the origin and the direction α of its normal: x cos α + y sin α = ρ. Fitting by total least squares minimises perpendicular distances. With the centroid (x̄, ȳ) and the scatter sums

Total least squares line fit
Sxx=∑(xi−xˉ)2S_{xx}=\sum (x_{i}-\bar{x})^{2}
Syy=∑(yi−yˉ)2S_{yy}=\sum (y_{i}-\bar{y})^{2}
Sxy=∑(xi−xˉ)(yi−yˉ)S_{xy}=\sum (x_{i}-\bar{x})(y_{i}-\bar{y})
α=12atan2(−2 Sxy, Syy−Sxx)\alpha =\tfrac{1}{2}\mathrm{atan}2(-2\,S_{xy},\,S_{yy}-S_{xx})
ρ=xˉ cos⁡ α+yˉ sin⁡ α\rho =\bar{x}\,\cos \,\alpha +\bar{y}\,\sin \,\alpha
(ρ, α)
line parameters: ρ is the signed distance from the origin, α the angle of the normal. Unlike y = m x + c, the form handles vertical lines.
Sxx, Syy, Sxy
scatter of the points about their centroid.
residual
perpendicular distance of a point to the line: x cos α + y sin α − ρ.

Pipeline: split and merge

  1. Split. Draw the chord from the first to the last point of the segment. Find the point with the largest perpendicular distance. If it exceeds a threshold (about 3σ of the sensor noise), split there and recurse on both halves.
  2. Merge. Join neighbouring segments whose combined fit has small residual (collinear after a gap or an over-split).
  3. Fit. Fit each remaining segment with total least squares; discard segments with fewer than a minimum number of points or length.
  4. Corners. Intersect neighbouring lines and keep the intersection if it is close to the end points of both segments and the angle between them is significant.

Comparing three kinds of map

MapWhat it storesStrengthFailure mode
Feature (lines, corners)Parametrised geometric primitivesVery compact, precise, easy to matchFails in curved, cluttered, natural scenes; extraction thresholds
Landmark (points)Isolated point positions with covarianceSimple filters (EKF), identity from fiducialsNeeds distinct points; sparse; no free space
Occupancy gridEvidence of occupied or free per cellAny shape; free space explicit; planningMemory; no compact matching; pose error blurs it

A worked example: a wall and an L

  1. A straight wall. Points (0, 1.00), (1, 1.02), (2, 0.98), (3, 1.00). Centroid (1.5, 1.00). Sxx = 5, Syy = 0.0008, Sxy = (−1.5)(0) + (−0.5)(0.02) + (0.5)(−0.02) + (1.5)(0) = −0.02. α = ½ atan2(0.04, −4.9992) = ½ (179.5°) = 89.8°, ρ = 1.5 cos 89.8° + 1.0 sin 89.8° = 1.00. The line is “y = 1” within 0.3°.
  2. An L-shaped scan. Eight points along two walls meeting at a corner at (3, 0): (0,0), (1,0.02), (2,−0.01), (3,0), (3.02,1), (3,2), (2.99,3). The chord from (0, 0) to (2.99, 3) is the line y = 1.003 x. The corner point (3, 0) is at perpendicular distance |3 × 1.003 − 0| / 1.416 = 2.1 m from it, far above the 0.1 m threshold: split there.
  3. Recurse. The left half (0,0) … (3,0): every point is within 0.02 m of its chord. The right half (3,0) … (2.99,3): within 0.02 m. No more splits. Two lines: α ≈ 90° (ρ ≈ 0) and α ≈ 0° (ρ ≈ 3).
  4. Corner. Intersecting the two lines gives (3.0, 0.0), the same as the split point, with an angle of 90°: a strong corner feature.
  5. Compare with a grid. The 8 points become 2 lines (4 numbers) and one corner (2 numbers). A grid of the same scene at 5 cm over a 4 m × 4 m area has 6,400 cells.

Matching these features between two scans is easy and fast: compare (ρ, α) after allowing for the robot’s motion. Doing the same with raw points is scan matching (M3-T4).

Engineering implications and limitations

Engineering implications

  • Tune the threshold from the sensor noise. Too small and noise creates fake segments; too large and corners are smoothed away. Use about 3σ of the range noise, scaled with range (noise often grows with distance).
  • Reject short and poorly supported lines. A line from four points has a large angular uncertainty; keep at least a handful of points and a minimum length.
  • Carry the covariance of each line. A line fitted to a few noisy points has an uncertain angle. EKF-based feature SLAM (and the lab) uses that uncertainty for matching.
  • Keep occupancy grids for planning and features for localisation: many systems carry both. Features are a good index into a large map; grids are the surface the planner walks on.
  • Check the environment. A hospital corridor is perfect for lines; a forest is not. If less than half of the scan points fall on lines, a feature map is the wrong choice.

Limits

Straight lines are an assumption about the world. Curved walls, stacked shelves, plants and people turn into many short, unstable segments. Feature extraction also adds a failure of its own: a corner may appear or disappear depending on the viewpoint, so features need verification before they are trusted for data association.

Common misconceptions

“Features are more accurate than raw points.”

They are more compact and average noise, but extraction can bias them: corners are rounded by thresholds and lines are only as straight as their points.

“y = m x + c is fine for walls.”

It fails for vertical walls (infinite slope). The (ρ, α) form has no singularity.

“Ordinary least squares and total least squares are the same.”

Ordinary least squares minimises vertical distances and is biased for steep lines. Total least squares minimises perpendicular distance.

“A feature map replaces the grid.”

It complements it. Free space is not represented, which planning needs.

Engineering takeaways

  1. A line is best described by (ρ, α) and fitted by total least squares to avoid vertical-line singularities.
  2. Split-and-merge segments a scan by repeatedly splitting at the point farthest from the chord.
  3. Corners are intersections of adjacent lines: compact, precise features for matching.
  4. Feature maps are compact and sharp but assume straight surfaces; grids handle any shape but are bulky.
  5. Choose the representation by what the environment looks like and what the map is for.

References and further reading

Primary papers and authoritative documentation.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

Question 1

Why is the (ρ, α) form preferred to y = m x + c for walls?

Explanation

It has no singularity: a vertical wall has infinite slope m, which breaks y = m x + c, but is just α = 0 or 180° in (ρ, α). The same parameters also give a perpendicular distance to the line directly, which is the residual we want.

Question 2

A split-and-merge run on a scan of a large round pillar produces 25 short segments. What is wrong, and what is the remedy?

Explanation

A circle is not made of straight segments, so each short chord fits a few points within the threshold and many splits result. Either relax the model (treat circles as landmarks or use a grid), merge segments by length, or discard features with too few points.

Question 3

A line fitted to six points has a normal angle uncertainty of 2°, and one fitted to sixty points of the same wall has 0.4°. Why should a SLAM system keep this?

Explanation

The covariance tells the data association and the filter how much to trust each line. Treating both as equally precise would let a weak line pull the pose as hard as a strong one, and overconfidence follows.

What’s next

With maps in different forms, the next problem is estimating the motion between two scans directly, without any features: scan matching.

Practice this lesson

Fix a Misaligned Map

Two map segments disagree: find whether pose offset, heading or scale is wrong and correct it.

Next lesson

M3-T4 — Scan Matching

Pose the scan-to-scan and scan-to-map alignment problem and name its main approaches and failure modes.

Nothing below is required to finish this lesson.