BMW CarIT Logo Typo

Blog

News, ideas and events

Blog

Barefoot release – An Open Source Java library for map matching with OpenStreetMap

Barefoot is an open source Java library for online and offline map matching with OpenStreetMap. Together with its extensive set of geometric and spatial functions, an in-memory map data structure and basic machine learning functions, it is a versatile basis for scalable location-based services and spatio-temporal data analysis on the map. It is designed for use in parallel and distributed systems and, hence, includes a stand-alone map matching server and can be used in distributed systems for a map matching service in the cloud.

Open source and open data

Barefoot is licensed under the business-friendly Apache License 2.0 and uses only business-friendly open source software with open map data from OpenStreetMap. Barefoot is already in production use of a spatial data analysis system on top of Apache Spark as in-house big data analytics service. With the release on GitHub (https://github.com/bmwcarit/barefoot), we open Barefoot for application and development with a broad community of professionals and enthusiasts. Any contribution, software or feedback, is very welcome.

State-of-the-art map matching

Map matching is the reconstruction of object positions or movements on the map from raw position data, e.g., GPS traces (Figure 1). A robust map matching solution is essential to a wide range of mobility applications and services, e.g., traffic analysis or personal mobility pattern analysis.

Figure 1: Screenshot of GPS positions and matched path on the map

Figure 1: Screenshot of GPS positions (violet) and matched path (orange) on the map, visualization made with (c) geojson.io, (c) Mapbox, (c) DigitalGlobe, (c) OpenstreetMap

Barefoot uses a Hidden Markov Model map matching algorithm, proposed by Newson and Krumm (Microsoft Research) in [1], together with OpenStreetMap data. It supports both, offline and online map matching [2]. Most applications rely on offline map matching, which matches a recorded GPS trace in a single step. In contrast, online map matching determines object positions and movements iteratively from live GPS position updates in real-time. Barefoot’s map matching accuracy with OpenStreetMap data is comparable to Newson and Krumm’s original algorithm with Microsoft’s map data (Figure 2).

Figure 2: Barefoot with open map data of OpenStreetMap shows comparable performance as Newson and Krumm with Microsoft's map data [1].

Figure 2: Barefoot with open map data of OpenStreetMap shows comparable performance as Newson and Krumm with Microsoft’s map data [1]. The benchmark is a single trip in the Seattle, WA, area of about 80 km route length, data provided by [1].

The Barefoot (eco-) system consists of a software library and a container-based (Docker) map server setup (Figure 3), which is flexible to be used as a central map repository in a distributed system or side-by-side with Barefoot’s stand-alone map matching server in a single node system. Access to map data is provided with a fast and flexible in-memory map data structure. Together with GeographicLib [3] (to which we contributed in the course of the project) and ESRI’s geometry API [4], it provides an extensive set of geographic and geometric operations for spatial data analysis on the map.

Figure 3: Barefoot (eco-) system with container-based (Docker) map server that enables versatile integration in parallel and distributed systems.

Figure 3: Barefoot (eco-) system with container-based (Docker) map server that enables versatile integration in parallel and distributed systems.

Scalable and versatile

Barefoot is desgined for use in parallel and distributed high-throughput systems [5]. For processing large amounts of data batches (offline map matching), it can be easily integrated in Apache Hadoop or Apache Spark (see example below), whereas Apache Storm and Apache Spark Streaming provide a runtime environment for processing massive data streams (online map matching). To support other data analysis functions, Barefoot comes with basic machine learning support, e.g., DBSCAN for spatial cluster analysis [6]. Further machine learning support is planned for future releases.

The following code example shows a simple map matching application for use in Apache Spark. It distributes a map matcher object as broadcast variable (a simple wrapper of Barefoot’s map matcher) that loads map data from a Barefoot map server (as an alternative one could store/load a serialized road map object in HDFS). After traces have been loaded and grouped into separate trips, map matching is done tripwise with the mmatch operation in parallel.

// Instantiate map matcher as broadcast variable in Spark Context (sc).
val matcher = sc.broadcast(
  new BroadcastMatcher(host, port, database, user, pass, config)
)
 
// Load trace data as RDD with tuples from CSV file:
// set of tuples (object-id: String, time: Long, position: Point)
val traces = sc.textFile("traces.csv").map(x => {
  val y = x.split(",")
  (y(0), y(1).toLong, new Point(y(2).toDouble, y(3).toDouble))
})
 
// Run a map job on RDD that uses the matcher instance.
val matches = traces.groupBy(x => x._1).map(x => {
  val trip = x._2.map({
    x => new MatcherSample(x._1, x._2, x._3)
  }).toList
  matcher.mmatch(trip)
)

References

[1] P. Newson and J. Krumm. Hidden Markov Map Matching Through Noise and Sparseness. In Proceedings of International Conference on Advances in Geographic Information Systems, 2009.

[2] C.Y. Goh, J. Dauwels, N. Mitrovic, M.T. Asif, A. Oran, and P. Jaillet. Online map-matching based on Hidden Markov model for real-time traffic sensing applications. In International IEEE Conference on Intelligent Transportation Systems, 2012.

[3] http://geographiclib.sourceforge.net/.

[4] https://github.com/Esri/geometry-api-java.

[5] S. Mattheis, K. Al-Zahid, B. Engelmann, A. Hildisch, S. Holder, O. Lazarevych, D. Mohr, F. Sedlmeier, and R. Zinck. Putting the car on the map: A scalable map matching system for the Open Source Community. In INFORMATIK 2014: Workshop Automotive Software Engineering, 2014.

[6] M. Ester, H.-P. Kriegel, J. Sander, X. Xu. A Density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), 1996.