VehicleMapping HD AV Spatial Data

Detecting HD Map Changes from Fleet LiDAR

The signal a fleet produces is not "the map is wrong here" — it is a residual field, computed by the localizer for its own purposes, that is large in some places and small in others. Turning that into something a map team can act on means three narrowing steps: rejecting the frames where the residual means the pose was wrong, clustering what remains, and describing the difference in terms the map understands.

This task implements those for change detection and map maintenance, with a hard constraint that the output be small enough to upload from every vehicle continuously.

Where the volume goes at each narrowing step:

From 864 000 Frames to 200 Kilobytes of Candidates A four-stage narrowing funnel with counts at each stage and the resulting upload volume compared with the raw LiDAR volume. 864 000 frames · structure test, nearly free 9 000 locally structured 340 clusters 62 described candidates — the only thing uploaded 1% of frames — the rest were pose error or noise semantic comparison runs only here 200 kB uploaded · 2.6 TB of LiDAR stayed onboard a ratio of roughly ten million to one every stage after the first is affordable only because the first one is nearly free and rejects 99%

Prerequisites #

  • Python 3.10+, NumPy 1.24+, SciPy 1.11+, scikit-learn 1.4+ for the clustering.
  • Input: the localizer's per-point residuals and their positions, the pose covariance, and the resident map tile.
  • Upstream stage: NDT localization against an HD map, which produces both.
  • Output: structured candidate records, a few kilobytes each.

Step-by-Step #

1. Test the residual field for spatial structure #

python
import numpy as np

def locally_structured(res: np.ndarray, xy: np.ndarray,
                       frac: float = 0.15, ratio: float = 4.0) -> bool:
    """Reject frames whose large residuals are spread across the whole sweep."""
    if len(res) < 200:
        return False
    hi = res > np.percentile(res, 100 * (1 - frac))
    if hi.sum() < 20:
        return False
    return np.linalg.norm(xy[hi].std(axis=0)) < np.linalg.norm(xy.std(axis=0)) / ratio

Key parameters: frac picks the top 15% of residuals, which is generous enough to catch a small change and tight enough to exclude ordinary noise; ratio at 4 requires the high-residual set to be four times more compact than the sweep. Expected output: a boolean, computed in microseconds from arrays that already exist.

2. Cluster the survivors #

python
from sklearn.cluster import DBSCAN

def cluster(xy: np.ndarray, hi: np.ndarray, eps_m: float = 1.2, min_pts: int = 25):
    """Compact candidate regions from the high-residual points."""
    pts = xy[hi]
    labels = DBSCAN(eps=eps_m, min_samples=min_pts).fit_predict(pts)
    return [pts[labels == k] for k in sorted(set(labels)) if k >= 0]

DBSCAN rather than k-means because the number of changes is unknown and noise must be excluded rather than assigned. min_pts at 25 is the smallest cluster worth describing: below that the semantic extraction has nothing to fit.

3. Describe the difference semantically #

python
def describe(region_pts, map_tile, tol_m: float = 0.15) -> dict | None:
    """What differs here, in terms the map can express."""
    observed = extract_boundary(region_pts)
    if observed is None:
        return None                             # nothing describable — drop it
    mapped = map_tile.nearest_boundary(observed.centroid)
    if mapped is None:
        return {"kind": "added_boundary", "geometry": observed.simplified()}
    offset = mapped.distance_to(observed)
    if offset <= tol_m:
        return None                             # within tolerance — not a change
    return {"kind": "moved_boundary", "feature_id": mapped.id,
            "offset_m": float(offset),
            "direction_deg": float(mapped.bearing_to(observed))}

Returning None for an indescribable cluster is the third narrowing step and the one that removes wet-road reflections and low-sun artefacts: they produce residuals and clusters, and nothing that extracts as a boundary.

4. Emit a compact record #

python
import json, hashlib

def candidate_record(desc: dict, pose, tile_quadkey: str, vehicle_id: str) -> dict:
    rec = {
        "tile": tile_quadkey,
        "vehicle": vehicle_id,
        "observed_at": pose.time_iso,
        "pose_sigma_m": float(pose.sigma_lat),
        **desc,
    }
    rec["id"] = hashlib.sha256(
        json.dumps({k: rec[k] for k in ("tile", "kind", "feature_id")
                    if k in rec}, sort_keys=True).encode()).hexdigest()[:16]
    return rec

Deriving the identifier from the tile, kind and affected feature — not from the vehicle or the time — is what lets independent observations of the same change be counted as agreement rather than as separate candidates. Including pose_sigma_m lets the scoring stage discount observations taken while localization was poor.

What survives each filter, on one day of one vehicle:

Rejection Reason at Each Filter Three rejection bars with counts and reasons, and the surviving candidate count. filterrejectedbecause structure test 855 000 global residual — the pose was wrong, not the map clustering 8 660 scattered — below the minimum cluster size semantic description 278 indescribable, or inside the 0.15 m tolerance 62 candidates uploaded

Verification & Acceptance Criteria #

python
def assert_detector(records, labelled, uplink_budget_kb=500) -> None:
    ids = {r["id"] for r in records}
    assert len(ids) == len({(r["tile"], r["kind"], r.get("feature_id")) for r in records}), \
        "candidate ids are not stable across vehicles — agreement cannot be counted"

    tp = len(ids & labelled.real_ids)
    assert tp / max(len(ids), 1) >= 0.5, "per-vehicle precision too low before scoring"
    assert tp / max(len(labelled.real_ids), 1) >= 0.7, "detector missing real changes"

    kb = sum(len(json.dumps(r)) for r in records) / 1024
    assert kb <= uplink_budget_kb, f"{kb:.0f} kB exceeds the daily uplink budget"

Acceptance gate: candidate identifiers stable across vehicles observing the same change, which is the precondition for the scoring stage; per-vehicle precision ≥0.5 before agreement scoring; recall ≥0.7 against a labelled set; and total upload inside the daily budget, measured rather than assumed.

What each detector parameter trades, and which one is not a tuning knob:

Detector Parameters and What Each Trades Four rows pairing a detector parameter with what it trades and whether it is a tuning knob. four parameters, three of them tunable residual percentile · 0.15 how much of the tail is examined sensitivity against noise admitted tunable compactness ratio · 4 how local a change must be large changes against pose errors tunable min cluster size · 25 the smallest describable change detection floor against noise clusters tunable semantic tolerance · 0.15 m what counts as different the map positional tolerance not a knob moving the last row does not make the detector more sensitive — it changes the definition of a change

Common Errors & Fixes #

Every frame in a tunnel becomes a candidate. The residual is global there, and the structure test should reject it. Confirm the test is running before the clustering, not after.

Candidates from different vehicles never match. The identifier includes the vehicle or the timestamp. Derive it from the tile, kind and feature only.

The uplink budget is blown by one drive. Geometry is being uploaded at full resolution. Simplify before emitting — a boundary candidate needs a handful of vertices, not the extracted polyline.

Wet weather produces hundreds of candidates. The clusters are real and indescribable, so the semantic filter should drop them. If it is not, extract_boundary is fitting to reflections; raise its inlier floor, as in the RANSAC discussion in extracting lane boundaries from point cloud data.

Detection cost dominates the compute budget. The semantic stage is running on every frame rather than on flagged regions. Gate it on the structure test.

FAQ #

Why not upload the point cloud and detect changes in the cloud? #

Because the uplink cannot carry it. A fleet of a thousand vehicles producing tens of megabytes a second of LiDAR would need a data budget nobody has, and the vast majority of it would describe a road that has not changed. Detecting onboard and uploading a described candidate of a few kilobytes moves the same information at a millionth of the cost, and keeps the raw evidence available locally for the small fraction of candidates a surveyor actually opens.

What makes a residual cluster a candidate rather than noise? #

Spatial compactness and a describable difference. Noise produces large residuals scattered across the frame; a change produces them in one place. Requiring a cluster with a minimum point count and a bounded extent removes the scatter, and requiring that a semantic feature can actually be extracted and compared removes clusters that are merely a wet road or a low sun. A cluster nobody can describe is not a candidate.

Should detection run on every frame? #

The structure test should, because it is nearly free and reads arrays the localizer already computed. The semantic comparison should not — it is the expensive stage and only needs to run on regions the test flags, which on a healthy map is a small fraction of driving. Running the expensive stage everywhere is how change detection acquires a reputation for being unaffordable onboard.

Up one level: Change Detection & Map Maintenance — the stage this detector opens.