Method and apparatus for determining similarity between surfaces

1. A method of determining similarity between a non-planar probe surface represented by a probe point-cloud and a non-planar model surface represented by a model point-cloud, the surfaces representing physical objects, the method comprising:

calculating a matrix of geodesic distances characterizing said non-planar model surface represented by said model point-cloud;

embedding said probe surface into an embedding space having a non-constant sectional curvature, wherein said embedding space is a polyhedral approximation of the model surface;

defining an objective function based on said embedding space adapted to map either said probe surface onto said model surface or said model surface onto said probe surface; and wherein said objective function is selected so as to allow calculation of at least one of: a partial embedding distance between the probe surface and the model surface; and a Gromov-Hausdorff distance between the probe surface and the model surface;

calculating an extremal value of said objective function by an iterative process, said iterative process comprising starting with a plurality of initial values of the optimization variables of the objective function, and iteratively updating the locations on said model surface so as to produce a decreasing sequence of function values; wherein said iterative process is selected from the group consisting of the steepest descent method, the fixed step gradient method, the conjugate gradient method, the Newton method, coordinate-wise descent and any combination thereof; and

determining similarity between the probe surface and the model surface based on said extremal value.

2. A method of searching a library of non-planar model surfaces for at least a partial match to a non-planar probe surface, the non-planar probe surface being represented by a probe point-cloud and each non-planar model surface being represented by a model point-cloud, the method comprising, for each non-planar model surface, performing the method of claim 1 so as to determine similarity between the probe surface and said model surface, thereby determining the presence or absence of at least a partial match.

3. The method of claim 1 , wherein said calculation of said extremal value comprises multiresolution optimization.

4. The method of claim 1 , further comprising selecting a subset of the probe point-cloud corresponding to a predetermined patch of the probe surface, wherein said calculation of said extremal value is based on said subset.

5. The method of claim 4 , wherein said geodesic distances are calculated using the fast marching method.

6. The method of claim 1 , further comprising constructing said polyhedral approximation from the model point-cloud.

7. The method of claim 1 , wherein said objective function comprises a sum of local distortions, each characterizing embedding of a pair of points in the probe point-cloud into said embedding space.

8. The method of claim 7 , wherein said sum is a weighted sum.

9. The method of claim 7 , wherein a plurality of said local distortions in said sum comprise a function of the difference between a first geodesic distance defined in the probe surface and a second geodesic distance, corresponding to said first geodesic distance and being defined in said embedding space.

10. The method of claim 9 , wherein said first geodesic distance characterizes a pair of points of the probe point-cloud and said second geodesic distance characterizes images of said pair of points.

11. The method of claim 9 , wherein said first geodesic distance characterizes a pair of points of the embedding space and said second geodesic distance characterizes images of said pair of points.

12. The method of claim 9 , wherein said first geodesic distance is a distance between a first point of the probe point-cloud and an image of a first point of said embedding space, and said second geodesic distance is a distance between a second point of said embedding space and an image of a second point of the probe point-cloud.

13. The method of claim 1 , wherein said probe surface and said model surface represent faces.

14. Apparatus for determining similarity between a non-planar probe surface represented by a probe point-cloud and a non-planar model surface represented by a model point-cloud, the apparatus comprising:

a extremal value calculator, for calculating a extremal value of an objective function describing embedding of said probe surface into an embedding space having a non-constant sectional curvature according to a method comprising:

defining an objective function based on said embedding space adapted to map either said probe surface onto said model surface or said model surface onto said probe surface; and wherein said objective function is selected so as to allow calculation of at least one of: a partial embedding distance between the probe surface and the model surface; and a Gromov-Hausdorff distance between the probe surface and the model surface, and

calculating an extremal value of said objective function by an iterative process, said iterative process comprising starting with a plurality of initial values of the optimization variables of the objective function, and iteratively updating the locations on said model surface so as to produce a decreasing sequence of function values; wherein said iterative process is selected from the group consisting of the steepest descent method, the fixed step gradient method, the conjugate gradient method, the Newton method, coordinate-wise descent and any combination thereof;

a matrix calculator for calculating a matrix of geodesic distances corresponding to the probe point-cloud, wherein said embedding space is a polyhedral approximation of the model surface; and

a similarity determinator operable to determine the similarity between the probe surface and the model surface based on said extremal value.

15. The apparatus of claim 14 , wherein said extremal value calculator is operable to employ multiresolution optimization.

16. The apparatus of claim 14 , further comprising a subset selector for selecting a subset of the probe point-cloud corresponding to a predetermined patch of the probe surface, wherein said extremal value calculator is operable to use said subset for calculating said extremal value.

17. The apparatus of claim 14 , further comprising a polyhedron constructor for constructing said polyhedral approximation from the model point-cloud.

18. The apparatus of claim 14 , wherein said objective function comprises a sum of local distortions, each characterizing embedding of a pair of points in the probe point-cloud into said embedding space.

19. The apparatus of claim 18 , wherein at least a plurality of said local distortions in said sum comprise a function of the difference between a first geodesic distance defined in the probe surface and a second geodesic distance, corresponding to said first geodesic distance and being defined in said embedding space.

20. The apparatus of claim 14 , wherein said geodesic distances are calculated using the fast marching method.