Interactive Mesh Segmentation Based on Graph Laplacian

Abstract:

This paper introduces a novel algorithm that decomposes a given shape into meaningful parts requiring only strokes to specify foreground and background regions. The user is asked to draws freehand sketches to provide some facets as belonging to the desired part of the surface, and then an energy function is constructed based on graph Laplacian. Finally, a solution of minimizing energy function is provided and then segmentation is finished. We have presented an effective interactive system with an easy-to-use UI for mesh segmentation. The experiment results show that our algorithm is robust, fast, and capable of producing satisfactory results with regard to the human intuition and geometric attributes.

• Periodical: Applied Mechanics and Materials (Volumes 58-60)
• Pages: 1535-1540
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.58-60.1535
• Online since: June 2011
• Authors: En Yang Gao, Wei Jun Liu, Tian Ran Wang
• Keywords: Graph Laplacian, Mesh Metric, Mesh Segmentation

References

[1] Attene, M., Falcidieno, B., Spagnuolo, M.: Hierarchical mesh segmentation based on fitting primitives. The Visual Computer 22(3), 181–193 (2006).

DOI: 10.1007/s00371-006-0375-x

[2] Chen, X., Golovinskiy, A., Funkhouser, T.: A benchmark for 3D mesh segmentation. In: ACM SIGGRAPH 2009 papers, p.1–12. ACM (2009).

DOI: 10.1145/1576246.1531379

[3] Funkhouser, T., Kazhdan, M., Shilane, P., Min, P., Kiefer, W., Tal, A., Rusinkiewicz, S., Dobkin, D.: Modeling by example. In: ACM SIGGRAPH 2004 Papers, p.663. ACM (2004).

DOI: 10.1145/1186562.1015775

[4] Gregory, A., State, A., Lin, M., Manocha, D., Livingston,M.: Interactive surface decomposition for polyhedral morphing. The Visual Computer 15(9), 453–470 (1999).

DOI: 10.1007/s003710050192

[5] Ji, Z., Liu, L., Chen, Z., Wang, G.: Easy mesh cutting. In: Computer Graphics Forum, vol. 25, p.283–291. WileyOnline Library (2006).

DOI: 10.1111/j.1467-8659.2006.00947.x

[6] Kalogerakis, E., Hertzmann, A., Singh, K.: Learning 3Dmesh segmentation and labeling. ACM Transactions onGraphics (TOG) 29(4), 1–12 (2010).

DOI: 10.1145/1778765.1778839

[7] Katz, S., Tal, A.: Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Transactions on Graphics (TOG) 22(3), 954–961 (2003).

DOI: 10.1145/882262.882369

[8] Koschan, A.: Perception-based 3D triangle mesh segmentationusin g fast marching watersheds. In: Computer Vision and Pattern Recognition, 2003. Proceedings. 2003 IEEE Computer Society Conference on, vol. 2. IEEE (2003).

DOI: 10.1109/cvpr.2003.1211448

[9] Lai, Y., Hu, S., Martin, R., Rosin, P.: Fast mesh segmentation using random walks. In: Proceedings of the 2008 ACM symposium on Solid and physical modeling, p.183–191. ACM (2008).

DOI: 10.1145/1364901.1364927

[10] Lavou´e, G., Dupont, F., Baskurt, A.: A new CAD mesh segmentation method, based on curvature tensor analysis. Computer-Aided Design 37(10), 975–987 (2005).

DOI: 10.1016/j.cad.2004.09.001

[11] Lee, Y., Lee, S.: Geometric snakes for triangular meshes. In: Computer Graphics Forum, vol. 21, p.229–238. WileyOnline Library (2002).

DOI: 10.1111/1467-8659.00582

[12] Lee, Y., Lee, S., Shamir, A., Cohen-Or, D., Seidel, H.: Intelligent mesh scissoring using 3d snakes (2004).

DOI: 10.1109/pccga.2004.1348358

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

DOI: 10.1016/j.cagd.2005.04.002

[14] L´evy, B., Petitjean, S., Ray, N., Maillot, J.: Least squares conformal maps for automatic texture atlas generation. ACM Transactions on Graphics 21(3), 362–371 (2002).

DOI: 10.1145/566654.566590

[15] Li, X., Woon, T., Tan, T., Huang, Z.: Decomposing polygon meshes for interactive applications. In: Proceedings of the 2001 symposium on Interactive 3D graphics, p.35–42. ACM New York, NY, USA (2001).

DOI: 10.1145/364338.364343

[16] Li, Y., Sun, J., Tang, C., Shum, H.: Lazy snapping. ACM Transactions on Graphics (ToG) 23(3), 303–308 (2004).

DOI: 10.1145/1015706.1015719

[17] Liu, R., Zhang, H.: Segmentation of 3D meshes through spectral clustering. In: Proc. Pacific Graphics, vol. 4, p.298–305. Citeseer (2004).

[18] Liu, R., Zhang, H.: Mesh segmentation via spectral embedding and contour analysis. In: Computer Graphics Forum, vol. 26, p.385–394. Wiley Online Library (2007).

DOI: 10.1111/j.1467-8659.2007.01061.x

[19] Pottmann, H., Steiner, T., Hofer, M., Haider, C., Hanbury, A.: The isophotic metric and its application to feature sensitive morphology on surfaces. Computer Vision- ECCV 2004 p.18–23 (2004).

DOI: 10.1007/978-3-540-24673-2_45