Model-based segmentation and classification of trajectories

Sander P.A. Alewijnse, Kevin Buchin, Maike Buchin, Stef Sijben, Michel A. Westenberg

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
19 Downloads (Pure)

Abstract

We present efficient algorithms for segmenting and classifying trajectories based on a movement model parameterised by a single parameter, like the Brownian bridge movement model. Segmentation is the problem of subdividing a trajectory into interior-disjoint parts such that each part is homogeneous in its movement characteristics. We formalise this using the likelihood of the model parameter, and propose a new algorithm for trajectory segmentation based on this. We consider the case where a discrete set of m parameter values is given and present an algorithm to compute an optimal segmentation with respect to an information criterion in O(nm) time for a trajectory with n sampling points. We also present an algorithm that efficiently computes the optimal segmentation if we allow the parameter values to be drawn from a continuous domain. Classification is the problem of assigning trajectories to classes of similar movement characteristics. The set of trajectories might for instance be the subtrajectories resulting from segmenting a trajectory, thus identifying movement phases. We give an algorithm to compute the optimal classification with respect to an information criterion in O(m2+ kmlog m) time for m parameter values and k trajectories, assuming bitonic likelihood functions. We also show that classification is NP-hard if the parameter values are allowed to vary continuously and present an algorithm that solves the problem in polynomial time under mild assumptions on the input.

Original languageEnglish
Pages (from-to)2422-2452
Number of pages31
JournalAlgorithmica
Volume80
Issue number8
DOIs
Publication statusPublished - 1 Aug 2018

    Fingerprint

Keywords

  • Classification
  • Movement model
  • Segmentation
  • Trajectory analysis

Cite this