XXIX-B3, 2012
ixels)
1at
ANSAC
|
extraction.
nage is interpolated
ends on the density
fies neighbourhood
zes algorithm time
ied out by region
els associated with
ocess we obtain not
erformed in other
stituting individual
on about buildings
e performance of
sification errors that
. As the output, the
building clusters
, a building cluster
which are adjacent
ve outliers, detected
oud, which is then
rmal vectors and
' image, they can be
constitute building
cels are detected by
utation is executed
ision of extracted
erpolation.
provided by laser
he original LIDAR
nore than one point
oints (projected on
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
the plane) that make up the outline contaminated by outliers.
Thus, similar to Neidhart and Sester (2008), straight lines
detection is performed by Random Sample Consensus
(RANSAC) (Fischer and Bolles, 1981). The algorithm enables
to estimate the parameters of a model in a noise data set. Each
set of building boundary points is processed separately. First,
the hypothesis is advanced based on the line equation computed
from the two randomly chosen points. The hypothesis is tested
by checking all the points from the data set. If they nearly lye on
the candidate line, the points are added to the consensus set.
The accepted distance from the point to the line is equal to the
double point spacing. The hypothesis is accepted when the size
of the consensus set exceeds predefined threshold. The line
equation is updated using all the points that fit to the line. They
are stored as a boundary line segment and excluded from the
data. Then, the whole process is repeated in order to detect the
next line segment. The algorithms stops when there is no line
composed of required number of points.
The boundary lines are detected based on their equations.
Therefore, non-adjacent segments on the both sides of
buildings’ protrusions or insets are merged together. According
to above, modifications of the algorithm are required in order to
disjoint non-adjacent segments that feature the same line
equation. Depending on the connectivity threshold (the
accepted distance between the subsequent points within one line
segment) erroneous connections are eliminated and the line is
divided into new, shorter intervals. The line parameters are
updated based on the new set of points. The result of boundary
lines detection algorithm is presented in Fig. 2c.
2.3 Outline improvement
The outlines provided in the previous step are composed of
unstructured line intervals. In order to produce realistic building
shapes, the boundaries have to be simplified, appropriately
merged and ultimately, adjusted. The first task — line
simplification — starts with determination of the sequence of line
intervals within the building boundary. Each interval is assigned
to a set of points, hence, we can easily determine the two
opposite points with the maximum distance from the interval
gravity centre. In order to establish topology relation between
all such points, a binary search tree is generated. Based on the
closets neighbours of their end points, line intervals are ordered
clockwise and enumerated. Once the line topology is
established, consecutive lines are investigated for their mutual
orientation. Nearly parallel segments are joined, thus, reducing
the number of lines that determine building outlines. According
to the settled threshold (depended on the desired generalization
level), generalization process reduces unwanted small details in
the boundary and maintains the basic essentials of shape.
The next part consists of segments merging and lines
adjustment. The process is based on the main orientation, which
is determined by the mean direction calculated from the longest
building segments. Each segment gets parallel or rectangular
label with respect to the difference between its own direction
and the main orientation. The consecutive lines are investigated
in order to find potential gaps within the contour. The gaps are
detected when the two following lines get the same label. With
respect to the distance between their end points, the lines are
either merged or separated by the new, perpendicular interval.
The interval is inserted halfway between their ends. In the next
step line equations are adjusted in order to form regular
building outlines. According to the segments’ label,
rectangularity or parallelism constraint is enforced. The
adjusted lines shorter than assumed generalization threshold are
121
removed from the contour. The final results of boundary
regularization is illustrated in Fig.2d.
Each line of a contour is either parallel or rectangular to the
main direction. This assumption is motivated by the fact that
buildings mainly consist of parallel and rectangular facades.
Although the presented algorithm gives very precise results in
the most cases, it fails when adjacent buildings create the
boundary shape with any possible variety of angles. Thus, in
order to improve the implementation additional research on that
task will be necessary.
Figure 2c. Set of refined straight lines resulting from the
modified RANSAC algorithm
ae
Figure 2d. Building boundaries after regularization.