ISPRS Commission III, Vol.34, Part 3A „Photogrammetric Computer Vision“, Graz, 2002
number of range points c,. The grid pixels are regarded as
having vertical volume if they satisfy the following conditions.
(z-z)»T ande >1 (1)
Where T. and T, are experience values. In addition, grid pixels
are segmented by region growing, where each pixel is assigned
to one of two states, i.e. 0 if c, -0 and 1 if c, 70. The grid pixels
belonging to a region that larger than a given threshold are
regarded as having horizontal volume. The scatter points that
belonging to a grid pixel of both horizontal and vertical volume
are extracted as the measurement of volume-structured objects.
4. VOLUMETRIC MODELING AND MARCHING
CUBE
One of the key issues of generating an implicit surface using
volumetric modelling and marching cube method is to calculate
the signed distance d from the centre point of each voxel y,
to the isosurface. The sign of d, indicates the state of y. i.e. it
is invisible from all viewpoints if d, >(), it is visible from one
of the viewpoints if d, <0, and it is on the iso-surface if d, =.
Hoppe, et al 1992 performed a search for the closet point to a
voxel's centre, while Wheeler et al.1996 generated triangular
meshes using the connectivity of structured data, and calculated
the signed distance from the centre of each voxel to the closest
triangular surface. Curless and Levoy 1994 calculated the
weighted signed distance of each voxel to the nearest range
surface of a single range view along the line of sight. The
weighted average of all these measures is exploited as the
signed distance estimate to the integrated iso-surface.
The surfaces of urban outdoor objects are always not
continuous ones. There might be window frames, rain pipes,
cables on a planar building surface. There might be pavement,
road guild on a road surface. The local surface normal
calculated using the neighbouring range points might not really
reflect the implicit surface that are of interest. In this research,
range points are treated as independent and unorganized points.
Extraction of iso-surface is conducted for surface-structured
objects, i.e. vertical (building) surfaces, windows, road surfaces
and other surfaces, and volume-structured objects, e.g. trees
separately.
4.1 Iso-surface of surface-structured objects
A range measurement x from viewpoint o(x) tells that there is
nothing in the extent of laser beam between o(x) and x, there are
something at x, and the extent far from x is unknown. On the
other hand, a point c is visible from o(x), if and only if it is in
the extent of laser beam between o(x) and x. It is invisible from
o(x) if and only if it is in the extent far from x. As the range
measurement in our research is a point sampling of the
surroundings with a vertical angular resolution (vres=0.25 )
and a horizontal spatial resolution (hres 0.1m), measurement
extent of a laser beam is considered as a compound of a circular
cone and a cylinder as shown in Figure 4, where radius of any
circular section of the compound structure is defined as follows.
R = max (r*tan(vres), hres) 2)
Where, r is the range distance from o(x) to the circular section.
According to marching cube algorithm, an edge is intersected
by the implicit iso-surface, if and only if the two terminal points
(centre points of neighbour voxels) of the edge are in different
states. Thus, instead of the signed distance estimate, in this
research, we first calculate the state of all voxel centres, then
calculated the intersection points on the edge that bridging
different states.
Extent of the measurement
Laser beam
Figure 4. Laser beam and its measurement extent
Computation of point state: Theoretically, if c is visible from
one of the viewpoint, it is outside of the surface. If c is invisible
from all of the viewpoints, it is inside of the surface. Let S. be
the sign of c, where, S. —-],1,0 indicates c inside, outside, and
on the object surface. S. is computed as follows, where E, isa
predefined value indicating the order of range error.
Algorithm ComputeState
Input: c
Input: the set of all range points X = {x}
Output: S.
Se]
For xe X
y, €- c- o(x).V, € x—-o(x).r.(x) € V,-V,
d. (x) «€ VI, : -rx) ,
R, (x) « max(r, (x) x tan(vres), hres)
If 4. (3) 2 R (x)
If | r. (x) - r(x) |« E, then S, —0
Else if r(x)«r(x) then § «1
Return S,
Computation of edge intersection point: Suppose the centre
points e of voxel V, and 6 of V, are of different states. The
intersection point p, on edge Tc 6;) by the implicit iso-
surface is calculated as follows, where d; (x) 1s the orthogonal
distance from range point x to edge Ble,.c,) > Ps (x) is the
corresponding orthogonal point.
z. SE En I 74
va AH
festen f!
(Cie | ° voxel
1 1
Range : udo :
: 70399 9 e A '
points NA ‚er og ei |
3}
Kl
ij A
v be : voXel ;
1 1
1 1
Figure 5. Edge intersection point
A - 415
