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.

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)

© Mapbox © OpenStreetMap Improve this map © DigitalGlobe © geojson.io

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)

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

3. Build Docker image.

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

4. Create Docker container.

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

5. Import OSM extract (in the container).

   bash 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").

   bash 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.)

   bash 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.

   bash 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.

   bash 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.

© Mapbox © OpenStreetMap Improve this map

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.)

   bash mvn package

   Note: Add -DskipTests to skip tests.

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

   bash 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) bash cd util/monitor && npm install && cd ../.. ... and start: bash node util/monitor/monitor.js 3000 127.0.0.1 1235

5. Test setup with provided sample data.

   bash 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 is either TIMEOUT or ERROR.

Spatial search and operations

Spatial operations

A straight line between two points, here Reykjavik (green marker) and Moskva (blue marker), on the earth surface is a geodesic (orange). The closest point on a geodesic to another point, here Berlin (violet marker), is referred to as the interception point (red marker).

© Mapbox © OpenStreetMap Improve this map © DigitalGlobe © geojson.io

import com.bmwcarit.barefoot.spatial.Geography;
import com.bmwcarit.barefoot.spatial.SpatialOperator;

import com.esri.core.geometry.Point;

SpatialOperator spatial = new Geography();

Point reykjavik = new Point(-21.933333, 64.15);
Point moskva = new Point(37.616667, 55.75);
Point berlin = new Point(13.408056, 52.518611);

double f = spatial.intercept(reykjavik, moskva, berlin);
Point interception = spatial.interpolate(reykjavik, moskva, f);

Other spatial operations and formats provided with GeographicLib and ESRI Geometry API:

• Geodesics on ellipsoid of rotation (lines on earth surface)
• Calculation of distances, interception, intersection, etc.
• WKT (well-known-text) import/export
• GeoJSON import/export
• Geometric operations (convex hull, overlap, contains, etc.)
• Quad-tree spatial index

Spatial search

Spatial search in the road map requires access to spatial data of the road map and spatial operations for distance and point-to-line projection. Barefoot implements the following basic search operations:

• radius
• nearest
• k-nearest (kNN)

The following code snippet shows a radius search given a certain map:

import com.bmwcarit.barefoot.roadmap.Loader;
import com.bmwcarit.barefoot.roadmap.Road;
import com.bmwcarit.barefoot.roadmap.RoadMap;

import com.esri.core.geometry.GeometryEngine;

RoadMap map = Loader.roadmap("config/oberbayern.properties", true).construct();

Point c = new Point(11.550474464893341, 48.034123185269095);
double r = 50; // radius search within 50 meters
Set<RoadPoint> points = map.spatial().radius(c, r);

for (RoadPoint point : points) {
    GeometryEngine.geometryToGeoJson(point.geometry()));
    GeometryEngine.geometryToGeoJson(point.edge().geometry()));
}

A radius search, given a center point (red marker), returns road segments (colored lines) with their closest points (colored markers) on the road.

© Mapbox © OpenStreetMap Improve this map © DigitalGlobe © geojson.io

Simple routing (Dijkstra)

TBD.

Spatial cluster analysis

Spatial cluster analysis aggregates point data to high density clusters for detecting e.g. points of interest like frequent start and end points of trips. For that purpose, Barefoot includes a DBSCAN implementation for simple density-based spatial cluster analysis, which is an unsupervised machine learning algorithm. For details, see the wiki.

The following code snippet shows the simple usage of the algorithm:

``` java import com.bmwcarit.barefoot.analysis.DBSCAN;

import com.esri.core.geometry.GeometryEngine; import com.esri.core.geometry.MultiPoint; import com.esri.core.geometry.Point;

List points = new LinkedList(); ... // DBSCAN algorithm with radius neighborhood of 100 and minimum density of 10 Set<Li