EXTRACTION OF ORTHOGONAL BUILDING BOUNDARY FROM AIRBORNE LIDAR DATA BASED ON FEATURE DIMENSION REDUCTION

: Building boundary extraction is an active research topic in the field of feature extraction from airborne LiDAR point cloud data. Owing to the high complexity of most building extraction algorithms based on point clouds, multiple feature parameters must often be combined with iterative operations, particularly in the process of mitigating the sawtooth phenomenon using the sleeve algorithm and its improved versions. To improve the degree of automation and ensure accuracy, this study proposes a fast corner point detection method based on a dimensionality reduction technique, which utilizes reduced data mapping from 3D to 2D. We converted the boundaries extracted by the alpha shape algorithm to a 2D image and applied recursive Gaussian filtering with a relatively high level of automation to smoothen the image edges and mitigate the sawtooth phenomenon, thereby improving upon the sleeve algorithm, which requires a large number of iterations. Subsequently, the DouglasPeucker algorithm is used to retrieve the contour key points after extracting the contour lines and obtaining the regularized building contours using the grouped orthogonal regularization method. To verify the accuracy of the algorithm, it was compared with a cluster and adjustment (CAA)method based on the sleeve algorithm using three major evaluation metrics with respect to four representative building instances in two experimental datasets of urban areas. The value of the RMSE was reduced by an average of 43.79%. In addition, the time complexity decreased from O ( n 2 ) to O ( n ). These results demonstrate that the proposed method improves not only the accuracy of boundary extraction, but also the efficiency of data processing.


INTRODUCTION
The identification and extraction of building boundaries are important for topographic map repair, change detection, and many location-based services (Rau, 2012). Light detection and ranging (LiDAR) can provide precise surface 3D information of buildings and is able to preserve the real structure of the buildings after extraction (Fan et al., 2014;Guo et al., 2021). However, the LiDAR data used to generate simplified boundary lines require a significant number of iterations. By contrast, extracting buildings from high-resolution images cannot guarantee the recovery of the real building shape because key building parts may be missing. Despite these limitations, the process of building boundary extraction and simplification based on images is highly automatic and fast. Guo et al. (2021) used two types of data, namely point cloud and image, to extract buildings from the same area and demonstrated that the method based on LiDAR can provide more accurate extraction results. Therefore, the geometric properties and echo information of LiDAR point clouds are currently used by most researchers for building extraction (Dey et al., 2020;Polewski and Yao, 2019;Yao and Wu, 2021;Yi et al., 2017;Zhang et al., 2018). The alpha-shape algorithm is generally used to determine building boundaries (Chen et al., 2017;Jung et al., 2017;Sohn et al., 2012) and is simple, efficient, and stable. However, the results of the alpha shape algorithm exhibit sawtooth phenomenon and cannot be formed into regular shapes because of the discreteness of the point distribution. To solve these problems, the sleeve algorithm (Wei, 2008) * Corresponding author and its improved versions (Liu et al., 2020;Ping et al., 2020) have been proposed to filter out the rough boundaries in the extracted point cloud and retain key corner points, such as turn points. However, it is challenging to simultaneously find a suitable threshold for screening and obtain accurate results owing to the presence of the sawtooth phenomenon. Moreover, a large number of iterative experimental steps are generally required to obtain satisfactory results. Hence, this process is time and resource intensive. Furthermore, Widyaningrum et al. (2020) applied a shrinking circle algorithm to convert the ALS boundary points extracted by the alpha shape algorithm into medial axis transform (MAT) points. These MAT points were grouped into corresponding medial branches using corner-aware segmentation to extrapolate the corner point positions based on the radii. The segmentation step requires a large number of iterations to adapt the thresholds, which is time consuming. By contrast, the process of building boundary extraction and simplification based on images (Turker and Koc-San, 2015;Zhu et al., 2020) is automatic and fast. RAN et al. (2020) proposed an automated method to extract and optimize building boundaries using Canny detection and the Hough algorithm. This method features a high degree of automation in the boundary extraction process without the need for a tedious iterative process. However, it does not make full use of the structural characteristics or rules of the building target, which may affect the accuracy of subsequent building extraction. Image-based methods for building extraction can be broadly classified into two categories: (1) building extraction based on artificially designed features (Alshehhi et al., 2017;Ghanea et al., 2016) and (2) building extraction based on deep learning (Lv et al., 2019;Szegedy et al., 2015;Zhou et al., 2020). The artificial-feature-based ap-proach relies mainly on geometric, spectral, and architectural information features to achieve building extraction in remote sensing images. Owing to the complex background information present in remote sensing imagery and the low distinguishability between building features and backgrounds, building contours can often be missing or distorted. Although an automated neural network can extract the distinctive features of an input image, it may fail to detect certain object details because of large variations in building textures. Therefore, the imagebased automatic building boundary extraction method may not be suitable for accurate extraction of buildings from images, but is more efficient.
To solve the problem of inaccurate and ineffective corner point extraction resulting from simplifications in the sleeve algorithm, this study proposes a method based on a dimensionality reduction technique, which reduces the initial contour extracted by the alpha shape algorithm from airborne LiDAR data into a 2-D image. The image is used to mitigate the sawtooth phenomenon by smoothing the image edges to achieve effective corner point extraction. Subsequently, the building boundary is extracted again and boundary simplification and regularization are performed. This method can improve the degree of automation of the entire process while ensuring accuracy.

METHODOLOGY
In this study, we propose a fast corner-point detection method based on dimensionality reduction. First, a method based on airborne LiDAR data was used to extract the building points, and the alpha shape algorithm was used to extract the initial boundary. Second, the extracted contour was converted into a 2-D image. Finally, the image-based method was used to extract the boundary of the building again and perform boundary simplification and regularization. This process is illustrated in Figure 1.

Building Extraction
Filtering is a technique of dividing a LiDAR point cloud into ground and non-ground points. The non-ground points are subsequently separated from the building points. This study utilizes a filtering method based on the cloth simulation filter (CSF ) proposed by Zhang et al. (2016). The principle of the algorithm is that a piece of virtual cloth sinks on the reversed surface of the terrain due to gravity (Liu et al., 2020). The change in the terrain can be observed directly and clearly by controlling rigidity, which represents the stiffness of the cloth in the previous analogy. Buildings, automobiles, vegetation, and other non-ground points were among the points generated using filtering. To distinguish the buildings from the non-ground points, we used a clustering segmentation method proposed by Hong et al. (2014) using the convergence area and slope of the point cloud as thresholds after classifying the point cloud based on elevation. Specifically, the surface equation of the local region (the eight neighborhoods of the point cloud) is fitted using the least squares method (equation1). In space, the slope of the tangent plane of the fitted surface at a point can be calculated using the gradient formula (Equation 2 ).
where xi, yi are the coordinates of LiDAR points The general steps of the algorithm are as follows: (1) select the bottom-left point in the point cloud as the seed point and create two 3 × 3 arrays C and N in the argument space; (2) fit the surface equation corresponding to the area of array C using equation 1; (3) calculate the gradient values of the seed point and its 8 neighboring points in the fitted surface and compare them with the slope threshold: if a gradient value is greater than or equal to the slope threshold, the corresponding position in C of the point is assigned a value of 0; otherwise, the assigned value is 1; (4) calculate the sum of all values in array C, which represents the area statistics of the local area where the seed point is located. If the sum of C is larger than N, the seed point is considered a building point. (5) The remaining points are searched from left to right and bottom to top, and the steps (1) through (4) are repeated until all points are determined. This method can effectively overcome the problem of missing details in the local areas of buildings resulting from noise and observation errors (Huo et al., 2019). After identifying the building points, each building roof is extracted using the region growing segmentation algorithm, which is based on the angle difference between the surface normal vectors to classify the point set associated with the same plane.

Initial Boundary Extraction and Image Conversion
The alpha shape algorithm was used to perform the initial 2D boundary extraction from the projected roof points. Figure 2 depicts the alpha shape algorithm workflow (Shen et al., 2008), where the S1 point cluster randomly selects a point from S1 and selects a point P2 from the S2 point cluster, which is composed of points whose distance to P1 is less than twice the alpha value, as shown in Figure 2(a). A circle with radius alpha passes through any two points P1 and P2. If there are no points in this circle, the two points are regarded as boundary points and the line between P1 and P2 as the boundary line. The specific judgment process is as follows: we can use the distance intersection algorithm (Pradhan et al., 2019) hybrid to obtain the center of the circle when the coordinates of P1(x1,y1) and P2(x2,y2) are known: where After acquiring the center of the circle, we determine if there are other points falling into this circle by comparing the distance between the points in S2 and the center of the circle with radius alpha. If the distance is less than alpha, the point is within the circle, and the line between P1 and P2 is not a boundary line. Finally, another point from S1 is selected, and the procedure is repeated until all points in S1 are classified, as shown in Figure  2(b).

Figure 2. Alpha Shapes algorithm principle
In Figure 3(a), the initial boundary exhibits the sawtooth phenomenon owing to uneven point density. To mitigate this and improve operational efficiency, this study used image-based boundary smoothing instead of the popular point-cloud-based sleeve algorithm. This process consists of two steps. First, the initial contour point cloud is rasterized at a certain resolution (0.1 m/pixel in this study) to a 2D image using the initial contour, as shown in Figure 3(b). Second, this image is smoothed by recursive Gaussian filtering (Van Vliet et al., 1998), which divides the two-dimensional convolution into independent convolutions in the X and Y directions for the smoothing operation. Subsequently, the image is converted to a binary image, as shown in Figure 3(c). Comparing Figure 3 (a) and (c), it can be seen that the sawtooth phenomenon is effectively suppressed, which provides a good basis for efficient and accurate boundary extraction from the binary image.

Boundary Extraction and Regularization
After boundary smoothing in the binarized image by Gaussian convolution, the sawtooth phenomenon of the original point cloud is effectively alleviated the resulting image can be easily filtered to obtain the key corner points. The boundary-tracking algorithm (Suzuki et al., 1985) was applied for fast contour detection on the binary image. The border point judgment principle underlying this function is as follows: in the 4-(8-) connected case, a 1-pixel containing a 0-pixel in its 8-(4) neighborhood is designated as a border point. The boundary represented by the topological structure derived from the algorithm can be applied to the image storage. This is because the topology allows simpler image processing without the need to restore the original image. The image processing include feature extraction for the boundary, such as the perimeter and area of the connected domain, which is useful for calculating the area of the extracted buildings. Subsequently, polygon construction is implemented using the D-P algorithm (Douglas and Peucker, 1973), as shown in Figure 4. First, we set a distance threshold ε and formed the baseline by connecting the first and last boundary grid vertices. Next, the distance of the remaining points to the line was calculated; if the largest distance was greater than ε, the point with the greatest distance was retained; otherwise, all the points between the two endpoints of the baseline were discarded. Finally, the calculation and judgment procedure are repeated until the distance between the points and the line is less than or equal to ε. Starting from the polygons, the direction of the longest edge was set as the main direction, and the other lines were sorted in the clockwise direction. The cosine of the angle between the remaining lines and the main direction was calculated to perform regularization. If the absolute value of the angle was greater than or equal to a, the line was considered parallel to the main direction and the slope of the main direction was assigned. Similarly, if the absolute value was between 0 and b, the line was considered perpendicular to the main direction; a cosine value between a and b indicates a straight line, which does not need to be regularized. In the final step, all adjusted lines were connected to generate the outline polygon ( Figure 5).

Data Sets
Two test areas were selected from airborne LiDAR point cloud datasets: the ISP RS V aihingen dataset (area V) and the ISP RS T oronto dataset (area T) (Rottensteiner et al., 2012). Most of the buildings in area V are rural buildings with a sparse distribution density and relatively homogeneous shapes. It has an average point density of 4 point/m 2 . By contrast, the buildings in Toronto are denser and more variable, with an average point density of 6 points/m 2 . Applying the proposed boundary extraction method to two completely different scenarios, the  Figure 6, the original point clouds of area V and area T are colored by classification labels. The grey points are the ground extracted by CSF , with the classification thresholds of 0.5m for the both areas . The green points denote trees while the red points indicate buildings, which are classified using the slope threshold (2.0 in area V; 1.5 in area T) and the area threshold ( 50m 2 in area V; 30m 2 in area T ).

Evaluation Metrics
To quantitatively analyze the performance of the direction prediction algorithm, we selected three evaluation metrics proposed in Guo et al. (2020): 3.2.1 M AD: This reflects the maximum deviation degree of the extracted corner points by the method. The smaller the MAD value, the better the method.
where xi, yi are the coordinates of the extracted point, and xj, yj are the coordinates of the point in the ground truth 3.2.2 RM SE: It reflects the true error of corner point extraction. The closer the RM SE value is to zero, the better the extraction result.
where xi, yi are the coordinates of the extracted point, xj, yj are the coordinates of the point in the ground truth, and N is the total number of extracted points 3.2.3 REA: It reflects the overall extraction effect of the method on the building boundaries. The smaller the value of REA, the closer the extracted building footprint is to the actual value.
where Sc is the area of the extracted building, and Sr is the reference area of the extracted building

Results
After extracting the buildings from the datasets, the regiongrowing algorithm to was used to perform monolithic extraction of the roof of each building, as depicted in Figure 7. The reason for the missing buildings compared to Figure 6 is that the proposed method cannot be applied to buildings with nonpolygonal shapes such as circular arcs; therefore irregular buildings are manually removed before roof extraction. In addition, the extracted building in area T loses some points on the roof due to the shading effect resulting from vegetation and noise. However, this effect only occurs inside the roof and has negligible influence on the corner of the roof; therefore, it can preserve the basic shape of the building. Figure 8 shows the boundary extraction results using the proposed method introduced in section 2.2 and 2.3. As is evident, building border point extraction is relatively complete and conforms to the outline of the building. The average results of each evaluation metric are presented in Table 1 to provide a quantitative comparison. The value of RM SE in area T (0.0537) is higher than that in area V (0.0418); because more complex buildings and vegetation are present in area T, the loss of a few point clouds will significantly affect the extraction accuracy owing to increased occlusion. However, the values of RM SE in both the areas are lower than 0.5, which indicates that the proposed method extracts corner points with high precision. In addition, the value of REA in area V and area T are 0.0418 and 0.0537, respectively, which indicates that the building outlines composed of the boundary extracted by the proposed method are consistent with the real shapes. In conclusion, the proposed method exhibited good boundary extraction performance for regular buildings in areas V and T.

Comparison and Analysis
To demonstrate the advantage of the proposed method with respect to building boundary extraction over the sleeve algorithm, we conducted a comparison based on two aspects: (1) algorithmic time complexity, and (2) boundary extraction precision.
(1) Algorithmic time complexity: The most significant difference between the proposed method and the method based on the sleeve algorithm is that this method uses image recursive Gaussian filtering instead of the sleeve algorithm to mitigate the sawtooth phenomenon resulting from the point cloud. Therefore, we only compared the time complexity of recursive Gaussian filtering with that of the sleeve algorithm. Recursive Gaussian filtering has a time complexity of O(n), whereas, the sleeve algorithm, which uses angle and distance thresholds to perform nested judgments for filtering the initial boundary, has a time complexity of O(n 2 ). This implies that the convergence time of the sleeve algorithm increases by an order of n 2 compared to that of the proposed method when the size of the data increases by n times. This shows that the proposed method can significantly improve the efficiency by mitigating the sawtooth phenomenon close to boundaries. In addition, as opposed to the sleeve algorithm, which requires two thresholds, Gaussian filtering only requires one threshold (standard deviation) in practice. This results in a decrease in the number of iterations required to find a suitable threshold and the associated costs compared to the sleeve algorithm.
(2) Boundary extraction precision. We select the four specific building instances in area V (shown in Figure 9) as examples to perform a comparison in terms of precision with the CAA method proposed in Guo et al. (2020), which is based on an improved version of sleeve algorithm. This comparison reflects the effectiveness of the proposed method in mitigating the sawtooth phenomenon and improving the accuracy of building boundary extraction. The results of this comparison are presented in Table 2.  As is evident from the results in Table 2, the values of the three evaluation metrics are lower for the proposed method compared to those of the CAA method proposed in Guo et al. (2020), indicating that the proposed method exhibits better performance in building boundary extraction. The higher precision is because of the supplementary effect of Gaussian filtering on parts of the building corner. Specifically, owing to uneven point density and occlusion, the point cloud at the corner may be missing. Gaussian filtering introduces a dilation effect on the image boundaries, which complements missing corner points to a certain extent. Therefore, the proposed method can recover corner points closer to the true value to obtain a more precise shape.
In addition, among the four buildings listed in Table 2, the enhancement effect of the proposed approach for building I was the most significant. The value of M AD decreased from 1.428 to 0.487, RM SE was reduced by approximately three times, and REA decreased from 0.165 to 0.011. Notably, the shape of building I was the most complex among the four buildings, with the largest number of corner points. The accuracy of each extracted corner point may be improved; thus, it reaches the maximum cumulative improvement in precision. In other words, the proposed method can effectively improve the precision of the building boundary extraction.

CONCLUSION
In order to achieve fast and accurate extraction of building boundary, this paper proposed a method based on feature dimension reduction of the LiDAR point clouds. First, the alpha shape algorithm is employed to conduct the initial boundary extraction from the point clouds of building roofs extracted by the region growing algorithm. Next, the initial boundary points are converted into the two-dimensional image. The contour lines are then extracted again on the image using boundary tracking algorithm after Gaussian smoothing. Finally, the DouglasP eucker algorithm is used to extract the contour key points and obtain the regular building outlines by using the grouped orthogonal regularization method. The extraction results (RM SE) of the proposed method upon two experimental airborne data are promising: 0.361 m in area V and 0.497 m in area T. To verify the accuracy of the pipeline, the algorithm is compared against the CAA method proposed in Guo et al. (2020), which is based on an improved version of sleeve algorithm for four representative building objects in area V. By contrast, the values of RM SE is reduced by 43.79% on average. In addition, the time complexity of the proposed method (O(n)) is lower than CAA method proposed in Guo et al. (2020) (O(n 2 )). Based on the above analysis, it is proved that the proposed method not only improves the accuracy of boundary extraction but also increases the efficiency of data processing.