Direct quad-dominant meshing of point cloud via global parameterization

In this paper, we present a new algorithm for quad-dominant meshing of unorganized point clouds based on periodic global parameterization. Our meshing method is guided by principal directions so as to preserve the intrinsic geometric properties. We use local Delaunay triangulation to smooth the initial principal directions and adapt the global parameterization to point clouds. By optimizing the fairness measure we can find the two scalar functions whose gradients best align with the guided principal directions. To handle the redundant vertices in the iso-lines due to overlapped triangles, an approach is specially designed to clean the iso-lines. Our approach is fully automatic and applicable to a surface of arbitrary genus. We also show an application of our method in curve skeleton extraction from incomplete point cloud data.     

Adaptive triangular-mesh reconstruction by mean-curvature-based refinement from point clouds using a moving parabolic approximation

We use a moving parabolic approximation (MPA) to reconstruct a triangular mesh that approximates the underlying surface of a point cloud from closed objects. First, an efficient strategy is presented for constructing a hierarchical grid with adaptive resolution and generating an initial mesh from point clouds. By implementing the MPA algorithm, we can estimate the differential quantities of the underlying surface, and subsequently, we can obtain the local quadratic approximants of the squared distance function for any point in the vicinity of the target shape. Thus, second, we adapt the mesh to the target shape by an optimization procedure that minimizes a quadratic function at each step. With the objective of determining the geometrical features of the target surface, we refine the approximating mesh selectively for the non-flat regions by comparing the estimated curvature from the point clouds and the estimated curvatures computed from the current mesh. Finally, we present various examples that demonstrate the robustness of our method and show that the resulting reconstructions preserve geometric details.     

An efficient solder joint defects method for 3D point clouds with double-flow region attention network

In electronics mass-production, image-based methods are often used to detect the solder joint defects for achieving high-quality assurance with low labor costs. Recently, deep learning in 3D point clouds has shown an effective form of characterization for 3D objects. However, existing work rarely involves defect detection for PCBs based on 3D point clouds. In this paper, we propose a novel neural network named double-flow region attention network (DoubRAN) to detect defects of solder joints with 3D point clouds. On the one hand, a binocular lidar system is designed to efficiently capture 3D point clouds of solder joints. On the other hand, a fine-grained method named region attention network (RAN) is designed to detect defects, which attends on the region of interest directly by backpropagation without bounding box annotation. To evaluate the performance of our proposed network, we conduct extensive experiments on a unique dataset built by ourselves. The experimental results show that the region of interest extracted by RAN is consistent with the basis for human evaluation of solder joint quality. Besides, the defect detection results of DoubRAN meet factory requirements.     

Moving parabolic approximation of point clouds

Using moving parabolic approximations (MPA), we reconstruct an improved point-based model of curve or surface represented as an unorganized point cloud, while also estimating the differential properties of the underlying smooth manifold. We present optimization algorithms to solve these MPA models, and examples which show that our reconstructions of the curve or surface, and estimates of the normals and curvature information, are accurate for precise point clouds and robust in the presence of noise.     

An evaluation of pose-normalization algorithms for point clouds introducing a novel histogram-based approach

Building Information Modeling is growing more relevant as digital models are not only used during the construction phase but also throughout the building’s life cycle. The digital representation of geometric, physical and functional properties enables new methods for planning, execution and operation. Digital models of existing buildings are commonly derived from surveying data such as laser scanning which needs to be processed either manually or automatically throughout various steps. Aligning point clouds along the coordinate system’s main axes (also commonly known as pose normalization) is a task benefitting any point cloud processing workflow, be it manual or automated. With the goal of automating this task, we compare various existing methods and present our own approach based on point density histograms. We conclude this paper by comparing and discussing all methods in terms of speed and robustness.     

Skeleton-based intrinsic symmetry detection on point clouds

We present a skeleton-based algorithm for intrinsic symmetry detection on imperfect 3D point cloud data. The data imperfections such as noise and incompleteness make it difficult to reliably compute geodesic distances, which play essential roles in existing intrinsic symmetry detection algorithms. In this paper, we leverage recent advances in curve skeleton extraction from point clouds for symmetry detection. Our method exploits the properties of curve skeletons, such as homotopy to the input shape, approximate isometry-invariance, and skeleton-to-surface mapping, for the detection task. Starting from a curve skeleton extracted from an input point cloud, we first compute symmetry electors, each of which is composed of a set of skeleton node pairs pruned with a cascade of symmetry filters. The electors are used to vote for symmetric node pairs indicating the symmetry map on the skeleton. A symmetry correspondence matrix (SCM) is constructed for the input point cloud through transferring the symmetry map from skeleton to point cloud. The final symmetry regions on the point cloud are detected via spectral analysis over the SCM. Experiments on raw point clouds, captured by a 3D scanner or the Microsoft Kinect, demonstrate the robustness of our algorithm. We also apply our method to repair incomplete scans based on the detected intrinsic symmetries.     

An extension on robust directed projection of points onto point clouds

Azariadis and Sapidis [Azariadis PN, Sapidis NS. Drawing curves onto a cloud of points for point-based modelling. Computer-Aided Design 2005;37(1):109-22] introduced a novel method of point directed projection (DP) onto a point cloud along an associated projection vector. This method is essentially based on an idea of least sum of squares by making use of a weight function for bounding the influence of noise. One problem with their method is the lack of robustness for outliers. Here, we present a simple, robust, and efficient algorithm: robust directed projection (RDP) to guide the DP computation. Our algorithm is based on a robust statistical method for outlier detection: least median of squares (LMS). In order to effectively approximate the LMS optimization, the forward search technique is utilized. The algorithm presented here is better suited to detect outliers than the DP approach and thus finds better projection points onto the point cloud. One of the advantages of our algorithm is that it automatically ignores outliers during the directed projection phase.     

An adaptive normal estimation method for scanned point clouds with sharp features

Normal estimation is an essential task for scanned point clouds in various CAD/CAM applications. Many existing methods are unable to reliably estimate normals for points around sharp features since the neighborhood employed for the normal estimation would enclose points belonging to different surface patches across the sharp feature. To address this challenging issue, a robust normal estimation method is developed in order to effectively establish a proper neighborhood for each point in the scanned point cloud. In particular, for a point near sharp features, an anisotropic neighborhood is formed to only enclose neighboring points located on the same surface patch as the point. Neighboring points on the other surface patches are discarded. The developed method has been demonstrated to be robust towards noise and outliers in the scanned point cloud and capable of dealing with sparse point clouds. Some parameters are involved in the developed method. An automatic procedure is devised to adaptively evaluate the values of these parameters according to the varying local geometry. Numerous case studies using both synthetic and measured point cloud data have been carried out to compare the reliability and robustness of the proposed method against various existing methods.     

Distributed data organization and parallel data retrieval methods for huge laser scanner point clouds

This paper proposes a novel method for distributed data organization and parallel data retrieval from huge volume point clouds generated by airborne Light Detection and Ranging (LiDAR) technology under a cluster computing environment, in order to allow fast analysis, processing, and visualization of the point clouds within a given area. The proposed method is suitable for both grid and quadtree data structures. As for distribution strategy, cross distribution of the dataset would be more efficient than serial distribution in terms of non-redundant datasets, since a dataset is more uniformly distributed in the former arrangement. However, redundant datasets are necessary in order to meet the frequent need of input and output operations in multi-client scenarios: the first copy would be distributed by a cross distribution strategy while the second (and later) would be distributed by an iterated exchanging distribution strategy. Such a distribution strategy would distribute datasets more uniformly to each data server. In data retrieval, a greedy algorithm is used to allocate the query task to a data server, where the computing load is lightest if the data block needing to be retrieved is stored among multiple data servers. Experiments show that the method proposed in this paper can satisfy the demands of frequent and fast data query.     

Automatic least-squares projection of points onto point clouds with applications in reverse engineering

A novel method for projecting points onto a point cloud, possibly with noise, is presented based on the point directed projection (DP) algorithm proposed by Azariadis P., Sapidis N. [Drawing curves onto a cloud of points for point-based modelling. Computer-Aided Design 2005; 37(1): 109–22]. The new method operates directly on the point cloud without any explicit or implicit surface reconstruction procedure. The presented method uses a simple, robust, and efficient algorithm: least-squares projection (LSP), which projects points onto the point cloud in a least-squares sense without any specification of the projection vector. The main contribution of this novel method is the automatic computation of the projection vector. Furthermore, we demonstrate the effectiveness of this approach through a number of application examples including thinning a point cloud, point normal estimation, projecting curves onto a point cloud and others.     

保特征的点云骨架提取算法

三维模型的骨架提取是计算机图形学中一个重要的研究方向。对于有噪声的点云模型,曲线骨 架提取的难点在于保持正确的拓扑结构以及良好的中心性;对于无噪声的点云模型,曲线骨架提取的难点在于 对模型细节特征的保留。目前主流的点云骨架提取方法往往无法同时解决这 2 个难点。算法在最优传输理论的 基础之上结合聚类的思想,将点云骨架提取的问题转化为一个最优化问题。首先使用最优传输得到原始点云与 采样点云之间的传输计划。然后使用聚类的思想将原始点云进行分割,采样点即成为了簇的中心。接着通过簇 与簇之间的调整与合并减少聚类个数,优化聚类结果。最后通过迭代的方式得到粗糙的骨架并使用插点操作进 行优化。大量实验结果表明,该算法在有噪声与无噪声的三维点云模型上均能提取出质量良好的曲线骨架并保 留模型的特征。     

ASM: An adaptive simplification method for 3D point-based models

Due to the popularity of computer games and computer-animated movies, 3D models are fast becoming an important element in multimedia applications. In addition to the conventional polygonal representation for these models, the direct adoption of the original scanned 3D point set for model representation is recently gaining more and more attention due to the possibility of bypassing the time consuming mesh construction stage, and various approaches have been proposed for directly processing point-based models. In particular, the design of a simplification approach which can be directly applied to 3D point-based models to reduce their size is important for applications such as 3D model transmission and archival. Given a point-based 3D model which is defined by a point set P () and a desired reduced number of output samples n^s, the simplification approach finds a point set P_s which (i) satisfies |P_s|=n^s (|P_s| being the cardinality of P_s) and (ii) minimizes the difference of the corresponding surface S_s (defined by P_s) and the original surface S (defined by P). Although a number of previous approaches has been proposed for simplification, most of them (i) do not focus on point-based 3D models, (ii) do not consider efficiency, quality and generality together and (iii) do not consider the distribution of the output samples. In this paper, we propose an Adaptive Simplification Method (ASM) which is an efficient technique for simplifying point-based complex 3D models. Specifically, the ASM consists of three parts: a hierarchical cluster tree structure, the specification of simplification criteria and an optimization process. The ASM achieves a low computation time by clustering the points locally based on the preservation of geometric characteristics. We analyze the performance of the ASM and show that it outperforms most of the current state-of-the-art methods in terms of efficiency, quality and generality.     

An approach to combine progressively captured point clouds for BIM update

Building information models (BIMs) provide opportunities to serve as an information repository to store and deliver as-built information. Since a building is not always constructed exactly as the design information specifies, there will be discrepancies between a BIM created in the design phase (called as-designed BIM) and the as-built conditions. Point clouds captured by laser scans can be used as a reference to update an as-designed BIM into an as-built BIM (i.e., the BIM that captures the as-built information). Occlusions and construction progress prevent a laser scan performed at a single point in time to capture a complete view of building components. Progressively scanning a building during the construction phase and combining the progressively captured point cloud data together can provide the geometric information missing in the point cloud data captured previously. However, combining all point cloud data will result in large file sizes and might not always guarantee additional building component information. This paper provides the details of an approach developed to help engineers decide on which progressively captured point cloud data to combine in order to get more geometric information and eliminate large file sizes due to redundant point clouds.     

一种基于RANSAC的点云特征线提取算法

点云中提取的特征线在点云处理中具有重要的应用价值,已被应用于对称性检测、表面重建及点云与图像之间的注册等。然而,已有的点云特征线提取算法无法有效地处理点云中不可避免的噪声、外点和数据缺失,而随机采样一致性RANSAC由于具有较高的鲁棒性,在图像和三维模型处理中具有广泛的应用。为此,针对由建筑物或机械部件等具有平面特征的物体扫描得到的点云,提出了一种基于RANSAC的特征线提取算法。本算法首先基于RANSAC在点云中检测出多个平面,然后将每个平面参数化域的边界点作为候选,在这些候选点上再应用基于全局约束的RANSAC得到最终的特征线。实验结果表明,该算法对点云中的噪声、外点和数据缺失具有很强的鲁棒性。     

Detection of closed sharp edges in point clouds using normal estimation and graph theory

The reconstruction of a surface model from a point cloud is an important task in the reverse engineering of industrial parts. We aim at constructing a curve network on the point cloud that will define the border of the various surface patches. In this paper, we present an algorithm to extract closed sharp feature lines, which is necessary to create such a closed curve network. We use a first order segmentation to extract candidate feature points and process them as a graph to recover the sharp feature lines. To this end, a minimum spanning tree is constructed and afterwards a reconnection procedure closes the lines. The algorithm is fast and gives good results for real-world point sets from industrial applications.     

Iso-parametric tool-path planning for point clouds

Due to the compute-intensiveness and the lack of robustness of the algorithms for reconstruction of meshes and spline surfaces from point clouds, there is a need for further research in the topic of direct tool-path planning based on point clouds. In this paper, a novel approach for planning iso-parametric tool-path from a point cloud is presented. Since such planning falls into the iso-parametric category, it intrinsically depends on the parameterization of point clouds. Accordingly, a point-based conformal map is employed to build the parameterization. Based on it, formulas of computing path parameters are derived, which are much simpler than the conventional ones. By regularizing parameter domain and on the basis of the previous formulas, boundary conformed tool-path can be generated with forward and side step calculated against specified chord deviation and scallop height, respectively. Experimental results are given to illustrate the effectiveness of the proposed methods.     

Adaptive feature-conserving compression for large scale point clouds

In this work, we introduce a practical method for reducing big point clouds of buildings and infrastructure. The proposed method introduces bilateral filtering with a tailored set of evaluation functions to conserve maximum information. The statistical parameters necessary for our model are selected by examining various point properties of a comprehensive dataset. The dataset contains artificial, photogrammetric and laser-scanned point clouds and has been made publicly available. For verification, we showcase our filtering method by preserving more information than voxel grid or density filters, enabling even sparser photogrammetric datasets. Finally, we discuss some encoding strategies as well as the best balance between size and resolution.     

基于EM-ICP的三维人脸简化点云并行配准算法

提出了一种基于离散曲率估计和kd-tree简化人脸点云的并行EM-ICP配准算法.首先建立人脸点云的三维空间kd-tree,并结合离散高斯曲率对点云进行了保留几何特征的简化;然后基于CUDA对EM-ICP算法进行并行加速,对简化的人脸点云进行配准.该算法能够避免局部配准等缺陷,同时EM-ICP算法并行保证了配准工作的高效.实验证实了本文算法的健壮性和稳定性.     

三维点云法向量估计综述

由于获取方便、表示简单、灵活等优势,点云逐渐成为常用的三维模型表示方法之一。法向量作为点云必不可少的属性之一,其估计方法在点云处理中具有重要的位置。另一方面,由于点云获取过程中不可避免的噪声、误差和遮挡,点云中通常含有噪声、外点和空洞,并且部分采样模型如CAD模型,也会存在尖锐特征,这些都给法向量估计提出了挑战。对当前已有的点云法向量估计算法进行综述,分析其原理及关键技术,着重分析它们在处理噪声、外点和尖锐特征等方面的能力并给出比较,最后为未来研究提供了一些建议。     

Automatic segmentation of unorganized noisy point clouds based on the Gaussian map

A nonparametric clustering algorithm, called cell mean shift (CMS), is developed to extract clusters of a set of points on the Gaussian sphere . It is computationally more efficient than the traditional mean shift (MS). Based on the singular value decomposition, the dimensional analysis is introduced to classify these clusters into point-, curve-, and area-form clusters. Each cluster is the Gaussian image of a set of points which will be examined by a connected search in . An orientation analysis of the Gaussian map to area-form clusters is applied to identify hyperbolic and elliptical regions. A signed point-to-plane distance function is used to identify points of convex and concave regions. Segmentation results of several real as well as synthetic point clouds, together with complexity analyses, are presented.