Image analysis – Applications – Target tracking or detecting
Reexamination Certificate
1998-02-06
2001-09-25
Johns, Andrew W. (Department: 2621)
Image analysis
Applications
Target tracking or detecting
Reexamination Certificate
active
06295367
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
A The present invention relates generally to a video tracking system, and more particularly to a tracking system which tracks objects through a scene using video information representative of activity in the scene.
2. Description of the Related Art
Basic video tracking systems are well known in the art. The video tracking systems heretofore known lack certain functional capabilities required for generating accurate and comprehensive tracking information.
Celenk et al. in a 1988 IEEE article entitled “Moving Object Tracking Using Local Windows,” disclose a simple tracking mechanism that employs frame differencing and centroid generation to track objects in a non-cluttered scene. This method is not-likely to be successful because it cannot process information from complex scenes and also cannot handle the movement of objects that split and merge.
Tsai et al. in IEEE articles, published in 1981, entitled “Estimating Three-Dimensional Motion Parameters Of A Rigid Planar Patch, and Uniqueness” and “Estimation Of Three-Dimensional Motion Parameters Of Rigid Objects With Curved Surfaces” disclose that only seven points on a rigid object are needed to uniquely find the motion parameters of the object from two images. The constraints on the seven points are provided, in order to yield a unique solution. While this method provides localized motion information, it is not a robust tracking solution.
Liao in a 1994 article entitled “Tracking Human Movements Using Finite Element Methods” discloses the use of a class of contours called Snakes with Finite Element Methods to extract and model the contour of a person as they walk through an environment. The method, though accurate, is not very efficient, and techniques for automatically initializing the algorithm must still be determined. Although this method might be used as part of a tracking system, it is not sufficiently robust to form a complete solution by itself.
Montera et al. in a 1993 SPIE article entitled “Object Tracking Through Adaptive Correlation” disclose the use of correlation templates to identify the location of objects in a scene, and track the object from frame to frame. The correlation template can adapt to changing image conditions over time. However, the object must maintain a fairly fixed, rigid form in order for correlation techniques to work, and therefore is limited in its application to the general tracking problem.
Burt et. al. in a 1989 article entitled “Object Tracking With A Moving Camera” provide a detailed, informative review of the use of “optical flow” for detection and analysis of motion. This particular technique is slow and computationally expensive. Sethi et al. in a 1987 article entitled “Finding Trajectories Of Feature Points In A Monocular Image Sequence” describe the use of path coherence and smoothness of motion as a cost measure for corresponding feature points on an object across image sequences. The cost measure is optimized on a sequence of frames using a technique called the Greedy Algorithm, which exchanges possible correspondences in order to optimize the cost measure. It is likely to work well in scenes in which feature points are easily extracted and maintained. However, it will not work well in cases of complex objects, object occlusion, object split and merge, and poor segmentation.
Salari et al. in a 1990 article entitled “Feature Point Correspondence In The Presence Of Occlusion” expands upon the previous work of Sethi and Jain by considering objects that are occluded. Specifically, the article discloses a set of phantom points which are constructed to represent the feature points missing due to occlusion. The Greedy Algorithm is updated to handle the phantom points. This method cannot handle complex objects.
There is a need for a sophisticated, yet cost effective, tracking system that can be used in many applications. For example, it has become desirable to acquire information concerning the activity of people, for example, within a scene of a retail establishment, a bank, automatic teller machines, bank teller windows, to name a few, using data gathered from analysis of video information acquired from the scene.
It is desirable to monitor the behavior of consumers in various locations of a retail establishment in order to provide information concerning the sequence of events and decisions that a consumer makes. This information is useful in many situations, such as, to adjust the location and features of services provided in a bank, to change merchandising strategies and display arrangements; etc. Consequently, it is necessary for the system to differentiate between people in the scene and between people and other stationary and moving objects in the scene.
A video tracking system is needed which can track the movement of complex objects, such as people, through a scene which may include complex objects itself. Moreover, a video tracking system which can function on an inexpensive computation platform offers significant advantages over the tracking systems heretofore known.
SUMMARY OF THE INVENTION
Briefly, the present invention is directed to a system and method for tracking movement of objects in a scene from a stream of video frames comprising image information. A first correspondence graph, called an object correspondence graph, is formed comprising a plurality of nodes representing regions in the scene that likely represent objects to be tracked and a plurality of tracks. Each track comprises an ordered sequence of nodes in consecutive video frames that represents a track segment of an object in the scene. A second correspondence graph, called a track correspondence graph, is created, comprising a plurality of nodes, each node corresponding to at least one track in the first correspondence graph. A track comprising an ordered sequence of nodes in the track correspondence graph represents the path of an object through the scene. Tracking information for objects, such as persons, in the scene, is accumulated based on the first correspondence graph and second correspondence graph. The movement of objects, including splits and merges of objects in a scene, is accurately detected and tracked.
The objects and advantages of the present invention will become more readily apparent when reference is made to the following description taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 5280530 (1994-01-01), Trew et al.
patent: 5285273 (1994-02-01), James et al.
patent: 5323470 (1994-06-01), Kara et al.
patent: 5341142 (1994-08-01), Reis et al.
patent: 5434927 (1995-07-01), Brady et al.
patent: 5537118 (1996-07-01), Appriou
patent: 5754694 (1998-05-01), Villalba
patent: 5761326 (1998-06-01), Brady et al.
patent: 5764283 (1998-06-01), Pingali et al.
patent: 5809161 (1998-09-01), Auty et al.
patent: 5870502 (1998-06-01), Bonneau et al.
patent: 5883969 (1999-03-01), Le Gouzouguec et al.
patent: 5923365 (1999-07-01), Tamir et al.
patent: 5947413 (1999-09-01), Mahalanobis
patent: 6035067 (2000-03-01), Ponticos
Cai et al., “Automatic Tracking of Human Motion in Door Scenes Across Multiple Synchronized Video Stream”, IEEE, Jan. 1998, pp. 356-362.
Munno et al., “Automatic Video Image Moving Target Detection for Wide Area Surveillance”, IEEE, 1993, pp. 47-57.
Lane et al., “Robust Tracking of Multiple in Sector-Scan Sonar Image Sequences Using Optical Flow Motion Estimation”, vol. 23, No. 1, Jan. 1998, pp. 31-46.
“Deformable Contours: Modeling, Extraction, Detection and Classification” by Kok Fung Lai, 1994.
“Vision Tutor” Version 1.1 Lecture Guide Ch. 5-6, from Amerinex Artificial Intelligence, Inc. 1995, pp, 5-1-6-90.
“Reduction of color space dimensionality by moment-preserving thresholding and its application for edge detection in color images” by Chen-Kuei Yang et al., in Pattern Recognition Letters, 1996, pp. 481-490.
“Automatic Feature Point Extraction and Tracking in Image Sequences for Unknown Camera Motion” by Qinfen Zheng and Rama Chellappa, IEEE Proc. 4th International Conference on Computer Vision, 1993, pp. 335-
Crabtree Ralph N.
Khosravi Mehdi
Moed Michael C.
Azarian Seyed
Emtera Corporation
Johns Andrew W.
Needle & Rosenberg P.C.
LandOfFree
System and method for tracking movement of objects in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for tracking movement of objects in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for tracking movement of objects in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2447612