Object-Based Building Boundary Extraction From Lidar Data
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 183 | |
| Author | ||
| License | CC Attribution - NonCommercial - ShareAlike 3.0 Germany: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/32006 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language | ||
| Producer | ||
| Production Year | 2015 | |
| Production Place | Seoul, South Korea |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
FOSS4G Seoul 201529 / 183
7
8
47
53
54
65
73
74
79
82
84
92
102
103
105
124
126
127
130
141
142
143
156
161
162
170
176
178
181
183
00:00
Presentation of a groupElectronic data processingReading (process)Point cloudModemPoint (geometry)Theory of relativityMultiplication signProcess (computing)Endliche ModelltheorieMassTouchscreenInformation securityRule of inferenceProjective planeGreatest elementText editorLine (geometry)Beat (acoustics)Differential equationSlide ruleMereologyType theoryDerivation (linguistics)NumberNetwork topologyRight angleWorkstation <Musikinstrument>Degree (graph theory)Bridging (networking)Artificial neural networkPolygonProfil (magazine)DigitizingGraph coloringCivil engineeringData modelComputer animation
02:09
Network topologyWindowInformationZeitdilatationAdaptive behaviorPixelProfil (magazine)Raster graphicsDiscrepancy theoryBasis <Mathematik>Point (geometry)FeedbackMathematicsDifferent (Kate Ryan album)AlgorithmPreprocessorSet (mathematics)Type theoryCalculationMedical imagingProcess (computing)Multiplication signSpacetimeCharacteristic polynomialOverhead (computing)AdditionGreen's functionDifferenz <Mathematik>Motion captureSpectrum (functional analysis)AreaRoundness (object)Vector spaceTrailTouchscreenElectric generatorPrice indexAlgebraMaxima and minimaObservational studyDigital photographyLevel (video gaming)ApproximationsalgorithmusLattice (order)ReliefFerry CorstenThermal radiationTheory of relativityCollisionNumberReading (process)Execution unitPoint cloudImage resolutionScripting languageEndliche ModelltheorieRight angleReal numberResultantSoftware testingDataflowSpline (mathematics)Rule of inferenceComplex (psychology)Parameter (computer programming)Square numberSlide ruleBeta functionSummierbarkeitTerm (mathematics)MereologyComputer animation
11:23
SurfaceProduct (business)Shape (magazine)Point (geometry)ResultantArtificial neural networkSpacetimeCivil engineeringAreaNetwork topologyIntegrated development environmentFigurate numberMathematicsSocial classMedical imagingProjective planeEndliche ModelltheorieApproximationsalgorithmusFilter <Stochastik>Type theoryDifferential equationObject (grammar)ChainEvent horizonPlanningGreatest elementComputer animation
13:34
SoftwareMedical imagingResultantPolygonDifferent (Kate Ryan album)Negative numberSummierbarkeitRaster graphicsConvex setAlgorithmVector spaceShape (magazine)CodeMereologyAlpha (investment)Visualization (computer graphics)Green's functionPairwise comparisonSpacetimeNetwork topologyRandwertproblemSaddle pointWindowOpen sourceConvex hullPoint (geometry)Differential equationAreaMusical ensembleTerm (mathematics)Vertex (graph theory)Axiom of choiceResidual (numerical analysis)Graph coloringGoodness of fitSource codeTracing (software)Normal (geometry)Multiplication signExecution unitType theoryTunisError messageRight angleBit rateFile formatSet (mathematics)Menu (computing)WordComputer hardwarePrisoner's dilemmaObservational studyGroup actionForm (programming)Subject indexingProduct (business)
21:24
Shape (magazine)Complete metric spaceGoodness of fitAreaTerm (mathematics)Annihilator (ring theory)Different (Kate Ryan album)Line (geometry)Data conversionPoint (geometry)Combinational logicSoftware testingEndliche ModelltheorieMetreResultantSoftwarePopulation densityMultiplication signWebsitePressureStatisticsMereologyAverageAlgorithmInformationReading (process)Closed setDistanceComplex (psychology)Parameter (computer programming)Query languageParticle systemType theoryWindowBitWorkstation <Musikinstrument>Set (mathematics)QuantumComputer fileTemporal logicExecution unitError messageSampling (statistics)RandwertproblemComputer hardwareMeasurementCarry (arithmetic)Figurate numberConvex hullAxiom of choiceDirection (geometry)Raster graphicsPolygonDuality (mathematics)Interior (topology)Vertex (graph theory)Computer animation
29:14
RandwertproblemType theorySquare numberAreaMoment (mathematics)Roundness (object)Touch typingResidual (numerical analysis)Shape (magazine)Endliche ModelltheoriePolygonComputer animation
31:10
Computer animation
Transcript: English(auto-generated)
00:03
Okay, this presentation is about LiDAR data processing. As you can see, LiDAR data has a lot of 3D points. So we say point cloud. On the bottom of the screen, you see 3D points,
00:22
a massive number of points, 3D points, represent by colors. Each color represents elevation. And on top of this slide, you see article profile along a line from A to B. So basically what we want to do is we want to classify
00:43
points representing ground and points representing non-ground. That's the first step we do for the LiDAR processing. And once we have ground points, then we create DEM, digital elevation model, or digital terrain model.
01:03
Some people say DTM. And that's basic data model for all kinds of civil engineering projects. Then the next step is we want to classify non-ground points further to vegetation points,
01:22
points, LiDAR points representing trees and shrubs and other types of vegetation. And then we want to extract points representing artificial objects like buildings and roads and bridges like that.
01:42
And that's not it because once you have point cloud representing buildings, they are just points. But what we want is a 3D model of each building. So you want to have a nice, smooth 3D polygon per building out of LiDAR point cloud.
02:03
So I want to talk about overall process of building extraction from airborne LiDAR data. Most filtering algorithms to classify ground points, most of filtering algorithms use rasterization.
02:20
What that means is we convert LiDAR data, which is a messy point, to grid-based images. The reason why we use rasterization is because we have too many points to process. So it takes a lot of time and it's not efficient.
02:41
But the drawback, the main drawback of rasterization is we need additional computing overhead. So it is an overhead for pre-processing. Once it's done, we can just go ahead and process raster data. And the reason why we use raster data is because
03:03
raster data is a lot easier to process. You can apply map algebra or any geo-processing algorithms to raster images. For example, you can just soft track from one image to another. That's very simple. But if you soft track, if you have two different
03:21
point data sets, then even subtraction of the two is not easy because it's all coordinate-based calculation. So coordinate-based calculation is very costly. And that's the main reason why we use rasterization for LiDAR data processing. However, if we use rasterization, some points,
03:42
a couple of points representing one pixel can be merged to one. So you have to average out a couple of points to represent single pixel, which means we lose some information out of that. And if we lose some information by rasterization,
04:04
it means we increase the uncertainty. And that's the reason why we use no rasterization. We want to just stick to vector data. And also, we want to use adaptive window size. When you filter out LiDAR data,
04:23
if we use LiDAR data as a raw data, then you have to use a window. You can use a three by three window or a seven by seven window, you have to filter out by swiping these windows across the data.
04:40
But our main goal is to extract buildings. And as you can imagine, we have all kinds of different size of buildings. Commercial properties, commercial buildings are often large size, and residential buildings like houses are relatively small.
05:03
So if you stick to the fixed window size, sometimes the accuracy is not good enough. So we want to use adaptive window size, and also we want to use morphological filtering, which means we want to use terrain as a basis
05:23
for the classification of ground and non-ground points. Once morphological filtering is applied to LiDAR data, then DTM generation is possible, and then building detection is followed.
05:42
The study area of our study is the UNSW campus, which is one kilometer by two kilometers. I want to say this data set is quite challenging in many reasons, because UNSW campus is situated
06:01
in the heart of Sydney, which is metropolitan city, and therefore we have small residential buildings, but also we have high-rise buildings, and sometimes roads are very steep, and tall trees and small bushes,
06:22
and large green areas are available across the campus. The LiDAR data set we have has X, Y, Z, and intensity, and as a supplement data, we use L1 imagery,
06:43
which comes with RGB values. The main problem with these two data sets is that the two data sets are acquired in different times. There is a two-year gap between two data sets,
07:01
so there is some discrepancy between two data sets. So this is an overview of the campus. It's an aerial also photo of the campus. You can see green space and round buildings
07:22
and very complex buildings. You don't see the topography here, but actually this is lower campus, and this is upper campus, and along the main road from lower campus to the upper campus, the slope is quite high.
07:47
And this is the screen capture of LiDAR intensity map, because LiDAR intensity is near infrared images, typical LiDAR is a spectrum of 1,040 nanometers,
08:07
which belongs to near infrared. So we can use LiDAR intensity to classify vegetation and buildings and roads and green spaces.
08:21
So the spectrum, I mean, the characteristics of each types of entity is different in intensity images. So this is quite useful information for our work. And this is vertical profile of the main road.
08:40
You can see high, tall trees along the road, and there is buildings, and you see there's upper campus. And our goal is to extract only buildings out of this LiDAR data.
09:02
So what do we do for the ground point classification is that we use morphological filtering, which employs dilation and erosion. The reason why we use dilation and erosion is to find the local maxima and local minima
09:23
from the LiDAR point cloud, so that we can separate ground points and non-ground points. And then we develop a adaptive window size indicator, and this indicator is used to detect a rough approximate size of the buildings.
09:45
And it is automatic adaptation of window size, so when we run this step for the first time, we can have approximate size of each building,
10:01
and therefore we can change the window size accordingly. Then window size is not fixed, it changes over time as we move along. So this is a workflow of adaptive filtering.
10:20
I don't want to go in detail because it's a bit complex, but what I want to say here is we use elevation information and intensity information, and we apply some criteria to classify ground points and non-ground points, and this is not just one time filter.
10:44
We use iteratively, and therefore we give some feedback to the results, and once the data doesn't meet one of the criteria, then we go back to the previous step and apply it, change the window size,
11:04
and we do it iteratively. So this, the right-hand side of this workflow is about adaptive indicator.
11:24
The details can be found from our paper, if you're interested. So this is initial outcome of filtering. The filter data has two classes, just two classes.
11:41
The first class is ground points, the points representing ground. So if you remember the area image that I've shown you before, you see green space is left here, and all black areas are building footprints. So colored areas are green areas,
12:04
and on the bottom, these are non-ground points, including tall trees and buildings and other artificial objects. So the top figure shows you very flat area,
12:23
although you can see the elevation change from lower campus to the upper campus, but all the points show you very smooth surface. But on the bottom, because this is a non-ground point, you see the shape of the building,
12:41
approximate height of the building, approximate height of tree, and so on. You can see them from the bottom figure. So this is the initial result. And many civil engineers, environmental engineers, other people use the top product. This is very useful product for them
13:02
because they can use this one to create DTM, and DTM can be used for many urban planning purposes. But we don't use them for our project because our goal is to create 3D model or the buildings.
13:22
So we discard the top product, and we use the just bottom product. But this is not ready for building extraction because of trees. In order to remove trees from the non-ground points, we use normalized difference vegetation index,
13:43
which is the ratio, which is the difference between red band from aerial image and new infrared band from LIDAR data. So we use the fused data. So first of all, we have to fuse LIDAR data and aerial imagery, and then use two different bands.
14:05
One is red band, and the other is new infrared, and take the difference between the two. But we have to normalize it by dividing by the sum of the two. Of course, some of you are aware
14:22
that NDVI is not perfect, especially if LIDAR intensity is not stable. LIDAR intensity is very good source for data classification,
14:40
but the main drawback of LIDAR intensity is that the amplitude of LIDAR may change depending on what time of day you use, depending on what time of the day you collect the LIDAR data. So we don't use LIDAR intensity as it is.
15:05
We actually normalize intensity first, and then we use normalized intensity to create, to calculate NDVI. Once vegetation is removed from non-ground points,
15:25
then what is left is just building points. So the points form each building. However, they are just saddle points. So what we do is to trace out the boundaries,
15:40
the edges of the buildings. There are many algorithms to detect the boundary of the buildings, but we tried three different algorithms. The first one is ARPA shape, and the second one is ARPA shape. I'm gonna explain what ARPA shape is.
16:00
The second one is grid-based algorithm. So we rasterize at this step. We rasterize building points into grid, and then use grid-based algorithm here. But this is just for comparison purpose. Our final choice is not grid-based. Our final choice is modified convex hull algorithm.
16:26
So we tried, we tested three different algorithms to create 3D building in vector format, and then fine-tuning is applied to remove small residuals.
16:44
So this is the extracted buildings of the campus. Now you can see the green space, large green space is removed. All the trees are removed. What is left here is just buildings.
17:01
But if you look at it very closely, you will see the building points are almost irregular. It's not smooth enough. So what we can do is we have to apply fine-tuning again to this product. But I want you to look at this part.
17:23
This is residential area, so it has very small houses compared to campus buildings. And that's the main reason why we try adaptive window size. When we have initial classification results
17:42
over the residential area, the result is not so good. You can see all the building points and ground points are mixed up. So this is unfiltered classification. Once we apply the filter,
18:00
what is left here is, so this is a negative image of buildings. So white space represent buildings and gray colors represent ground and trees.
18:20
So once fine-tuning is done, we have a final outcome. So we try to assess our results. We tried, we tested four different areas over the campus. Lower campus, upper campus, and sloppy area and the residential area. The commission area is,
18:44
on the average, about 6%. So we got about 94% accuracy in terms of commission area. But in terms of vertical RMSE,
19:00
our result shows about 36 centimeters overall, which is acceptable, I think. So what is alpha shape algorithm? Alpha shape algorithm is easy to understand,
19:22
but it's not easy to implement in coding. If we have points representing a building, what you can do is start from any point and draw a circle. And if there's some point inside the circle,
19:40
that's not part of the edge, so remove that point. And you move along. So at the end, what you have is, you have edge around the boundary or the buildings. So this is an alpha shape algorithm.
20:03
And the grid-based algorithm is, first of all, you just visualize vector data, and then once you have an image, raster image, then you can apply just any algorithm available.
20:20
Commercial software such as ArcGIS has a tool that converts images to polygons. You can have a polygonalization tool from open source software or commercial software.
20:42
So you can use just existing algorithm to create polygons. So I think this is one of the easiest method to create building boundaries, because you don't have to develop your own algorithm.
21:00
You can just simply use existing tool. The third one we tried is modified convex hull algorithm. So once you have a set of points, then you create convex hull. Once you have a convex hull,
21:21
then you start tracing. And just go on this tracing and find the next point that is part of the edge, and at the end you have a final boundary. I want to say that this modified convex hull algorithm
21:42
is not same as concave hull algorithm. Concave hull algorithm is also available on commercial software. But one of the disadvantages of concave hull algorithm is that you have to find a good parameter.
22:03
Depending on which parameter you use, you can have very thin polygons, or you have too much close to convex hull. So finding a suitable parameter for concave hull
22:20
is main challenge. But here, modified convex hull algorithm is different from concave hull algorithm because we trace along the boundary. So these are two samples of the UNSW buildings.
22:44
One is just rectangular annulus, and another one is complex building. Upper shape works very good. We can have outer polygon and inner polygon nicely.
23:01
And we can trace along the complex building. So upper shape works very good. Modified convex hull algorithm has a problem here because it's very difficult to identify inner polygon. So this is the main drawback of modified convex hull.
23:24
So our approach is to mix use these two. A grid-based works fine, but as I said, rasterization loses some information. And therefore, in terms of spatial accuracy,
23:45
grid-based doesn't perform well compared to other two algorithms. Again, we tested our research. We assessed the accuracy, the horizontal RMSE of eight different buildings
24:05
across the campus. Upper shape gave us 74 centimeter accuracy on the average. And modified convex hull is similar to upper shape.
24:20
So our choice is the two. And the grid-based was the worst among three. But it's not far from other two. It's very close to other two. We tested our algorithm on other data sets.
24:43
As I said, UNSW campus is very challenging area because it contains all different types of buildings and vegetation. Perhaps building extraction is popular in urban areas. So we applied our algorithm to urban setting.
25:03
And we choose two different sites in typical residential areas. And the algorithm works very well. On our site gave us good results.
25:20
I think the main challenge of this algorithm is how to separate two buildings in close proximity. If two buildings are too close to each other, if the gap between the two buildings is about one meter or two meters,
25:40
then we don't have enough point density. So what we have to do is just increase the point density of L1 Lidar data, then it'll work. But our temporal solution to remove to avoid this challenge is that
26:03
we apply windows horizontally and then vertically. So we try different directions and take the intersection of the two. Then it gives us better results.
26:21
The statistics of these two sites is that while in Lidar classification we have three different statistics, the completeness and correctness and quality. And we tried three different measures to assess our test results.
26:41
And the site one, the completeness is about 96%, and site two is about 94%. So it's over 90%. And correctness one is 98, and the other is 93.
27:00
But in terms of quality, quality means we compare the commission error and omission error. So in terms of quality, the site two gave us some poor results. It's almost, it is around 88%. So we are not satisfied with these results, which means we need to do something more
27:22
to improve our algorithms. So my concluding remarks are, the proposed algorithm is suitable for steep urban areas with varying building sizes. It works for commercial properties
27:40
and commercial properties. Our algorithm requires some parameters, but those parameters are automatically determined. It is adaptive filtering, and the test results show that the proposed algorithm is able to classify ground points with a vertical accuracy of 36 centimeters.
28:03
It's quite good, about 36 centimeters. But horizontal accuracy is about 75 centimeters. But I think it is understandable. It is well-known fact that a lot of data has a better accuracy in terms of vertical measurements rather than horizontal measurements.
28:22
So horizontal accuracy is lower than vertical accuracy when you look at a lot of data. So this is understandable figures, and our commission error is less than 6%. And as I mentioned before, the multi-loof top buildings,
28:41
or two buildings are close to each other, then it's a bit difficult to determine the actual size of building. But we tackle this problem by applying the algorithm in dual directions. But I think one of the easiest solutions
29:01
is to increase the point density. That'll solve this kind of problem nicely. I think that's it. Thank you very much. Do you have any questions?
29:22
Yes. I have a question. You just, let's use a mic. I was just wondering, you're just working 2D. You're not trying to determine the height of the buildings. We use elevation and intensity. So it's kind of 4D, if you will.
29:42
But you just, when you showed the results, it was just in 2D. You know the shape of the building, not how high it is. Because you could do that with the ground model. You are correct. The boundary itself is extracted in 2D, but the building heights are stored in LiDAR data.
30:01
So we can just extrude 2D building outlines to 3D. But you will have a flat roof, not shaped. Yes. Yeah, I think that's a very good comment. Because we have, I think the most challenging area
30:21
is dome-type shape. If you look at the campus, those buildings are rectangular or square, but this one, this is around the house. And it is like a dome-type building. So for this kind of round building,
30:44
what we got at the end of building detection, building boundary detection is just outside polygon. That's it. Okay. Any other questions from the audience?
31:07
Okay, thank you very much. Let's move on to the next speaker.