XIX-B3, 2012
SING
.edu.tw
cu.edu.tw
ing. In the last two
-driven and model-
is used thresholds,
canning rates have
| elevation analysis
contains two parts:
r generating digital
] its original three-
> topology of local
cations have small
roach, TEA can be
d with those of the
bint clouds.
cesses partition the
vith the designed
0 be successfully
, these designed
onsidered building
iven approach, the
yze the point cloud
ies. Many studies
ding the Hough
ANSAC) (Fischler
| (BSP) (Sohn and
>u and Vosselman,
ientation algorithm
reshaping (TMR)
Xd (Kim and Shan,
approaches can be
uds for modeling.
/zed under several
ifferences, shapes,
1, coplanar points
and calculate the
Nevertheless, these
nilding surfaces by
. The problematic
of segmentation
old determination.
t-processing have
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume XXXIX-B3, 2012
XXII ISPRS Congress, 25 August — 01 September 2012, Melbourne, Australia
Based on the geometric characteristics of a building's roof,
LIDAR points located at the building boundaries have greater
elevation differences. Additionally, these boundary points have
explicit permutations that follow the roof shape. For this spatial
phenomenon, this study proposes using topological elevation
analysis (TEA) to identify the structure lines instead of
threshold selection. This topological analysis concept was
originally developed to detect edges for grayscale images (Lo
and Chen, 2011). TEA then extends their concepts to manage
point clouds.
Because the analyses of spatial relation between each point may
need mass computation, many previous studies indicate that to
convert point clouds into grid format can enhance speed for
detection process (Cho et al., 2004). However, the traditional
rasterization may disturb elevations due to interpolation
processes. To avoid information loss, Cho et al. (2004)
proposed a pseudo-grid concept to assign the original elevation
to each grid from raw data without interpolation. The grid
spacing can be calculated from the average point density of
LIDAR data. Based on this merit of pseudo-grid, TEA
implements two steps to hierarchically handle point clouds for
structure line detection. In the first step, TEA generates pseudo-
grid digital surface models (PDSMs) using the highest point of
each grid. Topological permutations of the elevation differences
are then analyzed to identify local extrema for grid-based line
detection and produce an index map. According to this index
map, the second step employs point clouds to calculate three-
dimensional structure lines. For evaluation, the preliminary
results are compared with those of the octree-based split-and-
merge segmentation algorithm (Wang and Tseng, 2010) to
assess the relative accuracy and evaluate the applicability of the
proposed method.
2. METHODOLOGY
To identify three-dimensional structure lines using point clouds,
the topological relationship between each point must be first
established. Considering the characteristics of local relief, this
study proposes three major concepts: (a) possible locations of
structure lines may contain significant elevation differences in
the circular direction and small elevation differences in the
radial direction; (b) one structure line can be formed by several
basic elements in a three-by-three area; and (c) the basic
elements may have specific permutations. Figure 1 shows the
three-step workflow developed based on the proposed concepts,
that is, (1) pseudo-grid generation, (2) structure line detection,
and (3) line formation. In the proposed scheme, TEA used two
thresholds to identify grid-based lines including the grid
spacing and the minimum elevation difference. The grid
spacing can be derived from the average point density. The
elevation constraint for estimation of minimum height jump is
regarded as a constant in the processes.
141
Pseudo-grid
Generation
i
Structure Line
Detection
3D Line Formation
3D Structure Lines
Figure 1. Workflow
2.1 Pseudo-grid rasterization
Because the laser scanning system blind detects the geometry of
objects with dense point clouds, the resulting data lacks
information of the correlations between each point. In addition,
the point density is associated with the computation. Greater
point density can delineate detailed information, but it also
increases the computation required. To resolve this issue, this
study generates a PDSM to preserve the original elevation
information. TEA is employed instead of mathematical
interpolation to compare the point elevations and identify the
highest elevation in each grid. After pseudo-grid generation, the
PDSM provides the original elevation information for further
elevation analysis.
2.2 Structure line detection
During the second step, topological permutations of the
elevation differences are estimated for line detection. Local
elevation distribution is considered to identify the structure line
positions without threshold selection. Following the major
concepts, the generated unit of TEA is shown in Figure 2.
According to the characteristics of linear geometry, the
elevation differences in the circular direction may exceed the
differences in the radial direction for each grid (Figure 3) (Lo
and Chen, 2011). To formulize this phenomenon, TEA employs
two equations to represent the two-direction analyses.
RC, =C.-T (2)
ce = IC. = Ca 3)
where RC; is the elevation differences in the radial direction,
and CC; is the elevation differences in the circular direction.
Sample
Ce | © | Ca
C; Cs
CI CSIC,
Line
Figure 2. Kernel illustration
