Method for efficiently registering object models in images via dynamic ordering of features

• US 6,618,490 B1
• Filed: 12/20/1999
• Issued: 09/09/2003
• Est. Priority Date: 09/16/1999
• Status: Expired due to Fees

• Current Assignee: Compaq Information Technologies Group LP (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Cham, Tat-Jen, Rehg, James Matthew
• Primary Examiner(s): Patel, Jayanti K.
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/466,975
• Time in Patent Office: 1,359 Days
• Field of Search: 382/192, 382/312, 382/100, 382/118, 382/103, 382/228, 382/151, 382/289, 382/291, 382/294, 382/305, 382/107, 382/175, 382/282, 369/30.16, 369/178.01, 369/43, 712/234, 712/222, 712/4, 712/3, 342/25, 342/93, 704/232, 707/3, 345/420
• US Class Current: 382/103
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30196 Human being; Person
• CPC Class Codes: G06T 7/251 involving models
• CPC Class Codes: G06V 40/20 Movements or behaviour, e.g. gesture recognition recognition of facial expressions G06V40/16
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. The method of claim 1, wherein the state probability model has a Gaussian distribution.

11. The method of claim 10, wherein the state probability model is propagated using a Kalman filter update step.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. 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.

23. The system of claim 14, wherein the state probability model has a Gaussian distribution.

24. The system of claim 23, wherein the state probability model is propagated using a Kalman filter update step.

25. 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.

26. 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.

27. 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.

28. 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.