A non-iterative greedy algorithm for multi-frame point correspondence

We present a framework for finding point correspondences in monocular image sequences over multiple frames. The general problem of multiframe point correspondence is NP hard for three or more frames. A polynomial time algorithm for a restriction of this problem is presented, and is used as the basis of proposed greedy algorithm for the general problem. The greedy nature of the proposed algorithm allows it to be used in real time systems for tracking and surveillance etc. In addition, the proposed algorithm deals with the problems of occlusion, missed detections, and false positives, by using a single noniterative greedy optimization scheme, and hence, reduces the complexity of the overall algorithm as compared to most existing approaches, where multiple heuristics are used for the same purpose. While most greedy algorithms for point tracking do not allow for entry and exit of points from the scene, this is not a limitation for the proposed algorithm. Experiments with real and synthetic data show that the proposed algorithm outperforms the existing techniques and is applicable in more general settings.