Pedestrian and Bicycle matching

[fmguerreiro]

Hello,
I'm working on a project which tracks users on foot and on bicycle.
Barefoot seems to be only able to match on motor vehicles (which makes sense given the name of the copywrite holder).
I was curious if it would be difficult to add these capabilities to Barefoot. I noticed there is a bfmap/road-types.json file which I assume states the road types to get from OSM. I tried adding the footway, cycleway and path tags, but the final result was the same (only slower).

Thanks for taking the time to read. I'm not sure if this constitutes as an issue, but any information you can provide would be much appreciated.

Cheers,
Filipe

[smattheis]

Map matching of pedestrians and bicycles is an interesting use case, but is not in development by ourselves. I have two considerations/suggestions:

1. A modification of road-types.json is the right way to start, but map import scripts will definitely not consider special tags such as oneways for bicycle ways. HOWEVER, when tracking real people they often (especially with bicycles) don't care about oneways and having a high sampling rate of > 0.1 Hz (sampling interval of at most 10 seconds), map matching will probably give better results when explicitly not considering oneways.

   If you like, send me your road-types.json configuration and a link to the OSM area you're interested in; and I will see if there is something that could be improved.

2. Once a meaninful routing map for bicycle and pedestrians is import, map matching should work, however, I never tested this use case. Hence, you could alternatively try to find a tool/converter for OSM data to routing maps with bicycle and pedestrian ways; and setup a PostgreSQL/PostGIS table on your own. The table requires just the following format:

   CREATE TABLE my_table (
   gid bigint NOT NULL,
   osm_id bigint NOT NULL,
   class_id integer NOT NULL,
   source bigint NOT NULL,
   target bigint NOT NULL,
   length double precision NOT NULL,
   reverse double precision NOT NULL,
   maxspeed_forward integer,
   maxspeed_backward integer,
   priority double precision NOT NULL);
   SELECT AddGeometryColumn('my_table,'geom',4326,'LINESTRING',2);

   Note: You can ignore values of columns length, class_id, reverse (-1 = oneway, 1 = 'two'way), speed and priority, especially because bicycle and pedestrian will probably favour shortest path and do not need to consider road types and speed limits. Also a way's length is calculated from its geometry when the library loads the data. Once you have setup such a table, I can try to give you support to some degree for tuning your map matching.

[fmguerreiro]

Thanks for getting back to me so quickly.

You were right, the import script just works. I had forgotten to delete the generated .bfmap file before importing again.

The matching also worked pretty well, almost perfect! The drawback is that the matching time increased from 15 to 50 seconds, on an off-road bicycle track with 3000 points. Not sure if much can be done about that.

For reference, the area of interest: http://geojson.io/#map=14/38.7732/-9.4397 , and the modified road-types file: https://web.ist.utl.pt/ist173940/road-types.json

Thanks again for the help Sebastian.
Filipe

[smattheis]

Wow, that's actually great to hear! There may be some parameters you could tune to reduce computation time:
In the Matcher class there is the following line:

final double bound =
  Math.max(1000d, Math.min(distance, ((candidates.one().time() - predecessors.one()
    .time()) / 1000) * 100));

The bound parameter limits the route search depth in th case the target point of route search cannot be found. (If this isn't bound, search can spread over the full graph). In dependence on your sampling interval, you could decrease this parameter to some meaning full value.
The calculation is as follows: Take the maxmimum of (1) a minimum of 1000 meters and (2) the time between samples in seconds multiplied with maximum velocity of 100 meters/second (360km/h), but (3) bound it to a maximum of distance (15000 meters by default).
In (1), you could define a minimum threshold of 100 meters; in (2) you could set the maxmimun reasonable velocity to e.g. 90 km/h which is 25 m/s; and in (3) configure e.g. 3000 meters upper bound.
Using this parameters, the calculation is as follows:

final double bound =
  Math.max(100d, Math.min(distance, ((candidates.one().time() - predecessors.one()
    .time()) / 1000) * 25));

Is it possible to get a sample track from you for experimenting with it? I would highly acknowledge such a contribution!
BTW, if you have the ground truth of your track you can benchmark your results with the Benchmark class. It provides Benchmark.align to do sequence alignment, Benchmark.error to calculate a standardized error value, and Benchmark.candidatesToSequence to convert matcher result into the required format.

[smattheis]

I would close this issue since it's not really an issue any more, but please keep me up to date and feel free to contribute. :)

[fmguerreiro]

Hello again,

Just a quick update.
Here is the bicyle track (3000 points) I used for testing:
https://web.ist.utl.pt/ist173940/sintraBike/bikeTrack.geojson

I tried your suggestion of changing the Matcher with your recommended values. I recompiled with Maven, but the result was the same as the original and took the same time (about 50 seconds). Here is the result: https://web.ist.utl.pt/ist173940/sintraBike/defaultMatcher.json

I noticed the config/server.properties file and changed the matcherMaxDistance to 10000 (from 15000) and matcherMaxRadius to 100 (from 200). This decreased the time by almost half (30 seconds) and still gave great results. Here it is: https://web.ist.utl.pt/ist173940/sintraBike/modifiedMatcher.json

Thanks again for the support and great suggestions.
Cheers,
Filipe

[smattheis]

Thanks for the great insight! I forgot to mention, that server.properties overwrites the code defaults. Maximum radius decreases the number of matching candidates and, hence, decreases not only computation time but also quality of map matching while the other parameters usually don't decrease quality that much.
You can also set minDistance to e.g. 3 or 5 meters which will then skip some samples during matching (those with a distance to the last matched sample point below the threshold) if they are too dense on the track and usually don't give any additional information. This will also decrease computation time but may also decrease quality a little bit.
I'm very happy to see that it worked out for you! I would probably commit a variant of your road types configuration in future which will be under Apache License 2.0. Please give me feedback, if this is okay for you.

[fmguerreiro]

I had not thought of changing the minimum distance. I'll keep fiddling with the parameters based on your advice until I'm satisfied.
And yes, of course, if my pestering was helpful in some way, then by all means!
Thanks for all your help.
Filipe