Computations and Measures of Collective Movement Patterns Based on Trajectory Data

Typically, movement data of a moving entity (e.g., people, animal, or other moving objects) is described as a trajectory: a path made by a moving entity as it travels through space over a period of time. Various advanced tracking technologies such as Global Positioning Systems (GPS) able to gather trajectory data as a series of time-stamped locations where the position of the moving entity was recorded. One of the important tasks in the analysis of trajectory data is to recognize various patterns that may emerge from the movement of entities. These movement patterns are essential since they can reflect the behavior of an individual entity or show the relationship among multiple moving entities. In this thesis, we mostly focus on one particular type of pattern: the collective movement pattern or grouping. This pattern occurs when multiple entities travel together for a sufficiently long period of time. We begin our study on the collective movement with the analysis of various measures for a group of trajectories. For a single trajectory, these measures give a single value for the whole trajectory, for example, the average speed and the global direction. We extend measures for a single trajectory to a group of trajectories and add other measures specific for groups that do not exist for an individual trajectory, such as the density of a group. We show that a few tasks related to trajectory analysis, like the visualization of a large collection of trajectories, may use measures to improve its results. Next, we describe a new definition to model a collective movement. We present examples that in dense environments, we argue that our proposed definition corresponds better to human intuition. We formalize the model and give efficient algorithms to compute the refined groups from a set of trajectories. Finally, we compare four definitions of a collective movement experimentally, including our refined definition of groups. We evaluate the differences between each definition and human-annotated data quantitatively. We also examine the dependency of the grouping definitions on the density of the entities and the sampling rate of the input trajectories. For the qualitative analysis, we developed a novel visualization system that shows the reported groups with a color-coding in video footage. In addition to the collective movement pattern, we also study the polyline simplification problem. In particular, we look into the polyline simplification problem where given an input polyline, compute the output polyline that resembles the input and use the least number of vertices of the input such that the distance between the input and output polyline is at most ε (ε>0). In this thesis, we use two distance measures: the Hausdorff and Fréchet distance. Using these two distance measures, we first compare the two well-known algorithms for polyline simplification problems, the Douglas-Peucker and the Imai-Iri, with the optimum simplification possible. Finally, we consider the computation of the optimal simplification using the Hausdorff and Fréchet distance.