|
CGAL 6.1 - Kinetic Surface Reconstruction
|
Loading...
Searching...
No Matches
|
CGAL 6.1 - Kinetic Surface Reconstruction
|
Reconstruction of man-made objects from point clouds pose a challenge to traditional surface reconstruction methods that often produce a smooth surface, e.g., by meshing a fitted implicit function, see Poisson Surface Reconstruction, or by interpolation, see Advancing Front Surface Reconstruction and Scale Space Surface Reconstruction. The kinetic surface reconstruction package implements the pipeline proposed by Bauchet et. al [1]. At the core is the Kinetic space partition which efficiently decomposes the bounding box into a set of convex polyhedra. The decomposition is guided by a set of planar shapes which are aforehand abstracted from an input point cloud. The final surface is obtained via an energy formulation trading data faithfulness for low complexity which is solved via min-cut. The output is a polygonal watertight mesh.
The method overcomes the major limitation of similar approaches which decompose the bounding box using planar shapes. By partitioning the space into fewer cells using the kinetic approach and aforehand splitting of input data via an adaptive octree the method beats the common full decomposition of the bounding box which has a complexity of \(O(n^3)\). This allows for effective handling of large scenes. At the same time the kinetic approach of decomposing the bounding box limits the number of tiny cells in the partition. Tiny cells are often responsible for small artifacts and at the same time increase the memory requirements and running time.
The method takes as input a point cloud with oriented normals, see Figure 69.1. In a first step, Shape Detection is used to abstract planar shapes from the point cloud. The optional regularization of shapes, see Shape regularization, can not just improve the accuracy of the data by aligning parallel, coplanar and orthogonal shapes, but provides in the same time a reduction in complexity. Before inserting the planar shapes into the kinetic space partition, coplanar shapes are merged into a single shape and the 2d convex hull of each shape is constructed. The reconstruction is posed as an energy minimization labeling the convex volumes of the kinetic space partition as inside or outside. The optimal surface separating the differently labeled volumes is found via min-cut. A graph is embedded into the kinetic partition representing every volume by a vertex and every face between to volumes by an edge connecting the corresponding vertices.
\(\DeclareMathOperator*{\argmin}{arg\,min} \argmin\limits_{l \in {\{0, 1\}}^n} E(l) = (1 - \lambda) D(l) + \lambda U(l)\) \(D(l) = \sum\limits_{i \in C}\sum\limits_{p \in I_i}d_i(p, l_i)\) \(U(l) = \frac{I}{A}\sum\limits_{i\mathtt{\sim} j}a_{ij} \cdot (1-\delta_{l_i,l_j})\) | The energy function trads data term for regularization term via parameter \(\lambda\) The data term counts votes from the points \(p \in I_i\) based on their associated normal pointing towards or away from each volume \(i \in C\). The regularization term penalizes the total surface area and thus favors surfaces with low complexity. |
The labels \(l \in {\{0, 1\}}^n\) denote the label for the \(n\) volumes of the kinetic space partition. The data term measures the coherence of the labeled volumes with the orientation of normals of the input points. The preferred label for a volume is determined by a voting of the input points and their associated normals. For each volume \(i \in C\) the inliers from the shape detection associated with the faces of the volume \(I_i\) either vote inside or outside for the volume. The vote is inside \(d_i(p, inside) = 1\) and \(d_i(p, outside = 0)\) if the normal associated to the point is directed to the outwards of the volume or outside \(d_i(p, inside) = 0\) and \(d_i(p, outside = 1)\) if the normal is oriented inwards. The regularization term is penalizing the total surface area of the surface and thus favoring less complex surfaces. To put the data term and regularization term into balance, area of each face is normalized by the total area of all faces \(A\) and scaled by twice the total number of inliners \(I\) from the shape detection as each inlier counts as one inside and one outside vote.
Thus the reconstruction is guaranteed to be watertight as it equals a union of volumes. However, the reconstruction may consist of several components and is not guaranteed to be 2-manifold as different components may share a vertex or an edge.
Figure 69.1 Kinetic surface reconstruction pipeline.
From left to right: 1. input point cloud with 382k points 2. 98 detected planar shapes 3. 63 regularized convex shapes 4. kinetic space partition with 1,487 cells 5. reconstructed polygonal mesh with 131 faces.
The parameters of the method include the parameters from other packages which are used internally:
The reconstruction adds two new parameters:
reconstruct_with_ground estimates a ground plane within the detected shapes and sets up all faces on the bounding box below that ground plane to be connected to an external node set as inside while all other faces on the outside are connected to external nodes set to outside. It assumes the z-axis to be the upward pointing vertical direction.The kinetic space partition determines all possible reconstructions as the energy formulation only decides about the labels for the volumes, but cannot change the volumes themselves. Thus, the first stages of the pipeline, Shape Detection and Shape Regularization, have a large impact on the final reconstruction. In the simple case of a cube, one missing side would depending on the chosen lambda parameter either make the cube expand on that side towards the bounding box or make the full cube disappear. A proper parameterization of the Shape Detection to detect all relevant shapes may have a large impact. The debug parameter allows to export intermediate results for inspection. This is especially helpful for larger scenes, where the time for the whole reconstruction requires more computational effort.
However, in many cases a point cloud may be incomplete and not cover all shapes. The method offers two parameters to handle missing data. The k parameter of the kinetic space partition can extend the convex polygons further in the partition and thus may make up for missing shapes. The external_nodes parameter allows to preset an inside or outside label for bounding box sides. This is especially helpful for scanned buildings, where no points have been collect on the bottom side of the building, partial scans or scans where the orientation is inverted, e.g., inside an apartment.
The lambda parameter allows to trade data faithfulness for low complexity. The best choice depends on the individual point cloud and the sampled object. Figure 69.2 shows the lower complexity of the reconstruction with a higher lambda value. However, the actual reconstruction using min-cut only makes up a small fraction from the whole pipeline. Performing several reconstructions with different values of lambda is a reasonal approach, see Parameters Example.
Figure 69.2 Impact of parameters on the reconstruction of the rotated lans model.
From left to right: 1. & 2. Reconstruction with using \(\lambda = 0.7\) and \(\lambda = 0.8\). A higher value of lambda removes some details on the roof as well as the chimney. As no planar shape was detected at the top of the chimney, the kinetic space partition does not offer a volume that well covers the point cloud. The volume of the chimney is either too large for \(\lambda = 0.7\) or gets cut completely for \(\lambda = 0.8\) 3. Reconstruction of the model without reorienting the bbox. For the reconstruction to succeed it is necessary to set the external_node for ZMIN to inside as the point cloud does not close the church from below. 4. Reconstruction as in 3., but without setting external_node for ZMIN.
This minimal example shows the import of a simple synthetic point cloud and an reconstruction using mostly default parameters.
File Kinetic_surface_reconstruction/ksr_basic.cpp
This example shows the import of an acquired point cloud of a building and a reconstruction using a common choice of parameters for building reconstruction. The input point cloud is reoriented to be axis-aligned and regularization is used to simplify the detected shapes before reconstruction. The actual reconstruction method is actually fast. To avoid running the full shape detection and kinetic partition just to try different values for beta, several reconstructions are performed and exported into ply format.
File Kinetic_surface_reconstruction/ksr_building.cpp
This example provides a command line version of the kinetic surface reconstruction allowing to configure the input point cloud filename and most parameters.
File Kinetic_surface_reconstruction/ksr_parameters.cpp
Kinetic surface reconstruction is aimed at reconstructing piece-wise planar objects, e.g., man-made objects and architecture. Reconstruction results on point clouds acquired from architecture in different qualities are shown in figure Figure 69.3 in the first and last row. Synthetic point clouds from a CAD model and a fractal object are shown in rows 2 and three. The datasets used here are available at https://files.inria.fr/titane/KSR42_dataset.zip.
However, also smooth surfaces can be reconstructed to a certain level of detail as is shown on the fourth row. While the scales of the dragon are not replicated with their smooth boundary, each scale can still be recognized in the final model.
Figure 69.3 Results of kinetic surface reconstruction.
From left to right: 1. input point cloud 2. reconstructed polygon mesh 3. overlay of input and result 4. detail view.
From top to bottom: 1. Meeting room. Reconstruction of the roof framework is not perfect due to missing data. 2. Full Thing. Synthetic point cloud sampled from a CAD model. All details are well reconstructed 3. Hilbert cube. Synthetic point cloud from a fractal object. 4. Asian Dragon. Acquired point cloud from the Stanford 3D Scanning Repository. 5. Building_C. Point Cloud from multi view stereo.
The running time of the method depends mostly on the shape detection and the kinetic space partition steps. While running time of the shape detection scales with the complexity of the point cloud, the kinetic space partition depends on the number of input polygons. The running time of the shape regularization and the min-cut have not been listed, as they are <1 seconds in all cases besides the Asian Dragon with 2,75s for the min-cut.
| Data set | Points | Detected shapes | Regularized shapes | Volumes in partition | Polygons in reconstruction | Vertices in reconstruction | Shape Detection | Kinetic Space Partition | Total Time |
| Foam_box | 382.059 | 103 | 60 | 998 | 97 | 444 | 6,5 | 3,3 | 9,8 |
| Lans | 1.220.459 | 324 | 169 | 3.334 | 330 | 1.175 | 26,3 | 9,4 | 35,7 |
| Meeting Room | 3.074.625 | 1.652 | 777 | 29.605 | 2.867 | 11.819 | 37,1 | 93,4 | 131,1 |
| Full Thing | 1.377.666 | 1.947 | 1.790 | 21.804 | 2.655 | 12.984 | 8,6 | 238,8 | 248,2 |
| Hilbert cube | 144.092 | 968 | 48 | 5.778 | 986 | 4.124 | 0,6 | 10,5 | 11,1 |
| Asian Dragon | 3.609.455 | 2.842 | 2.842 | 101.651 | 10.209 | 34.237 | 31,2 | 757,5 | 790,7 |
| Building_C | 1.000.000 | 221 | 172 | 3.432 | 369 | 1.457 | 40,1 | 12,3 | 52,4 |
The parameters to reconstruct these models are available in the following table:
| Data set | Maximum distance | Maximum angle | Minimum region size | K nearest neighbors | Regularize parallelism Angle tolerance | Regularize coplanarity Maximum offset | K | Lambda | |
| Foam_box | 0,05 | 15 | 250 | 12 | 10 | 0,01 | 2 | 0,7 | |
| Lans | 0,15 | 20 | 300 | 12 | 8 | 0,08 | 2 | 0,7 | |
| Meeting Room | 0,03 | 19 | 100 | 15 | 10 | 0,03 | 3 | 0,5 | |
| Full Thing | 0,3 | 36 | 30 | 12 | 3 | 0,05 | 1 | 0,5 | |
| Hilbert cube | 0,3 | 10 | 10 | 12 | 5 | 0,03 | 4 | 0,5 | |
| Asian Dragon | 0,7 | 26 | 150 | 10 | 0 | 0 | 1 | 0,75 | |
| Building_C | 1,1 | 26 | 500 | 15 | 3 | 0,5 | 2 | 0,77 | |
This package is an implementation of Bauchet et. al [1]. A proof of concept of the kinetic surface reconstruction was developed by Dmitry Anisimov.
1.9.6