Skip to content

Home

Jump to bottom
Balzer82 edited this page Jan 10, 2019 · 6 revisions

Overview

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.

References

[1] GeographicLib.

[2] ESRI's Geometry API.

Map Server

Docker container

Setup

  1. Install prerequisites.
  1. Build Docker image.
cd barefoot
sudo docker build -t barefoot-map ./map
  1. Create Docker container.

Note: Give the a name otherwise Docker chooses a name.

sudo docker run -it -p 5432:5432 --name="<container>" -v ${PWD}/map/:/mnt/map barefoot-map
  1. Import OSM extract (inside the container).
root@acef54deeedb# bash /mnt/map/osm/import.sh <osm> <database> <user> <password> <config> slim|normal

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

  • For importing an OpenStreetMap extract <osm>, the *.osm.pbf file must be placed into the directory map/osm/ from outside the container, which is then accessible inside the container at /mnt/map/osm/.
  • The import script reads the extract and writes it into a database with specified name and credentials, i.e. <database>, <user>, and <password>.
  • A road type configuration <config> must be provided by its path and it must describe (in some JSON format) all road types to be imported. An example for roads of motorized vehicles is included at /mnt/map/tools/road-types.json.
  • The standard import mode normal runs a bunch of SQL queries to import OSM extract of any size, whereas slim mode runs the import in a single query which is faster but requires more memory. The latter should be used only for smaller OSM extracts (extracts of at most the size of e.g. Switzerland).

Docker overview

Some basic Docker commands for container administration:

  • Start/stop container:
sudo docker start <container>
sudo docker stop <container>
  • Attach to container (for maintenance):
sudo docker attach <container>
root@acef54deeedb# sudo -u postgres psql -d <database>
psql (9.3.5)
Type "help" for help.

<database>=# \q
root@acef54deeedb#

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

  • Execute commands on container (e.g. a shell for maintenance):
sudo docker exec -it <container> /bin/bash
root@acef54deeedb# sudo -u postgres psql -d <database>
psql (9.3.5)
Type "help" for help.

<database>=# \q
root@acef54deeedb# exit

Note: Here, shell can be closed and container doesn't stop.

  • List containers:
$ sudo docker ps -a
CONTAINER ID        IMAGE                     COMMAND                CREATED             STATUS              PORTS                      NAMES
acef54deeedb        barefoot-map              /bin/sh -c 'service    3 minutes ago       Up 2 seconds        0.0.0.0:5432->5432/tcp     <container>

Whitebox: PostgreSQL/PostGIS

Note: A manually PostgreSQL/PostGIS database setup is no longer a supported approach for setting up map servers. The following documentation is a 'whitebox' documentation for development of Docker-based map servers.

  1. Install prerequisites.
  • PostgreSQL (version 9.3 or higher)
  • PostGIS (version 2.1 or higher)
  • Osmosis (versionb 0.43.1 or higher)
  • Python (version 2.7.6 or higher)
  • Psycopg2
  • NumPy
  • Python-GDAL
  1. Setup the database and include extensions.
createdb -h <host> -p <port> -U <user> <database>
psql -h <host> -p <port> -U <user> -d <database> -c "CREATE EXTENSION postgis;"
psql -h <host> -p <port> -U <user> -d <database> -c "CREATE EXTENSION hstore;"

  1. Import the OSM data.

  2. Download and set up OSM database schema.

psql -h <host> -p <port> -U <user> -d <database> -f map/osm/pgsnapshot_schema_0.6.sql
  1. Import OSM extract with Osmosis.
osmosis --read-pbf file=<osm.pbf-file> --write-pgsql host=<host>:<port> user=<user> database=<database> password=<password>

Note: It may be necessary to define a temporary directory for use by Osmosis, e.g. if Osmosis stops with error 'No space left on device'. To do so, run the following commands beforehand:

JAVACMD_OPTIONS=-Djava.io.tmpdir=<path-to-tmp-dir>
export JAVACMD_OPTIONS
  1. Extract OSM ways in intermediate table.

Import of OSM extract can be usually run in slim mode, which creates table <ways-table> in a single query:

map/tools/osm2ways --host <host> --port <port> --database <database> --table <ways-table> --user <user> --slim

If memory is not sufficiently available, normal mode should be used, which requires a prefix <prefix> for temporary tables, which prevents overwriting of existing tables:

map/tools/osm2ways --host <host> --port <port> --database <database> --table <ways-table> --user <user> --prefix <prefix>

Note: To see SQL commands without being executed, use option --printonly.

  1. Compile Barefoot map data.

Transform ways <ways-table> into routing ways <bfmap-table>. A road type configuration <config> must be provided by its path and it must describe (in some JSON format) all road types to be imported. An example for roads of motorized vehicles is included at map/tools/road-types.json.

 map/tools/ways2bfmap --source-host <host> --source-port <port> --source-database <host> --source-table <ways-table> --source-user <user> --target-host <host> --target-port <port> --target-database <database> --target-table <bfmap-ways> --target-user <user> --config <config>

Note: To see SQL commands without being executed, use option --printonly

Library

Installation

Local installation (Maven)

Note: Use this approach only if Barefoot is not available with a public Maven repository.

  1. Install prerequisites.
  • Git (e.g. with sudo apt-get install git)
  • 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)
  1. Checkout the respository.
git clone https://github.com/bmwcarit/barefoot.git
cd barefoot
  1. Install JAR to your local Maven repository.

Note: Maven tests will fail if the test map server hasn't been setup as shown here.

mvn install

... and to skip tests (if test map server has not been set up) ...

mvn install -DskipTests
  1. Add dependency to your Java project with Maven.
<dependency>
  	<groupId>com.bmw-carit</groupId>
  	<artifactId>barefoot</artifactId>
  	<version>VERSION</version>
</dependency>
  1. Set up a map server, see here, or a test map server, see here.

Build Javadoc

mvn javadoc:javadoc

See here.

APIs

See here.

Testing

Library (Java/Maven)

Note: Tests for library development require a test map server, see above. The setup is the same as the standard setup but uses a pre-configuration (defaults) of the import script.

Test map server
  1. Install prerequisites.
  1. Download OSM extract oberbayern.osm.pbf.
curl http://download.geofabrik.de/europe/germany/bayern/oberbayern-latest.osm.pbf -o map/osm/oberbayern.osm.pbf
  1. Build Docker image.
cd barefoot
sudo docker build -t barefoot-map ./map
  1. Create Docker container.
sudo docker run -it -p 5432:5432 --name="barefoot-oberbayern" -v ${PWD}/map/:/mnt/map barefoot-map
  1. Import OSM extract (inside the container) and use defaults.
root@acef54deeedb# bash /mnt/map/osm/import.sh
Execute tests
mvn test

Map tools (Python)

Note: This is only useful, if you work on the Python import scripts.

  1. Install prerequisites.
  1. Build Docker image.
cd barefoot
sudo docker build -t barefoot-map ./map
  1. Create test container.
sudo docker run -it --name="barefoot-test" -v ${PWD}/map/:/mnt/map barefoot-map
  1. Run test script (in the container).
root@8160f9e2a2c0# bash /mnt/map/tools/test/run.sh

Stand-alone servers

Matcher server

The matcher server is a stand-alone server for offline map matching, which is 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. The figure below shows a map matched GPS trace (violet markers) in Munich city area which is shown by the path's geometry on the map (orange path).


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

Setup

  1. Setup a map server, see here, or a test map server, see here.

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

mvn package

Note: Add -DskipTests to skip tests.

  1. 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 [--slimjson|--debug|--geojson] /path/to/server/properties /path/to/mapserver/properties

Note: Stop server with Ctrl-c.

  • Map server properties include access information to map server.

    Note: An example is included at config/oberbayern.properties which can be used as reference or for testing.

  • Server properties include configuration for the server and map matching. Settings for configuration are explained here.

    Note: An example is included at config/server.properties and can be used for testing. The details for parameter settings are shown below.

Usage

The matcher server provides a REST-like API for sending requests with GPS traces and receiving map matched traces. A simple submission script is provided and can be tested with the test map server and the provided sample data:

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

A map matching request is a text message with a JSON array of JSON objects in the following form:

[
	{"id":"x001","time":1410324847000,"point":"POINT (11.564388282625075 48.16350662940509)"},
	...
]
  • id is user-specific identifier and has no further meaning for map matching or the server.
  • time is a timestamp in milliseconds unix epoch time.
  • point is a position (measurement) in WKT (well-known-text) format and with WGS-84 projection (SRID 4326). (In other words, this may be any GPS position in WKT format.)
  • azimuth is (optional) heading information of the object given as azimuth in degrees from north clockwise.
Response message formats

The matcher server's default response format is the JSON representation of the k-state data structure, see here. To change default output format, use the following options for the server:

  • --slimjson: Server outputs JSON format with map matched positions, consisting of road id and fraction as precise position on the road, and routes between positions as sequences of road ids.
  • --debug: Server outputs a JSON format similar to slim JSON format, but with timestamps of the measurements and geometries of the routes in WKT format.
  • --geojson: Server outputs the geometry of the map matching on the map in GeoJSON format.

In addition, a request may also demand a certain response format which can be specified with the submission script using option --format=slimjson|debug|geojson.

Tracker server

The tracker server is a stand-alone server for online map matching. Here, objects send position updates to some the tracking server periodically. The tracker server matches each position update right away (online) and, hence, keeps track of the objects' movements on the map in (near) real-time. The setup consists of a tracker server and a monitor, as illustrated below, which provides a website that shows object movements in the browser.

Setup

  1. Install prerequisites.
  • ZeroMQ (e.g. with sudo apt-get install libzmq3-dev)
  • NodeJS (e.g. with sudo apt-get install nodejs)
  1. Package Barefoot JAR. (Includes dependencies and executable main class.)
mvn package

Note: Add -DskipTests to skip tests.

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

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


© Mapbox © OpenStreetMap Improve this map

Usage

The tracker server provides a REST-like API for sending position updates with GPS points to the tracker server. A simple submission script that simulates a stream of position messages with an included sample data is provided:

python util/submit/stream.py --host localhost --port 1234  --file src/test/resources/com/bmwcarit/barefoot/matcher/x0001-015.json
Position message format

A position update is a text message with a JSON object of the following form:

{"id":"x001","time":1410324847000,"point":"POINT (11.564388282625075 48.16350662940509)"}
  • id is user-specific identifier and has no further meaning for map matching or the server.
  • time is a timestamp in milliseconds unix epoch time.
  • point is a position (measurement) in WKT (well-known-text) format and with WGS-84 projection (SRID 4326). (In other words, this may be any GPS position in WKT format.)
  • azimuth is (optional) heading information of the object given as azimuth in degrees from north clockwise.

Parameters

The server properties includes configuration of the server, e.g. TCP/IP port number, number of threads, etc., and parameter settings of the map matching.

Parameter Default Description
server.port 1234 The port of the map matching server.
server.timeout.request 15000 Maximum time in milliseconds of waiting for a request after connection has been established.
server.timeout.response 60000 Maximum time in milliseconds of waiting for reponse processing before a timeout is triggered and processing is aborted.
server.connections 20 Maximum number of connections to be established by clients. Also number of executor threads for reponse handling (I/O), which should be a multiple of the number of processors/cores of the machine to fully exploit the machine's performance.
matcher.sigma 5.0 Standard deviation of the position measurement error in meters, which is usually 5 meters for standard GPS error, as probability measure of matching candidates for position measurements on the map.
matcher.lambda 0.0 Rate parameter of negative exponential distribution for probability measure of routes between matching candidates. (The default is 0.0 which enables adaptive parameter setting, depending on sampling rate and input data, other values (manually fixed) may be 0.1, 0.01, 0.001 ...)
matcher.radius.max 200 Maximum radius for matching candidates to be searched in the map for respective position measurements in meters.
matcher.distance.max 15000 Maximum length of routes to be searched in the map for transitions between matching candidates in meters. (This avoids searching the full map for candidates that are for some reason not connected in the map, e.g. due to missing road links.)
matcher.distance.min 0 Minimum distance in meters for measurements to be considered for matching. Any measurement taken in less than the minimum distance from the most recent measurement is skipped. (This avoids unnnecessary matching of positions with very high measurement rate, useful e.g. if the object speed varies.)
matcher.interval.min 1000 Minimum time interval in milliseconds for measurements to be considered for matching. Any measurement taken in less than the minimum interval after the most recent measurement is skipped. (This avoids unnnecessary matching of positions with very high measuremnt rate, useful e.g. if the measurement rate varies.)
matcher.threads 8 Number of executor threads for reponse processing (map matching), which should at least the number of processors/cores of the machine to fully exploit the machine's performance.
tracker.port 1235 The port of the tracker server for subscribing to state updates, used by the tracker monitor for getting state updates pushed.
tracker.state.ttl 60 Maximum time to live (TTL) for object tracking states in seconds. Each state is discarded if there was no state update over one TTL.

Application programming interfaces (APIs)

HMM map matching

Foundation

A Hidden Markov Model (HMM) assumes that a system's state is only observable indirectly via measurements over time. This is the same in map matching where a sequence of position measurements (trace), recorded e.g with a GPS device, contains implicit information about an object's movement on the map, i.e. roads and turns taken. Hidden Markov Model (HMM) map matching is a robust method to infer stochastic information about the object's movement on the map, cf. [1] and [2], from measurements and system knowledge that includes object state candidates (matchings) and its transitions (routes).

A sequence of position measurements z0, z1, ..., zT is map matched by finding for each measurement zt, made at some time t (0 ≤ t ≤ T), its most likely matching on the map sti from a set of matching candidates St = {st1, ..., stn}. A set of matching candidates St is here referred to as a candidate vector. For each consecutive pair of candidate vectors St and St+1 (0 ≤ t < T), there is a transition between each pair of matching candidates sti and st+1j which is the route between map positions in the map. An illustration of the HMM with matching candidates and transitions is shown in the figure below.

To determine the most likely matching candidate, it is necessary to quantify probabilities of matching candidates and respective transitions. A HMM defines two types of probability measures:

  • A position measurement is subject to error and uncertainty. This is quantified with an emission probability p(zt | st) that defines a conditioned probability of observing measurement zt given that the true position in the map is st, where p(zt | st) ∼ p(st | zt).

Here, emission probabilities are defined with the distance between measured positions to its true position is used to model measurement errors which is described with gaussian distribution with some standard deviation σ (default is σ = 5 meters).

  • All transitions between different pairs of matching candidates st-1 to st have some measure of plausiblity which is quantified with a transition probability p(st | st-1) that is a conditioned probability of reaching st given that st-1 is the origin.

    Here, transition probabilities are quantified with the difference of routing distance and line of sight distance between respective position measurements. Transition probabilities are distributed negative exponentially with a rate parameter λ (default is λ = 0.1) which is the reciprocal of the mean.

In HMM map matching, we distinguish two different solutions to map matching provided by our HMM filter:

  • Our HMM filter determines an estimate s̅t of the object's current position which is the most likely matching candidate st ∈ St given measurements z0 ... zt, which is defined as:

s̅t = argmax(st ∈ St) p(st|z0 ... zt),

where p(st|z0 ... zt) is referred to as the filter probability of st and can be determined recursively:

p(st|z0...zt) = p(st|zt) · Σ(st-1 ∈ St-1) p(st|st-1) · p(st-1|z0 ... zt-1).

  • In addition, we extend our HMM filter to determine an object's most likely path s0 ... sT, that is the most likely sequence of matching candidates st ∈ St given the full knowledge of measurements z0 ... zT, which is defined as:

    s0 ... sT = argmax(sT ∈ ST) p(s0 ... sT|z0 ... zT),

    where we define p(s0 ... st|z0 ... zt) as the probability of the most likely sequence that reaches matching candidate st, referred to as the sequence probability of st, and can be also determined recursively:

    p(s0 ... st|z0 ... zt) = p(st|zt) · argmax(st-1 ∈ St-1) p(st|st-1) · p(s0 ... st-1|z0 ... zt-1).

Note: Here, p(s0 ... st|z0 ... zt) is defined as the probability of the most likely sequence that reaches candidate st, whereas in other literature, cf. [4], it is defined as the probability of the sequence s0 ... st. This is used for convenience to enable implementation of online and offline map matching in dynamic programming manner (according to online Viterbi algorithm). Nevertheless, the solution is the same.

Since both solutions are recursive both can be used for online and offline algorithms, i.e. online and offline map matching.

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.

Building blocks and API

Barefoot's map matching API consists of four main components. This includes a matcher component that performs map matching with a HMM filter iteratively for each position measurement zt of an object. It also includes a state memory component that stores candidate vectors St and their probabilities p; and it can be accessed to get the current position estimate s̅t or the most likely path (s0 ... st). Further, it includes a map component for spatial search of matching candidates St near the measured position zt; and a router component to find routes ⟨st-1,st⟩ between pairs of candidates (st-1,st).

A map matching iteration is the processing of a position measurement zt to update the state memory and includes the following steps:

  1. Spatial search for matching candidates st ∈ St in the map given measurement zt. St is referred to as a candidate vector for time t.
  2. Fetch candidate vector St-1 from memory if there is a candidate vector for time t-1 otherwise it returns an empty vector.
  3. For each pair of matching candidates (st-1, st) with st-1 ∈ St-1 and st ∈ St, find the route ⟨st-1,st⟩ as the transition between matching candidates.
  4. Calculate filter probability and sequence probability for matching candidate st, and update state memory with probabilities p and candidate vector St.

A simple map matching application shows the use of the map matching API (for details, see the Javadoc):

import com.bmwcarit.barefoot.roadmap.Loader;
import com.bmwcarit.barefoot.roadmap.Road;
import com.bmwcarit.barefoot.roadmap.RoadMap;
import com.bmwcarit.barefoot.roadmap.RoadPoint;
import com.bmwcarit.barefoot.roadmap.TimePriority;
import com.bmwcarit.barefoot.spatial.Geography;
import com.bmwcarit.barefoot.topology.Dijkstra;

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

// Instantiate matcher and state data structure
Matcher matcher = new Matcher(map, new Dijkstra<Road, RoadPoint>(), new TimePriority(),
        new Geography());

// Input as sample batch (offline) or sample stream (online)
List<MatcherSample> samples = readSamples();

// Match full sequence of samples
MatcherKState state = matcher.mmatch(samples, 1, 500);

// Access map matching result: sequence for all samples
for (MatcherCandidate cand : state.sequence()) {
    cand.point().edge().base().refid(); // OSM id
    cand.point().edge().base().id(); // road id
    cand.point().edge().heading(); // heading
    cand.point().geometry(); // GPS position (on the road)
    if (cand.transition() != null)
        cand.transition().route().geometry(); // path geometry from last matching candidate
}

Online map matching processes samples and updates state memory iteratively:

// Create initial (empty) state memory
MatcherKState state = new MatcherKState();

// Iterate over sequence (stream) of samples
for (MatcherSample sample : samples) {
	// Execute matcher with single sample and update state memory
    state.update(matcher.execute(state.vector(), state.sample(), sample), sample);

    // Access map matching result: estimate for most recent sample
    MatcherCandidate estimate = state.estimate();
    System.out.println(estimate.point().edge().base().refid()); // OSM id
}

k-State data structure

A k-State data structure is a state memory for map matching. It organizes sets of matching candidates as candidate vectors, and provides access to:

  • a matching estimate which is the most likely matching candidate s̅t for time t and represents an estimate of the object's current position on the map,
  • and an estimate of the sequence which is the most likely sequence of matching candidates (s0 ... st) and represents the object's most likely path on the map.

The k-State data structure is initially empty and must be updated with state vectors St. After the first update with state vector S0 (left subfigure), it contains matching candidates (circles) with a pointer to the estimate (thick circle). In the second matching iteration (middle subfigure), the matcher fetches state vector S0 and determines for each matching candidate s1i ∈ S1 its sequence and filter probability, and determines the most likely predecessor candidate in S0 (black arrows). After that, state vector S1 is used to update the state memory (right subfigure) which, in turn, updates pointers to the estimate and the most likely sequence (thick arrow).

Each matching iteration repeats basically the same procedure: fetching state vector St-1 (left subfigure), calculating for each candidate st ∈ St filter and sequence probability and its most likely predecessor in St-1 (middle subfigure), and updating state memory (right subfigure). With every update the k-State data structure converges, i.e. it removes all matching candidates that are neither relevant to the estimate nor to the most likely sequence.

Parameters

A k-State data structure provides two parameters to configure a maximum capacity in the number of state vectors stored in k-State (mostly relevant to online map matching):

  • k bounds the number of state vectors to at most k+1 state vectors with k ≥ 0, i.e. state vectors St-k ... St. If k is negative it is unbounded.
  • τ bounds the number of state vectors in time to only those state vectors that cover the time interval [t-τ,t] where τ > 0 and t is the time of the most recent state update with St. If τ ≤ 0 it is unbounded.

Note: Both parameters can be combined such that both bounding conditions hold. In turn, configuring k-State with k < 0 and τ ≤ 0 is fully unbounded, which is the default.

JSON format

A k-State's JSON representation is a JSON Object with parameters k and t (τ) and two JSON arrays sequence and candidates. JSON object sequence contains the sequence of candidate vectors where each vector element is a matching candidate that is represented by an identifier, i.e. candid, and an identifier to its predecessor, i.e. predid, in the candidate's most likely sequence. Matching candidates are contained in the JSON array candidates with respective identifier id that is referenced by candid and predid, and filter probability filtprob and sequence probability seqprob. ( The count is used only for convergence of the k-State data structure and is the number of matching candidates in the successor candidate vector that refer to this matching candidate as its predecessor.)

A matching candidate candidate further includes a position in the map point, i.e. road identifier road and fraction frac, as well as the transition transition from its predecessor, if it has one. The transition is a route route consisting of source and target, with road and frac to specify the respective position in the map, and a JSON array roads that gives the sequence of roads for the route.

{
  "sequence": [
    {
      "sample": {
        "id": "a1396ab7-7caa-4c31-9f3c-8982055e3de6",
        "point": "POINT (11.536577179945997 48.14905556426255)",
        "time": 1410325357000
      },
      "vector": [
        {
          "candid": "e649f976-564a-4760-9a74-c82ba6c4653e",
          "predid": ""
        }
      ]
    },
    {
      "sample": {
        "id": "a1396ab7-7caa-4c31-9f3c-8982055e3de6",
        "point": "POINT (11.536219651738836 48.14672536176703)",
        "time": 1410325372000
      },
      "vector": [
        {
          "candid": "648cd380-f317-4ebb-b9e2-650a80054bf7",
          "predid": "e649f976-564a-4760-9a74-c82ba6c4653e"
        },
        {
          "candid": "6b347e77-eb92-43d3-a60d-69d9bb71f9d4",
          "predid": "e649f976-564a-4760-9a74-c82ba6c4653e"
        }
      ]
    }
  ],
  "candidates": [
    {
      "count": 2,
      "candidate": {
        "filtprob": 0.11565717758307356,
        "id": "e649f976-564a-4760-9a74-c82ba6c4653e",
        "point": {
          "frac": 0.4104557158596576,
          "road": 9362030
        },
        "seqprob": -1.0999901830140701
      }
    },
    {
      "count": 0,
      "candidate": {
        "filtprob": 0.2370833183857761,
        "id": "648cd380-f317-4ebb-b9e2-650a80054bf7",
        "point": {
          "frac": 0.06531311234979269,
          "road": 8533290
        },
        "seqprob": -3.2870414276380666,
        "transition": {
          "route": {
            "roads": [
              9362030,
              ...
              8533290
            ],
            "source": {
              "frac": 0.4104557158596576,
              "road": 9362030
            },
            "target": {
              "frac": 0.06531311234979269,
              "road": 8533290
            }
          }
        }
      }
    },
    ...
  ],
  "k": -1,
  "t": -1
}

Scalable map matching

Barefoot is designed for use in parallel and distributed systems. This includes features such as:

  • serializable road map (store road map as serialized object in HDFS or send it from one machine to another)
  • JSON format of KState data structure (interchangeable and human readable map matching state information)
  • container-based map server setup (flexible to be used on high-end server systems or in low-end environments for development)
Apache Spark (scalable offline map matching)

The following code example shows a simple map matching application for use in an Apache Spark cluster. It distributes a map matcher object as broadcast variable (BroadcastMatcher.scala is a simple wrapper class), which loads map data from a map server (as an alternative map data can be stored/loaded as serialized object via HDFS).

// 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 from CSV file asset 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)
)

The example code uses a simple wrapper of Barefoot's matcher. It initializes matcher as static member (Singleton) and loads map data on first matching invocation.

object BroadcastMatcher {
  private var instance = null: Matcher

  private def initialize(host: String, port: Int, name: String, user: String, pass: String, config: String) {
    if (instance != null) return
    this.synchronized {
      if (instance == null) { // initialize map matcher once per Executor (JVM process/cluster node)
        val reader = new PostGISReader(host, port, name, "bfmap_ways", user, pass, Configuration.read(new JSONObject(config)))
        val map = RoadMap.Load(reader)

        map.construct();

        val router = new Dijkstra[Road, RoadPoint]()
        val cost = new TimePriority()
        val spatial = new Geography()

        instance = new Matcher(map, router, cost, spatial)
      }
    }
  }
}

@SerialVersionUID(1L)
class BroadcastMatcher(host: String, port: Int, name: String, user: String, pass: String, config: String) extends Serializable {

  def mmatch(samples: List[MatcherSample]): MatcherKState = {
    mmatch(samples, 0, 0)
  }

  def mmatch(samples: List[MatcherSample], minDistance: Double, minInterval: Int): MatcherKState = {
    BroadcastMatcher.initialize(host, port, name, user, pass, config)
    BroadcastMatcher.instance.mmatch(new ArrayList[MatcherSample](samples.asJava), minDistance, minInterval)
  }
}

Note: The shown example initializes a matcher instance for each Spark Executor. That means that if your Spark cluster configuration uses two Executors per machine, a machine instantiates two matcher and two map objects. To reduce memory consumption, one might configure only one Executor per machine.

Apache Storm, Kafka, and Cassandra (scalable online map matching)

TBD.

Spatial analysis

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

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:

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<Point> points = new LinkedList<Point>();
...
// DBSCAN algorithm with radius neighborhood of 100 and minimum density of 10
Set<List<Point>> clusters = DBSCAN.cluster(points, 100, 10);

for (List<Point> cluster : clusters) {
	MultiPoint multipoint = new MultiPoint();
	for (Point point : cluster) {
		multipoint.add(point);
	}
	GeometryEngine.geometryToGeoJson(multipoint);
}

As an example, the figure below shows typical locations for standing times of a New York City taxi driver (hack license BA96DE419E711691B9445D6A6307C170) derived by spatial cluster analysis of start and end points of all trips in January 2013. For details on the data set, see below.


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

Clone this wiki locally