Vehicle Tracking Using Motion-based Optimization and Graph Theory
C Lima Azevedo, LNEC, National Laboratory Of Civil Engineering, J Cardoso, LNEC, National Laboratory Of Civil Engineering, M Ben-Akiva, MIT, Massachusetts Institute Of Technology
In this paper we extend the application of the k-shortest paths algorithm for multiple-object tracking to the motion-based optimization.
Vehicle trajectory descriptions are required for the development of driving behaviour models and in the calibration of several traffic simulation applications. In recent years, the progress in sensing technologies and image processing algorithms allowed for easier collection of such detailed traffic datasets [1, 2]. Aerial imagery is the most common process for collecting the base data , and several vehicle detection and tracking algorithms have been deployed for different scenarios . In high density traffic situations, the vehicle tracking task may reach a high level of complexity, as the number of candidate vehicle positions between successive images may be very high. Multiple-object tracking based on constrained flow optimization has been shown to produce very satisfactory results . This method uses individual image features  collected for each candidate vehicle as criteria in the optimization process. When the extraction of such features is defective, either due to poor image quality or to low ground sampling distances, feature-based optimization may produce unreal trajectories, which is a known limitation that has to be addressed while extracting vehicle trajectories’ data.
In this paper we extend the application of the k-shortest paths algorithm for multiple-object tracking to the motion-based optimization. A graph of possible connections between successive candidate positions was built using a first level criteria based on speeds. Dual graphs were built to account for acceleration-based and acceleration variation-based criteria. With this framework both longitudinal and lateral motion-based criteria are contemplated in the optimization process. The k-shortest disjoints paths algorithm proposed by Suurballe  was then used to determine the optimal set of trajectories (paths) on the constructed graph.
The proposed algorithm was successfully applied to a vehicle positions dataset, collected through aerial remote sensing on a typical Portuguese suburban motorway. Vehicle positions were extracted by image processing and the proposed algorithm for the vehicle tracking task tested.
Besides the importance of a new trajectory dataset that will allow for the development of new behavioural models and the validation of existing ones, the motion-based multiple-vehicle tracking algorithm allowed for a fast and effective processing using a very simple optimization formulation.
 Laureshyn, A., (2010), Application of automated video analysis to road user behaviour. Ph.D. thesis, Lund University.
 Lenhart, D., Hinz, S., Leitloff, J., Stilla, U., (2008), Automatic traffic monitoring based on aerial image sequences. Pattern Recognition and Image Analysis 18 (3), 400–405.
 Hoogendoorn, S. P., Zuylen, H. J. V., Schreuder, M., Gorte, B., Vosselman, G., van Zuylen, H. J., (2003), Microscopic traffic data collection by remote sensing. Transportation Research Record (1855), 121–128.
 Angel, A., Hickman, M., Mirchandani, P. and Chandnani, D. (2003). Methods of Analyzing Traffic Imagery Collected From Aerial Platforms. IEEE Transactions on intelligent transportation systems Vol. 4 (2), 99–107.
 Berclaz, J., François, F., Türetken, E. and Fua, P. (2011), Multiple Object Tracking using K-Shortest Paths Optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence. Volume: 33, Issue: 9, Publisher: IEEE, Pages: 1806-1819.
 Saunier, N., Sayed, T., (2006), A feature-based tracking algorithm for vehicles in intersections. The 3rd Canadian Conference on Computer and Robot Vision. IEEE, Quebec, Canada.
 Suurballe, J. W. (1974), Disjoint Paths in a Network. Networks, vol. 4, pp. 125–145.
Association for European Transport