The 2D Fretsaw Algorithm takes advantage of the fact, that the distance between two points is smaller on a smooth surface (for example a wall) than it is on vegetation.
The precondition for the 2D Fretsaw Algorithm to work is like in the Chainsaw Algorithm, that the measurement points are sorted in a 2D-tree. The 2D Fretsaw Algorithm searches for the nearest neighbor of a point P(i) and calculates the height difference (z-axis) between the two points.
After calculating the height differences between all points inside a given patch, the height differences are summed up and divided by the number of points inside the patch to get the average distance H between the points.
If H overcomes a certain distance, specified by the user, the value of the height above which the points will be deleted is lowered.
We decided to use the height difference instead of the euclidean distance as this has no effect on the result: The height differences as well as the euclidean distances are greater on uneven surfaces.
Note that the algorithm searches the nearest neighbor using the 2D tree.
The steps of the 2D Fretsaw Algorithm:
for all points in a circle: calculate the average height distance H between the points:
a) search for the nearest neighbor (2D) 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 2D Fretsaw Algorithm
The gradient of the ground can be falsely considered as vegetation as its scan points have increased height differences between nearest neighbors.
Also it may occur that the nearest neighbor in the two dimensional projection of the points is far away in the third dimension (see picture), especially in fragmented scans.
An improvement is accomplished with the 3D-Fretsaw-Algorithm.