We address the problem of vehicle self-localization using visual odometry and freely available, crowd-sourced street maps. Given a short monocular video sequence captured from a moving vehicle, our system estimates the vehicle's position on an OpenStreetMap road network without GPS. We formulate this as a probabilistic inference problem, combining visual odometry measurements with a prior over plausible routes on the road network. Our approach achieves median localization error of approximately 3 meters in urban environments, demonstrating that crowd-sourced geographic data can serve as a powerful prior for visual localization.

GPS is the dominant technology for vehicle localization, yet it suffers from significant limitations in urban environments: multipath reflections from buildings, signal occlusion in tunnels and parking garages, and deliberate signal denial. These scenarios motivate the development of alternative localization methods that rely solely on onboard sensors. Visual odometry provides relative motion estimates from camera images but accumulates drift over time, making absolute localization impossible without additional constraints.

Our key insight is that freely available crowd-sourced maps, such as OpenStreetMap, encode rich topological and geometric constraints on vehicle motion. A vehicle must travel along roads, obey the road network topology, and its trajectory must be geometrically consistent with the road geometry. By combining noisy visual odometry with these map constraints in a principled probabilistic framework, we can achieve accurate absolute localization. Unlike methods that require pre-built visual databases (e.g., Google Street View), our approach uses only lightweight vector maps that are available globally.

Visual localization methods can be broadly categorized into image retrieval-based and structure-based approaches. Image retrieval methods match query images to a geo-tagged database, requiring extensive prior data collection. Structure-based methods use 3D point clouds from Structure-from-Motion (SfM) for precise localization but require dense 3D reconstructions of the environment. Map matching in the GPS/navigation community constrains GPS traces to road networks, but has not been combined with visual odometry for GPS-free localization.

We model the vehicle's trajectory as a path on a directed graph representing the road network. Each edge in the graph corresponds to a road segment with known geometry (polyline shape) and attributes (one-way, speed limit). The vehicle state at time t is defined by which edge it occupies and its position along that edge. Visual odometry provides noisy measurements of inter-frame translation and rotation. The goal is to compute the posterior distribution over vehicle states given the sequence of visual odometry measurements and the road network graph.

We perform inference using a particle filter adapted to the graph structure. Each particle represents a hypothesis about the vehicle's position on the road network. The transition model propagates particles along graph edges according to the measured velocity, respecting road connectivity and turn constraints. The observation model evaluates the likelihood of each particle by comparing the expected road geometry (curvature, heading changes) with the visual odometry measurements. Over time, particles on inconsistent routes are pruned by resampling, and the posterior concentrates on the correct location.

A critical component is the road geometry likelihood. As the vehicle traverses a road, the sequence of heading changes measured by visual odometry creates a distinctive "fingerprint" that can be matched against the road network geometry. Straight roads, sharp turns, gentle curves, and intersections each produce characteristic odometry patterns. The likelihood model captures these patterns using a Gaussian noise model on heading and speed measurements. This geometric matching is the primary mechanism by which ambiguity is resolved — even without recognizing landmarks, the shape of the road itself provides strong localization cues.

We evaluate on driving sequences in downtown Toronto, covering over 30 km of urban roads with diverse geometries. Using only a monocular dashboard camera and the OpenStreetMap road network, our system achieves a median localization error of 3.2 meters after 100 meters of driving and converges to sub-5-meter accuracy within 200 meters in 90% of test cases. The system correctly identifies the road segment within the first few turns, with ambiguity rapidly decreasing at intersections.

We analyze failure cases and find that the main sources of error are long straight roads with few distinctive features (where multiple hypotheses remain plausible) and OpenStreetMap inaccuracies (missing roads or incorrect geometry). We also compare against a GPS baseline, showing that our visual approach achieves comparable accuracy in open areas and significantly outperforms GPS in urban canyons where GPS error can exceed 50 meters.

We have demonstrated that accurate vehicle self-localization is possible using only visual odometry and crowd-sourced street maps, without GPS, 3D models, or visual databases. The probabilistic formulation on the road network graph naturally handles uncertainty and multi-modal hypotheses, converging to accurate estimates as geometric evidence accumulates. Our work suggests that the "wisdom of the crowd" — encoded in freely available geographic databases — provides a powerful complement to onboard perception for autonomous navigation.