Claus Brenner
+ j i i | "a k * I Kk. " =
D Bue oH RI id
0 1 2 3 4 5 6 7
Figure 5: The eight possible labels for junctions where 3 planes meet.
possible label (0) remains. Using the same argument, label 0 remains for junctions j»34 and j124 (Fig. 6(c)). However, in
the next iteration step, 234 and j124 cannot be connected on edge 4 — 2 since their respective arrows do not point towards
each other and no valid label remains for those junctions. Thus, in this case only by relaxation without any search, the
correct solution is found (j134 and j1»3 remain, both with label 0). Of course, in general, several solutions remain after
relaxation. A subsequent backtracking search with forward checking can be used to find them. Figure 7 shows results for
some cases.
63 Jaa Jos 64
J234 Ye Jy duas LU 412 hn
: : a 3
e,| Jm 4:25. | €2 e, a m e, x 1 e?
4 + 4Y2 ;
J124 1 J234
e, J14 e, J12 e,
(a) (b) (c)
Figure 6: (a) Rectangular ground plan and plane intersection points (junctions). (b) The connection from 714 to 134 leaves
only one valid interpretation. (c) Junctions 7934 and j124 cannot be connected and no valid label remains.
Toh ar
(b) | 364 (100%) 120 (100%) 220 (100%)
(c) | 63 (17%) 50 (42%) 63 (29%)
(d) 29 (8%) 31 (26%) 55 (25%)
(e) 48 65-727 887-67,848
(f) 5602 1647-168,085 269,837-795,654
Figure 7: Examples illustrating search space complexity. (a) Groundplans and all their possible roofs. (b) Total number
of junctions. (c) Number of junctions in ground plan P. (d) Junctions remaining after discrete relaxation. (e) Number of
search steps when using discrete relaxation (number range when there is more than one solution). (f) Number of search
steps without discrete relaxation.
3 HINTS FROM THE DSM
In the previous section, it was assumed that all roof faces have the same inclination. For the algorithms, however, this
is not necessary. Changing the inclination of some roof faces will change the topology of the associated graph G. For
example, depending on the roof inclinations, the ground plan of figure 6 has two possible associated graphs with junctions
{j134, j123} and {j124, ja34 }, corresponding to two ridge orientations. Would it be, then, possible to simply generate all
topologies, fit them to the DSM data (while checking that the fit does not violate the generated topology), and select the
one which meets some error criteria best? From the number of possible topologies, we can quickly see that this is no
sensible approach. As just seen, for N = 4 we obtain two solutions {{ÿ134, J123 }, {J124, j234 } }. For N = 5, there are
5 solutions {{j123, J134, J145}, {31233 J135; J345 }, {J124, J145, J234 }, {1253 J234; J245 }, {J125, J235; j345) ) and for N = 6,
14 solutions. In general, the number of solutions s(N) satisfies the recursion formula s(N) = s(N — 1) + s(3) - s(N —
2) + s(4)-s(N — 3) +... + s(N — 2) - s(3) + s(N — 1) with s(N) = 0 for N < 3 and s(3) = 1. It suffices to see that
s(N) > 2 - s(N — 1) and thus s(N) > 2Y73, ie. s(N) grows exponentially.
A more sensible approach is to obtain a first roof hypothesis from a reconstruction assuming identical roof inclinations. In
a second step, possible correspondences between the DSM and the reconstructed roof are established. From this, new roof
inclinations are derived and the roof reconstruction is repeated. This method has been presented in (Haala and Brenner,
1997). However, these approaches use the DSM only for measurement of heights and slopes, whereas the structure is
taken primarily from the ground plan. On the one hand, this is advantageous when the information content of the DSM is
rather low. On the other hand, the disadvantages are:
88 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.
