In: Paparoditis N., Pierrot-Deseilligny M.. Mallet C.. Tournaire O. (Eds), 1APRS. Vol. XXXVIII. Part ЗА - Saint-Mandé, France. September 1-3, 2010 
Dividing NP by max(s 0 , <Jzl2) avoids a numerical overflow for 
very small values of s 0 and means that planes w ith s 0 < cr z /2 are 
effectively ranked by NP. The best plane is the plane achieving 
the highest value of the score function in Equ. 3. It is selected 
for further processing. 
2.3.2 Matching of Segments: The best plane was selected in 
one of the projected label images. Due to uncertainties of the 
DSM at step edges, the boundaries of the projected segment 
may not be represented w'ell. Thus, the original image segment 
corresponding to the plane is again projected into object space, 
this time using the adjusting plane to obtain the heights, so that 
the segment boundaries should be more precise. After that, we 
check whether all parts of the projected image segment receive 
sufficient support from the point cloud. Fig. 2 shows a situation 
that should be avoided: the segment only contains points in its 
left half, whereas there are no points in the right part. This may 
happen if a segment covers both a roof plane and a part of the 
ground, but has a good planar fit because only off-terrain points 
are used for determining the adjusting plane. Each point 
assigned to the plane is supposed to be representative for a 
circular area in the (2CT) plane w'hose radius r is chosen to be 
slightly (10%) larger than the average point spacing of the point 
cloud. Any pixel assigned to the segment that is further aw'ay 
than r from its nearest point is erased in the label image. This 
might split the segment into two or more parts; in this case, the 
largest part is maintained. Due to cutting off at a distance r from 
the nearest point, the boundary of the segment is not very w ; ell 
defined at the locations w'here it had to be cut off (Fig. 2). 
Figure 2. Left: A planar segment projected to object space. 
Red dots: points assigned to the plane. The circles 
are centred at the points and correspond to the area 
for which the point is representative. Right: the 
segment is cut off. 
Having thus improved the shape of the planar segment, the 
actual matching process is carried out. Matching candidates are 
searched for in each image except the one from which the 
segment was taken. Each valid plane found in any of these 
projected label images (cf. Section 2.3.1) that overlaps with the 
planar segment is considered to be a matching candidate. If a 
matching candidate and the segment to be matched are found 
not to be co-planar based on a statistical test, the matching 
candidate defines an area that should not be merged with the 
plane. All such areas are marked in a binary “non-co-planarity- 
image’'. Otherwise, the candidate is accepted if there are a 
sufficient number N OL of points that have been assigned to both 
planes; the latter criterion enforces that there are actually points 
that are co-incident with both planes. Once a candidate has been 
accepted, the original image label corresponding to the accepted 
candidate is re-projected to object space using the adjusting 
plane, and it is checked for support from the point cloud in the 
same way as the segment to be matched (Fig. 2). Matching is 
guided by an “overlap counter’’, i.e. an image that counts the 
number of overlapping segments at any position, including the 
segment to be matched and the accepted matching candidates. 
This overlap counter is initialised by the segment to be matched, 
and it is incremented at all positions covered by any matching 
candidate after re-projection to the adjusting plane. 
The left part of Fig. 3 show's the overlap counter for the best 
segment (segment B) in Fig. 1. The total number of overlapping 
images in this case is eight. There is up to five-fold overlap, 
partly also with relatively small matching segments. In the 
centre of Fig. 3, the non-co-planarity-image is showm. From 
these tw'o images, the final roof segment is generated. Firstly, 
all pixels covered by at least two segments are accepted (all 
except the red ones in Fig. 3). Pixels only covered by one 
segment (red pixels in Fig. 3) are only accepted if they do not 
belong to a non co-planar area (black pixels in the middle part 
of Fig. 3). Thus, multiple overlap can override the non-co- 
planarity criterion. Finally, binary morphological opening using 
a small square structural element is used to smooth the 
boundaries of the resulting segment (right part of Fig. 3). 
¿V 
Figure 3. Left: overlap count for the best planar segment 
(segment B) in Fig. 1. Red / yellow / green / blue / 
cyan: 1 / 2/ 3/ 4/ 5 overlapping segments. Centre: 
regions belonging to non-co-planar matching 
candidates (black). Right: final roof segment. 
2.3.3 Accepting the Matched Segment and Iteration: The 
segment generated in the way described above is added to the 
combined label image of planar segments, and the segment's 
point list is updated to contain all points within the segment that 
are coincident with the adjusting plane. After that, the plane 
parameters are recomputed. Finally, the area covered by the 
new segment is set to zero in the projected label images (cf. 
Fig. 4, left). After that, the procedure of determining the best 
planar segment, matching of planes and adding the resulting 
segment is repeated until no more segments can be found. 
Erasing the accepted segment may change the structure of the 
projected label images. Most importantly, image segments that 
spanned several roof planes in some of the images (which 
w'ould have resulted in a poor planar fit) may be separated in 
these images if the one of the roof planes could be detected 
based on another image at some stage in the iteration process. 
2.3.4 Merging Co-planar Segments: The generation of roof 
segments is terminated when no more planar segments having at 
least NP min points can be found in the data. The results of multi 
image segmentation are represented by the combined label 
image of all roof segments. This label image is analysed for 
neighbourhood relations, and planes found to be co-planar 
based on a statistical test are merged. As the order of merging 
has a significant impact on the merging results, neighbouring 
planes are merged in the order of the combined r.m.s. error of 
the planar fit. The central part of Fig. 4 shows the combined 
label image for the building in Fig. 1. The rightmost label image 
in Fig. 4 shows the results after merging of co-planar segments. 
2.3.5 Region Growing and Completion of the Segmentation: 
In case of large contrast variations in the images, smoothing 
w'ill have the effect that some larger roof planes may not be 
separable by multi-image segmentation. This is w'hy we check 
the point cloud for any planes that have been missed. For each 
off-terrain point not yet assigned to any roof plane we get its N„„ 
nearest neighbours in the point cloud. If neither of these points 
has been assigned to a roof plane, we determine the adjusting 
plane through these points and check whether it can be accepted 
as a plane in the way described in Section 2.3.1. If no plane is 
accepted, the process is terminated. Otherwise, the plane having 
248