Feature sensitive mesh segmentation

ABSTRACT

Segmenting meshes into natural regions is useful for model understanding and many practical applications. In this paper, we present a novel, automatic algorithm for segmenting meshes into meaningful pieces. Our approach is a clustering-based top-down hierarchical segmentation algorithm. We extend recent work on feature sensitive isotropic remeshing to generate a mesh hierarchy especially suitable for segmentation of large models with regions at multiple scales. Using integral invariants for estimation of local characteristics, our method is robust and efficient. Moreover, statistical quantities can be incorporated, allowing our approach to segment regions with different geometric characteristics or textures.

REFERENCES

• 1: Pierre Alliez , Éric Colin de Verdière , Olivier Devillers , Martin Isenburg, Isotropic Surface Remeshing, Proceedings of the Shape Modeling International 2003, p.49, May 12-15, 2003
• 2: Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2004. Variational shape approximation. In Proceedings of SIGGRAPH, 905--914.
• 3: Funkhouser, T., Kazhdan, M., Shilane, P., Min, P., Kiefer, W., Tal, A., Rusinkiewicz, S., and Dobkin, D. 2004. Modeling by example. In Proceedings of SIGGRAPH, 652--663.
• 4: Michael Garland , Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.209-216, August 1997 [doi>10.1145/258734.258849]
• 5: Natasha Gelfand , Leonidas J. Guibas, Shape segmentation using local slippage analysis, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057461]
• 6: Hoffmann, D. D., and Richards, W. A. 1984. Parts of recognition. Cognition 18.
• 7: Hoffmann, D. D., and Singh, M. 1997. Salience of visual parts. Cognition 63, 29--78.
• 8: Hugues Hoppe, Progressive meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.99-108, August 1996 [doi>10.1145/237170.237216]
• 9: Julius, D., Kraevoy, V., and Sheffer, A. 2005. D-charts: Quasi-developable mesh segmentation. Computer Graphics Forum 24, 3, 581--590.
• 10: Katz, S., and Tal, A. 2003. Hierarchical mesh decomposition using fuzzy clustering and cuts. In Proceedings of SIGGRAPH, ACM Press, vol. 22(3), 954--961.
• 11: Katz, S., Leifman, G., and Tal, A. 2005. Mesh segmentation using feature point and core extraction. The Visual Computer 21, 8--10, 865--875.
• 12: Kelley, C. T. 1999. Iterative Methods for Optimization. SIAM.
• 13: R. Kimmel , R. Malladi , N. Sochen, Images as Embedded Maps and Minimal Surfaces: Movies, Color, Texture, and Volumetric Medical Images, International Journal of Computer Vision, v.39 n.2, p.111-129, Sept. 2000 [doi>10.1023/A:1008171026419 ]
• 14: Lai, Y.-K., Zhou, Q.-Y., Hu, S.-M., Wallner, J., and Pottmann, H. 2006. Robust feature classification and editing. IEEE Transactions on Visualization and Computer Graphics. to appear.
• 15: Lee, Y. and Lee, S. 2002. Geometric snakes for triangular meshes. Computer Graphics Forum 21, 3, 229--238.
• 16: 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 on (PG'04), p.279-287, October 06-08, 2004
• 17: Xuetao Li , Tong Wing Toon , 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]
• 18: Rong Liu , Hao Zhang, Segmentation of 3D Meshes through Spectral Clustering, Proceedings of the Computer Graphics and Applications, 12th Pacific Conference on (PG'04), p.298-305, October 06-08, 2004
• 19: Manay, S., Hong, B.-W., Yezzi, A. J., and Soatto, S. 2004. Integral invariant signatures. In Proceedings of ECCV, Springer, 87--99.
• 20: 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 ]
• 21: Mitani, J., and Suzuki, H. 2004. Making papercraft toys from-meshes using strip-based approximate unfolding. In Proceedings of SIGGRAPH, 259--263.
• 22: Page, D. L., Koschan, A. F., and Abidi, M. A. 2003. Perception-based 3D triangle mesh segmentation using fast marching watershed. In Proceedings of the IEEE Conf. on Computer Vision and Pattern Recognition, 27--32.
• 23: Pottmann, H., Steiner, T., Hofer, M., Haider, C., and Hanbury, A. 2004. The isophotic metric and its application to feature sensitive morphology on surfaces. In Proceedings of ECCV 2004, Part IV, Springer, 560--572.
• 24: P. V. Sander , Z. J. Wood , S. J. Gortler , J. Snyder , H. Hoppe, Multi-chart geometry images, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 25: Shamir, A., Shapira, L., Cohen-Or, D., and Golden-Thal, R. 2004. Geodesic mean shift. In Proceedings of the 5th Korea Israel conference on Geometric Modeling and Computer Graphics, 51--56.
• 26: Ariel Shamir, A Formulation of Boundary Mesh Segmentation, Proceedings of the 3D Data Processing, Visualization, and Transmission, 2nd International Symposium on (3DPVT'04), p.82-89, September 06-09, 2004 [doi>10.1109/3DPVT.2004.13]
• 27: Shlafman, S., Tal, A., and Katz, S. 2002. Metamorphosis of polyhedral surfaces using decomposition. Computer Graphics Forum 21, 3, 219--228.
• 28: Srinark, T., and Kambhamettu, C. 2003. A novel method for 3D surface mesh segmentation. In Proceedings of the 6th Intl. Conf. on Computers, Graphics and Imaging, 212--217.
• 29: Surazhsky, V., Alliez, P., and Gotsman, C. 2003. Isotropic remeshing of surfaces: a local parameterization approach. In Proceedings of 12th Intl. Meshing Roundtable, 215--224.
• 30: Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S., and Hoppe, H. 2005. Fast exact and approximate geodesics on meshes. In Proceedings of SIGGRAPH, 553--560.
• 31: Várady, T., Martin, R. R., and Cox, J. 1997. Reverse engineering of geometric models - an introduction. Computer Aided Design 29, 4, 255--268.
• 32: Andrew P. Witkin , Paul S. Heckbert, Using particles to sample and control implicit surfaces, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.269-277, July 1994 [doi>10.1145/192161.192227]
• 33: Kenong Wu , Martin D. Levine, 3D Part Segmentation Using Simulated Electrical Charge Distributions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.11, p.1223-1235, November 1997 [doi>10.1109/34.632982 ]
• 34: Hitoshi Yamauchi , Seungyong Lee , Yunjin Lee , Yutaka Ohtake , Alexander Belyaev , Hans-Peter Seidel, Feature Sensitive Mesh Segmentation with Mean Shift, Proceedings of the International Conference on Shape Modeling and Applications 2005 (SMI' 05), p.238--245, June 13-17, 2005 [doi>10.1109/SMI.2005.21]
• 35: Zhang, Y., Paik, J., Koschan, A., Abidi, M. A., and Gorsich, D. 2002. A simple and efficient algorithm for part decomposition of 3-D triangulated models based on curvature analysis. In Proceedings of Intl. Conf. on Image Processing, III, 273--276.
• 36: Zuckerberger, E., Tal, A., and Shlafman, S. 2002. Polyhedral surface decomposition with applications. Computers & Graphics 26, 5, 733--743.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Texture

General Terms:
Algorithms, Theory