Fast mesh segmentation using random walks

ABSTRACT

3D mesh models are now widely available for use in various applications. The demand for automatic model analysis and understanding is ever increasing. Mesh segmentation is an important step towards model understanding, and acts as a useful tool for different mesh processing applications, e.g. reverse engineering and modeling by example. We extend a random walk method used previously for image segmentation to give algorithms for both interactive and automatic mesh segmentation. This method is extremely efficient, and scales almost linearly with increasing number of faces. For models of moderate size, interactive performance is achieved with commodity PCs. It is easy-to-implement, robust to noise in the mesh, and yields results suitable for downstream applications for both graphical and engineering models.

REFERENCES

• 1: M. Attene , S. Katz , M. Mortara , G. Patane , M. Spagnuolo , A. Tal, Mesh Segmentation - A Comparative Study, Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006, p.7, June 14-16, 2006 [doi>10.1109/SMI.2006.24]
• 2: Marco Attene , Bianca Falcidieno , Michela Spagnuolo, Hierarchical mesh segmentation based on fitting primitives, The Visual Computer: International Journal of Computer Graphics, v.22 n.3, p.181-193, March 2006 [doi>10.1007/s00371-006-0375-x]
• 3: Pál Benkó , Tamás Várady, Direct Segmentation of Smooth, Multiple Point Regions, Proceedings of the Geometric Modeling and Processing — Theory and Applications (GMP'02), p.169, July 10-12, 2002
• 4: Doyle, P. G., and Snell, J. L. 1984. Random walks and eletric networks. No. 22 in Carus Mathematical Monographs. The Mathematical Association of America.
• 5: Edelsbrunner, H., Harer, J., and Zomorodian, A. 2003. Hierarchical morse-smale complexes for piecewise linear 2-manifolds. Discrete Computational Geometry 30, 1, 87--107.
• 6: Thomas Funkhouser , Michael Kazhdan , Philip Shilane , Patrick Min , William Kiefer , Ayellet Tal , Szymon Rusinkiewicz , David Dobkin, Modeling by example, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 7: 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]
• 8: Leo Grady, Random Walks for Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.11, p.1768-1783, November 2006 [doi>10.1109/TPAMI.2006.233]
• 9: Hoffmann, D., and Richards, W. 1984. Parts of recognition. Cognition 18, 65--96.
• 10: Hoffmann, D., and Singh, M. 1997. Salience of visual parts. Cognition 63, 29--78.
• 11: Sagi Katz , Ayellet Tal, Hierarchical mesh decomposition using fuzzy clustering and cuts, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 12: Katz, S., Leifman, G., and Tal, A. 2005. Mesh segmentation using feature point and core extraction. The Visual Computer 21, 8--10, 865--875.
• 13: Yu-Kun Lai , Qian-Yi Zhou , Shi-Min Hu , Ralph R. Martin, Feature sensitive mesh segmentation, Proceedings of the 2006 ACM symposium on Solid and physical modeling, June 06-08, 2006, Cardiff, Wales, United Kingdom [doi>10.1145/1128888.1128891]
• 14: Yu-Kun Lai , Qian-Yi Zhou , Shi-Min Hu , Johannes Wallner , Helmut Pottmann, Robust Feature Classification and Editing, IEEE Transactions on Visualization and Computer Graphics, v.13 n.1, p.34-45, January 2007 [doi>10.1109/TVCG.2007.19]
• 15: 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, p.279-287, October 06-08, 2004
• 16: Yunjin Lee , Seungyong Lee , Ariel Shamir , Daniel Cohen-Or , Hans-Peter Seidel, Mesh scissoring with minima rule and part salience, Computer Aided Geometric Design, v.22 n.5, p.444-465, July 2005 [doi>10.1016/j.cagd.2005.04.002]
• 17: Xuetao Li , Tong Wing Woon , Tiow Seng Tan , 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, p.298-305, October 06-08, 2004
• 19: Liu, R., Jain, V., and Zhang, H. 2006. Subsampling for efficient spectral mesh processing. Lecture Notes in Computer Science, 172--184.
• 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: Jun Mitani , Hiromasa Suzuki, Making papercraft toys from meshes using strip-based approximate unfolding, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 22: Mount, D., and Arya, S., 2005. ANN: a library for approximate nearest neighbors searching. url: http://www.cs.umd.edu/~mount/ann/.
• 23: Dennie Reniers , Alexandru Telea, Skeleton-based Hierarchical Shape Segmentation, Proceedings of the IEEE International Conference on Shape Modeling and Applications 2007, p.179-188, June 13-15, 2007 [doi>10.1109/SMI.2007.33]
• 24: Nickolas S. Sapidis , Paul J. Besl, Direct construction of polynomial surfaces from dense range images through region growing, ACM Transactions on Graphics (TOG), v.14 n.2, p.171-200, April 1995 [doi>10.1145/221659.221672]
• 25: Shamir, A., Shapira, L., Cohen-Or, D., and Golden-Thal, R. 2004. Geodesic mean shift. In Proc. 5th Korea-Israel Conf. Geometric Modeling and Computer Graphics, 51--56.
• 26: Sharf, A., Blumenkrants, M., Shamir, A., and Cohen-Or, D. 2006. Snappaste: an interactive technique for easy mesh composition. The Visual Computer 22, 9--11, 835--844.
• 27: Shlafman, S., Tal, A., and Katz, S. 2002. Metamorphosis of polyhedral surfaces using decomposition. Computer Graphics Forum 21, 3, 219--229.
• 28: Xianfang Sun , Paul L. Rosin , Ralph R. Martin , Frank C. Langbein, Random walks for mesh denoising, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China [doi>10.1145/1236246.1236252]
• 29: Vitaly Surazhsky , Tatiana Surazhsky , Danil Kirsanov , Steven J. Gortler , Hugues Hoppe, Fast exact and approximate geodesics on meshes, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 30: Toledo, S., Chen, D., and Rotkin, V., 2003. TAUCS: A library of sparse linear solvers, ver. 2.2 url: http://www.tau.ac.il/~stoledo/taucs/.
• 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: Tamás Várady , Michael A. Facello , Zsolt Terék, Automatic extraction of surface structures in digital shape reconstruction, Computer-Aided Design, v.39 n.5, p.379-388, May, 2007 [doi>10.1016/j.cad.2007.02.011]
• 33: 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]
• 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, p.238--245, June 13-17, 2005 [doi>10.1109/SMI.2005.21]
• 35: Yong-Liang Yang , Yu-Kun Lai , Shi-Min Hu , Helmut Pottmann, Robust principal curvatures on multiple scales, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 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

Keywords:
interactive, mesh segmentation, random walks