Automated extraction of structural planes and geometric information from point cloud

Abstract

Laser scanning (LS) is a powerful tool for acquiring geometric information about structures. However, they face challenges in capturing targets and computing edges. This paper presents a method for automatically identifying point cloud (PC) planes and obtaining geometric information, which can provide construction quality. The proposed method consists of two parts. First, an iterative growth algorithm is introduced to identify multiple planes simultaneously with fewer parameters, which improves upon the traditional plane detection method that needs better robustness due to the abundance of parameters. Second, a framework is introduced for computing geometric information of PC planes, which integrates a k-dimensional tree to replace local density in the density peak clustering algorithm and computes edges while considering mixed points, significantly reducing the time and increasing precision. The effectiveness and accuracy of the method are verified by structural geometric information in the construction process.

Keywords

PC density peak clustering building structure construction

Introduction

Currently, assessment of the geometrical information in construction structures relies primarily on manual inspections using traditional tools like tape measures. However, manual inspections have several limitations. Firstly, they are prone to inaccuracy and unreliability. Secondly, manual inspections are time-consuming and expensive, particularly for large and complex structures. Hence, there is a need to develop a solution that can provide accurate and efficient evaluations of embedded components’ quality.

Quality assessment techniques based on visual data have received much attention lately (Jiang and Zhang, 2019; Tian et al., 2021). A lot of research has been done in LS-based quality detection (Kim et al., 2016; Kim et al., 2013; Olsen et al., 2010; Wang et al., 2016), building reconstruction (Chen et al., 2019; Frias et al., 2022; Rashidi et al., 2015; Tang et al., 2010; Xiong et al., 2013; Xu, Ding, Du and Xue, 2018a), structural health monitoring (Chen et al., 2015; Park et al., 2007), and construction progress monitoring (Kim et al., 2013; Turkan et al., 2012). In these applications, determining the size and location of building components is essential for controlling PC components. A close-range, non-contact photogrammetry technique was suggested by Jauregui (Jauregui et al., 2003) to assess the vertical deflection of bridges. Tommaselli et al. (Tommaselli and Reiss, 2005) provide an image-based technique for measuring a plane’s dimensions using a camera and a laser gauge. This study uses three-dimensional laser scanning technology to capture the spatial coordinates and color information of PC components, and it realizes a more efficient and precise quality control approach for PC component assembly. Target recognition based on PC has been the subject of extensive investigation. Malek et al. (Maalek et al., 2019) delineated a methodology for autonomous extraction of pipelines and flanges of prefabricated modules in oil and gas refineries. Czerniawski et al. (Czerniawski et al., 2018) introduced an automated PC segmentation method for identifying and segmenting planar objects. A succinct intrinsic shape hybrid structure with point sets is decomposed based on PC. Schnabel et al. (Schnabel et al., 2007) developed an algorithm for automatically detecting primitive shapes within unstructured PC. This algorithm enhances the accuracy and completeness of indoor mobile LS plane detection. Wang et al. (Wang et al., 2017) color LS was utilized to improve the automatic estimation of PC bar positions. Zhao et al. (Zhao et al., 2022) developed a novel approach for automated recognition and measurement of PC components’ rebars, concrete, and sleeves based on PC. Based on the geometric and color features of points, the method utilizes a class of classifiers to extract rebars from LS data. Widyaningrum et al. (Widyaningrum et al., 2020) employed the medial axis transform descriptor to extract building outlines from airborne LS. In addition, object recognition based on deep learning has also been explored in recent years. Qi et al. (Qi et al., 2017) introduced an innovative neural network tailored for PC processing. Kim et al. (Kim et al., 2016) used 3-dimensional (3D) PC data for automatic dimensional quality assessment of formwork and reinforcement in reinforced concrete members. In addition, Wang et al. (Wang et al., 2019) conducted a comparison of four distinct edge line estimation algorithms to estimate edge lengths. In a separate study, Xu et al. (Xu et al., 2018a) applied PC for surface defect identification, measurement, and 3D reconstruction.

Over time, various researchers have adapted RANSAC for plane detection in 3D point clouds (Raguram et al., 2008). The fundamental concept of plane detection using RANSAC in point clouds involves extracting a subset of points representing the most dominant plane over N iterations. In each iteration, three non-collinear points, p1, p2, and p3, are randomly chosen. Subsequently, all points on the plane formed by these three points are gathered based on specific criteria. This process is repeated N times, and the plane with the highest score at the end of these iterations is considered the most prominent. However, due to the randomness in selecting the initial three points, traditional RANSAC can encounter the spurious-plane problem, especially in the presence of noise and outliers (Li et al., 2017). Moreover, the computational time required by standard RANSAC can grow exponentially with the noise level in the point cloud (Raguram et al., 2008). The region-growing technique for plane detection in point clouds is an extension of the region-growing method used for segmenting 2D images (Kang et al., 2012). Filin and Pfeifer (Filin and Pfeifer, 2006) enhanced the quality of the features by employing a slope-adaptive neighborhood system.

To execute plane detection in unorganized point clouds, researchers proposed a wide range of solutions based on different approaches (Grilli et al., 2017). The segmentation quality of region-growing-based methods is strongly linked to the strategy used to select the subset of points or regions (seeds) from where the growing accumulation step is executed (Teboul et al., 2010). Choosing unreliable seeds (points located at edges, noise points) would cause over-segmentation or under-segmentation (Huang et al., 2019; Xu et al., 2018b). We present a novel region-growing-based method for plane detection in unorganized point clouds in this research. The objectives of this work are: (1) to develop a new method for detecting flat structures (walls, ceilings, and floors) in building point clouds. (2) to propose a new efficient technique for selecting seed regions from which the accumulation step is executed. (3) to test our plane detection method on several building point clouds and compare the results to those obtained with other methods. The research has 2 main contributions. Firstly, we propose a new application of the Iterative Closest Point (ICP) algorithm used in 2D and 3D spaces for registration operations (Besl and McKay, 1991; Fotsing et al., 2020). We exploit ICP to efficiently choose reliable seed regions from which the accumulation step is conducted. Secondly, we use a voxelized representation of the point cloud to accelerate the growing process. Instead of accumulating all the points in a voxel as in the traditional voxel-based region growing-based methods (Vo et al., 2015), we treat each point of the voxel individually.

The aforementioned algorithm encounters two primary challenges. First, plane detection algorithms are sensitive to data noise, missing points, and outliers, complicating their application in intricate scenes. Second, these algorithms often necessitate manual adjustments of parameters to accommodate varying scenes, which requires users to possess specialized skills and experience. To address these issues, this paper introduces the Simultaneous Growth of Multi-Seeds (SGM) algorithm, which enables the concurrent growth of multiple planes, thereby significantly enhancing detection efficiency compared to traditional region-growing methods. The remainder of this paper is structured as follows: Section Two primarily employs the SGM algorithm to extract target planes from complex scenes. Section Three focuses on the extraction of comprehensive geometric information and laboratory validation based on the identified planes. Section Four emphasizes the engineering applications of the proposed method. Finally, Section Five presents the conclusions and future directions of this paper.

Method

This paper presents a novel framework for automatically identifying planes and extracting geometric information from PC (Figure 1). The framework comprises data acquisition, processing, and analysis. In the data acquisition stage, a standing LS is used to obtain PC information on pre-casting wall-embedded panels at a nuclear power construction site, which is transmitted to a computer in real time for processing. In the data processing stage, the paper proposes a new SGM algorithm for simultaneous multi-plane detection (Section 2.1) and a geometric information acquisition framework (Section 2.2). The SGM algorithm is designed to identify multiple planes in the PC simultaneously. After the target plane is obtained, the geometric information, such as the center, side length (radius), and deflection, is calculated using the framework proposed in Section 2.2. Finally, the deviation of all geometric information is calculated to provide reliable opinions for on-site construction acceptance.

Figure 1.

Flow-chart diagram of the proposed method.

Segment plane with Simultaneous Growth of Multi-seeds

Accurately and efficiently identifying target planes from complex construction backgrounds poses a significant challenge. This paper uses background and target characteristics to achieve plane separation. Specifically, this section details a method for segmenting multiple planes from complex backgrounds. The first step involves utilizing a standing scanner to collect data from pre-embedded panels at the construction site and transmitting the data. The collected data is down-sampled to process a large amount of PC more efficiently. Next, the K nearest neighboring (KNN) points are identified for all points within the PC, followed by the application of the MSAC algorithm to classify the K points into inner and outer points based on a predetermined model. Subsequently, the outer points are removed, and the PC is down-sampled again. Finally, initial points for the SGM algorithm are selected from the remaining points that exhibit no inner points, and all K points are identified as outer points using the MSAC algorithm. This process efficiently and accurately selects initial points for the SGM algorithm by identifying points that optimally represent the PC. The second step of the methodology entails the computation of K points near the initial point. The corresponding normal vectors are utilized to determine the entropy value and angle between the K and initial points. Subsequently, ineligible points are identified and eliminated to achieve complete growth. The process is repeated until no new points are added after removing ineligible corner points in the initial iteration. Appropriate parameters must be selected to compute the entropy value and included angle. In this study, the thickness of the PC resulting from comprehensive error is utilized to derive these parameters, thereby minimizing the influence of artificially chosen parameters on the computation outcomes. It is essential to note that this approach is intended to enhance the accuracy and reliability of the method.

Initial point selection strategy

The building surface has the characteristics of an extensive scanning area. Therefore, the input data always consists of millions of points. It selects points based on calculated sampling probabilities. The flowchart of Simultaneous Growth of Multi-seeds is shown in Figure 2.

Figure 2.

Flow-chart of simultaneous growth of multi-seeds.

The region growing algorithm needs to calculate the curvature value of all points first and then select the smallest value of the area as the seed point for growth until all the points around the seed point that meet the conditions have grown, and repeat the previous process until all the planes are fully grown. This strategy of selecting the initial point is inefficient and easily disturbed by noise. Therefore, this paper adopts a new plan to choose the initial point. Given a PC set ${P}$ , the first step of the proposed approach is to select point $p_{i} \in {P}$ and employ the K nearest neighbor algorithm to locate K points around $p_{i}$ (Figure 2). Plane fitting is then performed on the identified points using robust M-estimation. This method assigns varying weights to samples, which adaptively mitigates the influence of outliers on the estimation results of model parameters. Samples with high residuals are assigned lower weights, typically close to zero. To ensure the robustness of the plane fitting, this study employs the MSAC algorithm, an extended version of the M-estimator. The M-estimator is generally defined as:

{\hat{β}}_{M} = \underset{β}{argmin} \sum_{i = 1}^{n} ρ (\frac{y_{i} - x_{i}^{T} β}{\hat{σ}})

(1)

where n is the total number of points in the plane,

ρ

is the objective function and also the residual of the loss function;

y_{i} - x_{i}^{T} β

is the residual term is the robust scale estimation of the residual, which depends on the unknown regression coefficient.

MSAC will compensate for the influence of parameter selection and can divide K into interior points and $O_{p_{i}}$ . When calculating the fitting plane of all points, the point corresponding to the outer point 0 is used as the initial point set ${I}$ , and the remaining point sets are ${N}$

p_{i} \in {\begin{cases} I, i f O_{p_{i}} = \emptyset \\ N, e l s e \end{cases}

(2)

The normal vector of $p_{i}$ is $n_{p_{i}}$ , and the parameter selection of MSAC will be mentioned in 2.1.3.

Figure 3 illustrates the process of initial point selection, primarily by calculating the plane formed by the points surrounding each point and then decomposing them into inliers and outliers. When the normal vector calculated with consideration of outliers shows a significant difference compared to when they are not considered, as demonstrated by $V_{0}$ and $V_{0}^{'}$ in the figure, it becomes possible to filter out noise points located at the target edge, thereby identifying the complete plane.

Figure 3.

Iteration process of Simultaneous Growth of Multi-seeds.

Grow iteratively through the initial point

After getting all the initial seed points $I_{i} = (x_{i}, y_{i}, z_{i})$ and their corresponding normal vectors $n_{p_{i}} = (a, b, c)$ , add all the seed points to the target set ${T}$ , and select all $I_{i}$ points M $B_{m}, m \in {1, 2, \dots, M}$ points around and not in the T set, and use MSAC to calculate the normal vector of all $B_{m}$ points $n_{m_{i}} = (a_{i}, b_{i}, c_{i})$ ,

α = \arccos (| \frac{n_{m_{i}} n_{p_{i}}}{| n_{m_{i}} | | n_{p_{i}} |} |)

(3)

θ = {\begin{cases} α, i f α < π / 2 \\ π - α, else \end{cases}

(4)

This paper’s target area is a planar surface, while most noise points are surface and disordered. Therefore, the proposed target detection approach aims to preserve all planar points while eliminating curved surfaces and non-geometric noise points. The first step of the algorithm involves downsampling the original data. The resulting data shows that Plane A is the target area, but many noise points still exist. To calculate the normal vector of point P, the plane normal vector of the K points around point P is employed as the normal vector of point P. However, the K points around P may include both planar and non-planar points, such as the green points in Figure 4. Therefore, to obtain the true normal vector of P, this study considers only the interior points in the calculation, assuming that the number of interior points is k, while the number of exterior points is $K - k$ . The resulting normal vector of point P is a more accurate representation of the geometric information within the plane. After calculating the normal vectors of P and all interior points using this method, the angles between P and the normal vectors of the surrounding k interior points and the standard plane are computed.

θ_{P} = θ_{I_{i}} + θ_{O_{i}}

(5)

θ_{I_{i}} = n_{I_{i}} \cdot {[a, b, c]}^{T}, I_{i} \in {1, 2, 3, \dots k - 1, k}

(6)

θ_{O_{i}} = m e a n (θ_{I_{i}}), O_{i} \in {K - k, K - k + 1, \dots, K}

(7)

Figure 4.

Iterative result graph of multiple seed joint growth algorithm.

Parameter optimization

PC thickness is another crucial parameter that affects accuracy and requires attention. PC thickness refers to the fact that after scanning a regular surface, the resulting PC data is not an exact plane but a thick set of points, as shown in Figure 5. The generation of PC thickness is influenced by various factors, including the measurement and positioning difference of individual points, the degree of reflection of the material surface, the variation in spot diameter caused by the scanning distance, PC data conversion and extraction algorithms, and environmental factors such as air pressure, humidity, and temperature during scanning. The main reason for PC thickness is the inaccurate conversion of depth information. Considering the current software and hardware conditions of 3D scanners, PC thickness varies, but it is generally expected. The thickness of the PC ranges between 4 and 9 mm.

Figure 5.

PC thickness and its statistical distribution.

To mitigate the potential bias introduced by the manual selection of parameters, this study utilizes the thickness of the PC resulting from comprehensive error to derive the necessary parameters for PC processing. Specifically, an algorithm is employed to identify outliers in the PC (Rusu et al., 2008). The average Euclidean distance $d_{n}$ and the associated standard deviation e calculated for each point. If $d_{n}$ exceeds $d_{n} > μ_{d} + n σ_{d}$ for any point, this point will be excluded from the dataset. The number of standard deviations, denoted as n, can be adjusted according to the desired level of filtering. While point density may vary across the entire PC, outliers are often noticeably isolated from the neighboring PC.

The distribution shows the cloud area of outliers detected by the specified algorithm. Calculate the mean and variance of the PC and approximately distribute the PC as a Gaussian distribution. $(μ - 3 σ, μ + 3 σ)$ is a 99% confidence interval, so $6 σ$ i used as the thickness of the PC, and $e = 3 σ$ is used as $p_{i} = (x_{i}, y_{i}, z_{i})$ single-point precision error. Since the normal vector is obtained by plane fitting, the maximum value of the normal vector deviation is used for analysis to describe the influence of the adjacent point error on the normal vector accuracy.

Assuming that all adjacent points are on an error-free tangent plane, the fitted tangent plane $T (X)$ , the normal vector of this plane is $V_{0}$ . Since each point has point accuracy, take the maximum point error e, $p_{i}$ is within the range of the adjacent point $p_{i} \in (0, e)$ and the tangent plane with the largest error is $T (X^{'})$ . The vector is $V^{'}$ , then the normal vector accuracy is caused by the point error e. In the tangent plane $T (X)$ , assuming that the point farthest from the adjacent point to the center adjoining point is $P_{i}^{'}$ , then the difference between the tangent plane $T (X^{'})$ with the largest error and the tangent plane $T (X)$ without error. The angle is the angle between the normal vector $V_{0}^{'}$ and $V_{0}$ , so the error range of the normal vector estimation is (0, θ), where θ is

θ = \sin^{- 1} (\frac{3 σ}{| P_{i}^{'} - P_{i} |})

(8)

Assuming the positioning accuracy e of the adjacent points $p_{i} = (x_{i}, y_{i}, z_{i})$ , the local entropy under the field is:

H_{c} (θ_{k}) = - \sum_{i = 1}^{k} P_{θ_{i}} \log P_{θ_{i}}

(9)

P_{θ_{i}} = \frac{θ_{k}}{\sum_{i = 1}^{K} θ_{i}}

(10)

When the angles between the normal vectors of a point and its surrounding k interior points satisfy $θ_{k} = θ_{1} = θ_{2} = \dots = θ_{K}$ , the local entropy $H_{C} (θ_{k}) = H$ reaches its maximum value H. This indicates that the local entropy based on the angle between normal vectors can reflect the surface state, whereas a larger entropy implies a tendency towards a planar surface. In comparison, a smaller entropy suggests a tendency towards a curved surface. As adjacent points in hierarchical clustering jointly determine the local entropy, it is not easily influenced by a few noisy points and thus has a filtering effect. The local entropy can effectively describe the surface characteristics by setting several hierarchical clustering points, meeting the algorithm’s requirements for relativity, locality, and intuitive separation.

The conventional method for PC simplification involves uniformly reducing the number of points or removing adjacent points around the sampled points. However, this approach neglects the characteristics of the surface and results in excessive simplification of the convex and concave areas, which cannot accurately represent the surface’s features. Thus, a better PC simplification principle is to reduce simplification in the convex and concave or turning areas while simplifying more in the plane or smooth areas. This preserves the surface’s characteristic status and reduces data redundancy in the plane area, simplifying the PC. Using the formula (9), we obtain the information entropy $H_{C} (θ_{k}, θ_{m})$ for each primary clustering area. If the information entropy satisfies $H_{C} (θ_{k}) = \log (K)$ , the adjacent area is a plane. However, due to scanning accuracy $H_{C} (θ_{k}) \neq \log (K)$ , and we need to calculate the local entropy accuracy. The local entropy accuracy can be obtained as, taking the error 2 $σ_{H_{c}}^{2}$ as its limit value, and taking the local entropy $\log (m^{'})$ as the initial benchmark, if the local entropy $σ_{H_{c}}^{2}$ of point $p_{i}$ satisfies $H_{p_{i}} - \log (m^{'}) \leq 2 σ_{H_{c}}^{2}$ relative to $\log (m^{'})$ and delete the point. Otherwise keep $p_{i}$ and use $H_{p_{i}}$ which is closest to the local entropy $\log (m^{'})$ as the benchmark.

A framework for calculating the geometric information

Section 2.2’s main objective is to extract geometric information from each target individually. This process involves several steps, as depicted in Figure 6. All the targets obtained in Section 2.1 are classified into different categories. This step helps to distinguish between straight targets and circular targets. Edge detection methods are employed to identify the edges of the straight and circular targets separately. These methods consider the MP (multiple-point) points, which are likely used to improve the accuracy of the edge detection process. Once the edges of the targets are detected, various geometric information is calculated for each target. This includes side length (for straight targets) or radius (for circular targets), center coordinates, and corner points. These measurements allow for a precise description of the targets’ shapes and locations. The next step involves aligning the coordinates of the three-dimensional system used in the analysis with the construction coordinate system. Finally, the extracted construction information is compared to the corresponding design information. This step identifies any differences or deviations between the actual construction and the intended design. Following these steps, Section 2.2 aims to comprehensively analyze each target’s geometry and evaluate its conformity with the design specifications.

Figure 6.

Geometric Information flowchart.

Classify all targets

Although the SGM algorithm presented in Section 2.1 has successfully identified all the target planes, it does not classify the seed points during the selection of initial points, resulting in disordered seed points for each plane. As a result, the plane PC is thoroughly mixed. To obtain the geometric information of each aircraft, the target planes need to be separated by clustering. Rodriguez et al. (Rodriguez and Laio, 2014) proposed a new density peak clustering algorithm that solves many disadvantages of traditional clustering algorithms (Huang et al., 2016; Liu et al., 2018; Xu et al., 2018a). The principle of the DPC algorithm is simple, requiring only a few parameters, and it can identify clusters of different shapes and sizes. However, it does have certain drawbacks, such as the need for manual truncation distance setting and high memory consumption. Over time, numerous researchers have made improvements to the DPC algorithm, but the challenge of high computational complexity still needs to be solved.

DPC is a clustering method that tries to group data points more accurately by finding dense regions with high-density peak points and low-density areas between them. The main idea of the algorithm is to identify points with high local density, which are surrounded by data points with lower local density, and use them to separate noise from the meaningful clusters. The DPC algorithm typically consists of two main steps: 1. Determining Cluster Centers: In this step, the algorithm calculates two metrics for each data point: local density $ρ_{i}$ and distance $δ_{i}$ from higher density points. Local density $ρ_{i}$ represents the number of data points within a given radius around a particular data point. Distance $δ_{i}$ measures the minimum distance between a data point and other data points with higher density. By analyzing various metrics, DPCA identifies data points exhibiting high local density and significant distance from different points with higher density. These points are regarded as cluster centers. Once the cluster centers are determined, the algorithm assigns each data point to the appropriate cluster. This assignment is based on comparing the data points’ local density and distance metrics with those of the cluster centers. Data points with lower local density and larger distances from points with higher density are likely to be noise points. They are either assigned to a noise cluster or disregarded altogether. The remaining data points are allocated to the clusters whose centers are closest in distance and local density. By employing this density-based approach, DPC effectively distinguishes noise points from meaningful clusters. The algorithm identifies high-density peak points as cluster centers and views the surrounding low-density regions as potential noise areas. This methodology allows for precise clustering by effectively separating noise points from the main clusters based on their density characteristics.

The local density $ρ_{i}$ is defined as:

ρ_{i} = \sum_{i} χ (d_{i j} - d_{c})

(11)

χ (x) = {\begin{cases} 1, x < 0 \\ 0, x \geq 0 \end{cases}

(12)

d_{c}

is the truncation distance and is a user-defined parameter. The d_c should be selected such that the average number of neighbors for each data point is about 1% ∼ 2% of the total number of data points. If there are data points with higher density,

δ_{i}

can be calculated by the following formula:

δ_{i} = \min (d_{i j}), j \in I_{s}

(13)

where

I_{s}

represents the set of all ordinals whose local density exceeds that of data point i. In this context,

δ_{i}

denotes the distance between data point xi and the nearest data point, among all data points with local density greater than x_i, which has the smallest distance to x_i. When data point iIachieves the maximum local density,

I_{s}

is empty

I_{s} = \emptyset

, and

δ_{i}

is computed as the distance between x_i and the farthest data point. In cases where the cluster center cannot be intuitively obtained from the decision diagram, the value of γ can be calculated to determine the number of clusters.

{γ_{i} = ρ_{i} δ}_{i}, i \in I_{s}

(14)

γ

is arranged in descending order, with the horizontal axis as subscript and the vertical axis as

γ_{i}

. KNN

d_{i}

is the average distance of

x_{i}

to its KNN. The formula is as follows

d_{i} = \sum_{x_{j} \in K_{i}} d i s t (x_{i}, x_{j})

(15)

D_{i}

represents a local density estimation metric constructed from the K-nearest neighbor distances of

x_{i}

. The formula is as follows:

D_{i} = \frac{k}{\sum_{x_{j} \in K_{i}} d i s t (x_{i}, x_{j})}

(16)

During the computation of the K-nearest neighbor (KNN) distances for data objects, it is necessary to calculate the Euclidean distance between data objects. However, this process exhibits a time complexity of $O (n^{2})$ , resulting in substantial time and memory consumption when handling large-scale PC datasets. The KD-tree indexing data structure is employed to optimize the K-nearest neighbor distance calculation process to enhance the algorithm’s suitability for large-scale datasets. This optimization results in complexity of $O (n \cdot \log n)$ for the algorithm.

This paper proposes solutions for the challenges associated with initializing truncation distance and manually selecting the cluster center in the DPC algorithm. Instead of using local density estimation, the paper suggests using KNN local density, eliminating the need for manual truncation distance settings and reducing the sensitivity to truncation distance parameters. This paper introduces a product of local density and relative distance index to select cluster centers, mitigating potential issues associated with manual selection. Furthermore, to address the high time complexity of the DPC algorithm, this research incorporates the KD-tree indexing data structure into the computation process of K-nearest neighbor local density. The search operation in a balanced KD-tree operates in O (log n) time complexity, making it well-suited for scaling with increasing dataset sizes. The construction time of the KD-tree is O (n log n), which allows for efficient preprocessing, even as the dataset grows. This allows for more efficient determination of the K-nearest neighbors of each data object, resulting in a reduction of the complexity. Furthermore, when computing relative distances, the K-nearest neighbors of the data object are considered, which helps avoid extensive global searches. ${K N N}_{i}$ relative distance is ${r d}_{i}$ that the shortest distance between the exponential data object $x_{i}$ and other data objects in the k neighborhood whose local KNN density is larger than it. The formula is as follows:

{r d}_{i} = {\min (d i s t (x_{i}, x_{j})) | x_{i} ϵ {K N N}_{i}, D_{j} > D_{i}}

(17)

when

x_{i}

is the maximum local density in

{K N N}_{i}

, it is put into the set maxD of the maximum neighbor density, and then the minimum distance between

x_{i}

and other data in maxD is taken as

{r d}_{i}

distance of

x_{i}

, namely

{r d}_{i} = {\min (d i s t (x_{i}, x_{j})) | x_{i} ϵ m a x D}

(18)

The data in Section 2.1, computed using an enhanced DPC algorithm, is presented in Figure 7. Figure 7(a) illustrates the decision plot of $D_{i}$ and ${r d}_{i}$ , where it is evident that there are five distinct clusters with unique spatial positions. These clusters represent the central points of the five targets depicted in the Figure 7(b). The centroids, evaluated using

{cen}_{i} = D_{i} \cdot {r d}_{i}

(19)

as the evaluation metric, are then sorted in descending order within the graph. It can be observed that a jump occurs at the fifth point. Once all points are assigned to the cluster centroids, the clustering of the entire PC is completed. The overall complexity of the algorithm can be divided into two parts: Part 1 involves constructing the local density of the PC data, with a time complexity of

O (n \cdot \log n)

; Part 2 entails determining the cluster centroids for all PC, with a complexity of

O (n)

Figure 7.

DPC decision graph.

Acquire targets geometry information

The MSAC algorithm is applied in this study to compute the plane comprising Normal points in the PC data. A threshold is set at 3σ (three times the standard deviation) of the PC to distinguish between interior and exterior points. The calculation results show that all normal points are considered interior points, while all mixture points are classified as exterior points. Next, all exterior points are projected onto this plane to refine the representation. A more precise circular plane edge can be obtained by directly calculating the circle fitted by the innermost point among the exterior points. The outliers are easily identifiable in the provided Figure 8, simplifying the task. However, it is important to note that in practical engineering scenarios, identifying outliers can be challenging. Despite this difficulty, the method presented in the study offers a means to handle such cases and improve the accuracy of identifying circular holes in PC data.

Figure 8.

(a) Three types of point and (b) edge errors in scan data.

Considering that the surface of the PC is mostly flat, the PCA algorithm is initially employed for dimensionality reduction. Subsequently, the adjoining points of each detection point in the input data are divided into eight regions, as depicted in Figure 9. Points with at least one vacant region are designated as boundary points. To differentiate between inner and outer boundaries, two different numbers of adjacent points are defined based on the density of the input surface data. Consequently, the outer points must be determined through edge detection. This paper adopts the edge detection method described in the literature (Wang et al., 2019). Each central point is divided into eight regions by four lines, and the center points lacking NP (Normal points) in at least two areas are identified as boundary points.

Figure 9.

Boundary point diagnostic criterion. (a) Interior points (b) Mixture points (c) Boundary points.

In contrast to prior research, the focal point of this study lies in detecting linear boundary lines (such as edge lines) of planes when only surfaces with a single defined edge can be effectively scanned. As outlined in this study, previous investigations into edge line estimation did not explicitly address the issue of edge loss. In most scenarios, mixed pixels in laser scanning data are eliminated before estimating target edges. However, the straightforward removal of mixed pixels is not the optimal strategy for edge line estimation, as these mixed pixels also contain valuable information for detecting edge lines. Since edge lines intercept the laser beams used for mixed pixels, these mixed pixels indicate the position of the edge lines. This study did not devise a novel mixed pixel filtering algorithm; instead, existing algorithms were utilized for mixed pixel detection, and the information from detected mixed pixels was leveraged to enhance the precision of edge line estimation.

The geometric and algebraic methods are the two main approaches to circle fitting frequently used in circular hole estimation. A given set of points is fit to a circle using geometric approaches that involve solving a nonlinear least squares problem. Gauss-Newton and Levenberg-Marquardt are well-known geometric techniques frequently used to fit circles (Gillard, 2011). This study proposes a method to estimate the size of a circular hole in PC data. The process starts with obtaining inner boundary points described in Section 2.2.1. Next, points close to the circular hole are selected and added to the inner boundary points. Specifically, each inner boundary point is associated with 100 adjacent points. After obtaining the augmented set of points, an iterative correction method is used to estimate the center and radius of the circular hole. This step helps refine the size estimation. Finally, the process involves calculating the edge circle fitting to extract information about the circular hole. The MSAC algorithm is employed to achieve this. The MSAC algorithm operates in three-dimensional space, which aids in accurately determining the properties of the circular hole. Overall, the proposed approach combines inner boundary point selection, iterative correction, and the MSAC algorithm to estimate the size of the circular hole in the given PC data.

To validate the effectiveness of the proposed method in this section, a simple experiment consisting of a target area was designed. The targets in the complex background were obtained using the SGM algorithm described in Section 2.1, and all the geometric information of the target plane was acquired using the algorithms outlined in Sections 2.2.1 and 2.2.2. To further validate the effectiveness of the computational framework proposed in this paper, a comparison was made between the computational accuracy and efficiency of the traditional algorithm, and laboratory verification was conducted to complete the assessment (Figure 10).

Figure 10.

Experimental data processing.

The comparison above and experimental data demonstrate that the algorithm proposed in this paper achieves the required level of accuracy for construction purposes. Following the completion of PC recognition and calculation of geometric information described above, comparing the calculated results with the design values is necessary. However, it is important to note that the coordinate system used in 3D laser scanning differs from the design and construction coordinate systems. Therefore, it becomes necessary to transform both coordinate systems into a common reference frame to compare the geometric information accurately. The target plane is perpendicular to the X-axis in the standard design coordinate system. Consequently, this paper chooses to convert the 3D scanning coordinate system to the construction coordinate system and subsequently assess the deviation in geometric information. Use the ICP algorithm to convert the scanning coordinate system to the construction coordinate system. The three-dimensional position information deviation of all target boards can be obtained by directly calculating the center coordinates of the design value and the recognized center coordinates.

Figure 11 describes the experimental scene’s real values, the proposed algorithm’s recognition accuracy, and the classical algorithm. As can be seen from Fig, although both the algorithm proposed in this paper and the edge values calculated by the classical method are errors, the relative error of the latter is larger. The error calculated directly through the edge is 2.50 mm, and the calculation size error considering the MP points proposed in this paper is 1.07 mm. So, the experimental results show that the algorithm proposed in this paper is more effective. This is because mixing points at the edges of the target are not considered. The computational geometry information framework proposed in this paper has a lower relative error and is more effective.

Figure 11.

Comparison of edge calculation results of two algorithms.

Engineering applications

To evaluate the efficacy of the proposed algorithm, a standing scanner is employed during the wall construction phase to scan the target wall and generate a 3D model. The key geometric information, including the target size, positioning, and turning angle, can be accurately obtained and utilized with CAD to compare the design and verify if the construction conditions are met. The case 1 scene is depicted in Figure 12 below, which comprises 8 square targets and 3 round targets. The scanning instrument employed is the Austrian RIEGL VZ-400i long-range 3D LS, with 1732921 points used. The construction error should not surpass the 0.5 cm tolerance specified in the drawing, and the deflection angle must not exceed 7°. Moreover, the set entropy threshold for the local entropy is approximately 0.02.

Figure 12.

Site conditions and required calculation information.

First, downsample the PC to 20%, compute all initial seed points, and start iterating. The calculation results are shown in Figure 13. The set angle and entropy value are, respectively, and the nearest neighbor k is 100, which is about the 1% of total target. As seen from the figure below, the colored area in Figure 13 only needs four iterations to cover the entire planet, and the angle set according to the PC distribution statistics and entropy can achieve satisfactory results

Figure 13.

PC three views and object segmentation.

The PC model is divided into two parts by the SGM algorithm, one of which is the steel background, and the other is our desired target. Take T9 as an example to show how to extract objects from a complex background of rebar. Then, the completed plane is formed through the fourth iteration. Although all 11 jets have been identified through the first step, it can be seen that the scene blocks T2, T3, and T6, resulting in the target area being blocked and the scanning area missing. It is easy to understand that once a PC is missing. The missing part is not symmetrical about the center point, so calculating the center point by the mean of all PC coordinates will inevitably cause errors. Calculating the edge of the circular and square targets first and then passing the edge line is necessary. Calculate the coordinates of the center point. All the resulting target PCs are processed below according to the framework in 2.2. Under the existing conditions, the calculation time of the algorithm proposed in this paper and the traditional algorithm is 10.15s and 19.23s, respectively, and the computational efficiency is improved by about five times. The algorithm proposed in this paper has only one parameter that needs to be set manually, while the traditional algorithm has three. Details can be found in Table 1.

Table 1.

Comparison of algorithm.

Compactarison of parameters
Number (k)	DPC(s)	IDPC(s)	Increased efficiency
3000	1.9	0.38	79.8%
5000	4.8	1.49	68.9%
7000	9.3	2.95	68.2%
9000	15.3	4.63	69.7%
15000	43.9	10.88	75.2%
20000	82.1	17.34	78.9%
30000	170	29.08	82.9%

Although there is a certain interval between the target plane and the background layer of the rebar, the target plane is relatively complete. However, extracting the target plane from the complex background is difficult by directly using the plane detection method that considers the main direction. As shown in Figure 14, the SGM algorithm proposed in this paper can accurately extract the ROI area from the complex steel background. If the traditional method is used to identify the target plane, it can be seen that the identified ROI area is accurate. The reason is that although all planes have a certain interval from the background layer, the interval size differs. The traditional plane detection method that considers the main direction cannot consider each embedded plate’s local PC processing but performs plane recognition from the overall PC. Suppose all the target PC planes are strictly in one plane. In that case, the above method can achieve the effect, but in the actual project, due to the comprehensive accumulation of scanning errors and construction errors, all target planes are not in the same plane, so SMG is required. The algorithm considers local PC operations to achieve all target plane extraction (Figure 15).

Figure 14.

Plane classification.

Figure 15.

Algorithm comparison.

Figure 16(a) and (b) show that the calculation still has high accuracy in processing the target rotation angle and positioning, sufficient to meet the requirements of engineering acceptance. Whether the settlement result of the mixed point is considered when calculating the turning angle and the positioning information has little effect. The errors of the two algorithms are both about 1 mm. The three calculation results prove that the algorithm proposed in this paper has good accuracy and computational efficiency and can be applied in practical engineering. Figure 16 below shows the error of the center point coordinates of all targets and the design value in three directions. It can be seen from Figure 16 that in the algorithm in this paper, without considering the mixed point, the direct calculation results of the two strategies are very different. Because it is regarded as a mixed PC, the projection is centrosymmetric, so it does not affect the calculation result of the center point coordinates. It is noteworthy that the algorithm presented in this paper requires only 5–10 minutes from setting up the scanner to obtaining the results. In large-scale projects or complex environments, such as the construction of major nuclear power plants, the ability to quickly and accurately inspect embedded components ensures construction progress and prevents delays and resource waste due to inspection hold-ups.

Figure 16.

(a) Edge error, (b) Corner error, and (c) Location error between the proposed algorithm and the traditional algorithm.

Conclusion

This paper presents a method based on three-dimensional laser scanning technology for the acceptance inspection of embedded components in nuclear power plant walls. Experimental results demonstrate that this method maintains millimeter-level accuracy within a scanning distance of 20 m, ensuring high precision and reliability in data collection. We delve into the specific advantages of this method in practical engineering applications. Firstly, it significantly improves detection accuracy, effectively reducing errors compared to traditional manual measurement methods, thus ensuring the precise installation of embedded components and overall construction quality. Secondly, by minimizing manual operations, it enhances inspection efficiency, substantially shortens acceptance time, and lowers labor costs. Additionally, application cases in actual construction indicate that this method can significantly improve work efficiency on-site, ensuring construction progress and quality, thereby offering considerable practical value. The key findings of this research are outlined as follows:

(1) An innovative iterative algorithm is developed for identifying planes in complex backgrounds. Compared to the traditional region-growing algorithm, this method exhibits enhanced robustness in initial point selection and enables simultaneous iteration of all initial points. The data indicates an efficiency improvement of nearly two times compared to the region-growing algorithm.

(2) Addressing the issue of manually selecting numerous parameters in the PC processing algorithm, this paper derives the entropy threshold of the proposed algorithm based on the PC model’s thickness caused by PC errors. This approach mitigates the influence of manual selection on the calculation results.

(3) This paper proposes a framework to achieve faster and more accurate computation of geometric information for plane identification. The framework integrates the k-dimensional tree as a substitute for local density in the density peak clustering algorithm and incorporates edge calculation that considers mixture points. The data reveals an approximate 80% reduction in computational complexity compared to the original algorithm. Moreover, the framework accounts for mixed PC when computing edge information, reducing calculation dimensional errors.

(4) The traditional method of measuring a wall using a tape measure typically requires three people and takes about half an hour to an hour. In contrast, the method proposed in this paper requires only one person and takes only 5 to 10 minutes, including setup and calculations, significantly enhancing measurement efficiency. Moreover, the accuracy of this method can be maintained at a level consistent with that of manual measurements.

Footnotes

ORCID iD

Jian Zhang

Funding

The authors disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The research presented was financially supported by the National Key R&D Program of China (No.: 2022YFC3801700) and the National Natural Science Foundation of China (No. 52378289).

Declaration of conflicting interests

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

References

Besl

McKay

(1991) A method for registration of 3-D shapes. In: Paper Presented at the Sensor Fusion Conf: Control Paradigms and Data Structures, SPIE.

Chen

Shen

, et al. (2015) Collaborative mobile-cloud computing for civil infrastructure condition inspection. Journal of Computing in Civil Engineering 29(5): 04014066.

Chen

Kira

Cho

(2019) Deep learning approach to point cloud scene understanding for automated scan to 3D reconstruction. Journal of Computing in Civil Engineering 33(4): 04019027.1–04019027.10.

Czerniawski

Sankaran

Nahangi

, et al. (2018) 6D DBSCAN-based segmentation of building point clouds for planar object classification. Automation in Construction 88: 44–58.

Filin

Pfeifer

(2006) Segmentation of airborne laser scanning data using a slope adaptive neighborhood. ISPRS Journal of Photogrammetry and Remote Sensing 60(2): 71–80.

Fotsing

Nziengam

Bobda

(2020) Large common plansets-4-points congruent sets for point cloud registration. ISPRS International Journal of Geo-Information 9(11): 647.

Frias

Pinto

Sousa

, et al.(2022) Exploiting BIM objects for synthetic data generation toward indoor point cloud classification using deep learning. Journal of Computing in Civil Engineering 36(6): Article 4022032.

Gillard

(2011) Circular and linear regression: fitting circles and lines by least squares. Journal of the Royal Statistical Society - Series A: Statistics in Society 174: 843.

Grilli

Menna

Remondino

(2017) A review of point clouds segmentation and classification algorithms. In: Paper presented at the conference on 3D virtual reconstruction and visualization of complex architectures, ISPRS.

10.

Huang

Zhu

Yang

, et al. (2016) A non-parameter outlier detection algorithm based on Natural Neighbor. Knowledge-Based Systems 92: 71–77.

11.

Huang

Wei

Liu

(2019) An efficient encoding voxel-based segmentation (EVBS) algorithm based on fast adjacent voxel search for point cloud plane segmentation. Remote Sensing 11(23): 2727.

12.

Jauregui

White

Woodward

, et al. (2003) Noncontact photogrammetric measurement of vertical bridge deflection. Journal of Bridge Engineering 8(4): 212–222.

13.

Jiang

Zhang

(2019) Real‐time crack assessment using deep neural networks with wall‐climbing unmanned aerial system. Computer-Aided Civil and Infrastructure Engineering 35(6): 549–564.

14.

Kang

Wang

Kang

(2012) Image segmentation with complicated background by using seeded region growing. AEU-International Journal of Electronics and Communications 66(9): 767–771.

15.

Kim

Son

Kim

(2013) Automated construction progress measurement using a 4D building information model and 3D data. Automation in Construction 31: 75–82.

16.

Kim

Wang

Park

, et al. (2016) Automated dimensional quality assurance of full-scale precast concrete elements using laser scanning and BIM. Automation in Construction 72: 102–114.

17.

Yang

Zhu

, et al. (2017) An improved RANSAC for 3D point cloud plane segmentation based on normal distribution transformation cells. Remote Sensing 9(5): 433.

18.

Liu

Wang

(2018) Shared-nearest-neighbor-based clustering by fast search and find of density peaks. Information Sciences 450: 200–226.

19.

Maalek

Lichti

Walker

, et al. (2019) Extraction of pipes and flanges from point clouds for automated verification of pre-fabricated modules in oil and gas refinery projects. Automation in Construction 103: 150–167.

20.

Olsen

Kuester

Chang

, et al. (2010) Terrestrial laser scanning-based structural damage assessment. Journal of Computing in Civil Engineering 24(3): 264–272.

21.

Park

Lee

Adeli

, et al. (2007) A new approach for health monitoring of structures: terrestrial laser scanning. Computer-Aided Civil and Infrastructure Engineering 22(1): 19–30.

22.

, et al. (2017) PointNet: deep learning on point sets for 3D classification and segmentation. In: Paper presented at the 30th IEEE/CVF conference on computer vision and pattern recognition (CVPR). IEEE.

23.

Raguram

Frahm

Pollefeys

(2008) A comparative analysis of RANSAC techniques leading to adaptive real-time random sample consensus. In: Paper presented at the 10th European conference on computer vision (ECCV 2008). Springer.

24.

Rashidi

Brilakis

Vela

(2015) Generating absolute-scale point cloud data of built infrastructure scenes using a monocular camera setting. Journal of Computing in Civil Engineering 29(6).

25.

Rodriguez

Laio

(2014) Machine learning. Clustering by fast search and find of density peaks. Science 344(6191): 1492–1496.

26.

Rusu

Marton

Blodow

, et al. (2008) Towards 3D point cloud based object maps for household environments. Robotics and Autonomous Systems 56(11): 927–941.

27.

Schnabel

Wahl

Klein

(2007) Efficient RANSAC for point-cloud shape detection. Computer Graphics Forum 26(2): 214–226.

28.

Tang

Huber

Akinci

, et al. (2010) Automatic reconstruction of as-built building information models from laser-scanned point clouds: a review of related techniques. Automation in Construction 19(7): 829–843.

29.

Teboul

Simon

Koutsourakis

, et al. (2010) Segmentation of building facades using procedural shape priors. In: Paper Presented at the 23rd IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE.

30.

Tian

Zhang

Jiang

, et al. (2021) Noncontact cable force estimation with unmanned aerial vehicle and computer vision. Computer-Aided Civil and Infrastructure Engineering 36(1): 73–88.

31.

Tommaselli

AMG

Reiss

MLL

(2005) A photogrammetric method for single image orientation and measurement. Photogrammetric Engineering & Remote Sensing 71(6): 727–732.

32.

Turkan

Bosche

Haas

, et al. (2012) Automated progress tracking using 4D schedule and 3D sensing technologies. Automation in Construction 22: 414–421.

33.

Truong-Hong

Laefer

, et al. (2015) Octree-based region growing for point cloud segmentation. ISPRS Journal of Photogrammetry and Remote Sensing 104: 88–100.

34.

Wang

Kim

Cheng

JCP

, et al. (2016) Automated quality assessment of precast concrete elements with geometry irregularities using terrestrial laser scanning. Automation in Construction 68: 170–182.

35.

Wang

Cheng

JCP

Sohn

(2017) Automated estimation of reinforced precast concrete rebar positions using colored laser scan data. Computer-Aided Civil and Infrastructure Engineering 32(9): 787–802.

36.

Wang

Sohn

Cheng

JCP

(2019) Development of high-accuracy edge line estimation algorithms using terrestrial laser scanning. Automation in Construction 101: 59–71.

37.

Widyaningrum

Peters

Lindenbergh

(2020) Building outline extraction from ALS point clouds using medial axis transform descriptors. Pattern Recognition 106: 107447.

38.

Xiong

Adan

Akinci

, et al. (2013) Automatic creation of semantically rich 3D building models from laser scanner data. Automation in Construction 31: 325–337.

39.

Ding

, et al. (2018a) DPCG: an efficient density peaks clustering algorithm based on grid. International Journal of Machine Learning and Cybernetics 9(5): 743–754.

40.

Yao

Tuttas

, et al. (2018b) Unsupervised segmentation of point clouds from buildings using hierarchical clustering based on gestalt principles. Ieee Journal of Selected Topics in Applied Earth Observations and Remote Sensing 11(11): 4270–4286.

41.

Zhao

Jiang

Liu

, et al. (2022) Automated recognition and measurement based on three-dimensional point clouds to connect precast concrete components. Automation in Construction 133: 104000.