Method for establishing a deformable 3D model of an element, and associated system

Abstract

A method is provided for generating a three-dimensional morphable model of an element from an initial database of examples of such elements providing data allowing, for each of the elements of the initial database, a three-dimensional meshed surface based on points and on a triangular network connecting the points to be determined.

Claims

1. A method for generating a three-dimensional morphable model of a selected element, the method comprising: obtaining a plurality of training point clouds for the selected element, each training point cloud comprising a plurality of points representing an example of the selected element; for each training point cloud: calculating, from a meshed surface defined by the point cloud, one or more values of a geometric characteristic of the meshed surface as measured at a corresponding one or more points of the point cloud; and generating a two-dimensional representation of the meshed surface and the one or more calculated values; for a reference training point cloud selected from the plurality of training point clouds, registering a set of reference peaks, where the set of reference peaks is a subset of the plurality of points comprising the reference training point cloud; based on the registered set of reference peaks, down-sampling each non-reference training point cloud of the plurality of training point clouds; calculating a model of the selected element from the down-sampled training point clouds, the model of the selected element comprising an average shape of the selected element and one or more deformation modes; and re-meshing the average shape of the selected element.

2. The method of claim 1, wherein the down-sampling comprises, for each non-reference training point cloud, selecting a set of points that corresponds to the registered set of reference peaks from the reference point cloud.

3. The method of claim 2, further comprising: calculating a triangulation over the registered set of reference peaks, thereby generating a connected graph of triangles; and projecting the connected graph of triangles onto the down-sampled set of points selected for each non-reference training point cloud, thereby generating a plurality of projected triangulations.

4. The method of claim 3, wherein the triangulation is a Delaunay triangulation.

5. The method of claim 3, wherein re-meshing the average shape of the selected element comprises: generating a plurality of sets of matching triangles, such that the i.sup.th set of matching triangles contains the i.sup.th triangles from each of the projected triangulations; and calculating centroid coordinates for each triangle contained within the plurality of sets of matching triangles.

6. The method of claim 5, further comprising: for each reference peak contained within the i.sup.th triangle of the calculated triangulation of the reference training point cloud, determining, for each triangle contained within the i.sup.th set of matching triangles, the closet peak to the reference peak; and automatically generating new registrations from the determined closest peaks.

7. The method of claim 1, wherein the selected element is an ear.

8. The method of claim 1, wherein the meshed surface defined by the point cloud is three-dimensional.

9. The method of claim 8, further comprising applying the one or more calculated values of the geometric characteristic to the three-dimensional meshed surface as a texture, prior to generating the two-dimensional representation.

10. The method of claim 1, wherein the geometric characteristic includes a local curvature at or a shape descriptor at the one or more points of the point cloud.

11. The method of claim 10, wherein the local curvature comprises one or more of a minimum curvature, a maximum curvature, a Gaussian curvature, and an average curvature.

12. The method of claim 10, wherein the shape descriptor comprises a surface patch histogram of index shape.

13. The method of claim 1, wherein generating a two-dimensional representation of the meshed surface and the one or more calculated values comprises flattening or unwrapping the meshed surface having the one or more calculated values as a texture applied prior to the generating of the two-dimensional representation.

14. The method of claim 1, wherein flattening the meshed surface comprises an ABF, LSCM, ABF++, or HLSCM method.

15. The method of claim 1, wherein registering the set of reference peaks for the reference training point cloud comprises: segmenting the two-dimensional representation of the reference training point cloud into a uniform distribution over a range given by the one or more values of the geometric characteristic calculated for the reference training point cloud; wherein the segmentation comprises generating isocurvature lines such that the reference point cloud's plurality of points are uniformly distributed over the isocurvature lines according to their calculated value.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The invention will be better understood on studying a few embodiments, which are described by way of completely nonlimiting example and illustrated by the appended drawings, in which:

(2) FIGS. 1 to 7 schematically illustrate a method according to one aspect of the invention, said method being applied to human ears; and

(3) FIGS. 8 to 10 schematically illustrate a method according to one aspect of the invention, said method being applied to human faces.

DETAILED DESCRIPTION

(4) The present invention is an alternative to the aforementioned methods and allows a morphable model of any type of subject or element to be created on the basis of the study of its morphology.

(5) In the rest of the description, the described example elements will be human ears or human faces, but the invention may be applied to any other element whatsoever.

(6) In particular, the present invention does not require texture information and therefore thus avoids the pose and illumination problems to which optical flow algorithms, such as SFM (structure from motion) or SFS (structure from shading) algorithms, are subject. In addition, the invention makes it possible to naturally adapt to three-dimensional or 3D data just like to 2.5D data. Lastly, the present invention allows semantic information to be preserved, or in other words the physical sense conveyed by a zone, a group of peaks or even a single peak to be preserved. Thus, in the example of a human face, the peaks composing the nose of the average shape will also compose the nose of any face of the model after deformation. This observation is also valid for substructures, such as in the present case: the end of the nose, the right and left nostrils or the ridge.

(7) FIG. 1 shows the main steps of the method according to one aspect of the invention.

(8) In other words, FIG. 1 illustrates a method 1 for generating a three-dimensional morphable model of an element from an initial database of examples, which database is loaded 2 into the computational means implementing the method, of such elements providing data allowing, for each of the elements of the initial database, a three-dimensional meshed surface based on points and on a triangular network connecting said points to be determined, wherein: for each example element of the initial database, at each point of its meshed surface, the value of at least one parameter representative of the shape of the surface of the element at this point is determined 3 (by measurement or computation) in order to obtain an improved database of example elements; for each example element of the improved database, corresponding to the elements of the initial database, flattening or unwrapping is carried out 4 on the three-dimensional meshed surface in order to obtain a two-dimensional representation of said meshed surface; in all of the two-dimensional representations of the meshed surfaces of said elements, a plurality of respective points are brought into registration 5 using said determined values of the one or more parameters representative of the shape of the surface of the element at said points and a method for analyzing said two-dimensional representations of the meshed surfaces; on the basis of said registered points, said three-dimensional meshed surfaces of the initial database are down-sampled 6; on the basis of the three-dimensional meshed surfaces of the initial database, a model of the element comprising an average shape of the element and deformation modes is determined 7; and said average shape of the element is re-meshed 8.

(9) It is possible to down-sample each example element of the initial database.

(10) Thus, when the available computational power is limited, it is possible to adapt the data accordingly.

(11) As a variant, it is possible to down-sample each example element of the initial database except one of said examples, which is taken as reference.

(12) Thus, it is possible to improve the efficiency of the following step of automatic registration without requiring notably more computational power.

(13) FIGS. 2a and 2b show an example of a model obtained using an ear database. FIG. 2a shows the un-meshed average ear, and FIG. 2b shows the same ear deformed in the third deformation mode. In the present case, it is a question of right ears.

(14) More precisely, the models obtained by principal component analysis (PCA) take the form of an average and of deformation modes or of eigenvalue/eigenvector pairs hierarchized in order of importance, or of other terms in decreasing eigenvalue order. It is therefore possible to speak of the first deformation mode, of the second deformation mode, etc.

(15) In the present invention, in the 3D universe, each deformation mode represents a set of types of movement undergone by the elements of the point cloud. It is possible to see these types of movement as the data of a direction and of a movement speed for each point. The datum of a multiplicational coefficient, which could be likened to a duration in the preceding analogy, allows the exact movement thereof to be computed.

(16) FIG. 2a shows the average ear without deformation and the preceding figure is the same ear with deformations. In both cases, the gray level represents the movements of the points with respect to their position within the average ear. In FIG. 2a, seeing as there is no movement, the shade of gray is uniform.

(17) In FIG. 2b, the third deformation mode has been used. The peaks with the highest gray levels are those that have moved most and vice versa.

(18) The present model thus allows physical substructures of the ear that have a tendency to change in unison (or in contrast separately if a complementarity approach is employed) to be revealed.

(19) The gray level of each point is associated with its deviation with respect to its position in the average shape (the higher the gray level, the larger the deviation).

(20) The method according to one aspect of the invention is implemented as follows: 1) A database of training examples is assumed to be available, each of the examples allowing, directly or after processing, a meshed surface to be reconstructed in R3.

(21) 2) For each example:

(22) local geometric characteristics of each point of each example are measured. The result of each measurement is associated with the point that served for its realization. This measurement may be of local curvature, as illustrated in FIG. 3, such as the minimum, maximum, Gaussian or average curvature at the point in question, of a more complex shape descriptor such as a surface patch histogram of index shape (SPHIS), or of an equivalent or a combination of the above. The 3D ear of FIG. 3 has gray levels that depend on the local average curvaturethe higher the local average curvature, the darker the gray.

(23) The surface is unwrapped, which thus allows a representation of each mesh taking the form of a 2D image (denoted im2D) to be obtained, as illustrated in FIGS. 4a and 4b (which respectively correspond to the left and right ear of the subject 9 after curvature computation and flattening) and a connected graph to be obtained (which graph is conventionally denoted Gc but is not shown). In FIGS. 4a and 4b, the gray levels are such that the higher the local average curvature, the darker the gray.

(24) This unwrapping may be carried out in multiple ways, such as with ABF (angle-based flattening) algorithms, LSCM (least square conformal mapping) algorithms or derivatives thereof (ABF++ algorithms, HSLCM (hierarchical least square conformal mapping) algorithms, etc.).

(25) 3) Registration of a maximum of points is carried out on the basis of the 2D images using the characteristics measured in point 2) and analyzing methods related to 2D image processing, as illustrated in FIG. 5. FIG. 5 shows, to the left in 2D and to the right in 3D, the same ear after manual registration of 88 points on the isocurves 9, which are shown in the 2D image on the left. In FIG. 5, the gray levels are such that the higher the local average curvature, the darker the gray.

(26) 4) The points 10 retained during the registration are then used to down-sample the initial 3D meshes. The resulting point clouds are then used to form the actual model using conventional construction tools such as principal component analysis (PCA) or intermediate component analysis (ICA), etc.

(27) A shape called the average shape and deformation modes are then obtained as illustrated in FIG. 2b.

(28) 5) The average shape is remeshed in order to allow a surface to be given to the model.

(29) There follows an example embodiment of the method of the invention, relating to a 3D morphable ear model.

(30) The database used consisted of ten examples freely accessible from the SYMARE database, SYMARE being the acronym of Sydney-York Morphological And Recording of Ears.

(31) In addition, all the left ears of these 10 pairs of ears were symmetrized with respect to the sagittal plane so as to create twenty right ears (the ten initial right ears and the ten right ears obtained by symmetrization of the ten left ears).

(32) The set of indices of these right ears will be denoted I=[[1; 20]] and the index of the right ear taken as reference right ear will be denoted i=1.

(33) For reasons of consistency, the meshes of the ears thus obtained were down-sampled to about 6900 peaks. This purely optional step was present in order to optimize the digital processing time and to facilitate the subsequent integration of any other training examples.

(34) Lastly, the left ear of the first subject of the database was chosen as reference ear after right-ear symmetrization. In the rest of the document, all the notations indexed by ref naturally relate to this reference (in particular, iref=1).

(35) Point 2) of the description of the invention was then carried out. Local average curvature was used as geometric characteristic and applied as texture to the 3D meshes, as illustrated in FIG. 3.

(36) The unwrapping was carried out by virtue of an LSCM (least square conformal mapping) algorithm, as illustrated in FIGS. 4a and 4b.

(37) As specified in point 3), other algorithms are employable. There are no particular pre-requisites. Registration of the peaks of the connected graphs required the following steps:

(38) 1) A step in which the 2D images were segmented into N.sub.c=10 curvature levels that were uniformly distributed over the range of the values taken by the curvature measurements, as illustrated in FIG. 5.

(39) 2) A step in which N.sub.s.sup.manu=88 peaks of the reference connected graph were selected.

(40) This selection was carried out on n.sub.c isocurvature lines, as illustrated in the example of FIG. 6, with n.sub.c[[1,N.sub.c]], said lines themselves being chosen to ensure a uniform distribution of the peaks.

(41) 3) A step in which corresponding peaks were selected in each corresponding connected graph (not shown) G.sub.c.sup.i, iI{i.sub.ref}.

(42) 4) A step in which a triangulation (in the present case, a Delaunay triangulation) was carried out on the N.sub.s.sup.manu peaks issued from the connected graph G.sub.c.sup.i.sup.ref of the reference ear indexed i.sub.ref and in which the connectivity graph or connected graph that resulted therefrom was transferred to the other groups of peaks isolated beforehand.

(43) This created a finite set of triangles, indexed J. In the present case, J=[[1,163]].

(44) The set thus created for the i.sup.th ear, as illustrated in FIG. 7, was denoted T={t.sub.j.sup.i,jJ}, i1. FIG. 7 shows the ear indexed 1 at the top and the ear indexed 9 at the bottom, unwrapped in 2D on the left and in 3D on the right, respectively. A triangulation of the N.sub.s.sup.manu selected peaks was carried out on ear 1 and transferred to ear 9. By way of example, triangle number 116 of this triangulation is indicated for both of ears 1 and 9.

(45) 5) A step in which, for each jJ, T.sub.j={t.sub.j.sup.i, eI} was considered to be the set of the j.sup.th triangles. Each element t.sub.j.sup.i j potentially contained peaks of the graph G.sub.c.sup.i, the centroid coordinates of which were computed in the coordinate system specific to the triangle t.sub.i.sup.j.

(46) 6) A step in which the set of peaks included in t.sub.j.sup.i.sup.ref was parsed and, for each thereof, in each other triangle t.sub.j.sup.lT.sub.j\ii.sub.ref, the peak closest in terms of centroid coordinates was sought. This created new registrations.

(47) However, since it was necessary for a peak of a graph not to be associated with a plurality of peaks of another, conflicting registrations that were the least interesting from the point of view of centroid distance were deleted. Thus a set of automatic registrations was obtained from the elements of T.sub.j, jJ.

(48) This was done for all jJ and, in the end, N.sub.s.sup.auto automatic registrations were obtained for all the ears. In the present example, N.sub.s.sup.manu+N.sub.s.sup.auto=1460 points.

(49) Among the possible variants and improvements, the following may be listed: Use of other criteria for characterizing the local geometry rather than just curvature, and indeed conjoint use of a plurality thereof. Up-sampling of all the ears or of all the ears except the reference ear. This allows the efficiency of the automatic registration to be increased and, therefore, the final resolution of the model to be increased.

(50) This additional step makes it possible to pass from 1460 points to 5076 points, to be placed facing the 6900 peaks in the initial meshes. For example, this up-sampling may use the centroids of the initial triangles.

(51) The parameters N.sub.c and N.sub.s.sup.manu may of course be set to other values.

(52) The curvature levels may not be uniformly distributed over the available range but take into account the statistical distribution of the values of the curvatures.

(53) The N.sub.s.sup.manu points selected in registering step 2) may be selected automatically or semi-automatically, for example: gradual training of the selection process may be performed with the first ears, thus allowing preselection on the following ears. snake-based methods may be used to establish the detail of the transformations of an isoline of one image to the corresponding isoline of another image.

(54) In another example embodiment, as follows, the method was applied to human faces.

(55) The database of faces used in the present example consisted of examples 2, 5, 6 and 14 of the 3D database of faces UWA face database of the University of Western Australia, which is available at the following address: http://staffhome.ecm.uwa.edu.au/00053650/databases.html.

(56) As for the example described above applied to human ears, a mesh was chosen as reference. In the present case, that was subject number 2 of the database.

(57) Likewise, the local average curvature was also used as geometric characteristic and applied by way of texture to the 3D meshes, as illustrated in FIG. 8, in which the gray levels are representative of the local average curvaturethe higher or darker the gray level, the higher the local average curvature.

(58) In contrast, contrarily to the preceding case, the available meshes were not down-sampled. The number of initial peaks varied between 16655 and 25951.

(59) Step 2 of the description of the invention was then carried out using the same methodology as for the described example based on ears.

(60) The only notable differences were the number of training examples (4 faces) and the number of manually annotated points (N.sub.s.sup.manu=37), as illustrated in FIG. 9 which shows an example of a 2D and 3D representation of a given face after manual registration of 37 points located on isocurves, similarly to FIG. 5 for the example of application to the ears.

(61) The obtained result was a morphable face model comprising 6846 peaks and forming an average face, as illustrated in FIG. 10 in gray level, accompanied by 3 deformation modes.

(62) In the present application, an innovative way of constructing a morphable model has been described. This method has many advantages with respect to the prior art, and in particular: Potential application to any type of 3D shape, without loss of information. Preservation of the semantic aspect attached to the studied object, by virtue of the local character of the considered characteristics. Entirely automatable. Unconstrained with respect to the texture of the training examples and therefore to the illumination conditions during the acquisition of the data. The ability to incorporate 2D-image analyzing algorithms, which are more numerous and mature than those of the 3D world.

(63) The steps of the method described above may be carried out by one or more programmable processors executing a computer program in order to execute the functions of the invention by performing operations on input data and generating output data.

(64) A computer program may be written in any form of programming language, including compiled or interpreted languages, and the computer program may be deployed in any form, including as an autonomous program or as a subprogram, element or other unit suitable for use in a computational environment. A computer program may be deployed to be executed on one computer or on a plurality of computers at a single site or distributed over a plurality of sites and connected together by a communication network.

(65) The preferred embodiment of the present invention has been described. Various modifications may be made without departing from the spirit and scope of the invention. Therefore, other implementations fall within the scope of the following claims.