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

• US 7,929,775 B2
• Filed: 06/13/2006
• Issued: 04/19/2011
• 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
• Primary Examiner(s): Mariam; Daniel G
• Application Number:
  US11/452,815
• Publication Number:
  US 20060285755A1
• Time in Patent Office: 1,771 Days
• Field of Search: 382/154, 382/181, 382/209, 382/218, 382/224, 345/419
• 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 computer-implemented method for recognizing class instances in a 2D image, comprising the steps of:

(a) constructing a plurality of 3D class models, each model having one or more class parts, and storing the models in a database in a memory;

(b) acquiring a 2D image; and

(c) using a processor to match 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 one or more class parts belonging to the 3D class models.

2. The method of claim 1, where the step of constructing a plurality of 3D class models further comprises, for each class model, 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 method 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 method 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 method 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. The method of claim 6, where the step of evaluating each correspondence hypothesis under the aligning transformation by computing a class score further comprises the step of comparing, under the aligning transformation, class parts with image features.

18. The method of claim 17, where the step of comparing, under the aligning transformation, class parts with image features further comprises the step of computing a geometry comparison under the aligning transformation.

19. The method of claim 17, where the step of comparing, under the aligning transformation, class parts with image features further comprises the step of computing an appearance comparison under the aligning transformation.

20. The method 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) computing an aligning transformation for each of one or more class models to the 2D image;

(b) scoring the agreement of each said class model under its aligning transformation by computing a class score; and

(c) choosing class models whose class scores meet selected acceptance criteria.

21. The method of claim 20, where the step of scoring the agreement of class models under the aligning transformations by computing a class score further comprises the step of comparing, under the aligning transformation, class parts with image features.

22. The method of claim 21, where the step of comparing, under the aligning transformation, class parts with image features further comprises the step of computing a geometry comparison under the aligning transformation.

23. The method of claim 21, where the step of comparing, under the aligning transformation, class parts with image features further comprises the step of computing an appearance comparison under the aligning transformation.

24. A non-transitory computer-readable memory containing a database of 3D class models, where:

the computer-readable memory contains a database with a plurality of 3D class models, wherein;

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

25. The computer-readable memory of claim 24, where each part appearance further comprises a second part appearance descriptor that is pose invariant.

26. The computer-readable memory of claim 25, 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.

27. The computer-readable memory of claim 26, where the part geometry represents the canonical geometry of the corresponding elements.

28. The computer-readable memory of claim 26, where the second part appearance descriptor represents the canonical appearance of the corresponding elements.

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

(a) acquiring a 2D image;

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

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

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

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

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

30. The method of claim 29, 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.

31. The method of claim 29, where each class model in the database of 3D class models has class parts and the step of evaluating each correspondence hypothesis under the aligning transformation by computing a class score further comprises the step of comparing, under the aligning transformation, class parts with image features.

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

(a) a memory containing a database of 3D class models;

(b) an image acquisition device for acquiring a 2D image;

(c) a processor 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.

33. The system of claim 32, 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.

34. The system of claim 32, where the processor is further configured to match class instances appearing in the 2D image to the 3D class models by:

(a) computing an aligning transformation for each of one or more class models to the 2D image;

(b) scoring the agreement of each said class model under its aligning transformation by computing a class score; and

(c) choosing class models whose class scores meet selected acceptance criteria.

35. A non-transitory computer-readable medium having embodied thereon a program, the program being executable by a processor to perform a method comprising the steps of:

(a) constructing a database of 3D class models, each model having one or more class parts;

(b) acquiring a 2D image; and

(c) 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 one or more class parts of the 3D class models.