research-article

Free access

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

Authors:

William BarrettAuthors Info & Claims

GI '09: Proceedings of Graphics Interface 2009

Pages 23 - 30

Published: 25 May 2009 Publication History

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]

A. Agarwala, A. Hertzmann, D. H. Salesin, and S. M. Seitz. Keyframe-based tracking for rotoscoping and animation. In SIGGRAPH '04: ACM SIGGRAPH 2004 Papers, pages 584--591, New York, NY, USA, 2004. ACM.

Digital Library

[2]

M. Alexa, J. Behr, D. Cohen-Or, S. Fleishman, D. Levin, and C. T. Silva. Computing and rendering point set surfaces. IEEE Transactions on Visualization and Computer Graphics, 9(1):3--15, 2003.

Digital Library

[3]

N. Amenta, S. Choi, and R. K. Kolluri. The power crust. In SMA '01: Proceedings of the Sixth ACM Symposium on Solid Modeling and Applications, pages 249--266, New York, NY, USA, 2001. ACM.

Digital Library

[4]

C. J. Armstrong, B. L. Price, and W. A. Barrett. Interactive segmentation of image volumes with live surface. Computers & Graphics, 31(2):212--229, 2007.

Digital Library

[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]

Y. Boykov and G. Funka-Lea. Graph cuts and efficient n-d image segmentation. International Journal of Computer Vision, 70(2):109--131, 2006.

Digital Library

[7]

Y. Boykov and V. Kolmogorov. An experimental comparison of mincut/max-flow algorithms for energy minimization in vision. In EMMCVPR '01: Proceedings of the Third International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, pages 359--374, London, UK, 2001. Springer-Verlag.

Digital Library

[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]

T. Funkhouser, M. Kazhdan, P. Shilane, P. Min, W. Kiefer, A. Tal, S. Rusinkiewicz, and D. Dobkin. Modeling by example. ACM Transactions on Graphics, 23(3):652--663, Aug. 2004.

Digital Library

[11]

M. Gleicher. Image snapping. In Proceedings of SIGGRAPH '95, Computer Graphics Annual Conference Series, August 1995.

Digital Library

[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.

Digital Library

[14]

D. D. Hoffman, W. Richards, A. Pentl, J. Rubin, and J. Scheuhammer. Parts of recognition. Cognition, 18:65--96, 1984.

[15]

H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Surface reconstruction from unorganized points. In Proceedings of ACM SIGGRAPH, pages 71--78, New York, NY, USA, 1992. ACM.

Digital Library

[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]

S. Katz and A. Tal. Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Trans. Graphics, 22(3):954--961, 2003.

Digital Library

[19]

Y. Lee, S. Lee, A. Shamir, D. Cohen-Or, and H. P. Seidel. Intelligent mesh scissoring using 3D snakes. In Proceedings Pacific Conference on Computer Graphics and Applications, pages 279--287, 2004.

Digital Library

[20]

Y. Lee, S. Lee, A. Shamir, D. Cohen-Or, and H.-P. Seidel. Mesh scissoring with minima rule and part salience. Computer Aided Geometric Design, 22(5):444--465, 2005.

Digital Library

[21]

X. Li, T. W. Toon, and Z. Huang. Decomposing polygon meshes for interactive applications. In 13D '01: Proceedings of the 2001 Symposium on Interactive 3D Graphics, pages 35--42, New York, NY, USA, 2001. ACM.

Digital Library

[22]

Y. Li, J. Sun, C.-K. Tang, and H.-Y. Shum. Lazy snapping. ACM Transactions on Graphics, 23(3):303--308, 2004.

Digital Library

[23]

H. Lombaert, Y. Sun, L. Grady, and C. Xu. A multilevel banded graph cuts method for fast image segmentation. In IEEE International Conference on Computer Vision, volume 1, pages 259--265 Vol. 1, 2005.

Digital Library

[24]

F. Maes, D. Vandermeulen, P. Suetens, and G. Marchal. Computeraided interactive object delineation using an intelligent paintbrush technique. In N. Ayache, editor, International Conference on Computer Vision, Virtual Reality, and Robotics in Medicine, volume 905 of Lecture Notes in Computer Science, pages 77--81. Springer, 1995.

Digital Library

[25]

A. P. Mangan and R. T. Whitaker. Partitioning 3d surface meshes using watershed segmentation. Transactions on Visualization and Computer Graphics, 5(4):308--321, 1999.

Digital Library

[26]

E. N. Mortensen and W. A. Barrett. Intelligent scissors for image composition. In SIGGRAPH '95: Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques, pages 191--198, New York, NY, USA, 1995. ACM.

Digital Library

[27]

M. Pauly, R. Keiser, L. P. Kobbelt, and M. Gross. Shape modeling with point-sampled geometry. In SIGGRAPH '03: ACM SIGGRAPH 2003 Papers, pages 641--650, New York, NY, USA, 2003. ACM.

Digital Library

[28]

A. Protiere and G. Sapiro. Interactive image segmentation via adaptive weighted distances. Image Processing, IEEE Transactions on, 16(4):1046--1057, 2007.

Digital Library

[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]

S. Rusinkiewicz and M. Levoy. QSplat: A multiresolution point rendering system for large meshes. In Proceedings of ACM SIGGRAPH 2000, pages 343--352, July 2000.

Digital Library

[31]

A. Shamir. A formulation of boundary mesh segmentation. In Proceedings 2nd International Symposium on 3D Data Processing, Visualization and Transmission (3DPVT), pages 82--89, 2004.

Digital Library

[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]

A. Sharf, M. Blumenkrants, A. Shamir, and D. Cohen-Or. SnapPaste: an interactive technique for easy mesh composition. Vis. Comput., 22(9):835--844, 2006.

Digital Library

[34]

P. D. Simari and K. Singh. Extraction and remeshing of ellipsoidal representations from mesh data. In Proceedings of Graphics Interface, pages 161--168, 2005.

Digital Library

[35]

J. Wang, P. Bhat, R. A. Colburn, M. Agrawala, and M. F. Cohen. Interactive video cutout. In SIGGRAPH '05: ACM SIGGRAPH 2005 Papers, pages 585--594, New York, NY, USA, 2005. ACM.

Digital Library

[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.

Digital Library

[37]

K. C.-H. Wong, T. Y.-H. Siu, P.-A. Heng, and H. Sun. Interactive volume cutting. In Graphics Interface, 1998.

[38]

S. Zelinka and M. Garland. Surfacing by numbers. In Proceedings Graphics Interface, 2006.

Digital Library

[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]

M. Zwicker, M. Pauly, O. Knoll, and M. Gross. Pointshop 3d: an interactive system for point-based surface editing. In Proceedings of ACM SIGGRAPH, pages 322--329, New York, NY, USA, 2002. ACM.

Digital Library

Cited By

Fan LMeng MLiu L(2012)Sketch-based mesh cuttingGraphical Models10.1016/j.gmod.2012.03.00174:6(292-301)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1016/j.gmod.2012.03.001
Meng MFan LLiu L(2011)SMI 2011Computers and Graphics10.1016/j.cag.2011.03.03835:3(650-660)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1016/j.cag.2011.03.038

Index Terms

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

Recommendations

Adaptive mesh coarsening for quadrilateral and hexahedral meshes

Mesh adaptation methods can improve the efficiency and accuracy of solutions to computational modeling problems. In many applications involving quadrilateral and hexahedral meshes, local modifications which maintain the original element type are ...
Random Walk and Graph Cut for Co-Segmentation of Lung Tumor on PET-CT Images
Accurate lung tumor delineation plays an important role in radiotherapy treatment planning. Since the lung tumor has poor boundary in positron emission tomography (PET) images and low contrast in computed tomography (CT) images, segmentation of tumor in ...
3D Graph cut with new edge weights for cerebral white matter segmentation

Accurate and efficient automatic or semi-automatic brain image segmentation methods are of great interest to both scientific and clinical researchers of the human central neural system. Cerebral white matter segmentation in brain Magnetic Resonance ...

Comments

Information & Contributors

Information

Published In

cover image Guide Proceedings

GI '09: Proceedings of Graphics Interface 2009

May 2009

257 pages

ISBN:9781568814704

Program Chairs:
Amy Gooch
University of Victoria, Canada
,
Melanie Tory
University of Victoria, Canada

Sponsors

The Canadian Human-Computer Communications Society / Société Canadienne du Dialogue Humaine Machine (CHCCS/SCDHM)

Publisher

Canadian Information Processing Society

Canada

Publication History

Published: 25 May 2009

Author Tags

Qualifiers

Research-article

Acceptance Rates

GI '09 Paper Acceptance Rate 28 of 77 submissions, 36%;

Overall Acceptance Rate 206 of 508 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
471
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)8

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fan LMeng MLiu L(2012)Sketch-based mesh cuttingGraphical Models10.1016/j.gmod.2012.03.00174:6(292-301)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1016/j.gmod.2012.03.001
Meng MFan LLiu L(2011)SMI 2011Computers and Graphics10.1016/j.cag.2011.03.03835:3(650-660)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1016/j.cag.2011.03.038

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten