Filtering GPS Noise Before Map Matching

The single highest-return change to most map-matching pipelines is not in the matcher at all — it is in what reaches the matcher. A hidden Markov model is built to explain its observations, so an observation that should never have existed becomes a road sequence that makes it plausible. This page covers the preprocessing that removes those observations, as part of map matching GPS traces to OSM networks within Python Routing Engines & Isochrone Mapping.

Four defects dominate real traces: duplicate and out-of-order timestamps, single-fix teleports, stationary jitter at stops, and gaps where the receiver lost signal. Each has a cheap, specific remedy, and each is far cheaper to fix here than to detect in matched output.

When to use this approach

Filter every trace, always — but the parameters matter most when:

• The fleet uses consumer devices. Phone-derived traces have wider and more variable noise than dedicated trackers, and their accuracy varies within a single trip as the device switches between GNSS and network positioning.
• Vehicles dwell frequently. Delivery work spends a large fraction of the shift stationary, and every stationary second is an opportunity for the matcher to wander.
• The operating area has urban canyons or tunnels. Both produce the two hardest cases: multipath error that looks like real movement, and gaps that look like fast movement.
• Downstream analysis measures time rather than geometry. Speed calibration and dwell analysis are far more sensitive to a mis-collapsed stop than route-adherence checking is.

Implementation

The four filters run in a fixed order, because each depends on the previous one having run.

# requires: numpy, pandas (pip install numpy pandas)
import numpy as np
import pandas as pd


def clean(df: pd.DataFrame, *, max_speed_mps: float = 60.0,
          min_move_m: float = 5.0, gap_s: float = 120.0) -> list[pd.DataFrame]:
    """Sort, gate, collapse, split. Returns one frame per contiguous segment."""
    df = (
        df.sort_values("timestamp")
          .drop_duplicates(subset="timestamp", keep="first")
          .reset_index(drop=True)
    )
    if len(df) < 2:
        return [df]

    xs, ys = df["x"].to_numpy(), df["y"].to_numpy()
    dt = df["timestamp"].diff().dt.total_seconds().to_numpy()
    step = np.hypot(np.diff(xs, prepend=xs[0]), np.diff(ys, prepend=ys[0]))

    # Gate: a fix implying an impossible speed is a bad fix
    implied = np.divide(step, np.clip(dt, 0.1, None),
                        out=np.zeros_like(step), where=~np.isnan(dt))
    df = df[implied <= max_speed_mps].reset_index(drop=True)

    df = _collapse_stationary(df, min_move_m)
    return _split_on_gaps(df, gap_s)

Ordering matters. Gating before collapsing means a teleport inside a stationary cluster is removed rather than becoming the cluster’s representative point. Collapsing before splitting means a long dwell is not mistaken for a signal gap.

# requires: numpy, pandas (pip install numpy pandas)
def _collapse_stationary(df: pd.DataFrame, min_move_m: float) -> pd.DataFrame:
    """Keep the first fix of each stationary run and record its dwell."""
    xs, ys = df["x"].to_numpy(), df["y"].to_numpy()
    keep, dwell, anchor = [0], [], 0
    for i in range(1, len(df)):
        if np.hypot(xs[i] - xs[anchor], ys[i] - ys[anchor]) >= min_move_m:
            dwell.append(
                (df["timestamp"].iloc[i - 1] - df["timestamp"].iloc[anchor]).total_seconds()
            )
            keep.append(i)
            anchor = i
    dwell.append(
        (df["timestamp"].iloc[-1] - df["timestamp"].iloc[anchor]).total_seconds()
    )
    out = df.iloc[keep].copy().reset_index(drop=True)
    out["dwell_s"] = dwell
    return out

Retaining dwell_s is what separates collapsing from discarding. Service-time analysis, planned-versus-actual comparison and speed calibration all need to know that the vehicle was stationary for fourteen minutes; only the matcher needs it not to be ninety separate observations.

# requires: pandas (pip install pandas)
def _split_on_gaps(df: pd.DataFrame, gap_s: float) -> list[pd.DataFrame]:
    """A long silence is a break in the trace, not a fast leg."""
    gaps = df["timestamp"].diff().dt.total_seconds().fillna(0.0)
    segment = (gaps > gap_s).cumsum()
    return [g.reset_index(drop=True) for _, g in df.groupby(segment) if len(g) >= 2]

Splitting rather than bridging is the important decision. A vehicle that vanishes for three minutes and reappears two kilometres away did travel between those points, but the matcher has no observations to constrain which route it took, and the path it invents will be the shortest one — which is a guess presented as a measurement.

A note on what not to filter. Smoothing the trace — a moving average over positions, or a Kalman filter tuned for display — actively harms matching. The matcher’s emission model already assumes the observations are noisy draws around a true position, and pre-smoothing correlates the errors between consecutive observations in a way the model does not expect. The result is a matcher that becomes overconfident in whichever road the smoothed path happens to favour. Remove observations that should not exist; leave the ones that should alone.

Key parameters and tuning

Integration points

Into the emission model. Where the receiver reports a per-fix accuracy estimate, carrying it through lets the matcher set its emission sigma per observation rather than globally. That single change usually outperforms any amount of tuning of a fixed sigma, because it adapts continuously to the urban-canyon transitions that a two-environment split only approximates. The parameter itself is covered in map matching GPS traces to OSM networks.

Into dwell analysis. The dwell_s column is the input to service-time estimation, which in turn feeds the service times a dispatch model needs — see vehicle routing problem solvers and fleet dispatch. Deriving service time from matched traces rather than from a fleet-wide average is one of the cheapest accuracy improvements available to a dispatch system.

Into speed calibration. Filtered, collapsed traces are what the telematics ground-truthing in speed profile calibration for heavy vehicles consumes. Feeding it unfiltered traces systematically depresses observed speeds, because every stationary cluster contributes many zero-speed samples on an edge the vehicle merely stopped on.

Validation checklist

• No two observations share a timestamp. Assert it after sorting; duplicates produce a zero time delta and an infinite implied speed.
• Implied speeds are all plausible. Recompute after filtering and confirm the maximum is below the gate. A survivor means the gate ran before the sort.
• Dwell totals are preserved. Sum dwell_s plus inter-fix intervals and confirm it equals the trace’s original span. A shortfall means collapsing dropped time rather than recording it.
• Segments are individually matchable. Every returned segment should have at least two fixes and no internal gap above the threshold.
• Filtering improves matched recall. Run the hand-matched sample through the matcher with and without filtering. If recall does not improve, the parameters are too loose to be doing anything.

Related

• Map matching GPS traces to OSM networks — the matcher this preprocessing feeds, and the emission model that consumes per-fix accuracy
• Hidden Markov map matching in Python — the Viterbi implementation whose candidate count this filtering reduces
• Speed profile calibration for heavy vehicles — the calibration that unfiltered dwell systematically biases
• Using the OSRM match endpoint for trace snapping — the hosted alternative, which needs the same preprocessing