Method and apparatus for recognizing 3-D objects

• US 8,345,988 B2
• Filed: 06/22/2005
• Issued: 01/01/2013
• Est. Priority Date: 06/22/2004
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Shan, Ying, Matei, Bogdan Calin Mihai, Sawhney, Harpreet Singh, Kumar, Rakesh
• Primary Examiner(s): Bali, Vikkram
• Assistant Examiner(s): Rosario, Dennis
• Application Number:
  US11/159,969
• Publication Number:
  US 20060013450A1
• Time in Patent Office: 2,750 Days
• Field of Search: 382/216, 382/258, 382/181, 382/276, 382/282, 382/160, 382/190, 382/218, 706/19, 700/33, 700/34, 700/36, 700/100, 700/103, 375/E7.116, 375/E7.273, 345/631, 707/747
• US Class Current: 382/218
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 20/64 Three-dimensional objects
• CPC Class Codes: G06V 20/653 by matching three-dimensional models, e.g. conformal mapping of Riemann surfaces

Abstract

A method and apparatus for recognizing an object, comprising providing a set of scene features from a scene, pruning a set of model features, generating a set of hypotheses associated with the pruned set of model features for the set of scene features, pruning the set of hypotheses, and verifying the set of pruned hypotheses is provided.

Claims

1. A method for recognizing an object in a scene coordinate system with a set of model features from a plurality of sets of model features, comprising:

obtaining a set of scene features associated with the object from the scene coordinate system;

pruning the set of model features from a database, based on a comparison between the set of scene features and the set of model features to produce a pruned set of model features by applying a set of normals representing surface descriptor parameters to prune bogus model features, wherein the surface descriptor parameters comprise a location and a spin image;

generating a set of pose hypotheses based on a pair of scene features selected from the set of scene features;

removing one or more bogus pose hypotheses from the set of pose hypotheses through the use of geometric constraints, thereby creating a refined set of pose hypotheses;

pruning said refined set of pose hypotheses based on a comparison between each pose hypotheses from the refined set of pose hypotheses and a pair of model features selected from the set of pruned model features by;

computing the probability of collision between generated hash values of each of the refined set of pose hypotheses and the pair of model features and retaining those pose hypotheses from the refined set of pose hypotheses and the pair of model features whose probability of collision is above a threshold probability; and

selecting a verified pose hypothesis from the pruned and refined set of pose hypotheses by;

transforming the pruned set of model features into the scene coordinate system, calculating a similarity score for each pose hypothesis from the pruned and refined set of pose hypotheses based on a similarity between the each pose hypothesis and the transformed set of model features, and identifying the verified pose hypothesis associated with a highest similarity score.

2. The method of claim 1, wherein at least one of said refined set of pose hypotheses is used to transform said set of scene features into said pruned model features.

3. The method of claim 1, wherein pruning the set of model features comprises applying locality sensitive hashing (LSH) to prune said bogus model features.

4. The method of claim 1, further comprising a step of applying doublet-based hypotheses parameters comprising:

obtaining a pair of scene features for transforming to a corresponding pair of model features; and

generating a pose hypothesis.

5. The method of claim 4, wherein said step of applying doublet-based hypotheses parameters comprises associating angle and distance between the pair of scene features and the pair of model features.

6. The method of claim 1, wherein said step of generating the set of pose hypothesis comprises applying a RANSAC-based verification method.

7. The method of claim 6, wherein said RANSAC-based verification method is a multi-model RANSAC-based verification method.

8. The method of claim 1, wherein the set of scene features are obtained from a three dimensional point cloud.

9. A non-transitory computer-readable medium having stored thereon a plurality of instructions, which, when executed by a processor, cause the processor to perform the steps of a method for recognizing an object in a scene coordinate system with a set of model features from a plurality of sets of model features stored in a database, comprising:

obtaining a set of scene features associated with the object from the scene coordinate system;

pruning the set of model features from the database, based on a comparison between the set scene features and the set model features to produce a pruned set of model features by applying a set of normals representing surface descriptor parameters to prune bogus model features, wherein the surface descriptor parameters comprise a location and a spin image;

generating a set of pose hypotheses based on a pair of scene features selected from the set of scene features;

removing one or more bogus pose hypotheses from the set of pose hypotheses through the use of geometric'"'"' constraints, thereby creating a refined set of pose hypotheses;

pruning said refined set of pose hypotheses based on a comparison between each pose hypotheses from the refined set of pose hypotheses and a pair of model features selected from the set of pruned model features by;

computing the probability of collision between generated hash values of the refined set of pose hypotheses and the pair of model features and retaining those pose hypotheses from the refined set of pose hypotheses and the pair of model features whose probability of collision is above a threshold probability; and

selecting a verified pose hypothesis from the pruned and refined set of pose hypotheses by;

transforming the pruned set of model features into the scene coordinate system, calculating a similarity score for each pose hypothesis from the pruned and refined set of pose hypotheses based on a similarity between the each pose hypothesis and the transformed set of model features, and identifying the verified pose hypothesis associated with a highest similarity score.

10. The computer-readable medium of claim 9, wherein at least one of said refined set of pose hypotheses is used to transform said scene features into said pruned model features.

11. The computer-readable medium of claim 9, pruning the set of model features comprises applying locality sensitive hashing (LSH) to prune said bogus model features.

12. The computer-readable medium of claim 9, further comprising a step of applying doublet-based hypotheses parameters comprising:

obtaining a pair of scene features for transforming to a corresponding pair of model features; and

generating a pose hypothesis.

13. The computer-based medium of claim 12, wherein said step of applying doublet-based hypotheses parameters comprises associating angle and distance between the pair of scene features and the pair of model features.

14. The computer readable method of claim 9, wherein said step of generating the set of pose hypothesis comprises applying a RANSAC-based verification method.

15. An apparatus for recognizing an object in a scene coordinate system with a set of model features from a plurality if set of model features, comprising:

means for obtaining a set of scene features associated with the object from the scene coordinate system;

means for pruning the set of model features from a database, based on a comparison between the set scene features and the set model features to produce a pruned set of model features by applying a set of normals representing surface descriptor parameters to prune bogus model features, wherein the surface descriptor parameters comprise a location and a spin image;

means for generating a set of pose hypotheses based on a pair of scene features selected from the set of scene features;

means for applying geometric constraints to remove one or more bogus pose hypotheses for the set of pose hypotheses, thereby creating a refined set of pose hypotheses;

means for pruning said refined set of pose hypotheses based on a comparison between each pose hypotheses from the refined set of pose hypotheses and a pair of model features selected from the set of pruned model features by;

computing the probability of collision between generated hash values of the refined set of pose hypotheses and the pair of model features and retaining those pose hypotheses from the refined set of pose hypotheses and the pair of model features whose probability of collision is above a threshold probability; and

means for selecting a verified pose hypothesis from the pruned and refined set of pose hypotheses by;

transforming the set of pruned model features into the scene coordinate system, calculating a similarity score for each pose hypothesis from the pruned and refined set of pose hypotheses based on a similarity between the each pose hypothesis and the transformed set of model features; and

identifying the verified pose hypothesis associated with a highest similarity score.

16. A computer implemented method for recognizing an object in a scene coordinate system with a set of model features from a plurality of sets of model features, comprising:

obtaining a set of scene features associated with the object from the scene coordinate system;

pruning the set of model features from a database, based on a comparison between the set of scene features and the set of model features to produce a pruned set of model features by applying a set of normals representing surface descriptor parameters to prune bogus model features wherein the surface descriptor parameters comprise a location and a spin image;

generating, by a computer, a set of pose hypotheses based on a pair of scene features selected from the set of scene features;

removing one or more bogus pose hypotheses from the set of pose hypotheses through the use of geometric constraints, thereby creating a refined set of pose hypotheses;

pruning said refined set of pose hypotheses based on a comparison between each pose hypotheses from the refined set of pose hypotheses and a pair of model features selected from the set of pruned model features by;

computing the probability of collision between generated hash values of each of the refined set of pose hypotheses and the pair of model features and retaining those pose hypotheses from the refined set of pose hypotheses and the pair of model features whose probability of collision is above a threshold probability; and

selecting a verified pose hypothesis from the pruned and refined set of pose hypotheses.