TEXTURING A 3D MODELED OBJECT

[0001] This application claims priority under 35 U.S.C. §119 or 365 to European Application No. 14306986.2, filed Dec. 10, 2014. The entire teachings of the above application(s) are incorporated herein by reference.

[0002] The invention relates to the field of computer programs and systems, and more specifically to a method, system and program for designing a 3D modeled object representing a real object.

[0003] A number of systems and programs are offered on the market for the design, the engineering and the manufacturing of objects. CAD is an acronym for Computer-Aided Design, e.g. it relates to software solutions for designing an object. CAE is an acronym for Computer-Aided Engineering, e.g. it relates to software solutions for simulating the physical behavior of a future product. CAM is an acronym for Computer-Aided Manufacturing, e.g. it relates to software solutions for defining manufacturing processes and operations. In such computer-aided design systems, the graphical user interface plays an important role as regards the efficiency of the technique. These techniques may be embedded within Product Lifecycle Management (PLM) systems. PLM refers to a business strategy that helps companies to share product data, apply common processes, and leverage corporate knowledge for the development of products from conception to the end of their life, across the concept of extended enterprise.

[0004] The PLM solutions provided by Dassault Systemes (under the trademarks CATIA, ENOVIA and DELMIA) provide an Engineering Hub, which organizes product engineering knowledge, a Manufacturing Hub, which manages manufacturing engineering knowledge, and an Enterprise Hub which enables enterprise integrations and connections into both the Engineering and Manufacturing Hubs. All together the system delivers an open object model linking products, processes, resources to enable dynamic, knowledge-based product creation and decision support that drives optimized product definition, manufacturing preparation, production and service.

[0005] In this context, the field of computer vision and computer graphics offers technologies which are more and more useful. Indeed, this field has applications to 3D reconstruction, 3D models texturing, virtual reality and all domains where it is necessary to precisely build a 3D scene with exact geometry using as input, for example, the information in a set of photographs. 3D texturing can be used in any field which involves the creation of textured 3D models, such as serious gaming, video games, architecture, archeology, reverse engineering, 3D assets database, or virtual environments. 3D reconstruction from video stream and photographs set analysis is addressed in two different approaches in the state of the art, depending on the type of sensors used for the input data.

[0006] The first approach uses “receiver” sensors. This notably concerns 3D reconstruction from RGB images analysis. Here, 3D reconstruction is obtained by multi-view analysis of RGB color information contained in each of the image planes. The following papers relate to this approach:

• [0007] R. Hartley and A. Zisserman: Multiple View Geometry in Computer Vision, Cambridge Univ. Press 2004;
• [0008] R. Szeliski: Computer Vision: Algorithms and Applications, Edition Springer 2010; and
• [0009] O. Faugeras: Three-Dimensional Computer Vision: A Geometric viewpoint, MIT Press 1994.

[0010] The second approach uses “emitter-receiver” sensors. This notably concerns 3D reconstruction from RGB-Depth images analysis. This kind of sensors gives additional depth data to standard RGB data, and it is depth information that is mainly used in the reconstruction process. The following papers relate to this approach:

• [0011] Yan Cui et al.: 3D Shape Scanning with a Time-of-Flight Camera, CVPR 2010;
• [0012] R S. Izadi et al.: KinectFusion: Real-Time Dense Surface Mapping and Tracking, Symposium ISMAR 2011; and
• [0013] R. Newcombe et al.: Live Dense Reconstruction with a Single Moving Camera, IEEE ICCV2011.

[0014] Moreover, several academic and industrial players now offer software solutions for 3D reconstruction, by RGB image analysis, such as Acute3D, Autodesk, VisualSFM, or by RGB-Depth analysis, such as ReconstructMe or Microsoft's SDK for Kinect (registered trademarks).

[0015] Multi-view photogrammetry reconstruction methods use the sole information contained in the image plans of a video sequence (or a series of snapshots) in order to estimate 3D geometry of the scene. The matching of interest points between different ones of the 2D views yields the relative positions of the camera. An optimized triangulation is then used to compute the 3D points corresponding to the matching pair. Depth-map analysis reconstruction methods are based on disparity maps or approximated 3D point clouds. Those disparity maps are obtained using stereovision or structured light (see the ‘Kinect’ device for example) or ‘Time of Flight’ 3D-cameras. These state-of-the-art reconstruction methods then typically output a discrete 3D representation of the real object, most often a 3D mesh. The 3D model derives from the in fine volume closing off the resulting 3D point cloud.

[0016] A further step known from the prior art is to produce a texture for each polygon on the 3D mesh. In order to ensure photo-realism, prior art requires that the rendering use standard images from high-quality devices capturing the scene simultaneously. This is explained in the paper by T. Hanusch, “A new texture mapping algorithm for photorealistic reconstruction of 3D objects”, in ISPRS journal of photogrammetry and remote sensing.

[0017] FIG. 1 illustrates a common approach used to texture a 3D model with a photograph, which is the well-known projective texture mapping method. This method is described for example in the paper by P. Debevec, C. Taylor and J. Malik, “Modeling and Rendering Architecture from Photographs: A hybrid geometry-and image-based approach”, in SIGGRAPH 1996. This method uses image projection data associated to a 2D view (relative to the 3D model) to compute the mapping to the 3D model. FIG. 1 shows such a view-dependent 3D model texturing principle for 3D meshed model 102 and calibrated image 104: a projection texture mapping (represented by bundle 106, computed from camera projection matrix and departing from optical center 108) is used to estimate the texture coordinate for each triangle vertex.

[0018] Now, as illustrated on FIG. 2, the texturing quality by projection onto the 3D model is highly dependent on camera pose estimation. Indeed, FIG. 2 illustrates the 3D model texturing problematic: on the left, accurate calibration data allows coherent texturing 104 by projection on 3D model 102, whereas, on the right, inaccurate calibration data induces a drift in the projection of texturing 104 relative to 3D model 102. In other words, the estimation of camera rotation and translation at the time of the snapshot has a high impact on the final texturing. Obviously, any bias on the camera pose translates onto the re-projection and deteriorates the texturing process. Such a bias is usually particularly significant in the case of depth-map analysis methods. It generally originates from a shift in synchronizing between the depth sensor and the RGB sensor, corrupting the camera trajectory estimation. But it may also originate from: an outside shot from an independent camera whose relative position to the 3D model cannot be estimated with sufficient accuracy because there is no rigid dependency to the depth sensor; a noisy sensor, leading to inaccurate 3D models and camera poses; a drift in the 3D reconstruction process, leading to inaccurate 3D models; and/or distorted images leading to inaccurate texture mapping onto the 3D model.

[0019] Within this context, there is still a need for an improved solution for designing a 3D modeled object representing a real object.

[0020] It is therefore provided a computer-implemented method for designing a 3D modeled object representing a real object. The method comprises the steps of providing a 3D mesh representing the real object and having vertices, a texturing image and a mapping between the vertices of the 3D mesh and pixels of the texturing image; then maximizing a probability P(L(V)) of the form:

$P\left(L\left(V\right)\right)=\frac{1}{z}\exp \left(-\sum _{i=1}^n{\varphi }_i^{\prime }\left(L\left(v_i\right)\right)-{\sum }_{f\in ℱ}{\psi }_f^{\prime }\left({\left\{L\left(v_i\right)\right\}}_{i\in f}\right)\right).$

n designates the number of vertices of the 3D mesh and v_i designates the vertices of the 3D mesh. L(v_i) designates a pixel shift to be applied after mapping vertex v_i on the texturing image and selected in a predetermined finite set (L). Z=Σ_L(V) exp(−Σ_i=1ⁿφ_i′(L(v_i))−Σ_fεfψ_f′({L(v_i)}_iεf)). F designates the set of sets of indices of mesh tiles of the 3D mesh. φ_i′ designates a cost function associated to vertex v_i and decreasingly depending on an extent to which the result of applying the pixel shift, selected for vertex v_i, after mapping vertex v_i on the texturing image respects a predetermined relation between vertices of the 3D mesh and pixels of the texturing image. ψ_f′ designates a cost function associated to a tile f of the 3D mesh and depending on a global difference between pixel shifts selected for the vertices of tile f. The step of maximizing is performed with a predetermined discrete Markov Random Field optimization scheme. The scheme views the 3D mesh and the pixel shifts associated to the texture coordinates of the vertices of the 3D mesh as a Markov Random Field of energy:
−log(P(L(V)))−log(Z)=Σ_i=1ⁿφ_i′(L(v_i))+Σ_fεFψ_f′({L(v_i)}_iεf)). The method also comprises texturing the 3D mesh according to the texturing image, to the mapping, and to the result of the step of maximizing

[0021] The method may comprise one or more of the following:

• • [0022] the cost function ψ_f′ is of the form ψ_f′({L(v_i)}_iεf)=Σ_{i,j}εp(f)ψ_i,j′(L(v_i),L(v_j)), where p(f) designates the set of pairs of indices of vertices of tile f, and the predetermined discrete Markov Random Field optimization scheme is a pairwise discrete Markov Random Field optimization scheme;
  • [0023] ψ_i,j′(L(v_i),L(v_j)) is of the form

$\frac{\lambda }{3}({L\left(v_i\right)-L\left(v_j\right)}_1,$

where λ designates a positive scalar;

• • [0024] the predetermined relation between vertices of the 3D mesh and pixels of the texturing image amounts to a predetermined relation between 3D curvature values for a vertex of the 3D mesh and distance values to a nearest contour of the texturing image for a pixel of the texturing image;
  • [0025] 3D curvature values lower than a predetermined threshold are in the predetermined relation with all distance values, and 3D curvature values higher than the predetermined threshold are in the predetermined relation with distance values according to an increasing one-to-one correspondence;
  • [0026] φ_i′ is of the form

${\varphi }_i^{\prime }\left(L\left(v_i\right)\right)=1_{C_i>c}\frac{\gamma }{C_i}-T_i\left(L\left(v_i\right)\right),$

where 1_Ci>c designates an indicator function, with C_i designating the maximal 3D curvature of vertex v_i and c designating a positive scalar, γ designates a positive scalar, T_i(L(v_i)) designates the value of a distance transform of the texturing image at the result of applying the pixel shift, selected for vertex v_i, after mapping vertex v_i on the texturing image, the distance transform being relative to a contour image of the texturing image;

• • [0027] the contour image is determined with a Canny edge detector applied on the texturing image;
  • [0028] the distance transform of the texturing image is determined with a Chamfer mask applied on the texturing image relative to the contour image of the texturing image; and/or
  • [0029] the 3D mesh, the texturing image and the mapping are all outputted by a predetermined structure-from-motion analysis scheme applied on the real object, the mapping corresponding to pose camera parameters determined for the texturing image in the structure-from-motion analysis.

[0030] It is further provided a computer program comprising instructions for performing the method.

[0031] It is further provided a computer readable storage medium having recorded thereon, or in a container, the computer program.

[0032] It is further provided a computer system comprising a processor coupled to a memory and a graphical user interface, the memory having recorded thereon the computer program.

[0040] With reference to the flowchart of FIG. 3, it is proposed a computer-implemented method for designing a 3D modeled object representing a real object. Throughout the method, the 3D modeled object designates data that represent the real object in different ways: first its geometry via a 3D mesh, and then a textured geometry via the textured 3D mesh outputted by the method. The method comprises a step of providing S10 a 3D mesh representing the real object (the 3D mesh having notably vertices defined by 3D positions, e.g. but also edges linking the vertices, such as a triangular or a quad mesh), e.g. a 3D mesh without any texturing or with a texturing to be replaced by a new one (i.e. the texturing outputted by the method), a texturing image (a 2D view, e.g. an image such as a photograph, of the real object provided with values at pixel locations, of gray-level or of colors such as RGB values, being noted that the figures later illustrating examples of the method mainly show gray-level texturing images but that all these examples of the method may obviously apply mutatis mutandis to a color texturing image as well, e.g. an RGB image) and a mapping between the vertices of the 3D mesh and pixels of the texturing image (i.e. a function that corresponds positions of the 3D mesh to 2D locations, e.g. pixels, of the texturing image, such as camera pose parameters provided with the texturing image). Of course, the 3D mesh may represent only a part of the real object visible on the texturing image. Also, the method may be repeated with several texturing images. Such mesh “partitioning” and “iteration” features are implementation details in 3D mesh texturing known to the skilled person.

[0041] The method comprises then a step of maximizing S20 a probability (or likelihood) function P(L(V)). As known per se, from a computer-implementation point of view, this means that the method runs an optimization program that mathematically amounts to (at least substantially, or at least approximately in the case of pseudo-optimization or the use of a heuristic) finding, at least, the argument that maximizes said function. Said “optimal argument” is actually the data of interest here, the result of the evaluation of the probability at said optimal argument not being of particular interest for the present application. Probability P(L(V)) is of the following form:

$P\left(L\left(V\right)\right)=\frac{1}{Z}\exp \left(-\sum _{i=1}^n{\varphi }_i^{\prime }\left(L\left(v_i\right)\right)-\sum _{f\in ℱ}{\psi }_f^{\prime }\left({\left\{L\left(v_i\right)\right\}}_{i\in f}\right)\right).$

In practice, an energy which comprises a negative logarithmic term of the previous probability may actually be minimized by predetermined optimization schemes at use (but this amounts to the same result).

[0042] n designates the number of vertices of the 3D mesh and v_i designates the vertices of the 3D mesh. L(v_i) designates a pixel shift to be applied after mapping vertex v_i on the texturing image, all pixel shifts being selected/defined (i e taking values) in a predetermined finite set or list (L), for example L={(0,0), (0,1), (1,1), (1,0), (1,−1), (0,−1), (−1,−1), (−1,0), (−1,1)} with (x,y) indicating e.g. a shift in x pixels in the horizontal direction (e.g. the right direction applying to positive values) and in y pixels in the vertical direction (e.g. the upper direction applying to positive values). L(V), the argument of the optimization program, thus designates a set of pixel shifts (basically couples of positive and/or negative integers) that are explored by the optimization program, the optimal argument designating the pixel shifts that are actually and eventually applied by the method to the vertices (once such vertices are projected onto the texturing image according to the mapping) before performing the texturing (i.e. the texturing coordinates defined by the sole mapping are thereby “corrected” or “improved” by the method, thanks to this pixel shift outputted by the optimization step S20).

[0043] Z=Σ_L(V) exp(−Σ_i=1ⁿφ_i′(L(v_i))−Σ_fεfψ_f′({L(v_i)}_iεf)) designates a normalization term that ensures that the value of P is such that it is indeed a probability (in practice, Z need not necessarily be evaluated). F designates the set of sets of indices of mesh tiles (i.e. faces) of the 3D mesh.

[0044] φ_i′ designates a cost function associated to vertex v_i. Cost function φ_i′ decreasingly depends on a specific variable (i.e. it is a decreasing function of said variable). Said variable is in specific an extent (examples of how to measure/determine such extent being provided later) to which the result of applying the pixel shift selected for vertex v_i (i.e. the pixel shift relevant to vertex v_i in the exploration of the argument solution during the optimization and noted L(v_i) in the optimization process but which can in fine be noted L(v_i)* once the program is solved and a single pixel shift is retained, such notation being classical in the field of applied mathematics and optimization), after mapping vertex v_i on the texturing image (according to the mapping provided at S10), respects a predetermined relation between vertices of the 3D mesh and pixels of the texturing image. In other words, the system is provided with a predetermined relation (e.g. a predetermined knowledge that geometrical features of the 3D mesh should correspond to graphical features of the texturing image, e.g. such correspondence being distinct from the mapping provided at S10) between vertices of the 3D mesh and pixels of the texturing image and the maximization program tends to find a pixel shift L* that makes vertex v_i respect such relation as much as possible. The more an explored pixel shift makes the predetermined relation true, the less it will cost in the optimization such that its value will tend to be eventually retained in the optimum.

[0045] ψ_f′ designates similarly a cost function, but this time associated to a tile f of the 3D mesh and depending on a global difference between pixel shifts selected for the vertices of tile f. ψ_f′ penalizes such high global difference. In other words, the optimization tends in the exploration of the argument solution to reach pixel shifts that are, as much as possible, the same for all vertices of each respective single tile f. Such a term provide a good result from a visual/accuracy point of view as it relies on an assumption of global coherency in the texturing drifts, in the context of the method where a texturing image of a real object reconstructed as a 3D mesh is provided (e.g. a structure-from-motion analysis context).

[0046] Written in such a way, the maximization appears to amount to a Markov Random Field (MRF) optimization problem, where the MRF is the value of the pixel shifts assigned to the vertices of the mesh, the edges of the mesh representing conditional probabilities. The method actually includes performing the step of maximizing S20 with a predetermined discrete Markov Random Field optimization scheme (a class of well-known optimization schemes that converge efficiently—i.e., accurately and fast-for MRF problems), viewing the 3D mesh and the pixel shifts associated to the texture coordinates of the vertices of the 3D mesh (i.e. the texture coordinates being the pixels of the texturing image obtained by applying the mapping to the vertices of the 3D mesh) as a Markov Random Field of energy: −log(P(L(V)))−log(Z)=Σ_i=1ⁿφ_i′(L(v_i))+Σ_fεFψ_f′({L(v_i)}_iεf)). In other terms, the predetermined discrete MRF optimization scheme, which can be any known such scheme, is configured for the above-defined MRF structure with the above-defined energy corresponding to probability P. It is again noted that in practice, −log(Z) may be left unevaluated.

[0047] Once the program optimized and the optimal argument pixel shift L* obtained, the method comprises a step of texturing S30 the 3D mesh according to the texturing image, to the mapping, and to the result of the step S20 of maximizing (said optimal argument pixel shift L*). In brief, the method inserts within the classical texturing an application of the pixel shift L* to the texture coordinates implied by the data provided at S10. The method may for example project each respective 3D vertex of the 3D mesh on the texturing image, apply the optimal shift obtained at S20 (for that vertex) to find the (optimal, according to the method) respective texturing pixel, and then assign to said respective 3D vertex the texture/color (or any other data relevant to 3D texturing) found at the respective texturing pixel. This process is classical in the field, the originality of the method lying in the introduction of a pixel shift map obtained by optimization S20.

[0048] Such a method allows an improved way of designing a 3D modeled object. Notably, the method allows the texturing of a 3D mesh that represents a real object, and thus an improvement of the representation of the real object, which is an advantage that 3D reconstruction and texturing algorithms generally aim at obtaining. Furthermore, as the method acts without modifying the inputs provided at S10, the method can be used in conjunction with any other optimization algorithm that globally improves 3D mesh texturing (such as those of the prior art, e.g. identified earlier). Indeed, the method introduces a new variable: pixel shift L. The method then optimizes such variable, e.g. leaving other variables untouched. The method may thus form yet another optimization layer in a global process of performing a 3D reconstruction with texturing.

[0049] For example, the method may comprise, prior to the maximizing S20, possibly prior to the providing S10: providing the 3D mesh representation of the real object provided at S10; identifying, by fully automatic detection, occurrences of a geometric feature at 3D positions of the 3D representation, the geometric feature occurring and being detected each time a 3D curvature of the 3D representation is above a predetermined threshold; providing at least one 2D view of the real object, wherein the 2D view is an image of the real object that forms the texturing image provided at S10; identifying, by fully automatic detection, occurrences of a graphic feature at 2D positions of the 2D view, the geometric feature corresponding to the graphic feature, the graphic feature relating to a pixel gradient of the 2D view; computing the mapping provided at S10 as camera parameters, including a projection matrix which describes projection from the 3D representation to the 2D view, that minimize a distance between a set of projections of the 3D positions of the geometric feature on the 2D view and a set of the 2D positions of the graphic feature, wherein the distance is a predetermined distance between two general sets of 2D points. Such a scheme, that allows obtaining relatively accurate camera parameters or improving accuracy thereof, may be performed according to application EP13306576.3 of 18 Nov. 2013 in the name of DASSAULT SYSTEMES, which is incorporated herein by reference.

[0050] Most importantly, the specific way the pixel shift is optimized (that is, the specific optimization program implemented, with its specific cost terms), allows obtaining a good result from a visual/accuracy point of view, and this with a discrete Markov Random Field optimization scheme, which, as known, converges relatively fast. The method thus smartly makes use of a powerful mathematical tool to obtain computationally fast results in the context of 3D texturing. Notably, any MRF solving scheme described in the following references may be implemented and used:

• [0051] J. Kappes et al, “A Comparative Study of Modern Inference Techniques for Discrete Minimization Problems”, in CVPR 2013; or
• [0052] H. Ishikawa, “Higher-Order Clique Reduction in Binary Graph Cut”, in CVPR 2009.

[0053] These are however only examples, as any (e.g. high order) MRF solving scheme in general may be implemented by the method.

[0054] The method is computer-implemented. This means that the steps (or substantially all the steps) of the method are executed by at least one computer, or any system alike. Thus, steps of the method are performed by the computer, possibly fully automatically, or, semi-automatically. In examples, the triggering of at least some of the steps of the method may be performed through user-computer interaction. The level of user-computer interaction required may depend on the level of automatism foreseen and put in balance with the need to implement the user's wishes. In examples, this level may be user-defined and/or pre-defined. For instance, the step of maximizing S20 and/or the step of texturing S30 may fully automatic, but they may alternatively involve some manual user-interaction. The user may indeed directly identify/add occurrences of geometric features and/or graphic features on the 3D mesh and/or the texturing image to complete the above-mentioned predetermined relation involved in the optimization via cost function φ_i′.

[0055] A typical example of computer-implementation of the method is to perform the method with a system adapted for this purpose. The system may comprise a processor coupled to a memory and a graphical user interface (GUI), the memory having recorded thereon a computer program comprising instructions for performing the method. The memory may also store a database. The memory is any hardware adapted for such storage, possibly comprising several physical distinct parts (e.g. one for the program, and possibly one for the database). The system may also comprise devices to create the 3D mesh and/or to capture the texturing image, such as (e.g. RGB) camera(s) and/or depth sensor(s). The system may indeed be adapted in particular for performing a structure-from-motion analysis.

[0056] The method generally manipulates modeled objects. A modeled object is any object defined by data stored in the database. By extension, the expression “modeled object” designates the data itself. According to the type of the system, the modeled objects may be defined by different kinds of data. The system may indeed be any combination of a CAD system, a CAE system, a CAM system, a PDM system and/or a PLM system. In those different systems, modeled objects are defined by corresponding data. One may accordingly speak of CAD object, PLM object, PDM object, CAE object, CAM object, CAD data, PLM data, PDM data, CAM data, CAE data. However, these systems are not exclusive one of the other, as a modeled object may be defined by data corresponding to any combination of these systems. A system may thus well be both a CAD and PLM system, as will be apparent from the definitions of such systems provided below.

[0057] By CAD system, it is meant any system adapted at least for designing a modeled object on the basis of a graphical representation of the modeled object, such as CATIA. In this case, the data defining a modeled object comprise data allowing the representation of the modeled object. A CAD system may for example provide a representation of CAD modeled objects using edges or lines, in certain cases with faces or surfaces. Lines, edges, or surfaces may be represented in various manners, e.g. non-uniform rational B-splines (NURBS). Specifically, a CAD file contains specifications, from which geometry may be generated, which in turn allows for a representation to be generated. Specifications of a modeled object may be stored in a single CAD file or multiple ones. The typical size of a file representing a modeled object in a CAD system is in the range of one Megabyte per part. And a modeled object may typically be an assembly of thousands of parts.

[0058] In the context of CAD, a modeled object may typically be a 3D modeled object, e.g. representing a real object such as a product such as a part or an assembly of parts, or possibly an assembly of products. By “3D modeled object”, it is meant any object which is modeled by data allowing at least its 3D representation (the 3D representation in the case of the method). A 3D representation allows the viewing of the part from all angles. For example, the 3D representation may be handled and turned around any of its axes, or around any axis in the screen on which the representation is displayed. This notably excludes 2D icons, which are not 3D modeled. The display of a 3D representation facilitates design (i.e. increases the speed at which designers statistically accomplish their task). This speeds up the manufacturing process in the industry, as the design of the products is part of the manufacturing process.

[0059] The 3D modeled object may represent the geometry of a product to be manufactured in the real world subsequent to the completion of its virtual design with for instance a CAD software solution or CAD system, such as a (e.g. mechanical) part or assembly of parts, or more generally any rigid body assembly (e.g. a mobile mechanism). A CAD software solution allows the design of products in various and unlimited industrial fields, including: aerospace, architecture, construction, consumer goods, high-tech devices, industrial equipment, transportation, marine, and/or offshore or transportation. The 3D modeled object designed by the method thus represents an industrial product which may be a part of a terrestrial vehicle (including e.g. car and light truck equipment, racing cars, motorcycles, truck and motor equipment, trucks and buses, trains), a part of an air vehicle (including e.g. airframe equipment, aerospace equipment, propulsion equipment, defense products, airline equipment, space equipment), a part of a naval vehicle (including e.g. navy equipment, commercial ships, offshore equipment, yachts and workboats, marine equipment), a mechanical part (including e.g. industrial manufacturing machinery, heavy mobile machinery or equipment, installed equipment, industrial equipment product, fabricated metal product, tire manufacturing product), an electro-mechanical or electronic part (including e.g. consumer electronics, security and/or control and/or instrumentation products, computing and communication equipment, semiconductors, medical devices and equipment), a consumer good (including e.g. furniture, home and garden products, leisure goods, fashion products, hard goods retailers' products, soft goods retailers' products), a packaging (including e.g. food and beverage and tobacco, beauty and personal care, household product packaging).

[0060] By PLM system, it is meant any system adapted for the management of a modeled object representing a physical manufactured product. In a PLM system, a modeled object is thus defined by data suitable for the manufacturing of a physical object. These may typically be dimension values and/or tolerance values. For a correct manufacturing of an object, it is indeed better to have such values.

[0061] CAM stands for Computer-Aided Manufacturing. By CAM solution, it is meant any solution, software of hardware, adapted for managing the manufacturing data of a product. The manufacturing data generally includes data related to the product to manufacture, the manufacturing process and the required resources. A CAM solution is used to plan and optimize the whole manufacturing process of a product. For instance, it can provide the CAM users with information on the feasibility, the duration of a manufacturing process or the number of resources, such as specific robots, that may be used at a specific step of the manufacturing process; and thus allowing decision on management or required investment. CAM is a subsequent process after a CAD process and potential CAE process. Such CAM solutions are provided by Dassault Systemes under the trademark DELMIA®.

[0062] CAE stands for Computer-Aided Engineering. By CAE solution, it is meant any solution, software of hardware, adapted for the analysis of the physical behavior of modeled object. A well-known and widely used CAE technique is the Finite Element Method (FEM) which typically involves a division of a modeled objet into elements which physical behaviors can be computed and simulated through equations. Such CAE solutions are provided by Dassault Systemes under the trademark SIMULIA®. Another growing CAE technique involves the modeling and analysis of complex systems composed a plurality components from different fields of physics without CAD geometry data. CAE solutions allows the simulation and thus the optimization, the improvement and the validation of products to manufacture. Such CAE solutions are provided by Dassault Systemes under the trademark DYMOLA®.

[0063] PDM stands for Product Data Management. By PDM solution, it is meant any solution, software of hardware, adapted for managing all types of data related to a particular product. A PDM solution may be used by all actors involved in the lifecycle of a product: primarily engineers but also including project managers, finance people, sales people and buyers. A PDM solution is generally based on a product-oriented database. It allows the actors to share consistent data on their products and therefore prevents actors from using divergent data. Such PDM solutions are provided by Dassault Systemes under the trademark ENOVIA®.

[0064] FIG. 4 shows an example of the GUI of the system, wherein the system is a CAD system.

[0065] The GUI 2100 may be a typical CAD-like interface, having standard menu bars 2110, 2120, as well as bottom and side toolbars 2140, 2150. Such menu- and toolbars contain a set of user-selectable icons, each icon being associated with one or more operations or functions, as known in the art. Some of these icons are associated with software tools, adapted for editing and/or working on the 3D modeled object 2000 displayed in the GUI 2100. The software tools may be grouped into workbenches. Each workbench comprises a subset of software tools. In particular, one of the workbenches is an edition workbench, suitable for editing geometrical features of the modeled product 2000. In operation, a designer may for example pre-select a part of the object 2000 and then initiate an operation (e.g. change the dimension, color, etc.) or edit geometrical constraints by selecting an appropriate icon. For example, typical CAD operations are the modeling of the punching or the folding of the 3D modeled object displayed on the screen.

[0066] The GUI may for example display data 2500 related to the displayed product 2000. In the example of FIG. 2, the data 2500, displayed as a “feature tree”, and their 3D representation 2000 pertain to a brake assembly including brake caliper and disc. The GUI may further show various types of graphic tools 2130, 2070, 2080 for example for facilitating 3D orientation of the object, for triggering a simulation of an operation of an edited product or render various attributes of the displayed product 2000. A cursor 2060 may be controlled by a haptic device to allow the user to interact with the graphic tools.

[0067] FIG. 5 shows an example of the system, wherein the system is a client computer system, e.g. a workstation of a user.

[0068] The client computer of the example comprises a central processing unit (CPU) 1010 connected to an internal communication BUS 1000, a random access memory (RAM) 1070 also connected to the BUS. The client computer is further provided with a graphical processing unit (GPU) 1110 which is associated with a video random access memory 1100 connected to the BUS. Video RAM 1100 is also known in the art as frame buffer. A mass storage device controller 1020 manages accesses to a mass memory device, such as hard drive 1030. Mass memory devices suitable for tangibly embodying computer program instructions and data include all forms of nonvolatile memory, including by way of example semiconductor memory devices, such as EPROM, EEPROM, and flash memory devices; magnetic disks such as internal hard disks and removable disks; magneto-optical disks; and CD-ROM disks 1040. Any of the foregoing may be supplemented by, or incorporated in, specially designed ASICs (application-specific integrated circuits). A network adapter 1050 manages accesses to a network 1060. The client computer may also include a haptic device 1090 such as cursor control device, a keyboard or the like. A cursor control device is used in the client computer to permit the user to selectively position a cursor at any desired location on display 1080. In addition, the cursor control device allows the user to select various commands, and input control signals. The cursor control device includes a number of signal generation devices for input control signals to system. Typically, a cursor control device may be a mouse, the button of the mouse being used to generate the signals. Alternatively or additionally, the client computer system may comprise a sensitive pad, and/or a sensitive screen.

[0069] The computer program may comprise instructions executable by a computer, the instructions comprising means for causing the above system to perform the method. The program may be recordable on any data storage medium (for instance, in a container thereon), including the memory of the system. The program may for example be implemented in digital electronic circuitry, or in computer hardware, firmware, software, or in combinations of them. The program may be implemented as an apparatus, for example a product tangibly embodied in a machine-readable storage device for execution by a programmable processor. Method steps may be performed by a programmable processor executing a program of instructions to perform functions of the method by operating on input data and generating output. The processor may thus be programmable and coupled to receive data and instructions from, and to transmit data and instructions to, a data storage system, at least one input device, and at least one output device. The application program may be implemented in a high-level procedural or object-oriented programming language, or in assembly or machine language if desired. In any case, the language may be a compiled or interpreted language. The program may be a full installation program or an update program. Application of the program on the system results in any case in instructions for performing the method.

[0070] “Designing a 3D modeled object” designates any action or series of actions which is at least part of a process of elaborating a 3D modeled object. Thus, the method may comprise creating the 3D modeled object from scratch. Alternatively, the method may comprise providing a 3D modeled object previously created, and then modifying the 3D modeled object.

[0071] The method may be included in a manufacturing process, which may comprise, after performing the method, producing a physical product corresponding to the modeled object. In any case, the modeled object designed by the method may represent a manufacturing object. The modeled object may thus be a modeled solid (i.e. a modeled object that represents a solid). The manufacturing object may be a product, such as a part, or an assembly of parts. Because the method improves the design of the modeled object, the method also improves the manufacturing of a product and thus increases productivity of the manufacturing process.

[0072] The method allows getting high quality textured 3D meshes, without artifact (relatively), even in the case of an inaccurate 3D mesh as input. The method takes into account that in general the projective texture mapping algorithm cannot perfectly texture an inaccurate 3D model, even with a perfect calibration and pose estimation of the camera. Besides, it is very hard to directly optimize the inaccurate 3D model itself using only a single texture. The algorithm used by the method optimizes the texture coordinates in order to correct the visible artifacts of the texture mapping. Thus, the algorithm of the method handles inaccurate 3D models as well as distortions in the input texture. The optimization is based on a discrete energy formulation, which is more efficient and faster than a continuous one. It also avoids the numerous poor local minima where continuous optimizations fall in due to the very high dimension of parameters' space (typically higher than 10,000 in the context of the later detailed examples).

[0073] In examples, every visible vertex of the 3D model is assigned a texture coordinate on the texture, easily computed by projective texture mapping (which is merely a projection of the 3D model onto the image according to the mapping provided at 10). The texture coordinate is a 2D vector, which can usually be called a UV coordinate. Each UV coordinate (of each visible vertex) can then be adjusted with a discrete optimization, so that the image better fits the projected 3D model. In examples, the method sees a (e.g. triangular) 3D mesh as a 3D graph, where each vertex is a node, and each edge connecting two vertices is an edge in the graph. The discrete energy optimization is written as a Markov Random Field inference based on this 3D graph. Each node can take several labels representing a displacement of the UV coordinate (i.e. pixel shifts). In the discrete energy formulation, each node has its own data term, representing the conditional probability of this node to take a specific label knowing (in examples) its curvature and the edges (high gradient contours) of the input texturing image. Moreover, the Markov Random Field also contains what can be called a “smoothness term”, which represents the probability of a node to take a specific label, knowing the labels of its neighbors in the graph. This term enforces neighboring nodes to have close labels. Thus this discrete energy formulation can also be seen as a MAP (Maximum A Posteriori) inference problem within a probabilistic framework, and the method aims at finding the most likely labeling. Briefly, this optimization tends in particularly efficient examples to adjust the UV coordinates of each visible vertex so that a high curvature vertex projects onto an edge in the input image, and so that neighboring vertices have similar UV coordinates displacements. The former criterion is similar to the one retained in application EP13306576.3 of 18 Nov. 2013 in the name of DASSAULT SYSTEMES, and it is retained here for the same reasons. The latter criterion is a newly formulated criterion and not proves relevant in the context of 3D reconstruction but it also makes the application of MRF theory and its computational efficiency advantages available.

[0074] The method builds from the idea of having a camera pose for the picture intended to texture a possibly inaccurate model. FIG. 6 shows two major levels of the global texture 3D reconstruction pipeline implemented by an example of the method. The first level consists in reconstructing the 3D scene with RGB or RGB-Depth sensors: extrinsic camera parameters are then provided with a 3D mesh model. These techniques are largely described in the earlier-cited literature. The second level (i.e. the core originality of the method) is dedicated to texture coordinates optimization for the texturing process. In other words, FIG. 6 shows a global process overview in two levels, with LEVEL 1 designating 3D Reconstruction of the scene, and LEVEL 2 designating an Automatic Texturing of 3D Model. The following discussion will thus mainly focus on the description of the texture coordinates optimization process (i.e. step S20, or LEVEL 2-A of FIG. 6). The overall algorithm of the example is divided on these major steps: 1/Pre-process: robust curvatures extraction on the 3D model and distance transform computation on the image; 2/Optimization process: i) Build the graph, ii) Optimize the Markov Random Field.

[0075] Unlike state of the art approaches, the solution of the method allows high quality texturing using only an inaccurate 3D mesh model as input and a calibrated input image which may be distorted, as provided by common 3D reconstruction algorithms, and this in a fast manner. The solution of the method performs in examples particularly well if the 3D model contains a lot of edges, notably when it is based on the curvature of the 3D points. The solution of the method performs in examples particularly well with high resolution images. The solution of the method performs in examples particularly well if there are a lot of edges on the image, and if the objects on the image do not have a high color variance. The solution of the method performs in examples particularly well with contrasted images, because the solution may in examples detect strong gradients on the image. The solution of the method can in examples handle distorted meshes or images, unlike texturing processes based on camera pose optimization.

[0076] It is noted that the method builds on well-known mathematical results known from the study of Markov Random Fields. For example, the developments that have led to the method make use of the Hammersley-Clifford theorem. It is also noted that MRF theory has already been used in the field of image processing. However, previous applications see images as a grid of all image pixels, said grid defining the underlying graph of the MRF application. However, the method does not base the MRF on such a grid of pixels, but rather on a graph corresponding to the 3D mesh (i.e. the 3D mesh is seen as a graph, with a label assigned to each vertex and a conditional probability assigned to the edges). Furthermore, the MF results are here applied to 3D mesh texturing in specific. Thus, efficiency results of MRF are here smartly applied to the context of 3D reconstruction and 3D texturing.

[0077] The inputs provided at S10 are now discussed.

[0078] As known from the prior art, a real object may be represented by a CAD system in 3D with different data structures that correspond to different geometries. In the case of the method, the 3D representation (which may also be called “3D model” in the following) provided at S10 is a 3D mesh representation, well known from the prior art. Prior art 3D reconstruction techniques provide such a discrete 3D representation, as known. Examples of such techniques generally include performing measurements on a real object with sensors, and inferring the discrete 3D representation from the measurements. The technique may be a structure-from-motion analysis, meaning that multi-view images of the real object are captured to infer the discrete 3D representation via a mathematical model. The first approach (only RGB data) and the second approach (RGB and depth data) presented in the prior art constitute structure-from-motion analysis foreseen for the method. The discrete 3D mesh representation may also be obtained by laser triangulation, and/or acoustic propagation analysis, combinations of different techniques being also foreseen.

[0079] In the case of a structure-from-motion analysis consisting of 3D Reconstruction from RGB images, the method may comprise matching interest 2D points between images. Then the method may calibrate the cameras, e.g. by estimating the position relative to the observed scene (extrinsic calibration) and estimate physical parameters of the sensors (e.g. focal, distortion—intrinsic calibration). Then the method may triangulate the match point with calibration data to estimate 3D positions (e.g. point cloud generation). Then the method may build a 3D mesh model from all 3D triangulated points, thereby reaching the discrete 3D representation. Reference is made to previously cited papers Hartley and Zisserman, Szeliski, and Faugeras for details on the above steps.

[0080] In the case of a structure-from-motion analysis consisting of 3D Reconstruction from RGB-Depth, the method may mainly use depth images (i.e. image that contains disparity information for each pixel). The method may first build the 3D scene from a first depth image (i.e. 3D point cloud generation from disparity values). The method may then, for each new depth image, estimate extrinsic camera calibration (e.g.—rotation and translation—of camera from previous point of view). The method may update the global 3D point cloud. The method may finally generate a 3D mesh model from point cloud analysis, thereby reaching the discrete 3D representation. Reference is made to previously cited papers Cui et al. and Newcombe et al. for details on the above steps.

[0081] The 3D mesh and the mapping, and possibly the texturing image, may thus result from applying such a technique, within the method or prior to the method. The system may thus comprise at least one sensor coupled to the processor to provide sensing measurements, the system comprising instructions in its programs to determine the discrete 3D mesh representation according to the measurements. Preferably, the system comprises at least one depth sensor, such that the method may perform depth measurements that output a relatively accurate 3D representation of the real object. This is known from the prior art, as discussed earlier.

[0082] The texturing image is a 2D view of the real object comprising texturing information, such as an RGB image/photograph of the real object, as known from the prior art. It is noted that the 3D mesh may correspond to a visible part of the real object of which the texturing image is a photo. A view of the real object is any graphical representation of the real object, such as an image, a photo, a picture. A 2D view is thus a 2D representation allowing the viewing of the real object from only one angle/point of view, as opposed to the definition of 3D representation provided earlier. The providing of the texturing image may generally be performed independently of the providing of the 3D mesh, e.g. concomitant, prior or after. In the case of the method, the 2D view provided at S10 is calibrated. A calibrated view is one that is provided together with information (“calibration information”) that allows the correspondence between positions on the 2D view and positions in a corresponding 3D representation, i.e. the 3D mesh representation provided at S10 here: this is the mapping provided at S10. For example, such information may comprise camera parameters, which are parameters that represent the configuration of a camera having captured the 2D view (possibly virtually). In other words, the camera parameters constitute information that allow an a posteriori description of a camera that could have captured the texturing image, relative to the 3D representation. The method may perform such calibrating of the texturing image, relative to the 3D mesh representation provided at S10, by computing beforehand said camera parameters, or by improving a beforehand calibration of the 2D view by computing camera parameters that are more accurate (in other words, by optimizing the previous camera parameters), such as in application EP13306576.3 of 18 Nov. 2013 in the name of DASSAULT SYSTEMES.

[0083] In the case the discrete 3D mesh representation provided at S10 is an output of a structure-from-motion analysis, the 2D view (i.e. texturing image) of the real object may be captured during this structure-from-motion analysis. In other words, structure from motion analysis may be used for the providing S10 of the 3D mesh, involving at least one 2D view, e.g. an RGB image, and said 2D view may efficiently be the texturing image provided at S10. Indeed, the structure-from-motion analysis, based on at least one 2D view as input, outputs data describing projection from the discrete 3D representation onto the input texturing image. However, although the 2D texturing image view is calibrated in this case (i.e. positions of the 2D view correspond to positions of the 3D mesh representation according to the calibration information, as they both correspond to the real positions of the real object when performing the structure from motion analysis), said calibration data is not perfectly accurate, and the method may therefore advantageously counterbalance such error via the optimization of the texture coordinates performed S20. This is particularly true in the case the 3D representation of the real object is provided by reconstructing the 3D representation from measurements of at least one depth sensor. In such a case indeed, the depth data are mainly used for determining the 3D representation, and 2D data, such as RGB images, are mainly used for other purposes (such as texturing the 3D representation). For this reason, the texturing image may be captured by a high resolution camera (providing data with at least higher resolution than the depth sensor or other cameras capturing images used to reconstruct the initial 3D representation). Thus, although the 2D view is captured by a camera synchronous to the depth sensor, there may be a shift leading to a lack of accuracy, as explained above. The method therefore leads to a more accurate final texturing.

[0084] Camera parameters that may form the mapping provided at 10 are now further discussed.

[0085] These camera parameters allow the correspondence between positions on the 2D texturing image/view and positions in the 3D mesh representation provided at S10. The camera parameters are thus associated to the texturing image, and relative to the 3D mesh provided at S10. For that, the camera parameters may include a projection matrix (e.g. describing projection from the 3D representation to the 2D view). The projection matrix may be based on a referential associated to the 3D representation and on a referential associated to the 2D view. As known, the projection matrix may include extrinsic parameters, such as 3D position of point of view, e.g. camera position, and/or orientation, e.g. rotation and translation data, and/or intrinsic parameters, such as focal length, skew parameter, principal point, and/or distortion parameters. The intrinsic parameters are parameters related to the sensor (e.g. focal, optical center projection, distortion) and are generally estimated in the prior art by an offline process as defined in the paper by Z. Zhang, “A Flexible New Technique for Camera Calibration”, in International Conference on Computer Vision 1999. The extrinsic parameter, also called “pose parameters”, are related to the position (e.g. rotation matrix and translation vector) of the image in the referential of the 3D scene (here the 3D reconstructed model). A classical way to estimate these pose parameters known from the prior art is to approximate them during a reconstruction process such as the ones mentioned above, as in RGB-Depth based reconstruction (such as described in the previously mentioned paper by Izadi et al), where RGB pose is deduced from depth camera positioning. This is made possible because both sensors (RGB and depth) are rigidly connected, that so there is only relative transformation to change referential axis.

[0086] A specific example of the method in line with the example of FIG. 6 is now discussed with reference to FIGS. 7-15. In this example, the 3D mesh, the texturing image and the mapping may all be outputted by a predetermined structure-from-motion analysis scheme applied on the real object as explained above. The mapping may thus correspond to pose camera parameters determined for the texturing image in the structure-from-motion analysis. This allows an efficient and accurate 3D reconstruction with texturing.

[0087] This example builds from the idea of having possibly an approximate 3D triangular mesh, with a calibrated (intrinsic parameters+translation/rotation of the camera at the time when the image was taken) image to use for texturing. The following discussion focuses on the description of the texture coordinates optimization process (—LEVEL 2-A of FIG. 6), detailed in FIG. 7, which shows an flowchart description of the optimization for accurate texturing implemented by the example of the method. The algorithm of the example is divided in these major steps:

[0088] 1) Pre-processing: robust curvatures extraction on the 3D model, and distance transform computation on the 2D image.

[0089] 2) Optimization process:

[0090] i. Build the graph.

[0091] ii. Optimize the Markov Random Field.

[0092] In the example, the method first computes 3D point visibility with pose-camera. The first step is indeed to extract all the visible vertices of the mesh (in case the 3D mesh includes more than vertices visible on the texturing image). This is done very easily with a low-level graphics API, such as OpenGL or DirectX. These API provide a Z-buffer algorithm, usually hardware-implemented. The Z-buffer algorithm provides a depth map of the mesh for a given camera pose. Then, the method may use this depth map to check if a vertex of the mesh is visible or not. To do so, the method may simply project all vertices of the mesh onto the depth map, and for each vertex compare its depth with the value of the depth map at the pixel location of the projected vertex. If both values are close enough, the vertex is considered visible by the method.

[0093] The method of the example then extracts 3D primitives on the 3D mesh. The method may use here the same method as described in application EP13306576.3 of 18 Nov. 2013 in the name of DASSAULT SYSTEMES in order to compute the highest curvature value at each visible vertex of the mesh. FIG. 8 shows a photo corresponding to a given 3D mesh (not shown) and high curvature vertices 80 of the 3D mesh (i.e. vertices having a maximum curvature higher than a predetermined threshold) and low curvature vertices 82 (i.e. vertices having a maximum curvature lower than the predetermined threshold) highlighted on the photo in different colors.

[0094] Indeed, in the example, the optimization S20 is performed with a predetermined relation between vertices of the 3D mesh and pixels of the texturing image that amounts to a predetermined relation between 3D curvature values for a vertex of the 3D mesh and distance values to a nearest contour of the texturing image for a pixel of the texturing image. The mapping provided at S10 is supposed to indicate location of a 3D vertex of the 3D mesh on the texturing image. However, as mentioned earlier, the method corrects such location with S20, based on an evaluation during the optimization S20 (via cost function φ_i′), of an extent to which a predetermined relation between values of a first function evaluated at vertices of the 3D mesh and values of a second function (corresponding to the first function) evaluated at pixels of the texturing image is respected. Any way to evaluate the “extent of respect” itself may be implemented, such as a normalized difference between said two values. The “relationship” is any form of mathematical relationship, and it may be symmetrical relationship. The aim is to evaluate if a pixel shift retained in the predetermined list of pixel shifts will lead to coherency (rules for such coherency being predefined) between features of the 3D vertex and features of the shifted texturing coordinate, and more specifically how high the incoherency would be. The method of the example implements a specific example of such “extent of respect” evaluation detailed later. Such predetermined relation forms pre-knowledge related to the texturing image and the real object represented by the 3D mesh to texture, and may thereby depend on the application.

[0095] In the case of the example, the method considers a predetermined relation between 3D curvature values for a vertex of the 3D mesh (e.g. a maximum 3D curvature value at a vertex) and values related to the 2D gradient in the texturing image (e.g. distance values to a nearest contour of the texturing image for a pixel of the texturing image, a “contour” being as known a zone of the texturing image, e.g. a line, of high gradient that may be determined by any known predetermined scheme). In specific, the predetermined relation may be a decreasing function of the 3D curvature relative to said distance (that is, 3D vertices of high maximal curvature should be relatively close to contours of the texturing image). The method of the example uses a specific implementation of such a predetermined relation detailed later. This allows an optimization that takes well account of the context of having a texturing image and a real object, particularly if in the case of a structure-from-motion analysis. This is because a fold on the real object will generally result in a high curvature in the 3D representation (and thus occurrence of the geometric feature of the example) and it will generally result in a high gradient in the 2D view. Other predetermined relations may however be contemplated. For example, the pixel gradient of the texturing image may be directly considered. Other geometric features (not necessarily related to 3D curvature) and/or other graphic features (not necessarily related to pixel gradient) could be contemplated, as mentioned application EP13306576.3 of 18 Nov. 2013 in the name of DASSAULT SYSTEMES. Indeed, the method proves useful whatever the predetermined relation between the 3D vertices and the 2D pixels used (as long as such predetermined relation is a relevant one), because the method achieves an additional optimization layer with the computational advantages of discrete MRF solving.

[0096] Referring to FIG. 9 which illustrates curvature estimation of a point on a triangular mesh, let x denote a 3D point on the mesh and {x1 . . . xn} its immediate neighbors, implying that for every point in {x1, xn} there exists an edge in the mesh leading to x. Let {y1 . . . yn} denote the x-translated set of neighbors, so that x becomes the origin. Let Z be the normal of the mesh at point x. If it does not yet exist, the method may average normals of neighboring triangles. The method may then assume an arbitrary direction X normal to Z and complete the orthonormal basis by Y=ẐX. We call {z, z1 . . . zn}, the projected set {x, x1 . . . xn} in the new base. The surface within the set is then estimated by a least square fitting paraboloid, from which the method deduces a curvature and direction at point z estimation. Following the orthogonal basis, one can describe the paraboloid with (a,b,c) so that: z=ax²+bxy+cy²

[0097] The least-square method on coefficients a, b and c yields:

$\left(a,b,c\right)=\underset{a^{\prime },b^{\prime },c^{\prime }}{\mathrm{argmin}}\sum _{i=1}^n{\left(z_i\left(3\right)-\left(a^{\prime }{z_i\left(1\right)}^2+b^{\prime }z_i\left(1\right)z_i\left(2\right)+c^{\prime }{z_i\left(2\right)}^2\right)\right)}^2$

[0098] Let X be the n*3 matrix whose row i equals to (zi(1)², zi(1)zi(2), zi(2)²) and J the n-sized vector (zi(3))i. Then the linear least-square solution is:

$\left(\begin{array}{c}a\\ b\\ c\end{array}\right)={\left(X^TX\right)}^{-1}X^TJ$

[0099] As the surface of the example is regular, the principal curvatures are the Eigen values to the hessian matrix H. The mean curvature m is defined as the sum of the two principal curvatures, i.e. m=tr(H). The Gaussian curvature g being the product of the two principal curvatures, g=det(H).

$\mathrm{Since}H=\left(\begin{array}{cc}2a& b\\ b& 2c\end{array}\right),m=2\left(a+c\right)\mathrm{and}g=4\mathrm{ac}-b^2.$

[0100] Let c1 and c2 be the Eigen values of H at x. By definition m=c1+c2 and g=c1c2. Let Δ=m²−4 g, and we get:

$c1=\frac{m+\sqrt{\Delta }}{2}\mathrm{et}c2=\frac{m-\sqrt{\Delta }}{2}$

[0101] Obvious bounds to the surface curvature at x are [min(c1,c2); max(c1,c2)]. Therefore the curvature of highest value at x is approximated by max(|c1|,|c2|). The curvature at x may be considered to be equal to this value.

[0102] The above described the pre-processing that determines 3D curvature at vertices (later in order to evaluate the extent to which the predetermined relation is respected). As mentioned above however, the specific evaluation of the example of the method also requires distance values to a nearest contour of the texturing image for a pixel of the texturing image: the “distance transform”. Such distance transform can be computed as follows.

[0103] Let I be a RGB image (e.g. the texturing image), and S={x1, . . . , xN} be a subset of pixels of I. The distance transform of I given S is an image whose intensity of each pixel is its distance to S, i.e. the distance to the closest pixel of S. The method may use Chamfer masks to speed-up the computation of the distance transform. Chamfer masks allow approximate but still accurate and fast distance transform computation. Chamfer masks described in the following paper may in particular be implemented: M. Stencel et al, “On Calculation of Chamfer Distance and Lipschitz Covers in Digital Images”, in S4G 2006. Briefly, the idea is to use a small mask, which applied to a pixel gives an approximate of the distance of the neighboring pixels to it. The method may start with distance 0 for pixels of S, and infinity for the other pixels. The method may do a forward-backward pass applying a Chamfer mask, i.e. the method may start from upper left to bottom right for the forward pass, and from the bottom right to the upper left for the backward pass. For each pixel, the method may apply the Chamfer mask, and replace the distance of its neighbors if the chamfer mask returns smaller distances.

[0104] The goal in the example is to compute an image where each pixel has for value the distance to the closest edge of the input RGB image. The first step in the example is to convert the RGB image to a gray-level image. Then, the method of the example may apply a Canny edge detector to obtain the contour image, as widely known from the field of image processing, and for example as described in the paper J. F. Canny, “A Computational Approach to Edge Detection”, in IEEE PAMI 1986, to extract the edges of the image. Briefly, the Canny edge detector smoothens the image, computes the gradient at each pixel (norm+direction), suppresses the non-maximum gradient values, and finally applies a hysteresis thresholding.

[0105] The pixels belonging to these edges form a set noted S, and the method of the example may finally apply a distance transform to the texturing image, given S. Results are shown by FIGS. 10-12 which respectively show an input image that may be provided at S10 (FIG. 10), the edges detected by the Canny edge detector (FIG. 11), and the distance transform computed by Chamfer mask (FIG. 12).

[0106] Discussion on STEP2: Optimization

[0107] Discussion on sub-step i of optimization: Build the Markov Random Field

[0108] An example of how to build the graph underlying the MRF is first presented for a triangular 3D mesh provided at S10. Generalization of the example is straightforward.

[0109] Let V={v₁, . . . , v_n} be the set of the visible vertices of the 3D model, and N(v_i)={v_j1, . . . , v_jm(v1)} be the neighboring vertices of v_i, where m(v_i) is the number of neighbors of v_i

[0110] The method of the example defines the undirected graph G=(V,E), where E={{v_i,v_j}|i,jε{1, . . . , n}, v_jεN(v_i)}. E is the set of all the edges connecting two visible vertices in the 3D model. Let F={{v_i, v_j, v_k}|i, j, kε{1, . . . , n}, v_jεN(v_i), v_kεN(v_i), v_kεN(v_j)} be the set of all the visible triangles of the mesh

[0111] Each node v_i of the graph can take a label L(v_i) from a set L={l₁, . . . , l_h}. In the case of the example, L is the set of the allowed shifts/displacements of the texture coordinates in pixels. The method of the example takes L={(0,0), (0,1), (1,0), (1,1), (−1,0), (0,−1), (−1,−1), (−1,1), (1,−1)} which gives 9 labels. The method could also allow two pixels displacements (25 labels) or even more, but the computation speed greatly increases as the number of labels is kept low. Instead of increasing the number of labels in the case where the distortion of the mesh is important, the method may cut/reduce the resolution of the input image and keep 1 or 2 pixels shifts as allowed labels. L(v_i) is a random variable. A labeling L(V)=(L(v₁), . . . , L(v_n)) is a random variable which assigns a label to every node in the graph G. Notice that the label (0,0) for a vertex is a zero displacement of its texture coordinate, and so corresponds merely to the texture coordinate computed by the texture projection mapping algorithm, i.e. projection of the vertex onto the image according to the sole mapping provided at S10.

[0112] Each node v_i has a probability P(L(v_i)=l_a) to take a label l_a. The method assumes that v_i is conditionally independent of v_j given v_i's neighbors. This hypothesis is called the Markov property. A graph with this property is called a Markov Random Field (MRF). The edges of the graph G thus represent the dependencies between the nodes. The labels of two nodes are directly dependent if they share an edge.

[0113] The Hammersley-Clifford theorem states that if an undirected graph G satisfies the Markov property, the probability distribution P(L(V)) can be factorized over all the maximal cliques (complete subgraphs) of the graph. If the mesh is manifold, the maximal cliques of the present graph are merely the triangles of the mesh. So

$P\left(L\left(V\right)\right)=\frac{1}{Z}{\prod }_{\left\{\mathrm{vi},v_jv_k,\right\}\in F}{\psi }_{i,j,k}\left(L\left(v_i\right),L\left(v_j\right),L\left(v_k\right)\right).$

[0114] Of course, we want to involve the 3D mesh and the texturing image provided at S10, called here the observations, in the probabilistic framework. The method of the example has computed the distance transform of the input image, and the curvatures of the vertices. So we have an a priori for each label given the observations O of the distance transform and the curvatures, called a likelihood, and noted

$P\left(O|L\left(V\right)\right)=\prod _{i=1}^nP\left(O|{L\left(V\right)}_i\right)=\prod _{i=1}^nP\left(O|L\left(v_i\right)\right)=\frac{1}{z^{\prime }}\prod _{i=1}^n{\varphi }_i\left(L\left(v_i\right)\right).$

[0115] Finally, we get what can be called a MAP (maximum a posteriori) inference problem. We want to find the most likely labeling L(V′) knowing the curvatures and the distance transform of the input image, meaning L(V′)=argmax_L(V) P(L(V)|O).

[0116] Bayes' rule immediately gives that L(V′)=argmax_L(V) Π_i=1ⁿ P(O|L(v_i))×P(L(V)).

[0117] We can rewrite it

L(V′)=argmin_L(V)Σ_i=1ⁿ−log(φ_i(L(v_i))+Σ_{{vj,xjvk,}εF}−log(ψ_i,j,k(L(v_i),L(v_j),L(v_k)))+log(Z)+log(Z′)=argmin_L(V)Σ_i=1ⁿφ_i′(L(v_i))+Σ_{{vi,vj,vk,}εF}ψ_i,j,k′(L(v_i),L(v_j),L(v_k)), where φ_i′=−log(φ_i) and ψ_i,j,k′=−log(ψ_i,j,k).

[0118] Eventually we have rewritten the inference problem as a discrete optimization problem.

[0119] Notice that:

P(L(V)|O∝exp(−Σ_i=1ⁿφ_i′(L(v_i))−Σ_{{vi,vjvk,}εF}ψ_i,j,k′(L(v_i),L(v_j),L(v_k))).

[0120] φ′ may be called the data term, because it links the label of a vertex to the observations, independently of the labels of the other nodes. ψ′ may be called the smoothness term, because it enforces a regularity in the labels of neighboring nodes, it links the label of a node to its neighbors.

[0121] This Markov Random Field (MRF) is a high order MRF because the cliques have a size greater than 2. This means that the smoothness term cannot be generally factorized on the edges. High order MRFs require specific optimization methods. Nevertheless, nothing prevents the method to specifically define the smoothness term such as it can be factorized on the edges of the graph, and thus get a pairwise MRF for which there exists a larger number of inference methods.

[0122] For example, the predetermined MRF solving scheme may belong to one of these four well-known classes of pairwise MRF solving algorithms:

• • [0123] Convex Relaxation MRF solving schemes (e.g. Linear Programming (Schlesinger 1976), Semidefinite Programming (Lasserre 2000), or Second-Order Cone Programming (Muramatsu and Suzuki, 2003)).
  • [0124] Dual of the Linear Programming Relaxation MRF solving schemes (e.g. Tree Reweighted Message Passing, Dual Decomposition).
  • [0125] Graph Cut MRF solving schemes (e.g. Alpha Expansion, Alpha-Beta Swap, FastPD).
  • [0126] Belief Propagation MRF solving schemes (e.g. Loopy Belief Propagation, Generalized Belief Propagation).

[0127] These are however only examples, as any pairwise MRF solving scheme in general may be implemented by the method. It is also noted that the four classes provided above are not exclusive one of another, the classification depending on the adopted point of view.

[0128] So, as indicated, the cost function ψ_f′ is written in the example to be of the form: ψ_f′({L(v_i)}_iεf)=Σ_{i,j}εp(f)ψ_i,j′(L(v_i),L(v_j)), where p(f) designates the set of pairs of indices of vertices of tile f.

[0129] This allows the use of a pairwise discrete Markov Random Field optimization scheme at S20 and thus of faster performance.

[0130] In the example, as detailed hereunder, ψ_i,j′(L(v_i),L(v_j)) is specifically of the form

$\frac{\lambda }{3}({L\left(v_i\right)-L\left(v_j\right)}_1,$

where λ designates a positive scalar. λ may be superior to 0.01 and/or inferior to 0.1, e.g. approximately 0.05. Trial and error can be used to retain a best value, according to the application. Other distances may be contemplated (such as Euclidian distance).

[0131] Now, the method of the example implements a predetermined relation wherein 3D curvature values Ci lower (e.g. or equal) than a predetermined threshold C (that may, for a 3D mesh of edges of 1 millimeter order, be superior to 0.01 and/or inferior to 0.1, e.g. approximately 0.05, with a possible trial and error for adjustment) are in the predetermined relation with all distance values (noted T_i(L(v_i))), and 3D curvature values (e.g. strictly) higher than the predetermined threshold C are in the predetermined relation with distance values according to an increasing one-to-one correspondence. This means that, according to the very definition of such predetermined relation, when the 3D curvature is lower than the threshold any value of the distance transform is suitable, meaning that that the extent to which the relation is respected is the same for all values of the distance transform for such vertices. On the other hand, for high curvature values (above the threshold), the predetermined is a monotonous (increasing) function of the 3D curvature with respect to the distance transform value T_i(L(v_i))), an example of which is provided hereunder. The optimization thus focuses on the information conveyed by high curvature vertices only.

[0132] In particular, an implementation that works well is where φ_i′ is of the form

${\varphi }_i^{\prime }\left(L\left(v_i\right)\right)=1_{C_i>c}\frac{\gamma }{C_i}-T_i\left(L\left(v_i\right)\right){\mathrm{.1}}_{C_i>c}$

designates an indicator function, with Ci designating the 3D curvature of vertex v_i and c thus designating a positive scalar, γ designating a predetermined positive scalar (that may be superior to 0.01 and/or inferior to 0.5, e.g. approximately 0.25, with a possible trial and error for adjustment), and T_i(L(v_i)) designating—again—the value of the relevant distance transform of the texturing image (that is, at the result of applying the pixel shift, selected during the exploration of the possible arguments for the optimization program, for vertex v_i, after mapping vertex v_i on the texturing image), the distance transform being as mentioned earlier relative to the contour image of the texturing image pre-computed beforehand.

[0133] In other words, let T_i(x,y) be the distance transform of the input image, at pixel K(v_i)+(x,y), where K(v_i) is the projection of the vertex v_i onto the input image, i.e. the initial texture coordinate of v_i, and C_i the max curvature of the vertex v_i.

[0134] Then we define

${\varphi }_i^{\prime }\left(L\left(v_i\right)\right)=1_{C_i>c}\frac{\gamma }{C_i}-T_i\left(L\left(v_i\right)\right)$

where γ is a positive scalar which links curvatures to pixelic distances, c a positive scalar chosen to discard the low curvatures vertices in the data term.

[0135] We define φ_i,j,k′(L(v_i),L(v_j),L(v_k))=λ(∥L(v_i)−L(v_j)∥₁+∥L(v_j)−L(v_k)∥₁+∥L(v_i)−L(v_k)∥₁, where λ is a positive scalar which controls the tradeoff between the smoothness term and the data term. We can notice that ψ_i,j,k′(L(v_i),L(v_j),L(v_k))=ψ_i,j′(L(v_i),L(v_j))+′_i,k′(L(v_i),L(v_k))+ψ_j,k′(L(v_j),L(v_k)), where

${\psi }_{i,j}^{\prime }\left(L\left(v_i\right),L\left(v_j\right)\right)=\frac{\lambda }{3}{L\left(v_i\right)-L\left(v_j\right)}_1,$

and thus we get a pairwise MRF, which is easier to optimize than a higher order MRF.

[0136] In the case of the example, the data term forces strong curvature vertices to have a texture coordinate close to an edge in the input texture, and the smoothness term forces neighboring vertices to get a similar displacement in their texture coordinate.

[0137] It is important to notice that the method could be implemented with other expressions for both terms. In particular, ψ_i,j,k′ could be a general higher order term.

[0138] Also, the example of cost function φ_i′(L(v_i)) is just an example, as any cost function tending to press/shift 3D vertices of high maximal curvature towards high gradient (i.e. contours) of the texturing image may be implemented.

[0139] Discussion on sub-step ii of optimization: Optimize the Markov Random Field

[0140] The last step of the example is to solve the inference problem to find the best labeling, and thus the optimized texture coordinates.

[0141] There are a lot of different efficient algorithms to solve such an inference problem on a pairwise Markov Random Field, especially when the smoothness term is a metric distance. Any algorithm provided in J. Kappes et al, “A Comparative Study of Modern Inference Techniques for Discrete Minimization Problems”, in CVPR 2013 may be implemented. In case the method would replace ψ_i,j,k′ by a general higher order term, algorithms described in H. Ishikawa, “Higher-Order Clique Reduction in Binary Graph Cut”, in CVPR 2009 could be implemented.

[0142] FIG. 13 illustrates schematically the overall performance of the method of the example for a house real object based on texturing image 130, thus improving accuracy of the final texturing of the house from the result of FIG. 14 to the result of FIG. 15.

[0143] The teachings of all patents, published applications and references cited herein are incorporated by reference in their entirety.

[0144] While this invention has been particularly shown and described with references to example embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the scope of the invention encompassed by the appended claims.