) ON
ROC.
data densely
des abundant
jc. The sub-
e first step in
1 to split and
clusters and
d analysis of
ult shows the
both kind of
NTATION
loud into 3D
n the octree
| à root node.
spaces, if the
old. The split
> split spaces.
> scan points
ributed close
(b) the tr
Cc
a
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
2.2 Calculating best-fit planar of point cloud
The best-fit plane in each sub-node is determined using least-
squares estimation, i.e.j minimizing the squares sum of the
distances from points to the fitting plane. In the 3D Euclid
space, a 3D plane can be formulated as follows:
Ax t By Cz DzO (1)
z^ ; d. = T : P NV
l'he distance ( ^/) from the i" point 4,271)
can be expressed as:
to the plane
dim ado, x CR
Poo eB uc (2)
€
Then, the best-fit condition of minimizing the squares sum of
the distances will be:
N
Nd => min
z (3)
Eq. (2) is non-linear, so that it needs initial approximation
values of the unknown parameters (A, B, C, D) for the
calculation of least-squares estimation. To solve this problem,
we use a two-stage calculation to determine the unknown
parameters.
At first stage, a 3D plane is formulated as a slope-intercept form,
which has 3 types as Eq. (4):
x=ay+h+ce
y=ax+bz+c
z=ax+by+c (4)
To avoid the situation of obtaining infinite numbers for a and b
parameters, which slope-intercept form is suitable can be
predetermined according to the distribution ranges of the point
cloud. Figure 2 shows the idea. The outer frames in Fig. 2
represent the sub-node spaces, and the inner frames represent
the distribution ranges of the point cloud. The decision can be
done by checking the minimum distribution range. For example,
if x dimension has the minimum distribution range, then the
first type is the choice.
T =
#
4 /
Y A a dii
X [I all
X-Range=Min Y-Range=Min Z-Range=Min
‘
| | |
Plane type 1 Plane type 2 Plane type 3
x=ayv+hz+e o ymedxtbz-kc- zeaxtbyee
Figure 2. The ideas of selecting a suitable slope-intercept form.
Because the slope-intercept form is linear, the parameters can
be calculated without the need of iteration. The least-squares
linear regression can be applied to determine the plane
parameters. For example, if the slope-intercept form,
X=ay ZC : i S oil
y +bz+e , is used, the matrix form of the observation
equations can be listed as follows:
309
Fus A Ami]
| v, |y, 2 | a| |"
| M=|M M M »|-| M
y ? =, 1c N (5)
(6)
The calculation in this stage actually is to minimize the squares
sum of the x ranges from points to the fitting plane rather the
perpendicular distances. After the parameters are determined,
the x range residuals can be calculated. Split will proceed
continuously if there is a residual larger than the preset
threshold, otherwise rigorous calculation of the second stage
will be triggered.
Eq. 2 is applied for the rigorous calculation. Given the solution
in the first stage as the initial approximation, the rigorous
adjustment is performed iteratively. Following the use of the
slope-intercept form, Eq. 2 can be reformed as:
ds Fa. b.c) - je, +ay, DZ, + d
NED +a xb (7)
The observation equations can be obtained by linearizing Eq. 7:
(8)
; a, Ab, Ac F
In Eq. 8, the parameters ^ AD. AC sre increments of unknown
parameters. The increments will be added into the previous
approximations until the calculated increments get to very small.
The best-fit plane is determined if the computation converges.
The distance residuals can be calculated after the parameters are
solved. Again, split will proceed continuously if there is a
residual larger than the preset threshold, otherwise a plane is
formed.
2.3 Area of the point cloud on a fitting plane
The point cloud in a sub-space may not distribute evenly on the
sub-node. In order to find a suitable node size corresponding to
the distributing of point cloud, area of the point cloud is
checked for further splitting. For example, area of unbalanced
distributing points in Figure 3 is smaller than the area of face of
sub-node. Split can proceed further, until the area of
distributing points on each fitting plane is larger than a preset
threshold.
"e.
ó :
lee o)
e
Figure 3. An example of unbalanced distribution of points
Point cloud of each best plane in sub-node is than searching its
boundary and building its TIN for visual purpose. Figure 4 is
the example of source lidar points cloud before split. Figure 5 a,
