“A benchmark for 3D mesh segmentation” by Chen, Funkhouser and Golovinskiy

This paper describes a benchmark for evaluation of 3D mesh segmentation salgorithms. The benchmark comprises a data set with 4,300 manually generated segmentations for 380 surface meshes of 19 different object categories, and it includes software for analyzing 11 geometric properties of segmentations and producing 4 quantitative metrics for comparison of segmentations. The paper investigates the design decisions made in building the benchmark, analyzes properties of human-generated and computer-generated segmentations, and provides quantitative comparisons of 7 recently published mesh segmentation algorithms. Our results suggest that people are remarkably consistent in the way that they segment most 3D surface meshes, that no one automatic segmentation algorithm is better than the others for all types of objects, and that algorithms based on non-local shape features seem to produce segmentations that most closely resemble ones made by humans.

1. Agathos, A., Pratikakis, I., Perantonis, S., Sapidis, N., and Azariadis, P. 2007. 3d mesh segmentation methodologies for cad applications. 827–841.Google Scholar
2. Amazon, 2008. Mechanical turk. www.mturk.com.Google Scholar
3. Attene, M., Katz, S., Mortara, M., Patane, G., Spagnuolo, M., and Tal, A. 2006. Mesh segmentation – a comparative study. In SMI ’06: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006, IEEE Computer Society, Washington, DC, USA, 7. Google ScholarDigital Library
4. Attene, M., Falcidieno, B., and Spagnuolo, M. 2006. Hierarchical mesh segmentation based on fitting primitives. Vis. Comput. 22, 3, 181–193. Google ScholarDigital Library
5. Benhabiles, H., Vandeborre, J., Lavoue, G., and Daoudi, M. 2009. A framework for the objective evaluation of segmentation algorithms using a ground-truth of human segmented 3d-models. In Shape Modeling International.Google Scholar
6. Biasotti, S., Marini, S., Mortara, M., and Patanè, G. 2003. An overview on properties and efficacy of topological skeletons in shape modelling. In Shape Modeling International, 245–256, 297. Google ScholarDigital Library
7. Biederman, I. 1987. Recognition-by-components: A theory of human image understanding. Psychological Review 94, 2, 115–147.Google ScholarCross Ref
8. 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
9. Correia, P., and Pereira, F. 2000. Objective evaluation of relative segmentation quality. In ICIP00, Vol I: 308–311.Google Scholar
10. Everingham, M., Muller, H., and Thomas, B. T. 2002. Evaluating image segmentation algorithms using the pareto front. In ECCV ’02: Proceedings of the 7th European Conference on Computer Vision-Part IV, Springer-Verlag, London, UK, 34–48. Google ScholarDigital Library
11. Federico, M., Giordani, D., and Coletti, P. 2000. Development and evaluation of an Italian broadcast news corpus. In Second International Conference on Language Resources and Evaluation (LREC), 921–924.Google Scholar
12. Funkhouser, T., Kazhdan, M., Shilane, P., Min, P., Kiefer, W., Tal, A., Rusinkiewicz, S., and Dobkin, D. 2004. Modeling by example. ACM Trans. Graph. 23, 3, 652–663. Google ScholarDigital Library
13. Garland, M., Willmott, A., and Heckbert, P. S. 2001. Hierarchical face clustering on polygonal surfaces. In I3D ’01: Proceedings of the 2001 symposium on Interactive 3D graphics, ACM, New York, NY, USA, 49–58. Google ScholarDigital Library
14. Gelfand, N., and Guibas, L. J. 2004. Shape segmentation using local slippage analysis. In SGP ’04: Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, ACM, New York, NY, USA, 214–223. Google ScholarDigital Library
15. Giorgi, D., Biasotti, S., and Paraboschi, L., 2007. SHREC:SHape REtrieval Contest: Watertight models track, http://watertight.ge.imati.cnr.it/.Google Scholar
16. Golovinskiy, A., and Funkhouser, T. 2008. Randomized cuts for 3D mesh analysis. ACM Transactions on Graphics (Proc. SIGGRAPH ASIA) 27, 5 (Dec.). Google ScholarDigital Library
17. Gregory, A. D., State, A., Lin, M. C., Manocha, D., and Livingston, M. A. 1999. Interactive surface decomposition for polyhedral morphing. The Visual Computer 15, 9, 453–470.Google ScholarDigital Library
18. Hoffman, D. D., and Singh, M. 1997. Salience of visual parts. Cognition 63, 29–78.Google ScholarCross Ref
19. Hoffman, D. D., Richards, W., Pentl, A., Rubin, J., and Scheuhammer, J. 1984. Parts of recognition. Cognition 18, 65–96.Google ScholarCross Ref
20. Huang, Q., and Dom, B. 1995. Quantitative methods of evaluating image segmentation. In ICIP ’95: Proceedings of the 1995 International Conference on Image Processing (Vol. 3)-Volume 3, IEEE Computer Society, Washington, DC, USA, 3053. Google ScholarDigital Library
21. Katz, S., and Tal, A. 2003. Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Transactions on Graphics (Proc. SIGGRAPH) 22, 3 (July), 954–961. Google ScholarDigital Library
22. Katz, S., Leifman, G., and Tal, A. 2005. Mesh segmentation using feature point and core extraction. The Visual Computer 21, 8–10, 649–658.Google ScholarCross Ref
23. Kraevoy, V., Julius, D., and Sheffer, A. 2007. Shuffler: Modeling with interchangeable parts. In Pacific Graphics.Google Scholar
24. Lai, Y.-K., Hu, S.-M., Martin, R. R., and Rosin, P. L. 2008. Fast mesh segmentation using random walks. In Symposium on Solid and Physical Modeling, 183–191. Google ScholarDigital Library
25. Lee, Y., Lee, S., Shamir, A., Cohen-Or, D., and Seidel, H.-P. 2004. Intelligent mesh scissoring using 3D snakes. In 12th Pacific Conference on Computer Graphics and Applications (PG). Google ScholarDigital Library
26. Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21, 3, 362–371. Google ScholarDigital Library
27. Lin, H.-Y. S., Liao, H.-Y. M., and Lin, J.-C. 2007. Visual salience-guided mesh decomposition. IEEE Transactions on Multimedia 9, 1, 46–57. Google ScholarDigital Library
28. Liu, R., and Zhang, H. 2004. Segmentation of 3d meshes through spectral clustering. In PG ’04: Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, IEEE Computer Society, Washington, DC, USA, 298–305. Google ScholarDigital Library
29. Martin, D., Fowlkes, C., Tal, D., and Malik, J. 2001. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In in Proc. 8th Intl Conf. Computer Vision, 416–423.Google Scholar
30. Mortara, M., Patane, G., Spagnuolo, M., Falcidieno, B., and Rossignac, J. 2004. Blowing bubbles for the multi-scale analysis and decomposition of triangle meshes. Algorithmica (Special Issues on Shape Algorithms) 38, 2, 227–248. Google ScholarDigital Library
31. 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, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 339–344. Google ScholarDigital Library
32. Over, P., Leung, C., Ip, H., and Grubinger, M. 2004. Multimedia retrieval benchmarks. IEEE MultiMedia 11, 2, 80–84. Google ScholarDigital Library
33. Rand, W. 1971. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association 66, 846–850.Google ScholarCross Ref
34. Robbiano, F., Attene, M., Spagnuolo, M., and Falcidieno, B. 2007. Part-based annotation of virtual 3d shapes. In CW ’07: Proceedings of the 2007 International Conference on Cyberworlds, IEEE Computer Society, Washington, DC, USA, 427–436. Google ScholarDigital Library
35. Russell, B. C., Torralba, A., Murphy, K. P., and Freeman, W. T. 2008. Labelme: A database and web-based tool for image annotation. Int. J. Comput. Vision 77, 1–3, 157–173. Google ScholarDigital Library
36. Shamir, A. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum 28, 6, 1539–1556.Google ScholarCross Ref
37. 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
38. Shilane, P., Min, P., Kazhdan, M., and Funkhouser, T. 2004. The princeton shape benchmark. In Shape Modeling International, IEEE Computer Society, Washington, DC, USA, 167–178. Google ScholarDigital Library
39. Shlafman, S., Tal, A., and Katz, S., 2002. Metamorphosis of polyhedral surfaces using decomposition.Google Scholar
40. Smeaton, A. F., Kraaij, W., and Over, P. 2004. TREC video retrieval evaluation: a case study and status report. In Coupling Approaches, Coupling Media and Coupling Languages for Information Retrieval (RIAO).Google Scholar
41. Unnikrishnan, R., Pantofaru, C., and Hebert, M. 2005. A measure for objective evaluation of image segmentation algorithms. In Proceedings of the 2005 IEEE Conference on Computer Vision and Pattern Recognition (CVPR ’05), Workshop on Empirical Evaluation Methods in Computer Vision, vol. 3, 34–41. Google ScholarDigital Library
42. Wu, H.-Y., Pan, C., Pan, J., Yang, Q., and Ma, S. 2007. A sketch-based interactive framework for real-time mesh segmentation. In Computer Graphics International.Google Scholar
43. Zhang, H., Fritts, J. E., and Goldman, S. A. 2008. Image segmentation evaluation: A survey of unsupervised methods. Comput. Vis. Image Underst. 110, 2, 260–280. Google ScholarDigital Library
44. Zhang, Y. 1996. A survey on evaluation methods for image segmentation. PR 29, 8 (August), 1335–1346.Google Scholar
45. Zöckler, M., Stalling, D., and Hege, H.-C. 2000. Fast and intuitive generation of geometric shape transitions. The Visual Computer 16(5), 241–253.Google ScholarCross Ref
46. Zuckerberger, E. 2002. Polyhedral surface decomposition with applications. Computers and Graphics 26, 5 (October), 733–743.Google ScholarCross Ref