Image analysis – Applications – Target tracking or detecting
Reexamination Certificate
2000-05-05
2004-09-21
Boudreau, Leo (Department: 2621)
Image analysis
Applications
Target tracking or detecting
Reexamination Certificate
active
06795567
ABSTRACT:
BACKGROUND OF THE INVENTION
There is a large class of applications that depend upon the ability to localize a model of an object in an image, a task known as “registration.” These applications can be roughly categorized into detection, alignment, and tracking problems.
Detection problems involve, for example, finding objects in image databases or finding faces in surveillance video. The model in a detection problem is usually generic, describing a class of objects. For example, in a prior art face detection system, the object model is a neural network template that describes all frontal, upright faces. See Rowley et al., “Neural network-based face detection”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(1), pages 23-38, January 1998. Another example is locating armored vehicles in images for a military targeting system.
An example of an alignment application is mosaicing, in which a single large image is constructed from a series of smaller overlapping images. In this application, each model is simply an image to be added incrementally to the mosaic. The alignment goal is to position each new image so that it is consistent with the current mosaic wherever the two overlap. A description is given in Irani et al., “Mosaic based representations of video sequences and their applications,” Proceedings of Int. Conference on Computer Vision, pages 605-611, Cambridge, Mass., 1995.
Another example is the alignment of plural images obtained from different sensors, e.g. aligning remote-sensed images obtained via normal and infra-red photography, or aligning MRI and SPECT medical images. This allows different regions of an image to be analyzed via multimodal (i.e., vector) measurements instead of scalar pixel intensities. These and other applications are further discussed in the survey on image registration, Brown, “A survey of image registration techniques,” ACM Computing Surveys, 24(4), pages 325-376, 992.
In tracking applications, the models are typically specific descriptions of an image object that is moving through a video sequence. Examples include tracking people for surveillance or user-interface purposes. In figure tracking for surveillance, a stick-figure model of a person evolves over time, matched to the location of a person in a video sequence. A representative prior method is Cham et al., “A multiple hypothesis approach to figure tracking,” Proceedings Computer Vision and Pattern Recognition, pages 239-245, Fort Collins, Colo., 1999. In user-interface applications, the user's gaze direction or head pose may be tracked to determine their focus-of-attention. A prior method is described in Oliver et al., “LAFTER: Lips and face real time tracker,” Proceedings Computer Vision and Pattern Recognition, pages 123-129, San Juan, PR, Jun. 17-19, 1997.
In each of these application areas, there is a desire to handle increasingly sophisticated object models, which is fueled by the increasing demand for sensing technologies. For example, modern user interfaces may be based on tracking the full-body pose of a user to facilitate gesture recognition. As the complexity of the model increases, the computational cost of registration rises dramatically. A naive registration method such as exhaustive search would result in a slow, inefficient system for a complex object like the human figure. However a fast and reliable solution would support advanced applications in content-based image and video editing and retrieval, surveillance, advanced user-interfaces, and military targeting systems.
Therefore, there is a need for a registration method which is computationally efficient in the presence of complex object models.
SUMMARY OF THE INVENTION
The invention describes a method for efficiently tracking object models in a video or other image sequence.
Accordingly, tracking an object model in a sequence of frames where the object model comprises a plurality of features and is described by a model state, includes both selecting an unregistered feature of the object model and selecting an available frame from the sequence of frames, to minimize a cost function of a subsequent search. A search is performed for a match of the selected model feature to the image in the selected frame in order to register the feature in that frame. The model state is then updated for each available frame. The steps of selecting, searching and updating are repeated.
In an embodiment where at any given time only one frame is available, and where frames are available in sequential order, features of the object model are iteratively registered in the available frame. Each iteration includes the steps of selecting, searching, updating with respect to the available frame. This step is terminated , and the next frame is acquired. A state prior is predicted for the next frame, using a most recent state update. Finally, the steps of iteratively registering, terminating, acquiring and predicting, are repeated. Upon each repetition, features are registered responsive to the state prior predicted by the previous repetition.
Iteratively registering features can include selecting an unregistered feature of the object model to minimize a cost function of a subsequent search. A search is performed for a match of the selected model feature to the image to register the feature. The model state is updated. Finally, the steps of selecting, searching and updating are repeated.
A list of model features to be matched is maintained. Each listed model feature is associated with an indicator which provides an indication as to whether the respective model feature is available for matching. A feature is marked as unavailable when it is matched. All features are marked as available upon the acquisition of a new frame.
Determining when to advance to a next frame may be based on, for example, the number of unmatched model features, or the amount of time elapsed while iteratively registering features for a current frame.
In a particular embodiment of the present invention, a list of <feature, frame> pairs which have been matched is maintained.
In at least one embodiment, all frames of the sequence of frames are available.
In one embodiment, for each available frame in the sequence, features are extracted from the frame, and searching for a match employs feature-to-feature matching.
In another embodiment, searching for a match employs feature-to-image matching.
In one feature-to-image matching embodiment, each available frame in the sequence is preprocessed, and the number of image regions to search is restricted. Preprocessing may include identifying regions of at least one predetermined color, for example a skin color, such that restricting the number of image regions to search comprises searching only the identified regions.
Alternatively, preprocessing may include examining the local spatial-frequency content of the frame's image, and identifying regions in which to search based on the local spatial-frequency content.
All steps may be performed off-line.
A search window may be defined which specifies a range of frames from which a feature can be selected. The search window may include all available frames, or it may include a subset, such as five frames, including the most recently acquired frame.
In one embodiment, the feature associated with a lowest cost is selected.
Alternatively, any feature which is associated with a cost which is less than some threshold may be selected. For each unregistered feature of each available frame, a cost is determined of search operations required to find a match with at least a predetermined probability, until a feature is found which has an associated cost less than the threshold, and that feature is selected. If no feature is found which has an associated cost less than the threshold, then a feature with the lowest determined cost may be selected.
To select a feature, a list of features is maintained. A minimum cost, such as −1, is assigned to a feature which has an associated cost less than the predetermined threshold. The list is then ordered according to the determine
Cham Tat-Jen
Rehg James Matthew
Boudreau Leo
Hewlett--Packard Development Company, L.P.
Lu Tom Y.
LandOfFree
Method for efficiently tracking object models in video... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for efficiently tracking object models in video..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for efficiently tracking object models in video... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3208388