A numerical approach for tracking unknown number of individual targets in videos

• Brute-force search with O(n!)O(n!) can be used to get a comprehensive match of a target.
• Due to combinatorial explosion effect the usage of brute-force search is impractical.
• But we do not need to search a target all of its possible regions in the next frame.
• We can search it only some automatically generated regions, named candidate regions.
• With candidate regions full trajectories of targets can be obtained in O(n3)O(n3).

Suppose that we wish to get a comprehensive match of a target in the next frame. Where would we search the target in the next frame? Brute-force search has an asymptotic runtime of O(n!)O(n!) with problem size n  . Yet we can search the target only from a number of automatically generated specific regions, named candidate regions, in the next frame. But how can we get those regions? Deeming the silhouettes of movers, this paper denotes a detailed deliberation of how to generate those candidate regions automatically and then how to track unknown number of individual targets with them. Phase-correlation technique aids to find the key befitting matches of the targets using them. Hungarian method in combination with a state estimation process called Kalman filter finds the best correspondence of the targets among those matches, allowing us to construct full trajectories of unknown number of individual targets in 3D space irresistibly swift as compared to brute-force search since the relative runtime reduced from O(n!)O(n!) to O(n3)O(n3). Favorable outcomes, upon conducting experiments on videos from three different datasets, show the robustness and effectiveness of our approach.

Figure optionsDownload as PowerPoint slide