System and a method for learning features on geometric domains

• US 10,210,430 B2
• Filed: 11/22/2017
• Issued: 02/19/2019
• Est. Priority Date: 01/26/2016
• Status: Active Grant

• Current Assignee: Fabula AI Limited (X Holdings Corp.)
• Original Assignee: Fabula AI Limited (X Holdings Corp.)
• Inventors: Bronstein, Michael, Boscaini, Davide, Monti, Federico
• Primary Examiner(s): Mushambo, Martin
• Application Number:
  US15/820,909
• Publication Number:
  US 20180096229A1
• Time in Patent Office: 454 Days
• Field of Search: None
• CPC Class Codes: G06F 17/14 Fourier, Walsh or analogous domain transformations , e.g. Laplace, Hilbert, Karhunen-Loeve, transforms for correlation function computation G06F17/156; spectrum analysers G01R23/16
• 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: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/2413 based on distances to training or reference patterns
• CPC Class Codes: G06N 3/04 Architecture, e.g. interconnection topology
• CPC Class Codes: G06N 3/045 Combinations of networks
• CPC Class Codes: G06N 3/048 Activation functions
• CPC Class Codes: G06N 3/08 Learning methods
• CPC Class Codes: G06N 3/105 Shells for specifying net layout
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: G06V 10/426 Graphical representations
• CPC Class Codes: G06V 10/454 Integrating the filters into a hierarchical structure, e.g. convolutional neural networks [CNN]
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• 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 10/82 using neural networks
• 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 computer-system-implemented method for extracting hierarchical features from data defined on a geometric domain, comprising applying on said data at least an intrinsic convolution layer, the data being stored on a memory of a computer system, the method including the steps of:

applying, by a processor of the computer system, a patch operator to extract a local representation of the input data around a point on the geometric domain and outputting a correlation of said local representation resulting from the extraction with a plurality of templates;

defining, by the processor, a local system of multi-dimensional pseudo-coordinates around a point on the geometric domain;

computing, by the processor, a plurality of weighting functions acting on said pseudo coordinates;

storing said weighting functions on the memory of the computer system; and

applying, by the processor, said weighting functions to define said patch operator, thereby improving the ability of the computer system to apply a deep learning method to said data.

2. 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;

an undirected weighted or unweighted graph;

a directed weighted or unweighted graph.

3. The method according to claim 1, wherein the multi-dimensional pseudo-coordinates have one or more dimensions and comprise one or more of the following:

geodesic coordinates;

diffusion coordinates;

intrinsic polar coordinates;

vertex degree.

4. The method according to claim 1, wherein said weighting functions are fixed functions.

5. The method according to claim 1, wherein said weighting functions are parametric functions.

6. The method according to claim 5, wherein said weighting functions are sums of scaled trigonometric functions, and said parameters comprise the scale factors of the trigonometric functions.

7. The method according to claim 5, wherein said weighting functions are sums of scaled Gaussian kernels, and where said parameters comprise:

the scale factors of the Gaussian kernels;

the mean vectors of the Gaussian kernels, or a subset of elements thereof;

the covariance matrices of the Gaussian kernels, or a subset of elements thereof.

8. The method according to claim 7, wherein the covariance matrices of the Gaussian kernels are diagonal, and the subset of their elements comprises the diagonal elements.

9. The method according to claim 1, wherein said weighting functions are one of the following:

Gaussian kernels;

spline kernels;

trigonometric functions;

orthogonal basis functions.

10. The method according to claim 1, wherein the points of the geometric domain are in a grid, and wherein said step of applying the intrinsic convolutional layer on input data comprises applying a sliding window operation.

11. The method according to claim 10, wherein the sliding window operation further comprises:

determining the center point of the window;

extracting a block of points around said center point of the window;

defining said multi-dimensional pseudo-coordinates for each point of said block of points;

computing said plurality of weighting functions acting on said multi-dimensional pseudo-coordinates;

applying said weighting functions to define said patch operator extracting a local representation of the input data at the points of said block of points;

computing the correlation of said patch resulting from the extraction with a plurality of templates; and

moving the window to a next adjacent location.

12. The method according to claim 1, wherein the geometric domain is a directed graph, and further comprising the steps of:

inputting a plurality of graph motifs;

for each input graph motif

computing a new undirected weighted graph wherein the vertices are those of the input graph, and each edge is weighted by the occurrence of the graph motif;

computing said multi-dimensional pseudo-coordinates around each vertex of said undirected weighted graph;

computing said plurality of weighting functions acting on said pseudo -coordinates;

applying the weighting functions to define said patch operator extracting said local representation of the input data around said point on the geometric domain; and

outputting the correlation of said patch resulting from the extraction with said plurality of templates.

13. The method according to claim 12, wherein the multi-dimensional pseudo-coordinates computed for each undirected weighted graph comprise at least one of the following:

vertex degree;

geodesic distance from a vertex;

diffusion distance from a vertex.

14. The method according to claim 12, wherein the weighting functions are diffusion kernels computed on the weighted undirected graphs for all the input graph motifs.

15. The method according to claim 14, wherein the diffusion kernels comprise heat kernels with a plurality of time scales.

16. The method according to claim 15, wherein the diffusion kernels are anisotropic diffusion kernels.

17. The computer implemented method according to claim 1 for extracting hierarchical features from data defined on a geometric domain, wherein said data are defined and stored in a storage of a computer, said computer including means for applying on said data at least an intrinsic convolution layer, said means executing 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.

18. A computer-system-implemented method for extracting hierarchical features from data defined on a geometric domain, comprising applying on said data at least an intrinsic convolution layer, the data being stored on a memory of a computer system, the method including the steps of:

applying, by a processor of the computer system, a patch operator to extract a local representation of the input data around a point on the geometric domain and outputting a correlation of said local representation resulting from the extraction with a plurality of templates; and

further applying at least one of the following layers;

a linear 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 aggregation operation on input data over the neighbours for all the points of said subset;

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

a fully connected layer, including outputting a weighted linear combination of input data at all the points of the geometric domain,

wherein each layer has input data and output data stored on the memory of the computer system, and output data of one layer are given as input data to another layer, thereby improving the ability of the computer system to apply a deep learning method to said data.

19. The method according to claim 18, wherein said spatial pooling layer comprises aggregating of input data over the whole domain.

20. The method according to claim 18, wherein said aggregation operation of input data comprises one of the following:

maximum computation;

average computation;

weighted average computation;

average of squares computation.

21. The method according to claim 18, 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.

22. The method according to claim 18, wherein more than one of said layers is applied and wherein parameters of the applied layers comprise one or more of the following:

weights of the linear layers;

templates of the intrinsic convolutional layers;

parameters of the weighting functions used to compute the patch operators in the intrinsic convolutional layer.

23. The method according to claim 22, wherein parameters of the applied layers are determined by minimizing a cost function by means of an optimization procedure.

24. The method according to claim 23, 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.

25. The method according to claim 23, 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

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

and 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. A computer-system-implemented. method for extracting hierarchical features from data defined on a geometric domain, comprising applying on said data at least an intrinsic convolution layer, the data being stored on a memory of a computer system, the method including the steps of:

applying, by a processor of the computer system, a patch operator to extract a local representation of the input data around a point on the geometric domain and outputting a correlation of said local representation resulting from the extraction with a plurality of templates;

wherein the patch operator inputs data on geometric domain and said point on said domain, and outputs the local representation of said data around said point, thereby improving the ability of the computer system to apply a deep learning method to said data,

wherein the local representation is one or more of the following;

data represented in a local intrinsic polar system of coordinates;

data transformed by a windowed Fourier transform;

data weighted by anisotropic diffusion kernels.

27. The method according to claim 26, 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 data.

28. The method according to claim 27, 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.

29. The method according to claim 27, 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 data at said point.

30. The method according to claim 26, 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.

31. The method according to claim 26, wherein the computation of said correlation between said patch and said plurality of templates further comprises the steps of:

rotating each template along angular coordinates;

computing the correlation of the patch with the rotated template;

taking a maximum operation over all the rotations.

32. The method according to claim 26, 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;

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

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

geodesic distance;

diffusion distance;

commute time distance;

biharmonic distance.

34. The method according to claim 32, wherein the representation of input data further comprises the steps of:

computing weights localized around level sets and rays;

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

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

computing localized modulated atoms;

computing inner products of data with said atoms.

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

37. The method according to claim 36, wherein the heat kernels are anisotropic.

38. The method according to claim 26, wherein the computation of local representation of input data around a point on 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;

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

39. A computer-system-implemented method for extracting hierarchical features from data defined on a geometric domain. comprising applying on said data at least an intrinsic convolution layer, the data being stored on a memory of a computer system, the method including the steps of:

applying, by a processor of the computer system, a patch operator to extract a local representation of the input data around a point on the geometric domain and outputting a correlation of said local representation resulting from the extraction with a plurality of templates;

including extracting hierarchical features from data defined on another geometric domain, applying on data defined on said another geometric domain at least the intrinsic convolution layer, including the steps of;

applying a patch operator to extract a local representation of further input data around a point on the another geometric domain and outputting the correlation of a patch resulting from the extraction of the local representation of the further input data with said plurality of templates, thereby improving the ability of the computer system to apply a deep learning method to said data,

wherein data defined on the geometric domain are associated to a first geometric object and said data are defined on the additional geometric domain are associated to a second geometric object, and

wherein a similarity of the first object to the second object is measured based on the hierarchical features extracted from data defined on the geometric object and the hierarchical features extracted from data defined on said another geometric object.

40. The method according to claim 39, wherein said similarity measure is used for a shape retrieval application of the first object,

wherein data defined on a plurality of geometric domains are provided as a collection of second objects,

a similarity between each second object of the collection and the first object is measured,

an object of the collection having the highest measure of similarity is returned as an object retrieved in the first object.

41. The method according to claim 39, wherein the geometric domain is a graph modelling a social network wherein the first object and second object are nodes of the graph corresponding to members of the social network, and wherein said similarity measure is a measure of similarity between said members of the social network, and wherein the measure of similarity is used to estimate a behaviour of one of the member in the social network based on a known behaviour of the other member of the social network with which the similarity has been measured, wherein said estimated behaviour is considered to be the known behaviour for a value of said measured similarity which is above a predetermined threshold.

42. A computer-system-implemented method for extracting hierarchical features from data defined on a geometric domain comprising applying on said data at least an intrinsic convolution layer, the data being stored on a memory of a computer system, the method including the steps of:

applying, by a processor of the computer system, a patch operator to extract a local representation of the input data around a point on the geometric domain and outputting a correlation of said local representation resulting from the extraction with a plurality of templates, thereby improving the ability of the computer system to apply a deep learning method to said data;

wherein said extracted hierarchical features are used for determining correspondences between objects from a class of geometric objects, provided as a plurality of data defined on a corresponding plurality of geometric domains, and an first object associated to said data defined on the geometric domain.

43. The method according to claim 42, wherein said correspondences between said class of geometric objects and said first object are used to automatically transfer a texture of said first object to said class of objects.

44. The method according to claim 42, wherein said correspondences between said class of geometric objects and said first object are used to automatically transfer an animation of said reference object to said class of objects.

45. A computer system for extracting hierarchical features from data defined on a geometric domain, comprising a memory and a processor for applying on said data at least an intrinsic convolution layer, where said computer system is configured to:

apply, by the processor, a patch operator for extracting a local representation of the input data around a point on the geometric domain and to return as output a correlation of said local representation resulting from the extraction with a plurality of templates;

define, by the processor, a local system of multi-dimensional pseudo-coordinates around a point on the geometric domain;

compute, by the processor, a plurality of weighting functions acting on said pseudo -coordinates;

store said weighting functions on the memory; and

apply, by the processor, said weighting functions to define the patch operator, thereby improving the ability of the computer system to apply a deep learning method to said data.

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

a manifold;

a parametric surface;

an implicit surface;

a mesh;

a point cloud;

an undirected weighted or unweighted graph;

a directed weighted or unweighted graph.

47. The system according to claim 45, wherein the multi-dimensional pseudo-coordinates have one or more dimensions and comprise one or more of the following:

geodesic coordinates;

diffusion coordinates;

intrinsic polar coordinates;

vertex degree.

48. The system according to claim 45, wherein said weighting functions are fixed functions.

49. The system according to claim 45, wherein said weighting functions are parametric functions.

50. The system according to claim 49, wherein said weighting functions are sums of scaled trigonometric functions, and said parameters comprise the scale factors of the trigonometric functions.

51. The system according to claim 49, wherein said weighting functions are sums of scaled Gaussian kernels, and wherein said parameters comprise:

the scale factors of the Gaussian kernels;

the mean vectors of the Gaussian kernels, or a subset of elements thereof;

the covariance matrices of the Gaussian kernels, or a subset of elements thereof.

52. The system according to claim 51, wherein the covariance matrices of the Gaussian kernels are diagonal, and the subset of their elements comprises the diagonal elements.

53. The system according to claim 45, wherein said weighting functions are one of the following:

Gaussian kernels;

spline kernels;

trigonometric functions;

orthogonal basis functions.

54. The system according to claim 45, wherein the points of the geometric domain are in a grid, and wherein said means for applying the intrinsic convolutional layer on input data are configured to apply a sliding window operation.

55. The system according to claim 54, wherein said means for applying the intrinsic convolutional layer are further configured to:

determining the center point of the window;

extracting a block of points around said center point of the window;

defining said multi-dimensional pseudo-coordinates for each point of said block of points;

said plurality of weighting functions acting on said multi-dimensional pseudo -coordinates;

said weighting functions to define said patch operator extracting a local representation of the input data at the points of said block of points;

computing the correlation of said patch resulting from the extraction with a plurality of templates; and

moving the window to a next adjacent location.

56. The system according to claim 45, wherein the geometric domain is a directed graph and wherein means to input graph motifs are configured to:

input a plurality of graph motifs;

for each input graph motif

computing a new undirected weighted graph wherein the vertices are those of the input graph, and each edge is weighted by the occurrence of the graph motif;

computing said multi-dimensional pseudo-coordinates around each vertex of said undirected weighted graph;

computing said plurality of weighting functions acting on said pseudo -coordinates;

applying the weighting functions to define said patch operator extracting said local representation of the input data around said point on the geometric domain; and

outputting the correlation of said patch resulting from the extraction with said plurality of templates.

57. The system according to claim 56, wherein the multi-dimensional pseudo-coordinates of each undirected weighted graph comprise at least one of the following:

vertex degree;

geodesic distance from a vertex;

diffusion distance from a vertex.

58. The system according to claim 56, wherein the weighting functions are diffusion kernels and wherein said means to define the operator are configured to compute the weighted undirected graphs for all the input graph motifs.

59. The system according to claim 58, wherein the diffusion kernels comprise heat kernels with a plurality of time scales.

60. The system according to claim 59, wherein the diffusion kernels are anisotropic diffusion kernels.

61. A computer system for extracting hierarchical features from data defined on a geometric domain, comprising a memory and a processor for applying on said data at least an intrinsic convolution layer, where said computer system is configured to:

apply, by the processor, a patch operator for extracting a local representation of the input data around a point on the geometric domain and to return as output a correlation of said local representation resulting from the extraction with a plurality or templates;

apply at least another layer among the following layers;

a linear 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, wherein;

a subset of points on the geometric domain are determined;

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

an aggregation operation on input data over the neighbours for all the points of said subset is computed;

a covariance layer, wherein a covariance matrix of input data over all the points of the geometric domain is computed;

a fully connected layer, having as output a weighted linear combination of input data at all the points of the geometric domain,

wherein each layer has input data and output data stored on the memory of the computer system, and said system comprehends means that are configured to provide as input data to a layer the output data of another layer, thereby improving the ability of the computer system to apply a deep learning method to said data.

62. The system according to claim 61, wherein said spatial pooling layer comprises an aggregation of input data over the whole domain.

63. The system according to claim 61, wherein said means to apply the spatial pooling layer are configured to process said aggregation of input data by means of one of the following computation:

maximum computation;

average computation;

weighted average computation;

average of squares computation.

64. The system according to claim 61, wherein said means for applying at least another layer are configured to apply at least another layer in sequence, providing the output data of one layer in the sequence as input data to a subsequent layer in the sequence.

65. The system according to claim 61, wherein said means for applying the intrinsic convolutional layer and said means for applying at least another layer are configured to set one or more of the following parameters to the applied layers:

weights of the linear layers;

templates of the intrinsic convolutional layers;

parameters of the weighting functions used to compute the patch operators in the intrinsic convolutional layer.

66. The system according to claim 65, wherein said means for applying the intrinsic convolutional layer and said means for applying at least another layer are configured to determine parameters of the applied layers by minimizing a cost function by means of an optimization procedure.

67. The system according to claim 66, 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 may be carried out by the system.

68. The system according to claim 66, 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

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

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 is configured to minimize the distance between the outputs corresponding to positive pairs and maximize the distance between the outputs corresponding to negative pairs.

69. A computer system for extracting hierarchical features from data defined on a geometric domain, comprising a memory and a processor for applying on said data at least an intrinsic convolution layer, said data being stored on the memory of the computer system, where said computer system is configured to:

apply, by the processor, a patch operator for extracting a local representation of the input data around a point on the geometric domain and to return as output a correlation of said local representation resulting from the extraction with a plurality of templates;

wherein the patch operator is configured to input data on geometric domain and said point on said domain, and to output the local representation of said data around said point, thereby improving the ability of the computer system to apply a deep learning method to said data,

wherein the local representation is one or more of the following;

data represented in a local intrinsic polar system of coordinates;

data transformed by a windowed Fourier transform;

data weighted by anisotropic diffusion kernels.

70. The system according to claim 69, wherein the patch operator is configured to output said local representation of input data in the local intrinsic polar system of coordinates, and wherein 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 data.

71. The system according to claim 70, wherein the geometric domain is a surface and the side information for determining 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.

72. The system according to claim 70, wherein the side information for determining 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 data at said point.

73. The system according to claim 69, 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.

74. The system according to claim 69, configured to compute the correlation between said patch and said plurality of templates by:

rotating each template along angular coordinates;

computing the correlation of the patch with the rotated template;

taking a maximum operation over all the rotations.

75. The system according to claim 69, wherein the patch operator if further configured to represent input data in the local polar system of coordinates around the point on the geometric domain by:

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;

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

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

geodesic distance;

diffusion distance;

commute time distance;

biharmonic distance.

77. The system according to claim 75, wherein the patch operator if further configured to represent input data by:

computing weights localized around level sets and rays;

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

78. The system according to claim 69, wherein the patch operator is further configured to compute the windowed Fourier transform of input data by:

computing localized modulated atoms;

computing inner products of data with said atoms.

79. The system according to claim 78, wherein localized modulated atoms are heat kernels multiplied by Laplacian eigenfunctions.

80. The system according to claim 79, wherein the heat kernels are anisotropic.

81. The system according to claim 69, further configured to compute the 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;

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