Registration and comparison of three dimensional objects in facial imaging

• US 8,605,989 B2
• Filed: 02/13/2009
• Issued: 12/10/2013
• Est. Priority Date: 02/13/2009
• Status: Expired due to Fees

• Current Assignee: Cognitech, Inc.
• Original Assignee: Cognitech, Inc.
• Inventors: Rudin, Leonid I., Lisani, Jose L., Morel, Jean-Michel
• Primary Examiner(s): Newman, Michael A
• Application Number:
  US12/371,473
• Publication Number:
  US 20100209005A1
• Time in Patent Office: 1,761 Days
• Field of Search: 382/115, 382/118, 382/154, 382/199, 382/218, 382/294, 345/419, 345/420, 345/423, 345/427
• US Class Current: 382/154
• CPC Class Codes: G06V 20/653 by matching three-dimensional models, e.g. conformal mapping of Riemann surfaces

Abstract

Information of different scans of physical objects may require comparison, for example to determine if the scans are of the same object or if an object has changed, or better information for a three dimensional model may be desired. Different scans of physical objects may be compared by determining lines or planes tangent to a surface at a discrete number of points, registering three dimensional information provided by the scans using the tangent lines or planes, and determining a measure of discrepancy between the surfaces. Three dimensional information of different scans of the same object may also be merged after determining lines or planes tangent to a surface at a discrete number of points and performing registration and merging.

Claims

1. A method to determine congruence between a model corresponding to a first three dimensional (3-D) physical object and a model corresponding to a second 3-D physical object based on either complete or incomplete data for at least one of the model of the first 3-D physical object and the model of the second 3-D physical object, comprising:

determining, for the model of the first 3-D physical object, a plurality of first tangency points;

determining, for the model of the first 3-D physical object, a plurality of first lines, wherein each line of the plurality of first lines couples at least two first tangency points such that each line of the plurality of first lines does not intersect a surface defined by the model of the first 3-D physical object in a vicinity of the at least two first tangency points;

determining, for the model of the second 3-D physical object, a plurality of second tangency points;

determining, for the model of the second 3-D physical object, a plurality of second lines, wherein each line of the plurality of second lines couples at least two second tangency points such that each line of the plurality of second lines does not intersect a surface defined by the model of the second 3-D physical object in a vicinity of the at least two second tangency points;

registering the plurality of first lines of the model of the first 3-D physical object and the plurality of second lines of the model of the second 3-D physical object to a common coordinate system;

determining a measure of discrepancy between the model of the first 3-D physical object and the model of the second 3-D physical object; and

declaring that the model corresponding to the first 3-D physical object is the same as the model corresponding to the second physical 3-D object if the measure of discrepancy is less than a predefined magnitude.

2. The method of claim 1 wherein the number of first tangency points is 3 tangency points, the number of first lines is 3 lines, the number of second tangency points is 3 tangency points, and the number of second lines is 3 lines.

3. The method of claim 2 wherein registering the model of the first 3-D physical object and the model of the second 3-D physical object to a common coordinate system using the plurality of first lines and the plurality of second lines comprises determining a transform to place a first triangle formed by the plurality of first lines to a position in a coordinate system, determining a transform to place a second triangle formed by the plurality of second lines to the position of the first triangle, and transforming points of the model of the first 3-D physical object.

4. The method of claim 3 wherein the first transform is a null transform.

5. The method of claim 3 wherein determining a measure of discrepancy between the model of the first 3-D physical object and the second 3-D physical object comprises determining a measure of differences in position of at least some corresponding points of surfaces of the transformed first model and the transformed second model.

6. The method of claim 5 wherein the at least some corresponding points are near the first triangle or the second triangle.

7. The method of claim 1 further comprising merging information of the first model and information of the second model.

23. The method of claim 1, wherein at least one of the first 3-D physical object and the second 3-D physical object corresponds to a portion of a head.

24. The method of claim 1, wherein at least one of the model of the first 3-D physical object and the model of the second 3-D physical object lack complete 3-D model information.

25. The method of claim 1, further comprising:

determining, for the model of the first 3-D physical object, a plurality of third tangency points;

determining, for the model of the first 3-D physical object, a plurality of third lines, wherein each line of the plurality of third lines couples at least two third tangency points such that each line of the plurality of third lines does not intersect a surface defined by the model of the first 3-D physical object in a vicinity of the at least two third tangency points;

determining, for the model of the second 3-D physical object, a plurality of fourth tangency points;

determining, for the model of the second 3-D physical object, a plurality of fourth lines, wherein each line of the plurality of fourth lines couples at least two fourth tangency points such that each line of the plurality of fourth lines does not intersect a surface defined by the model of the second 3-D physical object in a vicinity of the at least two fourth tangency points;

registering the plurality of third lines of the model of the first 3-D physical object and the plurality of fourth lines of the model of the second 3-D physical object to a second common coordinate system, wherein the second common coordinate system is different than the common coordinate system in which the plurality of first lines of the model of the first 3-D physical object and the plurality of second lines of the model of the second 3-D physical object have been registered; and

determining a measure of discrepancy between the model of the first 3-D physical object and the model of the second 3-D physical object.

8. A method using a computer of determining congruence between physical objects, the physical objects each having a surface described by a model, comprising;

determining, for a model of a first physical object, a first plurality of tangency points;

determining, for the model of the first physical object, a first plurality of lines coupling tangency points that do not intersect a surface defined by the model of the first physical object in a vicinity of the tangency points coupled by the first plurality of lines;

determining, for a model of a second physical object, a second plurality of tangency points;

determining, for the model of the second physical object, a second plurality of lines coupling tangency points that do not intersect a surface defined by the model of the second physical object in a vicinity of the tangency points coupled by the second plurality of lines;

registering the model of the first physical object and the model of the second physical object to a common coordinate system using the first plurality of lines and the second plurality of lines;

determining a measure of discrepancy between the model of the first physical object and the model of the second physical object; and

declaring that the first physical object is the same as the second physical object if the measure of discrepancy is less than a predefined magnitude;

wherein registering the model of the first physical object and the model of the second physical object to a common coordinate system using the first plurality of lines and the second plurality of lines comprises;

extracting first local curves from the model of the first physical object by determining intersections with a surface defined by the model of the first physical object and a plane associated with the first plurality of lines;

extracting second local curves from the model of the second physical object by determining intersections with a surface defined by the model of the second physical object and a plane associated with the second plurality of lines;

encoding the first local curves and the second local curves determining meaningful matches between the local curves;

determining a first transform to map the first local curves with meaningful matches and a second transform to map the second local curves with meaningful matches to a common position on a coordinate system; and

applying the first transform to information of the model of the first physical object and applying the second transform to information of the model of the second physical object.

9. The method of claim 8 wherein the first local curves and the second local curves are Jordan curves.

10. A method to determine if a model of a first three dimensional (3-D) physical object is the same as a model of a second 3-D physical object, comprising:

receiving the model of the first 3-D physical object and the model of the second 3-D physical object, the model of the first 3-D physical object comprising a plurality of points descriptive of a surface of the first 3-D physical object and the model of the second 3-D physical object comprising a plurality of points descriptive of a surface of the second 3-D physical object;

determining n-tangents for the model of the first 3-D physical object and n-tangents for the model of the second 3-D physical object, wherein n represents a number of coupled tangency points and n is greater than or equal to two;

registering the n-tangents for the model of the first 3-D physical object and the n-tangents for the model of the second 3-D physical object to a common coordinate system;

determining if aspects of the surface of the model of the first 3-D physical object and aspects of the surface of the model of the second 3-D physical object match within a predefined criteria; and

declaring that the model corresponding to the first 3-D physical object and the model corresponding to the second 3-D physical object are the same 3-D physical object if the corresponding n-tangents match within the predefined criteria.

11. The method of claim 10 wherein the model of the first 3-D physical object and the model of the second 3-D physical object each comprise a cloud of points.

12. The method of claim 10 wherein the model of the first 3-D physical object and the model of the second 3-D physical model each comprise a three dimensional mesh.

13. The method of claim 12 wherein the three dimensional mesh comprises a plurality of points defining vertices of polygons.

14. The method of claim 10 wherein determining if aspects of the surface of the model of the first 3-D physical object and aspects of the surface of the model of the second 3-D physical object match within a predefined criteria comprises determining if n-tangents of the model of the first 3-D physical object correspond to n-tangents of the model of the second 3-D physical object.

15. The method of claim 10 wherein determining if aspects of the surface of the model of the first 3-D physical object and aspects of the surface of the model of the second 3-D physical object match within a predefined criteria comprises determining if a surface of the model of the first 3-D physical object about at least one n-tangent of the model of the first 3-D physical object is similar to a surface of the model of the second 3-D physical object about at least one n-tangent of the model of the second 3-D physical object.

16. The method of claim 15 wherein the at least one n-tangent of the model of the first 3-D physical object and the at least one n-tangent of the model of the second 3-D physical object are corresponding n-tangents.

17. The method of claim 15 wherein determining if a surface of the model of the first 3-D physical object about at least one n-tangent of the model of the first 3-D physical object is similar to a surface of the model of the second 3-D physical object about at least one n-tangent of the model of the second 3-D physical object comprises determining a measure of differences between portions of the surface of the model of the first 3-D physical object and portions of the surface of the model of the second 3-D physical object about the n-tangents.

18. The method of claim 10 wherein the surfaces are interior surfaces.

19. The method of claim 10 further comprising fusing information of the model of the first 3-D physical object and information of the model of the second 3-D physical object if the model of the first 3-D physical object and the model of the second 3-D physical object are declared to be the same.

20. The method of claim 10, wherein registering the model of the first 3-D physical object and the model of the second 3-D physical object to a common coordinate system using the n-tangents comprises determining a first transform for transforming an n-tangent of the at least one n-tangent of the model of the first 3-D physical object to a position in a coordinate system, determining a second transform for transforming an n-tangent of the at least one n-tangent of the model of the second 3-D physical object to the position in the coordinate system, transforming information of the model of the first 3-D physical object to the coordinate system using the first transform, transforming information of the model of the second 3-D physical object to the coordinate system using the second transform.

26. The method of claim 10, wherein at least one of the first 3-D physical object and the second 3-D physical object corresponds to a portion of a head.

27. The method of claim 10, wherein at least one of the model of the first 3-D physical object and the model of the second 3-D physical object lack complete 3-D model information.

21. A system for determining congruence between a model corresponding to a first three dimensional (3-D) physical object and a model corresponding to a second 3-D physical object based on either complete or incomplete data for at least one of the model of the first 3-D physical object and the model of the second 3-D physical object, comprising:

at least one memory containing program instructions and data corresponding to at least one of the model of the first 3-D physical object and the model of the second 3-D physical object;

at least one processor in communication with the memory, wherein the processor is configured by the program instructions to;

determine, for the model of the first 3-D physical object, a plurality of first tangency points;

determine, for the model of the first 3-D physical object, a plurality of first lines, wherein each line of the plurality of first lines couples at least two first tangency points such that each line of the plurality of first lines does not intersect a surface defined by the model of the first 3-D physical object in a vicinity of the at least two first tangency points;

determine, for the model of the second 3-D physical object, a plurality of second tangency points;

determine, for the model of the second 3-D physical object, a plurality of second lines, wherein each line of the plurality of second lines couples at least two second tangency points such that each line of the plurality of second lines does not intersect a surface defined by the model of the second 3-D physical object in a vicinity of the at least two second tangency points;

register the plurality of first lines of the model of the first 3-D physical object and the plurality of second lines of the model of the second 3-D physical object to a common coordinate system;

determine a measure of discrepancy between the model of the first 3-D physical object and the model of the second 3-D physical object; and

declare that the model corresponding to the first 3-D physical object is the same as the model corresponding to the second physical 3-D object if the measure of discrepancy is less than a predefined magnitude.

22. A system for determining if a model of a first three dimensional (3-D) physical object is the same as a model of a second 3-D physical object, comprising:

receiving the model of the first 3-D physical object and the model of the second 3-D physical object, the model of the first 3-D physical object comprising a plurality of points descriptive of a surface of the first 3-D physical object and the model of the second 3-D physical object comprising a plurality of points descriptive of a surface of the second 3-D physical object;

determining n-tangents for the model of the first 3-D physical object and n-tangents for the model of the second 3-D physical object, wherein n represents a number of coupled tangency points and n is greater than or equal to two;

registering the n-tangents for the model of the first 3-D physical object and the n-tangents for the model of the second 3-D physical object to a common coordinate system;

determining if aspects of the surface of the model of the first 3-D physical object and aspects of the surface of the model of the second 3-D physical object match within a predefined criteria; and

declaring that the model corresponding to the first 3-D physical object and the model corresponding to the second 3-D physical object are the same 3-D physical object if the corresponding n-tangents match within the predefined criteria.