Matching

candidate

class pytrack.matching.candidate.Candidate(node_id, edge_osmid, obs, great_dist, coord)[source]

Class to represent a candidate element.

Parameters

node_id (str) – OSM node ID.
edge_osmid (str) – OSM edge ID.
obs (tuple) – Coordinate of actual GPS points.
great_dist (float) – Distance between candidate and actual GPS point.
coord (tuple) – Candidate coordinate.

Return type

Candidate object

coord

edge_osmid

great_dist

node_id

obs

pytrack.matching.candidate.elab_candidate_results(results, predecessor)[source]

Elaborate results of candidate.get_candidates method. It selects which candidate best matches the actual GPS points.

Parameters

results (dict) – Output of candidate.get_candidates method.
predecessor (dict) – Output of mpmatching.viterbi_search method.

Returns

results – Elaborated results.

Return type

dict

pytrack.matching.candidate.get_candidates(G, points, interp_dist=1, closest=True, radius=10)[source]

Extract candidate points for Hidden-Markov Model map-matching approach.

Parameters

G (networkx.MultiDiGraph) – Street network graph.
points (list) – The actual GPS points.
interp_dist (float, optional, default: 1) – Step to interpolate the graph. The smaller the interp_dist, the greater the precision and the longer the computational time.
closest (bool, optional, default: True) – If true, only the closest point is considered for each edge.
radius (float, optional, default: 10) – Radius of the search circle.

Returns

G (networkx.MultiDiGraph) – Street network graph.
results (dict) – Results to be used for the map-matching algorithm.

cleaning

pytrack.matching.cleaning.park_filter(traj, th_dist=50, th_time=30)[source]

It removes parking behaviour by eliminating those points that remain in a certain area for a given amount of time.

Parameters

traj (pandas.DataFrame) – Dataframe containing 3 columns [timestamp, latitude, longitude].
th_dist (float, optional, default: 50 meters.) – Threshold for the distance of adjacent points.
th_time (float, optional, default: 30 min.) – Threshold for the delta time.

Returns

df – Filtered version of the input dataframe.

Return type

pandas.DataFrame

pytrack.matching.cleaning.veldist_filter(traj, th_dist=5, th_vel=3)[source]

It filters the GPS trajectory combining speed and distance between adjacent points. If the adjacent point distance does not exceed the threshold and the speed is less than th_vel (m/s), the current trajectory point is ignored.

Parameters

traj (pandas.DataFrame) – Dataframe containing 3 columns [timestamp, latitude, longitude].
th_dist (float, optional, default: 5 meters.) – Threshold for the distance of adjacent points.
th_vel (float, optional, default: 3 m/s.) – Threshold for the velocity.

Returns

df – Filtered version of the input dataframe.

Return type

pandas.DataFrame

matcher

class pytrack.matching.matcher.Matcher(G)[source]

Bases: object

Skeleton parent class to perform the matching operation.

match(points)[source]

mpmatching

pytrack.matching.mpmatching.viterbi_search(G, trellis, start='start', target='target', beta=3, sigma=4.07)[source]

Function to compute viterbi search and perform Hidden-Markov Model map-matching.

Parameters

G (networkx.MultiDiGraph) – Street network graph.
trellis –
start (str, optional, default: "start") – Starting node.
target (str, optional, default: "target") – Target node.
beta (float) – This describes the difference between route distances and great circle distances. See https://www.ismll.uni-hildesheim.de/lehre/semSpatial-10s/script/6.pdf for a more detailed description of its calculation.
sigma (float) – It is an estimate of the magnitude of the GPS error. See https://www.ismll.uni-hildesheim.de/lehre/semSpatial-10s/script/6.pdf for a more detailed description of its calculation.

Returns

joint_prob (dict) – Joint probability for each node.
predecessor (dict) – Predecessor for each node.

Notes

See https://www.ismll.uni-hildesheim.de/lehre/semSpatial-10s/script/6.pdf for a more detailed description of this method.

mpmatching_utils

pytrack.matching.mpmatching_utils.create_matched_path(G, trellis, predecessor)[source]

Create the path that best matches the actual GPS points. Route created based on results obtained from pmatching_utils.viterbi_search and mpmatching_utils.create_trellis methods.

Parameters

G (networkx.MultiDiGraph) – Street network graph used to create trellis graph.
trellis (networkx.DiGraph) – A directed acyclic Trellis graph.
predecessor (dict) – Predecessor for each node.

Returns

node_ids (list) – List of ids of the nodes that compose the path.
path_coords (list) – List of nodes’ coordinates, in the form of tuple (lat, lon), composing the path.

pytrack.matching.mpmatching_utils.create_path(G, trellis, predecessor)[source]

Create the path that best matches the actual GPS data.

Parameters

G (networkx.MultiDiGraph) – Road network graph.
trellis (networkx.DiGraph) – A directed acyclic graph.
predecessor (dict) – Predecessor for each node.

Returns

path_elab – List of node IDs.

Return type

list

pytrack.matching.mpmatching_utils.create_trellis(results)[source]

Create a Trellis graph.

Parameters: results (dict) – Output of candidate.get_candidates method.
Returns: G – A directed acyclic Trellis graph.
Return type: networkx.DiGraph

pytrack.matching.mpmatching_utils.emission_prob(u, sigma=4.07)[source]

Compute emission probability of a node

Parameters

u (pytrack.matching.Candidate) – Node of the graph.
sigma (float, optional, default: SIGMA_Z) – It is an estimate of the magnitude of the GPS error. See https://www.ismll.uni-hildesheim.de/lehre/semSpatial-10s/script/6.pdf for a more detailed description of its calculation.

Returns

ret – Emission probability of a node.

Return type

float

pytrack.matching.mpmatching_utils.get_predecessor(target, predecessor)[source]

Reconstruct predecessor dictionary of a decoded trellis DAG.

Parameters

target (str) – Target node of the trellis DAG.
predecessor (dict) – Dictionary containing the predecessors of the nodes of a decoded Trellis DAG.

Returns

pred_elab – Dictionary containing the predecessors of the best nodes of a decoded Trellis DAG.

Return type

dict

pytrack.matching.mpmatching_utils.transition_prob(G, u, v, beta=3)[source]

Compute transition probability between node u and v.

Parameters

G (networkx.MultiDiGraph) – Road network graph.
u (dict) – Starting node of the graph.
v (dict) – Target node of the graph.
beta (float) – This describes the difference between route distances and great circle distances. See https://www.ismll.uni-hildesheim.de/lehre/semSpatial-10s/script/6.pdf for a more detailed description of its calculation.

Returns

ret – Transition probability between node u and v.

Return type

float