The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B3b. Beijing 2008 
4. 3D ROOFTOP MODEL GENERATION 
4.1 Low Level Features Extraction 
To detect 2D lines from epipolar image, edge detection is 
carried out first and then 2D lines are formed from edges. We 
employed Canny edge detector, since it is optimal according to 
the criteria where edge is defined and comes up with thin edges. 
To obtain 2D line segment, we use Boldt algorithm (Boldt, 
1989) based on token grouping. The method extracts a basic 
line element, token, in terms of the properties of line A and 
construct 2D line using grouping process. It is efficient in 
detecting 2D lines of large structure appeared in urban image. 
4.2 Grouping and Filtering Processes 
Suspected building regions are used to remove line segment that 
outside or far from interested object boundaries meanwhile the 
needed line segments are still kept for later processing steps. 
Then, we group the closely parallel linear segments since they 
usually represent a linear structure of objects in image, like the 
border of a roof or the divider between ground terrain and 
building, by using a “folding space” between two line segments. 
If both line segments are inside the folding space, two line 
segments can be replaced by a single line which orientation is 
the longer line segment orientation and length is total length of 
two segments. After this process, each group of the closely 
overlapping and parallel line segments is represents only by one 
single line. 
4.3 Corner Detection 
Comer is calculated as intersection of two line segments which 
their angle is from 80° to 100° and one of them has nearest 
distance to another one. We define four types of comer. They 
are labeled as I, II, III and IV, as shown in Figure 4. Each 
comer has an attribute to indicate whether it is L-junction or T- 
junction. This attribute is used to decide whether two different 
comers have a connection or not. For example, if a comer’s 
label is I and type is L-junction, it connects to any type of 
comer. However, it prefers connecting to a comer which label 
is II or IV. If that comer is T-junction, it can only connect to a 
comer which label is II or IV. This mle is used in hypothesis 
generation to build collated features. 
With the flexible connection between comers, our method is 
able to detect rectilinear rooftops. Figure 5 show some 
examples of comer detection, A, B, E, F, G are L-junctions 
while C, D are T-junctions. 
II 
->111 
V 
IV 
Figure 2 showed the typical case of closely parallel linear 
segments grouping. These linear segments are or nearly parallel 
lines. So the first condition is the angle between them should be 
from 0° to 10°. If two line segments are fragmented lines from 
one edge, these line segments must be close and should be 
inside a folding space created by them. 
The U shaped structure in Figure 3 is used to detect candidates 
for rooftop hypothesis generation. Any line segment in a set of 
parallel lines with aligned end is a U shaped structure candidate 
which is kept as input for hypothesis generation, otherwise that 
line segment will be removed. 
Line formed Line segments 
Figure 2. Folding space 
Area searched fcr lines for forming 
the base of the U stricture 
z 
Figure 3 U-structure 
Figure 4. Comer labeling 
E 
F 
Figure 5. Comer detection 
4.4 Rooftop Hypothesis Generation 
A collated feature is a sequence of perceptually grouped comers 
and line segments. Here, collated features are constructed from 
filtered line segments and comers obtained from the filtering 
and grouping process. That reduces computational effort and 
false hypotheses. 
Hypotheses are formed by alternation of comers and line 
segments that form collated features. In a collated feature, two 
comers have connectivity only if they satisfy the comer relation 
condition and they are the nearest appropriate comer to each 
other. Beside, every comer connects to only one comer on each 
its line segment direction. Hypothesis generation is performed 
by constructing the feature graph. Construction of the graph can 
be seen as placing comers as nodes and edges between nodes if 
there is the relation between the corresponding comers in the 
collated features. When a node is inserted into the graph, the 
system looks into the remaining nodes whether any node has 
the relation with the inserted node. If some nodes satisfy the 
connectivity relation rules, those nodes are inserted into the