×

Rapid and effective segmentation of 3D models using random walks. (English) Zbl 1205.65090

Summary: 3D models are now widely available for use in various applications. The demand for automatic model analysis and understanding is ever increasing. Model segmentation is an important step towards model understanding, and acts as a useful tool for different model 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 model segmentation. This method is extremely efficient, and scales almost linearly with the number of faces, and the number of regions. For models of moderate size, interactive performance is achieved with commodity PCs. We demonstrate that this method can be applied to both triangle meshes and point cloud data. It is easy-to-implement, robust to noise in the model, and yields results suitable for downstream applications for both graphical and engineering models.

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)
60G50 Sums of independent random variables; random walks
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry

Software:

ANN; TAUCS
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Attene, M., Falcidieno, B., Katz, S., Mortara, M., Patane, G., Spagnuolo, M., Tal, A., 2006a. Mesh segmentation—a comparative study. In: Proc. IEEE Int’l Conference on Shape Modeling and Applications, pp. 7-18; Attene, M., Falcidieno, B., Katz, S., Mortara, M., Patane, G., Spagnuolo, M., Tal, A., 2006a. Mesh segmentation—a comparative study. In: Proc. IEEE Int’l Conference on Shape Modeling and Applications, pp. 7-18
[2] Attene, M.; Falcidieno, B.; Spagnuolo, M., Hierarchical mesh segmentation based on fitting primitives, The Visual Computer, 22, 3, 181-193 (2006)
[3] Benko, P., Várady, T., 2002. Direct segmentation of smooth, multiple point regions. In: Proc. Geometric Modeling and Processing, pp. 169-178; Benko, P., Várady, T., 2002. Direct segmentation of smooth, multiple point regions. In: Proc. Geometric Modeling and Processing, pp. 169-178
[4] Doyle, P. G.; Snell, J. L., Random Walks and Electric Networks, Carus Mathematical Monographs, vol. 22 (1984), The Mathematical Association of America · Zbl 0583.60065
[5] Edelsbrunner, H.; Harer, J.; Zomorodian, A., Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds, Discrete Computational Geometry, 30, 1, 87-107 (2003) · Zbl 1029.57023
[6] Funkhouser, T., Kazhdan, M., Shilane, P., Min, P., Kiefer, W., Tal, A., Rusinkiewicz, S., Dobkin, D., 2004. Modeling by examples. In: Proc. ACM SIGGRAPH, pp. 652-663; Funkhouser, T., Kazhdan, M., Shilane, P., Min, P., Kiefer, W., Tal, A., Rusinkiewicz, S., Dobkin, D., 2004. Modeling by examples. In: Proc. ACM SIGGRAPH, pp. 652-663
[7] Gelfand, N., Guibas, L.J., 2004. Shape segmentation using local slippage analysis. In: Proc. Eurographics Symposium on Geometry Processing, pp. 219-228; Gelfand, N., Guibas, L.J., 2004. Shape segmentation using local slippage analysis. In: Proc. Eurographics Symposium on Geometry Processing, pp. 219-228
[8] Grady, L., Random walks for image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 28, 11, 1768-1783 (2006)
[9] Hoffmann, D.; Richards, W., Parts of recognition, Cognition, 18, 65-96 (1984)
[10] Hoffmann, D.; Singh, M., Salience of visual parts, Cognition, 63, 29-78 (1997)
[11] Katz, S.; Leifman, G.; Tal, A., Mesh segmentation using feature point and core extraction, The Visual Computer, 21, 8-10, 865-875 (2005)
[12] Katz, S.; Tal, A., Hierarchical mesh decomposition using fuzzy clustering and cuts, ACM Transactions on Graphics, 22, 3, 954-961 (2003)
[13] Lai, Y.-K., Zhou, Q.-Y., Hu, S.-M., Martin, R.R., 2006. Feature sensitive mesh segmentation. In: Proc. ACM Symposium on Solid and Physical Modeling, pp. 17-25; Lai, Y.-K., Zhou, Q.-Y., Hu, S.-M., Martin, R.R., 2006. Feature sensitive mesh segmentation. In: Proc. ACM Symposium on Solid and Physical Modeling, pp. 17-25
[14] Lai, Y.-K.; Zhou, Q.-Y.; Hu, S.-M.; Wallner, J.; Pottmann, H., Robust feature classification and editing, IEEE Transactions on Visualization and Computer Graphics, 13, 1, 34-45 (2007)
[15] Lai, Y.-K., Hu, S.-M., Martin, R.R., Rosin, P.L., 2008. Fast mesh segmentation using random walks. In: Proc. ACM Symposium on Solid and Physical Modeling, pp. 183-191; Lai, Y.-K., Hu, S.-M., Martin, R.R., Rosin, P.L., 2008. Fast mesh segmentation using random walks. In: Proc. ACM Symposium on Solid and Physical Modeling, pp. 183-191
[16] Lee, Y., Lee, S., Shamir, A., Cohen-Or, D., Seidel, H.-P., 2004. Intelligent mesh scissoring using 3D snakes. In: Proc. Pacific Graphics, pp. 279-287; Lee, Y., Lee, S., Shamir, A., Cohen-Or, D., Seidel, H.-P., 2004. Intelligent mesh scissoring using 3D snakes. In: Proc. Pacific Graphics, pp. 279-287
[17] Lee, Y.; Lee, S.; Shamir, A.; Cohen-Or, D.; Seidel, H.-P., Mesh scissoring with minima rule and part salience, Computer Aided Geometric Design, 22, 5, 444-465 (2005) · Zbl 1205.65120
[18] Li, X., Woon, T.W., Tan, T.S., Huang, Z., 2001. Decomposing polygon meshes for interactive applications. In: Proc. ACM Symposium on Interactive 3D Graphics, pp. 35-42; Li, X., Woon, T.W., Tan, T.S., Huang, Z., 2001. Decomposing polygon meshes for interactive applications. In: Proc. ACM Symposium on Interactive 3D Graphics, pp. 35-42
[19] Liu, R., Jain, V., Zhang, H., 2006. Subsampling for efficient spectral mesh processing. In: Lecture Notes in Computer Science, pp. 172-184; Liu, R., Jain, V., Zhang, H., 2006. Subsampling for efficient spectral mesh processing. In: Lecture Notes in Computer Science, pp. 172-184
[20] Liu, R., Zhang, H., 2004. Segmentation of 3D meshes through spectral clustering. In: Proc. Pacific Graphics, pp. 298-305; Liu, R., Zhang, H., 2004. Segmentation of 3D meshes through spectral clustering. In: Proc. Pacific Graphics, pp. 298-305
[21] Mangan, A. P.; Whitaker, R. T., Partitioning 3D surface meshes using watershed segmentation, IEEE Transactions on Visualization and Computer Graphics, 5, 4, 308-321 (1999)
[22] Mitani, J., Suzuki, H., 2004. Making papercraft toys from meshes using strip-based approximate unfolding. In: Proc. ACM SIGGRAPH, pp. 259-263; Mitani, J., Suzuki, H., 2004. Making papercraft toys from meshes using strip-based approximate unfolding. In: Proc. ACM SIGGRAPH, pp. 259-263
[23] Mount, D.; Arya, S., ANN: a library for approximate nearest neighbors searching
[24] Pauly, M., Gross, M., Kobbelt, L., 2002. Efficient simplification and point-sampled surfaces. In: Proc. IEEE Visualization, pp. 163-170; Pauly, M., Gross, M., Kobbelt, L., 2002. Efficient simplification and point-sampled surfaces. In: Proc. IEEE Visualization, pp. 163-170
[25] Reniers, D., Telea, A., 2007. Skeleton-based hierarchical shape segmentation. In: Proc. Shape Modeling International, pp. 179-188; Reniers, D., Telea, A., 2007. Skeleton-based hierarchical shape segmentation. In: Proc. Shape Modeling International, pp. 179-188
[26] Sapidis, N. S.; Besl, P. J., Direct construction of polynomial surfaces from dense range images through region growing, ACM Transactions on Graphics, 14, 3, 171-200 (1995)
[27] Shamir, A., A survey on mesh segmentation techniques, Computer Graphics Forum, 27, 6, 1539-1556 (2008) · Zbl 1162.68769
[28] Shamir, A., Shapira, L., Cohen-Or, D., Goldenthal, R., 2004. Geodesic mean shift. In: Proc. 5th Korea-Israel Conf. Geometric Modeling and Computer Graphics, pp. 51-56; Shamir, A., Shapira, L., Cohen-Or, D., Goldenthal, R., 2004. Geodesic mean shift. In: Proc. 5th Korea-Israel Conf. Geometric Modeling and Computer Graphics, pp. 51-56
[29] Sharf, A.; Blumenkrants, M.; Shamir, A.; Cohen-Or, D., SnapPaste: An interactive technique for easy mesh composition, The Visual Computer, 22, 9-11, 835-844 (2006)
[30] Shlafman, S.; Tal, A.; Katz, S., Metamorphosis of polyhedral surfaces using decomposition, Computer Graphics Forum, 21, 3, 219-229 (2002)
[31] Sun, X.; Rosin, P. L.; Martin, R. R.; Langbein, F. C., Random walks for feature-preserving mesh denoising, Computer Aided Geometric Design, 25, 7, 437-456 (2008) · Zbl 1172.65349
[32] Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S., Hoppe, H., 2005. Fast exact and approximate geodesics on meshes. In: Proc. ACM SIGGRAPH, pp. 553-560; Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S., Hoppe, H., 2005. Fast exact and approximate geodesics on meshes. In: Proc. ACM SIGGRAPH, pp. 553-560
[33] Toledo, S.; Chen, D.; Rotkin, V., TAUCS: A library of sparse linear solvers, ver. 2.2
[34] Tomasi, C., Manduchi, R., 1998. Bilateral filter for gray and color images. In: Proc. IEEE Int’l Conf. on Computer Vision, pp. 839-846; Tomasi, C., Manduchi, R., 1998. Bilateral filter for gray and color images. In: Proc. IEEE Int’l Conf. on Computer Vision, pp. 839-846
[35] Várady, T.; Martin, R. R.; Cox, J., Reverse engineering of geometric models—an introduction, Computer-Aided Design, 29, 4, 255-268 (1997)
[36] Várady, T., Automatic extraction of surface structures in digital shape reconstruction, Computer-Aided Design, 39, 5, 379-388 (2007)
[37] Witkin, A., Heckbert, P., 1994. Using particles to sample and control implicit surfaces In: Proc. ACM SIGGRAPH, pp. 269-277; Witkin, A., Heckbert, P., 1994. Using particles to sample and control implicit surfaces In: Proc. ACM SIGGRAPH, pp. 269-277
[38] Yamachi, H., Lee, S., Lee, Y., Ohtake, Y., 2005. Feature sensitive mesh segmentation with mean shift. In: Proc. Shape Modeling International, pp. 236-243; Yamachi, H., Lee, S., Lee, Y., Ohtake, Y., 2005. Feature sensitive mesh segmentation with mean shift. In: Proc. Shape Modeling International, pp. 236-243
[39] Yang, Y.-L., Lai, Y.-K., Hu, S.-M., Pottmann, H., 2006. Robust principal curvatures on multiple scales. In: Proc. Eurographics Symposium on Geometry Processing, pp. 223-226; Yang, Y.-L., Lai, Y.-K., Hu, S.-M., Pottmann, H., 2006. Robust principal curvatures on multiple scales. In: Proc. Eurographics Symposium on Geometry Processing, pp. 223-226
[40] Zuckerberger, E.; Tal, A.; Shlafman, S., Polyhedral surface decomposition with applications, Computers & Graphics, 26, 5, 733-743 (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.