“Exploring collections of 3D models using fuzzy correspondences” by Kim, Li, Mitra, DiVerdi and Funkhouser

Large collections of 3D models from the same object class (e.g., chairs, cars, animals) are now commonly available via many public repositories, but exploring the range of shape variations across such collections remains a challenging task. In this work, we present a new exploration interface that allows users to browse collections based on similarities and differences between shapes in user-specified regions of interest (ROIs). To support this interactive system, we introduce a novel analysis method for computing similarity relationships between points on 3D shapes across a collection. We encode the inherent ambiguity in these relationships using fuzzy point correspondences and propose a robust and efficient computational framework that estimates fuzzy correspondences using only a sparse set of pairwise model alignments. We evaluate our analysis method on a range of correspondence benchmarks and report substantial improvements in both speed and accuracy over existing alternatives. In addition, we demonstrate how fuzzy correspondences enable key features in our exploration tool, such as automated view alignment, ROI-based similarity search, and faceted browsing.

1. Aiger, D., Mitra, N. J., and Cohen-Or, D. 2008. 4-points congruent sets for robust surface registration. ACM TOG 27, 3, #85, 1–10. Google ScholarDigital Library
2. Allen, B., Curless, B., and Popović, Z. 2003. The space of human body shapes: reconstruction and parameterization from range scans. In ACM SIGGRAPH, 587–594. Google ScholarDigital Library
3. Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Rodgers, J., and Davis, J. 2005. Scape: shape completion and animation of people. In ACM SIGGRAPH, 408–416. Google ScholarDigital Library
4. Besl, P. J., and McKay, N. D. 1992. A method for registration of 3-d shapes. IEEE PAMI 14, 2 (Feb.), 239–256. Google ScholarDigital Library
5. Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2006. Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching. PNAS 103, 5, 1168–1172.Google ScholarCross Ref
6. Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2008. Numerical geometry of non-rigid shapes. Springer. Google ScholarDigital Library
7. Chui, H., and Rangarajan, A. 2003. A new point matching algorithm for non-rigid registration. Comput. Vis. Image Underst. 89, 2-3, 114–141. Google ScholarDigital Library
8. Eldar, Y., Lindenbaum, M., Porat, M., and Zeevi, Y. 1997. The farthest point strategy for progressive image sampling. IJCV 40, 2, 99–121.Google Scholar
9. Fisher, M., Savva, M., and Hanrahan, P. 2011. Characterizing structural relationships in scenes using graph kernels. ACM SIGGRAPH 30, 34:1–34:12. Google ScholarDigital Library
10. Funkhouser, T., Kazhdan, M., Shilane, P., Min, P., Kiefer, W., Tal, A., Rusinkiewicz, S., and Dobkin, D. 2004. Modeling by example. ACM SIGGRAPH, 652–663. Google ScholarDigital Library
11. Giorgi, D., Biasotti, S., and Paraboschi, L. 2007. shrec:shape retrieval contest: Watertight models track. http://watertight.ge.imati.cnr.it/.Google Scholar
12. Giorgi, D., Frosini, P., Spagnuolo, M., and Falcidieno, B. 2010. 3D relevance feedback via multilevel relevance judgements. Vis. Comput. 26, 10, 1321–1338. Google ScholarDigital Library
13. Golovinskiy, A., and Funkhouser, T. 2009. Consistent segmentation of 3D models. Proc. SMI 33, 3, 262–269. Google ScholarDigital Library
14. Hearst, M. A. 2006. Clustering versus faceted categories for information exploration. Commun. ACM 49, 4 (Apr.), 59–61. Google ScholarDigital Library
15. Heath, K., Gelfand, N., Ovsjanikov, M., Aanjaneya, M., and Guibas, L. J. 2010. Image webs: Computing and exploiting connectivity in image collections. In IEEE CVPR.Google Scholar
16. Huang, Q., Koltun, V., and Guibas, L. 2011. Joint shape segmentation with linear programming. In ACM SIGGRAPH Asia, 125:1–125:12. Google Scholar
17. Kalogerakis, E., Hertzmann, A., and Singh, K. 2010. Learning 3D mesh segmentation and labeling. In ACM SIGGRAPH, 102:1–102:12. Google ScholarDigital Library
18. Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2003. Rotation invariant spherical harmonic representation of 3D shape descriptors. In Proc. SGP, 156–164. Google ScholarDigital Library
19. Kim, V. G., Lipman, Y., and Funkhouser, T. 2011. Blended intrinsic maps. In ACM SIGGRAPH, 79:1–79:12. Google ScholarDigital Library
20. Kraevoy, V., and Sheffer, A. 2004. Cross-parameterization and compatible remeshing of 3D models. In ACM SIGGRAPH, 861–869. Google ScholarDigital Library
21. Li, H., Sumner, R. W., and Pauly, M. 2008. Global correspondence optimization for non-rigid registration of depth scans. In Proc. SGP, 1421–1430. Google ScholarDigital Library
22. Lipman, Y., and Funkhouser, T. 2009. Mobius voting for surface correspondence. In ACM SIGGRAPH, 72:1–72:12. Google ScholarDigital Library
23. Lipman, Y., Chen, X., Daubechies, I., and Funkhouser, T. 2010. symmetry factored embedding and distance. in ACM SIGGRAPH, 103:1–103:12. Google ScholarDigital Library
24. Mitra, N. J., Gelfand, N., Pottmann, H., and Guibas, L. 2004. Registration of point cloud data from a geometric optimization perspective. In SGP, 22–31. Google ScholarDigital Library
25. Muja, M., and Lowe, D. G. 2009. Fast approximate nearest neighbors with automatic algorithm configuration. In Proc. VIS-SAPP, 331–340.Google Scholar
26. Nadler, B., Lafon, S., Coifman, R. R., and Kevrekidis, I. G. 2006. Diffusion maps, spectral clustering and reaction coordinates of dynamical systems. Applied and Computational Harmonic Analysis 21, 1, 113–127.Google ScholarCross Ref
27. Nguyen, A., Ben-Chen, M., Welnicka, K., Ye, Y., and Guibas, L. 2011. An optimization approach to improving collections of shape maps. SGP 30, 5, 1481–1491.Google Scholar
28. Ovsjanikov, M., Mérigot, Q., Mémoli, F., and Guibas, L. J. 2010. One point isometric matching with the heat kernel. SGP 29, 5, 1555–1564.Google Scholar
29. Ovsjanikov, M., Li, W., Guibas, L., and Mitra, N. J. 2011. Exploration of continuous variability in collections of 3D shapes. ACM SIGGRAPH 30, 4, 33:1–33:10. Google ScholarDigital Library
30. Schreiner, J., Asirvatham, A., Praun, E., and Hoppe, H. 2004. inter-surface mapping. ACM SIGGRAPH 23, 3, 870–877. Google ScholarDigital Library
31. Shilane, P., Min, P., Kazhdan, M., and Funkhouser, T. 2004. The princeton shape benchmark. In Proc. SMI, 167–178. Google ScholarDigital Library
32. Sidi, O., van Kaick, O., Kleiman, Y., Zhang, H., and Cohen-Or, D. 2011. Unsupervised co-segmentation of a set of shapes via descriptor-space spectral clustering. ACM SIGGRAPH Asia 30, 6, 126:1–126:9. Google Scholar
33. Sun, J., Chen, X., and Funkhouser, T. A. 2010. Fuzzy geodesics and consistent sparse correspondences for: eformable shapes. CGF 29, 5, 1535–1544.Google ScholarCross Ref
34. van Kaick, O., Zhang, H., Hamarneh, G., and Cohen-Or, D. 2011. A survey on shape correspondence. CGF 30, 6, 1681–1707.Google ScholarCross Ref
35. Xu, K., Zhang, H., Cohen-Or, D., and Chen, B. 2012. Fit and diverse: Set evolution for inspiring 3D shape galleries. ACM Trans. on Graph (Proc. of SIGGRAPH) 31, to appear. Google ScholarDigital Library