In this study, a new recursive approach to finding trajectories of feature points in an image sequence is asddressed, in which finding feature point trajectories is formulated as a multistage bipartite matching problem. Within the multistage bipartite graph, each partite represents a set of feature points extracted from an image frame, and each stage (a bipartite graph) represents the correspondence between two sets of feature points extracted from two consecutive image frames. In the proposed approach, a greedy strategy is employed. That is, based on the results (
) obtained in the previous k frames, the correspondence
between two sets of feature points extracted from the current two (kth and (k+1)th) image frames is determined as the maximum weighted matching of the current (kth) bipartite graph, and the feature point trajectories up to the current (k+1)th frame are determined (
) accordingly.
To reduce the time cost of the trajectory finding process, a prediction procedure based on smoothness of motion and a similarity checking procedure based on trajectory coherence are employed, and two proposed greedy algorithms are used to determine the corresponding feature point trajectories for two different application situations, respectively.|
Although the obtained results are just the "approximate" solutions, on the average, determining the correspondence between two consecutive image frames takes O(NlogN) time, and finding the feature point trajectories up to the (k+1)th frame in an image sequence takes only O(k NlogN) time, where N is the number of feature points. Some experimental results show the feasibility of the proposed approach.