Interactive part selection for mesh and point models using hierarchical graph-cut partitioning

ABSTRACT

This paper presents a method for interactive part selection for mesh and point set surface models that combines scribble-based selection methods with hierarchically accelerated graph-cut segmentation. Using graph-cut segmentation to determine optimal intuitive part boundaries enables easy part selection on complex geometries and allows for a simple, scribble-based interface that focuses on selecting within visible parts instead of precisely defining part boundaries that may be in difficult or occluded regions. Hierarchical acceleration is used to maintain interactive speed on large models and to provide connectivity when extending the technique to point set models.

REFERENCES

• 1: Aseem Agarwala , Aaron Hertzmann , David H. Salesin , Steven M. Seitz, Keyframe-based tracking for rotoscoping and animation, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 2: Marc Alexa , Johannes Behr , Daniel Cohen-Or , Shachar Fleishman , David Levin , Claudio T. Silva, Computing and Rendering Point Set Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.9 n.1, p.3-15, January 2003 [doi>10.1109/TVCG.2003.1175093]
• 3: Nina Amenta , Sunghee Choi , Ravi Krishna Kolluri, The power crust, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.249-266, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376986]
• 4: Christopher J. Armstrong , Brian L. Price , William A. Barrett, Interactive segmentation of image volumes with Live Surface, Computers and Graphics, v.31 n.2, p.212-229, April, 2007 [doi>10.1016/j.cag.2006.11.015]
• 5: X. Bai and G. Sapiro. A geodesic framework for fast interactive image and video segmentation and matting. In IEEE 11th International Conference on Computer Vision, pages 1--8, 2007.
• 6: Yuri Boykov , Gareth Funka-Lea, Graph Cuts and Efficient N-D Image Segmentation, International Journal of Computer Vision, v.70 n.2, p.109-131, November 2006 [doi>10.1007/s11263-006-7934-5]
• 7: Yuri Boykov , Vladimir Kolmogorov, An Experimental Comparison of Min-cut/Max-flow Algorithms for Energy Minimization in Vision, Proceedings of the Third International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, p.359-374, September 03-05, 2001
• 8: Y. Y. Boykov and M.-P. Jolly. Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images. In Proceedings Eighth International Conference on Computer Vision (ICCV 2001), volume 1, pages 105--112, 2001.
• 9: C. D. Bruyns and S. Senger. Interactive cutting of 3D surface meshes. Computers & Graphics, 25(4):635--642, August 2001.
• 10: Thomas Funkhouser , Michael Kazhdan , Philip Shilane , Patrick Min , William Kiefer , Ayellet Tal , Szymon Rusinkiewicz , David Dobkin, Modeling by example, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 11: Michael Gleicher, Image snapping, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.183-190, September 1995 [doi>10.1145/218380.218441]
• 12: M. Gopi, S. Krishnan, and C. T. Silva. Surface reconstruction based on lower dimensional localized delaunay triangulation. In M. Gross and F. R. A. Hopgood, editors, Computer Graphics Forum (Eurographics 2000), volume 19(3), 2000.
• 13: A. Gregory, A. State, M. C. Lin, D. Manocha, and M. A. Livington. Interactive surface decomposition for polyhedral morphing. The Visual Computer, 15(9):453--470, 1999.
• 14: D. D. Hoffman, W. Richards, A. Pentl, J. Rubin, and J. Scheuhammer. Parts of recognition. Cognition, 18:65--96, 1984.
• 15: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.71-78, July 1992
• 16: Z. Ji, L. Liu, Z. Chen, and G. Wang. Easy mesh cutting. In E. Groller and L. Szirmay-Kalos, editors, Computer Graphics Forum (Eurographics 2006), volume 25(3), 2006.
• 17: M. Kass, A. Witkin, and D. Terzopoulos. Snakes: active contour models. International Journal of Computer Vision, 1(4):321--331, 1987.
• 18: Sagi Katz , Ayellet Tal, Hierarchical mesh decomposition using fuzzy clustering and cuts, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 19: Yunjin Lee , Seungyong Lee , Ariel Shamir , Daniel Cohen-Or , Hans-Peter Seidel, Intelligent Mesh Scissoring Using 3D Snakes, Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, p.279-287, October 06-08, 2004
• 20: Yunjin Lee , Seungyong Lee , Ariel Shamir , Daniel Cohen-Or , Hans-Peter Seidel, Mesh scissoring with minima rule and part salience, Computer Aided Geometric Design, v.22 n.5, p.444-465, July 2005 [doi>10.1016/j.cagd.2005.04.002]
• 21: Xuetao Li , Tong Wing Woon , Tiow Seng Tan , Zhiyong Huang, Decomposing polygon meshes for interactive applications, Proceedings of the 2001 symposium on Interactive 3D graphics, p.35-42, March 2001 [doi>10.1145/364338.364343]
• 22: Yin Li , Jian Sun , Chi-Keung Tang , Heung-Yeung Shum, Lazy snapping, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 23: Herve Lombaert , Yiyong Sun , Leo Grady , Chenyang Xu, A Multilevel Banded Graph Cuts Method for Fast Image Segmentation, Proceedings of the Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, p.259-265, October 17-20, 2005 [doi>10.1109/ICCV.2005.13]
• 24: Frederik Maes , Dirk Vandermeulen , Paul Suetens , Guy Marchal, Computer-Aided Interactive Object Delineation Using an Intelligent Paintbrush Technique, Proceedings of the First International Conference on Computer Vision, Virtual Reality and Robotics in Medicine, p.77-83, April 03-06, 1995
• 25: Alan P. Mangan , Ross T. Whitaker, Partitioning 3D Surface Meshes Using Watershed Segmentation, IEEE Transactions on Visualization and Computer Graphics, v.5 n.4, p.308-321, October 1999 [doi>10.1109/2945.817348]
• 26: Eric N. Mortensen , William A. Barrett, Intelligent scissors for image composition, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.191-198, September 1995 [doi>10.1145/218380.218442]
• 27: Mark Pauly , Richard Keiser , Leif P. Kobbelt , Markus Gross, Shape modeling with point-sampled geometry, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 28: A. Protiere and G. Sapiro. Interactive image segmentation via adaptive weighted distances. Image Processing, IEEE Transactions on, 16(4):1046--1057, 2007.
• 29: L. J. Reese and W. A. Barrett. Image editing with intelligent paint. In Computer Graphics Forum (Eurographics 2002), volume 21, pages 714--724, 2002.
• 30: Szymon Rusinkiewicz , Marc Levoy, QSplat: a multiresolution point rendering system for large meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.343-352, July 2000 [doi>10.1145/344779.344940]
• 31: Ariel Shamir, A Formulation of Boundary Mesh Segmentation, Proceedings of the 3D Data Processing, Visualization, and Transmission, 2nd International Symposium, p.82-89, September 06-09, 2004 [doi>10.1109/3DPVT.2004.13]
• 32: A. Shamir. A survey on mesh segmentation techniques. Computer Graphics Forum, 27(6): 1539--1556, January 2008. Appeared previously as a State-of-the-Art Report in Eurographics 2006.
• 33: Andrei Sharf , Marina Blumenkrants , Ariel Shamir , Daniel Cohen-Or, SnapPaste: an interactive technique for easy mesh composition, The Visual Computer: International Journal of Computer Graphics, v.22 n.9, p.835-844, September 2006 [doi>10.1007/s00371-006-0068-5]
• 34: Patricio D. Simari , Karan Singh, Extraction and remeshing of ellipsoidal representations from mesh data, Proceedings of Graphics Interface 2005, May 09-11, 2005, Victoria, British Columbia
• 35: Jue Wang , Pravin Bhat , R. Alex Colburn , Maneesh Agrawala , Michael F. Cohen, Interactive video cutout, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 36: T. Weyrich, M. Pauly, R. Keiser, S. Heinzle, S. Scandella, and M. Gross. Post-processing of scanned 3D surface data. In Proceedings of Eurographics Symposium on Point-Based Graphics 2004, pages 85--94, 2004.
• 37: K. C.-H. Wong, T. Y.-H. Siu, P.-A. Heng, and H. Sun. Interactive volume cutting. In Graphics Interface, 1998.
• 38: Steve Zelinka , Michael Garland, Surfacing by numbers, Proceedings of Graphics Interface 2006, June 07-09, 2006, Quebec, Canada
• 39: M. Zöckler, D. Stalling, and H.-C. Hege. Fast and intuitive generation of geometric shape transitions. The Visual Computer, 16(5):241--253, 2000.
• 40: Matthias Zwicker , Mark Pauly , Oliver Knoll , Markus Gross, Pointshop 3D: an interactive system for point-based surface editing, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.m Miscellaneous

Keywords:
graph cut, interactive modeling tools, mesh, model partitioning, point set, scribble interface