International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
and elevation assessment and is implemented along the lidar
profile in two opposite directions. A local linear regression
along the lidar profile is then followed to further remove
possible non-ground points remained from the labeling process.
Tests over three urban areas with different complexity show
that over 96% of the lidar points can be correctly labeled. For
the details and the performance of the proposed approach we
refer to (Shan and Sampath, 2004). In the following studies, we
will use the building point clouds separated from this step.
3. BUILDING SEGMENTATION
Each of the lidar points that have been labeled as belonging to
building class through the previous step can only belong to one
single building. That is, there is a one-to-many correspondence
between the buildings and the 3D points, with each building
having many points and each point belonging to one particular
building. The Segmentation process assigns each point to a
unique building. A 3-D region growing algorithm, which starts
from a single point and successively collects points belonging
to the same building, is presented. This algorithm consists of
the following steps:
1) Start from a building point P ;
2)
Centre a 3-D window (cube) on the point and collect
all the points À = [D Pan } that fall within the
window.
3) Move the window to PD
4) Collect the points that fall within the window and
store them in a temporary set, say temp-
Points- {th 2 in : tP. Y.
5) Move to point R and place the window over it. Ap-
pend the newly collected set of points to the variable
tempPoints, and in the process making sure that no
two points are the same.
6) Continue the process till the window has been placed
over all the points PP 3 ES
7) Merge points in A and points in tempPoints and store
them in B. ie. B= {BU AUtempPoints}. Ini-
tially B is a null set.
8) Replace points in A with points in tempPoints such
that the newly populated set 4 is equivalent
to {AUtempPoints}.
9) Go back to step 3.
10) Stop when no new points are added to the set B.
In this way, the points in the building class are further seg-
mented into points belonging to individual buildings. The pro-
posed segmentation approach does not require any special data
structure. The initial input into the algorithm is a 3-D point
cloud, which is basically a set of X, Y and Z coordinates. Also,
the number of searches progressively reduces as more and more
points are assigned. Figure 1 shows a portion of the segmenta-
tion results over the test area, where different segmented build-
ings are color coded.
4. BUILDING BOUNDARY TRACING
Once each point has been mapped to a particular building, the
next step is to determine the footprint of the building. In this
section and the next, we explain a series of steps to
parameterize the edges of the segmented buildings as a series of
orthogonal straight lines. We call this step “regularizing”. Our
assumption here is that most buildings have only two mutually
perpendicular, dominant directions. In Figure 2, we
demonstrate the first step in regularizing the footprints, where
we determine points that belong to the outer boundary of the
building. In the second step, parametric lines are drawn to
represent the boundary edges of the building.
A convex hull algorithm, for a given set of points, determines
the smallest convex set containing the points. It can be regarded
as a rubber band wrapped around the set of points. To
determine the building boundary points, we use a modified
form of the convex hull algorithm. Figure 2 shows a convex
hull for the building points. Clearly, it does not represent all the
boundary points of the building, nor does it bring out the shape
of the building accurately. The algorithm determines the hull
points by selecting the left-most point and then successively
determining those points that make the least angle with the last
generated convex edge. To accomplish this, the algorithm
compares the slope of the last edge that is generated with lines
formed by connecting the current point with all the other
points.
Figure 2. “ Building points (left), convex hull around the
points (middle) and the actual boundary points (right)
To determine the boundary points for a building, we adapted
this algorithm. The steps are given below:
Intei
—
The
deter
probi
build
searc
thres
outlir
the r
that
prope
point
point
the d
to th
steps
algor
easy.
AS se
point:
most
mutu:
these
or the
all |
perpe
close
that t
the bi
buildi
deterr
based
buildi
regula
