Applying Graph Theory to Automatic Vehicle Tracking by Remote Sensing

The estimation of driving behavior models relies on the access to detailed traffic information such as vehicle trajectories. Recent developments in vision-based technologies have allowed an increased collection of vehicle trajectories around the world, with an emphasis on aerial or high observation point imagery methods. Several computer algorithms have been proposed using images of different traffic scenarios with the specific aim of detecting and tracking road users. Very recently, multiple-object tracking based on constrained flow optimization has been shown to produce very satisfactory results. Generally, this method uses individual image features collected for each candidate vehicle position as main criteria in the optimization process. Although these methods are very effective in controlled scenarios, adverse conditions such as dynamic view points and wider observation areas with low ground sampling distances are known to encumber significantly the vehicle trajectory extraction task. In this paper we present the application of a k-shortest disjoint paths algorithm for multiple-object tracking using a motion-based optimization based on dual graphs. A graph of possible connections between successive candidate positions was built using speed and lane connectivity. Dual graphs were constructed to allow for acceleration and lane-change-based optimization criteria. The k-shortest disjoint paths algorithm was then used to determine the optimal set of trajectories (paths). The proposed algorithm was successfully applied to the vehicle tracking in the A44 suburban motorway, in Portugal. Vehicle positions were detected by image processing and 99.4% of the trajectories were successfully and efficiently extracted using the proposed method.

  • Supplemental Notes:
    • This paper was sponsored by TRB committee ABJ50 Information Systems and Technology.
  • Corporate Authors:

    Transportation Research Board

    500 Fifth Street, NW
    Washington, DC  United States  20001
  • Authors:
    • Azevedo, Carlos Lima
    • Cardoso, João Lourenço
    • Ben-Akiva, Moshe
  • Conference:
  • Date: 2014


  • English

Media Info

  • Media Type: Digital/other
  • Features: Figures; References; Tables;
  • Pagination: 12p
  • Monograph Title: TRB 93rd Annual Meeting Compendium of Papers

Subject/Index Terms

Filing Info

  • Accession Number: 01518188
  • Record Type: Publication
  • Report/Paper Numbers: 14-2584
  • Files: TRIS, TRB, ATRI
  • Created Date: Jan 27 2014 2:53PM