Skip to the lesson
FixTheRobot Explore Robotics / Perception / P5 3D Perception and Point Clouds / P5-T4

Perception · Theory · P5

P5-T4 — Clustering and Object Separation

Clustering groups points into objects. One radius cannot be right at both 5 m and 25 m.

  • Lesson 4 of 6
  • Module 5: 3D Perception and Point Clouds
  • Theory
  • About 9 minutes to read

After the ground is removed, a cloud still holds many objects as one pile of points. Clustering splits it into groups, one per object, on the principle that points of the same object are close to each other and points of different objects are not. The principle is simple and the details decide whether it works: how close is close, how many points make an object, and what happens when point spacing changes with distance. This lesson covers Euclidean clustering and DBSCAN, the choice of radius, the range-dependence that makes a constant radius fail and the usual failure modes.

Learning objectives

After this lesson, you should be able to:

  • Describe Euclidean clustering and DBSCAN, and define the connection radius and the minimum cluster size.
  • Compute the spacing of LiDAR points at a given range and choose a range-dependent radius.
  • Explain over-segmentation and under-segmentation and the situations that cause them.
  • Estimate the cost of clustering and the effect of a k-d tree or a grid.

The idea: close points belong together

Take any point and find all points within a radius of it; take their neighbours’ neighbours; keep going until no new point is reached. That group is a cluster. Start from an unused point and repeat. This is Euclidean clustering, and it is the same flood fill as connected components in an image (Lesson P2-T4), applied to 3D points with distance instead of pixel adjacency.

Point spacing grows with rangeA plot of distance against range from 0 to 40 metres. A blue line shows the spacing between neighbouring LiDAR points at 1 degree resolution, rising from near zero to about 0.7 metres at 40 metres. A horizontal orange dashed line at 0.3 metres is a fixed clustering radius: it lies above the spacing at short range and below it beyond about 17 metres. A green line shows a radius that grows with range and stays above the spacing everywhere.01020304000.40.81.21.6range (m)distance (m) point spacing r·Δθ (1°)fixed radius 0.3 madaptive radius 0.1 + 0.05 r Left of ~17 m the fixed radiusis bigger than the spacing; right ofit the cluster falls apart.
The distance between neighbouring points on a surface grows linearly with range. A fixed radius that is right at 5 m is too small beyond about 17 m, so far objects fragment. A radius that grows with range stays above the spacing everywhere.

Two parameters decide the result:

  • The radius ε. Smaller than the spacing inside an object: the object splits (over-segmentation). Larger than the gap between two objects: they merge (under-segmentation).
  • The minimum cluster size. A cluster with fewer points is treated as noise. Too high and small or distant objects are lost; too low and every noise return becomes an “object”.

Cluster in a metric that matches how the points are spread. A LiDAR’s points are not uniformly spaced: they are spaced in angle, so the distance between them grows with range.

The mathematics: spacing, DBSCAN and cost

Point spacing

A sensor with angular resolution Δθ (radians) between neighbouring beams places points on a surface at range r facing the sensor about

spacing of neighbouring points
spacing≈r⋅Δθ\text{spacing}\approx r\cdot \Delta \theta
spacing on a tilted surface≈r⋅Δθcos⁡ ϕ\text{spacing on}\,a\,\text{tilted surface}\approx \frac{r\cdot \Delta \theta }{\cos \,\phi }
r
the range to the surface in metres.
Δθ
the angular step between beams, in radians (1° = 0.01745 rad). It can differ horizontally and vertically.
φ
the angle between the surface normal and the beam. A surface seen at a grazing angle (φ near 90°) has much larger spacing: a face turned away from the sensor is sparse.

The radius must exceed this spacing for points of one surface to connect. It should be a function of range: ε(r) = ε0 + k r, with ε0 a few centimetres to cover noise and k a small multiple of Δθ (for example 2 to 3 times) to cover spacing and some grazing.

DBSCAN

DBSCAN (Ester et al., 1996) formalises density-based clustering with two parameters, ε and minPts:

  • A point is a core point if at least minPts points (itself included) lie within ε.
  • A point is density-reachable from a core point if it lies within ε of it, or of a chain of core points.
  • A cluster is a maximal set of density-reachable points. Points reachable from no core point are noise.

Euclidean clustering is the special case with minPts = 1 and a size filter on the result. DBSCAN’s core-point rule removes thin chains of stray points that would otherwise bridge two objects.

Cost

Naively each point is compared with every other: O(N2) distance tests. With a k-d tree or a voxel/grid hash for radius queries it is about O(N log N). For 500 points the naive 250 000 tests are trivial; for 100 000 they are 1010, which is not. A bird’s-eye-view grid, where points are binned into 2D cells and cells are connected like an image, makes clustering as cheap as image connected components and is widely used in real-time pipelines.

Failure modes

FailureCauseRemedy
Over-segmentationRadius below the spacing: far or grazing surfaces, dark surfaces with dropouts, occlusion splitting an objectRange-dependent radius, merge clusters that touch in 3D, accumulate frames
Under-segmentationRadius above the gap between objects: people standing together, a car next to a wall, ground points left overSmaller radius near, remove ground carefully, split clusters by shape or a learned model
Noise clustersMinimum size too low; spurious returns (rain, dust, reflections)Minimum points, intensity or height filters, temporal consistency
Lost objectsMinimum size too high for thin or distant objectsRange-dependent minimum size; keep tracks through gaps
ChainsA line of stray points bridging two objectsDBSCAN core-point rule; erode in BEV

A worked example: the same objects at three ranges

A LiDAR with 1° resolution (Δθ = 0.01745 rad) sees a box at three ranges.

RangePoint spacing r·ΔθFixed radius 0.3 mAdaptive radius 0.1 + 0.05 rResult with the fixed radius
5 m8.7 cm30 cm35 cmconnected
12 m20.9 cm30 cm70 cmconnected
22 m38.4 cm30 cm120 cmfragmented
35 m61.1 cm30 cm185 cmfragmented

The spacing grows from 8.7 cm at 5 m to 61 cm at 35 m. With a fixed 30 cm radius the clusters are connected up to roughly 12 m (allowing some diagonal and grazing margin), then fall apart. The adaptive radius is always larger than the spacing and also grows in step with it.

The other side: merging

Two boxes stand 0.5 m apart at 6 m. An adaptive radius of 0.1 + 0.05 × 6 = 0.4 m keeps them separate (0.5 > 0.4). At 22 m the same two boxes would be 0.5 m apart and the radius is 1.2 m: they merge. This is physical, not a bug: at 22 m the sensor’s own point spacing (0.38 m) is comparable to the gap, and the data cannot show that the gap exists. A cluster at that range is “one or more objects in a 1 m region”. A downstream stage that needs the count (a counter of people, say) has to treat far clusters as uncertain.

Minimum size

A person (0.5 m wide, 1.7 m tall) at 10 m with 1° × 1° resolution gives about (0.5/0.175) × (1.7/0.175) ≈ 28 points (the spacing is 0.17 m); at 25 m the spacing is 0.44 m and about 4 points remain. A fixed minimum of 10 points would drop the person at 25 m. This is the same density argument as in Lesson P5-T6 and the reason for a minimum size that depends on range.

Computing cost

A scene with 5 000 obstacle points after ground removal: naive clustering needs up to 25 million distance tests per frame (at 10 Hz: 250 million per second). A grid with a cell of the clustering radius needs to examine only the 27 neighbouring cells of each point, typically a few tens of tests per point, 100 000 or so in total.

Engineering implications and limitations

Derive the radius from the sensor. Compute the spacing at each range from the angular resolution and the surface angle you expect, and set ε(r) a little above it. Do not tune one fixed value on a single scene.

Accept what the data cannot resolve. A cluster at long range may be several objects. Carry that as an attribute (range, point count, density) so that counting and tracking stages can handle it, and do not report a precise object count from the far field.

Remove the ground carefully first. Leftover ground points join objects into one cluster (under-segmentation) and make long chains. A good ground estimate (Lesson P5-T3) is a precondition for clustering.

Use a grid for speed. A bird’s-eye-view occupancy grid with connected components is fast and predictable; use the 3D radius query only where the extra precision is needed.

Split what clustering merges. If objects of different kinds touch (a person next to a car), shape or learned segmentation separates them. Clustering is the first step of detection, not the last.

Track across frames. A far object fragments in one frame and not the next. Association over time (Module 7) smooths such flicker, and aggregating frames in a common frame raises the density.

Common misconceptions

“One tuned radius works for the whole scene.”

Point spacing grows with range, so a radius that is right at 5 m is too small at 25 m and a radius that is right at 25 m merges neighbours at 5 m.

“If two objects are in one cluster, the clustering is wrong.”

At long range, the data may not contain the gap that separates them. Under-segmentation at range is a limit of the sensor, not an error of the algorithm.

“Clustering finds objects.”

It finds groups of nearby points. Whether a group is one object, part of one, or several depends on the scene and needs further reasoning.

“More points always make clustering better.”

Denser data helps up to a point; dense noise and leftover ground points make it harder, and the cost rises quickly with the naive algorithm.

Engineering takeaways

  1. Euclidean clustering connects points closer than a radius; DBSCAN adds a core-point rule that removes thin bridges and noise.
  2. LiDAR point spacing is about r·Δθ (more at grazing angles), so the radius must grow with range: ε(r) = ε0 + k·r.
  3. Over-segmentation comes from too small a radius (far, grazing or dropout regions); under-segmentation from too large a radius, leftover ground, or objects closer than the sensor can resolve.
  4. The minimum cluster size must also depend on range: a person at 25 m can have only a handful of points.
  5. Use a grid or k-d tree for speed, remove the ground first, and keep range and density with each cluster for downstream reasoning.

References and further reading

Standard references; the spacing and point-count numbers were computed for this lesson.

  • Ester, M., Kriegel, H.-P., Sander, J. and Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. KDD: DBSCAN.
  • Rusu, R. B. (2010). Semantic 3D Object Maps for Everyday Manipulation in Human Living Environments. KI – Künstliche Intelligenz: Euclidean cluster extraction.
  • Bogoslavskyi, I. and Stachniss, C. (2016). Fast range image-based segmentation of sparse 3D laser scans for online operation. IROS: clustering in the range image using angle criteria.
  • Himmelsbach, M., Hundelshausen, F. v. and Wuensche, H.-J. (2010). Fast segmentation of 3D point clouds for ground vehicles. IEEE Intelligent Vehicles Symposium.

Knowledge check

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

Question 1

A LiDAR has 0.2° horizontal resolution. What is the point spacing at 30 m on a surface facing the sensor, and what radius would you start with?

Explanation

0.2° = 0.00349 rad, so the spacing is 30 × 0.00349 ≈ 0.105 m. A radius of 2 to 3 times that, plus a few centimetres for noise (about 0.25 to 0.35 m), is a reasonable start; on a grazing surface the spacing is larger by 1/cos φ, so allow more.

Question 2

Two pedestrians walk 0.4 m apart at 30 m. The clustering returns one object. Is the algorithm wrong?

Explanation

Not necessarily. The clustering radius at 30 m must exceed the point spacing (here 0.5 m at 1°), which is larger than the 0.4 m gap. The data do not show the gap, so they merge. The system should label the cluster as uncertain at that range and rely on tracking or a classifier to resolve it as they approach.

Question 3

Why can a minimum cluster size of 10 points be right at 8 m and wrong at 25 m for a person-sized object?

Explanation

The number of points on an object falls as 1/r². A person (0.5 m by 1.7 m) gets about 45 points at 8 m (at 1° by 1° resolution) and about 4 at 25 m, so a fixed minimum of 10 loses the person well before the far edge of the range. Use a minimum that decreases with range, or a density-based criterion.

What’s next

Next: turning a cluster into a box, with a position, size, heading and distance.

Practice this lesson

Debug a Failed 3D Detection Pipeline

Repair range-dependent clustering and oriented boxes so distant and partially seen objects are found.

Next lesson

P5-T5 — Bounding Boxes and Geometric Object Properties

Compute axis-aligned and oriented boxes and the size, distance and heading of an object.

Nothing below is required to finish this lesson.