A Method for Regularizing Buildings through Combining Skeleton Lines and Minkowski Addition

Abstract

With the increasing availability of remote sensing images, the regularization of jagged building outlines extracted from high-resolution remote sensing images has become a current research hotspot. Based on an existing method proposed earlier by this author for extracting the skeleton lines of buildings through integrating vector and raster data using jagged building skeleton lines as the input data, a new method is proposed here for regularizing building outlines through combining the skeleton lines with the Minkowski addition algorithm. Since the size and orientation of the structuring elements remain constant in the traditional morphological method, they can easily lead to large changes in the area between the regularized results and area of the original building. In this work, structuring elements are constructed with the adaptive adjustment of size and orientation. The proposed method has an outstanding ability to maintain the area of the original building. The orthogonal characteristics of the building can be better preserved via rotating the structuring elements. Finally, the angular bisector method is used to dissipate conflicts among the redundant vertices in the building outlines. In comparison to the simplification method used in QGIS software, the method proposed in this paper could reduce the variation in the area while maintaining the orthogonal characteristics of the building more significantly.

1. Introduction

Buildings are the most common geographic features in urban mapping. Their accurate and rapid extraction and real-time updating have important roles in urban planning, land use, cartographic generalization and data updating [1]. It is also a research hotspot in the analysis of remote sensing images. Traditional manual extraction methods are time-consuming and make it difficult to meet the demand for updating real-time data. With the continuous development of remote sensing technology, airborne LiDAR technology and deep learning algorithms, the automatic extraction and classification of geographic features have become hot research problems in recent years, and certain promising results have also been achieved [2,3,4,5,6]. High-resolution remote sensing imagery can acquire massive spectral and geometric structural features of geographic features in a short period of time [7], which makes it possible to provide real-time and accurate source data. There is always a significant loss of relevant building cues due to occlusion, poor contrast, shadows and disadvantageous image perspective [8]. Under the influences of these factors, the extraction of building outlines often becomes jagged and noisy, making it difficult to apply directly to cartographic generalization. Nitin [9] proposed a morphologically based automatic approach for the extraction of buildings using high-resolution satellite images. However, the extracted buildings are not regularized and are difficult to use directly for cartographic generalization. Current building extraction methods focus on extraction with little further regularization for irregular buildings. Regularization is an operation for obtaining important information in detail about geographic features while reducing their complexities. Rottensteiner [10] found that the determination of the building outline was a crucial and difficult step in the task of building reconstruction. Therefore, the current research focuses on the regularization of building outlines rather than on their extraction [11]. The present work focuses on the regularization of jagged buildings extracted from high-resolution remote sensing imagery.

The existing building regularization methods are divided into two categories: geometric calculation-based methods and machine learning-based methods. For methods based on geometric calculations, three main types are included, from the perspective of template matching, optimization techniques, and image processing, respectively. Rainsford [12] and Yan [13] proposed a template-matching simplification method from the perspective of shape cognition based on the typical template characteristics of building distributions. It searches and matches the most similar template to replace the original building. This method requires extensive dynamic adjustment of the shape, size and orientation of the template as well as the replacement of the original building with the most similar template, which was inefficient. Secondly, optimization techniques are also widely used in building simplification. Sester [14] proposed a method for building simplification that uses least-squares adjustment theory. In the algorithm, the main structure is maintained, while the short edges are removed. Bayer [15] presented a recursive approach for building simplification. The method was able to simplify buildings with a random direction without depending on the order of points. Buchin [16] proposed a local operation for polygons and subdivisions, called an edge-move, which was efficient for area- and topology-preserving subdivision simplification. Tong [17] proposed an area-preservation approach for the simplification of polygonal boundaries through using the structured total least squares with constraints, where the area of a building can be effectively maintained after simplification. Additionally, an increasing number of researchers attempted to simplify buildings from the perspective of image processing. Shen [18] used unstructured raster data for the simplification of polygonal and line elements, where the used method is divided into two parts, namely global-based super-pixel segmentation and local simplification based on Fourier descriptors, which can better preserve the topological relationship of the original polygon. Kada [19] developed a simplification approach based on cell decomposition and half-space modeling. In order to generate a good result, the buildings were rotated along the main axis using dilation and erosion.

In recent years, machine learning algorithms have made groundbreaking research advances in the field of digital image processing. However, in the field of cartographic generalization, spatial vector data is the more common type of data that cannot be represented as an array but can be modeled only as a graph with nodes and edges for storing objects. To this end, some researchers have proposed neural networks for graphs, with the aim of extending deep learning technologies to analyze graph-structured data [20]. Yan [21] introduced a graph convolutional neural network approach to identify the distribution patterns of buildings. Machine learning methods depend on the training of labeled examples rather than on manual rule definitions for patterns. Yan [22] proposed a graph convolutional autoencoder model to identify the shape of buildings, which can significantly improve the efficiency of template matching. Shen [23] proposed a super-pixel segmentation method for building simplification based on raster data. However, it can only solve the one-to-one building simplification problem, and the merge operator is not taken into account when the scale of the map spans a large area. Yang [24] considered four existing simplification methods as the objects of a study and then constructed an evaluation model using a back-propagation neural network to identify the most appropriate simplification method. Pepe [25,26] first selected an appropriate pan-sharpening technique to enhance the contrast between the building and the surrounding background and then extracted the building using the Mask R-CNN model, the ArcGis Pro tool “Regularize Building Footprint” was used to regularize their shape. The results of the raster-based approach do not address the problem of building jaggedness, especially when redundant points were introduced after raster-to-vector conversion. Tripodi [27] adopted a U-Net convolutional neural network architecture to extract the contours of buildings and then searched for a compressed polygon with the best quality/complexity ratio, in other words, with the minimum number of vertices within a specified tolerance of error. Converting from raster to vector format may introduce redundant points.

In the process of acquiring geospatial data, high-resolution satellite imagery is used as the primary method for data acquisition. With the increasing maturity of processing airborne LiDAR point cloud data, LiDAR-based applications are being widely used in digital city construction, disaster management and environmental detection. Awrangjeb [11] proposed a contour-based method for identifying and regularizing building contours using LiDAR point cloud data, where the experimental results showed that the proposed method could preserve the features of building edges in detail. Widyaningrum [28] used ALS (airborne laser scanner) point cloud data to define line segments and corner points and subsequently proposed a method to extract accurate building contours using an extended Hough transform. The experimental results showed that the method was insensitive to the interference of noise. Xie [29] proposed a hierarchical regularization method for processing ALS point cloud data of building edges with a lot of noise interference, where the experimental results showed that the method could reconstruct the building regularized from noisy point clouds. Gilani [6] proposed a method for building detection and regularization using multisource data, including ALS point cloud data, ortho-images, and digital terrain models (DTM). The regularized building outlines may deviate from the correct building orientations as the obtained results depend on the selection of the longest lines. Yu [30] presented the first edge-aware deep learning network for 3D reconstruction from point cloud data, namely EC-Net. This method has limitations in case of large holes or incomplete data.

To summarize the above methods, few simplification methods can take into account both the orthogonal features of buildings and the consistency of the area. Therefore, we propose a new building regularization method that takes into account area consistency while maintaining the orthogonal characteristics of buildings. An important characteristic that distinguishes buildings from other natural geographic features is orthogonality, which should be maintained in the simplification process [31], while maintaining their area consistency. With the rapid development of machine learning algorithms in remote sensing image processing, machine learning methods are gradually replacing traditional manual extraction methods. The larger the amount of data, the higher the extraction accuracy of the machine learning algorithms. However, due to some factors, such as low contrast, shadow occlusion and sensors, building outlines are often blurred from other geographical elements around them. As a consequence, the extraction of sharp edges becomes difficult for machine learning methods, and the obtained results typically do not meet the requirements of cartographic generalization [28]. A skeleton line extraction algorithm that operates through integrating vector and raster data was proposed earlier by this author [32]. The extracted skeleton lines of the building were insensitive to the noise of the building contour. The results can maintain the centrality principle of the skeleton lines as well as the orthogonal characteristics of the building, which encourages this research. In this paper, the extracted skeleton lines of the building are combined with the Minkowski addition algorithm to develop a regularization algorithm for building contours, where jagged building outlines are regularized with orthogonal and non-orthogonal features, while maintaining the orthogonal characteristics and area consistency of the simplified building outline. In addition, the output data are the regular vector data format of building polygons, which is more in line with the requirements of cartographic generalization.

2. Principle of the Proposed Algorithm

2.1. Minkowski Addition Algorithm

Minkowski addition is a method for morphological operation, which is a common analytical method in computational geometry. Similar to the dilation operation in mathematical morphology, Minkowski addition also requires two regions. One of these two regions is the region we want to process, which is denoted with R. The other region is called the structuring element, denoted with S. The structuring element is the means for describing the shapes of interest [33,34]. The Minkowski addition can be expressed as follows:

$$\begin{array}{c}R⨁S=\left\{r+s|r\in R,s\in S\right\}\end{array}$$

(1)

As per the above formula, the Minkowski addition of R and S is obtained as the vector sum of every point in R with that in S. The Minkowski addition is the set of all those points. Compared with the dilation operation in mathematical morphology, the method of Minkowski addition can be used for processing both raster and vector data. However, the dilation operation is defined for gray-valued images, and it cannot be used for processing vector data. The Minkowski addition method can be more clearly described using raster data as the object of study, as shown in Figure 1.

Note that the results of Minkowski addition and dilation are different. In the dilation operation, the structuring elements need to be transposed. In other words, as long as the structuring elements are not symmetric with respect to the region, their results are different. Only if the structuring elements are symmetric with respect to the origin are their results then identical.

In summary, the flexibility of the morphological approach depends on the setting of the properties of the structuring elements. For the morphological approach, the attributes of the structuring elements include size, shape, origin and orientation. Therefore, this paper analyzes the shape, size, origin and orientation of the structuring elements for regularizing buildings through dynamically adjusting the size and orientation of the structuring elements.

2.2. Main Processing Flow of the Proposed Method

Based on the above analysis, this paper proposes a building regularization method that operates through combining skeleton lines and Minkowski addition. In this study, the extracted primary vector buildings from high-resolution remote sensing images are used as input data, the skeleton line of the building is extracted as the region to be processed R, and the rotatable structuring element S is then constructed according to the size of the building and the orientation of the skeleton line. The main processing flow of the proposed method is shown in Figure 2.

In this paper, the processing of building regularization is mainly divided into five parts, namely input data, data pre-processing, the processing of structuring elements, conflict resolution, and data output. The detailed steps are presented below:

• Input data: Building contours, extracted from a high-resolution remote sensing image, have been converted to vector format. The building outlines often become jagged and noisy, making it difficult to apply them directly to cartographic generalization.
• Pre-processing: In order to simplify the characteristics of buildings, a method was proposed by Chen [32] for extracting building skeleton lines through integrating vector and raster data, where the experimental results showed that the method has obvious advantages over traditional methods in terms of the centrality maintenance and right-angle feature maintenance of building skeleton lines, and it is suitable for processing buildings with non-orthogonal features.
• Structuring elements: The method developed based on Minkowski addition requires two regions, one of which is the region R to be processed. In this paper, the skeleton line in the pre-processing part of the data is taken as the region to be processed. The other region S in this method is the one containing the structuring element, which is defined in terms of size, origin, and orientation. In this study, the orientation of the structuring elements is adaptively adjusted through rotating them in a clockwise orientation until the skeleton lines are oriented in the same direction, whereas the traditional morphological method keeps the size, orientation and origin of the structuring elements constant during its operation.
• Conflict resolution: Due to the more blurred boundaries between buildings and surrounding natural geographical features, as well as the influence of a lot of noise on the edges of buildings, the buildings initially extracted from remote sensing imagery are usually not perfectly orthogonal at the corner locations, leading to a situation where the results of the regularization of buildings are prone to conflict at corner points. To address the above issues, this paper proposes a new approach of conflict resolution by means of using the angle bisector method to correct the results of the Minkowski addition.
• Output data: The output data are a regularized vector building, which better meets the requirements of cartographic generalization.

2.3. Properties of Structuring Elements

2.3.1. Shape and Origin of Structuring Elements

In the operation of mathematical morphology, structuring elements can be set to any shape and size as required. The position of the origin also has an effect on the results of the morphological operation. Given the obvious orthogonal characteristics of buildings, many scholars used rectangular graphical elements in the simplification of buildings [36]. Yan [13] constructed dynamic templates represented using common letters of the alphabet (I-shaped, C-shaped, T-shaped, F-shaped, L-shaped and so on) for building simplification, all of which can be obtained through combining multiple rectangles in a certain way.

In order to maintain the orthogonal characteristics of buildings, square-shaped structuring elements are chosen, with the center of a square as the origin of the representing element. As shown in Figure 3, the black point is the starting point of the skeleton line of the building, while the origin of the structuring element is located on the skeleton line throughout the morphology operation. The solid red line is the skeleton line extracted using the vector–raster data fusion method [32], and the green dashed box indicates the origin and shape of the structural element.

2.3.2. Adaptive Resizing of Structuring Elements

Generally, the size of the structuring elements cannot be adjusted in traditional mathematical morphology. However, in the process of regularizing buildings, there is a need to ensure the consistency of the area of the building before and after the regularization. So, the adaptive adjustment of the size of the structuring elements is required to achieve consistency in the area. The steps for the adaptive resizing of the structuring elements are as follows:

• The size of a structuring element can be calculated from the length of the skeleton line and the area of the original building. In this paper, the original size of a structuring element is denoted with d, the area of the building before its regularization is denoted with $S_{area}$, and the length of the skeleton line is denoted with L.
• It is checked, using the extracted skeleton lines, whether a building contains cross points. If the building contains any cross point, it has at least one more branch. Therefore, buildings are divided into those without cross points and those with cross points depending upon whether the skeleton lines contain intersections or not.
• Buildings without cross points have only two endpoints, as shown by the black points in Figure 4a. A building has more branches due to the presence of cross points. So, it has more than two endpoints. The yellow point in Figure 4b is the cross point of the skeleton lines.
• Assume that the number of endpoints is N. Then, the following condition is satisfied:

  $$\begin{array}{c}{S}_{area}=L\times d+d\times \frac{d}{2}\times N\end{array}$$

  (2)

The size of the structuring element d is calculated dynamically using the above Equation. Each building adjusts its corresponding structuring element dynamically according to its structuring element size d.

2.3.3. Adaptive Adjustment of Orientation of Structuring Elements

In traditional mathematical morphology, the orientation of the structuring elements remains constant during operations, and most operations, such as dilation or erosion, are performed directly on the buildings. In practical applications, this may change the topology of the original buildings, leading to errors or the generation of new noise. The method used in this paper extracts and simplifies the skeleton lines of the buildings to reduce the redundant points in the image segmentation process. At the same time, the immutability of the orientation of the structuring elements in the existing morphological method is improved through rotating them in line with the orientation of skeleton line so as to obtain more regular building outlines.

In this paper, the angle of rotation of a structuring element is defined as follows. The center of rotation is the origin of the structuring element. Here, the angle of rotation is taken as zero degrees when the orientation of the structuring element is the same as that of the Y-axis. The structuring element is rotated in a clockwise orientation until it is in the same orientation with the skeleton line. Then, the resulting angle becomes the angle of rotation of the structuring element. The angle of rotation is shown in Figure 5, where the solid black square is the state before the rotation, and the dashed red square is that after clockwise rotation in the amount of angle a.

Because of the complex shape of a building, its skeleton line consists of several line segments. For each building, all the structuring elements at each node of the skeleton line need to be rotated clockwise from zero degrees to the same orientation as the skeleton line. Consider a commonly distributed L-shaped building, as shown in Figure 6 as an example, where the skeleton line of the building consists of two lines, $P1\to P2$ and $P2\to P3$. In the programming of this study, the order of storing the data of the nodes in the skeleton line is $P1\to P2\to P3$, where point $P1$ is the starting point of the skeleton line and point $P3$ is its ending point.

• First rotation: First, when the center of a structuring element is located at the starting point of the skeleton line, it is necessary to rotate the element clockwise by an angle of a1, as shown in Figure 6a, so that the orientation of the element coincides with the orientation of the line segment $P1\to P2$.
• Second rotation: Since the two lines $P1\to P2$ and $P2\to P3$ are not in the same orientation, when the center of a structuring element is located at point $P2$, it becomes necessary to rotate the element to coincide with the orientation of line segment $P2\to P3$ as shown in Figure 6b.

Compared to traditional morphological methods, the approach in this paper is more flexible in defining the size and orientation of structuring elements. In particular, the orientation of a structuring element is defined in advance using a traditional morphological method. Whereas the structuring element is rotatable in this paper, the results are more in line with human visual cognition. The building regularization results obtained through applying the above method are shown in Figure 7a. However, the buildings initially extracted from remote sensing imagery are usually not perfectly orthogonal at the corner locations due to interference by noise; there are still many redundant vertices that need further processing. As depicted in Figure 6 for the line segments $P1\to P2$ and $P2\to P3$, the orientation of the skeleton line at point $P2$ can be expressed as either $\overrightarrow{P1P2}$ or $\overrightarrow{P2P3}$. In most cases, the two line segments are not perpendicular due to the effect of noise. As a result, there is a possibility a conflict may occur at point $P2$, as shown in Figure 7b, which affects the quality of the regularization process. In order to address these issues, this paper proposes a conflict resolution method based on angle bisectors to eliminate redundant vertices, as discussed below.

2.4. Method of Conflict Resolution for Building Vertices Based on Angle Bisectors

In order to further eliminate the redundant vertices of a building, this paper proposes a new method, namely the method of conflict resolution based on angle bisectors. If two adjacent line segments of the skeleton line are at right angle, there will not be any redundant vertex in the corresponding building; otherwise, redundant vertices will be generated in the building after the adjustment of the orientation of its structuring elements, as shown in Figure 7b. The steps of the proposed conflict resolution method are as follows:

• As shown in the building in Figure 8a, the skeleton lines are first numbered in the order in which points $P1\left(x_1,y_1\right)$, $P2\left(x_2,y_2\right)$ and $P3\left(x_3,y_3\right)$ are stored, and then $\overrightarrow{P2P1}\left(x_1-x_2,y_1-y_2\right)$ and $\overrightarrow{P2P3}\left(x_3-x_2,y_3-y_2\right)$ are calculated as the orientation vectors. The two vectors are then unitized. Assume that the unitized orientation vectors of vectors $\overrightarrow{P2P1}$ and $\overrightarrow{P2P3}$ are $v_1(x_{v1},y_{v1})$ and $v_2(x_{v2},y_{v2})$, respectively, and the angle bisector of $\overrightarrow{P2P1}$ and $\overrightarrow{P2P3}$ is $v_3(x_{v3},y_{v3})$. The unitized vectors are calculated as follows:

  $$\begin{array}{c}{x}_{v1}=\frac{\sqrt{{\left(x_1-x_2\right)}^2}}{\sqrt{{\left(x_1-x_2\right)}^2+{\left(y_1-y_2\right)}^2}},y_{v1}=\frac{\sqrt{{\left(y_1-y_2\right)}^2}}{\sqrt{{\left(x_1-x_2\right)}^2+{\left(y_1-y_2\right)}^2}}\end{array}$$

  (3)

  $$\begin{array}{c}{x}_{v2}=\frac{\sqrt{{\left(x_3-x_2\right)}^2}}{\sqrt{{\left(x_3-x_2\right)}^2+{\left(y_3-y_2\right)}^2}},y_{v2}=\frac{\sqrt{{\left(y_3-y_2\right)}^2}}{\sqrt{{\left(x_3-x_2\right)}^2+{\left(y_3-y_2\right)}^2}}\end{array}$$

  (4)
  The unitized vector $v_3$ is normalized as follows:

  $$\begin{array}{c}{x}_{v3}=\frac{\left(x_{v1}+x_{v2}\right)}{2},y_{v3}=\frac{\left(y_{v1}+y_{v2}\right)}{2}\end{array}$$

  (5)
• According to the results of step 1, the unitized vector $v_3$ is the orientation of the interior angle bisector of $\overrightarrow{P2P1}$ and $\overrightarrow{P2P3}$. The interior intersection M of the orientation of the unitized vector $v_3$ with the computed regularization result, as shown in Figure 8b.
• Assume that the opposite orientation vector of the angle bisector vector $v_3$ is $v_4(x_{v4},y_{v4})$. Then, the unitized orientation vector of the vector $v_4$ can be expressed as in Equation (6). The intersection of $v_4$ with the regularised result is N, as shown in Figure 8c.

  $$\begin{array}{c}{x}_{v4}=-\frac{\left(x_{v1}+x_{v2}\right)}{2},y_{v4}=-\frac{\left(y_{v1}+y_{v2}\right)}{2}\end{array}$$

  (6)
• In order to show the experimental results more intuitively, these are represented by the nodes of a polygon before and after the conflict resolution. The black points in Figure 9 are the nodes of the building after regularization, and the green dashed boxes are the results of the regularized building. As an example, in the L-shaped building, the number of nodes after regularization and before conflict resolution is 14, and the noise reduction in the building edge is incomplete. The number of building vertices is 6 after using the angle bisector-based conflict resolution method, which better solves the problem of incomplete noise reduction in edges.

3. Experiments and Analysis

3.1. Study Area

In order to validate the proposed building regularization method, we chose primary vector buildings (Figure 10b) extracted from high-resolution remote sensing images (Figure 10a) as the object of this study. The selected study area is located in Indianapolis, USA, and it ranges from ($39.7444°\mathrm{N}$, $86.2001°/\mathrm{W}$) to ($39.7924°\mathrm{N}$, $86.1355°/\mathrm{W}$) expressed in latitude and longitude with a spatial resolution of 0.67 m, containing a total of 10,348 pieces of building data.

3.2. Experimentation

QGIS is a free and open-source version of a desktop geographic information system that includes extensive spatial analysis functions. Therefore, QGIS is used as a development tool in this study. For the simplification of polygon features, QGIS provides the corresponding interface “simplify (double tolerance)” in the QgsGeometry class, which will return a simplified polygon feature using a specified tolerance value. Thus, it was chosen to be used as a comparison of the method in this study. For better presentation of the results of the regularization process, a part of the typical distribution of buildings was selected for analysis, as shown in Figure 11. Through constructing a mapping relationship between vector and raster data, the results were presented in high-resolution remote sensing images. Figure 11c,f,i show the most typical types of distributed buildings in the study area, such as I-shaped, L-shaped, C-shaped, T-shaped, F-shaped. According to the obtained experimental results, as shown in Figure 11b,e,h, the polygon feature simplification method of QGIS software can process regular buildings more efficiently. However, the results involve more nodes, simplification is incomplete and right-angled features are not obviously retained. Secondly, the results of the simplification are influenced by its threshold (Figure 11b,e,h use a simplification threshold of 3 m). The method proposed in this paper can better suppress the edge noise of a building, especially in concave areas of the building, due to the noise interference during primary extraction, such as with the L-shaped building as shown in Figure 11e. The proposed method better maintains the orthogonal features than the method provided in QGIS software.

4. Discussions

For buildings in the study area, as shown in Figure 10, automatic building detection has a low success rate due to scene complexity, incomplete cue extraction, and sensor dependencies [8], which makes regularization more difficult. Therefore, there are some details that need to be discussed in order to improve the overall quality of regularization.

1: As the result depicts in Figure 11f, the outcome of building regularization in the top-left corner is less than satisfactory. The results of the method in this paper are strongly influenced by the quality of the skeleton line extraction. Our previous research proposed a skeleton line extraction method suitable for buildings [32], as shown in Figure 12.

Figure 12a shows the skeleton line extraction results, which still contain a large number of redundant points. Therefore, simplification is necessary, and detailed methods of simplification are in the literature [32]. In order to simplify the building as much as possible and keep the overall quality of the regularization, some features may be lost, as shown in Figure 12b,c. In the method proposed in this paper, it tends to occur in buildings where the skeleton line is smoother or where the corner features are not obvious.

2: The interior of a building is prone to holes due to the complexity of the scene, incomplete cue extraction and poor contrast, as shown by the black circle in Figure 13a. However, the holes tend to lead to deviations in skeleton line extraction, resulting in unsatisfactory regularization results. Therefore, in order to improve the quality of regularization, the holes need to be filled in, as shown in Figure 13b. The hole filling method adopts the interface “removeInteriorRings()” from the QgsGeometry class in QGIS.

Rainsford [12] and Yan [13] attempted to use a series of simple alphabetic templates to match buildings, e.g., I-shaped, F-shaped, V-shaped, etc. These simple alphabetic templates remove tiny details of a single building and maintain key features of the building, which are suitable for describing the shape of buildings. There, seven types (C-shaped, F-shaped, H-shaped, I-shaped, L-shaped, T-shaped, V-shaped) of the most widely distributed buildings from the study area were randomly selected for analysis, and five typically distributed buildings of each type were randomly selected, as shown in Figure 14.

The number of vertices, $SurfaceDistance$ [37], change in area and the average value of deviation from a right angle at the vertices after the regularization of a building are analyzed from four aspects. In addition, the average running time for regularizing each type of building is used to measure the efficiency of the two approaches. The program was built in “Release” mode on the Visual Studio 2017 platform. The number of vertices after the regularization of a building reflects whether the simplification is complete or not.

$SurfaceDistance$ is a common quantitative analysis method used to measure the similarity of two polygon features. Given two polygon features M and N, the $SurfaceDistance$ can be calculated via two operations, the intersection and union of M and N, as expressed in Equation (7).

$$\begin{array}{c}SurfaceDistance=1-\frac{Area\left(M\cap N\right)}{Area\left(M\cup N\right)}\end{array}$$

(7)

In this Equation, $Area\left(M\cap N\right)$ is the area of the intersection of buildings M and N, and $Area\left(M\cup N\right)$ is the area of the union of buildings M and N. From this Equation, it can be found that the smaller the value of $SurfaceDistance$, the more similar the result of the regularization to that of the original building. The change in area of the two buildings can be calculated using Equation (8).

$$\begin{array}{c}ChangeInArea=1-\frac{\left|S_2-S_1\right|}{S_1}\end{array}$$

(8)

In this Equation, $S_2$ is the area after the simplification of the building, and $S_1$ is the area of the original building. According to this Equation, the larger the value of $ChangeInArea$, the closer the area of the two polygon features.

The average value of deviation from a right angle at the vertex of a building after regularization can be used to measure the orthogonal characteristic of the regularized building, which is a key feature that would distinguish a building from other natural polygonal features. For buildings after regularization, this value was used to measure the orthogonality of the result of the building being simplified. Taking a common L-shaped building as an example, the method for calculating the average vertex angle of the building is shown in Figure 15. The smaller the value, the better the orthogonality of the simplified result is maintained.

$$\begin{array}{c}AngleSum=\left|90-a_1\right|+\left|90-a_2\right|+\cdots ⌈90-a_6⌉\end{array}$$

(9)

$$\begin{array}{c}AverageAngle=\frac{AngleSum}{sNode}\end{array}$$

(10)

In Equations (9) and (10), AngleSum is the sum of the angles of the vertices of the simplified building that deviate from right angles, and sNode is the number of vertices of the simplified building. Therefore, AverageAngle is the building’s average value of the vertex angle deviation from a right angle after simplification, and the smaller the value is, the better the orthogonal features of the building are maintained.

In this paper, thirty-five typically distributed buildings, as shown in Figure 14, were randomly selected for comparative analysis. The quality of building regularization using QGIS software and the method proposed in this paper is evaluated in terms of five quantitative analysis indexes, which are the number of vertices, SurfaceDistance, change in area, average vertex angle after regularization, and average running time (the unit is seconds, expressed as running time in

Table 1. Indicators for quantitative evaluation of regularization results of typically distributed buildings.

	QGIS					Proposed Method
	Number of Nodes	Change in Area	Surface Distance	Average Angle	Running Time	Number of Nodes	Change in Area	Surface Distance	Average Angle	Running Time
C-shaped	9.8	0.94	0.10	13.2	0.0003	8.8	0.99	0.22	4.6	0.001
F-shaped	12.4	0.96	0.10	12.1	0.0003	11.6	0.99	0.20	9.1	0.0008
H-shaped	13	0.94	0.10	8.8	0.0004	14	0.99	0.22	12.8	0.001
I-shaped	4.6	0.88	0.14	10.8	0.0001	4	0.99	0.15	0	0.0002
L-shaped	7.4	0.91	0.11	9.2	0.0002	6	0.99	0.14	0.9	0.0007
T-shaped	9	0.94	0.09	11.8	0.0002	9	0.99	0.17	10	0.0004
V-shaped	9.2	0.91	0.12	21.6	0.0004	7.2	0.98	0.23	16	0.001

). The average value of the five evaluation indicators for each of the five building types was calculated. The details are presented in Table 1.

According to the statistical results as presented in Table 1 and shown in Figure 14, we can conclude that:

• After regularization, the number of nodes in the proposed method becomes smaller than that in the QGIS method, with some redundant building vertices and better noise suppression in the contours of the building edges.
• The area of the regularized building obtained using the QGIS method varies considerably, even excessively in complex buildings, indicating that the method of QGIS does not take into account the change in the area of buildings after simplification, whereas the method proposed in this paper maintains a good balance in the area before and after the regularization process. If a building is of a rectangular shape, or if the skeleton lines of the building are right angle at the corner points, then the area remains the same before and after the regularization.
• The SurfaceDistance values obtained using the QGIS method are significantly smaller than those obtained through applying the method proposed in this paper. According to the definition, the smaller the value of SurfaceDistance, the more similar the result of the simplification to that of the original building. This is because of the fact that the building simplified using the QGIS method is more inclined to adhere to the original building, whereas the method proposed in this paper retains the important features of the building and removes the unimportant noise. As shown in Figure 14(a5,b5,c4), the value of SurfaceDistance is greater than 0.25 after using the method proposed in this study; however, the result maintains the key features of the building. In addition, while the value of SurfaceDistance for both the QGIS method and the method in this paper exceeds 0.25 in Figure 14(g5), the method in this study has better performance in maintaining the main structure and orthogonality of the building. This shows that the noise suppression in the QGIS method is not as obvious as in the method proposed in this paper, which maintains the consistency of the area before and after regularization via the adaptive adjustment of the size of the structuring elements and also ensures the orthogonality of the regularized contour via the adaptive adjustment of the orientation of the structuring elements. Therefore, as observed by Yan [13], satisfactory results can be obtained as long as the value of SurfaceDistance remains within a reasonable range; a smaller value indicates a lower degree of regularization and does not necessarily meet the requirements of regularization.
• Through calculating the average value of the angle at each vertex of a building after regularization, the result of the proposed method is found to be closer to a right angle at the vertex of the building than that of the QGIS software, which is more in line with the orthogonal distribution of typical buildings. Especially for convex and concave buildings, as shown in Figure 14(a2,b5), the results of the proposed method are found to be more consistent with the real distribution of buildings.
• The method proposed in this paper is inefficient and the average running time is about three times longer than the QGIS method. The main reason is that the method in this paper encrypts the building edge points during preprocessing in order to improve the accuracy of the extracted skeleton lines.

5. Conclusions

This paper presents a new building regularization algorithm through combining skeleton lines and Minkowski addition. Minkowski addition is a method of regional morphology, which can be applied to both raster and vector data, compared to the mathematical morphological operations defined in the field of digital image processing. In addition to this, it can also reduce the errors caused due to the conversion of the data format during cartographic generalization. Since the size and orientation of the structuring elements in the traditional morphological method remain constant, this tends to lead to large changes in the area between the regularized results and the area of the original building. In contrast, in the proposed method, the size and orientation of the structuring elements are adaptively adjusted during the operation; consistency in area before and after regularization can be maintained through resizing the structuring elements, and the orthogonality of the corner points of building outlines can be preserved via rotating the orientation of the structuring elements. This paper also proposes an angle bisector method for conflict dissolution, which further strengthens the orthogonal characteristics of building outlines. This study provides a new research idea for the regularization of jagged building outlines extracted from remote sensing images.

However, further work is still necessary to improve the algorithm efficiency and improve the algorithm quality. Firstly, before the skeleton lines were extracted, the outline points of the buildings were encrypted. Although the quality of skeleton line extraction can be improved, it is unsatisfactory in terms of efficiency. Thus, adaptive encryption strategies for the contour points of buildings according to the scale of the buildings are necessary. Secondly, in response to the potential loss of building character caused by skeleton line simplification, in our method’s skeleton line simplification [32], its corner points were preserved. However, some buildings have unclear corner points, or the skeleton lines are smoother, leading to problems with missing the extraction of corner points. Therefore, it is necessary to improve the accuracy of corner point detection.