# Estimating Road Segments Using Kernelized Averaging of GPS Trajectories
## 1 Introduction  
During the last decade, the development of navigational and geolocation systems and applications has experienced strong growth. For the associated services, such as human behavior analysis, traffic modelization and prediction, smart city information services, geo-localized and contextualized recommendation, etc., to be exploitable in urban areas, it is necessary to rely on an up-to-date cartography. However, maintenance of road and pedestrian network maps requires costly manual editing in time and money. This need has spawned a specific research theme around the development of automated extraction algorithms of road network maps from GPS trajectories [1; 2; 3]. Global Position Systems (GPS) trajectories are easily and cheaply collected using consumer embedded equipment, such as smart-phones. Unfortunately, they are in general noisy, mainly due to the sensitivity of the GPS tracking system that is used, but also due to the fluctuation, or loss, of the signal from the satellites. Consequently, in many places, such as in cities or mountain environments, due to reflections, magnetic interferences or even tropospheric conditions or sun activities, GPS trajectories can be erroneous (more than 10 m deviations) or characterized with missing data, making them unsuited for applications without dedicated preprocessing. When a single trajectory is at hand, Kalman filtering [4] is usually the classical approach used to clean up this kind of sequential data. When, instead of a single trajectory, a set of trajectories can be considered, such as the random realization of a similar path followed by a population of pedestrians or road vehicles, one can consider ensemble filtering approaches such as ensemble Kalman filtering [5] or variant of particle filtering allowing to cope with historical data [6]. Both Kalman and ensemble Kalman methods require jointly the estimation of a measurement model and a dynamical model. However, the inference of these models are difficult to estimate with accuracy, specifically when the noise is non-Gaussian, and, furthermore, the parameters of the models may change with time and space, from one segment to the other. In this article, we address the problem of cleaning sets of pedestrian or vehicle GPS trajectories corresponding to a road segment without making any assumption on the noise or the nonlineardynamics underlying the movement of the tracked object. The cleaning procedure that we present relies on an ensemble filtering algorithm for sets of trajectories mostly based on the notion of centroid defined for a subset of time series. It involves five steps, as depicted in Figure 1:  
1. an over-sampling of the trajectories such that they all share a higher sampling rate, namely they are described with the same higher number of samples (Section 3.1);
2. a first extraction/estimation of a medoid/centroid for a subset of GPS trajectories (Sections 2.4 and 3.2);
3. anomaly (outlier) detection and removal (Section 3.2);
4. a second extraction/estimation of a medoid/centroid for a subset of GPS trajectories (Sections 2.4 and 3.2); and
5. a final down-sampling to reduce the sampling precision of the trajectories down to the average sampling precision of the initial set of trajectories (Section 3.3). This overall cleaning procedure was used during our experimentation to test comparatively various methods from the state of the art. We evaluated: (i) four medoid methods based on the  
Figure 1: Processing pipeline overview: The meta parameters \(\
u\) (iTEKA averaging method) and \(\gamma\) (soft-DTW averaging method) are defined, respectively, in Equations (5) and (8). The \(T\) meta parameter is the length of the trajectories when they have been over-resampled during the pre-processing step and is defined in Section 3.1. The \(\tau\) parameter is a threshold involved to decide whether a trajectory is an outlier and is defined in Section 3.2.