Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.10 No.4, pp.471-494 (December 1994)
Finding Trajectories of Feature Points in an Image
Sequence Via Multistage Bipartite Matching*

Shou-Hsin Lee and Jin-Jang Leou#
Technology Research Division
Institute for Information Industry
Taipei, Taiwan, Republic of China
#Institute of Computer Science and Information Engineering
National Chung Cheng University
Chiayi, Taiwan 621, Republic of China

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 (JISE) obtained in the previous k frames, the correspondence JISE 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 (JISE) 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.

Keywords: feature point correspondence, multistage weighted bipartite graph, image sequence, smoothness of motion, trajectory coherence

Received October 30, 1993; revised June 24, 1994.
Communicated by Soo-Chang Pe.
*This work was supported partially by National Science Council, Republic of China under Grant NSC-81-0422-E194-01.