Sketch-based tree modeling using Markov random field

ABSTRACT

In this paper, we describe a new system for converting a user's freehand sketch of a tree into a full 3D model that is both complex and realistic-looking. Our system does this by probabilistic optimization based on parameters obtained from a database of tree models. The best matching model is selected by comparing its 2D projections with the sketch. Branch interaction is modeled by a Markov random field, subject to the constraint of 3D projection to sketch. Our system then uses the notion of self-similarity to add new branches before finally populating all branches with leaves of the user's choice. We show a variety of natural-looking tree models generated from freehand sketches with only a few strokes.

REFERENCES

• 1: Christopher M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 2: Phillippe de Reffye , Claude Edelin , Jean Françon , Marc Jaeger , Claude Puech, Plant models faithful to botanical structure and development, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.151-158, June 1988
• 3: Holton, M. 1994. Strands, gravity and botanical tree imagery. Computer Graphics Forum 13, 1, 57--67.
• 4: Ijiri, T., Owada, S., and Igarashi, T. 2006. The sketch L-system: Global control of tree modeling using free-form strokes. In Smart Graphics, 138--146.
• 5: Jirasek, C., Prusinkiewicz, P., and Moulia, B. 2000. Integrating biomechanics into developmental plant models expressed using L-systems. In Proceedings of the 3rd Plant Biomechanics Conference, 615--624.
• 6: Lamdan, Y., Schwartz, J. T., and Wolfson, H. J. 1988. Object recognition by affine invariant matching. In CVPR, 335--344.
• 7: Lindenmayer, A. 1968. Mathematical models for cellular interaction in development, parts I and II. Journal of Theoretical Biology 18, 280--315.
• 8: Bernd Lintermann , Oliver Deussen, Interactive Modeling of Plants, IEEE Computer Graphics and Applications, v.19 n.1, p.56-65, January 1999 [doi>10.1109/38.736469]
• 9: Radomír Měch , Przemyslaw Prusinkiewicz, Visual models of plants interacting with their environment, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.397-410, August 1996 [doi>10.1145/237170.237279]
• 10: Boris Neubert , Thomas Franken , Oliver Deussen, Approximate image-based tree-modeling using particle flows, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 11: Okabe, M., Owada, S., and Igarashi, T. 2005. Interactive design of botanical trees using freehand sketches and example-based editing. In Computer Graphics Forum, Eurographics 2005, vol. 24.
• 12: Peter E. Oppenheimer, Real time design and animation of fractal plants and trees, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.55-64, August 1986
• 13: Prusinkiewicz, P., Hammel, M., Hanan, J., and Mech, R. 1996. L-systems: from the theory to visual models of plants. In Machine Graphics and Vision, 365--392.
• 14: Przemyslaw Prusinkiewicz , Lars Mündermann , Radoslaw Karwowski , Brendan Lane, The use of positional information in the modeling of plants, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.289-300, August 2001 [doi>10.1145/383259.383291]
• 15: Alex Reche-Martinez , Ignacio Martin , George Drettakis, Volumetric reconstruction and interactive rendering of trees from photographs, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 16: Ilya Shlyakhter , Max Rozenoer , Julie Dorsey , Seth Teller, Reconstructing 3D Tree Models from Instrumented Photographs, IEEE Computer Graphics and Applications, v.21 n.3, p.53-61, May 2001
• 17: Ping Tan , Gang Zeng , Jingdong Wang , Sing Bing Kang , Long Quan, Image-based tree modeling, ACM SIGGRAPH 2007 papers, August 05-09, 2007, San Diego, California
• 18: Ulam, S. 1966. Pattern of growth of figures: mathematical aspects. In Module, Proportion, Symmetry, Rhythm, G. Keps, Ed. Braziller, New York, 64--74.
• 19: Jason Weber , Joseph Penn, Creation and rendering of realistic trees, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.119-128, September 1995 [doi>10.1145/218380.218427]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

General Terms:
Design, Performance

Keywords:
Markov random field, geometric modeling, sketching, tree modeling