“Randomized cuts for 3D mesh analysis”
Conference:
Type(s):
Title:
- Randomized cuts for 3D mesh analysis
Session/Category Title: Mesh processing
Presenter(s)/Author(s):
Abstract:
The goal of this paper is to investigate a new shape analysis method based on randomized cuts of 3D surface meshes. The general strategy is to generate a random set of mesh segmentations and then to measure how often each edge of the mesh lies on a segmentation boundary in the randomized set. The resulting “partition function” defined on edges provides a continuous measure of where natural part boundaries occur in a mesh, and the set of “most consistent cuts” provides a stable list of global shape features. The paper describes methods for generating random distributions of mesh segmentations, studies sensitivity of the resulting partition functions to noise, tessellation, pose, and intra-class shape variations, and investigates applications in mesh visualization, segmentation, deformation, and registration.
References:
1. Agathos, A., Pratikakis, I., Perantonis, S., Sapidis, N., and Azariadis, P. 2007. 3D mesh segmentation methodologies for CAD applications. Computer-Aided Design & Applications 4, 6, 827–841.Google Scholar
2. Allen, B., Curless, B., and Popović, Z. 2003. The space of human body shapes: reconstruction and parameterization from range scans. In SIGGRAPH ’03: ACM SIGGRAPH 2003 Papers, ACM Press, New York, NY, USA, 587–594. Google Scholar
3. Antini, G., Berretti, S., Del Bimbo, A., and Pala, P. 2005. 3D mesh partitioning for retrieval by parts applications. In Multimedia and Expo.Google Scholar
4. Attene, M., Katz, S., Mortara, M., Patane, G., and a nd A. Tal, M. S. 2006. Mesh segmentation — a comparative study. In SMI ’06: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006 (SMI’06), IEEE Computer Society, Washington, DC, USA, 7. Google Scholar
5. Attene, M., Falcidieno, B., and Spagnuolo, M. 2006. Hierarchical mesh segmentation based on fitting primitives. The Visual Computer 22, 3, 181–193. Google ScholarDigital Library
6. Attene, M., Robbiano, F., Spagnuolo, M., and Falcidieno, B. 2007. Semantic annotation of 3D surface meshes based on feature characterization. Lecture Notes in Computer Science 4816, 126–139. Google ScholarDigital Library
7. Audette, M. A., Ferrie, F. P., and Peters, T. M. 2000. An algorithmic overview of surface registration techniques for medical imaging. Medical Image Analysis 4, 3, 201–217.Google ScholarCross Ref
8. Botsch, M., Pauly, M., Gross, M., and Kobbelt, L. 2006. Primo: coupled prisms for intuitive surface modeling. In SGP ’06: Proceedings of the fourth Eurographics symposium on Geometry processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 11–20. Google ScholarDigital Library
9. Chazelle, B., Dobkin, D., Shourhura, N., and Tal, A. 1997. Strategies for polyhedral surface decomposition: An experimental study. Computational Geometry: Theory and Applications 7, 4–5, 327–342. Google ScholarDigital Library
10. Edmonds, J., and Karp, R. M. 1972. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM 19, 2. Google ScholarDigital Library
11. Funkhouser, T., Kazhdan, M., Shilane, P., Min, P., Kiefer, W., Tal, A., Rusinkiewicz, S., and Dobkin, D. 2004. Modeling by example. ACM Transactions on Graphics (Siggraph 2004) (Aug.). Google Scholar
12. Garland, M., and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In Proceedings of SIGGRAPH 1997, Computer Graphics Proceedings, Annual Conference Series, 209–216. Google Scholar
13. Garland, M., Willmott, A., and Heckbert, P. 2001. Hierarchical face clustering on polygonal surfaces. In ACM Symposium on Interactive 3D Graphics, 49–58. Google Scholar
14. Gdalyahu, Y., Weinshall, D., and Werman, M. 2001. Self-organization in vision: Stochastic clustering for image segmentation, perceptual grouping, and image database organization. IEEE Transactions on Pattern Analysis and Machine Intelligence 23, 10, 1053–1074. Google ScholarDigital Library
15. Gelfand, N., and Guibas, L. 2004. Shape segmentation using local slippage analysis. In Symposium on Geometry Processing, 214–223. Google Scholar
16. Giorgi, D., Biasotti, S., and Paraboschi, L. 2007. SHape REtrieval Contest 2007: Watertight models track. In SHREC competition.Google Scholar
17. Hilaga, M., Shinagawa, Y., Kohmura, T., and Kunii, T. L. 2001. Topology matching for fully automatic similarity estimation of 3D shapes. In Proceedings of SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, 203–212. Google Scholar
18. Inoue, K., Takayuki, I., Atsushi, Y., Tomotake, F., and Kenji, S. 2001. Face clustering of a large-scale cad model for surface mesh generation. Computer-Aided Design 33, 251–261.Google ScholarCross Ref
19. Karger, D. R., and Stein, C. 1996. A new approach to the minimum cut problem. Journal of the ACM 43, 4, 601–640. Google ScholarDigital Library
20. Katz, S., and Tal, A. 2003. Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Transactions on Graphics (TOG) 22, 3, 954–961. Google ScholarDigital Library
21. Katz, S., Leifman, G., and Tal, A. 2005. Mesh segmentation using feature point and core extraction. The Visual Computer (Pacific Graphics) 21, 8–10 (October), 649–658.Google ScholarCross Ref
22. Lai, Y., Hu, S., Martin, R., and Rosin, P. 2008. Fast mesh segmentation using random walks. In ACM Symposium on Solid and Physical Modeling. Google Scholar
23. Lee, C. H., Varshney, A., and Jacobs, D. W. 2005. Mesh saliency. In SIGGRAPH ’05: ACM SIGGRAPH 2005 Papers, ACM, New York, NY, USA, 659–666. Google Scholar
24. Lee, Y., Lee, S., Shamir, A., Cohen-Or, D., and Seidel, H. 2005. Mesh scissoring with minima rule and part salience. Computer-Aided Geometric Design 22, 5, 444–465. Google ScholarDigital Library
25. Li, X., Woon, T. W., Tan, T. S., and Huang, Z. 2001. Decomposing polygon meshes for interactive applications. In Proc. Symposium on Interactive 3D Graphics, ACM, 35–42. Google Scholar
26. Lin, H., Liao, H., and Lin, J. 2004. Visual salience-guided mesh decomposition. In IEEE Int. Workshop on Multimedia Signal Processing, 331–334.Google Scholar
27. Lipman, Y., Sorkine, O., Levin, D., and Cohen-Or, D. 2005. Linear rotation-invariant coordinates for meshes. ACM Trans. Graph. 24, 3, 479–487. Google ScholarDigital Library
28. Liu, R., and Zhang, H. 2004. Segmentation of 3d meshes through spectral clustering. In Proceedings of the 12th Pacific Conference on Computer Graphics and Applications. Google ScholarDigital Library
29. Mangan, A., and Whitaker, R. 1999. Partitioning 3D surface meshes using watershed segmentation. IEEE Transactions on Visualization and Computer Graphics 5, 4, 308–321. Google ScholarDigital Library
30. Miller, G. 1994. Efficient algorithms for local and global accessibility shading. In SIGGRAPH ’94: Proceedings of the 21st annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 319–326. Google Scholar
31. Mortara, M., Patane, G., Spagnuolo, M., Falcidieno, B., and Rossignac, J. 2003. Blowing bubbles for multi-scale analysis and decomposition of triangle meshes. Algorithmica 38, 1, 227–248. Google ScholarDigital Library
32. Mortara, M., Patan, G., Spagnuolo, M., Falcidieno, B., and Rossignac, J. 2004. Plumber: a method for a multi-scale decomposition of 3D shapes into tubular primitives and bodies. In ACM Symposium on Solid Modeling and Applications. Google ScholarDigital Library
33. Popa, T., Julius, D., and Sheffer, A. 2006. Material-aware mesh deformations. In SMI ’06: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006, IEEE Computer Society, Washington, DC, USA, 22. Google ScholarDigital Library
34. Schreiner, J., Asirvatham, A., Praun, E., and Hoppe, H. 2004. Inter-surface mapping. ACM Transactions on Graphics (Proc. SIGGRAPH 2004) 23, 3, 870–877. Google Scholar
35. Shamir, A. 2006. Segmentation and shape extraction of 3d boundary meshes (state-of-the-art report). In Eurographics, 137–149.Google Scholar
36. 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
37. Shi, J., and Malik, J. 2000. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22, 8, 888–905. Google ScholarDigital Library
38. Shlafman, S., Tal, A., and Katz, S. 2002. Metamorphosis of polyhedral surfaces using decomposition. In Eurographics 2002, 219–228.Google Scholar
39. Wu, K., and Levine, M. 1997. 3D part segmetnation using simulationed electrical charge distributions. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI) 19, 11, 1223–1235. Google ScholarDigital Library
40. Yu, S. X., and Shi, J. 2003. Multiclass spectral clustering. In International Conference on Computer Vision, 313–319. Google ScholarDigital Library
41. Zhang, H., van Kaick, O., and Dyer, R. 2007. Spectral methods for mesh processing and analysis. In Eurographics State of the Art Report.Google Scholar
42. Zhukov, S., Inoes, A., and Kronin, G. 1998. An ambient light illumination model. In Rendering Techniques, 45–56.Google Scholar
43. Zuckerberger, E., Tal, A., and Shlafman, S. 2002. Polyhedral surface decomposition with applications. Computers & Graphics 26, 5, 733–743.Google Scholar
