Summary of common issues about fmm

cyang-kth commented 3 years ago

This page contains a summary of common issues in using fmm.

Firstly, make sure you pull the latest version of the program.

Road network

Road network should be downloaded following the script at https://github.com/cyang-kth/osm_mapmatching. The original network downloaded from osmnx will not work for fmm because

there is no ID for each edge, osmid may be a tuple
each bidirectional edge should be saved as two edges with reverse geometry and source, target node

If you use your own network, make sure your network has

The network contains fields representing id, source and target fields, which represents ID of a line, source node ID and target node ID. (The names of the three fields can be specified by the user.). As shown in the example below, the three values can be (13,5,6).
A bidirectional road should be stored as two reverse lines
- Their ID should be different (e.g., 12 and 13)
- Source and target fields should be reverted for the reverse edge. If one is source 5 target 6, the other one should be source 6, target 5.
- The geometry of the feature should be reversed for the feature. If one is LineString(0 1, 1 1, 2 2) the other one should be LineString(2 2, 1 1, 0 1).
Check the example network file at the data folder edges.shp.

The network downloaded from https://github.com/cyang-kth/osm_mapmatching generally satisfies the above requirement.

cyang-kth commented 3 years ago

Trajectories not matched.

In case that a trajectory cannot be matched to the road network. The reason could be

The road network topology is not correct.
- The direction of road edge should be correct, which could be verified with a commercial navigation map. It is also recommended to download from reliable sources such as OSM and follow this tutorial to generate topology https://github.com/cyang-kth/osm_mapmatching.
  https://github.com/cyang-kth/fmm/issues/139
- A bidirectional edge should be stored in as two directed edge in reverse directions. It is strongly recommended to download OSM network in shapefile using OSMNX. #99 #123
- Their ID should be different (e.g., 12 and 13)
- Source and target fields should be reverted for the reverse edge. If one is source 5 target 6, the other one should be source 6, target 5.
- The geometry of the feature should be reversed for the feature. If one is LineString(0 1, 1 1, 2 2) the other one should be LineString(2 2, 1 1, 0 1).
- Visualize and verify the network topology in QGIS

The GPS trajectory contains two points that are distant from each other. For FMM, their distance could not be fetched from UBODT.
- You can enlarge the delta used for precomputing UBODT
- You can set stmatch which does not need precomputation but could be less efficient.

cyang-kth commented 3 years ago

Weird map matching result

If you saw some weird matching result, where the matched trajectory significantly deviate from the original one, the reasons could be

Road network topology is not correct (Direction problem and disconnected edges). #99, #123,
Trajectory is too noisy, it is hard to infer the path manually
The trajectory contains reverse movement. #136, #98
- Set the reverse_tolerance parameter to 0-1.0 to check if the problem can be corrected.
The candidate size is too small. Increase k and r to include more candidates. https://github.com/cyang-kth/fmm/issues/189

cyang-kth commented 3 years ago

Configurations setting

Which algorithm to select?
FMM needs to do the precomputation, which occupies a lot of storage and it may be unsuitable for very big road network. STMATCH does not need precomputation but it is less efficient. You could try stmatch to explore other configurations such as candidate size k, search radius r and GPS error e.
How to select candidate size k, search radius r and GPS error e?
- k: 16 to 32
- r: 300 meters or above (if you are using GPS data in unit of degrees, setting the parameter as 0.003 degrees)
- e: 50 to 100 meters (if you are using GPS data in unit of degrees, setting the parameter as 0.005 degrees)
How to select the upper of delta? It depends on the frequency of your GPS data. A large value is needed for sparse GPS data. You can set 3km (if you are using GPS data in unit of degrees, setting the parameter as 0.03 degrees) and enlarge the value if a large proportion could not be matched.

cyang-kth commented 3 years ago

Be careful with unit of configurations

If your GPS data is in degrees e.g., latitude and longitude, your network should also be in degree. The configurations are also defined in degrees:

radius: search radius. If you want to set 300 meters, define it as 300/1.132e5 (degree)
gps_error: If you want to set 50 meters, define it as 50/1.132e5 (degree)
delta: if you want to set 3km, define it as 3000/1.132e5 (degree)
vmax: if you want to set 80km/h, define it as 80/3.6/1.132e5 (degree/s)

Extremely large UBODT or it takes long time to generate UBODT.

It is likely you set the wrong delta value.
If you network is in GPS degree unit, scale your delta by dividing 1.1e5. As one degree corresponds to approximately 1.1e5 meters. Otherwise, it may takes too long to generate an every pair UBODT. If you want to set 3km, define delta as 3000/1.132e5 (degree)

xingminw commented 3 years ago

How about the unit of the output? For example, the error and the offset, do they also need to multiply the 1.132e5 to get the unit in meters?

cyang-kth commented 3 years ago

All units are the same as GPS data and network data.

Rajjat commented 2 years ago

I am getting the following warning in most of the trajectories.

[warning] [fmm_algorithm.cpp:289] Traj 0 unmatched as points 83 and 84 not connected

which leads to no map matching to the given trajectory. I am using https://github.com/cyang-kth/osm_mapmatching link for network generation. Is it due to data quality? I was looking into HMM algorithm and some research says that "Matching break is a common problem in map-matching, which is mainly caused by trajectory outliers." However, most of the map matching algorithms (graphhopper, Barefoot) uses HMM. Is there any way out for matching which contains a few outliers?

Please let me know.

iTsingalis commented 2 years ago

I am getting the following warning in most of the trajectories.

[warning] [fmm_algorithm.cpp:289] Traj 0 unmatched as points 83 and 84 not connected

which leads to no map matching to the given trajectory. I am using https://github.com/cyang-kth/osm_mapmatching link for network generation. Is it due to data quality? I was looking into HMM algorithm and some research says that "Matching break is a common problem in map-matching, which is mainly caused by trajectory outliers." However, most of the map matching algorithms (graphhopper, Barefoot) uses HMM. Is there any way out for matching which contains a few outliers?

Please let me know.

I am having the same problem with a gps dataset [1] getting eros like

[warning] [fmm_algorithm.cpp:289] Traj 0 unmatched as points 83 and 84 not connected

in almost all cases. This warning returns empty results, i.e. not any matching is performed. I have tried multiple parameters like

_config = FastMapMatchConfig(k_arg=16, r_arg=300/1.132e5, gps_error=50/1.132e5)

but the warning persists. In addition, for the record, my example is based on [2]. In case you want to see the data, I am attaching a few trajectories taken from [1]. Could you please provide some suggestions on how to overcome this problem? Any help is highly appreciated! 1372741036620000446.txt 1372749928620000166.txt

[1] https://www.kaggle.com/c/pkdd-15-predict-taxi-service-trajectory-i

[2] https://github.com/cyang-kth/osm_mapmatching

1372690597620000513.txt 1372692499620000620.txt 1372699631620000667.txt 1372706586620000075.txt 1372709186620000136.txt

cyang-kth commented 2 years ago

Try to smooth your trajectory before performing map matching, it might help. There is also a parameter called reverse_tolerance, try to set it to 1 to check if it works. @iTsingalis

cyang-kth / fmm