Method and apparatus for determining similarity between surfaces
AssigneeTechnion Research & Development Foundation Limited
InventorsRon Kimmel, Alexander Bronstein, Michael Bronstein
Life of this patent
Estimating the term…
Abstract
A method for determining similarity between a non-planar probe surface and a non-planar model surface is disclosed. The method comprises calculating an extremal value of an objective function describing embedding of the probe surface into an embedding space having a non-constant sectional curvature; and determining similarity between the probe surface and the model surface based on the extremal value.
Claims20
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.
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.
Dependencies are inferred from the claim text.