REGISTRATION AND COMPARISON OF THREE DIMENSIONAL OBJECTS

• US 20100209005A1
• Filed: 02/13/2009
• Published: 08/19/2010
• Est. Priority Date: 02/13/2009
• Status: Active Grant

• Current Assignee: Cognitech, Inc.
• Original Assignee: Cognitech, Inc.
• Inventors: Lisani, Jose L., Morel, Jean-Michel, Rudin, Leonid I.
• Granted Patent: US 8,605,989 B2
• Time in Patent Office: Days
• US Class Current: 382/218
• 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 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 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

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

3. The method of claim 2 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 determining a transform to place a first triangle formed by the first plurality of lines to a position in a coordinate system, determining a transform to place a second triangle formed by the second plurality of lines to the position of the first triangle, and transforming points of the model of the first 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 physical object and the second 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 approximate 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.

8. The method of claim 1 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 using a computer of determining if a first physical object is the same as a second physical object, comprising:

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

determining n-tangents for the model of the first physical object and the model of the second physical object;

determining if aspects of the surface of the first model and aspects of the surface of the second model match within a predefined criteria; and

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

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

12. The method of claim 10 wherein the model of the first physical object and the model of the second 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 first model and aspects of the surface of the second model match within a predefined criteria comprises determining if n-tangents of the first model correspond to n-tangents of the second model.

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

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

17. The method of claim 15 wherein determining if a surface of the first model about at least one n-tangent of the first model is similar to a surface of the second model about at least one n-tangent of the second model comprises determining a first transform for transforming an n-tangent of the at least one n-tangent of the first model to a position in a coordinate system, determining a second transform for transforming an n-tangent of the at least one n-tangnet of the second model to the position in the coordinate system, transforming information of the first model to the coordinate system using the first transform, transforming information of the second model to the coordinate system using the second transform, and determining a measure of differences between portions of the surface of the first model and portions of the surface of the second model 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 first model and information of the second model if the first model and the second model are declared to be the same.

20. A computer system configured to determine groupings of points of tangency for models of physical objects, comprising:

at least one memory containing program instructions and information defining a surface a physical object using a plurality of points; and

a processor configured by the program instructions to;

determine lines coupling pairs of points;

for each line coupling pairs of points determine if the line cross the surface of the physical object about either of the pairs of points; and

selecting lines coupling pairs of points that do not cross the surface of the physical object about either of the pairs of points.