[OSRM-talk] Map-Matching geometry
Hi all, I'm wondering how the geometry returned by the map-matching algorithm is computed. I compared it to the geometry of viaroute when 1. requesting a route for each consecutive pair of points in the (map-matching output) trip. 2. requesting a route for the whole trip with via points. The geometry matched with neither 1 nor 2. I'm trying to fill the gaps of the map-matching result with optimal routes in between and was set on using the 'geometry' parameter of the 'match' service but now I'm unsure whether that's what I really want. Any help would be appreciated. Thanks. Best regards, Matthias -- Matthias Schwamborn University of Osnabrück Tel.: +49-541-969-7167 Institute of Computer Science Fax:+49-541-969-2799 Albrechtstr. 28 E-mail: schwamb...@informatik.uos.de D-49076 Osnabrück, Germany http://cs.uos.de/schwamborn/ signature.asc Description: OpenPGP digital signature ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
Re: [OSRM-talk] U-turns in Map-Matching Algorithm
Hi Patrick, thanks for the clarification. So this check is for the input coordinates, only, right? What if some candidates introduce a U-turn (e.g., due to some outliers in the input data)? Thanks. Best, Matthias On 22/07/15 12:17, Patrick Niklaus wrote: Hey Matthias, What the algorithm at that point does is check if the original trace might contain a U-Turn at that point. If so it does not add separate candidates for each direction (but bidirectional edge based nodes), resulting in the possibility of U-Turns at that position. Hope this helps. Best, Patrick On Wed, Jul 22, 2015 at 11:28 AM, Matthias Schwamborn schwamb...@informatik.uos.de wrote: Hi all, looking at the code in plugins/match.hpp [1], I noticed that candidates resulting in a U-turn are allowed but wouldn't you say that these candidates are actually pretty unlikely compared to candidates that don't result in a U-turn? Am I missing something here? Thanks. Best, Matthias [1] https://github.com/Project-OSRM/osrm-backend/blob/master/plugins/match.hpp#L104 -- Matthias Schwamborn University of Osnabrück Tel.: +49-541-969-7167 Institute of Computer Science Fax:+49-541-969-2799 Albrechtstr. 28 E-mail: schwamb...@informatik.uos.de D-49076 Osnabrück, Germany http://cs.uos.de/schwamborn/ ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk -- Matthias Schwamborn University of Osnabrück Tel.: +49-541-969-7167 Institute of Computer Science Fax:+49-541-969-2799 Albrechtstr. 28 E-mail: schwamb...@informatik.uos.de D-49076 Osnabrück, Germany http://cs.uos.de/schwamborn/ signature.asc Description: OpenPGP digital signature ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
[OSRM-talk] U-turns in Map-Matching Algorithm
Hi all, looking at the code in plugins/match.hpp [1], I noticed that candidates resulting in a U-turn are allowed but wouldn't you say that these candidates are actually pretty unlikely compared to candidates that don't result in a U-turn? Am I missing something here? Thanks. Best, Matthias [1] https://github.com/Project-OSRM/osrm-backend/blob/master/plugins/match.hpp#L104 -- Matthias Schwamborn University of Osnabrück Tel.: +49-541-969-7167 Institute of Computer Science Fax:+49-541-969-2799 Albrechtstr. 28 E-mail: schwamb...@informatik.uos.de D-49076 Osnabrück, Germany http://cs.uos.de/schwamborn/ signature.asc Description: OpenPGP digital signature ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
Re: [OSRM-talk] Map Matching Plugin Questions
Thanks a bunch, Patrick! That cleared things up for me considerably. Best, Matthias On 07/05/15 12:40, Patrick Niklaus wrote: - Did you implement all of the described HMM break conditions (route localization, low probability routes, GPS outliers)? After reading the code in OSRM, I was only able to find the low probability routes condition. Did I overlook something? The localization is implemented by choosing the candidates before we start the algorithm. For each input point we adaptively chose between 5 and 10 candidates based on the distance to the previous input point. That part of the algorithm can be found in plugins/match.hpp. The outliers test is not implemented, I'm not sure it would add much value over the limited search radius for candidates combined with the pruning based on transition probability. - As far as I understand, MAX_DISTANCE_DELTA corresponds to the delta when comparing the route length and great circle distance for the low probability routes condition. The paper states a delta of 2000m, the implementation uses a delta of 200m. Feature or bug? I found that 2000m is a little bit on the conservative side. At least for my data 200m worked pretty well (sampling period was approximately 7s). Please not that most parameters are tuned for sampling periods of around 5 to 10 seconds. - What exactly does the confidence return value mean? Since we are dealing with real world data, matching will fail for some traces. That might be cause the trace is too noisy or the data from OpenStreetMap has problems like connectivity errors. To get a handle on that I gathered some empirical data on mismatched traces and tried to find a good feature to classify matchings are valid or invalid. The feature that worked best for me was the ratio between trace length and matching length (the intuition here is that invalid matchings tend to contain loops where detours are taken). I used that labeled data to fit a Laplacian distribution and constructed a naive Bayes classifier based on that. The confidence is the probability P(x \in valid). The values are only based on ~800 labeled traces which specific sampling rate, so take that value with a grain of salt for your data. What is missing is a good parameter selection based on the sample rate of the input. Its not clear when I will have time again to do that (for now massaging the data to fit the current constraints works quite well). ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk -- Matthias Schwamborn University of Osnabrück Tel.: +49-541-969-7167 Institute of Computer Science Fax:+49-541-969-2799 Albrechtstr. 28 E-mail: schwamb...@informatik.uos.de D-49076 Osnabrück, Germany http://cs.uos.de/schwamborn/ signature.asc Description: OpenPGP digital signature ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
[OSRM-talk] Map Matching Plugin Questions
Hi all, I'm currently playing with the new map matching plugin in OSRM 4.6.0. Great work! It's been really useful for me so far. I also read the corresponding paper by Newson and Krumm and have some questions about the implementation: - Did you implement all of the described HMM break conditions (route localization, low probability routes, GPS outliers)? After reading the code in OSRM, I was only able to find the low probability routes condition. Did I overlook something? - As far as I understand, MAX_DISTANCE_DELTA corresponds to the delta when comparing the route length and great circle distance for the low probability routes condition. The paper states a delta of 2000m, the implementation uses a delta of 200m. Feature or bug? - What exactly does the confidence return value mean? Thanks! Best, Matthias -- Matthias Schwamborn University of Osnabrück Tel.: +49-541-969-7167 Institute of Computer Science Fax:+49-541-969-2799 Albrechtstr. 28 E-mail: schwamb...@informatik.uos.de D-49076 Osnabrück, Germany http://cs.uos.de/schwamborn/ signature.asc Description: OpenPGP digital signature ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
Re: [OSRM-talk] vector::_M_range_check error
Hi John, thanks for the hint. I double-checked and even prepared the map files again with 0.4.1. However, the error still persists. Best, Matthias On 19/06/14 20:18, John Firebaugh wrote: Hi Matthias, One thing to check is that the data files being used were generated with the same version of OSRM. I have seen this error when a 0.4.1 server used data files generated with 0.3.9. John On Thu, Jun 19, 2014 at 5:33 AM, Matthias Schwamborn schwamb...@informatik.uos.de mailto:schwamb...@informatik.uos.de wrote: Hi all, I've set up my own OSRM server (v0.4.1) and encountered the following error several times so far (for different (src,dst) pairs): [warn] [server error] code: vector::_M_range_check, uri: /viaroute?loc=55.76191121265607,37.599698264694666loc=55.76045290194501,37.59812508836046z=14 I also tried getting more information by compiling osrm-routed in debug mode, but to no avail. Any pointers to what this error means and how I can avoid it? Thanks. Best, Matthias -- Matthias Schwamborn University of Osnabrück Tel.: +49-541-969-7167 tel:%2B49-541-969-7167 Institute of Computer Science Fax:+49-541-969-2799 tel:%2B49-541-969-2799 Albrechtstr. 28 E-mail: schwamb...@informatik.uos.de mailto:schwamb...@informatik.uos.de D-49076 Osnabrück, Germany http://cs.uos.de/schwamborn/ ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org mailto:OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk -- Matthias Schwamborn University of Osnabrück Tel.: +49-541-969-7167 Institute of Computer Science Fax:+49-541-969-2799 Albrechtstr. 28 E-mail: schwamb...@informatik.uos.de D-49076 Osnabrück, Germany http://cs.uos.de/schwamborn/ signature.asc Description: OpenPGP digital signature ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
[OSRM-talk] vector::_M_range_check error
Hi all, I've set up my own OSRM server (v0.4.1) and encountered the following error several times so far (for different (src,dst) pairs): [warn] [server error] code: vector::_M_range_check, uri: /viaroute?loc=55.76191121265607,37.599698264694666loc=55.76045290194501,37.59812508836046z=14 I also tried getting more information by compiling osrm-routed in debug mode, but to no avail. Any pointers to what this error means and how I can avoid it? Thanks. Best, Matthias -- Matthias Schwamborn University of Osnabrück Tel.: +49-541-969-7167 Institute of Computer Science Fax:+49-541-969-2799 Albrechtstr. 28 E-mail: schwamb...@informatik.uos.de D-49076 Osnabrück, Germany http://cs.uos.de/schwamborn/ signature.asc Description: OpenPGP digital signature ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
[OSRM-talk] Operating on the original road network graph
Hi all, I would like to implement plugins which operate on the original road network graph (nodes=road segment end points/crossings, edges=road segments). However, I must admit that I'm somewhat overwhelmed by all the graph-related data structures. Which one is used for the original graph? Is it even accessible during runtime (since it doesn't seem to be used for routing etc.)? Can you please give me some pointers on where to start? Thanks! Best regards, Matthias -- Matthias Schwamborn University of Osnabrück Tel.: +49-541-969-7167 Institute of Computer Science Fax:+49-541-969-2799 Albrechtstr. 28 E-mail: schwamb...@informatik.uos.de D-49076 Osnabrück, Germany http://cs.uos.de/schwamborn/ signature.asc Description: OpenPGP digital signature ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
