Abstraction of 2D shapes in terms of parts

ABSTRACT

Abstraction in imagery results from the strategic simplification and elimination of detail to clarify the visual structure of the depicted shape. It is a mainstay of artistic practice and an important ingredient of effective visual communication. We develop a computational method for the abstract depiction of 2D shapes. Our approach works by organizing the shape into parts using a new synthesis of holistic features of the part shape, local features of the shape boundary, and global aspects of shape organization. Our abstractions are new shapes with fewer and clearer parts.

REFERENCES

• 1: Pascal Barla , Joëlle Thollot , François X. Sillion, Geometric clustering for line drawing simplification, ACM SIGGRAPH 2005 Sketches, July 31-August 04, 2005, Los Angeles, California [doi>10.1145/1187112.1187227]
• 2: Blum, H., and Nagel, R. 1978. Shape description using weighted symmetric axis features. Pattern Recog. 10, 167--180.
• 3: Brady, M., and Asada, H. 1984. Smoothed local symetries and their implementation. Int. J. of Robotics Research 3, 3, 36--61.
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: Doug DeCarlo , Anthony Santella, Stylization and abstraction of photographs, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 6: Mathieu Desbrun , Mark Meyer , Peter Schröder , Alan H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.317-324, July 1999 [doi>10.1145/311535.311576]
• 7: Tamal K. Dey , Kuiyu Li , Jian Sun , David Cohen-Steiner, Computing geometry-aware handle and tunnel loops in 3D models, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 8: Douglas, D., and Peucker, T. 1973. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer 10, 2, 112--122.
• 9: Frédo Durand , Victor Ostromoukhov , Mathieu Miller , Francois Duranleau , Julie Dorsey, Decoupling Strokes and High-Level Attributes for Interactive Traditional Drawing, Proceedings of the 12th Eurographics Workshop on Rendering Techniques, p.71-82, June 25-27, 2001
• 10: Jacob Feldman, Perceptual Grouping by Selection of a Logically Minimal Model, International Journal of Computer Vision, v.55 n.1, p.5-25, October 2003 [doi>10.1023/A:1024454423670]
• 11: Michael Garland , Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.209-216, August 1997 [doi>10.1145/258734.258849]
• 12: Giblin, P., and Brassett, S. 1985. Local symmetry of plane curves. The American Mathematical Monthly 92, 10, 689--707.
• 13: Gold, C., and Thibault, D. 2001. Map generalization by skeleton retraction. In Proceedings of the International Cartographic Association, 2072--2081.
• 14: Aaron Hertzmann, Paint By Relaxation, Computer Graphics International 2001, p.47-54, July 03-06, 2001
• 15: Hoffman, D. D., and Singh, M. 1997. Salience of visual parts. Cognition 63, 29--78.
• 16: Hugues Hoppe, Progressive meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.99-108, August 1996 [doi>10.1145/237170.237216]
• 17: Jeong, K., Ni, A., Lee, S., and Markosian, L. 2005. Detail control in line drawings of 3D meshes. The Visual Computer 21, 8--10 (September), 698--706. Pacific Graphics 2005.
• 18: Kang, H., and Lee, S. 2008. Shape-simplifying image abstraction. Computer Graphics Forum (Pacific Graphics 2008 Conference Proceedings) 27, 7, 1773--1780.
• 19: Benjamin B. Kimia , Allen R. Tannenbaum , Steven W. Zucker, Shapes, shocks, and deformations I: the components of two-dimensional shape and the reaction-diffusion space, International Journal of Computer Vision, v.15 n.3, p.189-224, July 1995 [doi>10.1007/BF01451741]
• 20: Kolliopoulos, A., Wang, J. M., and Hertzmann, A. 2006. Segmentation-based 3D artistic rendering. In Rendering Techniques 2006: 17th Eurographics Workshop on Rendering, 361--370.
• 21: Chang Ha Lee , Amitabh Varshney , David W. Jacobs, Mesh saliency, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 22: Yunjin Lee , Lee Markosian , Seungyong Lee , John F. Hughes, Line drawings via abstracted shading, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 23: Leyton, M. 1992. Symmetry, Causality, Mind. MIT Press, Cambridge, MA.
• 24: McCloud, S. 1993. Understanding Comics: The Invisible Art. Harper Perennial.
• 25: Mi, X., and DeCarlo, D. 2007. Separating parts from 2D shapes using relatability. In ICCV 2007.
• 26: Niloy J. Mitra , Leonidas J. Guibas , Mark Pauly, Partial and approximate symmetry detection for 3D geometry, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 27: Farzin Mokhtarian , Alan K. Mackworth, A Theory of Multiscale, Curvature-Based Shape Representation for Planar Curves, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.8, p.789-805, August 1992 [doi>10.1109/34.149591]
• 28: Alexandrina Orzan , Adrien Bousseau , Pascal Barla , Joëlle Thollot, Structure-preserving manipulation of photographs, Proceedings of the 5th international symposium on Non-photorealistic animation and rendering, August 04-05, 2007, San Diego, California [doi>10.1145/1274871.1274888]
• 29: Prasad, L. 1997. Morphological analysis of shapes. Tech. Rep. CNLS Newsletter, No. 139, LALP-97-010-139, Center for Nonlinear Studies, T-DOT, Theoretical Division, Los Alamos National Laboratory, July.
• 30: Robinson, A. H., Morrison, J. L., Muehrcke, P. C., Kimerling, A. J., and Guptill, S. C. 1995. Elements of Cartography, 6th edition. Wiley.
• 31: H. Rom , G. Medioni, Hierarchical Decomposition and Axial Shape Description, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.10, p.973-981, October 1993 [doi>10.1109/34.254054]
• 32: Thomas B. Sebastian , Philip N. Klein , Benjamin B. Kimia, On Aligning Curves, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.1, p.116-125, January 2003 [doi>10.1109/TPAMI.2003.1159951]
• 33: Chen Shen , James F. O'Brien , Jonathan R. Shewchuk, Interpolating and approximating implicit surfaces from polygon soup, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 34: Jonathan Richard Shewchuk, Updating and constructing constrained delaunay and constrained regular triangulations by flips, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777821]
• 35: Philip Shilane , Thomas Funkhouser, Distinctive regions of 3D surfaces, ACM Transactions on Graphics (TOG), v.26 n.2, p.7-es, June 07 [doi>10.1145/1243980.1243981]
• 36: Kaleem Siddiqi , Benjamin B. Kimia, Parts of Visual Form: Computational Aspects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.3, p.239-251, March 1995 [doi>10.1109/34.368189]
• 37: Singh, M., and Fulvio, J. M. 2005. Visual extrapolation of contour geometry. Proceedings of the National Academy of Sciences, USA 102, 3, 939--944.
• 38: Singh, M., and Hoffman, D. D. 2001. Part-based representations of visual shape and implications for visual cognition. In From Fragments to Objects: Grouping and Segmentation in Vision, T. F. Shipley and P. J. Kellman, Eds. Elsevier Science Ltd., 401--459.
• 39: Singh, M., Seyraninan, G., and Hoffman, D. 1999. Parsing silhouettes: The short-cut rule. Perception and Psychophysics, 61, 636--660.
• 40: Van Der Poorten, P., and Jones, C. B. 2002. Characterisation and generalisation of cartographic lines using Delaunay triangulation. International Journal of Geographical Information science, 8, 773--794.
• 41: Jue Wang , Yingqing Xu , Heung-Yeung Shum , Michael F. Cohen, Video tooning, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 42: Holger Winnemöller , Sven C. Olsen , Bruce Gooch, Real-time video abstraction, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance

Keywords:
abstraction, non-photorealistic rendering, symmetry