International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004 
  
of phase-difference laser rangers (Fröhlich et al., 2000). These 
points, but also points on leaves, which typically have no, or only 
a few neighbors on the same leaf, can be eliminated by removing 
all those points where the plane fitting accuracy is below a certain 
threshold. Choosing a threshold of 2cm reduces the number of 
points by a few percent only, removing points that are not suited 
for tree modelling anyway. 
3.3 Cylinder fitting 
Cylinders have 5 parameters: the radius is one parameter and 
the axis (a line in 3-dimensional space) has 4 parameters. It 
is, however, easier to use more parameters for the cylinder axis 
and introduce some conditions between those. The following 
parameterization of a cylinder is adopted: 
I(P — Qu) xal -r-0 Q) 
The symbol x denotes the outer product between two vectors and 
the symbol ||... || denotes the euclidian norm of the vector. In 
the above equation P — (x. yp, zp)! is a point on the axis, a = 
(315,35 za)! isa vector of unit length that points into the direction 
of the axis, and r is the radius. All points Qi — (zi, yi zi) 
fulfilling this equation lie on the cylinder. Demanding that a has 
length 1 and that P lies in a fixed, predefined plane reduces the 
parameters from 7 to 5 again. 
In order to fit a cylinder to a given number of points Qi;, 2 = 
1,...n, the unknowns (i.e. P,a,r) are determined by least 
squares adjustment. The residuals v; are the the distances from 
the measured points to the ideal cylinder: 
u = |(P- Qi xal -r 
As the problem is not linear the observation equations of the least 
squares problem are linearized and the adjustment is iterated. 
Approximation values are required for the parameters PC ad of 
the cylinder. The radius enters only linearly into the cylinder 
equation, and therefore no approximation is needed. An initial 
guess for the axis direction can be obtained from the normals 
estimated in each point. The normal vectors lie approximately in 
one plane, which is perpendicular to the cylinder axis a9. The 
point P? can be estimated from the center of gravity of the points 
Qi. A method for cylinder fitting without additional constraint 
equations is described in detail in (Lukacs et al., 1998). 
Typical accuracies achieved in cylinder fitting are in the order 
of +3cm. As for the normal estimation this value is below the 
accuracy of the laser scanner, but the rough surface of the tree, as 
well as the deviation of a real branch from a circular cross-section 
explain this difference. Fig. 2 shows an example of a cylinder fit 
to a set of points. The r.m.s.e. of the fit is £2.7cm, the cylinder 
radius is 29cm. 
Applying cylinder fitting to a point cloud, does not only determine 
radius and axis, but by projecting the given points to the axis, two 
outermost points can be identified, marking the top and bottom 
end (or start and end point) of the cylinder. 
3.4 Cylinder following 
Assuming that the axis direction and radius of a branch are known 
at a certain position, this branch can be tracked (in both axis direc- 
tions) in the given point cloud, using the cylinder fitting described 
above. The base cylinder is described by the known radius and an 
axis segment (i.e. the two axis end points). Shifting this cylinder 
forward (or backward) in the axis direction for a certain percent- 
age of its length, an approximate position for the next cylinder 
  
Figure 2: Cylinder fitted to 10600 points of a tree trunk in a 
perspective view. The cylinder is shown semi-transparent and its 
axis is drawn, too. Arrow 1 indicates one place where shadows 
of another branch between the scanner and the trunk caused oc- 
clusions. Arrows 2 and 3 indicate where systematic deviations 
from the circular form can be found (2: points inside cylinder, 3: 
outside). Fitting accuracy for this example is £2.7cm. 
is found. Points that are close (i.e. within a certain distance) to 
this new cylinder can be selected and used for cylinder fitting. 
If the parameters of the fitted cylinders are in accordance with 
quality criteria, the cylinder is accepted and tracking continues. 
If the cylinder does not pass the quality checks, another (e.g. a 
smaller) forward shift is applied, or a shorter cylinder can be used 
for selecting the points for the cylinder fitting. 
The method of cylinder following has many parameters, but given 
the domain of tree reconstruction, these values can be set easily. 
The measurement accuracy, the tree surface roughness, the curva- 
ture of branches, the change in radius along the axis, and finally 
the deviation of the circular cross-section guide the selection of 
the necessary threshold values. Values have been determined em- 
pirically and checked for compatibility to knowledge of forest 
experts. To account for gross measurement errors in the forest 
environment, these values must not be set too tight. 
For trunks, usually growing straight, the length ofthe cylinder can 
be set to 50cm. Smaller branches showing stronger curvatures 
require shorter lengths. Forward shift has been set to 30% of 
the length, which gives enough flexibility to adopt to the curved 
branch. If cylinder fitting is not accepted, shorter forward shifts 
(16%, ...) are tried first, assuming that a point set similar to 
the previously successfully used points will give better results. If 
these shifts fail too, longer forward shifts are tried (100%, ...), 
assuming that a major irregularity in the branch disables the good 
fit of a cylinder. If this fails too, cylinder following is stopped in 
this direction. 
Points being close to the shifted cylinder are selected for the next 
least squares fit. Closeness is determined in radial direction to the 
cylinder side surface, and good results have been achieved with a 
threshold value of 7cm, both for the inner and the outer distance. 
This corresponds to a 3c bound of the achievable fitting accuracy. 
Points lying inside this bound are counted, but not used for fitting 
of the cylinder. If the forward shifts are enlarged (e.g. 100%), the 
selection of points has to be made more generous, too, because 
of the unknown curving direction of the branch (e.g. 10cm for 
100%). 
   
Internationa 
CT CHLOE 
Figure 3: N 
segments a € 
and end poi 
segment (do 
used to dem 
Deciding if | 
of the fit (3c1 
(5cm-50cm) 
secutive cyli 
percent (e.g. 
within the cy 
sible measur 
points on the 
3.5 Segme 
The algorith 
the given pc 
surface and a 
algorithm fo: 
points are su 
the point cloi 
relevant bran 
Pfeifer, 2004 
into voxel s 
with matheir 
tree. Each sl 
a branch in « 
based on dist 
3.6 Cluste 
The cylinder 
precisely a s 
of axis poin! 
different pos 
mentioned al 
à severe pro 
makes sense 
but results on 
between two 
the combinec 
shifted apart. 
radius. In o 
the cylinder 
combined to 
collection of 
For this, a mq 
Given are tw 
Start and an « 
E, for axis a