Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Summary of common issues about fmm #138

Open
cyang-kth opened this issue Nov 3, 2020 · 9 comments
Open

Summary of common issues about fmm #138

cyang-kth opened this issue Nov 3, 2020 · 9 comments

Comments

@cyang-kth
Copy link
Owner

cyang-kth commented Nov 3, 2020

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.

  • The column names of this shapefile does not follow the default of setting of fmm. You need to explicitly specify the ID, source, target column name as fid,u and v respectively.
  • network = Network("network/edges.shp","fid","u","v")
@cyang-kth
Copy link
Owner Author

cyang-kth commented Nov 3, 2020

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.
      The returned matching result is null #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. Common issues with using fmm on OpenStreetMap data #99 The result of map matching is strange #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

image

  • 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
Copy link
Owner Author

cyang-kth commented Nov 3, 2020

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

@cyang-kth cyang-kth unpinned this issue Nov 18, 2020
@cyang-kth cyang-kth pinned this issue Nov 18, 2020
@cyang-kth
Copy link
Owner Author

cyang-kth commented Nov 25, 2020

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
Copy link
Owner Author

cyang-kth commented Dec 7, 2020

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
Copy link

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
Copy link
Owner Author

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

@Rajjat
Copy link

Rajjat commented Feb 6, 2022

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
Copy link

iTsingalis commented Jul 15, 2022

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
Copy link
Owner Author

cyang-kth commented Jul 17, 2022

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

4 participants