System and a method for learning features on geometric domains

• US 10,013,653 B2
• Filed: 01/26/2016
• Issued: 07/03/2018
• Est. Priority Date: 01/26/2016
• Status: Active Grant

• Current Assignee: Fabula AI Limited (X Holdings Corp.)
• Original Assignee: Università della Svizzera italiana
• Inventors: Bronstein, Michael, Boscaini, Davide, Masci, Jonatan, Vandergheynst, Pierre
• Primary Examiner(s): Mushambo, Martin
• Application Number:
  US15/006,694
• Publication Number:
  US 20170213381A1
• Time in Patent Office: 889 Days
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 18/21345 enforcing sparsity or involving a domain transformation
• CPC Class Codes: G06F 18/21355 nonlinear criteria, e.g. embedding a manifold in a Euclidean space
• CPC Class Codes: G06N 3/045 Combinations of networks
• CPC Class Codes: G06N 3/08 Learning methods
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 20/64 Three-dimensional objects

Abstract

A method for extracting hierarchical features from data defined on a geometric domain is provided. The method includes applying on said data at least an intrinsic convolution layer, including the steps of applying a patch operator to extract a local representation of the input data around a point on the geometric domain and outputting the correlation of a patch resulting from the extraction with a plurality of templates. A system to implement the method is also described.

Claims

1. A method for extracting hierarchical features from input data defined on a geometric domain, comprising applying on said input data at least an intrinsic convolution layer, including the steps of applying a patch operator to extract a local representation of input data around a point on the geometric domain and outputting the correlation of a patch resulting from the extraction with a plurality of templates,

the method further comprising applying at least one of the following layers:

a linear layer or fully connected layer, including outputting a weighted linear combination of input data;

a non-linear layer, including applying a non-linear function to input data;

a spatial pooling layer, including;

determining a subset of points on the geometric domain;

for each point of said subset, determining the neighbours on the geometric domain; and

computing an averaging operation on input data over neighbours for all the points of said subset; and

a covariance layer, including computing a covariance matrix of input data over all the points of the geometric domain;

wherein each layer has input data and output data and output data of one layer are given as input data to another layer.

2. The method according to claim 1, wherein two or more of said layers are applied in sequence, and the output data of one layer in the sequence is given as input data to a subsequent layer in the sequence.

3. The method according to claim 1, wherein the geometric domain is one of the following:

a manifold;

a parametric surface;

an implicit surface;

a mesh;

a point cloud;

or

a graph.

4. The method according to claim 1, wherein parameters of the applied layer are determined by minimizing a cost function by means of an optimization procedure.

5. The method according to claim 4, wherein a plurality of said cost functions are defined, and wherein each of said cost functions is associated to one or more application for which feature extraction is carried out.

6. The method according to claim 4, wherein the input into the optimization procedure is a training set comprising:

a positive set of pairs of points on one or more geometric domains; and

negative set of pairs points on one or more geometric domains,

wherein two identical copies of the hierarchical system configured with the same parameters are fed with pairs of points from said positive and negative sets, and

wherein the optimization procedure tries to minimize the distance between the outputs corresponding to positive pairs and maximize the distance between the outputs corresponding to negative pairs.

7. The method according to claim 1, wherein the patch operator inputs input data on the geometric domain and said point on said domain, and outputs the local representation of said input data around said point, wherein the local representation is one or more of the following:

input data represented in a local intrinsic polar system of coordinates;

input data transformed by a windowed Fourier transform; and

input data weighted by anisotropic diffusion kernels.

8. The method according to claim 7, wherein the patch operator outputs said local representation of input data in the local intrinsic polar system of coordinates, and wherein an origin of angular coordinates of the local intrinsic polar system of coordinates is provided as side information extracted from the geometric domain or the input data.

9. The method according to claim 8, wherein the geometric domain is a surface and the side information used to determine the origin of the angular coordinate of the local intrinsic polar system of coordinates at each point on the surface is a principle curvature direction at said point.

10. The method according to claim 8, wherein the side information used to determine the origin of the angular coordinate of the local intrinsic polar system of coordinates at each point is a direction of a minimal or maximal absolute change of the input data at said point.

11. The method according to claim 7, wherein the patch operator outputs said local representation of input data in the local intrinsic polar system of coordinates, and the Fourier transform is applied with respect to angular coordinates, followed by an absolute value operation.

12. The method according to claim 7, wherein the representation of input data in the local polar system of coordinates around the point on the geometric domain further comprises the steps of:

computing an intrinsic distance from said point to all the other points on the geometric domain;

computing level sets of said intrinsic distance at a plurality of levels;

splitting a full angle at said point into a plurality of angular directions; and

shooting rays emanating from said point along said directions perpendicular to said level sets.

13. The method according to claim 12, wherein said intrinsic distance is one of the following or an approximation thereof:

geodesic distance;

diffusion distance;

commute time distance;

or

biharmonic distance.

14. The method according to claim 12, wherein the representation of input data further comprises the steps of

computing weights localized around level sets and rays;

and

computing weighted averages of input data with each of said weights.

15. The method according to claim 7, wherein computing the windowed Fourier transform of input data further comprises:

computing localized modulated atoms; and

computing inner products of input data with said atoms.

16. The method according to claim 15, wherein localized modulated atoms are heat kernels multiplied by Laplacian eigenfunctions.

17. The method according to claim 16, wherein the heat kernels are anisotropic.

18. The method according to claim 7, wherein the computation of local representation of input data around a point on the geometric domain further comprises the steps of

computing a plurality of directed anisotropic heat kernels at said point, corresponding to a plurality of anisotropy constants and directions;

and

computing weighted averages of input data with said directed anisotropic heat kernels.

19. The method according to claim 1, wherein the intrinsic convolution layer includes applying said patch operator to extract a local representation of input data in a local intrinsic polar system of coordinates around a point on the geometric domain, and outputting the correlation of a patch resulting from the extraction with a plurality of templates, the computation of said correlation further comprising the steps of:

rotating each template along angular coordinates;

computing the correlation of the patch with the rotated template; and

taking a maximum operation over all the rotations.

20. The method according to claim 1, wherein the averaging operation includes one or more of the following:

an arithmetic average;

a maximum operation;

an average weighted by weights dependent on a distance between points; and

an average weighted by weights dependent on local volume elements.

21. A system for extracting hierarchical features from input data defined on a geometric domain, the system comprising:

a processor; and

a computer-readable medium having instructions stored thereon that, when executed by the processor, perform a method including applying on said input data at least an intrinsic convolution layer, wherein the program instructions are configured to apply a patch operator, to extract a local representation of input data around a point on the geometric domain, and to output the correlation of a patch resulting from the extraction with a plurality of templates,

the program instructions being further configured for applying one or more of the following layers on said input data;

an intrinsic convolution layer, to apply a patch operator for extracting a local representation of the input data around a point on the geometric domain and to correlate a patch. resulting from the extraction, with a plurality of templates;

a linear layer or fully connected layer, to take said input data in input and to give in output a weighted linear combination;

a non-linear layer, to take said input data in input into a non-linear function;

a spatial pooling layer, to determine neighbours of a point on the geometric domain and to compute an averaging operation over the neighbours; and

a covariance layer, to compute a covariance matrix of said input data in input over all the points of the geometric domain.

22. The system according to claim 21, wherein the geometric domain is one of the following:

a manifold;

a parametric surface;

a mesh;

a point cloud;

or

a graph.

23. The system according to claim 21, including an optimization procedure for minimizing a cost function to determine parameters of the layer to be applied.

24. The system according to claim 23, which stores a plurality of said cost functions, wherein each of said cost functions is associated to one or more application for which features may be extracted.

25. The system according to claim 24, including a training set as an input for the optimization procedure, comprising:

a positive set of pairs of points on one or more geometric domains; and

negative set of pairs points on one or more geometric domains,

wherein two identical copies of the hierarchical system configured with the same parameters are fed with pairs of points from said positive and negative sets, and

wherein the optimization procedure tries to minimize the distance between the outputs corresponding to positive pairs and maximize the distance between the outputs corresponding to negative pairs.

26. The system according to claim 21, wherein the patch operator is one or more of the following:

a local polar system of coordinates;

a windowed Fourier transform; and

an anisotropic diffusion kernels.

27. The system according to claim 26, wherein the patch operator is configured to output said local representation of input data in the local intrinsic polar system of coordinates, and to provide an origin of angular coordinates of the local intrinsic polar system of coordinates as side information extracted from the geometric domain or the input data.

28. The system according to claim 27, configured to take a surface as a geometric domain and to a take a principle curvature direction at said point as the side information used to determine the origin of the angular coordinate of the local intrinsic polar system of coordinates at each point on the surface.

29. The system according to claim 27, configured to take a direction of a minimal or maximal absolute change of the input data at said point as the side information used to determine the origin of the angular coordinate of the local intrinsic polar system of coordinates at each point.

30. The system according to claim 26, wherein the patch operator is configured to output said local representation of input data in the local intrinsic polar system of coordinates, and to apply the Fourier transform with respect to angular coordinates, followed by an absolute value operation.

31. The system according to claim 26, wherein said program instructions are further configured to compute the windowed Fourier transform of input data by:

computing localized modulated atoms; and

computing inner products of input data with said atoms.

32. The system according to claim 31, wherein said localized modulated atoms are heat kernels multiplied by Laplacian eigenfunctions.

33. The system according to claim 32, wherein the heat kernels are anisotropic.

34. The system according to claim 26, wherein said program instructions are further configured for the computation of local representation of input data around a point on geometric domain by:

computing a plurality of directed anisotropic heat kernels at said point, corresponding to a plurality of anisotropy constants and directions; and

computing weighted averages of input data with said directed anisotropic heat kernels.

35. The system according to claim 21, wherein said program instructions are configured to apply said patch operator to extract a local representation of input data in a local intrinsic polar system of coordinates around a point on the geometric domain, and to output the correlation of a patch resulting from the extraction with a plurality of templates, and is further configured to:

rotate each template along angular coordinates;

compute the correlation of the patch with the rotated template; and

take a maximum operation over all the rotations.

36. The system according to claim 21, wherein said program instructions are further configured to:

compute an intrinsic distance from said point to all the other points on the geometric domain;

compute level sets of said intrinsic distance at a plurality of levels;

split a full angle at said point into a plurality of angular directions; and

shoot rays emanating from said point along said directions perpendicular to said level sets.

37. The system according to claim 36, wherein said intrinsic distance is one of the following or an approximation thereof:

geodesic distance;

diffusion distance;

commute time distance;

or

biharmonic distance.

38. The system according to claim 36, wherein said program instructions are further configured to:

compute weights localized around level sets and rays; and

compute weighted averages of input data with each of said weights.

39. The system according to claim 21, wherein the averaging operation includes one or more of the following:

an arithmetic average;

a maximum operation;

an average weighted by weights dependent on a distance between points; and

an average weighted by weights dependent on local volume elements.

40. The system according to claim 21, further comprising program instructions for determining similarity between two geometric objects or for determining correspondence between objects from a class of geometric objects and a reference object.