Navigation and Tree Measurement
The SLAM is based on the raw 2D laser scanner data.
The first step is the feature extraction. In this application,
the features are the surrounding trees. The tree features
identified from a single scan are called echoes due to their
uncertain nature. In a clean forest with little or no underbrush, it is a relatively simple task to find the tree trunks
from the raw laser scans. This is done in the second step.
An example scan and its segmentation are shown in
Figure 4. However, in more dense forests, finding the trunks
can be extremely difficult, if not impossible. The dense
vegetation drastically reduces the effective measurement
range. Even in relatively clean forests, the blind areas
behind the nearest trunks can be substantial.
Instead of trying to identify individual trees, it is better
to identify groups of trees. These groups are identified in
the third step. The tree groups offer a variety of features
that can be used for identification: distances and angles
between adjacent trees, and trunk diameters.
One of the central challenges in this approach is that
the tree groups are not constant. Depending on the current
FIGURE 4. The date of one laser scan in a forest
for which the tree segmentation is done.
position, not all trees may be visible. The matching of
echoes to the tree map is done in the fourth step. After the
echoes have been matched to the trees, a simple algorithm
is used to estimate the new pose.
First, the “centers of gravities” of both set of points are
calculated and the echo set is then translated so that the
CoGs coincide. Second, the average angle between all
echo-tree pairs is calculated and the echo set is then rotated
by this angle. Care should be taken that all the angles are
calculated on the correct cycle. This algorithm is based on
the realistic assumption that the subsequent scans differ
only by a translation and a rotation.
In the final phases, the echoes are projected to map
coordinates. At this point, they are classified either as new
or old trees. New trees are added to the tree graph and
diameter information is accumulated to the old trees.
The closer the scan is taken, the better the diameter
information. New edges are also inserted into the tree
graph and old edges are updated to reflect this. Currently,
only the distances between the trees are recorded but later
angles will be used, as well.
One of the problems of this algorithm is that it makes
the optimistic assumption that all echoes really are trees.
This helps the algorithm to acquire new trees and to keep
going, but if echoes of branches are falsely interpreted as
trees they will be added permanently to the tree map. To
solve this problem, another algorithm was added to remove
false positives from the tree map.
The algorithm works by projecting laser scans to map
coordinates and then using a collision detection algorithm
to find intersections between the “rays” and the trees in the
map. If there are more rays passing through a tree than
there are valid measurements of that tree, the tree is
removed from the map. This second algorithm was added
as an afterthought and it reflects the inability of the first
algorithm to record what is sometimes referred to as
negative information. Future improvements
of the algorithm may use local occupancy
grids to keep track of areas that are known
to be free of trees.
The calculation of the tree parameters
is divided into two consecutive phases. The
first part deals with the method used for
feature extraction in the measurement
data. The second phase contains the
determination of the midpoint location and
trunk diameter. These methods provide only
the relative location between the trees and
the measurement device.
The feature extraction can furthermore
be divided into two consecutive parts:
clustering and validation. A straightforward
clustering algorithm is used in this case
when the points representing objects are
easily distinguishable. The clustering
FIGURE 5. Tree map and the route
created by the SLAM algorithm.
48 SERVO 04.2009