ul 2004
| placed
1d store
+ dui
ts such
iivalent
er seg-
he pro-
ial data
D point
s. Also,
id more
"menta-
] build-
ing, the
In this
eps to
eries of
g^. Our
'utually
25 We
, Where
/ of the
awn to
ermines
egarded
nts. To
vodified
convex
t all the
e shape
the hull
'ssively
the last
oorithm
th lines
e other
und the
)
adapted
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
1) Start from an extreme point that is necessarily a
boundary point (say P).
2) Select all points that lie within a threshold distance
from this point, say Pfs — Ub Dilly he
threshold distance was the point density of the data-
set.
3) Determine the slopes of all the line segments that
connect the current point P, with the set of selected
points in Pts.
4) Determine the point D, in Pts which has the least
angle from the Y-axis.
5) Move to this point and consider this to be the next
current point P and determine the slope of the line
(say L. ) connecting this point with the previous
point.
6) Select all points that lie within the threshold distance
from P , determine the point/line segment which
makes the least angle with line L . Append this point
to the boundary point set and make this point the
new P .
e
7) Continue till the first selected point is reached.
The result is shown in Figure 2. Many algorithms that can
determine the convex hull of a give set of points exist. The
problem in directly applying the convex hull algorithm is that
buildings are not necessarily in convex. But, if we restrict the
search space of the algorithm to a smaller area, given by a
threshold distance, the algorithm will give us an accurate
outline of the border points on a building. As can be expected,
the result of the algorithm depends on the threshold distance
that is assigned in steps 2 and 6. This distance, in turn, is
proportional to the point density or the point spacing of the 3D
point cloud. In most point clouds, the distance between two
points lying on (or parallel) the X-axis will be different from
the distance between two adjacent points lying on( or parallel)
to the Y axis. Therefore the threshold distance mentioned in
steps 2 and 6 should be adjusted accordingly. The convex hull
algorithm is implemented as it is a well known algorithm and is
easy to implement as well as to adapt for our purposes.
5. BUILDING REGULARIZATION
As seen in Figure 2, the above steps give us a set of adjacent
points lying on the boundary of the building. Assuming that
most buildings have only two dominant directions that are also
mutually perpendicular, we can use the points to determine
these directions, and fit parametric lines that represent the edge
or the footprint of the building. As can be seen in Figure 2, not
all line segments that we obtain from lidar data are
Perpendicular. However, likely longer lines seem to be very
close to being mutually orthogonal. It is then safe to assume
that these line segments represent the dominant directions of
the building. These larger lines represent the basic frame of the
building footprint. This idea is the basis of our method to
determine the footprint of a building and a global solution
based on the least squares criterion is proposed to square the
building boundary so that the extracted buildings are
regularized.
There exists a one-to-many correspondence between boundary
edges and the boundary points. Each point lies on a single line,
unless it is a point that lies where two lines intersect. Based on
the assumptions mentioned above, the first step in regularizing
a building is to extract the points that lic on the longer edges of
the building. This is done by sequentially following the
boundary points, and looking for positions where the slope
between two consecutive points SE (PP. is different
frem( p. oa): The set of points is mapped to the line
segments (/1,/5,../,j Then, the longest set of these lines (e.g.,
dli t) were selected, along with their corresponding
sets of points, say
Ap y Pa Do Pob oe (DD uh
Then, the least squares solution for these lines are determined,
with the constraint that the slopes of these lines are either equal
(the lines being parallel), or their product is equal to -1 (in
which case, the lines are perpendicular). The solutions consist
of a set of parameters that describe each of the line
segments 11-44) . In particular, we have the following set
up for our building squaring problem. For each line segment,
Ax BN TIO i12.
| (1)
IzI0)-12..m,
l
where n is the number of line segments, m;is the number of
points on line segment /. Line segments of a building are
grouped based on their slopes. Lines that are parallel within a
given tolerance are sorted as one group with the same slope.
Let K be the number of parallel line groups, then lines in every
group should meet the following condition
A,
——+ M, =0 K= 12... K
B, (2)
Ss = s(k)=1,2,...., 7x
where M; is the slope of parallel line group k, ny is the
number of lines in the k-/ parallel line group. Similarly, for the
line groups that are perpendicular, we can write the following
condition equation
M,M,+1=0 u, V=1,2,3....,K: u >V. (3)
The least squares criterion is used to solve the above equation
systems. The unknowns include all the line segment parameters
A; and B; (i —1,2,..., n) , and the slope M, (k x 1,2,..., K) of
parallel line groups. In the current study, only two groups of
parallel lines, namely horizontal and vertical line segments are
considered. This leads to only one conditional constraint in
Equation (3).
To determine the parametric line segments, a hierarchical
approach is designed. This approach starts with relatively
longer line segments detected in the lidar points. In the next
step, relatively shorter line segments are introduced and their
parameters are determined based on the slopes of the line
segments obtained from the previous step, keeping in mind that
we consider only two possible directions for each line segment.
Figure 3 shows the determined parametric line segments for the
