US6618490B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for efficiently registering object models in images via dynamic ordering of features
Assignee: Digital Equipment Corp
•
Filing: 1999-12-20
•
Granted: 2003-09-09
•
Expires: 2019-12-20
Abstract
Abstract An object model, having a plurality of features and described by a model state, is registered in an image. Unregistered features of the object model are dynamically selected such that the cost function of each feature search is minimized. A search is performed for a match of the selected model feature to the image, or to features within the image, to register the feature, and the model state is updated accordingly. These steps are repeated until all features have been registered. The search is performed in a region of high probability of a match. The cost function for a feature is based on the feature's basin of attraction, and in particular can be based on the complexity of the search process at each basin of attraction. A search region is based on a projected state probability distribution. In particular, the cost function is based on the "matching ambiguity," or the number of search operations required to find a true match with some specified minimum probability. For feature-to-feature matching, the number of search operations is preferably the number of target features located within each search region. For feature-to-image matching, the matching ambiguity is computed, for each search region, by dividing the region into minimally-overlapping volumes which have the same size and shape as a basin of attraction associated with the feature, and then counting the number of volumes required to cover the regions. The model state is updated according to a propagated state probability distribution. Preferably, the propagation of the probability distribution is based on successive registered features.
Inventors
- 👤 Tat-Jen Cham
- 👤 James Matthew Rehg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 07:57
CPC Classifications
G; G06; G06V; G06V40/00; G06V40/20; G06T; G06T7/00; G06T7/20; G06T7/246; G06T7/251; G06T2207/00; G06T2207/10; G06T2207/10016; G06T2207/30; G06T2207/30196; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
94 words
A method of registering an object model in an image, the object model comprising a plurality of features, the object model described by a model state, comprising: selecting an unused model feature based initially on a prior state probability model, and subsequently on a propagated state probability model; searching for a match of the selected model feature to the image to register the feature; updating the state probability model based on the optimal configuration, the updated state probability model being propagated for a next iteration; and repeating the steps of selecting, searching and updating.
Claim 2
Independent Claim
94 words
A method of registering an object model in an image, the object model comprising a plurality of features, the object model described by a model state, comprising: selecting an unused model feature based initially on a prior state probability model, and subsequently on a propagated state probability model; searching for a match of the selected model feature to the image to register the feature; updating the state probability model based on the optimal configuration, the updated state probability model being propagated for a next iteration; and repeating the steps of selecting, searching and updating.
Claim 3
Dependent Claim
45 words
The method of claim 1 wherein selecting an unused model feature comprises: determining, for each unregistered feature, a number of search operations required to find a match with at least a predetermined probability, wherein a feature requiring a least number of search operations is selected.
Claim 4
Dependent Claim
67 words
The method of claim 2 , wherein, for each unregistered feature, determining a number of search operations comprises: determining search regions within a feature space, each search region having an associated probability density, such that a total probability equal to the sum of the search regions' associated probability densities exceeds a predetermined probability, wherein the number of required search operations is based on the found search regions.
Claim 5
Dependent Claim
41 words
The method of claim 3 , wherein determining search regions comprises: iteratively finding search regions such that each search region's associated probability density exceeds a predetermined threshold, lowering the predetermined threshold each iteration until the total probability exceeds the predetermined probability.
Claim 6
Dependent Claim
33 words
The method of claim 3 , wherein searching comprises: performing feature-to-feature matching, such that the number of required search operations is related to the number of target features located within the search regions.
Claim 7
Dependent Claim
25 words
The method of claim 5 wherein the number of features which lie within the search region is based on Mahalanobis distances to potential target features.
Claim 8
Dependent Claim
42 words
The method of claim 6 wherein, when target features are approximately uniformly distributed, the number of features is proportional to the search region's size, such that selecting a feature comprises ranking the features according to the sizes of their associated search regions.
Claim 9
Dependent Claim
50 words
The method of claim 3 wherein searching comprises: performing feature-to-image matching, such that the number of required search operations is related to a number of minimally-overlapping volumes having a same size and shape as a basin of attraction associated with the feature, the volumes being sufficient to cover the regions.
Claim 10
Dependent Claim
46 words
The method of claim 8 , wherein the number of volumes is approximated with a count responsive to eigenvalues and basin of attraction spans, the eigenvalues associated with a covariance matrix associated with the feature search region, and each span based associated with an eigenvector direction.
Claim 11
Dependent Claim
15 words
The method of claim 1 , wherein the state probability model has a Gaussian distribution.
Claim 12
Dependent Claim
19 words
The method of claim 10 , wherein the state probability model is propagated using a Kalman filter update step.
Claim 13
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 14
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 15
Independent Claim
95 words
A system for registering an object model in an image, the object model comprising a plurality of features, the object model described by a model state, comprising: a selection module which selects an unregistered model feature based initially on a prior state probability model, and subsequently on a propagated state probability model; a search module which searches the image and finds an optimal configuration for the selected model feature; and an update module which updates the state probability model based on the optimal configuration, the updated state probability model being propagated to the selection module.
Claim 16
Independent Claim
95 words
A system for registering an object model in an image, the object model comprising a plurality of features, the object model described by a model state, comprising: a selection module which selects an unregistered model feature based initially on a prior state probability model, and subsequently on a propagated state probability model; a search module which searches the image and finds an optimal configuration for the selected model feature; and an update module which updates the state probability model based on the optimal configuration, the updated state probability model being propagated to the selection module.
Claim 17
Dependent Claim
49 words
The system of claim 14 wherein the selection module comprises: a matching ambiguity calculator which determines, for each unregistered feature, a number of search operations required to find a match with at least a predetermined probability, the selection module selecting a feature requiring a least number of search operations.
Claim 18
Dependent Claim
69 words
The system of claim 15 , wherein, for each unregistered feature, the matching ambiguity calculator determines search regions within a feature space, each search region having an associated probability density, such that a total probability equal to the sum of the search regions' associated probability densities exceeds a predetermined probability, and wherein the matching ambiguity calculator computes the number of required search operations based on the found search regions.
Claim 19
Dependent Claim
45 words
The system of claim 16 , wherein the matching ambiguity calculator determines search regions by iteratively finding search regions such that each search region's associated probability density exceeds a predetermined threshold, lowering the predetermined threshold each iteration until the total probability exceeds the predetermined probability.
Claim 20
Dependent Claim
34 words
The system of claim 16 , wherein the searching module performs feature-to-feature matching, such that the number of required search operations is related to the number of target features located within the search regions.
Claim 21
Dependent Claim
25 words
The system of claim 18 wherein the number of features which lie within the search region is based on Mahalanobis distances to potential target features.
Claim 22
Dependent Claim
41 words
The system of claim 19 wherein, when target features are approximately uniformly distributed, the number of features is proportional to the search region's size, such that the feature selection module ranks the features in order corresponding to their associated search regions.
Claim 23
Dependent Claim
51 words
The system of claim 16 wherein the searching module performs feature-to-image matching, such that the number of required search operations is related to a number of minimally-overlapping volumes having a same size and shape as a basin of attraction associated with the feature, the volumes being sufficient to cover the regions.
Claim 24
Dependent Claim
46 words
The system of claim 21 , wherein the number of volumes is approximated with a count responsive to eigenvalues and basin of attraction spans, the eigenvalues associated with a covariance matrix associated with the feature search region, and each span based associated with an eigenvector direction.
Claim 25
Dependent Claim
15 words
The system of claim 14 , wherein the state probability model has a Gaussian distribution.
Claim 26
Dependent Claim
19 words
The system of claim 23 , wherein the state probability model is propagated using a Kalman filter update step.
Claim 27
Dependent Claim
29 words
The system of claim 14 , wherein only some of the available features, sufficient to achieve a predetermined level of certainty in an estimate of the model, are registered.
Claim 28
Dependent Claim
62 words
The system of claim 14 , 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.
Claim 29
Dependent Claim
106 words
A computer program product for registering an object model in an image, the object model comprising a plurality of features, the object model described by a model state, the computer program product comprising a computer usable medium having computer readable code thereon, including program code which iteratively: selects an unused model feature based initially on a prior state probability model, and subsequently on a propagated state probability model; searches for a match of the selected model feature to the image to register the feature; and updates the state probability model based on the optimal configuration, the updated state probability model being propagated for a next iteration.
Claim 30
Dependent Claim
106 words
A computer program product for registering an object model in an image, the object model comprising a plurality of features, the object model described by a model state, the computer program product comprising a computer usable medium having computer readable code thereon, including program code which iteratively: selects an unused model feature based initially on a prior state probability model, and subsequently on a propagated state probability model; searches for a match of the selected model feature to the image to register the feature; and updates the state probability model based on the optimal configuration, the updated state probability model being propagated for a next iteration.
Claim 31
Dependent Claim
49 words
The computer program product of claim 27 wherein, in selecting an unregistered feature, the program code further: determines, for each unregistered feature, a number of search operations required to find a match with at least a predetermined probability; and selects a feature requiring a least number of search operations.
References Cited (Backward Citations)
US4513286A
Cited
US5012522A
Cited
US5164992A
Cited
USRE36041E
Cited
US5687286A
Cited
US5430445A
Cited
US5825368A
Cited
US6188776B1
Cited
US5847716A
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) | 2006-09-08 | 2007-03-10 | 2007-09-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-09-08 | 2011-03-10 | 2011-09-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-09-08 | 2015-03-10 | 2015-09-09 | $7700.00 | Window Closed / Lapsed |