Inverse Procedural Modeling

Figure 2.14.:Left: This image shows several buildings generated with split grammars, a modeling tool introduced in this paper. Right: The terminal shapes of the grammar are rendered as little boxes. A scene of this complexity can be automatically generated within a few seconds. Figure courtesy of [WWSR03].

limitation of this methods is the complicated way of the creation of the rules and architec-tural styles.

2.6. Inverse Procedural Modeling

In the previous chapter we have introduced the concept of procedural modeling. It provides an elegant and fast way to generate huge, complex and realistically looking urban sites.

Due to its generative nature it can also be referred to asforward procedural modeling. A recent survey [VAW^∗10] presents this approach for synthesis of urban environments.

2.6.1. Inverse Modeling of Buildings

On the other hand, the paradigm of grammar driven building model construction is not limited only to pure synthesis, but also to the reconstruction of existing buildings. A very complete, yet manual solution to this problem has been presented by Aliaga et al.

[ARB07]. This paper presents an inverse procedural modeling system for whole urban buildings. They extract manually a repertoire of grammars from a set of photographs of a building and utilize this information in order to visualize a realistic and textured urban model. This approach allows for quick modifications of the architectural structures, like number of floors or windows in a floor. The disadvantage of this approach is the quite labor intensive grammar creation process.

Another approach to inverse procedural modeling has been recently proposed by Bokeloh et al. [BWS10]. This work aims in slightly a different goal: automatic extraction of grammars by the means of an exemplar geometric model. Further the paper discusses the idea of a general rewriting system and context free rules for geometry, thus it provides important cues to the still very novel research topic.

Figure 2.15.:Example of inverse procedural modeling. Figure courtesy of [ARB07].

Also Vanegaset al. [VAB10] proposed a method to extract block models of buildings from images based on a grammar and Stava et al. a technique to infer a compact grammar from arbitrary 2d vector content [SBM^∗10].

The paper of Dicket al. [DTC04] describes an automatic acquisition attempt of three di-mensional architectural models from short image sequences. The approach is Bayesian and model based. Bayesian methods necessitate the formulation of a prior distribution; how-ever designing a generative model for buildings is a difficult task. In order to overcome this a building is described as a set of walls together with a “Lego” kit of parameterized primitives, such as doors or windows. A prior on wall layout, and a prior on the param-eters of each primitive can then be defined. Part of this prior is learnt from training data and part comes from expert architects. The validity of the prior is tested by generating example buildings usingMarkov Chain Monte Carlo(MCMC) and verifying that plausi-ble buildings are generated under varying conditions. The same MCMC machinery can also be used for optimizing the structure recovery, this time generating a range of possible solutions from the posterior. The fact that a range of solutions can be presented allows the user to select the best when the structure recovery is ambiguous.

A general work which aims on grammar driven segmentation has been published by Han and Zhu [HZ05,HZ09]. It presents a simple attribute graph grammar as a generative repre-sentation for made-made scenes and proposes a top-down/bottom-up inference algorithm for parsing image-content. Is simplifies the objects which can be detected to quare boxes in order to limit the grammar space. Nevertheless, this approach provides a good starting point for inverse procedural image segmentation.

2.6 Inverse Procedural Modeling

Figure 2.16.:Example of inverse procedural modeling: A labeled 3d model is generated from several images of an architectural scene. Figure courtesy of [DTC04].

2.6.2. Inverse Modeling of Façades

It appears plausible to adapt the concept of inverse procedural modeling to reconstruct façades. In this section we discuss the class of solutions that are driven by hierarchical, rule based segmentation algorithms. They cut down a façade into small irreducible parts which are arranged according to hierarchical context free grammar rules. A single-view approach for rule extraction from segmentation of simple regular façades has been published by Mülleret al. [MZWvG07] who cut the façade image into floors and tiles. The tiles are then synchronized, split and finally procedural rules are extracted.

However, already Alegre and Dellaert [AD04] proposed a specific set of grammar rules and a Markov Chain Monte Carlo (MCMC) approach to optimize the parameters in order to fit the hierarchical model against the façade image. Yet, the model they provide does not generalize to a large class of building façades. Also Korah and Rasmussen introduced a method for automatic detection of window-grids in ortho-rectified façade images [KR07a]

based on MCMC optimization. Further, Mayer and Reznik [MR05,MR06,MR07,RM07, May08] propose a series of papers, where they present a system for façade reconstruction and window detection by fitting a model by MCMC. Van Goolet al. [vGZBM07] search for similarity chains in perspective images to identify repeated façade elements. Hohmann et al.[HKHF09] attempts an interactive solution combined with a façade grammar.

Brenner and Ripperda [BR06,RB07,Rip08,RB09] develop in a series of publications a system for grammar-based decomposition of façades in elements from images and laser scans. Also they utilize MCMC for optimization. The papers of Becker et al.

Figure 2.17.: Left: original image and right: segmentation produced by the method of [MZWvG07].

[BH07,BHF08,Bec09,BH09] and Pu and Vosselman [PV09a,PV09c] are about build-ing and detailed façade reconstruction from photographs and LIDAR scans by utilizbuild-ing higher order models.

A recent approach [KST^∗09] examines a rectified façade image in order to fit a hierarchical tree grammar. This task is formulated as a Markov Random Field (MRF) [GG84] and solved by an approximating algorithm. In the following, the tree formulation of the façade image is converted in to a shape grammar which is responsible to generate a model in procedural modeling style. Teboulet al. [TSKP10] extend their work by combining a bottom-up segmentation through superpixels with top-down consistency checks coming from style rules. The space of possible rules is explored efficiently.