Patent US6795567B1 successfully refreshed from Google Patents.
US6795567B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for efficiently tracking object models in video sequences via dynamic ordering of features
Assignee: Hewlett Packard Development Co LP
•
Filing: 2000-05-05
•
Granted: 2004-09-21
•
Expires: 2020-05-05
Abstract
Abstract An object model has a plurality of features and is described by a model state. An unregistered feature of the object model, and an available frame from a sequence of images are selected to minimize a cost function of a subsequent search for a match of the selected model feature to the image in the selected frame. Upon a match, the feature is registered in that frame. The model state is then updated for each available frame. The steps of selecting, searching and updating are repeated. A video storage module may contain only one frame corresponding to a single time instance, in which case the framework used is based on integrated sequential feature selection. Alternatively, the video store may contain the entire video sequence, in which case feature selection is performed across all video frames for maximum tracking efficiency. Finally, the video store may contain a small number of previous frames plus the current frame, in which case feature selection spans only a subset of the entire video sequence for each feature matching cycle.
Inventors
- 👤 Tat-Jen Cham
- 👤 James Matthew Rehg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 19:45
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/20; G06T7/246; G06T7/251; G06T2207/00; G06T2207/10; G06T2207/10016; G06T2207/30; G06T2207/30196
Claims Analysis
Total Claims: 90
Claim 1
Independent Claim
208 words
A method for tracking an object model in a sequence of frames, the object model comprising a plurality of features, the object model described by a model state, the method comprising: for each unregistered model feature, determining a number of search operations required to find a match with at least a predetermined probability by: (i) finding search regions within a feature space, in which each region has an associated probability density that exceeds a predetermined threshold; (ii) summing the probabilities associated with each of the found search regions to form a total probability; (iii) while the total probability is less than a predetermined probability, lowering the threshold, and repeating the steps of finding search regions and summing the probabilities; and (iv) computing the number of required search operations based on the determined search regions; selecting a feature requiring a least number of search operations such that an unregistered model feature of the object model and an available frame from the sequence of frames are selected; searching for a match of the selected model feature to the selected frame's image to register the feature; updating the model state for each available frame based on the match found in the searching step; repeating the steps of selecting, searching and updating.
Claim 2
Independent Claim
208 words
A method for tracking an object model in a sequence of frames, the object model comprising a plurality of features, the object model described by a model state, the method comprising: for each unregistered model feature, determining a number of search operations required to find a match with at least a predetermined probability by: (i) finding search regions within a feature space, in which each region has an associated probability density that exceeds a predetermined threshold; (ii) summing the probabilities associated with each of the found search regions to form a total probability; (iii) while the total probability is less than a predetermined probability, lowering the threshold, and repeating the steps of finding search regions and summing the probabilities; and (iv) computing the number of required search operations based on the determined search regions; selecting a feature requiring a least number of search operations such that an unregistered model feature of the object model and an available frame from the sequence of frames are selected; searching for a match of the selected model feature to the selected frame's image to register the feature; updating the model state for each available frame based on the match found in the searching step; repeating the steps of selecting, searching and updating.
Claim 3
Dependent Claim
103 words
The method of claim 1 , wherein, at any given time, only one frame is available, frames being available in sequential order, the method further comprising: iteratively registering features of the object model in an available frame, each iteration comprising said steps of selecting, searching, updating with respect to the available frame; terminating the step of iteratively registering features; acquiring a next frame; predicting a state prior for the next frame, using a most recent state update; and repeating the steps of iteratively registering, terminating, acquiring and predicting, upon each repetition registering features responsive to the state prior predicted by the previous repetition.
Claim 4
Dependent Claim
60 words
The method of claim 2 , wherein the step of iteratively registering features comprises: selecting an unregistered feature of the object model to minimize a cost function of a subsequent search; searching for a match of the selected model feature to the image to register the feature; updating the model state; and repeating the steps of selecting, searching and updating.
Claim 5
Dependent Claim
60 words
The method of claim 2 , further comprising: maintaining a list of model features to be matched, each listed model feature associated with an indicator which provides an indication as to whether the respective model feature is available for matching; marking a feature as unavailable when it is matched; and marking all features as available upon acquiring a new frame.
Claim 6
Dependent Claim
24 words
The method of claim 2 , wherein determining when to advance to a next frame is based on a number of unmatched model features.
Claim 7
Dependent Claim
31 words
The method of claim 2 , wherein determining when to advance to a next frame is based on an amount of time elapsed while iteratively registering features for a current frame.
Claim 8
Dependent Claim
19 words
The method of claim 1 , further comprising: maintaining a list of <feature, frame> pairs which have been matched.
Claim 9
Dependent Claim
16 words
The method of claim 1 , wherein all frames of the sequence of frames are available.
Claim 10
Dependent Claim
28 words
The method of claim 1 , further comprising: for each available frame in the sequence, extracting features from the frame, wherein searching for a match comprises feature-to-feature matching.
Claim 11
Dependent Claim
14 words
The method of claim 1 , wherein searching for a match comprises feature-to-image matching.
Claim 12
Dependent Claim
27 words
The method of claim 10 , further comprising: for each available frame in the sequence, preprocessing the frame, and restricting the number of image regions to search.
Claim 13
Dependent Claim
33 words
The method of claim 11 , wherein preprocessing comprises: identifying regions of at least one predetermined color, such that restricting the number of image regions to search comprises searching only the identified regions.
Claim 14
Dependent Claim
17 words
The method of claim 12 , wherein the at least one predetermined color is a skin color.
Claim 15
Dependent Claim
30 words
The method of claim 11 , wherein preprocessing comprises: examining local spatial-frequency content of the frame's image; and identifying regions in which to search based on the local spatial-frequency content.
Claim 16
Dependent Claim
14 words
The method of claim 1 , wherein all of the steps are performed off-line.
Claim 17
Dependent Claim
25 words
The method of claim 1 , further comprising: defining a search window which specifies a range of frames from which a feature can be selected.
Claim 18
Dependent Claim
13 words
The method of claim 16 wherein the search window includes all available frames.
Claim 19
Dependent Claim
18 words
The method of claim 16 wherein the search window comprises five frames including a most recently acquired frame.
Claim 20
Dependent Claim
16 words
The method of claim 1 wherein the selected model feature is associated with a lowest cost.
Claim 21
Dependent Claim
21 words
The method of claim 1 wherein the selected model feature is associated with a cost which is less than a threshold.
Claim 22
Dependent Claim
52 words
The method of claim 20 , wherein selecting comprises: for each unregistered feature of each available frame, determining a cost 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 selecting the feature.
Claim 23
Dependent Claim
32 words
The method of claim 21 , wherein if no feature is found which has an associated cost less than the threshold, selecting further comprises: selecting a feature with the lowest determined cost.
Claim 24
Dependent Claim
56 words
The method of claim 20 , wherein selecting further comprises: maintaining a list of features; assigning a minimum cost to a feature which has an associated cost less than the predetermined threshold; and ordering the list according to determined cost, such that a feature with lowest determined cost is listed at the top of the list.
Claim 25
Dependent Claim
32 words
The method of claim 23 , further comprising: after searching for a match of the selected feature and updating the model, recalculating the cost only of features affected by the state update.
Claim 26
Dependent Claim
13 words
The method of claim 20 , wherein the threshold is a predetermined threshold.
Claim 27
Dependent Claim
13 words
The method of claim 20 , wherein the threshold is an adaptive threshold.
Claim 28
Dependent Claim
25 words
The method of claim 1 , further comprising: defining an update window which specifies a range of frames for which the model state is updated.
Claim 29
Dependent Claim
22 words
The method of claim 27 , wherein the update window is centered around a frame in which the most recent matching occurred.
Claim 30
Dependent Claim
21 words
The method of claim 27 , wherein the update window spans between 2 and 7 multiples of a dominant time constant.
Claim 31
Dependent Claim
20 words
The method of claim 1 , wherein all of the steps are performed on-line, the frames provided by a source.
Claim 32
Dependent Claim
13 words
The method of claim 30 , wherein the source is a video source.
Claim 33
Dependent Claim
13 words
The method of claim 31 wherein the video source is a video camera.
Claim 34
Dependent Claim
20 words
The method of claim 31 , further comprising: providing a signal to the video source to acquire a next frame.
Claim 35
Dependent Claim
18 words
The method of claim 31 , further comprising: providing frames from the video source at a fixed rate.
Claim 36
Dependent Claim
14 words
The method of claim 34 wherein the fixed rate is 30 frames per second.
Claim 37
Dependent Claim
58 words
The method of claim 30 , further comprising: upon the acquisition of a new frame from the source, determining whether to use the new frame; and if it has been determined to use the new frame, adding a new state vector to a state sequence; and initializing the new state vector based on a previous set of measurements.
Claim 38
Dependent Claim
15 words
The method of claim 1 , wherein the sequence of frames comprises a video sequence.
Claim 39
Dependent Claim
14 words
The method of claim 37 , wherein features are attributes of an object appearance.
Claim 40
Dependent Claim
21 words
The method of claim 1 , wherein the sequence of frames comprises an audio sequence and the image is audio image.
Claim 41
Dependent Claim
14 words
The method of claim 39 , wherein features are elements of a speech signal.
Claim 42
Dependent Claim
17 words
The method of claim 1 , wherein the sequence of frames comprises a sequence of genetic data.
Claim 43
Dependent Claim
11 words
The method of claim 41 , wherein features are biological markers.
Claim 44
Dependent Claim
18 words
The method of claim 1 , wherein the cost function is based on the feature's basin of attraction.
Claim 45
Dependent Claim
22 words
The method of claim 43 , wherein the cost function is further based on complexity of searching at each basin of attraction.
Claim 46
Dependent Claim
19 words
The method of claim 1 , wherein searching is performed in a region of high probability of a match.
Claim 47
Dependent Claim
17 words
The method of claim 45 wherein a search region is based on a projected state probability distribution.
Claim 48
Dependent Claim
15 words
The method of claim 1 , wherein searching is based on maximizing a comparison function.
Claim 49
Dependent Claim
17 words
The method of claim 1 wherein selecting and searching are responsive to a propagated state probability distribution.
Claim 50
Dependent Claim
15 words
The method of claim 48 wherein the state probability distribution is projected into feature space.
Claim 51
Dependent Claim
11 words
The method of claim 1 , wherein searching comprises feature-to-feature matching.
Claim 52
Dependent Claim
23 words
The method of claim 50 , wherein the number of search operations is the number of target features located within each search region.
Claim 53
Dependent Claim
25 words
The method of claim 51 wherein the number of target features located within the search region is based on Mahalanobis distances to potential target features.
Claim 54
Dependent Claim
40 words
The method of claim 50 wherein target features are approximately uniformly distributed, and the number of features is proportional to the search region's size, the method further comprising: ranking the features according to the sizes of the associated search regions.
Claim 55
Dependent Claim
10 words
The method of claim 1 wherein searching comprises feature-to-image matching.
Claim 56
Dependent Claim
48 words
The method of claim 54 wherein computing the number of required search operations comprises, for each search region, dividing the region into minimally-overlapping volumes having a same size and shape as a basin of attraction associated with the feature; and counting such volumes required to cover the regions.
Claim 57
Dependent Claim
47 words
The method of claim 55 , wherein counting volumes is approximated by: obtaining eigenvalues and eigenvectors to a covariance matrix associated with the feature search region; calculating a basin of attraction span for each eigenvector direction; and approximating a count responsive to the eigenvalues and the spans.
Claim 58
Dependent Claim
18 words
The method of claim 1 , wherein model states are updated according to a propagated state probability distribution.
Claim 59
Dependent Claim
19 words
The method of claim 57 , wherein the propagation of the probability distribution is based on successive registered features.
Claim 60
Dependent Claim
15 words
The method of claim 1 , wherein the state probability model has a Gaussian distribution.
Claim 61
Dependent Claim
19 words
The method of claim 59 , wherein the state probability model is propagated using a Kalman filter update step.
Claim 62
Dependent Claim
37 words
The method of claim 1 , wherein the step of repeating continues only until a predetermined level of certainty in an estimate of the model is achieved, such that some of the available features are not registered.
Claim 63
Dependent Claim
56 words
The method of claim 1 , further comprising: providing a training set of registration tasks; for each registration task, determining an optimal feature ordering by performing the steps of selecting, searching, updating and repeating; responsive to the optimal feature orderings, determining a fixed ordering; and registering the object model in the image using the fixed ordering.
Claim 64
Independent Claim
194 words
A system for tracking an object model in a sequence of frames, the object model comprising a plurality of features, the object model described by a model state, comprising: a feature selection module which, (a) for each unregistered model feature, iteratively finds search regions within a feature space such that each region's associated probability density exceeds a predetermined threshold, sums the probabilities associated with each of the found search regions to form a total probability, and if the total probability is less than a predetermined probability then lowering the threshold and performing another iteration, computes a number of required search operations based on the found search regions, and (b) selects an unregistered model feature requiring a least number of search operations such that the feature selection module selects an unregistered model feature of the object model and an available frame from the sequence to minimize a cost function of a subsequent search; a search module which searches for a match of the selected model feature to the image to register the feature; and an update module which updates the model state for each available frame based on the match found by the search module.
Claim 65
Independent Claim
194 words
A system for tracking an object model in a sequence of frames, the object model comprising a plurality of features, the object model described by a model state, comprising: a feature selection module which, (a) for each unregistered model feature, iteratively finds search regions within a feature space such that each region's associated probability density exceeds a predetermined threshold, sums the probabilities associated with each of the found search regions to form a total probability, and if the total probability is less than a predetermined probability then lowering the threshold and performing another iteration, computes a number of required search operations based on the found search regions, and (b) selects an unregistered model feature requiring a least number of search operations such that the feature selection module selects an unregistered model feature of the object model and an available frame from the sequence to minimize a cost function of a subsequent search; a search module which searches for a match of the selected model feature to the image to register the feature; and an update module which updates the model state for each available frame based on the match found by the search module.
Claim 66
Dependent Claim
58 words
The system of claim 63 , wherein, at any given time, only one frame is available, frames being available in sequential order, the system further comprising: an acquisition module for acquiring sequence frames; and a process control module which signals the feature selection module to terminate, and which signals the acquisition module to make available a next frame.
Claim 67
Dependent Claim
54 words
The system of claim 64 , further comprising: a feature list comprising a plurality of entries, an entry for each model feature, wherein all features are initially marked as unmatched, and wherein a feature is marked as matched when it is matched, such that the selection feature module selects only features marked as unmatched.
Claim 68
Dependent Claim
29 words
The system of claim 63 , further comprising: a feature extraction module which extracts features from each available frame in the sequence, wherein the search module performs feature-to-feature matching.
Claim 69
Dependent Claim
25 words
The system of claim 63 , further comprising: a frame preprocessor which identifies regions of available frames which are not searched by the search module.
Claim 70
Dependent Claim
13 words
The system of claim 67 , wherein the search module performs feature-to-image matching.
Claim 71
Dependent Claim
18 words
The system of claim 63 , wherein the cost function is based on the feature's basin of attraction.
Claim 72
Dependent Claim
22 words
The system of claim 69 , wherein the cost function is further based on complexity of searching at each basin of attraction.
Claim 73
Dependent Claim
20 words
The system of claim 63 , wherein the search module searches in a region of high probability of a match.
Claim 74
Dependent Claim
17 words
The system of claim 71 wherein a search region is based on a projected state probability distribution.
Claim 75
Dependent Claim
17 words
The system of claim 63 , wherein the search module searches based on maximizing a comparison function.
Claim 76
Dependent Claim
21 words
The system of claim 63 , wherein the selection module and search module are responsive to a propagated state probability distribution.
Claim 77
Dependent Claim
15 words
The system of claim 74 wherein the state probability distribution is projected into feature space.
Claim 78
Dependent Claim
13 words
The system of claim 63 , wherein the search module performs feature-to-feature matching.
Claim 79
Dependent Claim
23 words
The system of claim 76 , wherein the number of search operations is the number of target features located within each search region.
Claim 80
Dependent Claim
25 words
The system of claim 77 wherein the number of target features located within the search region is based on Mahalanobis distances to potential target features.
Claim 81
Dependent Claim
41 words
The system of claim 76 wherein target features are approximately uniformly distributed, and the number of features is proportional to the search region's size, and wherein the search module ranks the features according to the sizes of the associated search regions.
Claim 82
Dependent Claim
12 words
The system of claim 63 wherein the search module performs feature-to-image matching.
Claim 83
Dependent Claim
51 words
The system of claim 80 wherein the selection module, to compute the number of required search operations, for each search region, divides the region into minimally-overlapping volumes having a same size and shape as a basin of attraction associated with the feature, and counts such volumes required to cover the regions.
Claim 84
Dependent Claim
56 words
The system of claim 81 , wherein the selection module uses an approximation to a volume count, the approximation derived by obtaining eigenvalues and eigenvectors to a covariance matrix associated with the feature search region, calculating a basin of attraction span for each eigenvector direction, and approximating a count responsive to the eigenvalues and the spans.
Claim 85
Dependent Claim
21 words
The system of claim 63 , wherein the update module updates the model state according to a propagated state probability distribution.
Claim 86
Dependent Claim
19 words
The system of claim 83 , wherein the propagation of the probability distribution is based on successive registered features.
Claim 87
Dependent Claim
15 words
The system of claim 63 , wherein the state probability model has a Gaussian distribution.
Claim 88
Dependent Claim
19 words
The system of claim 85 , wherein the state probability model is propagated using a Kalman filter update step.
Claim 89
Dependent Claim
29 words
The system of claim 63 , wherein only some of the available features, sufficient to achieve a predetermined level of certainty in an estimate of the model, are registered.
Claim 90
Dependent Claim
62 words
The system of claim 63 , wherein for each registration task in a training set of registration tasks, an optimal feature ordering is determined by the selection module, the search module and the update module, and wherein a fixed ordering is determined responsive to the optimal feature orderings, such that the object model is registered in the image using the fixed ordering.
References Cited (Backward Citations)
US4513286A
Cited
USRE36041E
Cited
US5687286A
Cited
US5430445A
Cited
US5995639A
Cited
US6188776B1
Cited
US6377263B1
Cited
US6269172B1
Cited
US6353679B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-09-21 | 2008-03-22 | 2008-09-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-09-21 | 2012-03-22 | 2012-09-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-09-21 | 2016-03-22 | 2016-09-21 | $7700.00 | Window Closed / Lapsed |