DOCSEARCHbyAlgolia
Submit Docs

GoTrackIt

repository·main·Indexed 43 days ago

https://github.com/zdsjjttlg/trackit

A Python package for map matching based on an improved Hidden Markov Model (HMM). It provides a full pipeline for road network processing, GPS data cleaning, high-performance matching algorithms (including FastMapMatching and multi-core parallel matching), and animated visualization. Version 0.3.18 and later introduces 'st-match' for spatio-temporal path matching and log-probability optimization to prevent floating-point overflow.

Tokens
55.5K
Snippets
141
Records
217
Agent score
54%

What's inside GoTrackIt

  1. Overview of GoTrackIt

    main

    GoTrackIt is a Python package developed by the data analysis team at Hangzhou Zhecheng Data Technology Co., Ltd. It implements a full-process map-matching workflow based on an improved Hidden Markov Model (HMM).

    By using probabilistic graphical modeling, GoTrackIt matches vehicle GPS trajectory data to road networks to obtain standardized spatio-temporal trajectories. This is useful for applications such as navigation, traffic monitoring, traffic governance, carbon emission accounting, and traffic modeling.

  2. Overview of gotrackit features

    main

    GoTrackIt is an end-to-end map matching package based on an improved Hidden Markov Model (HMM). It handles the entire workflow from road network acquisition to visualization.

    Core Capabilities:

    • Road Network Management: Modules for road network production and optimization tools. You do not need to provide your own road network to start.
    • GPS Data Handling: Includes modules for generating sample GPS data and interfaces for cleaning data (trip splitting, filtering/smoothing, stop point identification, and point densification).
    • Optimized Matching Algorithms:
      • Supports FastMapMatching based on path pre-computation.
      • Supports multi-core parallel matching.
      • Supports grid parameter searching.
      • Automatically performs path completion for disconnected locations.
    • Visualization: Outputs matching results in three formats:
      1. GPS point matching result tables (.csv).
      2. Vectorized matching layers.
      3. Vector layer matching animations (.html files) for intuitive inspection.

  3. Overview of Road Network Generation via NetReverse

    main

    The gotrackit package provides a method to generate road network data by analyzing paths returned from the Amap (高德) official Path Planning API.

    Key Concepts

    • Mechanism: Unlike OSM (OpenStreetMap) which queries an existing database, gotrackit reconstructs the network by requesting multiple Origin-Destination (OD) paths and analyzing the resulting trajectories.
    • Completeness: The completeness of the generated road network depends directly on the precision and quantity of the OD requests. A higher od_num results in more requested paths and higher network coverage.
    • Coordinate System: The road network obtained through this method uses the GCJ-02 coordinate system. This is different from the standard WGS-84 GPS coordinate system.

    Important Usage Restrictions

    • Non-Commercial Use Only: Due to the open-source license and the use of the Amap API, the generated data is strictly prohibited for commercial use. It is intended only for educational and scientific research purposes.
    • Commercial Requirements: For commercial applications, users should contact Amap customer service to purchase official road network data.

  4. Net Object Construction Requirements

    main

    When constructing a Net object, ensure the following requirements are met:

    • Coordinate System: Input link and node data must use WGS-84 EPSG:4326 geographic coordinates.
    • Projection: Manual specification of planar projection coordinate systems is no longer required; the system automatically determines the appropriate 6-degree zone.
    • Performance: For optimized projection calculations during matching, use the prj_cache parameter when building the Net (available in v0.3.17).

  5. Accelerate map matching with four strategies

    main

    gotrackit provides four acceleration strategies to improve matching performance. These strategies can be used individually or combined.

    1. Path Pre-computation: Pre-calculates shortest paths between network nodes and stores them in memory. This reduces the time spent on shortest path calculations during matching but requires significant memory.
    2. Multi-core Parallel Matching: Groups GPS data by agent_id and uses multiple CPU cores to process different groups simultaneously. This uses multi-processing, so memory usage increases by approximately $N$ times (where $N$ is the number of cores).
    3. Projection Parameter Pre-computation: Reduces the time spent on projection parameter calculations during matching. This is particularly effective for networks with very fine/dense line geometries.
    4. Spatial Hierarchical Association: Reduces the time spent on spatial association, which is highly effective for long trajectory matching in ultra-large-scale networks.
    # Example of combining strategies (conceptual)
my_net = Net(link_gdf=link, node_gdf=node, fmm_cache=True, prj_cache=True, is_hierarchical=True)
# ...
match_res, may_error_info, error_info = mpm.multi_core_execute(gps_df=gps_df, core_num=4)

  6. Understand the st-match probability adjustment

    main

    The st-match feature modifies the standard spatial transfer probability using a speed correction factor $\phi(v_{gps}, v_{route})$.

    Standard spatial-only probability: $$p_{transfer} = \frac{1}{\beta}e^{\frac{-\lvert l_1-l_2\rvert}{\beta}}$$

    With use_st=True, the probability becomes: $$p_{transfer} = \phi(v_{gps},v_{route}) \cdot \frac{1}{\beta}e^{\frac{-\lvert l_1-l_2\rvert}{\beta}}$$

    Where the correction factor is calculated as: $$\phi(v_{gps},v_{route}) = st_main_coe * \max(\min(1 - \frac{v_{gps} - v_{route}}{v_{route}}, 1) , st_min_factor)$$

    This formula ensures that probability is only reduced when the GPS speed exceeds the road's speed limit, helping to differentiate between paths that are spatially similar but have different speed characteristics.

  8. Key Features of GoTrackIt

    main

    GoTrackIt provides a comprehensive suite of tools for map-matching tasks:

    Data Management

    • Road Network & GPS Generation: Includes modules for road network production, road network optimization, and GPS sample data production, allowing users to start without pre-existing datasets.
    • GPS Data Cleaning: Provides interfaces for trip splitting, filtering/smoothing, and stop-point identification.

    Algorithm Optimizations

    • FastMapMatching: Supports path pre-computation for speed.
    • Parallel Processing: Supports multi-core parallel matching.
    • Parameter Tuning: Supports grid parameter searching.
    • Robustness: Automatically searches for and completes paths for disconnected locations and provides warnings for actual road network discontinuities.

    Visualization

    • Multiple Output Formats: Supports GPS point matching result tables, vectorized map layers (GeoJSON), and HTML-based animated visualizations for intuitive result inspection.

  9. Select Plane Projection Coordinate Systems (plain_crs)

    main

    For studies using plane projection coordinate systems, you can select a system based on the longitude of your study area's center point.

    6-Degree Zone Mapping:

    • Longitude range -180 ~ -174: EPSG:32601
    • Longitude range -174 ~ -168: EPSG:32602
    • ...
    • Longitude range 108 ~ 114: EPSG:32649
    • ...
    • Longitude range 174 ~ 180: EPSG:32660

    Global Coverage: If your study area covers the entire world, use EPSG:3857.

  10. Enable st-match for speed-aware path matching

    main

    Standard HMM path matching relies on spatial similarity, which can fail in scenarios like parallel roads. st-match introduces a speed (time) factor to correct transition probabilities. If a vehicle's average speed between two GPS points exceeds the speed limit of a candidate road, the probability of it being on that road decreases.

    To enable st-match:

    1. Set use_st=True in the MapMatch class parameters.
    2. Ensure your road network (link layer) contains a speed field representing the maximum speed limit.

    Note: You do not need to specify speed for every road, but you must ensure that competing roads (e.g., parallel segments) have non-empty speed values.

    # Example configuration for MapMatch
mpm = MapMatch(
    net=my_net, 
    use_st=True,  # Enable st-match
    # ... other parameters
)
# Ensure your link layer (gdf) has a 'speed' column

  11. How road network production works in gotrackit

    main

    Road network production in gotrackit follows a four-step process:

    1. Construct OD (Origin-Destination) coordinates: Generate start and end points.
    2. Request driving paths: Send OD pairs to the Amap Web Service API to retrieve driving routes.
    3. Store paths locally: Save the retrieved driving paths as binary path files.
    4. Parse and calculate: Parse the binary files to compute a [Standard Road Network].

    To perform these tasks, you primarily use the NetReverse class, which provides methods for requesting paths, parsing files, and generating/merging networks.

  12. Log-probability optimization in v0.3.18

    main

    Starting from version v0.3.18, gotrackit has optimized its Hidden Markov Model (HMM) calculations by directly computing log-probabilities instead of computing raw probabilities and then taking the logarithm. This change prevents floating-point precision overflow in long sequences and improves computational efficiency.

    Note for users: This change is transparent (non-breaking) for most workflows, but it changes the underlying mathematical approach from:

    • Old (<= v0.3.17): $p = e^{log(p)}$
    • New (>= v0.3.18): Direct calculation of $\log(p)$

    New calculation methods:

    • Transfer Probability: $p_{transfer} = \text{np.log}(\phi(v_{gps},v_{route})) - \frac{dis_{para}\lvert l_1-l_2\rvert}{\beta}$
    • Emission Probability: $p_{emission} = \text{np.log}(\omega(\theta)) - \frac{(dis_{para} \cdot x)^{2}}{2\sigma^2}$