Point cloud modelling with the 3D Medial Axis Transform


Point cloud modelling

Through point clouds we can obtain dense and accurate representations of real-world objects and landscapes. If we merely look at a visualisation of this point cloud, already a great deal of information is conveyed to us. We can easily recognise different objects and measure distances, areas, and volumes.

Yet to a computer a point cloud is nothing more than a bunch of 3D coordinates, without any structure or semantics. If we want a computer do the same things, we need to first structure the point cloud in a way also a computer can efficiently make use of it.

In the 3DSM project we aim to find 3D methods and datastructes that make it easier to work with pointclouds. By achieving this we enable a number of key applications of point clouds such as point cloud visualisation, visibility analysis, automatic object detection and surface reconstruction.


3D Medial Axis Transform (MAT)

The MAT represents the shape of an object, in 2D or 3D, with balls contained inside it, and should be seen as the skeleton of an object. Given an object, it is an alternative representation that captures both the shape of the object and its topology (how its different parts are connected), and has therefore been used in numerous shape-related problems.


MAT for point cloud modelling

The general idea of the project is to process point clouds not by manipulating the surface points, but rather by working on its MAT. While the MAT contains the same information as the conventional 'surface points' (i.e. the input point cloud), it models key properties of a shape in a much more explicit way. The key benefit of the MAT here is its skeleton-like and explicitly topological representation. Using this skeleton we can easily isolate distinct object from the point cloud and remove them for instance. This is possible because we always keep the link to the surface points while we work with the MAT.

Generic placeholder image

Generic placeholder image

Case studies

An important part of this project is to demonstrate the viablity of the MAT for a number of real-world applications and by using real-world datasets. We have identified the following case studies:

  • Point cloud visualisation and simplification
  • Building detection
  • Watercourse detection
  • Visibility analysis
  • Surface reconstruction

Open-source software

We will release all the code that is developed for this project as open source software. As of today not everthing is published yet. However, the core algorithm that we use to robustly compute the 3D MAT of point clouds is already available:


Funding

3DSM is a research project funded by the Netherlands Organisation for Scientific Research (NWO) under the Open Technology programme.

NWO logo

Publications

2017

Automatic identification of watercourses in flat and engineered landscapes by computing the skeleton of a lidar point cloud. Tom Broersen, Ravi Peters and Hugo Ledoux. Computers & Geosciences 106, 2017, pp. 171–180.
PDF DOI BibTeX
@article{Broersen17,
	author = {Tom Broersen and Ravi Peters and Hugo Ledoux},
	journal = {Computers & Geosciences},
	pages = {171--180},
	title = {Automatic identification of watercourses in flat and engineered landscapes by computing the skeleton of a LiDAR point cloud},
	volume = {106},
	year = {2017}
}

2016

Robust approximation of the Medial Axis Transform of LiDAR point clouds as a tool for visualisation. Ravi Peters and Hugo Ledoux. Computers & Geosciences 90(A), March 2016, pp. 123–133.
PDF DOI BibTeX
@article{Peters16,
	author = {Peters, Ravi and Ledoux, Hugo},
	journal = {Computers \& Geosciences},
	month = {mar},
	number = {A},
	pages = {123--133},
	title = {Robust approximation of the {Medial Axis Transform} of {LiDAR} point clouds as a tool for visualisation},
	volume = {90},
	year = {2016}
}
Creating the medial axis transform for billions of LiDAR points using a memory efficient method. Marco Lam. Master's thesis, MSc thesis in Geomatics, Delft University of Technology, 2016.
DOI BibTeX
@mastersthesis{Lam16,
	author = {Lam, Marco},
	school = {MSc thesis in Geomatics, Delft University of Technology},
	title = {Creating the medial axis transform for billions of {LiDAR} points using a memory efficient method},
	year = {2016}
}
Automatic identification of water courses from AHN3 in flat and engineered landscapes. Tom Broersen. Master's thesis, MSc thesis in Geomatics, Delft University of Technology, 2016.
DOI BibTeX
@mastersthesis{Broersen16,
	author = {Broersen, Tom},
	school = {MSc thesis in Geomatics, Delft University of Technology},
	title = {Automatic identification of water courses from {AHN3} in flat and engineered landscapes},
	year = {2016}
}

2015

Visibility Analysis in a Point Cloud Based on the Medial Axis Transform. Ravi Peters, Hugo Ledoux and Filip Biljecki. Eurographics Workshop on Urban Data Modelling and Visualisation 2015, Delft, Netherlands, November 2015, pp. 7–12.
PDF DOI BibTeX
@inproceedings{Peters15,
	address = {Delft, Netherlands},
	author = {Peters, Ravi and Ledoux, Hugo and Biljecki, Filip},
	booktitle = {Eurographics Workshop on Urban Data Modelling and Visualisation 2015},
	month = {nov},
	pages = {7--12},
	title = {{Visibility Analysis in a Point Cloud Based on the Medial Axis Transform}},
	year = {2015}
}
Het 3D skelet van een puntenwolk. Ravi Peters. Presentation at the AHN/NCG studiemiddag (Amersfoort, the Netherlands), Januari 28 2015.
PDF BibTeX
@misc{15_ahn_studie_middag,
	author = {Ravi Peters},
	howpublished = {Presentation at the AHN/NCG studiemiddag (Amersfoort, the Netherlands)},
	month = {Januari 28},
	title = {Het {3D} skelet van een puntenwolk},
	year = {2015}
}

2014

A Voronoi-based approach to generating depth-contours for hydrographic charts. Ravi Peters, Hugo Ledoux and Martijn Meijers. Marine Geodesy 37(2), 2014, pp. 145–166.
PDF DOI BibTeX
@article{Peters14,
	author = {Peters, Ravi and Ledoux, Hugo and Meijers, Martijn},
	journal = {Marine Geodesy},
	number = {2},
	pages = {145--166},
	title = {A {V}oronoi-based approach to generating depth-contours for hydrographic charts},
	volume = {37},
	year = {2014}
}
Feature aware digital surface model analysis and generalization based on the 3D medial axis transform. Ravi Peters. PhD research proposal GISt Report No. 65, Delft University of Technology, 2014.
PDF BibTeX
@techreport{14phdproposal,
	address = {the Netherlands},
	author = {Ravi Peters},
	institution = {Delft University of Technology},
	number = {GISt Report No. 65},
	title = {Feature aware digital surface model analysis and generalization based on the {3D} medial axis transform},
	type = {PhD research proposal},
	year = {2014}
}
Approximating the medial axis transform of LiDAR point clouds. Ravi Peters. Poster at the Lorentz workshop on geometric algorithms in the field, June 2014.
PDF BibTeX
@misc{14_lorentz_poster,
	address = {Leiden, the Netherlands},
	author = {Ravi Peters},
	howpublished = {Poster at the Lorentz workshop on geometric algorithms in the field},
	month = {June},
	title = {Approximating the Medial Axis Transform of {LiDAR} point clouds},
	year = {2014}
}
Towards Medial Axis-based simplification of LiDAR point clouds. Ravi Peters. Presentation at the iQumulus workshop (Cardiff, United Kingdom), July 8 2014.
PDF BibTeX
@misc{14_iqmulus_workshop,
	author = {Ravi Peters},
	howpublished = {Presentation at the iQumulus workshop (Cardiff, United Kingdom)},
	month = {July 8},
	title = {Towards {M}edial {A}xis-based simplification of {LiDAR} point clouds},
	year = {2014}
}
Feature-aware LiDAR point cloud simplification. Ravi Peters. Poster at the GeoBuzz conference, November 2014.
PDF BibTeX
@misc{14_geobuzz_poster,
	address = {s'Hertogenbosch, the Netherlands},
	author = {Ravi Peters},
	howpublished = {Poster at the GeoBuzz conference},
	month = {November},
	title = {Feature-aware {LiDAR} point cloud simplification},
	year = {2014}
}
MATAHN: a seamless AHN2 download service. Ravi Peters and Hugo Ledoux. Presentation at the 3D BGT dag (Amersfoort, the Netherlands), June 19 2014.
PDF BibTeX
@misc{14_3dbgtdag_matahn,
	author = {Ravi Peters and Hugo Ledoux},
	howpublished = {Presentation at the 3D BGT dag (Amersfoort, the Netherlands)},
	month = {June 19},
	title = {{MATAHN:} A seamless {AHN2} download service},
	year = {2014}
}

2013

Generation and generalization of safe depth-contours for hydrographic charts using a surface-based approach. Ravi Peters, Hugo Ledoux and Martijn Meijers. In D. Burghardt (eds.), Proceedings 16th ICA Generalisation Workshop, Dresden, Germany, 2013.
PDF BibTeX
@inproceedings{Peters13,
	address = {Dresden, Germany},
	author = {Peters, Ravi and Ledoux, Hugo and Meijers, Martijn},
	booktitle = {Proceedings 16th ICA Generalisation Workshop},
	editor = {D. Burghardt},
	title = {Generation and generalization of safe depth-contours for hydrographic charts using a surface-based approach},
	year = {2013}
}

STW Users’ committee

Meeting 2017-07-04

Meeting 2016-11-09

Meeting 2016-01-19

Meeting 2015/05/19

Meeting 2014/09/11

Meeting 2014/01/23

Members

Company Name
Bentley Benoit Frédéricque
Gemeente Rotterdam Joris Goos
Sweco Marco Grimaudo
Kadaster Marc Post
Het Waterschaphuis Niels van der Zon
Rijkswaterstaat DVS René Visser
Safe Sotware Kevin Wiebe
Waterschap Scheldestromen Sicco van Mullem

Team

Ravi Peters PhD candidate

tudelft.nl/rypeters
r.y.peters@tudelft.nl