Viewpoint-invariant image matching and generation of three-dimensional models from two-dimensional imagery

• US 20040175039A1
• Filed: 03/05/2004
• Published: 09/09/2004
• Est. Priority Date: 03/06/2003
• Status: Active Grant

• Current Assignee: Animetrics Incorporated
• Original Assignee: Animetrics Incorporated
• Inventors: Miller, Michael
• Granted Patent: US 7,643,685 B2
• Time in Patent Office: Days
• US Class Current: 382/181
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06V 10/772 Determining representative reference patterns, e.g. averaging or distorting patterns; Generating dictionaries
• CPC Class Codes: G06V 20/647 by matching two-dimensional images to three-dimensional objects
• CPC Class Codes: G06V 40/172 Classification, e.g. identification

Abstract

A method and system for characterizing features in a source multifeatured three-dimensional object, and for locating a best-matching three-dimensional object from a reference database of such objects by performing a viewpoint invariant search among the reference objects. The invention further includes the creation of a three-dimensional representation of the source object by deforming a reference object.

Claims

1. A method of comparing at least one source 2D projection of a source multifeatured object to a reference library of 3D reference objects, the method comprising the steps of:

a. providing a plurality of reference 3D representations of generically similar multifeatured objects; and

b. performing a viewpoint-invariant search of the reference 3D representations to locate the reference 3D representation having a 2D projection most resembling the at least one source 2D projection.

2. The method of claim 1 wherein the search step comprises, for each reference 3D representation, searching over a range of possible 2D projections of the 3D representation without actually generating any projections.

3. The method of claim 2 wherein searching over a range of possible 2D projections comprises computing a rigid motion of the reference 3D representation optimally consistent with a viewpoint of the source multifeatured object in at least one of the 2D projections.

4. The method of claim 3 wherein the optimum rigid motion is determined by:

a. estimating a conditional mean of feature items comprising points, curves, surfaces, and subvolumes in a 3D coordinate space associated with the reference 3D representation, which feature items are projectionally consistent with feature items in the at least one source 2D projection; and

b. generating, for rigid motions of the reference 3D representation, minimum mean-squared error estimates between the conditional mean estimate of the projected feature items and corresponding feature items of the reference 3D representation.

5. The method of claim 4 wherein the feature items are generated from the imagery using dynamic programming.

6. The method of claim 4 wherein the feature items are found automatically by using correspondences between source imagery and projected imagery of a reference 3D object.

7. The method of claim 3 wherein the rigid motions comprise pitch, roll, yaw, and translation in three dimensions.

8. The method of claim 7 wherein automatic camera calibration is performed by estimation of camera parameters from image landmarks.

9. The method of claim 1 wherein resemblance is determined by a degree of alignment between feature items in the 3D representation and corresponding feature items in the at least one source 2D projection.

10. The method of claim 4 further comprising constraining the rigid motion based on known 3D position information associated with the at least one source 2D projection.

11. The method of claim 1 further comprising the step of creating a 3D representation of the at least one source 2D projection by deforming the located reference 3D representation so as to resemble the source multifeatured object.

12. The method of claim 11 wherein the located reference 3D representation is deformed using large deformation diffeomorphisms, thereby preserving the geometry and topology of the reference 3D representation.

13. The method of claim 11 wherein the deformation enforces constraints on the symmetry of the reference 3D representation.

14. The method of claim 11 wherein the deformation step comprises deforming the located reference 3D representation so that feature items in the at least one source 2D projection align with corresponding feature items in the located reference 3D representation.

15. The method of claim 11 wherein the deformation step comprises deforming the located reference 3D representation to optimize the match between the projection of a plurality of points on the located reference 3D representation and the at least one source 2D projection.

16. The method of claim 11 wherein the deformation occurs without rigid motions.

17. The method of claim 11 wherein the deformation includes at least one of rigid motions and affine motions.

18. The method of claim 11 wherein the deformation is constrained by at least one of known 3D position information associated with at least one source 2D projection, and 3D data of the source multifeatured object.

19. The method of claim 11 wherein the deformation is performed using a closed form expression.

20. The method of claim 11 wherein the deformation is performed substantially in real time.

21. A method of comparing at least one source 2D projection of a source face to a reference library of 3D reference avatars, the method comprising the steps of:

a. providing a plurality of reference 3D representations of avatars; and

b. performing a viewpoint-invariant search of the reference 3D avatars to locate the reference 3D avatar having a 2D projection most resembling the at least one source 2D projection.

22. The method of claim 21 wherein the search step comprises, for each reference 3D avatar, searching over a range of possible 2D projections of the 3D avatar without actually generating any projections.

23. The method of claim 22 wherein searching over a range of possible 2D projections comprises computing a rigid motion of the reference 3D avatar optimally consistent with a viewpoint of the source face in at least one of the 2D projections.

24. The method of claim 23 wherein the optimum rigid motion is determined by:

a. estimating a conditional mean of feature items comprising points, curves, surfaces, and subvolumes in a 3D coordinate space associated with the reference 3D avatar, which feature items are projectionally consistent with feature items in the at least one source 2D projection; and

b. generating, for rigid motions of the reference 3D avatar, minimum mean-squared error estimates between the conditional mean estimate of the projected feature items and corresponding feature items of the reference 3D avatar.

25. The method of claim 21 further comprising the step of creating a 3D avatar of the at least one source 2D projection by deforming the located reference 3D avatar so as to resemble the source face.

26. The method of claim 21 wherein resemblance is determined by a degree of alignment between feature items in the 3D avatar and the corresponding feature items in the at least one source 2D projection.

27. The method of claim 25 wherein the deformation step comprises deforming the located reference avatar to optimize the match between the projection of a plurality of points on the located reference avatar and the at least one source 2D projection.

28. A system for comparing at least one source 2D projection of a source multifeatured object to a reference library of 3D reference objects, the system comprising:

a. a database comprising a plurality of reference 3D representations of generically similar multifeatured objects; and

b. an analyzer for performing a viewpoint-invariant search of the reference 3D representations to locate the reference 3D representation having a 2D projection most resembling the at least one source 2D projection.

29. The system of claim 28 wherein the analyzer searches, for each reference 3D representation, over a range of possible 2D projections of the 3D representation without actually generating any projections.

30. The system of claim 29 wherein the analyzer computes a rigid motion of the reference 3D representation optimally consistent with a viewpoint of the source multifeatured object in at least one of the 2D projections.

31. The system of claim 30 wherein the analyzer is configured to determine the optimum rigid motion by:

a. estimating a conditional mean of feature items comprising points, curves, surfaces, and subvolumes in a 3D coordinate space associated with the reference 3D representation, which feature items are projectionally consistent with feature items in the at least one source 2D projection; and

b. generating, for rigid motions of the reference 3D representation, minimum mean-squared error estimates between the conditional mean estimate of the projected feature items and corresponding feature items of the reference 3D representation.

32. The system of claim 31 wherein the feature items are generated from the imagery using dynamic programming.

33. The system of claim 31 wherein the feature items are found automatically by using correspondences between source imagery and projected imagery of a reference 3D object.

34. The system of claim 30 wherein the rigid motions comprise pitch, roll, yaw, and translation in three dimensions.

35. The system of claim 34 wherein the analyzer is further configured to perform automatic camera calibration by estimation of camera parameters from image landmarks.

36. The system of claim 28 wherein resemblance is determined by a degree of alignment between feature items in the 3D representation and corresponding feature items in the at least one source 2D projection.

37. The system of claim 31 wherein the analyzer constrains the rigid motion based on known 3D position information associated with the at least one source 2D projection.

38. The system of claim 28 further comprising a deformation module for creating a 3D representation of the at least one source 2D projection by deforming the located reference 3D representation so as to resemble the source multifeatured object.

39. The system of claim 38 wherein the deformation module deforms the located reference 3D representation using large deformation diffeomorphism, thereby preserving the geometry and topology of the reference 3D representation.

40. The system of claim 38 wherein the deformation module enforces constraints on the symmetry of the deformed located reference 3D representation.

41. The system of claim 38 wherein the deformation module deforms the located reference 3D representation so that feature items in the at least one source 2D projection align with corresponding feature items in the located reference 3D representation.

42. The system of claim 38 wherein the deformation module deforms the located reference 3D representation to optimize the match between the projection of a plurality of points on the located reference 3D representation and the at least one source 2D projection.

43. The system of claim 38 wherein the deformation module does not use rigid motions.

44. The system of claim 38 wherein the deformation module uses at least one of rigid motions and affine motions.

45. The system of claim 38 wherein operation of the deformation module is constrained by at least one of known 3D position information associated with at least one source 2D projection, and 3D data of the source multifeatured object.

46. The system of claim 38 wherein the deformation module operates in accordance with a closed-form expression.

47. The system of claim 38 wherein the deformation module performs the deformation substantially in real time.

48. A system for comparing at least one source 2D projection of a source face to a reference library of 3D reference avatars, the system comprising:

a. a database comprising a plurality of reference 3D representations of avatars; and

b. an analyzer for performing a viewpoint-invariant search of the reference 3D avatars to locate the reference 3D avatar having a 2D projection most resembling the at least one source 2D projection.

49. The system of claim 48 wherein the analyzer searches, for each reference 3D representation, over a range of possible 2D projections of the 3D avatar without actually generating any projections.

50. The system of claim 49 wherein the analyzer computes a rigid motion of the reference 3D avatar optimally consistent with a viewpoint of the source face in at least one of the 2D projections.

51. The system of claim 50 wherein the analyzer is configured to determine the optimum rigid motion by:

a. estimating a conditional mean of feature items comprising points, curves, surfaces, and subvolumes in a 3D coordinate space associated with the reference 3D avatar, which feature items are projectionally consistent with feature items in the at least one source 2D projection; and

b. generating, for rigid motions of the reference 3D avatar, minimum mean-squared error estimates between the conditional mean estimate of the projected feature items and corresponding feature items of the reference 3D avatar.

52. The system of claim 48 wherein resemblance is determined by a degree of alignment between feature items in the 3D avatar and corresponding feature items in the at least one source 2D projection.

53. The system of claim 48 further comprising a deformation module for creating a 3D representation of the at least one source 2D projection by deforming the located reference 3D avatar so as to resemble the source face.

54. The system of claim 53 wherein the deformation module deforms the located reference avatar to optimize the match between the projection of a plurality of points on the located reference avatar and the at least one source 2D projection.

55. A method of comparing a source 3D object to at least one reference 3D object, the method comprising the steps of:

a. creating 2D representations of the source object and the at least one reference object; and

b. using projective geometry to characterize a correspondence between the source 3D object and a reference 3D object.

56. A system for comparing a source 3D object to at least one reference 3D object, the system comprising:

a. a projection module for creating 2D representations of the source object and the at least one reference object; and

b. an analyzer which uses projective geometry to characterize a correspondence between the source 3D object and a reference 3D object.

57. A method of creating a 3D representation from at least one source 2D projection of a source multifeatured object, the method comprising the steps of:

a. providing a set of at least one reference 3D representations of generically similar multifeatured objects;

b. locating a reference 3D representation from the set; and

c. creating a 3D representation of the at least one source 2D projection by deforming the located reference 3D representation in accordance with the at least one source 2D projection so as to resemble the source multifeatured object.

58. The method of claim 57 further comprising the step of basing the locating step on the at least one source 2D projection.

59. The method of claim 57 wherein:

a. the set comprises a plurality of reference 3D representations; and

b. the locating step comprises performing a viewpoint-invariant search of the set of reference 3D representations to locate the reference 3D representation having a 2D projection most resembling the at least one source 2D projection.

60. The method of claim 59 wherein the search step comprises, for each reference 3D representation, searching over a range of possible 2D projections of the 3D representation without actually generating any projections.

61. The method of claim 57 wherein searching over a range of possible 2D projections comprises computing a rigid motion of the reference 3D representation optimally consistent with a viewpoint of the source multifeatured object in at least one of the 2D projections.

62. The method of claim 57 wherein resemblance is determined by a degree of alignment between feature items in the 3D representation and corresponding feature items in the at least one source 2D projection

63. The method of claim 57 wherein the deformation step comprises deforming the located reference 3D representation using large deformation diffeomorphism, thereby preserving the geometry and topology of the reference 3D representation.

64. The method of claim 57 wherein the deformation step comprises deforming the located reference 3D representation so that feature items in the at least one source 2D projection align with corresponding feature items in the located reference 3D representation.

65. The method of claim 57 wherein the deformation step comprises deforming the located reference 3D representation to optimize the match between the projection of a plurality of points on the located reference 3D representation and the at least one source 2D projection.

66. The method of claim 57 wherein the deformation is performed substantially in real time.

67. A system for creating a 3D representation from at least one source 2D projection of a source multifeatured object, the system comprising:

a. a database comprising at least one reference 3D representation of generically similar multifeatured objects;

b. an analyzer for locating a reference 3D representation from the set; and

c. a deformation module for creating a 3D representation of the at least one source 2D projection by deforming the located reference 3D representation in accordance with the at least one source 2D projection so as to resemble the source multifeatured object.

68. The system of claim 67 in which the analyzer bases the location of the 3D reference representation on the at least one source 2D projection.

69. The system of claim 67 wherein:

a. the database comprises a plurality of reference 3D representations; and

b. the analyzer locates the reference 3D representation having a 2D projection most resembling the at least one source 2D projection step by performing a viewpoint-invariant search of the set of reference 3D representations.

70. The system of claim 69 wherein the analyzer searches, for each reference 3D representation, over a range of possible 2D projections of the 3D representation without actually generating any projections.

71. The system of claim 70 wherein the search over a range of possible 2D projections comprises computing a rigid motion of the reference 3D representation optimally consistent with a viewpoint of the source multifeatured object in at least one of the 2D projections.

72. The system of claim 67 wherein resemblance is determined by a degree of alignment between feature items in the 3D representation and corresponding feature items in the at least one source 2D projection.

73. The system of claim 67 wherein the deformation module deforms the located reference 3D representation using large deformation diffeomorphism, thereby preserving the geometry and topology of the reference 3D representation.

74. The system of claim 67 wherein the deformation module deforms the located reference 3D representation so that feature items in the at least one source 2D projection align with corresponding feature items in the located reference 3D representation.

75. The system of claim 67 wherein the deformation module deforms the located reference 3D representation to optimize the match between the projection of a plurality of points on the located reference 3D representation and the at least one source 2D projection.

76. The system of claim 67 wherein the deformation is performed substantially in real time.