METHOD FOR GENERATING A SET OF SHAPE DESCRIPTORS FOR A SET OF TWO OR THREE DIMENSIONAL GEOMETRIC SHAPES

Abstract

In the invention for generating a set of shape descriptors for a set of two or three dimensional geometric shapes in order to arrive at an unified efficient low-dimensional representation of the complete set of shapes to enable memory and disk efficient storage, indexing, referencing, and making the complete set available for further processing, at first a set of N feature locations having a distance from the shapes is read. Further, a set of M wave numbers is read and a parameter controlling degree of locality of the features. Then, for each shape s in the set of shapes {S.sub.s, s=1, . . . , N.sub.s} and for each of the N feature locations and M wave numbers a feature descriptor is calculated according to

[00001]$f_s\left(n,m\right)={\left({.Math.{\stackrel{.fwdarw.}{R}}_n.Math.}_{}\right)}^{}.Math.e^{-{\mathrm{ik}}_m.Math.R_n}.Math.C.Math.{}_{\mathrm{shape}.Math..Math.s}.Math.d^3.Math.\stackrel{.fwdarw.}{s}.Math.\frac{e^{{\mathrm{ik}}_m.Math.{.Math.\stackrel{.fwdarw.}{s}-{\stackrel{.fwdarw.}{R}}_n.Math.}_2}}{{\left({.Math.\stackrel{.fwdarw.}{s}-{\stackrel{.fwdarw.}{R}}_n.Math.}_{}\right)}^{}},$

where the integral is summing all contributions from each point of shape s. The calculated feature descriptors are then assigned to elements of an M.Math.N dimensional vector as the shape descriptor for shape s

{right arrow over (F)}.sub.s=(f.sub.s(n=1,m=1),f.sub.s(n=1,m=2), . . . ,f.sub.s(n=N,m=M)).sup.T

and the complete set of shape descriptors {{right arrow over (F)}.sub.s, s=1, . . . , N.sub.s} of the set of shapes is output.

Claims

1. A method for generating a set of shape descriptors {{right arrow over (F)}.sub.s, s=1, . . . , N.sub.s} for a set of two or three dimensional geometric shapes in order to arrive at an unified efficient low dimensional representation of the complete set of shapes to enable memory and disk efficient storage, indexing, referencing, and making the complete set available for further processing, comprising the following steps: reading a set {{right arrow over (R)}.sub.n} of N feature locations having a distance from the shape, where {right arrow over (R)}.sub.n is the position vector of the feature location having the length R.sub.n=|{right arrow over (R)}.sub.n| and n=1, . . . , N reading a set {k.sub.m} of M wave numbers, where m=1, . . . , M reading , which is a parameter controlling degree of locality of the features for each shape s calculating for each of the N feature locations {right arrow over (R)}.sub.n and M wave numbers k.sub.m a feature descriptor f.sub.s(n, m) according to the rule $f_s\left(n,m\right)={\left({.Math.{\stackrel{.fwdarw.}{R}}_n.Math.}_{}\right)}^{}.Math.e^{-{\mathrm{ik}}_m.Math.R_n}.Math.C.Math.{}_{\mathrm{shape}.Math..Math.s}.Math.d^3.Math.\stackrel{.fwdarw.}{s}.Math.\frac{e^{{\mathrm{ik}}_m.Math.{.Math.\stackrel{.fwdarw.}{s}-{\stackrel{.fwdarw.}{R}}_n.Math.}_2}}{{\left({.Math.\stackrel{.fwdarw.}{s}-{\stackrel{.fwdarw.}{R}}_n.Math.}_{}\right)}^{}}$ where the integral is summing all contributions from each point of the shape s, {right arrow over (s)} is a position vector of points of the shape, i is the imaginary unit, {right arrow over (x)}.sub.=[.sub.i(x.sub.i).sup.].sup.1/ is the L.sub. norm of the vector {right arrow over (x)}, and C is a normalization constant which can be chosen either C=1 or to normalize the feature to the absolute volume or surface area of the shape: C=1/.sub.shape s d.sup.3{right arrow over (s)}. assigning the calculated feature descriptors f.sub.s(n, m) to an M.Math.N dimensional vector of features as the shape descriptor {right arrow over (F)}.sub.s according to
{right arrow over (F)}.sub.s=(f.sub.s(n=1,m=1),f.sub.s(n=1,m=2), . . . ,f.sub.s(n=N,m=M)).sup.T and outputting the set of shape descriptors {{right arrow over (F)}.sub.s, s=1, . . . , N.sub.s} for further processing.

2. The method described in claim 1, wherein the shape data is provided as a volume or surface mesh and for each feature descriptor the integral is calculated according to $C.Math.{}_{\mathrm{shape}.Math..Math.s}.Math.d^3.Math.\stackrel{.fwdarw.}{s}.Math.\frac{e^{{\mathrm{ik}}_m.Math.{.Math.\stackrel{.fwdarw.}{s}-{\stackrel{.fwdarw.}{R}}_n.Math.}_2}}{{\left({.Math.\stackrel{.fwdarw.}{s}-{\stackrel{.fwdarw.}{R}}_n.Math.}_{}\right)}^{}}.Math.C.Math.\underset{\mathrm{mesh}.Math..Math.\mathrm{cells}.Math..Math.c.Math..Math.\mathrm{of}.Math..Math.s}{.Math.}.Math.A_c.Math.\frac{e^{{\mathrm{ik}}_m.Math.{.Math.\stackrel{.fwdarw.}{s}-{\stackrel{.fwdarw.}{R}}_n.Math.}_2}}{{\left({.Math.{\stackrel{.fwdarw.}{s}}_c-{\stackrel{.fwdarw.}{R}}_n.Math.}_{}\right)}^{}}$ wherein c are the mesh cells c of shape s, {right arrow over (s)}.sub.c is a center-of-mass coordinate of the respective cell c, A.sub.c is the volume or area of the respective mesh cell c, and C is a normalization constant which can be chosen either C=1 or to normalize the feature to the absolute volume or surface area of the shape: C=1/.sub.mesh cells c of s A.sub.c.

3. The method according to claim 1, wherein the positions of the feature locations lie on a surface around the shapes with the feature locations being calculated by a deterministic algorithm to follow a desired pattern or randomly, where the positions of the feature locations on the surface are determined by a randomized sampling technique in order to follow a desired distribution.

4. The method according to claim 1, where the M wave numbers are chosen to range from k.sub.min to k.sub.max and the spacing between the values is constant, linearly increasing, linearly decreasing, exponentially increasing, exponentially decreasing or explicitly given by the user.

5. The method according to claim 4, wherein random noise of a defined strength can also be added to the values of the wave numbers.

6. The method according to claim 1, where a dimensionality reduction or embedding technique is used to transform the complete set of shape descriptors {{right arrow over (F)}.sub.s} and possibly reduce the dimensionality of each shape descriptor {right arrow over (F)}.sub.s in the set of shape descriptors.

7. The method according to claim 1, wherein the feature locations or the values for the wave numbers are determined by an optimization algorithm.

8. The method according to claim 1, wherein a pose-normalization procedure is applied to each of a plurality of shape descriptors {{right arrow over (F)}.sub.s, s=1, . . . , N.sub.s}.

9. The method according to claim 1, wherein a classification algorithm is run based on the calculated set of shape descriptors {{right arrow over (F)}.sub.s, s=1, . . . , N.sub.s}.

10. The method according to claim 1, wherein shape retrieval is performed based on the set of shape descriptors {{right arrow over (F)}.sub.s: s=1, . . . , N.sub.s}.

11. The method according to claim 1, wherein a performance prediction process is performed which could be integrated into a surrogate-assisted shape optimization process based on the calculated set of shape descriptors {{right arrow over (F)}.sub.s, s=1, . . . , N.sub.s}.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0028] Explanations on an embodiment of the present invention will now be given with respect to the annexed drawings in which

[0029] FIG. 1 illustrates feature locations arranged on a surface enclosing one respective shape of the set of shape to be represented, and

[0030] FIG. 2 is a flowchart in which the main method steps according to the invention are illustrated.

DETAILED DESCRIPTION

[0031] For a given set of shapes {S.sub.s, s=1, . . . , N.sub.s} the set of shape descriptors {{right arrow over (F)}.sub.s, s=1, . . . , N.sub.s} (i.e. the set of diffraction feature vectors) can be calculated in the following way which is explained with reference to FIG. 1. First, N position vectors {right arrow over (R)}.sub.n, where n={1, . . . , N} are chosen some distance away from the shapes {S.sub.s} and distributed all around the shapes. The position vectors {right arrow over (R)}.sub.n point to feature locations. As an example, FIG. 1 illustrates that the feature locations are chosen to all lie on a sphere where the length of {right arrow over (R)}.sub.n is fixed for all n, |{right arrow over (R)}.sub.n|=5L and where L is some characteristic length scale of some shape S.sub.s of the set of shapes, i.e. its maximum linear dimension. The distribution of the feature locations on the sphere could be chosen accordingly by using a regular grid in the azimuthal and polar angles or to be a Fibonacci lattice.

[0032] Then, a set of wave numbers is determined by the engineer, for example

[00006]$\left\{k_m=\frac{0.1}{M}.Math.m^2.Math.\frac{2.Math.}{L}.Math.\text{:}.Math..Math.m=1,\mathrm{.Math.}.Math.,M\right\}$

where L is the characteristic length scale of the set of shapes {S.sub.s} determined above. Now, the complete set of diffraction feature shape descriptors {{right arrow over (F)}.sub.s} can be generated where each individual shape descriptor

{right arrow over (F)}.sub.s=(f.sub.s(1,1),f.sub.s(1,2), . . . ,f.sub.s(1,M),f.sub.s(2,1) . . . ,f.sub.s(N,M)).sup.T

of the shape S.sub.s is composed of feature descriptor f.sub.s(n, m) which are calculated according to the formula

[00007]$f_s\left(n,m\right)={\left(R_n\right)}^2.Math.e^{-{\mathrm{ik}}_m.Math.R_n}.Math.{}_{\mathrm{shape}.Math..Math.s}.Math.d^3.Math.\stackrel{.fwdarw.}{s}.Math.\frac{e^{{\mathrm{ik}}_m.Math..Math.\stackrel{.fwdarw.}{s}-{\stackrel{.fwdarw.}{R}}_n.Math.}}{{.Math.\stackrel{.fwdarw.}{s}-{\stackrel{.fwdarw.}{R}}_n.Math.}^2}$

where R.sub.n=|{right arrow over (R)}.sub.n|=5L is the length (L2 norm) of the position vector of the feature location, {right arrow over (s)} is a position vector of the points on the shape S.sub.s and the integral is summing all contributions from each point of the shape S.sub.s. i is the imaginary unit and k.sub.m the wave number. The pre-factor (R.sub.n).sup.e.sup.ik.sup.m.sup.R.sup.n is included to factor out the trivial far-field dependence of the features and its exponent as well as the exponent of the denominator in the integral is set to 2 in the example in order to have a slightly larger bias toward local features as compared to choosing an exponent of 1 (which is the value for the wave kernel of physical light diffraction patterns). In order to adapt the degree of locality this exponent may be set by an engineer.

[0033] In typical engineering applications where the shapes are usually evaluated with respect to some performance using simulations such as computational fluid dynamics (CFD) or computations structural dynamics (CSD), the shape data is naturally provided as a volume or surface mesh. In such a case the integral over the shape can be represented as a sum over all mesh cells c and the contribution of each mesh cell c is calculated using the center-of-mass coordinate of each cell, {right arrow over (s)}.sub.c, and the volume- or area-weighted sum is taken over all mesh cells, i.e.,

[00008]$f_s\left(n,m\right)={\left(R_n\right)}^2.Math.e^{-{\mathrm{ik}}_m.Math.R_n}\left(\underset{\mathrm{mesh}.Math..Math.\mathrm{cells}.Math..Math.c.Math..Math.\mathrm{of}.Math..Math.\mathrm{shape}.Math..Math.s}{.Math.}.Math.A_c.Math.\frac{e^{{\mathrm{ik}}_m.Math..Math.{\stackrel{.fwdarw.}{s}}_c-{\stackrel{.fwdarw.}{R}}_n.Math.}}{{.Math.{\stackrel{.fwdarw.}{s}}_c-{\stackrel{.fwdarw.}{R}}_n.Math.}^2}\right).Math.\frac{1}{\underset{\mathrm{mesh}.Math..Math.\mathrm{cells}.Math..Math.c.Math..Math.\mathrm{of}.Math..Math.\mathrm{shape}.Math..Math.s}{.Math.}.Math.A_c}$

where A.sub.c is the volume or area of the mesh cell c and the last factor realizes the normalization of the diffraction features to the volume or surface area of the shape.

[0034] FIG. 1 shows an example for the positioning of the feature locations around one specific car shape S from the set of shapes. The maximal linear dimension L of the car shape S as well as the integration vector {right arrow over (s)} running over the car shape is also indicated.

[0035] It is to be noted, that scale-invariance with respect to the overall scale of each shape S from the set of shapes is achieved if desired by using the normalization of the shape to the absolute surface area or volume of the shape, as indicated by the last factor in the above equation, and by calculating the maximal linear length L of each shape s and placing the feature locations on a sphere with a radius given in terms of this length L and also selecting the wave numbers dependent on this length scale.

[0036] Further, invariance of the features with respect to orientation of the shape can be achieved if desired by determining a set of symmetry transformations {.sub.b} which map the set of feature locations onto itself, {.sub.b: {R.sub.n}.fwdarw.{.sub.b(R.sub.n)=R.sub.n}}. A symmetry-transformation just re-names the feature locations, i.e. permutes the ordering of the set of feature locations. All shape descriptors which are produced under such symmetry transformation just have permuted entries and are considered as equivalent.

[0037] In combination, both measures realize pose normalization of the 3D shape.

[0038] The set of shape descriptors {{right arrow over (F)}.sub.s, s=1, . . . , N.sub.s} of a set of shapes serves as a low-dimensional representation of the complete set of shapes and is, according to a preferred embodiment of the invention, used to build models which are trained to predict a performance of a new shape. Thus, one preferred embodiment regards multi-disciplinary shape optimization starting from an initial shape. For example, such optimization could be an optimization of the car body shape s for aerodynamic efficiency where drag should be minimized while certain other aspects of the flow should be maintained such as downforce in the rear part of the car. In addition to the aerodynamics, the structural mechanical properties of the car should also be optimized for supporting various given static loads cases. For such application, the car shape is parameterized by one or more methods most convenient for the development engineer of each discipline and such paramterization usually changes during such a process as different parts of the car are optimized separately in each discipline. The evaluation of the aerodynamic properties is done with computational fluid dynamics (CFD) and finite element method (FEM) simulations, for example.

[0039] A significant gain and speed-up in the individual disciplines, CFD or FEM, can already be achieved by utilizing surrogate models which replace part of the actual CFD or FEM simulations andafter being trained on a set of simulation data obtained for a set of shapespredict the aerodynamics and structural mechanics for new car shapes only using the efficient low-dimensional representation of the car shape as input. In order to utilize all available data, the efficient low-dimensional representation must represent the complete car geometry. Even further gain is possible by using a unified efficient low-dimensional representation which can be utilized in multiple disciplines such as CFD of FEA simultaneously.

[0040] The proposed set of diffraction feature shape descriptors for a set of shapes is a very promising realization of such unified efficient low dimensional representations for a set of shapes. In such a scenario, the set of diffraction feature shape descriptors is calculated for a set of shapes generated during some initial phase of the design procedure. The dimensionality of each diffraction feature shape descriptor can be reduced by applying a dimensionality reduction technique such as principal component analysis or locally linear embedding to the complete set of shape descriptors. Then surrogate models, such as Gaussian process kriging models, support vector regressors, or random forest models are trained on the set of dimensionally reduced shape descriptors to predict the aerodynamic and structural mechanics performance given the dimensionality reduced diffraction feature shape descriptors of a new shape as input. Then, such models can be used in one of the many surrogate-assisted single-objective and multi-objective optimization approaches that are already known in the art. In such optimization approaches, for a newly proposed design the diffraction feature shape descriptor is calculated, the dimensionality reduction transformation is applied and then the surrogate models are used to estimate the aerodynamic and structural mechanics performance of the new shape, without running the resource consuming CFD or FEM simulations. Thus, a new car shape with improved aerodynamic and structural mechanics performance can be achieved with a numerical optimization approach, where depending on the details of the surrogate-assisted optimization algorithm, the number of necessary CFD and FEM simulations can be drastically reduced. Similar approaches can be taken for other and arbitrary number of disciplines, where this embodiment of the invention serves as the one unified efficient low-dimensional representation for a set of shapes.

[0041] One significant advantage of the shape descriptors generated by the invention used for such applications described above using CFD simulations in particular, is that the interference pattern encoded in the diffraction feature shape descriptors is sensitive to small changes of the geometry which might have strong impact on the aerodynamics. But at the same time, the features are global in nature, where large scale changes are captured as well. And additionally, when used without any pose normalization, the features are sensitive to the absolute positioning and orientation of the shapes which is a very good aspect when used for modelling fluid flow around shapes or the effect static or dynamic directed forces have in a shape since in both applications the absolute orientation of the shapes is important.

[0042] According to another advantageous embodiment of the invention, the set of diffraction feature shape descriptors are used in shape matching or shape retrieval algorithms where similarities between shapes need to be assessed. This application is, for example, relevant in the engineering design process when an engineer develops a new shape and then tries to find similar shapes in the existing database of shapes which were already evaluated in prior design processes. In a typical application we are given a set of shapes, {S.sub.s, s= . . . , N.sub.s}, which is for example the archive of already evaluated shapes, which we would like to partition into different categories and then allow for shape retrieval applications, where the most similar shape to a novel shape to arrive later is sought. First, the feature locations are chosen where the same feature locations and wave vectors will be used for all shapes. Then, for each shape S.sub.s the diffraction feature shape descriptor {right arrow over (F)}.sub.s is calculated. The set of shapes {S.sub.s} can then be partitioned into different categories by applying a clustering algorithm on the set of respective shape descriptors {{right arrow over (F)}.sub.s, s=1, . . . , N.sub.s}. For the subsequent shape retrieval application the query shape is evaluated with the clustering algorithm which was used to determine the categories and all shapes with the same class label are determined and considers as similar.

[0043] The major advantage of the proposed set of diffraction feature shape descriptors calculated in the above described manner is that one unified set of shape descriptors can be used for all applications described above. For properly chosen feature locations, degree of locality and wave numbers, the one set of shape descriptor {{right arrow over (F)}.sub.s, s=1, . . . , N.sub.s} calculated once for the associated set of shapes {S.sub.s, s=1, . . . , N.sub.s} can be simultaneously used for all types of applications, such as shape classification, shape retrieval, performance prediction of new shapes, surrogate assisted shape optimization, and more. This is enabled by the global nature of the shape descriptors which are at the same time sensitive to local changes of shapes due to the interference and complex valuedness of the shape descriptors.

[0044] In FIG. 2 there is shown a simplified flowchart to illustrate the main method steps according to the invention. At first in step S1 the feature locations are defined. Then, in step S2 the wave numbers are defined. It is to be noted that, of course, the sequence of the first two method steps S1 and S2 may be altered. Further, in step S3 the degree of locality is set. According to one aspect of the invention, all these inputs that are necessary in order to calculate the se of feature descriptors in step S4 may be read in from a memory which is part of a computer system that is used in order to calculate the feature descriptors and later on to generate the set of shape descriptors {{right arrow over (F)}.sub.s} from the feature descriptors. The computer furthermore includes a processor connected to the memory where the calculation of the feature descriptors is done and also the generation of the set of shape descriptors {{right arrow over (F)}.sub.s}.

[0045] Alternatively, the definition of the feature location, the wave numbers and the degree of locality could be input into the computer system directly by an engineer via an interface.

[0046] After the feature descriptors have been calculated for each shape s, they are assigned to elements of feature vector, in order to generate the set of shape descriptors {{right arrow over (F)}.sub.s} in step S5. The set of shape descriptors {{right arrow over (F)}.sub.s} is then output either directly into an algorithm where, based on the set of shape descriptors {{right arrow over (F)}.sub.s}, further processing is performed, for example in order to perform shape matching or retrieval of the shape, or to perform surrogate-assisted optimization is already mentioned above in greater detail. Of course, the set of shape descriptors {{right arrow over (F)}.sub.s} may also be stored in the memory of the computer system.