




Automatic Detection and Elimination of Vegetation from 3D Laser Scan Data


Advanced Software Practical



The 3DFretsaw Algorithm
As a precondition for the 3D Fretsaw Algorithm the measuring points need to be sorted both in a 2D and a 3D tree. The 2D Tree is necessary to separate the data into 2D cells, the 3D tree is needed to find the nearest neighbor of a given point in 3D.
The 3D Fretsaw Algorithm is almost the same as the 2D Fretsaw Algorithm. Instead of the height differences between a point and its nearest neighbor in a two dimensional projection of all points, it searches for the nearest neighbor in 3D.
The steps of the 3DFretsaw Algorithm
 for all points in a circle: calculate the average height distance H between the points:
a) search for the nearest neighbor (3D) of point P(i)
b) measure the height difference H(i) between P(i) and its nearest neighbor
c) sum up all h(i) and divide by the number of points in the circle
 if H is higher than a user defined value, lower the threshold T
 delete all points above the threshold T
 go to the next cell, until all cells are examined.
Limits of the 3DFretsaw Algorithm
Like in the 2D version of the algorithm the gradient of the ground can still be falsely considered as vegetation, however it must have a much bigger uphill grade for an incorrect outcome of the 3DFretsaw. An other thing to mention is that an unexperienced user may have to run the algorithm several times to get a good result, because the threshold of the height must be estimated.






