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.

Table of Contents

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

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

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

3. 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}
}