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

  • ©Juyong Zhang, Jianmin Zheng, Chunlin Wu, and Jianfei Cai




    Variational Mesh Decomposition



    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

ACM Digital Library Publication: