Functions

bmm.offline_map_match(graph, polyline, n_samps, timestamps, mm_model=<bmm.ExponentialMapMatchingModel object>, proposal_func=<function optimal_proposal>, d_refine=1, initial_d_truncate=None, max_rejections=20, ess_threshold=1, store_norm_quants=False, store_filter_particles=False, verbose=True, **kwargs)

Runs offline map-matching, i.e. receives a full polyline and returns an equal probability collection of trajectories. Forward-filtering backward-simulation implementation - no fixed-lag approximation needed for offline inference.

Parameters:
  • graph (MultiDiGraph) – encodes road network, simplified and projected to UTM
  • polyline (ndarray) – series of cartesian cooridnates in UTM
  • n_samps (int) – int number of particles
  • timestamps (Union[float, ndarray]) – seconds either float if all times between observations are the same, or a series of timestamps in seconds/UNIX timestamp
  • mm_model (MapMatchingModel) – MapMatchingModel
  • proposal_func (Callable) – function to propagate and weight single particle defaults to optimal (discretised) proposal
  • d_refine (int) – metres, resolution of distance discretisation
  • initial_d_truncate (Optional[float]) – distance beyond which to assume zero likelihood probability at time zero defaults to 5 * mm_model.gps_sd
  • max_rejections (int) – number of rejections to attempt before doing full fixed-lag stitching 0 will do full fixed-lag stitching and track ess_stitch
  • ess_threshold (float) – in [0,1], particle filter resamples if ess < ess_threshold * n_samps
  • store_norm_quants (bool) – if True normalisation quantities (including gradient evals) returned in out_particles
  • store_filter_particles (bool) – if True filter particles returned in out_particles
  • verbose (bool) – bool whether to print ESS at each iterate
  • kwargs – optional parameters to pass to proposal i.e. d_max, d_refine or var as well as ess_threshold for backward simulation update
Returns:

MMParticles object
Return type:

MMParticles
bmm.initiate_particles(graph, first_observation, n_samps, mm_model=<bmm.ExponentialMapMatchingModel object>, d_refine=1, d_truncate=None, ess_all=True, filter_store=True)

Initiate start of a trajectory by sampling points around the first observation. Note that coordinate system of inputs must be the same, typically a UTM projection (not longtitude-latitude!).

Parameters:
  • graph (MultiDiGraph) – encodes road network, simplified and projected to UTM
  • mm_model (MapMatchingModel) – MapMatchingModel
  • first_observation (ndarray) – cartesian coordinate in UTM
  • n_samps (int) – number of samples to generate
  • d_refine (float) – metres, resolution of distance discretisation
  • d_truncate (Optional[float]) – metres, distance beyond which to assume zero likelihood probability defaults to 5 * mm_model.gps_sd
  • ess_all (bool) – if true initiate effective sample size for each particle for each observation otherwise initiate effective sample size only for each observation
  • filter_store (bool) – whether to initiate storage of filter particles and weights
Returns:

MMParticles object
Return type:

MMParticles
bmm.update_particles(graph, particles, new_observation, time_interval, mm_model=<bmm.ExponentialMapMatchingModel object>, proposal_func=<function optimal_proposal>, update='BSi', lag=3, max_rejections=20, **kwargs)

Updates particle approximation in receipt of new observation

Parameters:
  • graph (MultiDiGraph) – encodes road network, simplified and projected to UTM
  • particles (MMParticles) – unweighted particle approximation up to the previous observation time
  • new_observation (ndarray) – cartesian coordinate in UTM
  • time_interval (float) – time between last observation and newly received observation
  • mm_model (MapMatchingModel) – MapMatchingModel
  • proposal_func (Callable) – function to propagate and weight single particle
  • update (str) –
    • ‘PF’ for particle filter fixed-lag update
    • ’BSi’ for backward simulation fixed-lag update

    must be consistent across updates

  • lag (int) – fixed lag for resampling/stitching
  • max_rejections (int) – number of rejections to attempt before doing full fixed-lag stitching 0 will do full fixed-lag stitching and track ess_stitch
  • kwargs – optional parameters to pass to proposal i.e. d_max, d_refine or var as well as ess_threshold for backward simulation update
Returns:

MMParticles object
Return type:

MMParticles
bmm._offline_map_match_fl(graph, polyline, n_samps, timestamps, mm_model=<bmm.ExponentialMapMatchingModel object>, proposal_func=<function optimal_proposal>, update='BSi', lag=3, d_refine=1, initial_d_truncate=None, max_rejections=20, verbose=True, **kwargs)

Runs offline map-matching but uses online fixed-lag techniques. Only recommended for simulation purposes.

Parameters:
  • graph (MultiDiGraph) – encodes road network, simplified and projected to UTM
  • polyline (ndarray) – series of cartesian coordinates in UTM
  • n_samps (int) – int number of particles
  • timestamps (Union[float, ndarray]) – seconds, either float if all times between observations are the same, or a series of timestamps in seconds/UNIX timestamp
  • mm_model (MapMatchingModel) – MapMatchingModel
  • proposal_func (Callable) – function to propagate and weight single particle defaults to optimal (discretised) proposal
  • update (str) –
    • ‘PF’ for particle filter fixed-lag update
    • ’BSi’ for backward simulation fixed-lag update

    must be consistent across updates

  • lag (int) – fixed lag for resampling/stitching
  • d_refine (int) – metres, resolution of distance discretisation
  • initial_d_truncate (Optional[float]) – distance beyond which to assume zero likelihood probability at time zero, defaults to 5 * mm_model.gps_sd
  • max_rejections (int) – number of rejections to attempt before doing full fixed-lag stitching, 0 will do full fixed-lag stitching and track ess_stitch
  • verbose (bool) – bool whether to print ESS at each iterate
  • kwargs – optional parameters to pass to proposal i.e. d_max or var as well as ess_threshold for backward simulation update
Returns:

MMParticles object
Return type:

MMParticles
bmm.sample_route(graph, timestamps, num_obs=None, mm_model=<bmm.ExponentialMapMatchingModel object>, d_refine=1.0, start_position=None, num_inter_cut_off=None)

Runs offline map-matching. I.e. receives a full polyline and returns an equal probability collection of trajectories. Forward-filtering backward-simulation implementation - no fixed-lag approximation needed for offline inference.

Parameters:
  • graph (MultiDiGraph) – encodes road network, simplified and projected to UTM
  • timestamps (Union[float, ndarray]) – seconds either float if all times between observations are the same, or a series of timestamps in seconds/UNIX timestamp
  • num_obs (Optional[int]) – int length of observed polyline to generate
  • mm_model (MapMatchingModel) – MapMatchingModel
  • d_refine (float) – metres, resolution of distance discretisation
  • start_position (Optional[ndarray]) – optional start position; array (u, v, k, alpha)
  • num_inter_cut_off (Optional[int]) – maximum number of intersections to cross in the time interval
Returns:

tuple with sampled route (array with same shape as a single MMParticles) and polyline (array with shape (num_obs, 2))
Return type:

Tuple[ndarray, ndarray]
bmm.random_positions(graph, n=1)

Sample random positions on a graph. :param graph: encodes road network, simplified and projected to UTM :param n: int number of positions to sample, default 1 :return: array of positions (u, v, key, alpha) - shape (n, 4)

Parameters:
  • graph (MultiDiGraph) –
  • n (int) –
Return type:

ndarray
bmm.offline_em(graph, mm_model, timestamps, polylines, save_path, n_ffbsi=100, n_iter=10, gradient_stepsize_scale=0.001, gradient_stepsize_neg_exp=0.5, **kwargs)

Run expectation maximisation to optimise parameters of bmm.MapMatchingModel object. Updates the hyperparameters of mm_model in place.

Parameters:
  • graph (MultiDiGraph) – encodes road network, simplified and projected to UTM
  • mm_model (MapMatchingModel) – MapMatchingModel - of which parameters will be updated
  • timestamps (Union[list, float]) – seconds, either float if all times between observations are the same, or a series of timestamps in seconds/UNIX timestamp, if timestamps given, must be of matching dimensions to polylines
  • polylines (list) – UTM polylines
  • save_path (str) – path to save learned parameters
  • n_ffbsi (int) – number of samples for FFBSi algorithm
  • n_iter (int) – number of EM iterations
  • gradient_stepsize_scale (float) – starting stepsize
  • gradient_stepsize_neg_exp (float) – rate of decay of stepsize, in [0.5, 1]
  • kwargs – additional arguments for FFBSi
Returns:

dict of optimised parameters
bmm.plot(graph, particles=None, polyline=None, label_start_end=True, bgcolor='white', node_color='grey', node_size=0, edge_color='lightgrey', edge_linewidth=3, particles_color='orange', particles_alpha=None, polyline_color='red', polyline_s=100, polyline_linewidth=3, **kwargs)

Plots particle approximation of trajectory

Parameters:
  • graph – NetworkX MultiDiGraph UTM projection encodes road network e.g. generated using OSMnx
  • particles – MMParticles object (from inference.particles) particle approximation
  • polyline – list-like, each element length 2 UTM - metres series of GPS coordinate observations
  • label_start_end – bool whether to label the start and end points of the route
  • bgcolor – str background colour
  • node_color – str node (intersections) colour
  • node_size – float size of nodes (intersections)
  • edge_color – str colour of edges (roads)
  • edge_linewidth – float width of edges (roads
  • particles_color – str colour of routes
  • particles_alpha – float in [0, 1] plotting parameter opacity of routes
  • polyline_color – str colour of polyline crosses
  • polyline_s – str size of polyline crosses
  • polyline_linewidth – str linewidth of polyline crosses
  • kwargs – additional parameters to ox.plot_graph
Returns:

fig, ax
bmm.get_possible_routes(graph, in_route, dist, all_routes=False, num_inter_cut_off=inf)

Given a route so far and maximum distance to travel, calculate and return all possible routes on graph.

Parameters:
  • graph (MultiDiGraph) – encodes road network, simplified and projected to UTM
  • in_route (ndarray) – shape = (_, 9) columns: t, u, v, k, alpha, x, y, n_inter, d t: float, time u: int, edge start node v: int, edge end node k: int, edge key alpha: in [0,1], position along edge x: float, metres, cartesian x coordinate y: float, metres, cartesian y coordinate d: metres, distance travelled
  • dist (float) – metres, maximum possible distance to travel
  • all_routes (bool) – if true return all routes possible <= d otherwise return only routes of length d
  • num_inter_cut_off (int) – maximum number of intersections to cross in the time interval
Returns:

list of arrays each array with shape = (_, 9) as in_route each array describes a possible route
Return type:

list
bmm.cartesianise_path(graph, path, t_column=True, observation_time_only=False)

Converts particle or array of edges and alphas into cartesian (x,y) points.

Parameters:
  • path – numpy.ndarray, shape=(_, 5+) columns - (t), u, v, k, alpha, …
  • t_column – boolean boolean describing if input has a first column for the time variable
Returns:

numpy.ndarray, shape = (_, 2) cartesian points
bmm.get_geometry(graph, edge)

Extract geometry of an edge from global graph object. If geometry doesn’t exist set to straight line.

Parameters:
  • graph (MultiDiGraph) – encodes road network, simplified and projected to UTM
  • edge (ndarray) – length = 3 with elements u, v, k * u: int, edge start node * v: int, edge end node * k: int, edge key
Returns:

edge geometry
Return type:

LineString
bmm.discretise_edge(graph, edge, d_refine)

Discretises edge to given edge refinement parameter. Returns array of proportions along edge, xy cartesian coordinates and distances along edge

Parameters:
  • graph (MultiDiGraph) – encodes road network, simplified and projected to UTM
  • edge (ndarray) – list-like, length = 3 with elements u, v, k * u: int, edge start node * v: int, edge end node * k: int, edge key
  • d_refine (float) – metres, resolution of distance discretisation
Returns:

shape = (_, 4) with columns * alpha: float in (0,1], position along edge * x: float, metres, cartesian x coordinate * y: float, metres, cartesian y coordinate * distance: float, distance from start of edge
Return type:

ndarray
bmm.observation_time_indices(times)

Remove zeros (other than the initial zero) from a series

Parameters:times (ndarray) – series of timestamps
Returns:bool array of timestamps that are either non-zero or the first timestamp
Return type:ndarray
bmm.observation_time_rows(path)

Returns rows of path only at observation times (not intersections)

Parameters:path (ndarray) – numpy.ndarray, shape=(_, 5+) columns - t, u, v, k, alpha, …
Returns:trimmed path numpy.ndarray, shape like path
Return type:ndarray
bmm.long_lat_to_utm(points, graph=None)

Converts a collection of long-lat points to UTM :param points: points to be projected, shape = (N, 2) :param graph: optional graph containing desired crs in graph.graph[‘crs’] :return: array of projected points

Parameters:points (Union[list, ndarray]) –
Return type:ndarray