# US 8,280,150 B2 · Method and apparatus for determining similarity between surfaces

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,280,150 B2
- Document ID: US8280150B2
- Status: Granted
- Kind: B2
- Application number: 12/086,623
- Filed: 2006-12-17
- Published: 2009-01-29
- Granted: 2012-10-02
- Earliest claimed: 2005-12-16
- Assignees: Technion Research & Development Foundation Limited
- Inventors: Ron Kimmel; Alexander Bronstein; Michael Bronstein
- Web page: https://patentgrep.com/patent/US8280150B2

## CPC

- G06V 20/653: {by matching three-dimensional models, e.g. conformal mapping of Riemann surfaces}
- G06V 2201/11: Technique with transformation invariance effect
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## 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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 4)

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

### Claim 6 (depends on 1)

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

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 7)

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

### Claim 9 (depends on 7)

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.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 9)

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.

### Claim 12 (depends on 9)

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.

### Claim 13 (depends on 1)

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

### Claim 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.

### Claim 15 (depends on 14)

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

### Claim 16 (depends on 14)

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.

### Claim 17 (depends on 14)

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

### Claim 18 (depends on 14)

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.

### Claim 19 (depends on 18)

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.

### Claim 20 (depends on 14)

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