fmm: A C++ repository from chengxuwei

Linux / macOS	Windows	Wiki	Docs

FMM is an open source map matching framework integrating hidden Markov models and precomputation. It solves the problem of matching noisy GPS data to a road network. By maximizing performance and functionality, FMM allows for map matching algorithms that are both efrficient and scalable to large volumes of data.

FMM provides Python and C++ APIs and can be used in the command line, in Jupyter notebooks, or in web app.

Features
Screenshots of notebook
Requirements
Getting Started
Documentation
Code docs for developer
Contact and citation

Features

High performance: C++ implementation using Rtree, optimized routing, parallel computing (OpenMP).
Python API: jupyter-notebook and web app
Scalability: millions of GPS points and millions of road edges.
Multiple data formats:
- Road network in OpenStreetMap or ESRI shapefile.
- GPS data in Point CSV, Trajectory CSV and Trajectory Shapefile (more details).
Detailed matching information: traversed path, geometry, individual matched edges, GPS error, etc. More information at here.
Multiple algorithms: FMM (for small and middle scale networks) and STMatch (for large scale road networks)
Platform support: Unix (ubuntu) , Mac and Windows(cygwin environment).
Hexagon match: 🎉 Match to the uber's h3 Hexagonal Hierarchical Geospatial Indexing System. Check the demo.

We encourage contribution with feature request, bug report or developping new map matching algorithms using the framework.

Screenshots of notebook

Map match to OSM road network by drawing

Explore the factor of candidate size k, search radius and GPS error

Explore detailed map matching information

Explore with dual map

Map match to hexagon by drawing

Explore the factor of hexagon level and interpolate

Source code of these screenshots are available at https://github.com/cyang-kth/fmm-examples.

Requirements

C++ Compiler supporting c++11 and OpenMP
CMake >=3.5: provides cross platform building tools
GDAL >= 2.2: IO with ESRI shapefile, Geometry data type
Boost Graph >= 1.54.0: routing algorithms used in UBODT Generator
Boost Geometry >= 1.54.0: Rtree, Geometry computation
Boost Serialization >= 1.54.0: Serialization of UBODT in binary format
~~Libosmium: a library for reading OpenStreetMap data. Requires expat and bz2.~~ (The direct input with OSM file is removed since the raw dataset may contain topology errors. It is suggested to use shapefile input downloaded from osmnx.)
swig: used for building Python bindings

Getting Started

These instructions are for the Ubuntu platform. For installation on Windows and Mac, refer to the installation instructions here.

Install Requirements

Update the ppa to install the required version (>=2.2) of GDAL.

sudo add-apt-repository ppa:ubuntugis/ppa
sudo apt-get -q update

Then, install all the requirements with

sudo apt-get install libboost-dev libboost-serialization-dev \
gdal-bin libgdal-dev make cmake libbz2-dev libexpat1-dev swig python-dev

Install C++ program and Python bindings
- Build and install the program with cmake.
```
# Under the project folder
mkdir build
cd build
cmake ..
make -j4
sudo make install
```
  This will build executable files under the build folder, which are installed to /usr/local/bin:
  - ubodt_gen: the Upper bounded origin destination table (UBODT) generator (precomputation) program
  - fmm: the program implementing the fast map matching algorithm
  - stmatch: the program implementing the STMATCH algorithm, no precomputation needed
  It will also create a folder python under the build path, which contains fmm bindings(fmm.py and _fmm.so) that are installed into the Python site-packages location (e.g., /usr/lib/python2.7/dist-packages).

Verification of Installation

Run command line map matching Open a new terminal and type fmm. You should see the following output:

------------ Fast map matching (FMM) ------------
------------     Author: Can Yang    ------------
------------   Version: 2020.01.31   ------------
------------     Applicaton: fmm     ------------
A configuration file is given in the example folder
Run `fmm config.xml` or with arguments
fmm argument lists:
--ubodt (required) <string>: Ubodt file name
--network (required) <string>: Network file name
--gps (required) <string>: GPS file name
--output (required) <string>: Output file name
--network_id (optional) <string>: Network id name (id)
--source (optional) <string>: Network source name (source)
--target (optional) <string>: Network target name (target)
--gps_id (optional) <string>: GPS id name (id)
--gps_geom (optional) <string>: GPS geometry name (geom)
--candidates (optional) <int>: number of candidates (8)
--radius (optional) <double>: search radius (300)
--error (optional) <double>: GPS error (50)
--pf (optional) <double>: penalty factor (0)
--log_level (optional) <int>: log level (2)
--output_fields (optional) <string>: Output fields
  opath,cpath,tpath,ogeom,mgeom,pgeom,
  offset,error,spdist,tp,ep,all
For xml configuration, check example folder
------------    Program finished     ------------

Run python script To verify that the Python bindings are working:

# Change to the parent folder which contains fmm_test.py
cd ../example/python
python fmm_test.py

Refer to the Q&A for any installation errors.

Documentation

Check https://fmm-wiki.github.io/ for installation, documentation.
Check example for simple examples of fmm.
🎉 Check https://github.com/cyang-kth/fmm-examples for interactive map matching in notebook.

Code docs for developer

Check https://cyang-kth.github.io/fmm/

Contact and citation

Can Yang, Ph.D. student at KTH, Royal Institute of Technology in Sweden

Email: cyang(at)kth.se

Homepage: https://people.kth.se/~cyang/

FMM originates from an implementation of this paper Fast map matching, an algorithm integrating hidden Markov model with precomputation. A post-print version of the paper can be downloaded at link. Substaintial new features have been added compared with the original paper.

Please cite fmm in your publications if it helps your research:

Can Yang & Gyozo Gidofalvi (2018) Fast map matching, an algorithm
integrating hidden Markov model with precomputation, International Journal of Geographical Information Science, 32:3, 547-570, DOI: 10.1080/13658816.2017.1400548

Bibtex file

@article{Yang2018FastMM,
  title={Fast map matching, an algorithm integrating hidden Markov model with precomputation},
  author={Can Yang and Gyozo Gidofalvi},
  journal={International Journal of Geographical Information Science},
  year={2018},
  volume={32},
  number={3},
  pages={547 - 570}
}

chengxuwei/fmm

Table of Contents