[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Next Article in Journal
Comment on Hicham Bahi, et al. Effects of Urbanization and Seasonal Cycle on the Surface Urban Heat Island Patterns in the Coastal Growing Cities: A Case Study of Casablanca, Morocco. Remote Sens. 2016, 8, 829
Next Article in Special Issue
Classification of ALS Point Cloud with Improved Point Cloud Segmentation and Random Forests
Previous Article in Journal
Satellite Attitude Determination and Map Projection Based on Robust Image Matching
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Remote Sensing
Volume 9
Issue 1
10.3390/rs9010092
remotesensing-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

A Graph-Based Approach for 3D Building Model Reconstruction from Airborne LiDAR Point Clouds

by
Bin Wu
1,2,
Bailang Yu
1,2,*,
Qiusheng Wu
3,
Shenjun Yao
1,2,
Feng Zhao
4,
Weiqing Mao
4 and
Jianping Wu
1,2,*
1
Key Laboratory of Geographic Information Science (Ministry of Education), East China Normal University, Shanghai 200241, China
2
School of Geographic Sciences, East China Normal University, Shanghai 200241, China
3
Department of Geography, Binghamton University, State University of New York, Binghamton, NY 13902, USA
4
Shanghai Surveying and Mapping Institute, 419 Wuning Rd., Shanghai 200063, China
*
Authors to whom correspondence should be addressed.
Remote Sens. 2017, 9(1), 92; https://doi.org/10.3390/rs9010092
Submission received: 13 November 2016 / Revised: 15 December 2016 / Accepted: 12 January 2017 / Published: 20 January 2017
(This article belongs to the Special Issue Remote Sensing for 3D Urban Morphology)
Browse Figures
Graphical abstract
"> Figure 1
<p>Illustration of graph-based localized contour tree representation of buildings: (<b>a</b>) contour representation of a single building; (<b>b</b>) a single-branch contour tree representation of the building shape shown in (<b>a</b>); (<b>c</b>) contour representation of a multi-layers building; and (<b>d</b>) a multi-branch contour tree representation of the building shape shown in (<b>c</b>).</p> "> Figure 2
<p>Bipartite graph matching: (<b>a</b>) two consecutive contours; (<b>b</b>) sets of nodes in two consecutive contours; (<b>c</b>) resulting matchings between the two sets of nodes in (<b>b</b>); and (<b>d</b>) the surface model.</p> "> Figure 3
<p>Virtual contours: (<b>a</b>) the existing gap and virtual contour; (<b>b</b>) a complete model by filling the gap.</p> "> Figure 4
<p>Geographical location and high-resolution aerial photograph of the Lujiazui region in Shanghai, China.</p> "> Figure 5
<p>The georeferenced point clouds of the Lujiazui region.</p> "> Figure 6
<p>Reconstructed building models for the Lujiazui region: (<b>A</b>) the 3D building models for area A; (<b>B</b>) the 3D building models for area B; and (<b>C</b>) the 3D building models for area C.</p> "> Figure 7
<p>Results on selected buildings: (<b>a</b>) and (<b>e</b>) are the building point clouds; (<b>b</b>) and (<b>f</b>) are the outdoor scene pictures; (<b>c</b>) and (<b>g</b>) are the contours in 3D scene; and (<b>d</b>) and (<b>h</b>) are the reconstructed building models.</p> "> Figure 8
<p>Statistical result of the performance.</p> ">
Versions Notes

Abstract

:
3D building model reconstruction is of great importance for environmental and urban applications. Airborne light detection and ranging (LiDAR) is a very useful data source for acquiring detailed geometric and topological information of building objects. In this study, we employed a graph-based method based on hierarchical structure analysis of building contours derived from LiDAR data to reconstruct urban building models. The proposed approach first uses a graph theory-based localized contour tree method to represent the topological structure of buildings, then separates the buildings into different parts by analyzing their topological relationships, and finally reconstructs the building model by integrating all the individual models established through the bipartite graph matching process. Our approach provides a more complete topological and geometrical description of building contours than existing approaches. We evaluated the proposed method by applying it to the Lujiazui region in Shanghai, China, a complex and large urban scene with various types of buildings. The results revealed that complex buildings could be reconstructed successfully with a mean modeling error of 0.32 m. Our proposed method offers a promising solution for 3D building model reconstruction from airborne LiDAR point clouds.

Graphical Abstract">

Graphical Abstract

1. Introduction

Accurate and timely updated three-dimensional (3D) building modelling is a critical component in environmental and modern urban information systems [1,2]. An increasing number of applications, such as urban planning, training simulations, virtual tourism, real-time emergency response, personal navigation, and homeland security, require 3D building models as an input source [2,3,4,5,6]. The 3D building models provide quick access to the urban topography, human-made structures, and our surrounding environment. Thus, 3D reconstruction of buildings has become increasingly important and efficient 3D urban building model reconstruction methods have become a very active research domain in recent years [7,8].
Traditionally, 3D building models are built up manually by using a digital photogrammetric workstation [9]. However, manual 3D processing is time-consuming and labor-intensive [4,10]. Therefore, it is desirable to develop automatic or semi-automatic procedures. The rapid development of spatial data survey techniques in recent years helps to facilitate the development of 3D building model reconstruction [7,8]. Various types of data such as space-borne and aerial imagery [4,11], oblique imagery [12], airborne LiDAR data [3,13], terrestrial laser scanning [14,15], and digital surface model derived from different raw remote sensing data [16,17,18] are available for the extraction and reconstruction of building models. Among the above data sources, airborne LiDAR is one of the most attractive choices for 3D building modeling due to its ability to directly acquire dense 3D point clouds of the observed building surface [3,13,19,20,21,22,23,24,25,26,27,28,29].
A number of approaches have been proposed for extraction and reconstruction of 3D building models from airborne LiDAR data, which can be briefly divided into three categories according to [7]: reconstruction with parametric shapes [30,31], reconstruction based on segmentation [32,33], and reconstruction by digital surface model (DSM) simplification [34,35]. In addition, a more typical classification scheme divides the current approaches into two categories [28,36]: data-driven and model-driven. The data-driven approaches process each part of the building point clouds individually and then obtain the optimal planar roof primitives [13,37]. Several methods have been proposed to determine the planar roof primitives, including plane detection and extraction by random sample consensus (RANSAC) [35,36,38], clustering analysis [39,40], region growing [5,41], and Hough transform [28,36], among others. In contrast, the model-driven approaches search the most appropriate models that are fitted by the corresponding given point clouds among primitive building models contained in a predefined model library [28]. Some methods for the determination of the roof model type were proposed, such as normal vectors [30], reversible jump Markov Chain Monte Carlo [42], support vector machine [43], and the generative statistical approach [44].
Several studies [45,46,47,48] attempted to exploit structural analyses as a way to better understand the 3D structures of historical buildings. In order to monitoring the condition of historical buildings, the finite element (FE) method has been developed to transform three-dimensional point clouds into 3D FE models. A voxel-based algorithm that captures the geometry of the buildings was proposed in [45,46], which uses a voxel grid bounding the cloud region to automatically transform point cloud data into solid 3D models. Other interesting studies [47,48] developed a procedure, called CLOUD2FEM, to transform the 3D point clouds into solid geometry and consequently into an FE model. The FE modeling requires massive dense point clouds as an input, so the algorithm mainly designed for terrestrial laser scanning (TLS) data which cannot be directly applied to ALS data. In addition, the complex processing flow and the poor mobility of TLS systems hinder the extensive 3D building reconstruction for a large urban area.
Although most existing methods for building reconstruction showed promising results, buildings with complex structure are still challenging and difficult to reconstruct. Due to the uncertainty of building structures in urban areas, additional knowledge of buildings has to be incorporated into the modeling process to increase the reliability of building models as well as the range of possible applications [28]. Many approaches [1,5,7,28,49,50,51] rely on the critical observation that most complex structures can be decomposed into multiple parts with much simpler structures. Therefore, topological relations of building structures are of vital importance for building reconstruction. The building contours have explicit topological relationships among each other and therefore can be used for gaining knowledge of topological relations between building structures [1,49,50,52]. Li, Zhang, and Jiang [50] proposed an automatic building reconstruction method by tracing building contours which were extracted from LiDAR-derived TIN dataset. By analyzing characteristics of the building contour lines, it was found that contour lines are important for quantitatively displaying relief and identifying morphometric features on the contour map. Different from other ground objects’ contour lines, the geometric characteristics, such as the area, closeness, completeness of the closed contour lines, appear to be useful for building extraction from other objects and can be further exploited for the model reconstruction [1,50]. On the basis of the inter-topology of building contour lines, Song, Wu, and Jiang [1] separated LiDAR points corresponding to different parts of the building roof and then identified the rooftop type for each part of the building roof. However, these methods still rely on prior knowledge of building primitives and the scheme for determination of primitive mathematical models. Moreover, since the building contours are attached with rich architectural information, such as the shape and structure of buildings, the topological relationships and geometrical information between these contours are not fully utilized.
In this study, we aim to address the drawbacks identified above by employing the graph-based localized contour tree method [53] and bipartite graph-matching theory to reconstruct 3D building models directly from building contours. The proposed method is capable of capturing the topological structure of buildings by using the graph theory-based localized contour tree method, and then reconstructs different parts of buildings from the contours separated by the contour tree.
The organization of the paper is as follows: In the next section, we describe our proposed method for 3D building model reconstruction in detail. In Section 3, the performance of our proposed method is evaluated through a case study. Section 4 provides some discussions of the method. Finally, conclusions are drawn in Section 5.

2. Methodology

The purpose of our research is to reconstruct the building models by addressing both topological and geometrical relations which rely on the information derived from building contours only. The topological relations of building contours are obtained by using the graph-based localized contour tree, while the geometry can be specified by the contours. There are four key procedures that constitute this method: building contour generation, graph-based localized contour tree construction, bipartite graph matching, and building model reconstruction. In the building contour generation, the contours of each building are extracted from airborne LiDAR point clouds with guidance from vector data of 2D building footprints. In the graph-based localized contour tree construction, the hierarchical structure of each building is analyzed and represented by a contour tree. By investigating its topological structure, the contour tree was then separated into several sub-trees, which represent different parts of the building. In the stage of bipartite graph matching, a weighted bipartite graph is constructed between any two adjacent contours to solve the correspondence problem for surface modeling. In the building model reconstruction, building models are reconstructed by connecting all individual parts of the building models generated from the bipartite graph matching into a complete model.

2.1. Building Contours Generation

The preprocessing of getting the contours of each building can be divided into three steps. The first step is to derive the normalized digital surface model (nDSM), which is a rasterized representation of relative height information about objects above the ground [54]. It is computed as the difference between the digital surface model (DSM) and the digital elevation model (DEM). In our study, the DSM was generated from the airborne LiDAR point clouds by using the linear triangulated irregular network (TIN) interpolation method [23,24,25,26]. The DEM was then interpolated from the ground points which was classified using a progressive morphological filter [55]. The selection of cell size is also a key issue in the generation of DSM and DEM. According to [23,56], the cell size ( c ) can be determined by the following formula:
c = 1 / n
where n is the LiDAR pulse density (returns/m2).
The second step is contour generation. Before creating vector contours, a Gaussian smoothing filter was applied to the nDSM to reduce data noise [23]:
G ( x , y ) = 1 2 π δ 2 e − ( x 2 + y 2 ) 2 δ 2
where ( x , y ) is the location and G is a Gaussian kernel with standard deviation δ . Then the contours can be created based on the smoothed nDSM. Two parameters, base contour ( d 0 ) and contour interval ( d i ), should be considered during the contour generation. As the nDSM records relative height information of ground objects, the base contour d 0 is set to 0 m. Following [53], the contour interval d i can be set slightly greater than the vertical accuracy of the LiDAR-derived nDSM. More details about the selection of contour interval d i will be discussed in Section 4.2. After the contour line generation, both open contours and closed contours may appear on the contour map. On the contour map, buildings are represented as closed contours surrounded by other closed contours at a lower height, i.e., contour clusters. Therefore, we removed the open contours to avoid incomplete buildings. Since data noise may exist, the extracted contours may appear to be very coarse. Consequently, a contour line optimization was then conducted. Previous studies used line segments to delineate and fit the basic shapes of buildings. However, many buildings are irregular in reality and, thus, cannot be delineated by line segments only. In order to derive smooth contour lines by preserving the building shape, we adopted the method introduced by Liu [57] for approximation of building contours with line segments and circular arcs.
The final step is obtaining building contours. After the second phase, there are many non-building contours existing on the contour map, such as trees and cars. To eliminate the non-building contours, we employed the vector data of 2D building footprints, which were visually interpreted from high-resolution aerial photographs. With the guidance of the building footprints, individual building contours can be extracted and identified. Then the determined individual building contours are used in the subsequent analyses.

2.2. Graph-Based Localized Contour Tree Construction

After the extraction of building contours, buildings are represented as contour clusters in which closed contours at a higher height are surrounded by other closed contours at a lower height. Previous studies [23,53,58] showed that such contour clusters could be further represented by graph-based localized contour trees. Detailed information about the conceptual framework of the localized contour tree method can be found in [23,53].
In our study, we used contour trees to analyze the topological relationships and structure of building contours. The graph-based localized contour tree of building contours can be constructed based on the contour height values. Each contour tree contains a root node, several internal nodes and leaf (terminal) nodes. It is constructed in a bottom-up manner regarding height value. For a monotonous structural building shown in Figure 1a, the local contour tree (Figure 1b) is initiated with the contour A as the root node, which has the lowest height value. Then, the adjacent contour B is identified and added as the child node of contour A. This iterative process continues until the highest contour F is included as the leaf node. Finally, the single building leads to a single-branch contour tree. Similarly, for a multi-story composite building, as shown in Figure 1c, a multi-branch contour tree (Figure 1d) is established through the contour tree construction. As shown in Figure 1d, the multi-branch contour tree is composed of a root node (A1), six internal nodes (A2, B1, B2, B3, B4, and C1) and two terminal nodes (B5 and C2).
The structure of a building can be decomposed into collections of smaller structures. By analyzing the data structure of the local contour tree, the building structures and topologies can be simplified and recognized. For the single structure building, all the building contours belong to the same structure and the topological relationship of the contours is monotonous. Thus, the single building is represented by a single-branch contour tree. The single branch contour tree in Figure 1b has shown that there are no topology changes in the contour tree, indicating that the corresponding building (Figure 1a) has a single and simple structure. For the buildings with complex structure, interior topological changes are occurring in their corresponding trees. In these trees, only the contours having a homogeneous spatial topology relationship are existing in the same structure, and these contours are represented by a sub-tree in the contour tree. For the multi-branch contour tree shown in Figure 1d, the node A2 has two child nodes B1 and C1, representing a separation relationship in the sense of topological representation. The sub-tree rooted at B1 is a monotonous structure, representing a part of the building. Similarly, the sub-tree rooted at C1 is also a part of the building. Besides, the sub-tree A1–A2 is also a part of the building, which represents the base of the building. Therefore, the building in Figure 1c can be separated into three different components: A1–A2, B1–B5, and C1–C2. Clearly, the local contour tree can capture and emulate the spatial and topological structure of buildings nicely.
With the contour tree construction, each building can be decomposed into multiple individual parts, and each part has a homogeneous and monotonous structure. In the next section, the construction of a surface model for each part is given in detail.

2.3. Bipartite Graph Matching

In our study, the 3D building models are reconstructed directly from the contours. The aim is to create a complete model by integrating all the individual models which are reconstructed from the contours identified in a sub-tree. To simplify the problem, we consider two consecutive contours C B and C U (see Figure 2a). Here, the surface model is constructed by solving the point correspondence problem between these two contours. Then, we use a graph theoretic approach, the weighted bipartite graph matching [59], to solve the point correspondence problem.
Since the number of vertices in contour C B and C U may not equal, the point matching of two point sets does not guarantee the maintenance of the spatial relations [60]. Thus, contour C B and C U are equally divided into n parts, then we get two point sets B and U which correspond to contour C B and C U , respectively. More details about the selection of contour interval n will be discussed in Section 4.2. Subsequently, a bipartite graph G = { B , U , E } is constructed, where E represents the edges linking the vertices in point sets B and U . The bipartite graph G can be defined with | G | = | B | + | U | vertices, where | . | is the cardinality and | B | = | U | = n . According to [6,60,61], the weight of the edges from vertices in B to vertices in U is defined by the distance in the spatial domain, as shown in Figure 2b. Let v i = [ x i ,   y i , c B ] T and v j = [ x j ,   y j , c U ] T be vertices in B and U , respectively, where c B and c U are the contour value (elevation) of contour C B and C U , respectively, and 1 ≤ i , j ≤ n . We calculate the distance by:
d i , j = ‖ v i − v j ‖ 2 ,
where ‖ . ‖ 2 represents the Euclidean norm.
Using the distance term defined in Equation (3), the weight w i , j from v i to v j is given by:
w i , j = e x p ( − d i , j 2 σ 2 ) ,
where e x p is an exponential function, σ is a reduction factor which controls the distance between the vertices. In most cases, σ is selected by trial and error. An appropriate selection for σ can be set to 15 according to [60].
Through constructing the weighted bipartite graph, the point matching problem is solved by computing the maximum matching of the weighted bipartite graph. In our case, if the ∑ i ∑ j w i , j is maximized, the maximum matching result will provide the 1:1 mappings from B and U (Figure 2c). In the graph G = { B , U , E } , let γ k be a bipartite graph matching, and γ represents all of the possible bipartite graph matchings. The maximum matching result γ m means every vertex in point set B is matched to only one vertex in the point set U . In order to solve the maximal matching problem, we employ the Kuhn-Munkres algorithm [62], which is a minimization/maximization algorithm for square matrices of general assignment problems invented by Kuhn [63] and improved by Munkres [62]. Firstly, an n × n edge cost matrix Μ is created, with Μ i , j = w i , j . Given the n × n matrix Μ , find a permutation p ( p t ; t = 0 , … , n − 1 ) of the integers 0 , 1 , 2 , … , n − 1 that minimizes ∑ t = 0 n − 1 M [ t , p t ] . In our research, the objective function of the maximum weighted bipartite matching is given by the following equation:
γ m = a r g m a x γ k ∈ γ ∑ 1 ≤ i , j ≤ n Μ i , j ,
Thus, given a graph G = { B , U , E } and an n × n edge costs matrix Μ , the Kuhn–Munkres algorithm will output a complete max-weighted bipartite matching γ m . The output max-weighted bipartite matching is not only a matching of maximum cardinality, but also is the similarity between two nodes (contours). Large γ m value means a higher similarity, indicating that the shapes of the contours are very similar. By using the Kuhn-Munkres algorithm, we establish the correspondence between the points in consecutive contours to generate the surface model (Figure 2d).
Given any two adjacent contours in a sub-contour tree, the surface model can be generated by the above process. Finally, we integrate all of the surface models into a composite surface model.

2.4. Building Model Reconstruction

Since the building models can be complicated and complex, single-surface models may not be sufficient to express the buildings. In our proposed approach, the buildings are separated into several parts, and each part is reconstructed individually. Each part of the building can be reconstructed by using the procedure above. Thus, the final step is to composite all of the individual part models to a complete model. When connecting the individual part models, the junctions between the lower model and upper model might not come in direct contact but are separated by a small gap (Figure 3a). This is due to the inherent characteristic of the contours: contour interval. Due to the contour interval, the contours positioned at the junctions may be missed.
Considering that the contour interval is very small, we assume that there is no dramatic change in the shape and spatial extent between the two neighboring contours in the gap. Therefore, we add a virtual contour (black dot line B0 and C0 in Figure 3a) in the gap. The shape of the virtual contour is the same as the nearest neighbor contour at a higher height value, while the contour value of the virtual contour is set as same as the most adjacent neighbor contour at a lower height value. As shown in Figure 3a, the virtual contour B0 has the same shape as contour B1 and its contour value is identical to the height value of contour A2. By adding the virtual contour, the gap can be filled (see Figure 3b). So far, we can get a complete and unbroken 3D building model by connecting all the individual parts of the building together.

2.5. Implementation

The proposed algorithm has been implemented using the C# programming language in Microsoft Visual Studio 2015 (Microsoft Corporation, Redmond, WA, USA) and the ArcObjects SDK (Environmental Systems Research Institute, Redlands, CA, USA) for the Microsoft .NET Framework and a software tool was built to streamline the procedures. The ArcObjects SDK provides the basic geometric functions and interface for the analysis of the point clouds and model generation. The required input data include the raw airborne LiDAR point clouds, the ground points identified by the progressive morphological filter, and the 2D building footprints vector data. The output data of the software tool include the building contours and the 3D building models in Multipatch data format.

3. Experiment

3.1. Study Area and Data

We selected the Lujiazui region (Figure 4), a typical urban part of Shanghai, China, as our study area to test the performance of the proposed algorithm. Situated on the eastern bank of Huangpu River and facing the Bund (i.e., a famous waterfront regarded as the landmark of Shanghai) in the Pudong New District, the Lujiazui region is the most famous financial and trade center in Shanghai. The region is studded with around 100 high-rise buildings, many of which are landmark buildings of Shanghai. Six-hundred eighteen buildings (574 residential buildings and 44 commercial buildings) were visually interpreted and recognized from the high-resolution aerial photograph. Together with the residential buildings, the wide range of building heights and various building structure types make the Lujiazui area a great place for validating our proposed method.
The airborne LiDAR point clouds used in our study were provided by the Geomatics Centre at Shanghai Municipal Institute of Surveying and Mapping and were acquired by the Optech ALTM 3100 system. The LiDAR data were provided as ASCII files and each file contains data in XYZ coordinates along with LiDAR intensity. Only the XYZ coordinates were used in our study. These datasets were imported using the “ASCII 3D to Feature Class” conversion tool in the ArcGIS® 3D Analyst Toolbox (Environmental Systems Research Institute, Redlands, CA, USA). The LiDAR point cloud data extracted from the ASCII file is in the map projection of Shanghai local coordinate system and referenced to the horizontal datum-D_Beijing_1954. The study area consists of 15,940,136 sampling points, covering an area of 4,184,300 m2 with an average point density of approximately 4 points/m2. Figure 5 shows the 3D georeferenced point clouds of the study area.

3.2. Results

A total of 1,083,988 ground points were identified using the progressive morphological filter. The DSM and DEM were generated at 0.5-m resolution from the raw points and ground points, respectively. By subtracting the DEM from the DSM, we derived the nDSM. Several parameters are introduced during the four steps of the algorithm. In the contour line generation, contour lines are generated from the nDSM by setting the contour interval d i to 0.5 m and the base contour d 0 to 0 m. In the process of bipartite graph matching, the contours are equally divided into 300 parts ( n = 300).
All of the computations were conducted on a consumer-level PC with an Intel (Intel Corporation, Santa Clara, CA, USA) Core i7 3.0 GHz CPU, 16 GB RAM, running the Windows 7 64-bit operating system. The average time for the 3D reconstruction was 6.47 s per building, including exporting the model to the geodatabase. By using our proposed algorithm, all of the 618 building models (574 residential buildings and 44 commercial buildings) were reconstructed successfully. Figure 6 shows the 3D building models reconstructed in the study area.
Six buildings (marked with red “#” symbol in Figure 4 and Figure 6) are selected to show the details of the raw point clouds, outdoor scene pictures, 3D contours, and reconstructed models (see Figure 7). Compared to the raw 3D point clouds and outdoor scene pictures, the outlines and most of the body details of the selected buildings are well preserved in the corresponding reconstructed models. Buildings #1 to #4 are tower buildings. Building #1, named the Bocom Financial Towers, is a twin-tower structure building with two pitched roofs. The Bocom Financial Towers can be split into the north and south towers. Therefore, the building structure can be represented by a two-branch contour tree. Compared to the reference point clouds and outdoor picture, the outlines and body details of the reconstructed model are well preserved. Buildings #2 (the World Finance Tower), #3 (the Oriental Pearl TV Tower), and #4 (the Shanghai Pudong Customs Building) are all single-tower buildings and, therefore, form single-branch contour trees. The World Finance Tower is a 43-floor skyscraper with an elliptic cylinder body and a crown-shaped roof. Similar to Building #1, the World Finance Tower is reconstructed successfully. The Oriental Pearl TV Tower features two large spheres which are linked by three columns (see Figure 7b). The lower and upper towers have a diameter of 50 and 45 m, respectively. Compared with the outdoor picture reference and raw point clouds, the reconstructed model does not coincide with its actual shape. This is because the three different sized spherical-shaped roofs are located vertically. As a result, only the top spherical-shaped roof was captured in the raw LiDAR points and the other parts were blocked by the topmost spherical-shape roof. When generating the contours, the details of the three columns and walls between the spheres are missing and, thus, the walls are perpendicular to the ground, forming a cylindrical body. A similar situation is found in the Shanghai Pudong Customs Building. Nevertheless, the overall result is acceptable because only a small number of contours are affected by the rooftop. Building #5 (the Sightseeing Platform) is a saddle-shaped building with no clear boundary of the roof. There are two sets of oval-shaped contours, which results in a two-branch contour tree structure. From the reconstruction results in Figure 7, it implies that our proposed method can fully extract and express this irregularly curved shape and the leaf-like roof is reconstructed accurately. Building #6 is the Shanghai International Convention Center with two spheres on the top of both ends. From the raw point clouds, it is a curved building with a flat roof along with four small tops. This complex structure is represented by a six-branch contour tree. Compared with the reference point clouds, the outlines and body details of the reconstructed model are well preserved.

4. Discussion

4.1. Performance

Previous studies showed that the evaluation of methods for 3D building reconstruction is a challenging task [1,8,9,27,64]. Nevertheless, there are still some simple indices that can be used for validation, such as the distance of the input points to the 3D model. In order to measure the quality of our modeling results, we calculated the average point-to-model distance for the 618 buildings. We used the 2D building footprint data to extract the point clouds for each building. The geometric accuracy of the above validation method is displayed in Figure 8. The minimum, maximum, and average distances are 0.10, 0.69 and 0.32 m, respectively. The results show a high accuracy with respect to the distance of the input points to the 3D model.
The reconstruction results of the Lujiazui region and the statistical distance errors demonstrate that the proposed method is suitable for the reconstruction of complex buildings. We compared the performance of our method with the results reported in the literature: 0.14–0.2 m reported by [2], 0–0.2 m reported by [28], 0.03–0.15 m reported by [8], 0.1–0.24 m reported by [27], and 0.17–0.34 m reported by [1]. Although the mean distances reported in these studies are slightly smaller than the one shown in our study, the LiDAR point clouds and the size of study areas used in these studies differ significantly from our study. Our study area is a typical urban scene, which is larger and more complex than the study areas shown in these studies. Additionally, the point density of LiDAR point clouds used in our study is relatively lower. Taking these factors into account, our result is still comparable to the results reported in these previous studies.

4.2. Tuning of Algorithm Parameters

There are two main parameters, contour interval d i and variable n , that need to be set in our approach. In general, the selection of d i and n varies based on the input LiDAR point clouds and the building complexity in the study area. It is challenging to automatically adjust the parameter d i and n for different LiDAR point clouds without prior knowledge. In our study, a range of d i (from 0.1 to 5 m) and n (from 20–500) for model reconstruction of all the six selected buildings (#1 to #6) were conducted to evaluate their impacts on modeling accuracy of 3D buildings. The results are shown in Table 1 and Table 2.
For the parameter d i , selection of a small d i will help to detect the detail of the building surface, but it might result in high computation time. A large d i will help to enhance computing efficiency, but it might lead to reduced accuracy of 3D models. From Table 1, we found that the model errors are relatively stable and low when d i changes from 0.1 to 0.5 m, and then the model errors increase gradually when d i changes from 0.6 to 5 m. As expected, the results indicate that the model errors increase gradually when d i changes from 0.1 to 5 m. When d i is very small, many small building components or details could be captured during the contouring process, which preserves the building components very well. When d i gets larger, many small building components or details may be missed due to the lower density of contour lines, resulting in partial deviation.
In contrast, the effect of parameter n is just the opposite. Large n will help to enhance the model quality, but result in high computation time. Small n will help to increase the speed of modeling, but result in low model quality. From Table 2, we found that the larger the parameter n , the smaller the modeling error. In our experiment, the modeling error is relatively stable and low when n changes from 250 to 500. When n becomes larger, the models are more accurate and can better retain the spatial information among the contours. When n is very small, the spatial information implied in contours may be missed, which could result in geometric distortion.

4.3. Limitations

There are some limitations in our proposed approach. The factors influencing model errors mainly include two aspects: the LiDAR point clouds and the contours. In fact, the level of detail of the 3D model primarily depends on the LiDAR point clouds. In our approach, the airborne LiDAR point cloud dataset is the main input. It records the geometric information about the rooftop structure of building objects from the top and, thus, lacks the capability to capture the sides of buildings. Due to this limitation, the true architectural form under the rooftop might not be detectable, and it could produce a geometric distortion. Additionally, some rooftops are made of transparent materials, such as glass. In this case, the LiDAR system typically does not get effective returns from these rooftops. Moreover, some buildings are adopted in layer structural roofs (e.g., the Oriental Pearl Tower shown in Figure 7). The ALS system only captures the topmost roofs, while the lower parts are obstructed by the higher parts. As a result, these kinds of building surfaces may not be well reconstructed in the final models due to the missing point clouds. Another concern is the contour generation. As mentioned above, selection of a small contour interval will help to detect small objects, but it might result in high computation power and unnecessary redundancy. A large contour interval will contribute to enhancing computing efficiency, but it can cause failure to the recognition of small structures. It should be noted that our algorithm generates the building models directly from the derived contours and does not use the raw point clouds of the buildings. Thus, the sources of error and uncertainty mainly include the interpolation of DSM and DEM, the elimination of open and tiny contours, contour smoothing. These errors could lead to the deviation between the final contours and raw point clouds.

5. Conclusions

3D building reconstruction from airborne LiDAR data is still a challenging problem in the field of remote sensing and computer vision, and it has been an active research topic for the past decades. In this paper, we propose a graph-based approach for modeling urban buildings from airborne LiDAR point clouds. Our method consists of four technical steps: building contour generation, graph-based localized contour tree construction, bipartite graph matching, and building model reconstruction. Different from previous studies, our method is based on the hierarchical structure and topological analysis of building contours. The topological relationships can be quantified using the graph theory-based localized contour tree method. The contour tree is built to split the building structure into individual parts for surface modeling. The case study demonstrates that our proposed method can reconstruct the urban 3D building models well.
The primary contributions of the proposed method are three-fold. First, we applied the localized contour tree method to represent the hierarchical structures of urban buildings. The localized contour tree derives spatial and topological information directly from building contours. The complex structure of building contours can be simplified and separated into several individual parts according to their topological relationships. Second, we adopted the bipartite matching algorithm to generate the surface model for each building component. A significant strength of the algorithm compared to existing methods is the full utilization of building contours. In our work, we made no assumption about prior knowledge of building types. We reconstructed the 3D building models directly from the building contours, and no primitive mathematical models are necessary. Third, the topological and geometrical information of building contours are fully utilized for 3D building model reconstruction.
There are some limitations to our method. Our method has difficulty in reconstructing concave or arch-type rooftops. Since building reconstruction from the LiDAR point clouds is a challenging task, much research still needs to be done in the future. In future work, it would be interesting to improve the building’s reconstruction accuracy by fusing additional LiDAR data collected by other platforms, such as the mobile laser scanning (MLS) data. The MLS data can provide information about the true architectural form under the rooftop. The fusion is useful for improving the extraction of building contours. Additionally, by investigating the morphological character and topological relationships among the contours, individual roof faces, vertical walls, or other objects could be better distinguished from each other. Thus, our method can be combined with other data-driven and model-driven approaches to improve the reconstruction accuracy. Another worthwhile challenge would be to adapt our approach to reconstruct other urban objects, such as street trees.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (No. 41471449), the Natural Science Foundation of Shanghai (No. 14ZR1412200), the Fundamental Research Funds for the Central Universities of China, and the China Scholarship Council (No. 201506140090).

Author Contributions

Bailang Yu and Jianping Wu conceived and supervised this study. Bin Wu, Bailang Yu, Qiusheng Wu, Shenjun Yao, Feng Zhao, Weiqing Mao and Jianping Wu designed the data processing procedures and analyzed the results. Bin Wu, Bailang Yu and Qiusheng Wu performed the experiments and wrote the paper.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Song, J.; Wu, J.; Jiang, Y. Extraction and reconstruction of curved surface buildings by contour clustering using airborne lidar data. Optik 2015, 126, 513–521. [Google Scholar] [CrossRef]
  2. Cheng, L.; Gong, J.; Li, M.; Liu, Y. 3D building model reconstruction from multi-view aerial imagery and lidar data. Photogramm. Eng. Remote Sens. 2011, 77, 125–139. [Google Scholar] [CrossRef]
  3. Vosselman, G.; Dijkman, S. 3D building model reconstruction from point clouds and ground plans. Int. Arch. Photogram. Rem. Sens. Spat. Inform. Sci. 2001, 34, 37–44. [Google Scholar]
  4. Suveg, I.; Vosselman, G. Reconstruction of 3D building models from aerial images and maps. ISPRS J. Photogramm. Remote Sens. 2004, 58, 202–224. [Google Scholar] [CrossRef]
  5. Verma, V.; Kumar, R.; Hsu, S. 3D building detection and modeling from aerial lidar data. In Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Washington, DC, USA, 17–22 June 2006.
  6. Gao, Y.; Dai, Q.; Wang, M.; Zhang, N. 3D model retrieval using weighted bipartite graph matching. Signal Process Image 2011, 26, 39–47. [Google Scholar] [CrossRef]
  7. Haala, N.; Kada, M. An update on automatic 3D building reconstruction. ISPRS J. Photogramm. Remote Sens. 2010, 65, 570–580. [Google Scholar] [CrossRef]
  8. Oude Elberink, S.; Vosselman, G. Quality analysis on 3D building models reconstructed from airborne laser scanning data. ISPRS J. Photogramm. Remote Sens. 2011, 66, 157–165. [Google Scholar] [CrossRef]
  9. Sohn, G.; Huang, X.; Tao, V. Using a binary space partitioning tree for reconstructing polyhedral building models from airborne lidar data. Photogramm. Eng. Remote Sens. 2008, 74, 1425–1438. [Google Scholar] [CrossRef]
  10. Zhou, Q.-Y.; Neumann, U. Fast and extensible building modeling from airborne lidar data. In Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Irvine, CA, USA, 5–7 November 2008.
  11. Brenner, C. Building reconstruction from images and laser scanning. Int. J. Appl. Earth Obs. Geoinf. 2005, 6, 187–198. [Google Scholar] [CrossRef]
  12. Xiao, J.; Gerke, M.; Vosselman, G. Building extraction from oblique airborne imagery based on robust façade detection. ISPRS J. Photogramm. Remote Sens. 2012, 68, 56–68. [Google Scholar] [CrossRef]
  13. Rottensteiner, F. Automatic generation of high-quality building models from lidar data. IEEE Comput. Graph. Appl. 2003, 23, 42–50. [Google Scholar] [CrossRef]
  14. Pu, S.; Vosselman, G. Knowledge based reconstruction of building models from terrestrial laser scanning data. ISPRS J. Photogramm. Remote Sens. 2009, 64, 575–584. [Google Scholar] [CrossRef]
  15. Yang, B.; Fang, L.; Li, J. Semi-automated extraction and delineation of 3D roads of street scene from mobile laser scanning point clouds. ISPRS J. Photogramm. Remote Sens. 2013, 79, 80–93. [Google Scholar] [CrossRef]
  16. Arefi, H.; Reinartz, P. Building reconstruction using dsm and orthorectified images. Remote Sens. 2013, 5, 1681–1703. [Google Scholar] [CrossRef]
  17. Brédif, M.; Tournaire, O.; Vallet, B.; Champion, N. Extracting polygonal building footprints from digital surface models: A fully-automatic global optimization framework. ISPRS J. Photogramm. Remote Sens. 2013, 77, 57–65. [Google Scholar] [CrossRef]
  18. Yang, B.; Shi, W.; Li, Q. An integrated tin and grid method for constructing multi-resolution digital terrain models. Int. J. Geogr. Inf. Sci. 2005, 19, 1019–1038. [Google Scholar] [CrossRef]
  19. Wu, B.; Yu, B.; Yue, W.; Wu, J.; Huang, Y. Voxel-based marked neighborhood searching method for identifying street trees using vehicle-borne laser scanning data. In Proceedings of the Second International Workshop on Earth Observation and Remote Sensing Applications, Shanghai, China, 8–11 June 2012; pp. 327–331.
  20. Wu, B.; Yu, B.; Yue, W.; Shu, S.; Tan, W.; Hu, C.; Huang, Y.; Wu, J.; Liu, H. A voxel-based method for automated identification and morphological parameters estimation of individual street trees from mobile laser scanning data. Remote Sens. 2013, 5, 584–611. [Google Scholar] [CrossRef]
  21. Huang, Y.; Chen, Z.; Wu, B.; Chen, L.; Mao, W.; Zhao, F.; Wu, J.; Wu, J.; Yu, B. Estimating roof solar energy potential in the downtown area using a gpu-accelerated solar radiation model and airborne lidar data. Remote Sens. 2015, 7, 17212–17233. [Google Scholar] [CrossRef]
  22. Wu, B.; Yu, B.; Huang, C.; Wu, Q.; Wu, J. Automated extraction of ground surface along urban roads from mobile laser scanning point clouds. Remote Sens. Lett. 2016, 7, 170–179. [Google Scholar] [CrossRef]
  23. Wu, B.; Yu, B.; Wu, Q.; Huang, Y.; Chen, Z.; Wu, J. Individual tree crown delineation using localized contour tree method and airborne lidar data in coniferous forests. Int. J. Appl. Earth Obs. Geoinf. 2016, 52, 82–94. [Google Scholar] [CrossRef]
  24. Yu, S.; Yu, B.; Song, W.; Wu, B.; Zhou, J.; Huang, Y.; Wu, J.; Zhao, F.; Mao, W. View-based greenery: A three-dimensional assessment of city buildings’ green visibility using floor green view index. Landsc. Urban Plan. 2016, 152, 13–26. [Google Scholar] [CrossRef]
  25. Yu, B.; Liu, H.; Wu, J.; Hu, Y.; Zhang, L. Automated derivation of urban building density information using airborne lidar data and object-based method. Landsc. Urban Plan. 2010, 98, 210–219. [Google Scholar] [CrossRef]
  26. Huang, Y.; Yu, B.; Zhou, J.; Hu, C.; Tan, W.; Hu, Z.; Wu, J. Toward automatic estimation of urban green volume using airborne lidar data and high resolution remote sensing images. Front. Earth Sci. 2013, 7, 43–54. [Google Scholar] [CrossRef]
  27. Lafarge, F.; Mallet, C. Creating large-scale city models from 3D-point clouds: A robust approach with hybrid representation. Int. J. Comput. Vis. 2012, 99, 69–85. [Google Scholar] [CrossRef]
  28. Maas, H.-G.; Vosselman, G. Two algorithms for extracting building models from raw laser altimetry data. ISPRS J. Photogramm. Remote Sens. 1999, 54, 153–163. [Google Scholar] [CrossRef]
  29. Cheng, L.; Tong, L.; Chen, Y.; Zhang, W.; Shan, J.; Liu, Y.; Li, M. Integration of lidar data and optical multi-view images for 3D reconstruction of building roofs. Opt. Lasers Eng. 2013, 51, 493–502. [Google Scholar] [CrossRef]
  30. Kada, M.; McKinley, L. 3D building reconstruction from lidar based on a cell decomposition approach. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. 2009, 38, 47–52. [Google Scholar]
  31. Milde, J.; Brenner, C. Graph-based modeling of building roofs. In Proceedings of the 12th AGILE Conference on GIScience, Hannover, Germany, 2–5 June 2009.
  32. Vosselman, G.; Gorte, B.G.; Sithole, G.; Rabbani, T. Recognising structure in laser scanner point clouds. Int. Arch. Photogram. Rem. Sens. Spat. Inf. Sci 2004, 46, 33–38. [Google Scholar]
  33. Sampath, A.; Shan, J. Segmentation and reconstruction of polyhedral building roofs from aerial lidar point clouds. IEEE Trans. Geosci. Remote Sens 2010, 48, 1554–1567. [Google Scholar] [CrossRef]
  34. Wahl, R.; Schnabel, R.; Klein, R. From detailed digital surface models to city models using constrained simplification. Photogramm. Fernerkund. 2008, 12, 207–215. [Google Scholar]
  35. Schnabel, R.; Wahl, R.; Klein, R. Efficient ransac for point-cloud shape detection. Comput. Graph. Forum 2007, 26, 214–226. [Google Scholar] [CrossRef]
  36. Tarsha-Kurdi, F.; Landes, T.; Grussenmeyer, P. Hough-transform and extended ransac algorithms for automatic detection of 3D building roof planes from lidar data. In Proceedings of the ISPRS Workshop on Laser Scanning, Espoo, Finland, 12–14 September 2007.
  37. Kim, K.; Shan, J. Building roof modeling from airborne laser scanning data based on level set approach. ISPRS J. Photogramm. Remote Sens. 2011, 66, 484–497. [Google Scholar] [CrossRef]
  38. Tarsha-Kurdi, F.; Landes, T.; Grussenmeyer, P. Extended ransac algorithm for automatic detection of building roof planes from lidar data. Photogramm. J. Finl. 2008, 21, 97–109. [Google Scholar]
  39. Filin, S.; Pfeifer, N. Segmentation of airborne laser scanning data using a slope adaptive neighborhood. ISPRS J. Photogramm. Remote Sens. 2006, 60, 71–80. [Google Scholar] [CrossRef]
  40. Biosca, J.M.; Lerma, J.L. Unsupervised robust planar segmentation of terrestrial laser scanner point clouds based on fuzzy clustering methods. ISPRS J. Photogramm. Remote Sens. 2008, 63, 84–98. [Google Scholar] [CrossRef]
  41. Rottensteiner, F.; Trinder, J.; Clode, S.; Kubik, K. Automated delineation of roof planes from lidar data. Isprs Workshop Laser Scanning 2005, 36, 221–226. [Google Scholar]
  42. Lafarge, F.; Descombes, X.; Zerubia, J.; Pierrot-Deseilligny, M. Structural approach for building reconstruction from a single DSM. IEEE Trans. Pattern Anal. Mach. Intell. 2010, 32, 135–147. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  43. Henn, A.; Gröger, G.; Stroh, V.; Plümer, L. Model driven reconstruction of roofs from sparse lidar point clouds. ISPRS J. Photogramm. Remote Sens. 2013, 76, 17–29. [Google Scholar] [CrossRef]
  44. Huang, H.; Brenner, C.; Sester, M. A generative statistical approach to automatic 3D building roof reconstruction from laser scanning data. ISPRS J. Photogramm. Remote Sens. 2013, 79, 29–43. [Google Scholar] [CrossRef]
  45. Truong-Hong, L.; Laefer, D. Validating computational models from laser scanning data for historic facades. J. Test. Eval. 2013, 41, 1–16. [Google Scholar] [CrossRef]
  46. Truong-Hong, L.; Laefer, D.F. Octree-based, automatic building façade generation from lidar data. Comput. Aided Des. 2014, 53, 46–61. [Google Scholar] [CrossRef]
  47. Castellazzi, G.; Altri, A.; Bitelli, G.; Selvaggi, I.; Lambertini, A. From laser scanning to finite element analysis of complex buildings by using a semi-automatic procedure. Sensors 2015, 15, 18360–18380. [Google Scholar] [CrossRef] [PubMed]
  48. Castellazzi, G.; D’Altri, A.M.; de Miranda, S.; Ubertini, F. An innovative numerical modeling strategy for the structural analysis of historical monumental buildings. Eng. Struct. 2017, 132, 229–248. [Google Scholar] [CrossRef]
  49. Zhang, J.; Li, L.; Lu, Q.; Jiang, W. Contour clustering analysis for building reconstruction from lidar data. In Proceedings of the International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Beijing, China, 3–11 July 2008.
  50. Li, L.; Zhang, J.; Jiang, W. Automatic complex building reconstruction from lidar based on hierarchical structure analysis. Proc. SPIE 2009, 7496, 74961–74968. [Google Scholar]
  51. Chen, L.; Teo, T.; Rau, J.; Liu, J.; Hsu, W. Building reconstruction from lidar data and aerial imagery. In Proceedings of the IEEE International Geoscience and Remote Sensing Symposium, Boston, MA, USA, 6–11 July 2005.
  52. Yang, B.; Wei, Z.; Li, Q.; Li, J. Semiautomated building facade footprint extraction from mobile lidar point clouds. IEEE Geosci. Remote Sens. Lett. 2013, 10, 766–770. [Google Scholar] [CrossRef]
  53. Wu, Q.; Liu, H.; Wang, S.; Yu, B.; Beck, R.; Hinkel, K. A localized contour tree method for deriving geometric and topological properties of complex surface depressions based on high-resolution topographical data. Int. J. Geogr. Inf. Sci. 2015, 29, 2041–2060. [Google Scholar] [CrossRef]
  54. Yu, B.; Liu, H.; Wu, J.; Lin, W.-M. Investigating impacts of urban morphology on spatio-temporal variations of solar radiation with airborne lidar data and a solar flux model: A case study of downtown houston. Int. J. Remote Sens. 2009, 30, 4359–4385. [Google Scholar] [CrossRef]
  55. Zhang, K.; Chen, S.-C.; Whitman, D.; Shyu, M.-L.; Yan, J.; Zhang, C. A progressive morphological filter for removing nonground measurements from airborne lidar data. IEEE Trans. Geosci. Remote Sens. 2003, 41, 872–882. [Google Scholar] [CrossRef]
  56. Chen, Q.; Baldocchi, D.; Gong, P.; Kelly, M. Isolating individual trees in a savanna woodland using small footprint lidar data. Photogramm. Eng. Remote Sens. 2006, 72, 923–932. [Google Scholar] [CrossRef]
  57. Liu, H. The Automatic Recognition Software Technique of the Geometrical Elements about the Skeleton Map. Master’s Thesis, Tsinghua University, Beijing, China, 2006. [Google Scholar]
  58. Guilbert, E. Multi-level representation of terrain features on a contour map. GeoInformatica 2013, 17, 301–324. [Google Scholar] [CrossRef]
  59. West, D.B. Introduction to Graph Theory; Prentice hall Upper Saddle River: Bergen County, NJ, USA, 2001. [Google Scholar]
  60. Alper, Y.; Mubarak, S. Actions sketch: A novel action representation. In Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Washington, DC, USA, 20–26 June 2005.
  61. Wen, Y.; Gao, Y.; Hong, R.; Luan, H.; Liu, Q.; Shen, J.; Ji, R. View-based 3d object retrieval by bipartite graph matching. In Proceedings of the 20th ACM International Conference on Multimedia, Nara, Japan, 29 October–2 November 2012; pp. 897–900.
  62. Munkres, J. Algorithms for the assignment and transportation problems. SIAM J. Appl. Math 1957, 5, 32–38. [Google Scholar] [CrossRef]
  63. Kuhn, H.W. The hungarian method for the assignment problem. Nav. Res. Logist. Q. 1955, 2, 83–97. [Google Scholar] [CrossRef]
  64. You, S.; Hu, J.; Neumann, U.; Fox, P. Urban site modeling from lidar. In Computational Science and Its Applications—ICCSA 2003; Kumar, V., Gavrilova, M.L., Tan, C.J.K., L’Ecuyer, P., Eds.; Springer: Berlin/Heidelberg, Germany, 2003; pp. 579–588. [Google Scholar]
Remotesensing 09 00092 g001 550
Figure 1. Illustration of graph-based localized contour tree representation of buildings: (a) contour representation of a single building; (b) a single-branch contour tree representation of the building shape shown in (a); (c) contour representation of a multi-layers building; and (d) a multi-branch contour tree representation of the building shape shown in (c).
Figure 1. Illustration of graph-based localized contour tree representation of buildings: (a) contour representation of a single building; (b) a single-branch contour tree representation of the building shape shown in (a); (c) contour representation of a multi-layers building; and (d) a multi-branch contour tree representation of the building shape shown in (c).
Remotesensing 09 00092 g001
Remotesensing 09 00092 g002 550
Figure 2. Bipartite graph matching: (a) two consecutive contours; (b) sets of nodes in two consecutive contours; (c) resulting matchings between the two sets of nodes in (b); and (d) the surface model.
Figure 2. Bipartite graph matching: (a) two consecutive contours; (b) sets of nodes in two consecutive contours; (c) resulting matchings between the two sets of nodes in (b); and (d) the surface model.
Remotesensing 09 00092 g002
Remotesensing 09 00092 g003 550
Figure 3. Virtual contours: (a) the existing gap and virtual contour; (b) a complete model by filling the gap.
Figure 3. Virtual contours: (a) the existing gap and virtual contour; (b) a complete model by filling the gap.
Remotesensing 09 00092 g003
Remotesensing 09 00092 g004 550
Figure 4. Geographical location and high-resolution aerial photograph of the Lujiazui region in Shanghai, China.
Figure 4. Geographical location and high-resolution aerial photograph of the Lujiazui region in Shanghai, China.
Remotesensing 09 00092 g004
Remotesensing 09 00092 g005 550
Figure 5. The georeferenced point clouds of the Lujiazui region.
Figure 5. The georeferenced point clouds of the Lujiazui region.
Remotesensing 09 00092 g005
Remotesensing 09 00092 g006 550
Figure 6. Reconstructed building models for the Lujiazui region: (A) the 3D building models for area A; (B) the 3D building models for area B; and (C) the 3D building models for area C.
Figure 6. Reconstructed building models for the Lujiazui region: (A) the 3D building models for area A; (B) the 3D building models for area B; and (C) the 3D building models for area C.
Remotesensing 09 00092 g006
Remotesensing 09 00092 g007 550
Figure 7. Results on selected buildings: (a) and (e) are the building point clouds; (b) and (f) are the outdoor scene pictures; (c) and (g) are the contours in 3D scene; and (d) and (h) are the reconstructed building models.
Figure 7. Results on selected buildings: (a) and (e) are the building point clouds; (b) and (f) are the outdoor scene pictures; (c) and (g) are the contours in 3D scene; and (d) and (h) are the reconstructed building models.
Remotesensing 09 00092 g007
Remotesensing 09 00092 g008 550
Figure 8. Statistical result of the performance.
Figure 8. Statistical result of the performance.
Remotesensing 09 00092 g008
Table
Table 1. Impact of contour interval d i on the accuracy of building model reconstruction.
Table 1. Impact of contour interval d i on the accuracy of building model reconstruction.
No./ d i 0.10.20.30.40.50.60.70.80.91.01.52.03.04.05.0
#10.390.410.420.430.430.520.650.960.980.991.041.071.101.441.84
#20.330.350.350.360.360.370.390.390.430.450.590.720.971.021.43
#30.490.490.500.520.540.570.600.670.770.911.031.572.223.284.05
#40.280.290.290.370.420.420.480.540.670.790.901.282.002.934.42
#50.170.190.200.220.280.300.300.320.390.440.510.701.321.972.56
#60.260.280.300.310.310.430.460.470.590.650.670.811.702.233.19
Table
Table 2. Impact of parameter n on the accuracy of building model reconstruction.
Table 2. Impact of parameter n on the accuracy of building model reconstruction.
No./ n 20406080100120140160180200250300350400500
#10.660.510.450.440.440.430.430.430.430.430.430.430.430.430.43
#20.820.670.590.510.420.410.390.390.370.370.360.360.360.350.35
#30.930.810.740.690.670.600.580.570.570.560.550.540.520.510.51
#41.231.051.010.980.790.770.760.680.600.550.450.420.400.380.38
#50.510.460.440.430.410.390.350.320.320.310.280.280.240.220.21
#60.470.360.330.320.320.320.320.320.320.320.310.310.310.310.31

Share and Cite

MDPI and ACS Style

Wu, B.; Yu, B.; Wu, Q.; Yao, S.; Zhao, F.; Mao, W.; Wu, J. A Graph-Based Approach for 3D Building Model Reconstruction from Airborne LiDAR Point Clouds. Remote Sens. 2017, 9, 92. https://doi.org/10.3390/rs9010092

AMA Style

Wu B, Yu B, Wu Q, Yao S, Zhao F, Mao W, Wu J. A Graph-Based Approach for 3D Building Model Reconstruction from Airborne LiDAR Point Clouds. Remote Sensing. 2017; 9(1):92. https://doi.org/10.3390/rs9010092

Chicago/Turabian Style

Wu, Bin, Bailang Yu, Qiusheng Wu, Shenjun Yao, Feng Zhao, Weiqing Mao, and Jianping Wu. 2017. "A Graph-Based Approach for 3D Building Model Reconstruction from Airborne LiDAR Point Clouds" Remote Sensing 9, no. 1: 92. https://doi.org/10.3390/rs9010092

APA Style

Wu, B., Yu, B., Wu, Q., Yao, S., Zhao, F., Mao, W., & Wu, J. (2017). A Graph-Based Approach for 3D Building Model Reconstruction from Airborne LiDAR Point Clouds. Remote Sensing, 9(1), 92. https://doi.org/10.3390/rs9010092

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop