Multiple Object Tracking Using K-Shortest Paths Optimization.

Area of Science:

• Computer Vision
• Artificial Intelligence
• Optimization Algorithms

Background:

• Multi-object tracking involves detecting objects in frames and linking them across sequences.
• Current methods, often using dynamic programming, face optimization challenges in complex scenarios with many targets.
• Occasional detection failures can be tolerated, but false positives and complex linking pose significant problems.

Purpose of the Study:

• To develop a more robust and efficient method for multi-object tracking.
• To address the optimization difficulties in linking object detections across frames for multiple targets.
• To present a novel formulation of the trajectory linking step as a convex optimization problem.

Main Methods:

• Reformulating the trajectory linking problem as a constrained flow optimization.
• Utilizing the k-shortest paths algorithm to solve the resulting convex problem efficiently.
• Comparing the new approach against existing sampling or greedy search methods.

Main Results:

• The proposed method transforms a difficult optimization problem into a convex one.
• The k-shortest paths algorithm provides a fast and effective solution.
• Demonstrated excellent performance in two distinct application contexts.

Conclusions:

• The new formulation offers a simpler and algorithmically superior approach to multi-object tracking.
• This method enhances robustness against detection failures and false positives.
• The approach shows significant potential for various real-world tracking applications.