“Machine learning is the science of getting computers to act without being explicitly programmed. In the past decade, machine learning has given us self-driving cars, practical speech recognition, effective web search, and a vastly improved understanding of the human genome.” Andrew Ng.
Surface reconstruction is an important trend in 3D scanning. The problem is to recreate surfaces from a given point cloud within the shortest possible time and with a given quality criteria. There is a set of different approaches for solving this problem, which includes Self-Organized Maps, Bayesian reconstruction and Poisson reconstruction.
The aim of the research is to find the most suitable method based on Machine Learning unsupervised learning techniques for reconstruction of interior and exterior 3D scans of original objects. The self-organizing map type of the artificial neural network was chosen due to its ability to produce good results without restrictions on point cloud size and points’ order. It can generate meshes from a small number of point samples in an unorganized point cloud.
The purpose of this article highlight a paper, “Surface Reconstruction Based on Neural Networks” that analyzes and compares results obtained with the usage of two self-organizing map types – Surface Growing Neural Gas (sGNG) and Growing Cell Structures (GCS) reconstruction – for reconstruction of a 3D mesh from point cloud. In addition, the sGNG extension to multithreading is presented and compared to the original approach.
sGNG is a reconstruction algorithm based on GNG with a large number of improvements. Our implementation is based on Fast Growing Neural Gas (FGNG), which is written in C++, works fast and has a convenient API. The algorithm has been modified and the results are post-processed for removing unexpected holes. The most important changes are: the process of activity update, triangle creation and triangle flip, additional triangle creation and modified edge split. Activity of the best matching vertex allows to detect regions where vertex density is lower than the density of the input points. Updating activity of vertex has been modified. Instead of incrementing activity values for each vertex in the list on every iteration, it has been decided to store iteration number of last activity for each vertex. The main idea is to compare current iteration number with vertex last activity iteration number, and remove it if it doesn’t satisfy condition. This changes the complexity of the algorithm updating vertices activity from O(N) to O(1). Complexity of vertex removal stays the same. Triangle creation, triangle flip and additional triangle creation have been added to the algorithm to improve the smoothness of the surface and prevent the occurrence of non-2-manifold edges. Edge splitting has been modified by performing the split in the middle of the longest edge instead of the middle of the edge connected with its most active neighbor.
Reconstruction algorithm based on GCS is modified by replacing edge split and vertex removal with vertex split and edge collapse, as the last ones work better in 3D space. Also, adjusting vertex position by linear combination with a sample and Laplacian tangential neighbor smoothing improve the quality of the mesh and prevent the surface from stacking to a local minimum or folding over.
The parallel computation of the nearest neighbor was added to both algorithms, to improve the speed for the huge number of vertices.
The main bottleneck of the neural networks of this type is the Nearest Neighbor Search that is performed at each iteration. Various approaches were introduced to perform this operation faster.
The basic approach is to iterate over all nodes at the current neural network state and compute their distances to the input sample. This algorithm introduces O(N) complexity at each iteration. Although the algorithm could be boosted by CUDA, the data transfers required for node deletion and mesh improvement techniques (triangle flip, edge flip, etc.) at each iteration make the CUDA-based NN Search even slower than the CPU-based one.
Another NN Search approach, R-Tree, introduces better complexity O(log N). The use of this sparse tree data structure provides significant improvement in NN Search according to the tests. The disadvantage of R-Tree is the complex structure, making the task of implementation on the GPU challenging. Although the GPU-based R-Tree approaches exist, they outperform the CPU-based one only at data sets larger than 1,000,000 points.
The main issue of the approaches mentioned above is their dependency on the number of nodes. This problem was partially solved in Growing Uniform Grid Structure. The NN Search query complexity is close to constant with the O(N) complexity in the worst case. Although it requires O(N) for growth, the number of growth phases decreases significantly during the increase of nodes. Due to the fact that the NN search query examines very small amount of points, addition of the CUDA improvements is useless.
The other way to improve performance of the reconstruction process is to use Message Passing Interface technology. We combined multithreading and MPI, to check out how it can improve reconstruction speed on large point clouds.
The research demonstrates that Self-Organizing Maps are suitable for 3D Surface Reconstruction. The testing shows that GCS approach provides comparable results only on meshes that are not difficult, while the sGNG approach reconstructs meshes with a huge number of small details very well. The sGNG approach is advisable to use for reconstruction in most cases when the vertex normals are unimportant. The GCS showed inferior results but it could be useful for reconstruction of meshes with the correct vertex normals for further processing. PCL Poisson algorithm works faster, but the quality of reconstruction is unsuitable, so it could be used only for previewing of the target mesh.
To get more information on these algorithms performance and check visual examples, download the full document in PDF from the insideBIGDATA White Paper Library, courtesy of AMC Bridge.
Sign up for the free insideBIGDATA newsletter.
Speak Your Mind