CMRT09: Object Extraction for 3D City Models, Road Databases and Traffic Monitoring - Concepts, Algorithms, and Evaluation 
In principle, formal grammars provide a vocabulary and a set of 
production or replacement rules. The vocabulary comprises 
symbols of various types. The symbols are called non-terminals 
if they can be replaced by other symbols, and terminals 
otherwise. The non-terminal symbol which defines the starting 
point for all replacements is the axiom. The grammar’s 
properties mainly depend on the definition of its production 
rules. They can be, for example, deterministic or stochastic, 
parametric and context-sensitive. A common notation for 
productions which we will refer to in the following sections is 
given by 
id : Ic < pred > rc : cond —> succ : prob 
The production identified by the label id specifies the 
substitution of the predecessor pred for the successor succ. 
Since the predecessor considers its left and right context, Ic and 
rc, the rule gets context-sensitive. If the condition cond 
evaluates to true, the replacement is carried out with the 
probability prob. Based on these definitions and notations, we 
develop a facade grammar P aiaJe (N,T,P,ao) which allows us to 
synthesize new facades of various extents and shapes. The 
axiom co refers to the new facade to be modelled and, thus, 
holds information on the facade polygon. The sets of terminals 
and non-terminals, T and N, as well as the production rules P 
are automatically inferred from the reconstructed facade as 
obtained by the data driven reconstruction process (section 2.2). 
2.3.1 Searching for Terminals 
In order to yield a meaningful set of terminals for the facade 
grammar, the building facade is broken down into some set of 
elementary parts, which are regarded as indivisible and 
therefore serve as terminals. For this purpose, a spatial 
partitioning process is applied which segments the facade into 
floors and each floor into tiles. Tiles are created by splitting the 
floors along the vertical delimiters of geometries. A geometry 
describes a basic object on the facade that has been generated 
during the data driven reconstruction process (section 2.2). It 
represents either an indentation like a window or a protrusion 
like a balcony or an oriel. Two main types of tiles can be 
distinguished: wall tiles, which represent blank wall elements, 
and geometry tiles, which include structures like windows and 
doors. All these tiles are used as terminals within our facade 
grammar. In the remaining sections of the paper, wall tiles will 
be denoted by the symbols W for non-terminals and w¡ for 
terminals. Geometry tiles will be referred to as G and g¡ in case 
of non-terminals and terminals, respectively. 
2.3.2 Interrelationship between Terminals 
Having distinguished elementary parts of the facade we now 
aim at giving further structure to the perceived basic tiles by 
grouping them into higher-order structures. This is done fully 
automatically by identifying hierarchical structures in sequences 
of discrete symbols. The structural inference reveals 
hierarchical interrelationships between the symbols in terms of 
rewrite rules. These rules identify phrases that occur more than 
once in the string. Thus, redundancy due to repetition can be 
detected and eliminated. For more information on this process 
please refer to Becker et al. (2008). As an example, Figure 6a 
shows a modelled floor. While Figure 6b depicts the 
corresponding tile string in its original version, the compressed 
string and the extracted structures are given in Figure 6c. The 
hierarchical relations between the facade elements can be stored 
in a parse tree illustrated in Figure 6d. 
b) floor 1 —► W, g l w 3 g, w, g, w 3 gj w, g : w 3 g, w, g, w 3 g, ... 
W 2 gl w 3 g, w 2 gl w 3 g, w, g, w 3 g, w, g, w 3 g, w, g, w 3 g, w, 
c) floor 1 —> Wj S 3 w 2 Sj w 2 S 3 W] 
51 -*■ gl W 3 g, 
5 2 —► S| W] S| 
5 3 —* S 2 W] S 2 
d) floor 1 
Si Wj S-, 2i w 3 gj S-> W] Si 
^A IW " IV. 
Si Wj Si S! w x Si Si Wj S t Si Wi Si 
gl' v 3§l glWjgi gjW 3 gi gi'Yjgi giWigi gjWigi gjWjgi gjWjgi 
Figure 6. Modelled floor (a), corresponding tile string (b), 
compressed tile string and extracted structures (c), 
parse tree (d) 
2.3.3 Inference of Production Rules 
Based on the sets of terminals T={w l , w 2 , ... , gi, g 2 , ...} and 
non-terminals N={W, G, ... , S It S 2 , ...}, which have been set up 
previously, the production rules for our facade grammar can be 
inferred. Following types of production rules are obtained 
during the inference process: 
p,: F—* W+ 
p 2 : W: cond —► W G W 
p 3 : G : cond —► S : : P(x\p 3 ) 
p 4 : G : cond —> g,: P(x\p 4 ) 
p s : lc < W > rc : cond —» w,-: P(x\p 5 ) 
The production rules p t and p 2 stem from the spatial 
partitioning of the facade. p t corresponds to the horizontal 
segmentation of the facade into a set of floors. The vertical 
partitioning into tiles is reflected in rule p 2 . A wall tile, which in 
the first instance can stand for a whole floor, is replaced by the 
sequence wall tile, geometry tile, wall tile. Each detected 
structure gives rise to a particular production rule in the form of 
p 3 . This rule type states the substitution of a geometry tile for a 
structure Sj. In addition, all terminal symbols generate 
production rules denoted by p 4 and p 5 in the case of geometry 
terminals g, and wall terminals w h respectively. A more detailed 
description of all rule types p, and the probabilities P(x\pj) 
assigned to them can be found in Becker et al. (2008). 
3. APPLICATION OF FACADE GRAMMAR 
Our facade grammar derived in the previous section implies 
information on the architectural configuration of the observed 
facade concerning its basic facade elements and their 
interrelationships. Based on this knowledge facade hypotheses 
can be generated as described in section 3.1. Section 3.2 
presents different application scenarios. Facades and building 
parts which are covered by noisy or incomplete sensor data are 
usually subject to inaccurate and false reconstructions which are 
due to problems of the data driven reconstruction process. For 
such regions possible facade geometry can be proposed in order 
to improve and complete facade structures. Furthermore, the 
production process can also be used to synthesize totally 
unobserved building objects.