A Constrained Spectral Clustering Method for Lane Identification Using Trajectory Data

Lane identification from trajectory data is useful to build high precision maps and enriches the application in traffic research. A constrained spectral clustering method is proposed to identify the lane information from trajectory data. Contrary to the Gaussian mixture model applied to lateral distances in the literature, the proposed method is applied to the two-dimensional trajectory data. A Kalman filter is used to remove the measurement error and smooth the trajectory data. Then, a fast and reliable method of calculating the mean trajectory by oversampling and averaging is used, and the mean trajectory is simplified by the Douglas-Peucker algorithm. After calculating the projected longitudinal distance and lateral distance with respect to the mean trajectory, the must-link constraints and must-not-link constraints are constructed. Lastly, the constraints are embedded in the spectral clustering framework and the lane information for every position is obtained. The method does not require the commonly used assumption of the same lane width across multiple lanes. It shows good result in a complex road segment where the number of lanes changes and many vehicles changes lane.