Image parsing with graph grammars and Markov Random Fields applied to facade analysis

Mateusz Kozinski, Renaud Marlet

TL;DR

This paper introduces a novel approach to parsing complex object structures like building facades by decoupling the inference of object structure from the precise positioning of its parts. By using graph grammars to model structural variations and Markov Random Fields (MRFs) for part localization, they achieve more robust and repeatable results than previous methods.

What Problem Does This Paper Address?

Parsing images of objects with complex, non-hierarchical structures, such as building facades, is challenging. Existing methods often struggle with the vast search space that combines object structure and part positions. This leads to algorithms that are either randomized or greedy, producing inconsistent results or failing to find optimal solutions. The core problem is how to effectively model and infer both the structural variations and the precise spatial arrangement of components in these objects, ensuring that the final parsed output is both accurate and structurally valid.

Methods

The paper proposes a two-stage approach:

  • Decoupled Inference: The key innovation is separating the inference of the object's structure from the inference of its parts' positions.
  • Graph Grammars for Structure: A graph grammar (specifically, Neighborhood Controlled Embedding grammars) is used to define the possible structural variations of an object. This allows for a flexible representation of how components can be arranged and related.
  • Markov Random Fields (MRFs) for Position: For a given structure derived from the grammar, a Markov Random Field (MRF) is constructed. The MRF's energy function is designed to penalize violations of geometric constraints and to evaluate how well detected image features (like texture and object detections) match the proposed part positions.
  • Late Fusion: A "late fusion" scheme is employed to combine texture classification and object detection cues. This means that raw detections are used directly in the MRF's energy function, rather than being pre-processed into pixel-level features, which the authors argue prevents "blurring" effects seen in "early fusion" methods.
  • Optimization Strategy: Structure exploration is handled by a randomized/greedy approach (based on Teboul et al.'s work), while part position optimization within a given structure is performed using a state-of-the-art MRF solver (TRW-S algorithm).

Datasets

The paper evaluates its method on datasets for facade parsing, specifically referencing datasets used in prior work by Teboul et al. [23] and Martinovic et al. [14]. They use a train-test split of 80 training and 20 testing images, repeating validation five times and averaging the results.

Key Insights and Ideas

  • Separation is Key: Decoupling structure inference from position inference significantly improves robustness and repeatability. This allows for more reliable optimization of each aspect independently.
  • Grammars for Flexibility: Graph grammars provide a powerful way to capture the inherent variability in object structures like facades, going beyond simple hierarchical models.
  • Late Fusion Advantage: Using raw object detections directly in the MRF energy function (late fusion) leads to better parsing results for complex elements like windows and balconies compared to early fusion methods.
  • Guaranteed Validity: The grammar-based approach ensures that the output segmentation conforms to the defined structural rules, avoiding artifacts seen in grammar-free methods.

Key Results

  • The proposed method achieves competitive performance compared to state-of-the-art facade parsing algorithms, particularly for classes with complex interactions like windows and balconies.
  • The advantage of separating structure and position inference is demonstrated, with the method showing improvements over prior work that combines these aspects.
  • Late fusion of texture and detection cues yields better results for window and balcony parsing than early fusion.
  • The method guarantees that parsed segmentations belong to the language generated by the grammar, preventing structural artifacts.

Limitations and Future Work

  • Structure Optimization: The paper acknowledges that structure optimization is inherently ill-posed and relies on randomized/greedy methods. While their approach limits the application of these less reliable methods to structure inference, further improvements in this area are desirable.
  • Efficient Bottom-Up Graph Construction: The authors suggest exploring more efficient methods for building the initial structure graph from bottom-up cues.
  • Warm-Starting MRF Inference: Developing methods for warm-starting MRF inference after perturbing the structure could speed up optimization.
  • 3D Objects and Grammar Learning: Future work could extend graph grammars to model 3D objects and explore methods for learning grammars directly from training data.

Summary updated

Abstract

Existing approaches to parsing images of objects featuring complex, non-hierarchical structure rely on exploration of a large search space combining the structure of the object and positions of its parts. The latter task requires randomized or greedy algorithms that do not produce repeatable results or strongly depend on the initial solution. To address the problem we propose to model and optimize the structure of the object and position of its parts separately. We encode the possible object structures in a graph grammar. Then, for a given structure, the positions of the parts are inferred using standard MAP-MRF techniques. This way we limit the application of the less reliable greedy or randomized optimization algorithm to structure inference. We apply our method to parsing images of building facades. The results of our experiments compare favorably to the state of the art.
BibTeX
@inproceedings{kozinski2014image,
  author = {Mateusz Kozinski and Renaud Marlet},
  title = {{Image parsing with graph grammars and Markov Random Fields applied to facade analysis}},
  booktitle = {IEEE/CVF Winter Conference on Applications of Computer Vision},
  year = {2014},
  doi = {10.1109/wacv.2014.6836030},
}

Loading related content...

Figure