System and method for recognition in 2D images using 3D class models

• US 20060285755A1
• Filed: 06/13/2006
• Published: 12/21/2006
• Est. Priority Date: 06/16/2005
• Status: Active Grant

• Current Assignee: Strider Labs, Inc.
• Original Assignee: Strider Labs, Inc.
• Inventors: Hager, Gregory D., Wegbreit, Eliot Leonard
• Granted Patent: US 7,929,775 B2
• Time in Patent Office: Days
• US Class Current: 382/224
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06V 20/647 by matching two-dimensional images to three-dimensional objects
• CPC Class Codes: G06V 20/653 by matching three-dimensional models, e.g. conformal mapping of Riemann surfaces

Abstract

A system and method for recognizing instances of classes in a 2D image using 3D class models and for recognizing instances of objects in a 2D image using 3D class models. The invention provides a system and method for constructing a database of 3D class models comprising a collection of class parts, where each class part includes part appearance and part geometry. The invention also provides a system and method for matching portions of a 2D image to a 3D class model. The method comprises identifying image features in the 2D image; computing an aligning transformation between the class model and the image; and comparing, under the aligning transformation, class parts of the class model with the image features. The comparison uses both the part appearance and the part geometry.

Claims

1. A method for recognizing class instances in a 2D image, comprising the steps of

(a) constructing a database of 3D class models;

and

(b) matching class instances appearing in the 2D image to the 3D class models, by identifying one or more image features in the 2D image and comparing the identified image features with class parts belonging to the 3D class models.

2. The method of claim 1, where the step of constructing a 3D class model further comprises the steps of:

(a) acquiring 3D images of sample objects belonging to the class;

(b) constructing an object model for each sample object;

(c) placing the object models in canonical geometric form; and

(d) merging the object models in canonical geometric form.

3. The method of claim 2, where the step of constructing an object model further comprises the steps of identifying one or more interest points and computing a canonical appearance descriptor at each interest point.

4. The method of claim 2, where the step of merging the object models in canonical geometric form further comprises the steps of:

(a) identifying sets of corresponding elements in the object models, each set comprising an element from one object model and one or more corresponding elements from other object models; and

(b) constructing a class part for each set of corresponding elements.

5. The method of claim 4, where the step of constructing a class part further comprises the steps of:

(a) computing a part geometry; and

(b) computing a part appearance;

6. The system of claim 1, where the step of matching class instances appearing in the 2D image to the 3D class models further comprises the steps of:

(a) identifying one or more image features in the 2D image, each feature having a feature location and a feature appearance;

(b) constructing one or more correspondence hypotheses, each correspondence hypothesis comprising a class model and a set of feature-part matches;

(c) using each correspondence hypothesis to compute an aligning transformation of the class model to the 2D image;

(d) evaluating each correspondence hypothesis under the aligning transformation by computing a class score; and

(e) choosing correspondence hypotheses whose class scores meet selected acceptance criteria.

7. The system of claim 6, where the step of constructing a correspondence hypothesis further comprises the steps of:

(a) selecting an initial correspondence hypothesis;

(b) identifying potential additional feature-part matches;

(c) for each additional feature-part match, evaluating the class score for the correspondence hypothesis augmented by the feature part match;

(d) extending the correspondence hypothesis with those feature part matches that increase the class score; and

(e) repeating steps (b) through (d) above until no new feature-part matches are found that increase the class score.

8. The system of claim 7, where the step of selecting an initial correspondence hypothesis further comprises the steps of:

(a) choosing a class model and a set of initial feature-part matches, each feature-part match comprising a feature appearance and a part appearance, and where the initial-feature part matches is chosen by comparing some component of the feature appearance with some component of the part appearance; and

(b) forming a vector of the initial feature-part matches.

9. The method of claim 7, where the step of evaluating the class score for the correspondence hypothesis augmented by the feature-part match further comprises the steps of:

(a) using the augmented correspondence hypothesis to compute an aligning transformation of the class model to the image;

(b) comparing, under the aligning transformation, class parts with image features;

10. The method of claim 9, where the step of comparing, under the aligning transformation, class parts with image features further comprises the steps of:

(a) computing a geometry comparison under the aligning transformation;

(b) computing an appearance comparison under the aligning transformation; and

(c) combining the results of the geometry comparison and the appearance comparison.

11. The method of claim 10, where the step of computing the geometry comparison under the aligning transformation further comprises the step of projecting the location component of the class part geometry to its equivalent 2D image location.

12. The method of claim 10, where the step of computing the geometry comparison under the aligning transformation further comprises the step of projecting the image feature location to its equivalent 3D model location.

13. The method of claim 10, where the step of computing the appearance comparison under the aligning transformation further comprises the step of projecting some component of the image feature appearance to its equivalent 3D model appearance.

14. The method of claim 10, where the step of computing the appearance comparison under the aligning transformation further comprises the step of projecting some component of the class part appearance to its equivalent 2D image appearance.

15. The method of claim 1, further comprising the step of frontally aligning the 2D image in local regions.

16. The method of claim 15, where the step of frontally aligning the 2D image in local regions is performed by hypothesizing one or more possible surface orientations and, for each surface orientation, computing the local image appearance as if the surface were at that orientation.

17. A database of 3D class models, where:

(a) each 3D class model comprises a plurality of class parts;

(b) each class part comprises a part geometry and a part appearance; and

(c) each part appearance comprises a first part appearance descriptor that is computed from 2D information.

18. The system of claim 17, where each part appearance further comprises a second part appearance descriptor that is pose invariant.

19. The system of claim 18, where:

(a) each 3D class model represents a set of sample objects belonging to the class;

(b) each sample object comprises a plurality of elements;

(c) a plurality of the elements in each sample object have corresponding elements in another sample object;

(d) each element comprises an element geometry and an element appearance.

(e) each class part represents a set of corresponding elements in the sample objects;

(f) the part geometry represents the set of element geometries of the corresponding elements; and

(g) the part appearance represents the set of element appearances of the corresponding elements.

20. The system of claim 19, where the part geometry represents the canonical geometry of the corresponding elements.

21. The system of 19, where the second part appearance descriptor represents the canonical appearance of the corresponding elements.

22. A method for recognizing class instances in a 2D image, using a database of 3D class models, comprising the steps of

(a) identifying one or more image features in the 2D image, each feature having a feature location and a feature appearance;

(b) constructing one or more correspondence hypotheses, each correspondence hypothesis comprising a class model and a set of feature-part matches;

(c) using each correspondence hypothesis to compute an aligning transformation of the class model to the 2D image;

(d) evaluating each correspondence hypothesis under the aligning transformation by computing a class score; and

(e) choosing correspondence hypotheses whose class scores meet selected acceptance criteria.

23. A system for recognizing class instances in a 2D image, comprising

(a) a database of 3D class models;

(b) a computer configured to match class instances appearing in the 2D image to the 3D class models, by identifying image features in the 2D image and comparing the image features with class parts belonging to the 3D class models.

24. The system of claim 23, where in the database of 3D class models:

(a) each 3D class model comprises a plurality of class parts;

(b) each class part comprises a part geometry and a part appearance; and

(c) each part appearance comprises a first part appearance descriptor that is computed from 2D information and a second part appearance descriptor that is pose invariant.

25. A computer-readable medium storing information for performing the steps of:

(a) constructing a database of 3D class models; and

(b) matching class instances appearing in the 2D image to the 3D class models, by identifying one or more image features in the 2D image and comparing the identified image features with class parts belonging to the 3D class models.

26. A method for recognizing objects in a 2D image, comprising the steps of:

(a) constructing a database of 3D object class models where each 3D object class model comprises a plurality of object class parts, each object class part comprising a part geometry and a part appearance, where each part appearance comprises a first part appearance descriptor that is computed from 2D information and a second part appearance descriptor that is pose invariant; and

(b) matching object instances appearing in the 2D image to the 3D object class models, by identifying one or more image features in the 2D image and comparing the identified image features with object class parts belonging to the 3D object class models.

27. The method of claim 26, where the step of constructing a 3D object class model further comprises the steps of:

(a) acquiring 3D images of the object in various sample states;

(b) constructing an object model for each sample state;

(c) placing the object models in canonical geometric form; and

(d) merging the object models in canonical geometric form.

28. The method of claim 26, where the step of comparing the image features with object class parts belonging to the 3D object class models further comprises the steps of:

(a) constructing one or more correspondence hypotheses, each correspondence hypothesis comprising an object class model and a set of feature-part matches;

(b) using each correspondence hypothesis to compute an aligning transformation of the object class model to the 2D image;

(c) evaluating each correspondence hypothesis under the aligning transformation by computing a class score; and

(d) choosing correspondence hypotheses whose class scores meet selected acceptance criteria.

29. The method of claim 28, where

(a) the step of constructing one or more correspondence hypotheses further comprises the step of identifying feature-part matches using the first part appearance descriptors;

and

(b) the step of computing a class score further comprises the step of computing appearance comparisons, under the aligning transformations, using the second part appearance descriptors.

30. A method for recognizing deformable objects in a 2D image, comprising the steps of:

(a) constructing a database of 3D object class models where each 3D object class model comprises a plurality of object class parts, each object class part comprising a part geometry and a part appearance, where each part appearance comprises a first part appearance descriptor that is computed from 2D information and a second part appearance descriptor that is pose invariant, where the part geometry models variability of the object due to deformations; and

(b) matching object instances appearing in the 2D image to the 3D object class models, by identifying image features in the 2D image and comparing the image features with object class parts belonging to the 3D object class models.

31. A method for recognizing objects in a 2D image, where the objects have multiple appearance states, comprising the steps of:

(a) constructing a database of 3D object class models where each 3D object class model comprises a plurality of object class parts, each object class part comprising a part geometry and a part appearance, where each part appearance comprises a first part appearance descriptor that is computed from 2D information and a second part appearance descriptor that is pose invariant, where one or more of the part appearance descriptors model the multiple appearance states of the object; and

(b) matching object instances appearing in the 2D image to the 3D object class models, by identifying image features in the 2D image and comparing the image features with object class parts belonging to the 3D object class models.

32. A system for recognizing objects in a 2D image, comprising:

(a) a database of 3D object class models where each 3D object class model comprises a plurality of object class parts, each object class part comprising a part geometry and a part appearance, where each part appearance comprises first appearance descriptor which is computed from 2D information and a second part appearance descriptor that is pose invariant.

(b) a computer configured to match object instances appearing in the 2D image to the 3D object class models, by identifying one or more image features in the 2D image and comparing the identified image features with object class parts belonging to the 3D object class models.

33. A computer-readable medium storing information for performing the steps of:

(a) constructing a database of 3D object class models where each 3D object class model comprises a plurality of object class parts, each object class part comprising a part geometry and a part appearance, where each part appearance comprises a first part appearance descriptor that is computed from 2D information and a second part appearance descriptor that is pose invariant; and

(b) matching object instances appearing in the 2D image to the 3D object class models, by identifying one or more image features in the 2D image and comparing the identified image features with object class parts belonging to the 3D object class models.