Map Matching Algorithm Prototype

Overview

This project implements a robust map-matching algorithm using geospatial data processing and machine learning techniques. The algorithm accurately matches GPS trajectory data to a road network, enabling intelligent classification of vehicular movement on highways versus service roads, even with noisy GNSS signals and coordinate biases.

Key Features

• GPS Data Parsing: Extract and process GPX files containing vehicle trajectory data
• Road Network Integration: Leverage OpenStreetMap (OSM) data via OSMnx for accurate road geometry
• Map Matching: Snap noisy GPS points to the nearest road segments using geometric algorithms
• Road Classification: Classify matched roads by type (highway, tertiary, residential, etc.)
• Interactive Visualization: Generate interactive HTML maps with Folium showing original vs. matched trajectories
• Data Cleaning: Handle invalid coordinates and normalize GPS data for preprocessing
• Point Interpolation: Add interpolated points between matched GPS coordinates for smoother trajectories

Project Structure

├── minipro.ipynb                 # Main Jupyter notebook with complete pipeline
├── minipro.py                    # Standalone Python script version
├── casestudy.ipynb               # Case study and documentation
├── *.gpx                          # Sample GPS trace files
├── *.csv                          # Processed GPS and road classification data
├── *.html                         # Generated interactive maps
└── *.geojson                      # Geospatial feature collections

Installation

Prerequisites

• Python 3.7+
• Jupyter Notebook (for running .ipynb files)

Required Libraries

pip install gpxpy pandas geopandas shapely osmnx folium scikit-learn matplotlib numpy regex

Key Dependencies:

• gpxpy: Parse GPX (GPS Exchange Format) files
• osmnx: Download and work with road networks from OpenStreetMap
• geopandas: Handle geospatial data and operations
• folium: Create interactive maps
• pandas: Data manipulation and analysis
• shapely: Geometric operations and coordinate transformations

Usage

1. Parse GPS Data (GPX File)

import gpxpy
import pandas as pd

def parse_gpx(file_path):
    with open(file_path, 'r') as gpx_file:
        gpx = gpxpy.parse(gpx_file)
    
    data = []
    for track in gpx.tracks:
        for segment in track.segments:
            for point in segment.points:
                data.append({
                    'latitude': point.latitude,
                    'longitude': point.longitude,
                    'time': point.time
                })
    return pd.DataFrame(data)

# Load GPX file
gpx_data = parse_gpx('path_to_gpx_file.gpx')

2. Classify Roads and Map Match

import osmnx as ox
import geopandas as gpd
from shapely.geometry import Point

def classify_roads(gpx_df, network_type='all'):
    # Load road network for the area
    central_point = (gpx_df['latitude'].mean(), gpx_df['longitude'].mean())
    graph = ox.graph_from_point(central_point, dist=3000, network_type=network_type)
    
    # Convert GPS points to GeoDataFrame
    gpx_df['geometry'] = gpx_df.apply(
        lambda row: Point(row['longitude'], row['latitude']), axis=1
    )
    gpx_gdf = gpd.GeoDataFrame(gpx_df, geometry='geometry', crs='EPSG:4326')
    gpx_gdf = gpx_gdf.to_crs(crs=ox.graph_to_gdfs(graph)[0].crs)
    
    # Find nearest road segments
    nearest_edges = ox.distance.nearest_edges(
        graph, gpx_gdf['geometry'].x, gpx_gdf['geometry'].y
    )
    edge_info = []
    for edge in nearest_edges:
        u, v, key = edge
        edge_data = graph[u][v][key]
        edge_info.append({
            'highway': edge_data.get('highway', 'unknown'),
            'road_name': edge_data.get('name', 'unknown')
        })
    return pd.concat([gpx_df, pd.DataFrame(edge_info)], axis=1)

# Run classification
classified_data = classify_roads(gpx_data)
classified_data.to_csv('classified_roads.csv', index=False)

3. Visualize Results

import folium
from folium.plugins import MarkerCluster

def plot_comparison_map(gpx_df, classified_data):
    base_map = folium.Map(
        location=[gpx_df['latitude'].mean(), gpx_df['longitude'].mean()],
        zoom_start=14
    )
    
    # Original GPS trajectory (blue)
    folium.PolyLine(
        list(zip(gpx_df['latitude'], gpx_df['longitude'])),
        color="blue", weight=2.5, tooltip="Original GPS Path"
    ).add_to(base_map)
    
    # Map-matched trajectory (green)
    folium.PolyLine(
        list(zip(classified_data['latitude'], classified_data['longitude'])),
        color="green", weight=2.5, tooltip="Map-Matched Path"
    ).add_to(base_map)
    
    return base_map

# Generate comparison map
comparison_map = plot_comparison_map(gpx_data, classified_data)
comparison_map.save('comparison_map.html')

4. Advanced: Map Matching with Interpolation

def map_match_with_interpolation(df, interpolation_distance=20):
    from shapely.geometry import LineString
    from shapely.ops import nearest_points
    import numpy as np
    
    gps_points = [Point(lon, lat) for lon, lat in zip(df['longitude'], df['latitude'])]
    central_point = (df['latitude'].mean(), df['longitude'].mean())
    graph = ox.graph_from_point(central_point, dist=3000, network_type='all')
    nodes, edges = ox.graph_to_gdfs(graph, nodes=True, edges=True)
    
    matched_points = []
    for i, gps_point in enumerate(gps_points):
        nearest_edge = ox.distance.nearest_edges(graph, gps_point.x, gps_point.y)
        u, v, key = nearest_edge
        edge_geom = edges.loc[(u, v, key), 'geometry']
        nearest_point = nearest_points(edge_geom, gps_point)[0]
        matched_points.append(nearest_point)
    
    return matched_points

Data Processing Pipeline

Step 1: GPS Data Cleaning

• Remove invalid coordinates using regex validation
• Normalize GPS data (handle missing timestamps, duplicates)
• Replace invalid entries with NaN and drop null values

import re
import numpy as np

def clean_coordinates(df, lat_col='latitude', lon_col='longitude'):
    valid_number = re.compile(r'^-?\\d+(\\.\\d+)?$')
    df[lat_col] = df[lat_col].apply(
        lambda x: float(x) if valid_number.match(str(x)) else np.nan
    )
    df[lon_col] = df[lon_col].apply(
        lambda x: float(x) if valid_number.match(str(x)) else np.nan
    )
    df.dropna(subset=[lat_col, lon_col], inplace=True)
    return df

Step 2: Road Network Extraction

• Download road network from OpenStreetMap using OSMnx
• Extract nodes and edges with highway classifications
• Create geometric representations of road segments

Step 3: Geometric Matching

• Project GPS data to road network CRS (EPSG:3857)
• Find nearest edge for each GPS point
• Snap GPS point to closest location on road segment

Step 4: Classification & Output

• Extract road type (highway, tertiary, residential, etc.)
• Extract road name from OSM data
• Generate interactive visualizations
• Export results to CSV/GeoJSON

Output Files

File	Description
original_gpx_map.html	Interactive map of raw GPS trajectory
map_matched_map.html	Interactive map of matched road segments
comparison_map.html	Side-by-side comparison of GPS vs. matched paths
classified_roads.csv	Matched GPS points with road classifications
classified_roads1.csv	Classified roads data format variant
.geojson	GeoJSON format of road networks and GPS data

Algorithm Details

Map Matching Components

1. Nearest Edge Lookup: OSMnx finds the closest road segment for each GPS point
2. Point Snapping: Geometric algorithms snap GPS coordinates to road geometries
3. Edge Geometry: LineString objects represent road segments in projected space
4. Coordinate Transformation: GPS data (EPSG:4326) → Road network CRS (typically EPSG:3857)

Interpolation Strategy

• Calculate distance between consecutive matched points
• Add interpolated points at regular intervals (default: 10-20m)
• Smooths trajectory and improves road coverage

Use Cases

• Navigation Systems: Enhance accuracy of GPS-based route guidance
• Traffic Management: Real-time congestion analysis and traffic pattern detection
• Urban Planning: Analyze vehicular movement patterns for infrastructure planning
• Autonomous Vehicles: Improve decision-making with accurate road classification
• Fleet Management: Optimize delivery routes using accurate map-matching

Sample Data

• Location: Various geographic coordinates (Brazil, India, UAE samples included)
• Format: GPX files with timestamps
• Points: 400-500+ GPS coordinates per trajectory
• Processing: ~1-2 seconds per 500-point trajectory

Performance Metrics

• Accuracy: Successfully classifies highway vs. service roads
• Processing Speed: Efficient for real-time applications
• Robustness: Handles noisy GPS signals with outlier removal

Future Enhancements

1. Real-Time Processing: Stream GPS data for live map-matching
2. ML Classification: Train models to distinguish road types with higher accuracy
3. Scalability: Optimize for large-scale networks
4. Additional Features: Incorporate speed, traffic conditions, and temporal data
5. Deep Learning: Integrate LSTM/CNN models for sequence prediction

Troubleshooting

Common Issues

• OSMnx Connection Error: Ensure internet connection and OSM API availability
• Coordinate Projection Issues: Verify CRS compatibility between GPS (EPSG:4326) and road network
• Empty Road Network: Increase dist parameter in ox.graph_from_point()
• Large Processing Time: Reduce dataset size or use smaller geographic areas

References

• OSMnx Documentation: https://osmnx.readthedocs.io/
• OpenStreetMap: https://www.openstreetmap.org/
• GeoPandas: https://geopandas.org/
• Folium: https://python-visualization.github.io/folium/

License

This project is open-source and available for educational and research purposes.

Contributors

Developed as a prototype for map-matching algorithm research using AI/ML techniques.