“Schelling points on 3D surface meshes” by Chen, Saparov, Pang and Funkhouser

  • ©Xiaobai Chen, Abulhair Saparov, Bill Pang, and Thomas (Tom) A. Funkhouser




    Schelling points on 3D surface meshes



    This paper investigates “Schelling points” on 3D meshes, feature points selected by people in a pure coordination game due to their salience. To collect data for this investigation, we designed an online experiment that asked people to select points on 3D surfaces that they expect will be selected by other people. We then analyzed properties of the selected points, finding that: 1) Schelling point sets are usually highly symmetric, and 2) local curvature properties (e.g., Gauss curvature) are most helpful for identifying obvious Schelling points (tips of protrusions), but 3) global properties (e.g., segment centeredness, proximity to a symmetry axis, etc.) are required to explain more subtle features. Based on these observations, we use regression analysis to combine multiple properties into an analytical model that predicts where Schelling points are likely to be on new meshes. We find that this model benefits from a variety of surface properties, particularly when training data comes from examples in the same object class.


    1. Alexa, M. 2000. Merging polyhedral shapes with scattered features. Visual Computer 16, 26–37.Google ScholarDigital Library
    2. Amazon, 2009. Mechanical turk. http://www.mturk.com.Google Scholar
    3. Attneave, F. 1954. Some informational aspects of visual perception. Psychological Review 61, 3.Google ScholarCross Ref
    4. Breiman, L. 2001. Random forests. Machine Learning 45, 1, 5–32. Google ScholarDigital Library
    5. Bronstein, A., Bronstein, M., and Kimmel, R. 2006. Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching. Proceedings of the National Academy of Science, 1168–1172.Google Scholar
    6. Bronstein, A., Bronstein, M., Bustos, B., Castellani, U., Crisani, M., Falcidieno, B., Guibas, L., Kokkinos, I., Murino, V., Ovsjanikov, M., Patane, G., Sipiran, I., Spagnuolo, M., and Sun, J. 2010. SHREC 2011: robust feature detection and description benchmark. In Eurographics Workshop on 3D Object Retrieval. Google ScholarDigital Library
    7. Castellani, U., Cristani, M., Fantoni, S., and Murino, V. 2008. Sparse points matching by combining 3d mesh saliency with statistical descriptors. Computer Graphics Forum 27, 2, 643–652.Google ScholarCross Ref
    8. Chen, X., Golovinskiy, A., and Funkhouser, T. 2009. A benchmark for 3D mesh segmentation. ACM Transactions on Graphics (Proc. SIGGRAPH) 28, 3 (Aug.). Google ScholarDigital Library
    9. Chua, C., and Jarvis, R. 1996. Point signatures: A new representation for 3D object recognition. International Journal of Computer Vision 25, 1, 63–85. Google ScholarDigital Library
    10. Cole, F., Golovinskiy, A., Limpaecher, A., Barros, H. S., Finkelstein, A., Funkhouser, T., and Rusinkiewicz, S. 2008. Where do people draw lines? ACM Transactions on Graphics (Proc. SIGGRAPH) 27, 3 (Aug.). Google ScholarDigital Library
    11. Cole, F., Sanik, K., DeCarlo, D., Finkelstein, A., Funkhouser, T., and an d Manish Singh, S. R. 2009. How well do line drawings depict shape? ACM Transactions on Graphics (Proc. SIGGRAPH) 28, 3 (Aug.). Google ScholarDigital Library
    12. Funkhouser, T., and Shilane, P. 2006. Partial matching of 3d shapes with priority-driven search. In Symposium on Geometry Processing. Google ScholarDigital Library
    13. Gal, R., and Cohen-Or, D. 2006. Salient geometric features for partial shape matching and similarity. ACM Transaction on Graphics (January). Google ScholarDigital Library
    14. 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 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. Heer, J., and Bostock, M. 2010. Crowdsourcing graphical perception: Using Mechanical Turk to assess visualization design. In ACM Human Factors in Computing Systems (CHI), 203–212. Google ScholarDigital Library
    17. Hisada, M., Belyaev, A., and Kunii, T. 2002. A skeleton-based approach for detection of perceptually salient features on polygonal surfaces. Computer Graphics Forum 21, 4, 689–700.Google ScholarCross Ref
    18. Hoffman, D. D., and Singh, M. 1997. Salience of visual parts. vol. 63.Google Scholar
    19. Huang, T., Cheng, K., and Chuang, Y. 2009. A collaborative benchmark for region of interest detection algorithms. 296–303.Google Scholar
    20. Itti, L., Koch, C., and Neibur, E. 1998. A model of saliency-based visual attention for rapid scene analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence 20, 11, 1254–1259. Google ScholarDigital Library
    21. Johnson, A. 2000. Surface landmark selection and matching in natural terrain. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), vol. 2, 413–420. Using saliency in choosing spin images.Google ScholarCross Ref
    22. Kalogerakis, E., Hertzmann, A., and Singh, K. 2010. Learning 3d mesh segmentation and labeling. ACM Transactions on Graphics (proc. SIGGRAPH) 29, 3. Google ScholarDigital Library
    23. Katz, S., Leifman, G., and Tal, A. 2005. Mesh segmentation using feature point and core extraction. Visual Computer (September).Google Scholar
    24. Kim, Y., Varshney, A., and adn François Guimbretière, D. J. 2010. Mesh saliency and human eye fixations. ACM Transactions on Applied Perception 7, 2 (February). Google ScholarDigital Library
    25. Kim, V., Lipman, Y., and Funkhouser, T. 2011. Blended intrinsic maps. ACM Transactions on Graphics (SIGGRAPH 2011) (jul). Google ScholarDigital Library
    26. Ko, B., and Nam, J. 2006. Object-of-interest image segmentation based on human attention and semantic region clustering. J Opt Soc Am A Opt Image Sci Vis 23, 10 (October), 2462–2470.Google ScholarCross Ref
    27. Koch, C., and Ullman, S. 1985. Shifts in selective visual attention: towards the underlying neural circuitry. Human Neurobiology 4, 219–227.Google Scholar
    28. Kraevoy, V., and Sheffer, A. 2004. Cross-parameterization and compatible remeshing of 3d models. ACM Transactions on Graphics (Proc SIGGRAPH) 23, 3, 861–869. Google ScholarDigital Library
    29. Lee, C. H., Varshney, A., and Jacobs, D. W. 2005. Mesh saliency. ACM Transactions on Graphics (SIGGRAPH 2005) (aug). Google ScholarDigital Library
    30. Lewis, D. 1969. Convention: A Philosophical Study. Harvard University Press.Google Scholar
    31. Li, X., and Guskov, I. 2005. Multi-scale features for approximate alignment of point-based surfaces. In Symposium on Geometry Processing. Google ScholarDigital Library
    32. Li, X., and Guskov, I. 2007. 3d object recognition from range images using pyramid matching. In Workshop on 3D Representation for Recognition (3dRR).Google Scholar
    33. Lipman, Y., and Funkhouser, T. 2009. Mobius voting for surface correspondence. ACM Transactions on Graphics (SIGGRAPH 2009) (August). Google ScholarDigital Library
    34. Milanes, R., Wechsler, H., Gil, S., Bost, J., and Pun, T. 1994. Integration of bottom-up and top-down cues for visual attention using non-linear relaxation. IEEE Computer Vision and Pattern Recognition, 781–785.Google Scholar
    35. Moreels, P., and Perona, P. 2007. Evaluation of features detectors and descriptors based on 3d objects. IJCV 73, 3 (July), 263–284. Google ScholarDigital Library
    36. Novotni, M., Degener, P., and Klein, R. 2005. Correspondence generation and matching of 3d shape subparts. Tech. Rep. CG-2005-2, Universität Bonn, June.Google Scholar
    37. Parker, P. 2011. Webster’s On-line Dictionary: The Rosetta Edition. http://www.websters-online-dictionary.org.Google Scholar
    38. Privitera, C., and Stark, L. 2000. Algorithms for defining visual regions-of-interest: Comparison with eye fixations. PAMI 22, 9 (September), 970–982. Google ScholarDigital Library
    39. Rosenholtz, R. 1999. A simple saliency model predicts a number of motion popout phenomena. Vision Research 39, 19, 3157–3163.Google ScholarCross Ref
    40. Rusinkiewicz, S. 2004. Estimating curvatures and their derivatives on triangle meshes. In Symposium on 3D Data Processing, Visualization, and Transmission. Google ScholarDigital Library
    41. Santella, A., and DeCarlo, D. 2004. Robust clustering of eye movement recordings for quantification of visual interest. In Eye Tracking Research and Applications (ETRA), 27–34. Google ScholarDigital Library
    42. Schelling, T. 1960. The Strategy of Conflict. Harvard University Press.Google Scholar
    43. Schlattmann, M., Degener, P., and Klein, R. 2008. Scale space based feature point detection on surfaces. Journal of WSCG 16 (February).Google Scholar
    44. Schmid, C., Mohr, R., and Bauckhage, C. 2000. Evaluation of interest point detectors. IJCV 37, 2 (June), 151–172. Google ScholarDigital Library
    45. Sebe, N., and Lew, M. 2003. Comparing salient point detectors. Pattern Recognition Letters 24, 1-3 (January), 89–96. Google ScholarDigital Library
    46. 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
    47. Shilane, P., and Funkhouser, T. 2007. Distinctive regions of 3d surfaces. ACM Transactions on Graphics 26, 2 (June). Google ScholarDigital Library
    48. Simpson, J. 1989. Oxford English Dictionary, Second Edition. Oxford University Press. http://dictionary.oed.com.Google Scholar
    49. Sonthi, R., Kunjur, G., and Gadh, R. 1997. Shape feature determination using the curvature region representation. In Proc. Solid Modeling, ACM. Google ScholarDigital Library
    50. Stark, M., and Schiele, B. 2007. How good are local features for classes of geometric objects. 1–8.Google Scholar
    51. Sumner, R., and Popovic, J. 2004. Deformation transfer for triangle meshes. ACM Transactions on Graphics (Proc SIGGRAPH) 23, 3, 399–405. Google ScholarDigital Library
    52. Sun, J., Ovsjanikov, M., and Guibas, L. 2009. A Concise and Provably Informative Multi-Scale Signature Based on Heat Diffusion. In Computer Graphics Forum, vol. 28, Wiley Online Library, 1383–1392. Google ScholarDigital Library
    53. Tsotsos, J., Culhane, S., Wai, W., Lai, Y., Davis, N., and Nuflo, F. 1995. Modeling visual-attention via selective tuning. Artificial Intelligence 78, 1-2, 507–545. Google ScholarDigital Library
    54. van Kaick, O., Zhang, H., Hamarneh, G., and Cohen-Or, D. 2010. A survey on shape correspondence. In Proc. of Eurographics State-of-the-art Report.Google Scholar
    55. Von Ahn, L., and Dabbish, L. 2008. Designing games with a purpose. Communications of the ACM 51, 8, 58–67. Google ScholarDigital Library
    56. Witten, I. H., and Frank, E. 2005. Data mining: Practical machine learning tools and techniques, 2nd edition. Google ScholarDigital Library
    57. Xu, K., Zhang, H., Tagliasacchi, A., Liu, L., Li, G., Meng, M., and Xiong, Y. 2009. Partial intrinsic reflectional symmetry of 3d shapes. ACM Transactions on Graphics, (Proceedings SIGGRAPH Asia 2009) 28, 5, to appear. Google ScholarDigital Library
    58. Zaharescu, A., Boyer, E., Varanasi, K., and Horaud, R. 2009. Surface feature detection and description with applications to mesh matching. In CVPR.Google Scholar
    59. Zhang, E., Mischaikow, K., and Turk, G. 2005. Feature-based surface parameterization and texture mapping. ACM Transactions on Graphics 24, 1. Google ScholarDigital Library
    60. Zhang, H., Sheffer, A., Cohen-Or, D., Zhou, Q., van Kaick, O., and Tagliasacchi, A. 2008. Deformation-driven shape correspondence. Comput. Graph. Forum 27, 5, 1431–1439. Google ScholarDigital Library
    61. Zhou, Y., and Huang, Z. 2004. Decomposing polygon meshes by means of critical points. In MMM, 187–195. Google ScholarDigital Library
    62. Zuliani, M., Kenney, C., and Manjunath, B. 2004. A mathematical comparison of point detectors. In Computer Vision and Pattern Recognition Workshop, 172. Google ScholarDigital Library

ACM Digital Library Publication: