Inverse Procedural Modeling of Branching Structures by Inferring L-Systems

ACM Transactions on Graphics (Present at SIGGRAPH 2020)

Jianwei Guo1    Haiyong Jiang2    Bedrich Benes3    Oliver Deussen4,5    Xiaopeng Zhang1    Dani Lischinski6    Hui Huang7*

1NLPR, Institute of Automation, CAS    2UCAS and NTU Singapore    3Purdue University    4SIAT Shenzhen    5University Konstanz    6The Hebrew University of Jerusalem    7Shenzhen University

Fig. 1. Our algorithm analyzes the input image and infers a parametric L-system that represents it (d is the size of the detected structure and R is the scaling factor). The L-system represents the input and can be also used to produce its variations (right).


We introduce an inverse procedural modeling approach that learns L-system representations of pixel images with branching structures. Our fully automatic model generates a compact set of textual rewriting rules that describe the input. We use deep learning to discover atomic structures such as line segments or branchings. Orientation and scaling of these structures are determined and the detected structures are combined into a tree. The initial representation is analyzed, and repeating parts are encoded into a small grammar by using greedy optimization while the user can control the size of the detected rules. The output is an L-system that represents the input image as a simple text and a set of terminal symbols.We apply our approach to a variety of examples, demonstrate its robustness against noise and blur, and we show that it can detect user sketches and complex input structures.

Fig. 2. Overview: During training, we generate large sets of data to train a CNN in order to detect atomic structures in an input image. During the subsequent inference based on the input data, the CNN detects atomic elements in an image, their transformations are determined and organized into a tree-like structure that is then combined into an output grammar using optimization.

Fig. 7. Detection (bottom) of structures from input images (top) with random branching angles and scales.
Fig. 8. Comparison of instance detection methods (left-right): input image, detection results for template matching [Brunelli 2009], generalized Hough transformation [Mata et al. 1999], and our deep learning-based method.

Fig. 9. Detection and grammar inference results on images generated with different number of iterations (3-5).
Fig. 10. Our algorithm infers correct grammar from a complex example (left) and reproduces its structure (right).

Fig. 13. Grammar inference from user sketches (left-right): input, detection result, and our re-produced results with two different iterations. For each iteration, we automatically select random user-drawn curves to replace straight line segments.

Fig. 17. Lichtenberg image (top) and a stream network (bottom). Left to right: input, detected result, reconstructed straight branching pattern and branches after adding Perlin noise.

Fig. 18. Left: input artistic images. Middle: derivation results using our inferred grammar. Right: the re-produced designs by manually positioning the patterns according to the inferred branching structures (middle).
Fig. 20. Synthesis of layout variations: Left: input layouts that are analyzed and coded as L-systems. Right: generated new layouts via rule editing.


We thank the reviewers for their valuable comments. This work was supported in parts by National Key R&D Program (2018YFB2100602), NSFC (61861130365, 61761146002, 61802406, 61802362), GD Higher Education Key Program (2018KZDXM058), LHTD (20170003), GD Leading Talent Program (00201509), DFG (422037984), NSF (10001387), FAR (602757), and GD Laboratory of Artificial Intelligence and Digital Economy (SZ).

title = {
Inverse Procedural Modeling of Branching Structures by Inferring L-Systems},
author = {Jianwei Guo and Haiyong Jiang and Bedrich Benes and Oliver Deussen and Xiaopeng Zhang and Dani Lischinski and Hui Huang},
journal = {ACM Transactions on Graphics},
volume = {},
number = {},
pages = {},  
year = {2020},

Downloads(faster for people in China)

Downloads(faster for people in other places)