1 Introduction
In recent years, with the development of virtual reality and computer graphics, 3D scene models have been widely used in smart cities, 3D map navigation, and cultural and entertainment scenarios, attracting a large number of scholars to study them. In the 3D reconstruction of urban scenes, planes are crucial elements in the final polyhedral geometric model, making plane extraction a key step in solving the problem.
Plane extraction involves extracting potential planes from acquired 3D data. Traditional methods (primarily processing point cloud models) include plane fitting algorithms based on Random Sample Consensus (RANSAC), region growing algorithms based on data similarity, and plane fitting algorithms based on Hough transform. Due to the massive data volume and high noise levels of point clouds, point cloud-based plane extraction algorithms are often time-consuming and have poor accuracy. Currently, the research objects in 3D reconstruction of urban scenes are mainly regular objects, such as buildings in cities, which are usually composed of regular edges. By observing and analyzing these edges, the overall shape of the building can be inferred. The concept of line clouds is similar to that of point clouds, consisting of a collection of line segments. Compared to point cloud data, 3D line segments are higher-level geometric data, containing not only positional information but also directional information that 3D points cannot represent. Furthermore, line cloud data is smaller than point cloud data in the same scene. Therefore, the rational use of line segment information can reduce the difficulty of plane extraction and improve its efficiency and accuracy.
Given the advantages of line clouds, such as small data volume and large information content, researchers have gradually shifted their focus to acquiring 3D line cloud data in recent years and have begun to study 3D reconstruction algorithms based on line cloud data. However, there are currently few methods for plane extraction based on 3D line clouds. Although they can be implemented by analogy with point cloud plane extraction algorithms, these methods all have certain limitations. For example, unlike region-growing algorithms which rely on the selection of initial seeds and require relatively dense data, RANSAC-based plane extraction methods are suitable for sparse data. However, because this method uses random sampling, it is highly dependent on the number of samplings and the randomness leads to insufficient accuracy of the results. Methods based on Hough transform first project the original data onto Hough space, mapping a plane in the real space to a point in the Hough space, and then use a voting mechanism to determine the parameters of the plane. Since the parameters of each plane vary greatly, it is difficult to determine the range of the parameter space of this method, and mesh generation is also difficult. Although Hough space represented by polar coordinates can effectively reduce the range, it is still difficult to uniformly divide the space.
To address the problems of the above-mentioned plane extraction algorithms based on 3D line clouds, this paper proposes a new plane extraction algorithm based on line cloud data. The main steps include: First, mapping each line segment of the input line cloud to a point on the Gaussian sphere; second, using spiral curve Fibonacci sampling to perform approximately uniform sampling on the surface space of the Gaussian sphere, and fitting the plane passing through the center of the sphere; then, separating parallel planes based on the intercept information of the plane equation and using singular value decomposition to correct the sampling error; finally, iteratively fitting all possible planes. This method has two innovative points: (1) transforming the problem of extracting planes from line clouds into the problem of extracting planes from the surface space of the Gaussian sphere.
(1) Sampling problem simplifies the complexity of the problem; (2) Using spiral curve Fibonacci sampling on the surface of Gaussian sphere makes the sampling space distribution more uniform and improves the quality of final plane extraction.
2. Related Work
Based on the classification of input sources of 3D data, plane fitting algorithms can be divided into plane extraction algorithms based on point cloud models and plane extraction algorithms based on line cloud models.
2.1 Planar Extraction Algorithm Based on Point Cloud Model
The RANSAC-based plane extraction algorithm first randomly samples points that can form a plane; then it calculates the distance from the remaining points to the plane, counts points whose distance is less than a certain threshold and classifies them into the plane, and then calculates the number of points on the final plane. After multiple iterations, the plane with the most points is selected as the newly fitted plane. Then, iterative fitting of other planes continues in the remaining data until a termination condition is met. This method can achieve good results with appropriate parameter selection, but due to random sampling and reliance on parameter control, the results may not be the actual optimal solution. Li et al. proposed a method that uses normal direction and proximity information to extract all substructures from the point cloud, and then performs plane information extraction on the substructures. As a variant of the RANSAC-based method, this method significantly improves the accuracy of the reconstruction results, but its drawback is the difficulty in determining the size of the substructures. Yue et al. proposed a RANSAC segmentation method based on normal clustering and constrained initial points. This method first uses the Mean Shift method to solve for the point cloud normals, and then executes the RANSAC method to complete the plane segmentation based on the initial constraints of the normals. Region-growing methods first select seed points, then set growth and termination conditions. The algorithm automatically searches for all points constituting the plane. However, the lack of a unified standard for seed point selection limits the accuracy and robustness of region-growing algorithms. Currently, many efficient initial point selection methods have been proposed, among which the most classic method is to use the point with the minimum curvature in the point cloud as the initial point for region growing. Region-growing algorithms are simple to implement, but they are very sensitive to noise. When different regions are excessively smoothed, the system has difficulty distinguishing planar structures. Li et al. used hierarchical clustering to solve the problem of initial point selection difficulties and completed the task of roof plane segmentation. Methods based on Hough transform—using a voting mechanism to project the original data onto Hough space to determine specific parameters—are often used for detecting two-dimensional lines and circles. For a three-dimensional plane, each point in Hough space corresponds to a plane in real space. By discrete sampling and statistically analyzing the peak values in Hough space, the parameters of the plane in three-dimensional space can be determined. Although such methods are not sensitive to noise, they suffer from inconsistent parameter spatial distribution. In response, some scholars have proposed solutions. For example, Zhang Dayong et al. used a three-dimensional Hough transform method based on dual space partitioning to divide the spherical sampling region into multiple symmetrical regions. Then, sampling was performed in these regions using different parameters, which to some extent eliminated the inconsistency in the sampling region caused by the transform. In addition, Tian et al. used GPU parallel acceleration to implement a plane extraction algorithm based on Hough transform, achieving fast plane detection of three-dimensional LiDAR point clouds.
2.2 Planar Extraction Algorithm Based on Line Cloud Model
Compared to extracting planes from point cloud data, there is currently limited research on methods for plane extraction using contour information such as line segments. Wu et al. proposed a method to first obtain the structure of intersecting line segments from the point cloud and then further extract plane information. Zhang et al. utilized local information, calculating the distance between line segments and performing spectral clustering to extract the plane structure. However, this method requires calculating local information, and the distribution density of line segments on different planes in real-world buildings can vary significantly, making it difficult to set the parameter range. Cabo et al. used laser scanning data and detected planes using 3D line segments; however, they leveraged the powerful characteristics of LiDAR data acquisition, namely, the acquisition of parallel and dense line clouds.
In summary, most plane extraction algorithms are based on point cloud models or analyze line segment information within point cloud models to perform plane fitting, and the system still needs to process a large amount of point cloud data. There is relatively little research on extracting planes directly using line cloud models as input, and existing line cloud model-based plane extraction algorithms have poor universality, usually requiring high-quality input line clouds, such as uniformly distributed line cloud information or densely parallel line clouds.
3. Algorithm for Plane Extraction from 3D Line Cloud Model Based on Fibonacci Sampling
This paper proposes a novel Fibonacci sampling-based planar extraction algorithm for 3D line cloud models. The algorithm mainly includes four steps: data acquisition and preprocessing, spherical approximate uniform sampling, statistical sampling points, and planar fitting. Among them, the statistical sampling points and planar fitting steps are iterative processes, and the process is shown in Figure 1.
3.1 Data Acquisition and Preprocessing
3.1.1 Data Acquisition
The input to the algorithm in this paper is a 3D line cloud. To facilitate data acquisition, this method uses Line3D proposed by Hofer et al. to obtain the 3D line cloud of the scene from multiple images. Similar to 3D point reconstruction, 3D line segments are reconstructed using the straight line structure in the image. Hofer et al. used the camera pose provided by Structure-from-Motion to solve the problem of line segment matching between different images, thereby constructing the 3D line cloud. The algorithm in this paper first uses a consumer-grade camera to acquire several scene images, and then inputs the image sequence into Line3D to reconstruct the original line cloud as the input of the algorithm. The acquired 3D line cloud is represented by a set L, where k represents the total number of line segments in the line cloud model; li represents the i-th line segment located in set L. An example of extracting a line cloud from an image sequence is shown in Figure 2.
Figure 1. Method Flowchart
Figure 2 Data Acquisition
3.1.2 Data Preprocessing
The original input 3D line cloud model is highly complex, with line segments arranged in a chaotic manner. Different line cloud models also have different spatial ranges, making data processing difficult. Since determining whether a line segment lies on a specific plane depends on its direction and whether there is an intersection point, and is independent of its length, this paper maps each line segment in the line cloud model to a Gaussian sphere with a radius of 1, as shown in Figure 3. Specifically, the length of each 3D line segment is first normalized; then each line segment is translated so that one endpoint of the segment lies at the origin, and the other endpoint lies on a Gaussian sphere with a radius of 1. Mapping the 3D line cloud model L onto the Gaussian sphere yields a new set of points, where k represents the total number of line segments in the set; si represents the i-th point in set S. The elements in set L correspond one-to-one with those in set S.
Theoretically, a set of coplanar line segments in space corresponds to a plane passing through the center of a Gaussian sphere. Therefore, the problem of plane extraction based on 3D line segments can be transformed into the problem of detecting planes passing through the center of a Gaussian sphere. Simultaneously, for each circular surface passing through the center of the Gaussian sphere, its normal vector, represented by a unit vector, also corresponds exactly to a point on the Gaussian sphere. Thus, determining the plane passing through the center can also be transformed into determining a point on the Gaussian sphere. This approach not only simplifies the representation of 3D line segments and reduces the difficulty of data processing, but also transforms the complex plane fitting problem into a point sampling problem on the Gaussian sphere.
It's worth noting that points on a Gaussian sphere only represent the direction of a 3D line segment, losing positional information perpendicular to that direction. Therefore, after detecting the circle with the center of the Gaussian sphere, the set of coplanar points on that circle may not all correspond to the set of line segments in the original 3D line cloud model. Further processing, combining this with the original 3D line segment information, is required in subsequent steps. However, overall, transforming the complex plane fitting problem into a point sampling problem on a Gaussian sphere greatly simplifies the problem.
3.2 Spherical Approximate Uniform Sampling
Although the data is simplified after preprocessing, point-based plane detection is not suitable for direct implementation using RANSAC due to noise. Methods based on the Hough transform struggle to generate uniform grids, resulting in uneven sampling spatial distribution. Inspired by the voting mechanism of the Hough transform, this paper uses a spiral curve Fibonacci sampling method to approximate uniform sampling of points on a Gaussian sphere to obtain possible plane normals, thereby determining the plane passing through the center of the Gaussian sphere. Using a Fibonacci spiral curve to generate uniformly distributed points on the sphere yields excellent results. Studies have shown that compared to measuring the area of irregular shapes on a sphere using a latitude-longitude grid, using a Fibonacci grid to measure the area of irregular shapes on a sphere can reduce the weighted error by 40%.
The set of sampling points is denoted by , where n represents the total number of sampling points in the set; ti represents the i-th sampling point in the set T. Figure 4 shows a schematic diagram of sampling a Gaussian sphere using spiral curve Fibonacci sampling.
Figure 3 Data Preprocessing
Figure 4. Schematic diagram of sampling points
3.3 Statistical Sampling Points
Unlike the statistical method in the Hough transform, each sampling point in the approximately uniform sampling process represents the normal vector of the corresponding plane. Therefore, after the approximately uniform sampling process, it is necessary to count the number of all points on the circular surface passing through the center of the Gaussian sphere, determined by the sampling point as the normal vector. When the number of points is greater than a specified threshold, it indicates that these points on the circular surface can fit the circular surface, meaning that there may be a plane to be fitted to the set of line segments in the original 3D line cloud. The specific process of counting sampling points includes: for each sampling point, calculating the angle between the vector osj formed by the center o of the Gaussian sphere and each point on the Gaussian sphere and the direction of the sampling point ti . When it is within the range, the point on the Gaussian sphere is considered to belong to the sampling point ti . Since there are errors in the acquisition process of the line cloud model, the direction of each line in 3D space cannot be accurately obtained. Therefore, this paper sets an angle error threshold. If the angle between two vectors is within the error range, the two vectors are considered to be perpendicular. For each sampling point, count the number of all points on the circular surface passing through the center of the Gaussian sphere, find the set of points Sm with the largest number of points and the subset Lm of the original set of line segments corresponding to Sm , and record the corresponding sampling point tm . The set of line segments Lm and the sampling point tm will be used as the basis for plane fitting.
3.4 Plane Fitting
The statistical sampling process yields the set of line segments L<sub> m </sub> corresponding to the plane to be fitted. However, because the intercept information of the lines is lost when mapping the 3D line segments onto the Gaussian sphere, the set of line segments L<sub> m </sub> obtained by the statistical sampling process may represent a plane or multiple parallel planes. That is, the set of 3D line segments coplanar on the Gaussian sphere may lie on multiple parallel planes in the real space. Given that these planes have the same normal and only have different intercepts, multiple parallel planes can be separated based on the differences in the intercepts.
To extract a precise single plane, this paper uses the intercept information of the plane to divide the set of line segments, and selects the set of line segments with the largest number of segments after the division as the plane extracted in this iteration. The process of one plane fitting is as follows:
(1) Given the set of line segments Lm obtained during the statistical sampling process and the unit direction vector u corresponding to the sampling point tm .
(2) For each original line segment, take its midpoint as the representative and calculate the projection d i in the direction of vector u.
(3) Calculate the intercept dp of the plane P with vector u as the normal, such that the number of intercepts in the set C of line segments within the range is maximized, where is the distance error threshold. Then, singular value decomposition is used on the set of line segments of the plane to correct the error caused by range sampling, so as to determine the final plane parameters.
(4) When the number of line segments in the line segment set C is less than the specified threshold λ, it means that the line segments in set C cannot form a plane, and the plane extraction algorithm ends.
After each iteration of the plane fitting process, the set of line segments C used to construct the plane, as well as the corresponding points on the Gaussian sphere, need to be deleted. The original set of line segments L and the set of points S on the Gaussian sphere are then updated. The next round of statistical sampling and plane fitting is then performed until the algorithm reaches its termination condition.
Furthermore, after completing the iterative process of plane fitting, due to the inherent error in the discrete sampling normals, two or more extracted planes may be very similar, as shown in Figure 5. The two planes in Figure 5(a) and Figure 5(b) correspond to the same plane in the original model. Therefore, a post-processing step is required after plane extraction: planes that are parallel to each other within the angle error threshold and whose intercept difference is within the distance error threshold are merged, and singular value decomposition is used to correct the final plane parameters. In this paper's method, a value of 2 is used, and the post-processing result is shown in Figure 5(c). It should be noted that obtaining multiple similar planes is a problem inherent in all plane fitting algorithms; therefore, in this experiment, the same post-processing operation is performed on all plane fitting methods.
4 Results and Discussion
Compared with other traditional methods, the plane extraction algorithm proposed in this paper is characterized by directly using line clouds as algorithm input, resulting in high integrity and quality of extracted planes. High integrity of extracted planes indicates strong plane extraction capability. To verify the effectiveness of the proposed algorithm, experimental results are analyzed from two aspects: (1) integrity and efficiency of extracted planes; (2) quality of extracted planes. Furthermore, experiments were conducted on multiple data samples, and the results were compared with those of traditional methods.
4.1 Experimental Setup
The experimental parameters for different methods should be kept as consistent as possible. The parameters used in this experiment are shown in Table 1.
The distance error threshold indicates that when the distance between a line and a parallel plane is within a certain range, the line is considered to be on the parallel plane; in this experiment, it is set to 0.1 m. The angle error threshold indicates that when the angle between two lines is within a certain range, the two lines are considered to be perpendicular; in this experiment, it is set to 1.5 ˚. Since the sampling space is divided according to latitude and longitude in the Hough transform, the angle threshold in the Hough transform is related to the actual sampling size; therefore, no angle error threshold is set in the Hough transform method. λ represents the minimum number of line segments that can form a plane; in all three methods, it is set to 15.
Table 1 Parameters of different algorithms
Figure 5. Two planes that are repeatedly expressed
Figure 6 Comparison of planar extraction results
In addition to the common parameters mentioned above, each method requires setting additional, different parameters. In the RANSAC-based method, the number of random samples needs to be specified; this paper sets the number of random samples to 10,000. In the Hough transform method, the sampling step size needs to be specified as the angular difference between sampling points in the Hough space; in the experiment, the sampling step size was set to 18 ˚. Experiments showed that at a step size of 18 ˚, 10,000 samples are required in the Hough space. Furthermore, this paper's method requires specifying the number of sampling points needed for approximate uniform sampling; to ensure consistency with the sampling count of the Hough transform-based and RANSAC-based methods, this paper sets the number of sampling points to 10,000.
4.2 Integrity
One criterion for evaluating plane extraction algorithms is the completeness of the extracted planes, i.e., the ability to extract more planes that conform to the original line cloud model from the line cloud. This paper conducts experiments on four line cloud model instances and compares the results with those of traditional methods. The line segment extraction results of different methods are shown in Figure 6. Figure 6(a) shows the four input line cloud models, and Figures 6(b-d) show the plane extraction results of the RANSAC-based method, the Hough transform-based method, and the proposed method, respectively. Different extracted planes are marked with different colors. The results show that the proposed method extracts more complete planes with the fewest missing line segments.
Figure 7. Comparison of effective and ineffective planes
Table 2 Comparison of results from different plane extraction methods
The higher the completeness of the plane extraction algorithm, the more planes that conform to the original line cloud model are extracted from the line cloud. To quantitatively evaluate the completeness of the extracted planes, this paper statistically analyzes the number of planes extracted by the plane fitting algorithm and the proportion of effective planes. Generally, the more planes extracted, the better the plane fitting algorithm's ability to represent the original data. However, not all extracted planes conform to the original data; that is, the planes extracted by the algorithm differ significantly from the corresponding planes in the original line cloud data, and these planes cannot effectively represent the original data. Therefore, this paper also statistically analyzes the proportion of effective planes in the plane fitting algorithm to further measure its ability to represent the original line cloud model data.
The statistical results of the experiments conducted using different planar extraction methods on four line cloud model instances are shown in Table 2. The data in the table are the average results of 10 algorithm runs. Among them, Model 1 and Model 2 are relatively clean line cloud data, while Model 3 and Model 4 are noisier line cloud data, and the scene of Model 4 is more complex.
As shown in Table 2, among the four model examples, the method presented in this paper extracts the most effective planes and has the highest proportion of effective planes, indicating that the planes extracted by this method are more complete. The extraction results of the RANSAC-based method are also excellent, but because random sampling may produce suboptimal results, some unreasonable planes may be extracted. Figure 7 shows a comparison of the results of extracting effective and invalid planes. Figure 7(a) shows the expected extracted plane region, Figure 7(b) shows the plane extracted by the algorithm in this paper, and Figure 7(c) shows the plane extracted by the RANSAC-based method. The results show that the planes extracted by the method in this paper correspond well to the original line cloud and are denoted as one effective plane. However, the RANSAC-based method, due to the influence of outlier line segments, interferes with the plane extraction process, resulting in a large deviation between the extracted planes and the original line cloud; these are denoted as invalid extracted planes. The Hough transform-based method, due to the uneven sampling space, extracts more unreasonable planes, resulting in a low proportion of effective planes and poor plane extraction completeness. As shown in Table 2 for Models 3 and 4, when the line cloud data contains significant noise, the proportion of effective planes extracted by the RANSAC-based method and the Hough transform-based method decreases significantly. This is because outlier noisy line segments significantly interfere with the random sampling process of RANSAC, and the Hough transform-based method is more sensitive to noise. Compared to the other two algorithms, the proposed method still performs very stably for line cloud data with significant noise and complex scenes.
Figure 8. Comparison of results from different methods for extracting the same plane
In terms of runtime, the Hough transform-based method has the best time complexity because it uses dual information to calculate which sampling points each line segment passes through, without traversing every single sampling point. The RANSAC-based method and the method presented in this paper are slightly slower than the Hough transform-based method. When the scene data contains significant noise and the scene is complex, the efficiency of the Hough transform-based method decreases because it extracts many unreasonable planes.
4.3 Quality of the extracted plane
Another criterion for evaluating the effectiveness of plane extraction algorithms is the quality of the extracted planes. Since it is difficult to quantitatively assess the quality of plane extraction, this paper compares the experimental results of extracting the same plane using different methods and performs a qualitative analysis of these results. Figure 8 shows the results of different methods extracting the same plane, displaying the fitting results of four planes from top to bottom. In Figure 8(a), the area within the red box represents the region in the original image and line cloud corresponding to the extracted single plane. Figures 8(b-d) show the single planes extracted by the RANSAC-based method, the Hough transform-based method, and the method presented in this paper, respectively. Due to the lack of true plane parameters for the extracted planes, it is difficult to quantify the accuracy of the extracted planes. However, by observing the composition of the line segment set in the extracted plane, the quality of the extracted plane can be intuitively perceived. When the line segment set on the plane fits more closely to the original line cloud and the reference image, the extraction of that plane can be considered more accurate.
As shown in Figure 8, the line segment set extracted by the proposed method more accurately corresponds to the original line cloud model and the planar structure in the image, and contains less information about line segments from other planes. This largely reflects the higher accuracy of the planar parameters extracted by the proposed algorithm. This is mainly because the proposed method uses a spiral curve Fibonacci method for approximately uniform sampling, making the spatial division more uniform, thus resulting in a more accurate and better-performing set of line segments for the fitted plane. Compared to the other two methods, the RANSAC-based method yields the worst overall quality in plane extraction. This is because the method randomly samples and constructs the initial plane, leading to poor stability of the extracted planar parameters.
5. Conclusion
This paper proposes a plane extraction method based on a line cloud model and employs a spiral curve Fibonacci method to approximately uniformly partition the sampling space to improve the plane fitting results. Experimental results show that compared with RANSAC-based and Hough transform-based methods, the proposed method has superior performance in terms of the completeness and quality of extracted planes. However, the proposed method still has certain limitations—its running efficiency is relatively slow. Future work will focus on further improving the efficiency of the algorithm while maintaining the existing plane extraction performance.
Authors: Wu Kai 1,2, Zhou Jiaxin 1,2, Cheng Zhanglin 1*
1. Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences
2 School of Computer Science and Technology, University of Chinese Academy of Sciences
Reprinted from "Integration Technology"
