NavSight: GPS-Denied Real-Time Navigation on a Consumer Smartphone via Visual–Inertial Odometry and Offline HMM Map Matching

Abstract—Satellite navigation in parts of the Middle Easthas become unreliable due to wide-area GNSS disruption,leaving smartphone users without a dependable positionestimate precisely when they need one. We presentNavSight, an Android application that maintains a roadaccurate position estimate with no GPS and no networkconnectivity, using only the phone's camera and inertialsensors together with a preprocessed OpenStreetMap(OSM) extract bundled in the application. The pipelinecombines (i) a sparse optical-flow visual front-end withmulti-stage outlier rejection feeding an error-state extendedKalman filter; (ii) a metric speed estimator based oninverse-perspective mapping (IPM) of ground-plane flowwith a robust two-sided vote and an inertial bridge forturns; (iii) an on-device, offline implementation of hiddenMarkov-model (HMM) map matching in the style ofNewson and Krumm, decoded with a windowed Viterbialgorithm against an in-memory R-tree of road segments;and (iv) a routing-graph display constraint ("graph rail")that advances the displayed position only along connectedroad edges, structurally eliminating the parallel-roadteleports that plague projection-based matching. On a1.28 km urban drive with the phone as the only sensorpackage, NavSight reported 93.4% of the true route distanceand remained on the correct road sequence throughout,while the phone's GPS track on the same drive—corruptedby the local interference—overestimated distance by 33%.The visual front-end runs in 15.4 ms per frame (median) ona Samsung Galaxy S21 Ultra. All processing is on-device; noindividual algorithm is novel, and we position thecontribution as the end-to-end integration and theengineering required to make these established methodscooperate in real time on a phone