“Variational Mesh Decomposition” by Zhang, Zheng, Wu and Cai

The problem of decomposing a 3D mesh into meaningful segments (or parts) is of great practical importance in computer graphics. This article presents a variational mesh decomposition algorithm that can efficiently partition a mesh into a prescribed number of segments. The algorithm extends the Mumford-Shah model to 3D meshes that contains a data term measuring the variation within a segment using eigenvectors of a dual Laplacian matrix whose weights are related to the dihedral angle between adjacent triangles and a regularization term measuring the length of the boundary between segments. Such a formulation simultaneously handles segmentation and boundary smoothing, which are usually two separate processes in most previous work. The efficiency is achieved by solving the Mumford-Shah model through a saddle-point problem that is solved by a fast primal-dual method. A preprocess step is also proposed to determine the number of segments that the mesh should be decomposed into. By incorporating this preprocessing step, the proposed algorithm can automatically segment a mesh into meaningful parts. Furthermore, user interaction is allowed by incorporating the user’s inputs into the variational model to reflect the user’s special intention. Experimental results show that the proposed algorithm outperforms competitive segmentation methods when evaluated on the Princeton Segmentation Benchmark.

Attene, M., Katz, S., Mortara, M., Patanè, G., Spagnuolo, M., and Tal, A. 2006. Mesh segmentation – A comparative study. In Proceedings of the International Conference on Shape Modeling and Applications, 14–25. Google ScholarDigital Library
Bardsley, J. M. and Luttman, A. 2009. A fixed point formulation of the k-means algorithm and a connection to Mumford-Shah. Appl. Math. E-Notes 9, 274–276.Google Scholar
Chen, X., Golovinskiy, A., and Funkhouser, T. 2009. A benchmark for 3D mesh segmentation. ACM Trans. Graph. 28, 3. Google ScholarDigital Library
Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2004. Variational shape approximation. ACM Trans. Graph. 23, 3, 905–914. Google ScholarDigital Library
Delaunoy, A., Fundana, K., Prados, E., and Heyden, A. 2009. Convex multi-region segmentation on manifolds. In Proceedings of the International Conference on Computer Vision (ICCV).Google Scholar
Dey, T. K., Giesen, J., and Goswami, S. 2003. Shape segmentation and matching with flow discretization. In Proceedings of 8th International Workshop on Algorithms and Data Structures (WADS). 25–36.Google Scholar
Dey, T. K., Ranjan, P., and Wang, Y. 2010. Convergence, stability, and discrete approximation of Laplace spectra. In Proceedings of ACM/SIAM Symposium on Discreate Algorithms (SODA). 650–663. Google ScholarDigital Library
Funkhouser, T., Kazhdan, M., Shilane, P., Min, P., Kiefer, W., Tal, A., Rusinkiewicz, S., and Dobkin, D. 2004. Modeling by example. ACM Trans. Graph. 652–663. Google ScholarDigital Library
Golovinskiy, A. and Funkhouser, T. A. 2008. Randomized cuts for 3D mesh analysis. ACM Trans. Graph. 27, 5. Google ScholarDigital Library
Grady, L. 2006. Random walks for image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 28, 11, 1768–1783. Google ScholarDigital Library
Gregory, A., State, A., Lin, M. C., Manocha, D., and Livingston, M. A. 1999. Interactive surface decomposition for polyhedral morphing. Vis. Comput. 9, 453–470.Google ScholarDigital Library
Hagen, L. W. and Kahng, A. B. 1992. New spectral methods for ratio cut partitioning and clustering. IEEE Trans. Comput. Aid. Des. Integr. Circ. Syst. 11, 9, 1074–1085. Google ScholarDigital Library
Hoffman, D. and Singh, M. 1997. Salience of visual parts. Cognition, 29–78.Google Scholar
Hoffman, D. D. and Richards, W. 1984. Parts of recognition. Cognition, 65–96.Google Scholar
Kalogerakis, E., Hertzmann, A., and Singh, K. 2010. Learning 3D mesh segmentation and labeling. ACM Trans. Graph. 29, 4. Google ScholarDigital Library
Katz, S., Leifman, G., and Tal, A. 2005. Mesh segmentation using feature point and core extraction. Vis. Comput. 21, 8-10, 649–658.Google ScholarCross Ref
Katz, S. and Tal, A. 2003. Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Trans. Graph. 22, 3, 954–961. Google ScholarDigital Library
Lai, Y.-K., Hu, S.-M., Martin, R. R., and Rosin, P. L. 2008. Fast mesh segmentation using random walks. In Proceedings of the ACM Symposium on Solid and Physical Modeling. 183–191. Google ScholarDigital Library
Lee, Y., Lee, S., Shamir, A., Cohen-Or, D., and Seidel, H.-P. 2005. Mesh scissoring with minima rule and part salience. Comput. Aid. Geom. Des. 22, 5, 444–465. Google ScholarDigital Library
Lellmann, J. and Schnörr, C. 2011. Continuous multiclass labeling approaches and algorithms. CoRR abs/1102.5448.Google Scholar
Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21, 362–371. Google ScholarDigital Library
Lévy, B. and Zhang, R. H. 2010. Spectral geometry processing. In ACM SIGGRAPH Course Notes.Google Scholar
Liu, R. and Zhang, H. 2004. Segmentation of 3D meshes through spectral clustering. In Proceedings of the Pacific Conference on Computer Graphics and Applications. 298–305. Google ScholarDigital Library
Liu, R. and Zhang, H. 2007. Mesh segmentation via spectral embedding and contour analysis. Comput. Graph. Forum 26, 3, 385–394.Google ScholarCross Ref
Mumford, D. and Shah, J. 1989. Optimal approximations by piecewise smooth functions and associated variational problems. Comm. Pure Appl. Math. 42, 5, 577–685.Google ScholarCross Ref
Ng, A. Y., Jordan, M. I., and Weiss, Y. 2001. On spectral clustering: Analysis and an algorithm. In Proceedings of the Conference on Neural Information Processing Systems (NIPS). 849–856.Google Scholar
Nikolova, M., Esedoglu, S., and Chan, T. F. 2006. Algorithms for finding global minimizers of image segmentation and denoising models. SIAM J. Appl. Math. 66, 5, 1632–1648.Google ScholarCross Ref
Pock, T., Chambolle, A., Cremers, D., and Bischof, H. 2009a. A convex relaxation approach for computing minimal partitions. In Computer Vision and Pattern Recognition, 810–817.Google Scholar
Pock, T., Cremers, D., Bischof, H., and Chambolle, A. 2009b. An algorithm for minimizing the piecewise smooth Mumford-Shah functional. In Proceedings of the IEEE International Conference on Computer Vision (ICCV).Google Scholar
Polito, M. and Perona, P. 2001. Grouping and dimensionality reduction by locally linear embedding. In Proceedings of the Conference on Neural Information Processing Systems (NIPS). 1255–1262.Google Scholar
Popov, L. D. 1980. A modification of the Arrow-Hurwicz method for search of saddle points. Math. Notes 28, 5, 845–848.Google ScholarCross Ref
Rockafellar, R. T. 1970. Convex Analysis. Princeton University Press.Google Scholar
Shamir, A. 2008. A survey on mesh segmentation techniques. Comput. Graph. Forum 27, 6, 1539–1556.Google ScholarCross Ref
Shamir, A., Shapira, L., and Cohen-Or, D. 2006. Mesh analysis using geodesic mean-shift. Vis. Comput. 22, 99–108. Google ScholarDigital Library
Shapira, L., Shamir, A., and Cohen-Or, D. 2008. Consistent mesh partitioning and skeletonisation using the shape diameter function. Vis. Comput. 24, 4, 249–259. Google ScholarDigital Library
Shlafman, S., Tal, A., and Katz, S. 2002. Metamorphosis of polyhedral surfaces using decomposition. Comput. Graph. Forum 21, 219–228.Google ScholarCross Ref
Vese, L. A. and Chan, T. F. 2002. A multiphase level set framework for image segmentation using the mumford and shah model. Int. J. Comput. Vis. 50, 3, 271–293. Google ScholarDigital Library
von Luxburg, U. 2007. A tutorial on spectral clustering. Statist. Comput. 17, 4, 395–416. Google ScholarDigital Library
Wu, C., Deng, J., Chen, F., and Tai, X. 2009. Scale-Space analysis of discrete filtering over arbitrary triangulated surfaces. SIAM J. Imaging Sci. 2, 2, 670–709. Google ScholarDigital Library
Yamauchi, H., Lee, S., Lee, Y., Ohtake, Y., Belyaev, A., and Seidel, H.-P. 2005. Feature sensitive mesh segmentation with mean shift. In Proceedings of the International Conference on Shape Modeling and Applications. 238–245. Google ScholarDigital Library
Zelnik-Manor, L. and Perona, P. 2004. Self-Tuning Spectral Clustering. In Proceedings of the Conference on Neural Information Processing Systems (NIPS).Google Scholar
Zhang, J., Wu, C., Cai, J., Zheng, J., and Tai, X.-C. 2010. Mesh snapping: Robust interactive mesh cutting using fast geodesic curvature flow. Comput. Graph. Forum 29, 2, 517–526.Google ScholarCross Ref