3D reconstruction of a structure of a real scene

Abstract

A computer-implemented method for 3D reconstruction of a structure of a real scene including obtaining a 3D point cloud representing the structure. The method further includes determining a closed triangulated surface representing a skin of the structure. The determining explores candidate closed triangulated surfaces each meshing at least a respective part of the 3D point cloud. The determining penalizes a high rank of the candidate closed triangulated surfaces according to a lexicographic order. The lexicographic order is based on a triangle order and orders a first candidate closed triangulated surface having first triangles which are ordered according to a decreasing rank of the triangle order, relative to a second candidate closed triangulated surface having second triangles which are ordered according to a decreasing rank of the triangle order. The triangle order penalizes a triangle size. This constitutes an improved method for 3D reconstruction of a structure of a real scene.

The invention claimed is: 
     
       1. A computer-implemented method for 3D reconstruction of a structure of a real scene, the method comprising:
 obtaining a 3D point cloud representing the structure; and 
 determining a closed triangulated surface representing a skin of the structure, the determining exploring candidate closed triangulated surfaces each meshing at least a respective part of the 3D point cloud and the determining penalizing a high rank of the candidate closed triangulated surfaces according to a lexicographic order, the lexicographic order being based on a triangle order and the lexicographic order ordering a first candidate closed triangulated surface having first triangles which are ordered according to a decreasing rank of the triangle order, relative to a second candidate closed triangulated surface having second triangles which are ordered according to a decreasing rank of the triangle order, the triangle order penalizing a triangle size, 
 wherein the triangle order penalizes, for a respective triangle, a high value of a radius of a smallest enclosing circle, and 
 wherein the triangle order further penalizes, for a first triangle and a second triangle having a same smallest enclosing circle, a value of a radius of a circumscribed circle. 
 
     
     
       2. The method of  claim 1 , wherein the candidate closed triangulated surfaces each include a respective set of triangle faces each of a respective tetrahedron of a tetrahedral meshing of the 3D point cloud. 
     
     
       3. The method of  claim 2 , wherein the tetrahedral meshing includes the following properties:
 a union of the tetrahedrons of the tetrahedral meshing forms the convex envelop of points of the 3D point cloud, and 
 an intersection between any first tetrahedron of the tetrahedral meshing and any second tetrahedron of the tetrahedral meshing intersecting the first tetrahedron is a vertex of the first tetrahedron, an edge of the first tetrahedron, or a face of the first tetrahedron. 
 
     
     
       4. The method of  claim 1 , wherein, the candidate closed triangulated surfaces each including a respective set of triangle faces each of a respective tetrahedron of a tetrahedral meshing of the 3D point cloud, the tetrahedral meshing is a regular triangulation. 
     
     
       5. The method of  claim 4 , wherein the exploring and the penalizing further including:
 visiting triangles of the tetrahedral meshing according to a decreasing rank of the triangle order, and 
 discarding visited triangles having a high rank of the triangle order. 
 
     
     
       6. The method of  claim 5 , wherein each tetrahedron of the tetrahedral meshing defines a respective region,
 wherein the determining further includes: 
 declaring an outside tetrahedron of the tetrahedral meshing and an inside tetrahedron of the tetrahedral meshing, the outside tetrahedron and the inside tetrahedron representing respectively an outside region of the structure and an inside region of the structure, and 
 wherein: 
 the visiting of the triangles includes, for each visited triangle, assessing whether the visited triangle separates an inside region from an outside region, and 
 the discarding of the triangles includes, for each visited triangle which does not separate an inside region from an outside region, the triangle separating two regions, suppressing the triangle and merging the two regions. 
 
     
     
       7. The method of  claim 6 , wherein each visited triangle separating an inside region from an outside region is kept, the kept triangles forming the determined closed triangulated surface. 
     
     
       8. The method of  claim 1 , wherein the determining includes providing a zone within the 3D point cloud representing an inside location of the structure, the candidate closed triangulated surfaces each encompassing the zone. 
     
     
       9. The method of  claim 1 , wherein the structure includes at least one corner structure. 
     
     
       10. The method of  claim 1 , wherein the 3D point cloud stems from photogrammetry, laser-scan, RGB-D measurements and/or medical or industrial tomography, and/or wherein the real scene is an architectural scene, a building interior scene, a mining scene, an organic tissue or a mechanical part. 
     
     
       11. A non-transitory computer readable storage medium having recorded thereon a computer program comprising instructions for performing a computer-implemented method for 3D reconstruction of a structure of a real scene, the method comprising:
 obtaining a 3D point cloud representing the structure; and 
 determining a closed triangulated surface representing a skin of the structure, the determining exploring candidate closed triangulated surfaces each meshing at least a respective part of the 3D point cloud and the determining penalizing a high rank of the candidate closed triangulated surfaces according to a lexicographic order, the lexicographic order being based on a triangle order and the lexicographic order ordering a first candidate closed triangulated surface having first triangles which are ordered according to a decreasing rank of the triangle order, relative to a second candidate closed triangulated surface having second triangles which are ordered according to a decreasing rank of the triangle order, the triangle order penalizing a triangle size, 
 wherein the triangle order penalizes, for a respective triangle, a high value of the radius of a smallest enclosing circle, and 
 wherein the triangle order further penalizes, for a first triangle and a second triangle having a same smallest enclosing circle, a value of the radius of a circumscribed circle. 
 
     
     
       12. The non-transitory computer readable storage medium of  claim 11 , wherein the candidate closed triangulated surfaces each include a respective set of triangle faces each of a respective tetrahedron of a tetrahedral meshing of the 3D point cloud. 
     
     
       13. The non-transitory computer readable storage medium of  claim 12 , wherein the tetrahedral meshing includes the following properties:
 a union of the tetrahedrons of the tetrahedral meshing forms the convex envelop of the points of the 3D point cloud, and 
 an intersection between any first tetrahedron of the tetrahedral meshing and any second tetrahedron of the tetrahedral meshing intersecting the first tetrahedron is a vertex of the first tetrahedron, an edge of the first tetrahedron, or a face of the first tetrahedron. 
 
     
     
       14. The non-transitory computer readable storage medium of  claim 11 , wherein the triangle order penalizes, for a respective triangle, a high value of the radius of a smallest enclosing circle. 
     
     
       15. A computer comprising:
 a processor coupled to a memory and a display, the memory having recorded thereon a computer program comprising instructions for performing 3D reconstruction of a structure of a real scene that when executed by the processor causes the processor to be configured to: 
 obtain a 3D point cloud representing the structure, and 
 determine a closed triangulated surface representing a skin of the structure, the determining exploring candidate closed triangulated surfaces each meshing at least a respective part of the 3D point cloud and the determining penalizing a high rank of the candidate closed triangulated surfaces according to a lexicographic order, the lexicographic order being based on a triangle order and the lexicographic order ordering a first candidate closed triangulated surface having first triangles which are ordered according to a decreasing rank of the triangle order, relative to a second candidate closed triangulated surface having second triangles which are ordered according to a decreasing rank of the triangle order, the triangle order penalizing a triangle size, 
 wherein the triangle order penalizes, for a respective triangle, a high value of the radius of a smallest enclosing circle, and 
 wherein the triangle order further penalizes, for a first triangle and a second triangle having a same smallest enclosing circle, a value of the radius of a circumscribed circle. 
 
     
     
       16. The computer of  claim 15 , wherein the candidate closed triangulated surfaces each include a respective set of triangle faces each of a respective tetrahedron of a tetrahedral meshing of the 3D point cloud. 
     
     
       17. The computer of  claim 16 , wherein the tetrahedral meshing includes the following properties:
 a union of the tetrahedrons of the tetrahedral meshing forms the convex envelop of the points of the 3D point cloud, and 
 an intersection between any first tetrahedron of the tetrahedral meshing and any second tetrahedron of the tetrahedral meshing intersecting the first tetrahedron is a vertex of the first tetrahedron, an edge of the first tetrahedron, or a face of the first tetrahedron. 
 
     
     
       18. The computer of  claim 15 , wherein the triangle order penalizes, for a respective triangle, a high value of the radius of a smallest enclosing circle.