Choosing a Map-Matching Algorithm: HMM vs Geometric Snapping vs Viterbi

Every fleet map-matching project starts with the same question: do we need a full probabilistic matcher, or is snapping each GPS ping to the nearest road enough? Get the answer wrong in the cheap direction and your matched traces flicker between parallel carriageways, corrupting toll attribution and mileage reports. Get it wrong in the expensive direction and you pay for a road-graph cache, a shortest-path engine, and weeks of probability tuning to solve a problem that a fifty-line snapper would have handled on a rural network. This page is a decision guide, not an advocacy piece: it lays out the three names you keep hearing — geometric snapping, the hidden Markov model, and Viterbi — shows exactly where each one belongs, and gives you a rubric and working Python to make the call.

The single most common source of confusion is the third name. Teams routinely ask whether they should use “an HMM or Viterbi,” as if the two were competing designs. They are not. A hidden Markov model is a model — it defines how likely a GPS observation is given a candidate road segment (the emission probability) and how likely one segment is to follow another (the transition probability). Viterbi is the decoder — the dynamic-programming recursion that searches those probabilities and returns the single most likely sequence of segments. You do not choose between them; you choose the HMM and then Viterbi is how you solve it. The genuine architectural decision is geometric snapping versus an HMM, and this guide treats it that way while clearing up the Viterbi question directly in its own section.

Why Naive Snapping Fails (and When It Doesn’t)

Geometric snapping projects each GPS ping onto the closest road segment and calls that the match. It is fast, deterministic, trivially auditable, and correct most of the time on a network where roads are far apart. On a two-lane rural road, a motorway with a wide median, or an industrial yard with a single access road, the nearest edge to a clean fix is the road the vehicle is on, and nothing more elaborate is warranted.

The failure is structural, not incidental. A snapper treats every ping as an independent decision with no memory of where the vehicle just was. When a divided highway places the northbound and southbound carriageways ten metres apart, or a service road runs alongside a main artery, an 8-12 metre GPS error is enough for a ping to land closer to the wrong edge. Because each ping is decided in isolation, the matched path flickers: three pings on the correct carriageway, one on the opposing one, two back on the correct one. Every flicker is a phantom U-turn, a mis-attributed toll, and a corrupted speed sample. The same failure appears at junctions, roundabouts, and multi-level interchanges, and it gets dramatically worse as the sampling interval grows, because a ping every thirty seconds gives proximity even less to work with.

An HMM fixes this by adding memory. It keeps every plausible segment for every ping as a candidate state and scores not only how well each candidate explains its ping (emission) but how plausible it is to travel from the previous candidate to this one along the actual road graph (transition). A jump from the northbound carriageway to the southbound one requires an implausibly long detour through the next legal U-turn, so its transition probability is tiny, and the decoder rejects the flicker in favour of a path that stays on one carriageway. This is precisely the machinery described in hidden Markov model map matching in Python, and it is why the HMM is the production standard for urban fleets.

Prerequisites

Before you can fairly compare the two approaches you need the same inputs both would consume:

Python environment. Python 3.10+, numpy ≥ 1.24, shapely ≥ 2.0 (the vectorised 2.x API; never run production matching on Shapely 1.x), and geopandas ≥ 0.14 for the road-network GeoDataFrame. The HMM path additionally needs networkx for shortest-path transition distances, or an OSRM server for route distances at scale.

A clean coordinate sequence. Both algorithms assume the trace is temporally ordered, deduplicated, and free of gross jumps. Run outlier removal and, where noise is high, Kalman filtering for GPS noise reduction upstream. A matcher of either kind amplifies whatever positional error it is handed.

A projected road network. Load edges as a GeoDataFrame and project both the network and the pings to a metric CRS (a local UTM zone) so that perpendicular distances are in metres, not degrees. Matching on raw WGS84 degrees silently corrupts every distance comparison.

A labelled ground-truth corpus. You cannot choose between algorithms by inspecting output on a map. Assemble at least a few hundred manually verified trips spanning urban, suburban, and rural conditions plus known edge cases (tunnels, parallel carriageways, roundabouts) so the rubric below has something to measure against.

Comparison at a Glance

The table makes the trade explicit: the two approaches are equally accurate exactly where snapping is defensible, and diverge sharply as the network gets denser and the sampling gets sparser. Infrastructure and tuning cost move in the opposite direction. The decision tree above is simply this table read as a flowchart.

The Three Names, Precisely

Geometric nearest-edge snapping

The whole algorithm is: for each ping, find the nearest road segment and project the point onto it. The only nuance is doing it quickly (a spatial index over the edges) and safely (a distance gate that refuses to snap a ping sitting 300 metres from any road). It has no notion of the previous ping, no probabilities, and no road connectivity. Its entire strength — determinism and speed — is a direct consequence of that statelessness, and so is its entire weakness. The full, tunable implementation lives in geometric nearest-edge snapping in Python; the minimal version below is enough to reason about the choice.

The hidden Markov model

The HMM reframes matching as recovering a hidden truth from noisy observations. The hidden states are “which road segment the vehicle is actually on”; the observations are the GPS pings. Two probabilities define the model. The emission probability is a Gaussian on the perpendicular distance from a ping to a candidate segment: P(z | segment) ∝ exp(−0.5 · (d / σ_z)²), where σ_z is the GPS noise standard deviation in metres. The transition probability penalises the difference between the on-road route distance and the straight-line distance between two consecutive pings: P(s_j | s_i) ∝ exp(−|route − great_circle| / β), where β controls how much detour is tolerated. Tuning these two parameters is the whole game — see tuning HMM emission and transition probabilities for calibration procedure.

Viterbi — the decoder, not a competitor

Given the emission and transition probabilities, there is an astronomically large number of possible segment sequences across a trace: with ten candidates per ping and six hundred pings, that is 10⁶⁰⁰ paths. You cannot enumerate them. Viterbi is the dynamic-programming recursion that finds the single most probable one in linear time by keeping, at each ping, only the best cumulative score to reach each candidate. It works in log-space — summing log-probabilities instead of multiplying probabilities — because the products underflow to exactly zero within about twenty pings otherwise.

The crucial point for this decision: Viterbi presupposes the HMM. It is meaningless without emission and transition probabilities to search. So the question is never “HMM or Viterbi.” It is “geometric snapping or an HMM,” and if you pick the HMM, Viterbi (or its beam-search variant) is simply the solver. When you see a library advertise “Viterbi map matching,” it is advertising an HMM whose decoder is Viterbi.

Step 1 — A Minimal Geometric Snapper

The following snapper is deliberately small: an STRtree over the edges, a nearest-edge query, a perpendicular-distance gate, and a one-step continuity check that flags implausible jumps. It is enough to answer “does snapping already meet my target?” on a sample of traces.

import numpy as np
from shapely import STRtree
from shapely.geometry import Point
import geopandas as gpd


def snap_trace(
    pings: np.ndarray,          # shape (N, 2), columns [x, y] in a metric CRS
    edges: gpd.GeoDataFrame,    # road segments, geometry in the same metric CRS
    max_snap_m: float = 30.0,   # reject snaps farther than this (metres)
    max_jump_m: float = 400.0,  # flag when the matched point leaps this far in one step
) -> gpd.GeoDataFrame:
    """
    Nearest-edge snapper with a distance gate and a continuity check.

    Returns one row per input ping with the matched edge index, the snapped
    point, the perpendicular distance, and a boolean 'suspect' flag raised when
    the ping is un-snappable or the matched point jumped implausibly far from
    the previous match.
    """
    geoms = edges.geometry.values
    tree = STRtree(geoms)                       # built once; reuse across traces
    points = [Point(x, y) for x, y in pings]

    nearest_idx = tree.nearest(points)          # index into geoms for each ping

    rows = []
    prev_xy = None
    for i, (pt, edge_i) in enumerate(zip(points, nearest_idx)):
        edge = geoms[edge_i]
        # project() gives the arc-length of the closest point along the edge
        proj = edge.interpolate(edge.project(pt))
        perp_m = pt.distance(edge)              # perpendicular distance, metres

        jump_m = 0.0 if prev_xy is None else proj.distance(Point(prev_xy))
        suspect = bool(perp_m > max_snap_m or jump_m > max_jump_m)

        rows.append({
            "ping_i": i,
            "edge_i": int(edge_i),
            "snap_x": proj.x,
            "snap_y": proj.y,
            "perp_m": float(perp_m),
            "jump_m": float(jump_m),
            "suspect": suspect,
        })
        prev_xy = (proj.x, proj.y)

    return gpd.GeoDataFrame(
        rows,
        geometry=gpd.points_from_xy([r["snap_x"] for r in rows],
                                    [r["snap_y"] for r in rows]),
        crs=edges.crs,
    )

Expected output shape: one row per ping. The suspect column is your diagnostic: on a rural sample it should be almost entirely False; on an urban sample a suspect rate above a few percent is snapping telling you it cannot cope, which is your cue to escalate to the HMM. The perp_m and jump_m thresholds are the only knobs, and the child page covers how to set them per fleet.

Step 2 — Sketching the HMM Approach

You do not implement Viterbi to decide whether you need it — you reason about it. The sketch below shows the shape of the HMM so the cost is concrete: candidate retrieval per ping, an emission score per candidate, a transition score per candidate pair, and a Viterbi pass. This is a skeleton for sizing the decision, not a production matcher; the complete, tested implementation is in building an HMM-based map matcher with OSRM and Python.

import numpy as np


def emission_logp(perp_dist_m: np.ndarray, sigma_z: float = 4.07) -> np.ndarray:
    """Log-Gaussian emission: closer candidates score higher (less negative)."""
    return -0.5 * (perp_dist_m / sigma_z) ** 2 - np.log(sigma_z * np.sqrt(2 * np.pi))


def transition_logp(route_m: float, gc_m: float, beta: float = 3.0) -> float:
    """Penalise route distance that diverges from straight-line distance."""
    return -abs(route_m - gc_m) / beta - np.log(beta)


def viterbi_match(candidates, emissions, transitions):
    """
    candidates : list over pings; candidates[t] is a list of segment ids
    emissions  : emissions[t][k]      -> log emission prob of candidate k at ping t
    transitions: transitions[t][k][j] -> log transition prob from cand j (t-1) to k (t)

    Returns the most probable candidate index per ping (the matched path).
    """
    n = len(candidates)
    score = list(emissions[0])                       # log score to reach each cand at t=0
    back = [[-1] * len(candidates[0])]

    for t in range(1, n):
        new_score = []
        bp_t = []
        for k in range(len(candidates[t])):
            # best previous candidate j feeding candidate k
            totals = [score[j] + transitions[t][k][j] for j in range(len(candidates[t - 1]))]
            j_best = int(np.argmax(totals))
            new_score.append(totals[j_best] + emissions[t][k])
            bp_t.append(j_best)
        score = new_score
        back.append(bp_t)

    # backtrack from the best final candidate
    path = [int(np.argmax(score))]
    for t in range(n - 1, 0, -1):
        path.append(back[t][path[-1]])
    return path[::-1]

Expected output shape: one candidate index per ping, forming a connected path through the road graph. Note the two structural costs snapping does not have: you must retrieve multiple candidates per ping (not just the nearest), and you must compute a route distance between candidate pairs, which is the shortest-path or OSRM call that dominates the HMM’s runtime and infrastructure footprint.

Step 3 — A Rubric to Decide

Run the decision tree, then confirm with numbers. For a representative sample of your traces:

1. Measure snapping’s suspect rate. Run snap_trace on the labelled corpus. If the suspect rate is under ~1–2% and the segment F1 against ground truth clears your target, stop — snapping is enough, and every day you do not run a road-graph cache is a day of saved infrastructure.
2. Segment by condition. Split the corpus into rural/motorway and dense-urban buckets. It is common for snapping to pass comfortably on the former and fail on the latter. A hybrid — snap where the network is sparse, HMM where it is dense — is a legitimate and cheaper answer than “HMM everywhere.”
3. Check the sampling interval. If the median Δt exceeds ~10 seconds, weight toward the HMM even on moderate density: sparse pings starve proximity of context and only the transition model keeps the path connected.
4. Price the latency budget. Sub-millisecond, minimal-infrastructure requirements (edge devices, tight real-time loops) favour snapping; a 5–50 ms per-trace budget with a graph cache already in place removes the HMM’s main cost objection.
5. Compare F1 and Hausdorff, then pick the cheapest passer. Compute segment F1 and 95th-percentile Hausdorff distance for both algorithms on the corpus. Choose the least expensive algorithm that clears the threshold — not the most accurate one available.

The rubric’s bias is deliberate: escalate only when the evidence forces you to, because the HMM’s accuracy is worthless if snapping already met the target at a fraction of the cost.

Routing-Engine Integration Notes

Once you commit to the HMM, the transition probability needs route distances, and that is where a routing engine enters. Three integration details bite repeatedly:

Coordinate order. OSRM and Valhalla both accept [longitude, latitude] order. If your matcher works internally in projected [x, y] or in [lat, lon], back-project and swap before every API call. A silent lat/lon transposition places your fixes in a different hemisphere with no error response — the single most common integration bug.

Snapping radius per ping. OSRM’s /match endpoint takes a radiuses parameter in metres per coordinate. Derive it from the ping’s positional uncertainty rather than using a global constant: a tight radius on clean fixes suppresses false candidates, a relaxed radius on degraded fixes prevents dropped matches. If you ran a Kalman filter upstream, 3 · sqrt(P[0,0]) gives a principled 3-sigma radius.

Engine choice affects the transition model. OSRM, Valhalla/Meili, and GraphHopper differ in how they compute and expose route distances and in their rate limits. The selection is its own decision, covered in choosing a routing engine: OSRM vs Valhalla vs GraphHopper. For the algorithm decision here, the relevant point is that an HMM inherits a dependency on one of these engines (or a self-hosted road graph), whereas snapping needs only a spatial index over your own edges.

After matching, both algorithms feed the same downstream stages: speed profiling from raw GPS coordinates derives kinematics from the matched path, and stop detection partitions it into driving and dwell events.

Operational Troubleshooting

Deployment Checklist

• Trace characterised: sampling rate, urban fraction, and latency budget measured before an algorithm is chosen
• Coordinates and road network projected to a common metric CRS before any distance comparison
• Upstream outlier removal and (where noisy) Kalman filtering applied
• Geometric snapper run first; suspect rate measured against a labelled corpus
• Escalation to the HMM justified by segment F1 / Hausdorff, not by intuition
• Hybrid split considered: snap sparse/rural, HMM dense/urban
• HMM decoder confirmed as Viterbi or beam search — not treated as an alternative to the HMM
• Candidate count per ping capped (top-k) and route distances cached
• Routing-engine coordinate order verified as [lon, lat] on every call
• Per-ping snap radius derived from positional uncertainty, not a global constant
• Geometric fallback wired for HMM non-convergence; fallback rate alerted
• Suspect / fallback rates monitored per region as live health metrics

Parent topic: Trajectory Analysis & Map Matching Techniques

Related

• Geometric Nearest-Edge Snapping in Python — the full, tunable snapper this page sketches, with STRtree, a distance gate, and a heading check
• Hidden Markov Model Map Matching in Python — the model you escalate to, with emission, transition, and log-space Viterbi in depth
• Building an HMM-Based Map Matcher with OSRM and Python — production HMM wired to a routing engine for transition distances
• Choosing a Routing Engine: OSRM vs Valhalla vs GraphHopper — the engine decision an HMM inherits once you commit to it
• Speed Profiling from Raw GPS Coordinates — the downstream stage that consumes whichever matched path you produce