Barefoot

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 map matching services in the cloud.

Flexible and extensive

Barefoot consists of a software library and a (Docker-based) map server that provides access to street map data from OpenStreetMap and is flexible to be used in distributed cloud infrastructures as map data server or side-by-side with Barefoot's stand-alone servers for offline (matcher server) and online map matching (tracker server), or other applications built with Barefoot library. Access to map data is provided with a fast and flexible in-memory map data structure. Together with GeographicLib [1] and ESRI's geometry API [2], it provides an extensive set of geographic and geometric operations for spatial data analysis on the map.

<p align="center"> <img src="doc-files/com/bmwcarit/barefoot/barefoot-ecosystem.png?raw=true" width="650"> </p>

State-of-the-art map matching

Barefoot includes a Hidden Markov Model map matching implementation for both, offline map matching as proposed by Newson and Krumm in [3] and online map matching as proposed by Goh et al. in [4]. Offline map matching is the path reconstruction of a moving object from a recorded GPS trace. In contrast, online map matching determines an object's position and movement on the map iteratively from live GPS position updates in real-time.

Scalable and versatile

Barefoot is designed for use in parallel and distributed high-throughput systems [5]. For map matching large batches of GPS traces (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].

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.

Documentation

Manual

See wiki.

Javadoc

See Javadoc.

Showcases and Quick Starts

Online and offline HMM map matching

Barefoot provides a HMM map matching solution that can be used via the software library API, see the wiki, or via REST-like APIs provided with the stand-alone servers (matcher and tracker servers), see below or the wiki. This map matching solution covers both, online and offline map matching:

• Offline map matching: Most map matching applications rely on the matching of a sequence of position measurements recorded in the past (traces) for reconstruction of the object's path on the map. Offline map matching finds the best matching on the map and exploits availability of the full trace.
• Online map matching: In many other applications, objects send position updates to some monitoring system periodically. An online map matching system matches each position update right away and, hence, keeps track of the objects' movements on the map in (near) real-time.

Accuracy of map matching depends mostly on the quality and quantity of input data, which consists of a sequence of measurement samples over time (including position measurement). Samples are submitted as a whole sequence for offline map matching or one after another for online map matching. A single sample includes the following information:

• time of the measurement sample which is given in unix time.
• position of the object (point in space, e.g. GPS measurement).
• heading of the object (azimuth measurement) which is optional and, if available, increases map matching accuracy.

Matcher server (Quick Start)

Map matching of a GPS trace (violet markers) in Munich city area shown as geometrical path (orange path)

<p align="center"> <img src="doc-files/com/bmwcarit/barefoot/matcher/matching-satellite.png" width="700"> <br/> <a href="https://www.mapbox.com/about/maps/">&#xA9; Mapbox</a> <a href="http://www.openstreetmap.org/">&#xA9; OpenStreetMap</a> <a href="https://www.mapbox.com/map-feedback/"><b>Improve this map</b></a> <a href="https://www.digitalglobe.com/">&#xA9; DigitalGlobe</a> <a href="http://geojson.io">&#xA9; geojson.io</a> </p>

Map server

Note: The following example uses the setup of the test map server. For further details, see the wiki.

1. Install prerequisites.

   • Docker Engine (version 1.6 or higher, see https://docs.docker.com/installation/ubuntulinux/)

2. Download OSM extract (examples require oberbayern.osm.pbf)

   curl http://download.geofabrik.de/europe/germany/bayern/oberbayern-latest.osm.pbf -o barefoot/map/osm/oberbayern.osm.pbf
   

3. Build Docker image.

   cd barefoot
   sudo docker build -t barefoot-map ./map
   

4. Create Docker container.

   sudo docker run -it -p 5432:5432 --name="barefoot-oberbayern" -v ${PWD}/map/:/mnt/map barefoot-map
   

5. Import OSM extract (in the container).

   root@acef54deeedb# bash /mnt/map/osm/import.sh
   

   Note: To detach the interactive shell from a running container without stopping it, use the escape sequence Ctrl-p + Ctrl-q.

6. Make sure the container is running ("up").

   sudo docker ps -a
   ...
   

   Note: The output of the last command should show status 'Up x seconds'.

Matcher server

Note: The following example is a quick start setup. For further details, see the wiki.

1. Install prerequisites.

   • Maven (e.g. with sudo apt-get install maven)
   • Java JDK (Java version 7 or higher, e.g. with sudo apt-get install openjdk-1.7-jdk)

2. Package Barefoot JAR. (Includes dependencies and executable main class.)

   mvn package
   

   Note: Add -DskipTests to skip tests.

3. Start server with standard configuration for map server and map matching, and option for GeoJSON output format.

   java -jar target/barefoot-<VERSION>-matcher-jar-with-dependencies.jar --geojson config/server.properties config/oberbayern.properties
   

   Note: Stop server with Ctrl-c.

   Note: In case of 'parse errors', use the following Java options: -Duser.language=en -Duser.country=US

4. Test setup with provided sample data.

   python util/submit/batch.py --host localhost --port 1234  --file src/test/resources/com/bmwcarit/barefoot/matcher/x0001-015.json
   SUCCESS
   ...
   

   Note: On success, i.e. result code is SUCCESS, the output can be visualized with http://geojson.io/ and should show the same path as in the figure above. Otherwise, result code is either TIMEOUT or ERROR.

Tracker server (Quick Start)

Online (real-time) map matching of a GPS trace in Munich city area with most likely position (blue dot) and alternative possible positions and routes (green dots and paths with transparency according to their probability). Alternative positions and routes disappear with continuously processed updates, which shows the principle of online map matching converging alternatives over time.

<p align="center"> <img src="doc-files/com/bmwcarit/barefoot/tracker/monitor-1600x1000.gif" width="650"> <br/> <a href="https://www.mapbox.com/about/maps/">&#xA9; Mapbox</a> <a href="http://www.openstreetmap.org/">&#xA9; OpenStreetMap</a> <a href="https://www.mapbox.com/map-feedback/"><b>Improve this map</b></a> </p>

Map server

(see above)

Tracker server

Note: The following example is a quick start setup. For further details, see the wiki.

1. Install prerequisites.

   • Maven (e.g. with sudo apt-get install maven)
   • Java JDK (Java version 7 or higher, e.g. with sudo apt-get install openjdk-1.7-jdk)
   • ZeroMQ (e.g. with sudo apt-get install libzmq3-dev)
   • NodeJS (e.g. with sudo apt-get install nodejs)

2. Package Barefoot JAR. (Includes dependencies and executable main class.)

   mvn package
   

   Note: Add -DskipTests to skip tests.

3. Start tracker with standard configuration for map server, map matching, and tracking.

   java -jar target/barefoot-<VERSION>-tracker-jar-with-dependencies.jar config/tracker.properties config/oberbayern.properties
   

   Note: Stop server with Ctrl-c.

   Note: In case of 'parse errors', use the following Java options: -Duser.language=en -Duser.country=US

4. Install and start monitor (NodeJS server).

   Install (required only once)

   cd util/monitor && npm install && cd ../..
   

   ... and start:

   node util/monitor/monitor.js 3000 127.0.0.1 1235
   

5. Test setup with provided sample data.

   python util/submit/stream.py --host localhost --port 1234 --file src/test/resources/com/bmwcarit/barefoot/matcher/x0001-001.json
   SUCCESS
   ...
   

   _Note: On success, i.e. result code is SUCCESS, the tracking is visible in the browser on http://localhost:3000. Otherwise, result code