# Three Rapid Methods for Averaging GPS Segments
## 1 Introduction  
We study the problem of finding a good representative of a set of GPS trajectories. Solutions are needed in several applications such as extracting road network, trajectory clustering, and calculating average routes for taxi trips, see Figure 1. The input is an ordered sequence of geographical points (latitude, longitude), and the output is a polygon that approximates the path traveled.  
The problem is closely related to averaging time series, which has been studied actively in recent years in the context of dynamic time warping (DTW) distance. The common problem is that the observations may have been collected with different frequency, and the number of samples varies  
Figure 1: Averaging a set of global positioning system (GPS) trajectories is needed in road network extraction (above) and clustering of GPS trajectories (below).  
across the sequences. The major issue is how to align the sequences before averaging. Earlier studies have considered the problem as multiple sequence alignment (MSA), which is equivalent to the Steiner sequence [1]. However, it was recently shown that the multiple alignment approach does not guarantee optimality [2].  
It is possible to solve the averaging problem by using \"Mean\", which is defined as any sequence that minimizes the sum of squared distances to all the input sequences:  
\[arg_{C}min\sum_{i=1}^{k}D(x_{i},\ C) \tag{1}\]  
where \(X=\{x_{1},\ x_{2},\ \ldots,\ x_{k}\}\) is the set of input sequences and \(C\) is the mean. This definition defines averaging as an optimization problem. However, the search space is huge, and exhaustive search by enumeration is not feasible. An exponential time algorithm for solving the exact DTW-mean was recently given in [2], but the problem was shown to be NP-hard concerning the number of sequences [3].  
The GPS trajectories differ from time series in a few ways. First, the alignment of the time series is performed in the time domain, whereas the GPS points need to be aligned in geographical space. Second, GPS data can be noisy. This means that the mean might not even be the best solution to the problem.  
The averaging problem of GPS trajectories has been recently studied in a Segment averaging challenge ([[http://cs.uet.fi/sipu/segments/](http://cs.uet.fi/sipu/segments/)]([http://cs.uet.fi/sipu/segments/](http://cs.uet.fi/sipu/segments/))), with several new solutions proposed [4]. Most methods in the competition apply the four-step procedure shown in Figure 2. Some trajectories can be stored in reverse order, and reordering of the sequences is needed. Outlier removal is commonly applied to reduce the effect of the noisy trajectories. After these steps, the problem reduces to normal sequence averaging. Postprocessing by polygonal approximation is sometimes also done to simplify the final representation.  
Although several reasonable solutions have been proposed, several of them are rather complicated, and some also suffer from high time complexity. In this paper, we present three rapid and simple methods based on analyzing three descriptors of the curves: start (S), middle (M), and destination (D), see Figure 3. If the trajectory resembles a line, a simple linear model with 3 points is produced; except when no intermediate points exist. Otherwise, a more complex curvy model is applied as a backup. Three methods are considered for this: Median, Medoid, and Divide-and-Conquer.  
Figure 3: Sketch of the proposed solution: trajectories are analyzed based on three descriptors: start (S), middle (M), and destination (D). The input trajectories are colored by gray and the predicted average segment as blue.  
Figure 2: Generic diagram of most existing methods for segment averaging.  
The rest of the paper is organized as follows. Existing methods are reviewed in Section 2. The three proposed methods are introduced in Section 3. Experiments are performed in Section 4, and conclusions are drawn in Section 5.