Sage Journals: Discover world-class research

Abstract

This article presents a novel method for estimating normals on unorganized point clouds that preserves sharp features. 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 neighborhood reconstruction-based normal estimation method is developed to find a proper neighborhood for points around sharp features. A robust statistics-based method is proposed to identify points that near sharp features and classify the points into two categories: edge points and non-edge points. Two specific neighborhood reconstruction strategies are designed for these two types of points to generate a neighborhood clear of sharp features. The normal of the current point can thus be reliably estimated by principal component analysis using the generated isotropic neighborhood. Numerous case studies have been carried out to compare the reliability and robustness of the proposed method against various existing methods. The experiment results show that the proposed approach performs better than the state-of-the-art methods most of the time and offers an ideal compromise between precision, speed, and robustness.

Keywords

Normal estimation point cloud feature preserving neighborhood segmentation neighborhood growth

Introduction

Reliable estimation of the normals of point clouds is a crucial preprocessing operation. Numerous point clouds processing algorithms benefit from an accurate normal associated with each point. For example, many surface reconstruction algorithms require accurate normals as input in order to generate high-quality surfaces.^1,2 The performance of point-based rendering techniques is heavily depends on the accuracy of the input normal.^3,4 Many other applications of normal estimation can also be found in segmentation,⁵ smoothing,⁶ simplification,^7,8 shape modeling,⁹ and feature detection and extraction.^10,11

The points acquired by three-dimensional scanners are inevitably defect-ridden due to the precision limitation of scanning equipment and artifact in the scene. A good estimator should be robust to these defects, including noise, outliers, non-uniformities, and so on. Moreover, many captured scenes include human-made objects, which generally contain sharp features that have to be preserved and not smoothed.

Regression-based normal estimation methods^12–15 are most commonly employed. The methods estimate normal with the whole neighborhood centered at the point, which tend to smooth sharp features. Some robust statistics approaches^16–18 have been brought out to estimate consistent sub-neighborhoods to compute normals for feature preserving. However, some erroneous normals may still persist near the sharp features with anisotropic sampling or large dihedral angels. In recent years, segmentation-based approaches^19,20 are proposed to segment the anisotropic neighborhood into several isotropic sub-neighborhoods and select a consistent sub-neighborhood to estimate normals. The methods generate more faithful normals than previous methods but at the price of a long runtime.

In this article, a neighborhood reconstruction-based method is presented to estimate normals for unorganized point clouds with sharp features. Instead of using the whole neighborhood centering at the current point, the proposed method tries to locate a neighborhood containing the current point but clear of sharp features, which is usually not centering at the point. And the located neighborhood is then used for more faithful normal estimation. To this end, the points are first classified into edge points and non-edge points through robust statistics-based method. Then a neighborhood segmentation-based and a neighborhood growth-based method are proposed for edge points and non-edge points, respectively, to construct a neighborhood containing the current point but clear of sharp features. Finally, the normal can be accurately estimated by principal component analysis (PCA) using the constructed isotropic neighborhood. The experiments illustrate that the presented method can estimate normals accurately even in the presence of noise and anisotropic samplings, while preserving sharp features. The contributions of this article can be summarized as follows:

A robust statistics–based recognition method is proposed to identify points that near sharp features. The proposed method can accurately identify points near sharp features even in the presence of high level noise.

A specific strategy is devised to generate a set of isotropic candidate neighborhoods for each edge point, which makes the presented method effective.

A neighborhood growth strategy is proposed for each non-edge point to generate a neighborhood clear of edge points, which improves the reliability of normal estimation for non-edge point.

Related works

There has been a considerable amount of works on normal estimation which can be categorized into four types: regression based, mollification based, Delaunay/Voronoi based, and segmentation based. Regression-based methods are most widely employed. Hoppe et al.¹² (PCA) approximate a tangent plane at a given point by regression on its neighboring points. The normal of the point is defined as the eigenvector corresponding to the smallest eigenvalue of the covariance matrix of its neighbors. To better adapt to the shape of the underlying surface, some higher order algebraic surfaces such as spheres¹³ and quadrics¹⁴ are used to replace planes. Optimal neighborhood sizes can be computed to minimize the estimation error by analyzing local properties, such as curvature, noise, sampling density.¹⁵ However, all regression-based methods are actually low-pass filters and tend to smooth the normals at sharp features. Moreover, a higher robustness to outliers needs larger neighborhoods, which makes sharp features even smoother.

To improve the robustness to outliers and non-uniformity, Pauly et al.¹⁰ weaken some points’ influence to the regression by assigning Gaussian weights to the distances between current point and its neighbors when estimating the local plane. The method improves the robustness of normal estimation to outliers and non-uniformity. Khaloo and Lattanzi²¹ propose an improved Mahalanobis distance–based outliers detection method to find and discard outlier points prior to estimating the best local tangent plane around any point in a cloud. However, in Pauly et al.¹⁰ and Khaloo and Lattanzi,²¹ the neighborhood used to estimate the local plane still contains neighboring points from different surface patches than the patch current point belongs to when current point is very close to sharp features. Nurunnabi et al.²² estimate the best-fit-plane based on most probable outlier free, and most consistent, points set in a local neighborhood. The normal can thus be reliably estimated from the best-fit-plane. However, the method is computationally expensive and fails in detecting outliers in the presence of additive Gaussian noise.²³ Huang et al.²⁴ present an interesting resample-wPCA-based method in which an edge-aware resampling algorithm is used to generate denoised, outlier free and evenly distributed points. Then a sophisticated approach is employed to get reliable orientation for the normals computed by weighted PCA. The method is robust to noise and outliers. However, the output of this method is a new consolidated point cloud; thus, the normals corresponding to the original points are not computed. Li et al.¹⁶ (RNE) propose a robust normal estimation method by combining a robust local noise estimation and a kernel density estimation that is parameterized by the estimated noise scale. The method generates accurate normals near sharp features and is robust to the noise and outliers. Boulch and Marlet²⁵ (Hough transform (HF)) propose a uniform sampling technique to overcome the sampling non-uniformity. The method is based on the randomized Hough transform (RHT). The filled HF accumulator is viewed as an image of the discrete probability distribution of possible normal and the normal corresponds to the maximum of this distribution is selected. However, the normal will be blurred near the edge when the dihedral angle between the two planes is large. Instead of designing explicit criteria to select a normal from the accumulator, he then comes up with a decision procedure base on convolutional neural network (CNN).²⁶ The method is robust to noise, to outliers, and to density variation, in the presence of sharp edges. However, it is expensive to change the value of a parameter; the network has to be retrained when it needs to adapt specifically to the input data.

Since the preliminary normals are likely to be noisy or smoothed, normal mollification methods are studied to improve the initial normals. Algorithms such as moving least squares (MLS),³ adaptive versions⁹ locally approximate the surface with implicit surface. The normal is estimated as the gradient of the surface. Better normal can be obtained due to the good approximation ability of implicit surfaces. However, the surface approximations performed in a least square sense are sensitive to outliers, and still smooth out small or sharp features. To deal with this problem, Öztireli et al.¹ proposed a robust implicit moving least squares (RIMLS) algorithms which combine robust local kernel regression (LKR) techniques with implicit moving least squares (IMLS). Combining with statistics makes IMLS more robust in the presence of noise, outliers, and sparse sampling. Taking into account both positions and preliminary normals of the points, half-quadratic regularization²⁷ improves normals by selecting the nearest neighbors belonging to the same plane as current point. Bilateral filtering proposed by Jones et al.²⁸ also recovers sharp features while improve noisy normals. Normal mollification methods can obtain nearly correct normals for the points close to sharp features. However, as post-processing methods, all of them require reliable initial normal which at least roughly respecting sharp features. Otherwise, the mollification can only smooth noisy normals but is incapable to preserve sharp features.

Voronoi/Delaunay-based method is first introduced into normal estimation by Amenta and Bern.²⁹ The Voronoi diagram and the furthest vertex of the Voronoi cell are used to approximate the normals. The method preserves sharp features and can deal with density variation, but it works only for the noise-free point clouds. Dey and Goswami³⁰ extend the idea to noisy point clouds by finding big Delaunay balls. Also based on the Voronoi diagram, OuYang and Feng³¹ construct a local Voronoi mesh at each point and estimate the normal via fitting a group of quadric curves through which the directional tangent vectors could be obtained. The method also needs a noise-free point cloud though. In order to be robust to noise, Alliez et al.³² present a combination of PCA and Voronoi-based method that compute the covariance matrix of a Voronoi cell or a union of Voronoi cells in the noisy case. The method benefits from the local nature of PCA and the global partition quality of Voronoi-based approach, more stable normals can thus be obtained.

Recently, some neighborhood segmentation-based methods are proposed to determine consistent point clusters for a better normal estimation near sharp features. Fleishman et al.¹⁷ segment the local neighborhood of a point into multiple outlier-free smooth regions. Zhang et al.¹⁹ (low-rank representation (LRR)) segment the local neighborhood of a point into such clusters using low-rank subspace clustering with prior knowledge. The method yields accurate normal, even in the presence of noise and anisotropic samplings. However, the algorithm is too slow to employ it in practice, since it requires to solve a non-smooth optimization problem for each point near the sharp features. Liu et al.²⁰ address this issue using a different representation for subspaces and clustering only a subset of the points before propagating the results to adjacent points. The method is much faster while being as accurate as Zhang et al.’s method.¹⁹ But it can be seen from the experimental comparison of the article, its computational efficiency is still lower than other classical algorithms. Cao et al.³³ presented a fast and quality normal estimator based on neighborhood shift. Instead of using the neighborhood centering at the current point, a set of neighborhoods containing the current point are evaluated and the one with the most consistent normals is selected as the neighborhood of the current point. Two specific neighborhood shift operations to build faithful neighborhoods for points near different types of features are introduced. The method is robust to noise, to outliers, to non-uniform sampling, performed well near the edge, but to evaluating all candidate neighborhoods of a point with very large neighborhood may be impractical. Hence, the method may be not robust to large noise and some extreme cases when only small neighborhoods are explored.

Overview

Assuming that the point cloud $P = {p_{i}}_{i = 1}^{N}$ is sampled from piecewise smooth surfaces, $p_{i}$ is a point on this surface, and let $N_{i}$ be the neighborhood of $p_{i}$ . There are two basic cases as follows:

If $p_{i}$ lies far from any edge or sharp feature, as shown in Figure 1(a). Its neighborhood can be well approximated by a plane and the normal can thus be accurately estimated by PCA.

If $p_{i}$ lies near an edge partitioning the neighborhood $N_{i}$ into $N_{i . 1} \cup N_{i, 2}$ with $p_{i} \in N_{i, 1}$ as shown in Figure 1(b). Then it will result in inaccurate normal if apply PCA on the whole neighborhood directly. But both $N_{i . 1}$ and $N_{i . 2}$ could be well approximated by a plane; the normal can be accurately estimated with the neighborhood $N_{i . 1}$ that locates on the same surface patch as $p_{i}$ . This generalizes to situations where $p_{i}$ is close to several edges; in this case, more sub-neighborhoods are obtained, as shown in Figure 1(c).

Figure 1.

The structure of the neighborhood of points at different positions: (a) Point p_i lies far from any edge or sharp feature, (b) Point p_i lies near an edge and (c) Point p_i lies near a corner where several surface patches join together.

Based on this simple principle, this article presents an effective algorithm to identify a consistent neighborhood for each point near sharp features. Then, accurate normal can be estimated with the identified neighborhood. The algorithm consists of five phases: (1) for each point $p_{i}$ , K₀-nearest neighbor $N_{i}$ is computed and an initial normal vector is estimated by covariance analysis of $N_{i}$ . Then each point $p_{i}$ is identified as edge point or non-edge point according to the standard deviation of the normal vectors of p_i’s neighbors, which is detailed in section “Edge point recognition.” (2) For an edge point, a larger neighborhood of size $K_{1}$ is recalculate as $N_{i}$ , and an Euclidean distance clustering–based neighborhood segmentation strategy is designed to segment $N_{i}$ into several consistent sub-neighborhoods, which is explained in section “Neighborhood Segmentation.” Several reasonable candidate neighborhoods are constructed with a residual constrained neighborhood construction method, which is explained in sections “Candidate neighborhood construction” and “Dealing with features with close proximity.” (3) An evaluation criteria is presented, in section “Criteria for neighborhood selection,” to identify a neighborhood that locates on the same surface patch as $p_{i}$ from the candidate neighborhood set. (4) For each non-edge point, if there are no edge points in the neighborhood, the initial neighborhood $N_{i}$ is taken as its final consistent neighborhood ${\tilde{N}}_{i}$ . If its neighborhood contains edge points, then a neighborhood growth strategy is used to generate a new neighborhood clear of edge points, which is explained in section “Dealing with sampling anisotropy.” (5) Finally, a more accurate normal is estimated by PCA using the newly constructed neighborhood. The overview of presented method is illustrated in Figure 2.

Figure 2.

Pipeline of our algorithm.

Edge point recognition

PCA of the covariance matrix of a local neighborhood is widely used to estimate local surface properties, such as normal and curvature.⁷ For each point $p_{i}$ , a neighborhood $N_{i}$ of size $K_{0}$ is computed. The corresponding covariance matrix C is defined as

C = {[\begin{matrix} p_{1} - \bar{p} \\ \dots \\ p_{K_{0}} - \bar{p} \end{matrix}]}^{T} \cdot [\begin{matrix} p_{1} - \bar{p} \\ \dots \\ p_{K_{0}} - \bar{p} \end{matrix}], p_{i = 1, K_{0}} \in N_{i}

(1)

where $\bar{p}$ is the centroid of the set of neighbors in $N_{i}$ .

The eigenvalues ${λ_{0}, λ_{1}, λ_{2}}$ of the covariance matrix can be estimated by analyzing the following eigenvector problem

C \cdot {\bar{v}}_{j} = λ_{j} \cdot {\bar{v}}_{j}, j \in {0, 1, 2}

(2)

where ${v_{0}, v_{1}, v_{2}}$ are corresponding eigenvectors.

Assume that $λ_{0} < λ_{1} < λ_{2}$ , then the surface variation $σ_{i}$ of the underlying surface at point $p_{i}$ and an initial normal $n_{i}$ can be estimated. The surface variation $σ_{i}$ is defined as

σ_{i} = \frac{λ_{0}}{λ_{0} + λ_{1} + λ_{2}}

(3)

The normal $n_{i}$ is defined as the eigenvector $v_{0}$ corresponding to the smallest eigenvalue $λ_{0}$ .

In previous studies,^19,20,33 $σ_{i}$ is considered as a curvature and used to distinguish edge points, who have a more complicated neighborhood, from non-edge points. The coefficient of a point near sharp features is considered to be larger than that of a point in smooth regions. Therefore, each point $p_{i}$ with $σ_{i}$ greater than a threshold $σ_{τ}$ is viewed as an edge point.

However, it has been shown that PCA is sensitive to noise and outliers due to using classic covariance matrix. As a result, attributes calculated through PCA are highly sensitive to noise and outliers.³⁴ Figure 3 shows the results of edge point identification under different noise levels using above curvature-based method. For each point cloud and noise level, the curvature threshold $σ_{τ}$ is set to the optimal value. It can be seen that when the noise level is up to 70%, curvature-based method fails to accurately identify edge points. Large tracts of points in smooth regions are mistakenly identified to be edge points, which will subsequently affect the accuracy and efficiency of our normal estimation algorithm.

Figure 3.

Edge points detection using curvature-based method. Points in red color are identified edge points, and non-edge points are shown in green points. From left to right, they are Fandisk, Revolved part, and Anchor.

To improve the accuracy and robustness of edge point recognition, a statistics-based edge point recognition strategy is proposed in this article. For each point $p_{i}$ , the initial normal is computed using PCA mentioned above, and then the standard deviation of the point normal values within the point’s $K_{2}$ neighborhood is computed. The standard deviation of point normal is calculated by

σ_{ni} = | \sqrt{\frac{\sum_{j = 0}^{K_{2}} n_{j} - {\bar{n}}_{i}}{K_{2}}} | = \sqrt{\frac{\sum_{j = 0}^{K_{2}} {(n_{jx} - {\bar{n}}_{ix})}^{2} + \sum_{j = 0}^{K_{2}} {(n_{jy} - {\bar{n}}_{iy})}^{2} + \sum_{j = 0}^{K_{2}} {(n_{jz} - {\bar{n}}_{iz})}^{2}}{K_{2}}}

(4)

where ${\bar{n}}_{j}$ is the unit normal vector of each point in p_i’s neighborhood. ${\bar{n}}_{i}$ is the average normal vector calculated from the normalized point normals within p_i’s neighborhood by

{\bar{n}}_{i} = \sum_{j = 0}^{K_{2}} \frac{n_{j}}{K_{2}}

(5)

Similar to $σ_{i}$ , the standard deviation of points’ normals in a neighborhood indicates the level of changes in the shape of the underlying surface at point $p_{i}$ . Each point $p_{i}$ with normal standard deviation larger than the user-defined threshold $σ_{n τ}$ is viewed as an edge point. In this way, the edge points are identified by statistical analysis of all points’ normals in the neighborhood, which is more robust than judging only by the curvature of a single point.

Figure 4 shows the result of our edge point identification algorithm. The standard deviation tolerance $σ_{n τ}$ for model Fandisk, Revolved part, and Anchor are set to 0.21, 0.17, and 0.19, respectively. It can be seen that the proposed algorithm shows good robustness to noise; it can accurately identify edge points under different noise levels. The edge point set is denoted as $P_{E}$ in this article.

Figure 4.

Edge points detection using statistics-based method. Points in red color are identified edge points, and non-edge points are shown in green points. From left to right, they are Fandisk, Revolved part, and Anchor.

The normal standard deviation threshold $σ_{n τ}$ is a critical factor of our edge point recognition method and the appropriate value is the premise of our normal estimation algorithm. Too small value leads to too many points that are identified as edge points, which will reduce the efficiency of algorithm. Conversely, a large value makes few edge points be identified. If the threshold is large enough, no edge points will be identified or too few edge points are identified to separate points belonging to different surface patches. In this case, our algorithm will degenerate into PCA, because only one cluster is generated through Euclidean clustering. The choice of $σ_{n τ}$ depends on the neighborhood size, noise level, and the level of sharpness of the features contained in the object. Figure 5 shows the effect of these three factors on the threshold selection. It can be learned from Figure 5(a) that $σ_{n τ}$ increases slightly with the increase of neighborhood size and a larger neighborhood corresponds to a larger threshold selection range. From Figure 5(b), we can see that $σ_{n τ}$ keeps almost constant under different noise levels, which indicates that our edge point identification algorithm is robust to noise. To evaluate the influence of sharpness of features on threshold selection, we test our algorithm on a set of point clouds sampled from two intersecting plane with the intersection angles varying from 30° to 150°, as shown in Figure 5(c). It can be seen that a smaller curvature threshold is expected for a shallower intersection angle and the range of appropriate threshold value becomes smaller with the increase of intersection angle. Experiments on all the models used in this article show that $σ_{n τ}$ varies slightly for different models. When $K_{2} = 20$ , noise level is 50%; its value ranges from 0.17 to 0.28 for different models.

Figure 5.

The effect of (a) neighborhood size, (b) noise level, and (c) the level of sharpness on the threshold selection.

Neighborhood reconstruction

Neighborhood segmentation

For an edge point $p_{i} \in P_{E}$ , its original neighborhood $N_{i}$ may contain points sampled from different surface patches across the sharp features, as shown in Figure 6(a). Hence, it is unreliable to compute p_i’s normal by applying PCA on $N_{i}$ directly. But the normal can be faithfully represented by the sub-neighborhood sampled from one of those surface patches at which $p_{i}$ is located. So instead using the whole neighbor $N_{i}$ , the presented method tries to segment $N_{i}$ into several isotropy sub-neighborhoods and the one which $p_{i}$ belongs to is selected to give accurate estimation to point’s normal.

Figure 6.

Pipeline of the neighborhood segmentation and construction algorithm: (a) Initial neighborhood of $p_{i}$ , the current point $p_{i}$ is shown in a large red solid point, its neighborhood is marked by the black circle. The edge points in $p_{i}' s$ neighborhood are shown in red solid points and the non-edge points are shown in blue solid points, (b) $p_{i}' s$ neighborhood after removing edge points, (c) Two sub-neighborhoods are obtained after Euclidean distance clustering, (d) Each sub-neighborhood is fitted into a plane and the corresponding median value of fitting residual is computed, (e) Each edge point is assigned to corresponding sub-neighborhood according to its deviation to fitting planes. The green points are edge points shared by the two sub-neighborhoods and (f) Two candidate neighborhoods are constructed for $p_{i}$ .

For this purpose, a neighborhood segmentation method is proposed to segment $N_{i}$ into several isotropic sub-neighborhoods. An edge point’s neighborhood usually contains both edge points and non-edge points. For convenience, the set of edge points in $N_{i}$ is donated as $P_{iE}$ and the set of non-edge points in $N_{i}$ is donated as $P_{iN}$ . First, in order to realize neighborhood segmentation, all the edge points $p_{iE} \in P_{iE}$ are removed from $N_{i}$ , and the neighborhood is naturally divided into several separated point sets in space domain, as shown in Figure 6(b). Then, Euclidean distance clustering³⁵ is used to segment the neighborhood, and several isotropy sub-neighborhoods $N_{i}^{s} = {N_{ij}^{s}}$ are obtained, as shown in Figure 6(c). The number of sub-neighborhoods depends on the location of $p_{i}$ . If the edge point is near an edge, the number of sub-neighborhoods is two, and for the edge points near a corner where several surface patches join together, three or more sub-neighborhoods are obtained. If the number of clusters obtained by Euclidean distance clustering is zero, it means that the current point is located in the area of high curvature and all the points in the neighborhood are identified as edge points. In this case, a small neighborhood of $p_{i}$ , with $K_{0} / 2$ points is chosen as the final ${\tilde{N}}_{i}$ . If the number of clusters is one, it means that the current point is located in a relatively smooth region and only a few edge points are identified. In this case, the initial neighborhood $N_{i}$ is taken as its final consistent neighborhood ${\tilde{N}}_{i}$ .

The key to neighborhood segmentation is the selection of distance threshold t used in Euclidean distance clustering. An inappropriate distance threshold may lead to over segmentation or under segmentation, which would negatively impact the accuracy of normal estimation. The distance threshold usually changes with the density variation in the point cloud model or between models. To improve the algorithm’s performance and practicability, an adaptive distance threshold is essential. To this end, a sample distance threshold determination procedure is introduced. First, after all the edge points are removed from $N_{i}$ , one-tenth points are randomly selected from $N_{i}$ . And then, the local point spacing $\bar{δ}$ is estimated as the average distance of these points from their nearest neighbors.³⁶ Finally, the distance threshold is adaptively set as $t = 2.5 \bar{δ}$ .

The relationship between t and $\bar{δ}$ is determined by experimental test on different point cloud models. As shown in Figure 7, it can be seen that the distance threshold t has a large value range. This is because the identified edge points form a banded area with a certain width that separates sub-neighborhoods belonging to different surface patches as shown in Figure 4. It can be learned from Figure 7 that the distance threshold is selected as two to three times the local point spacing is appropriate. Therefore, the distance threshold is determined to be $t = 2.5 \bar{δ}$ in this article.

Figure 7.

Relationship between distance threshold t and local point spacing $\bar{δ}$ of different models.

Candidate neighborhood construction

To realize the neighborhood segmentation, all the edge points are removed from $N_{i}$ , the obtained sub-neighborhoods do not contain edge points which are close to $p_{i}$ . However, theoretically, points closer to $p_{i}$ have a greater impact on normal estimation. Applying PCA directly to the above determined sub-neighborhoods may lead to inaccurate normal estimation due to the absence of edge points around $p_{i}$ . Therefore, the edge points belong to the same surface patch as $p_{i}$ should be taken into consideration when estimate the normal.

In this study, a residual constrained neighborhood construction strategy is presented to add the edge points to the corresponding sub-neighborhood and generate a set of reasonable candidate neighborhoods. The strategy is based on the segmented sub-neighborhoods. For each segmented sub-neighborhood $N_{ij}^{s}$ , a least squares plane $P_{ij}^{s}$ is estimated by analyzing its covariance matrix; the corresponding median value of fitting residual $ε_{ij}^{c}$ is computed, as shown in Figure 6(d). And then we calculate the deviation from each edge point $p_{iE} \in P_{iE}$ to the fitting plane $P_{ij}^{s}$ , if the deviation of an edge point is less than the median value of fitting residuals of the plane $P_{ij}^{s}$ , the point is added to the corresponding sub-neighborhood $N_{ij}^{s}$ , as shown in Figure 6(e). Several isotropy candidate neighborhoods $N_{i}^{c} = {N_{ij}^{c}}$ are constructed in this way, as shown in Figure 6(f).

Dealing with features with close proximity

Features with close proximity are common in many captured scenes, especially when the scanned object is mechanical part or artifact. However, it is likely that all points in narrow-band region between these features are identified as edge points using the edge points identification method mentioned in section “Edge point recognition,” as shown in Figure 8(a). In this case, the points’ normal may be incorrectly calculated, as shown in Figure 8(b), the normal of the edge points between the two features are considered as the normal of the two features.

Figure 8.

Deal with features with close proximity: (a) All the points in narrow-band region are identified as edge points, (b) Points’ normal vectors are incorrectly calculated in narrow-band region, (c) Neighborhood of a point $p_{i}$ between features with close proximity. Current point $p_{i}$ is shown in large red point, the smaller red points are edge points in its neighborhood. The points in green and blue are two segmented sub-neighborhoods belong to two surface patches that in close proximity to each other, (d) Each sub-neighborhood is fitted into a plane and the corresponding maximum value of fitting residual is computed, (e) The remaining points in $p_{iE}$ after removing edge points whose distance from the plane is less than the plane’s maximum fitting residual and (f) Optimal result of the normal estimation in the narrow region.

To cope with this problem, a two-stage clustering strategy is devised. As shown in Figure 8(c), after the first clustering mentioned in section “Neighborhood segmentation,” neighborhood of an edge point in narrow-band region is segmented into two sub-neighborhoods, in green and blue color, respectively. The two sub-neighborhoods are located on the surface patches in close proximity to each other. First, each of the sub-neighborhoods is fitted to a plane as mentioned in section “Candidate neighborhood construction,” and the corresponding maximum fitting residuals $ε_{ij}^{m}$ can be calculated. Then for each fitting plane $P_{ij}^{s}$ , we compute the deviation of each edge point in $P_{iE}$ from $P_{ij}^{s}$ . If the deviation is less than the corresponding maximum fitting residuals $ε_{ij}^{m}$ , the edge point is removed from $P_{iE}$ , as shown in Figure 8(d). After all the fitting planes are traversed, if the number of remaining points in $P_{iE}$ is greater than $K_{2}$ , the point is considered to locate on a narrow region, and it may not belongs to any of the segmented sub-neighborhoods, as shown in Figure 8(e). In order to find the right neighborhood of current edge point, a second Euclidean distance clustering is conducted on the remaining point set in $P_{iE}$ , clusters larger than $K_{2}$ are selected, and the obtained clusters are donated as ${C_{il}}_{l = 1}^{n}$ . For each cluster $C_{il}$ , we calculate the standard deviation $σ_{n}$ of the points’ preliminary normal values within cluster $C_{il}$ , if $σ_{n} < σ_{n τ}$ , the cluster is considered as a candidate neighborhood and added to candidate neighborhood set ${N_{ij}^{c}}$ . If no cluster satisfies condition $σ_{n} < σ_{n τ}$ is found, the point is considered to locate on a more complicated region; then a small neighborhood of $p_{i}$ with $K_{0} / 2$ points is chosen as the final ${\tilde{N}}_{i}$ . The optimal result of the normal estimation in the narrow region is shown in Figure 8(f).

Dealing with sampling anisotropy

Non-uniform sampling occurs ordinarily due to varying incidences on scanned surfaces. As shown in Figure 9(a), when the sampling is extremely non-uniform near the sharp features, the proposed edge point recognition method may fail to detect the edge points on the surface with higher sampling density. This will lead to a smooth normal by applying PCA on these points’ neighborhoods, as shown in Figure 9(b).

Figure 9.

Dealing with sampling anisotropy: (a) Result of edge point recognition, blue points are non-edge points, red points are edge points. The proposed edge point recognition method fails to detect the edge points on the surface with higher sampling density, (b) Non-edge point’s neighborhood may contain edge points from different surface patches, (c) The blue points in the circle are seed points for neighborhood growth, (d) Result of neighborhood growth, a consistent neighborhood is generated for normal estimation, (e) Neighborhood of an edge point on sparse sampling surface and (f) Result of sub-neighborhood growth, a larger sub-neighborhood in surface patch with sparse sampling is generated.

For robustness to density variation, a neighborhood growth strategy is proposed to generate a consistent neighborhood which is clear of edge points. For each non-edge point, if its neighborhood contains edge points, this means that the point is near sharp features. To avoid using points belonging to different surface patches, all the edge points in the neighborhood together with non-edge points with a distance greater than t from the current point are removed from the neighborhood. Then the remaining non-edge points in the neighborhood are used as seed points for neighborhood growth, as shown in Figure 9(c); the points in the circle are the seed points. For each remaining non-edge point, 10-nearest neighbor points are computer and the non-edge points with a distance less than t from the current seed point are added to the current neighborhood. If the neighborhood size is less than $K_{0}$ , the new added points are used as new seed points for neighborhood growth, until the size of the neighborhood reaches $K_{0}$ or no conditions satisfying non-edge point are found. This growth strategy ensures that all the neighborhood points are located on the same surface patch as current point $p_{i}$ , as shown in Figure 9(d). Finally, PCA is applied on the generated neighborhood to give a faithful normal estimation.

Sampling anisotropy leads to another challenge for edge point normal estimation. As shown in Figure 9(e), when an edge point $p_{i}$ lies in a surface patch with sparse sampling, only a few non-edge points belonging to the same surface patch with $p_{i}$ will be found, even though a large neighborhood is used. Too small a sub-neighborhood will cause large deviation in plane fitting, which will affect the accuracy of normal estimation. To conquer this problem, the same neighborhood growth strategy is used to expand the sub-neighborhood to $K_{0}$ . If the size of a sub-neighborhood obtained by Euclidean clustering in section “Neighborhood segmentation” is less than $K_{0}$ , then each point in the sub-neighborhood is used as a seed point for neighborhood growth using the growth strategy mention above. For each point in the sub-neighborhood, 10-nearest neighbor points are computer and the non-edge points with a distance less than t from the current seed point are added to the current sub-neighborhood. If the neighborhood size is less than $K_{0}$ , the new added points are used as new seed points for neighborhood growth, until the size of the sub-neighborhood reaches $K_{0}$ or no conditions satisfying non-edge point are found. As shown in Figure 9(f), a larger sub-neighborhood in surface patch with sparse sampling is generated for current edge point.

Criteria for neighborhood selection

Several candidate neighborhoods are obtained after the neighborhood segmentation and construction operation outlined earlier, each candidate neighborhood contains solely the points sampled from the same surface patch. To accurately estimate the normal, the proper neighborhood needs to be identified from the neighborhood set. For this purpose, the following weight is defined

γ (N_{ij}^{c}) = α_{1} \cdot D (p_{i}) + α_{2} \cdot ‖ p_{i} - p_{ic} ‖

(6)

where $D (p_{i})$ is the deviation of current edge point $p_{i}$ from the plane fitted with the candidate neighborhood $N_{ij}^{c}$ , $p_{ic}$ is the centroid of the set of neighbors in $N_{ij}^{c}$ , $α_{1}$ and $α_{2}$ are given parameters.

The first item $D (p_{i})$ measures the confidence of point $p_{i}$ belonging to the face patch in which the candidate neighborhood is located. And the candidate neighborhood closer to $p_{i}$ is also considered more confident. So the candidate neighborhood with the minimal $γ (N_{ij}^{c})$ will be selected as the neighborhood of the current edge point. We think that the deviation of current edge point $p_{i}$ from the plane fitted with the candidate neighborhood $N_{ij}^{c}$ can better reflect whether the point belongs to the surface patch in which the neighborhood lies. In addition, when the sampling is extremely non-uniform near the sharp features, the centroid of the sub-neighborhood located on the same surface patch as the current point may be farther from the current point than that of other sub-neighborhoods, as shown in Figure 9(f). So we weaken the effect of $‖ p_{i} - p_{ij} ‖$ and set the two parameters as $α_{1} = 0.8$ , $α_{2} = 0.2$ in this article.

To make sure the success of the neighborhood segmentation, a large initial neighborhood $N_{i}$ is usually chosen; this may lead to large candidate neighborhoods. However, when the underlying surface patch of candidate neighborhood is curved rather than planar, too large a neighborhood may lead to bias when fitting the local plane of point $p_{i}$ and then affects the accuracy of the normal estimation. Thus, for each candidate neighborhood, the nearest $K_{0}$ points from $p_{i}$ are selected to fit the local plane.

Computational complexity

In our method, only classical PCA and Euclidean distance clustering are used, no complex iterative optimization algorithm is included. Thanks to the simplicity of our approach, the speed of our method is acceptable, although there are many steps to build and evaluate candidate neighborhoods. The neighborhood search and candidate neighborhood construct part are the main computational cost. For each edge point, the computational complexity of our candidate neighborhood construction algorithm is roughly $O (K_{2} \log N + K_{2} + M_{1} M_{2})$ . For a non-edge point, the cost of generating a consistent neighborhood is roughly $O (i (10 \log N) + K_{0})$ , where N is the size of point cloud, $M_{1}$ is the number of sub-neighborhoods generated by Euclidean distance clustering, $M_{2}$ is the number of edge points in current point’s $K_{2}$ neighborhood, and i is the neighborhood search times for neighborhood growth.

Implementation results

To evaluate the performance of the proposed approach, a variety of point cloud models with sharp features and synthetic Gaussian noise are tested. A series of comparisons are made between this paper’s method and some state-of-the-art methods: PCA,¹² robust normal estimation (RNE),¹⁶ HF,³⁰ and LRR,¹⁹ in view of sharp features, sampling anisotropy, and noise. According to the sampling strategy, HF has three versions: HF_points, HF_cubes and HF_unif.

Two different scores are used to quantitatively evaluate the algorithms’ performance: the root mean square with threshold (RMS_τ) and the number of bad points (NBP). The RMS_τ is a standard error measure which provides a good idea of the overall performance of an algorithm. It is defined as

RMS_τ = \sqrt{\frac{1}{| P |} {\sum_{p \in P} f (\hat{n_{p}, {\tilde{n}}_{p}})}^{2}}

where

f (\hat{n_{p}, {\tilde{n}}_{p}}) = {\begin{matrix} \hat{n_{p} {\tilde{n}}_{p}}, if \hat{n_{p} {\tilde{n}}_{p}} < τ \\ π / 2, otherwise \end{matrix}

$n_{p}$ is the ground truth normal at p, and ${\tilde{n}}_{p}$ is the estimated one. $\hat{n_{p} {\tilde{n}}_{p}}$ is the angle between $n_{p}$ and ${\tilde{n}}_{p}$ . As proposed by Mitra and Nguyen¹⁵ and Kolluri,²τ = 10° is chosen in this article; the bad points are defined as those points with measure greater than 10°.

All the noise used in the experiments is Gaussian noise, with different standard deviations as % of the mean distance between points. The proposed method is implemented using VC++ and Point Cloud Library (PCL). HF are also programed based on the PCL, while LRR and RNE are in MATLAB version. All the experiments have been performed on the same computer with 1 CPU Inter(R) Core(TM) i3-3240M 3.40 GHZ and 4 GB RAM without parallel computing.

The parameters used in this article are summarized as follows:

$K_{0}$ : the number of neighbors used to PCA.

$K_{1}$ : the number of neighbors used for neighborhood segmentation.

$K_{2}$ : the number of neighbors used to identify edge points.

$σ_{nt}$ : the threshold used to distinguish edge points and non-edge points.

t: the distance threshold used in Euclidean distance clustering.

The choice of parameters depends on the surface sampling density and noise. Empirically, the parameters $K_{0}$ , $K_{1}$ , $K_{2}$ are chosen as $K_{0} = 60$ , $K_{1} = 400$ , $K_{2} = 20$ in implementation. Parameter $σ_{nt}$ is a user-specified value. Parameter t is adaptively determined using the method mentioned in section “Neighborhood segmentation.” The parameters used in these existing methods are either manually adjusted to attain the best results or set as the suggested values, according to their respective procedures.

Comparison on feature preservation

Sharp features with shallow angles

To compare the performance of each algorithm on sharp features with shallow angles, all the methods are applied on the 20K octahedron model with 50% noise. The sharp features included in the model are generated by two intersection planes with shallow angles. The comparison results are shown in Figure 10. It can be seen that the computation time of PCA is less than other methods, but there are many mistakes around the edges. The normals are overly smoothed near sharp edges, which lead to the loss of sharp features after point-based rendering. The performance of HF_points is worse than PCA, since the RHT does not smooth out noises. HF_unif and HF_cubes blur the edges in less degree but many erroneous normals may still persist in the vicinities of sharp features. The reason of the inferiority of HF for such case is that when the intersection angle is shallow, the normals produced by triples sampled from different sides are likely to vote for the same bin. RNE performs better than those of HF and PCA but still inferior than LRR and the presented method. The NBP and RMS_τ of the presented method are similar with LRR and much less than the other methods, while the computation time of the presented method is far less than that of LRR.

Figure 10.

Comparison on octahedron containing sharp edges with shallow angles. From top to bottom row are the visualization of bad points colored in red, estimated normals, rendering using surfels and the result statistics of each algorithm, respectively. From left to right are the results of PCA, RNE, HF_points, HF_cubes, HF_unif, LRR, and proposed algorithm, respectively.

Neighborhood with multiple features

Fandisk model with 40K points and 50% noise is used to evaluate the performance of each algorithm on complex neighborhood structure. Many points’ neighborhood of Fandisk model may contain multiple feature lines because of the narrow-band regions it contains. The complex neighborhood structure presents challenges for the normal estimation. The results are presented in Figure 11. PCA, RNE, and those of HF generate many bad points around the narrow-band region marked in Figure 11. By contrast, the presented method and LRR perform much better on the region, and most bad points are distributed along the edges. The second row of Figure 11 shows that although other algorithms overly smooth the normal around features, the presented method remains the discontinuity of normals properly, almost as good as LRR. This illustrates that the presented neighborhood segmentation method can handle complex neighborhood.

Figure 11.

Comparison on Fandisk containing complex neighborhood structure. 50% noise is added. From left to right, they are the results of PCA, RNE, HF_points, HF_cubes, HF_unif, LRR, and proposed algorithm. From top to bottom row are the visualization of bad points colored in red, estimated normals, rendering using surfels and the result statistics of each algorithm, respectively.

Comparison on robustness to sampling density

To evaluate the robustness of the presented method to non-uniform sampling, a tetrahedron with 13K points and a cube model with 20K points sampled with face-specific variations of density are tested. The results are shown in Figures 12 and 13, respectively. It can be seen that PCA and HF_points generate many erroneous normal near sharp features. HF_cubes and HF_unif perform better than RNE, since they are devised to deal with density variation. However, there are still some errors near sharp features. The presented method and LRR are still much more superior to other methods. As shown in the bottom row of Figure 13, in view of RMS_τ, the proposed method is better than LRR. The experiment indicates that the presented method can find a neighborhood without crossing features even when the sampling is very anisotropic around sharp features.

Figure 12.

The presented method is robust to anisotropic sampling. The numbers of points on tetrahedron’s four surfaces are at a ratio of 1:2:3:4.

Figure 13.

The presented method is robust to anisotropic sampling. The numbers of points on cube’s right, up, and front surfaces are at a ratio of 1:2:6, and surfaces on the opposite position have same number of points.

Comparison on robustness to noise

Figure 14 shows that the proposed method is robust to noise. In this experiment, two models of Cube and Octahedron with varying Gaussian noise levels are tested. The noise level of these models varies from 0% to 100%. Although the performances of all the methods drop with the increase of the noise level, the proposed method achieves the lowest RMS_τ and NBP. With the increase of the noise level, the RMS_τ and NBP of HF increase rapidly when the noise level is greater than 40%. The same phenomena can be observed in RNE when the noise level is greater than 60%. The proposed method and LRR increase in small amplitude until the noise level is greater than 80%, and the proposed method achieves the lowest RMS_τ and NBP when the noise level is greater than 80%. This shows that the presented method has good robustness to noise.

Figure 14.

The presented method is robust to noise. RMS_τ and NBP of RNE, HF_points, HF_cubes, HF_unif, LRR, and proposed method on octahedron and cube at different noise levels are shown in the top and bottom row, respectively.

Comparison on detailed shapes

Three models with detailed features are used to evaluate the performance of each algorithm in dealing with detailed shapes. To clearly show the rendering effect of detail features, no noise was added to the point cloud. As shown in Figure 15, the performances of all the methods drop when dealing with detailed features and high RMS_τ and NBP are achieved. HF achieves lower RMS_τ and NBP, that is because the method estimates local normal vector with only three randomly selected points in the neighborhood, so it can better describe sharp detail features. This advantage is particularly evident when deal with red_circular_box model, which contains more detailed sharp features. Figure 16 shows the rending of each model with the estimated normal. It can be seen that HF and LRR preserve sharp features, but the details in smooth region are seriously smoothed out. That is because triples would be selected with a higher probability in regions of large area; thus, the details in smooth region will be smoothed out. And the LRR may fail to analyze neighborhood structures correctly when the neighborhood structures are complex. Our method, RNE and PCA are a bit smooth near detailed sharp features, but more detail features are preserved.

Figure 15.

Comparison of the NBP and RMS_τ on the detailed shapes.

Figure 16.

Rendering results using normals computed by different methods. For each model, from left to right, they are the input model, the local enlarged drawing of input model, the local enlarged drawing of the rendering results of PCA, RNE, HF_points, HF_cubes, HF_unif, LRR, and proposed algorithm, respectively.

Actually, our algorithm will degrade into PCA in dealing with these highly curved models. That is because most of the points in highly curved regions are identified as edge points. In such circumstance, two special cases arise: one case is that no clustering is found by Euclidean clustering. In this case, as stated in section “Neighborhood segmentation,” a neighborhood with $K_{0} / 2$ points is chosen as the final neighborhood. The other case is that some clusters are found, and after removing the edge points whose distance to the fitting planes of these clusters are less than their fitting residuals, the remaining points in $P_{iE}$ are usually more than $K_{2}$ due to the complexity of the neighborhood structure. This leads to a second Euclidean clustering on $P_{iE}$ , but usually no cluster satisfies condition $σ_{ni} < σ_{n τ}$ is found in these highly curved regions. In this case, as stated in section “Dealing with features with close proximity,” a neighborhood with $K_{0} / 2$ points is chosen as the final neighborhood.

Comparison on raw scans data

Real scanned point clouds, sampled from four workpieces, are used to evaluate the effectiveness of the presented method to handle the real data. The obtained data are defective because of the noise, outliers, and sampling anisotropy, which usually smooth out the sharp features. As the ground truth normals are unknown, quantitative evaluations are not possible, straightforward visual comparison is used to compare the point-based rendering results based on normal estimated by PCA and the proposed method. The results are presented in Figure 17. It can be seen that the proposed method can preserve the sharp features quite well whereas the estimated normals from PCA result in loss of the sharp edges.

Figure 17.

Comparison on real scanned data. The result of PCA is shown on the top row, and the result of proposed method is shown on the bottom row.

Conclusion

In this article, a robust feature preserving normal estimation method based on neighborhood reconstruction has been presented. A robust edge point recognition method based on the statistics analysis of neighborhood points’ normals is proposed. Two specific neighborhood reconstruction techniques are introduced for edge points and non-edge points to generate an isotropy neighborhood for normal estimation. The experiments exhibit that the proposed method outperforms other state-of-the-art methods most of the time, while with relatively low computational cost. Moreover, the proposed method shows good robustness to noise, non-uniform sampling.

However, the presented approach may be unstable when dealing with sparsely sampled models, since it will be hard to get enough points in each segmented sub-neighborhood to accurately identify the parameters of the corresponding underlying surfaces, especially on narrow region. In these cases, the sharp features will be totally lost. Furthermore, some parameters used in this article are decided empirically; more faithful normals can be generated with delicate parameters turning. In the future, we would like to choose these parameters adaptively according to various noises and sampling density.

Footnotes

Acknowledgements

The authors are grateful to all the reviewers for their valuable comments. Thanks to Jie Zhang and Alexandre Boulch for providing the code used for comparison. Thanks to Junjie Cao for providing the models used in this article.

Handling Editor: Francesco Massi

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was sponsored by the National Natural Science Foundation of China (grant number 51475324) and Tianjin Science and Technology Committee (grant number 16PTGCCX00080).

ORCID iD

Zhiqiang Yu

Graphical abstract

In this article, a neighborhood reconstruction-based normal estimation method is presented to reliably estimate normals for unorganized point clouds. As the figure above shows, the algorithm consists of five phases: (1) for each point $p_{i}$ , K₀-nearest neighbor $N_{i}$ is computed and an initial normal vector is estimated by covariance analysis of $N_{i}$ . Then each point $p_{i}$ is identified as edge point or non-edge point according to the standard deviation of the normal vectors of p_i’s neighbors. (2) For an edge point, a larger neighborhood of size $K_{1}$ is recalculated as $N_{i}$ , and an Euclidean distance clustering–based neighborhood segmentation strategy is designed to segment $N_{i}$ into several consistent sub-neighborhoods. Several reasonable candidate neighborhoods are constructed with a residual constrained neighborhood construction method. (3) Evaluation criteria are presented to identify a neighborhood that locates on the same surface patch as $p_{i}$ from the candidate neighborhood set. (4) For each non-edge point, if there are no edge points in the neighborhood, the initial neighborhood $N_{i}$ is taken as its final consistent neighborhood ${\tilde{N}}_{i}$ . If its neighborhood contains edge points, then a neighborhood growth strategy is used to generate a new neighborhood clear of edge points. (5) Finally, a more accurate normal is estimated by principal component analysis using the newly constructed neighborhood.

References

Öztireli

Guennebaud

Gross

MH.

Feature preserving point set surfaces based on non-linear kernel regression. Comput Graph Forum 2009; 28: 493–501.

Kolluri

. Provably good moving least squares. In: Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, Vancouver, BC, Canada, 23–25 January 2005, pp.1008–1017. Philadelphia, PA: Society for Industrial and Applied Mathematics.

Alexa

Behr

Cohen-Or

et al . Point set surfaces. In: Proceedings of the IEEE conference on visualization, San Diego, CA, 21–26 October 2001, pp.21–28. New York: IEEE.

Alexa

Behr

Cohen-Or

et al . Computing and rendering point set surfaces. IEEE T Vis Comput Gr 2003; 9: 3–15.

Yang

Lee

Segmentation of measured point data using a parametric quadric surface approximation. Comput Aided Design 1999; 31: 449–457.

Jones

Durand

Desbrun

Non-iterative, feature-preserving mesh smoothing. ACM T Graphic 2003; 22: 943–949.

Pauly

Gross

Kobbelt

. Efficient simplification of point-sampled surfaces. In: Proceedings of the IEEE conference on visualization, Boston, MA, 27 October–1 November 2002, pp.163–170. New York: IEEE.

Song

Feng

HY.

A global clustering approach to point cloud simplification with a specified data reduction ratio. Comput Aided Design 2008; 40: 281–292.

Pauly

Keiser

Kobbelt

et al . Shape modeling with point-sampled geometry. ACM T Graphic 2003; 22: 641–650.

10.

Pauly

Keiser

Gross

Multi-scale feature extraction on point-sampled surfaces. Comput Graph Forum 2003; 22: 281–289.

11.

Demarsin

Vanderstraeten

Volodine

et al . Detection of closed sharp edges in point clouds using normal estimation and graph theory. Comput Aided Design 2007; 39: 276–283.

12.

Hoppe

DeRose

Duchamp

et al . Surface reconstruction from unorganized points. In: SIGGRAPH’92 19th annual conference and exhibition on computer graphics and interactive techniques, Chicago, IL, 27–31 July 1992, pp.71–78. New York: ACM.

13.

Guennebaud

Gross

MH.

Algebraic point set surfaces. ACM T Graphic 2007; 26: 23.

14.

Cazals

Pouget

Estimating differential quantities using polynomial fitting of osculating jets. Comput Aided Geom D 2005; 22: 121–146.

15.

Mitra

Nguyen

Estimating surface normals in noisy point cloud data. In: Proceedings of the nineteenth annual symposium on computational geometry, San Diego, CA, 8–10 June 2003, pp.322–328. New York: ACM.

16.

Schnabel

Klein

et al . Robust normal estimation for point clouds with sharp features. Comput Graphics 2010; 34: 94–106.

17.

Fleishman

Cohen-Or

Silva

CT.

Robust moving least-squares fitting with sharp features. ACM T Graphic 2005; 24: 544–552.

18.

Yoon

Lee

et al . Surface and normal ensembles for surface reconstruction. Comput Aided Design 2007; 39: 408–420.

19.

Zhang

Cao

Liu

et al . Point cloud normal estimation via low-rank subspace clustering. Comput Graphics 2013; 37: 697–706.

20.

Liu

Zhang

Cao

et al . Quality point cloud normal estimation by guided least squares representation. Comput Graphics 2015; 51: 106–116.

21.

Khaloo

Lattanzi

Robust normal estimation and region growing segmentation of infrastructure 3D point cloud models. Adv Eng Inform 2017; 34: 1–16.

22.

Nurunnabi

West

Belton

Outlier detection and robust normal-curvature estimation in mobile laser scanning 3D point cloud data. Pattern Recogn 2015; 48: 1404–1419.

23.

Haque

Govindu

. Robust feature-preserving denoising of 3D point clouds. In: 2016 fourth international conference on 3D vision (3DV), Stanford, CA, 25–28 October 2016, pp.83–91. New York: IEEE.

24.

Huang

Gong

et al . Edge-aware point set resampling. ACM T Graphic 2013; 32: 9-1–9-12.

25.

Boulch

Marlet

Fast and robust normal estimation for point clouds with sharp features. Comput Graph Forum 2012; 31: 1765–1774.

26.

Boulch

Marlet

Deep learning for robust normal estimation in unstructured point clouds. Comput Graph Forum 2016; 35: 281–290.

27.

Calderon

Ruiz

Rivera

. Surface-normal estimation with neighborhood reorganization for 3D reconstruction. In: Progress in pattern recognition, image analysis and applications, Valparaiso, Chile, 13–16 November 2007, pp.321–330. Berlin; Heidelberg: Springer.

28.

Jones

Durand

Zwicker

Normal improvement for point rendering. IEEE Comput Graph 2004; 24: 53–56.

29.

Amenta

Bern

Surface reconstruction by Voronoi filtering. Discrete Comput Geom 1999; 22: 481–504.

30.

Dey

Goswami

Provable surface reconstruction from noisy samples. Comp Geom 2006; 35: 124–141.

31.

OuYang

Feng

H-Y.

On the normal vector estimation for point cloud data from smooth surfaces. Comput Aided Design 2005; 37: 1071–1079.

32.

Alliez

Cohen-Steiner

Tong

et al . Voronoi-based variational reconstruction of unoriented point sets. In: Symposium on geometry processing, Barcelona, 4–6 July 2007, pp.39–48. Aire-la-Ville: Eurographics Association.

33.

Cao

Chen

Zhang

et al . Normal estimation via shifted neighborhood for point cloud. J Comput Appl Math 2017; 329: 57–67.

34.

Hubert

Rousseeuw

Branden

KV.

ROBPCA: a new approach to robust principal component analysis. Technometrics 2005; 47: 64–79.

35.

Assem

Dupont

Friezes and a construction of the Euclidean cluster variables. J Pure Appl Algebra 2011; 215: 2322–2340.

36.

Point Cloud Library (PCL). 3D object recognition based on correspondence grouping, http://pointclouds.org/documentation/tutorials/correspondence_grouping.php (2011, accessed 25 October 2018).

Robust point cloud normal estimation via neighborhood reconstruction

Abstract

Keywords

Introduction

Related works

Overview

Edge point recognition

Neighborhood reconstruction

Neighborhood segmentation

Candidate neighborhood construction

Dealing with features with close proximity

Dealing with sampling anisotropy

Criteria for neighborhood selection

Computational complexity

Implementation results

Comparison on feature preservation

Sharp features with shallow angles

Neighborhood with multiple features

Comparison on robustness to sampling density

Comparison on robustness to noise

Comparison on detailed shapes

Comparison on raw scans data

Conclusion

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

ORCID iD

Graphical abstract

References