“Retrieval on Parametric Shape Collections” by Schulz, Shamir, Baran, Levin, Sitthi-amorn, et al. …

  • ©Adriana Schulz, Ariel Shamir, Ilya Baran, David I. W. Levin, Pitchaya Sitthi-amorn, and Wojciech Matusik

Conference:


Type:


Title:

    Retrieval on Parametric Shape Collections

Session/Category Title: Comparing 3D Shapes and Part


Presenter(s)/Author(s):


Moderator(s):



Abstract:


    While collections of parametric shapes are growing in size and use, little progress has been made on the fundamental problem of shape-based matching and retrieval for parametric shapes in a collection. The search space for such collections is both discrete (number of shapes) and continuous (parameter values). In this work, we propose representing this space using descriptors that have shown to be effective for single shape retrieval. While single shapes can be represented as points in a descriptor space, parametric shapes are mapped into larger continuous regions. For smooth descriptors, we can assume that these regions are bounded low-dimensional manifolds where the dimensionality is given by the number of shape parameters. We propose representing these manifolds with a set of primitives, namely, points and bounded tangent spaces. Our algorithm describes how to define these primitives and how to use them to construct a manifold approximation that allows accurate and fast retrieval. We perform an analysis based on curvature, boundary evaluation, and the allowed approximation error to select between primitive types. We show how to compute decision variables with no need for empirical parameter adjustments and discuss theoretical guarantees on retrieval accuracy. We validate our approach with experiments that use different types of descriptors on a collection of shapes from multiple categories.

References:


    1. Mihael Ankerst, Gabi Kastenmller, Hans-Peter Kriegel, and Thomas Seidl. 1999. Nearest neighbor classification in 3D protein databases. In Proceedings of ISMB (1999), 34–43.Google Scholar
    2. Melinos Averkiou, Vladimir Kim, Youyi Zheng, and Niloy J. Mitra. 2014. ShapeSynth: Parameterizing model collections for coupled shape exploration and synthesis. Computer Graphics Forum (Special Issue of Eurographics 2014) (2014), 10.Google Scholar
    3. Christopher M. Bishop. 2006. Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verlag New York, Inc., Secaucus, NJ.Google Scholar
    4. Martin Bokeloh, Michael Wand, Hans-Peter Seidel, and Vladlen Koltun. 2012. An algebraic model for parameterized shape editing. ACM Transactions on Graphics 31, 4 (2012), 78:1–78:10.Google ScholarDigital Library
    5. Alexander M. Bronstein, Michael M. Bronstein, Leonidas J. Guibas, and Maks Ovsjanikov. 2011. Shape google: Geometric words and expressions for invariant shape retrieval. ACM Transactions on Graphics 30, 1, Article 1 (2011), 1:1–1:20.Google ScholarDigital Library
    6. Ding-Yun Chen, Xiao-Pei Tian, Yu-Te Shen, and Ming Ouhyoung. 2003. On visual similarity based 3D model retrieval. Computer Graphics Forum 22, 3 (2003), 223–232. Google ScholarCross Ref
    7. Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the 20th Annual Symposium on Computational Geometry. ACM, 253–262. Google ScholarDigital Library
    8. Manfredo Perdigao Do Carmo. 1976. Differential Geometry of Curves and Surfaces. Vol. 2. Prentice-Hall, Englewood Cliffs.Google Scholar
    9. Thomas A. Funkhouser, Michael M. Kazhdan, Philip Shilane, Patrick Min, William Kiefer, Ayellet Tal, Szymon Rusinkiewicz, and David P. Dobkin. 2004. Modeling by example. ACM Transactions on Graphics 23, 3 (2004), 652–663. Google ScholarDigital Library
    10. Ran Gal, Ariel Shamir, and Daniel Cohen-Or. 2007. Pose oblivious shape signature. IEEE Transactions of Visualization and Computer Graphics 13, 2 (2007), 261–271. Google ScholarDigital Library
    11. Ran Gal, Olga Sorkine, Niloy J. Mitra, and Daniel Cohen-Or. 2009. IWIRES: An analyze-and-edit approach to shape manipulation. ACM Transactions on Graphics 28, 3 (2009). Google ScholarDigital Library
    12. Zoubin Ghahramani, Geoffrey E. Hinton, et al 1996. The EM Algorithm for Mixtures of Factor Analyzers. Technical Report CRG-TR-96-1, University of Toronto.Google Scholar
    13. Qixing Huang, Hai Wang, and Vladlen Koltun. 2015. Single-view reconstruction via joint analysis of image and shape collections. ACM Transactions on Graphics 34, 4, Article 87 (July 2015), 10 pages. DOI:http://dx.doi.org/10.1145/2766890 Google ScholarDigital Library
    14. Vladimir G. Kim, Wilmot Li, Niloy J. Mitra, Siddhartha Chaudhuri, Stephen DiVerdi, and Thomas Funkhouser. 2013. Learning part-based templates from large collections of 3D shapes. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2013) (2013).Google ScholarDigital Library
    15. Niloy J. Mitra, Natasha Gelfand, Helmut Pottmann, and Leonidas Guibas. 2004. Registration of point cloud data from a geometric optimization perspective. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. ACM, 22–31. Google ScholarDigital Library
    16. Liangliang Nan, Ke Xie, and Andrei Sharf. 2012. A search-classify approach for cluttered indoor scene understanding. ACM Transactions on Graphics 31, 6, Article 137 (Nov. 2012), 10 pages. DOI:http://dx.doi.org/10.1145/2366145.2366156 Google ScholarDigital Library
    17. Robert Osada, Thomas Funkhouser, Bernard Chazelle, and David Dobkin. 2001. Matching 3D models with shape distributions. In Proceedings of the International Conference on Shape Modeling 8 Applications (SMI’01). IEEE Computer Society, Washington, DC, 154. Google ScholarCross Ref
    18. Maks Ovsjanikov, Wilmot Li, Leonidas J. Guibas, and Niloy J. Mitra. 2011. Exploration of continuous variability in collections of 3D shapes. ACM Transactions on Graphics 30, 4 (2011), 33.Google ScholarDigital Library
    19. Helmut Pottmann and Michael Hofer. 2003. Geometry of the Squared Distance Function to Curves and Surfaces. Springer. Google ScholarCross Ref
    20. Helmut Pottmann, Stefan Leopoldseder, and Michael Hofer. 2004. Registration without ICP. Computer Vision and Image Understanding 95, 1 (2004), 54–71. Google ScholarDigital Library
    21. Sam T. Roweis and Lawrence K. Saul. 2000. Nonlinear dimensionality reduction by locally linear embedding. Science 290, 5500 (December 2000), 2323–2326. DOI:http://dx.doi.org/10.1126/science.290.5500.2323 Google ScholarCross Ref
    22. Adriana Schulz, Ariel Shamir, David I. W. Levin, Pitchaya Sitthi-amorn, and Wojciech Matusik. 2014. Design and fabrication by example. ACM Transactions on Graphics 33, 4, Article 62 (July 2014), 11 pages. DOI:http://dx.doi.org/10.1145/2601097.2601127 Google ScholarDigital Library
    23. Chao-Hui Shen, Hongbo Fu, Kang Chen, and Shi-Min Hu. 2012. Structure recovery by part assembly. ACM Transactions on Graphics 31, 6, Article 180 (Nov. 2012), 11 pages. DOI:http://dx.doi.org/10.1145/2366145.2366199 Google ScholarDigital Library
    24. Philip Shilane, Patrick Min, Michael Kazhdan, and Thomas Funkhouser. 2004. The Princeton shape benchmark. In Proceedings of the Shape Modeling International 2004. 167–178. Google ScholarCross Ref
    25. SHREC. 2014. 3D Shape Retrieval Contest at EUROGRAPHICS. Retrieved June 2, 2015 from http://3dor2014.ensea.fr/SHREC2014.html.Google Scholar
    26. Anuj Srivastava, Shantanu H. Joshi, Washington Mio, and Xiuwen Liu. 2005. Statistical shape analysis: Clustering, learning, and testing. IEEE Transactions on Pattern Analysis and Machine Intelligence 27, 4 (2005), 590–602. Google ScholarDigital Library
    27. Jerry O. Talton, Yu Lou, Steve Lesser, Jared Duke, Radomír Měch, and Vladlen Koltun. 2011. Metropolis procedural modeling. ACM Transactions on Graphics 30, 2, Article 11 (April 2011), 14 pages. DOI:http://dx.doi.org/10.1145/1944846.1944851 Google ScholarDigital Library
    28. Johan W. Tangelder and Remco C. Veltkamp. 2008. A survey of content based 3D shape retrieval methods. Multimedia Tools and Applications 39, 3 (2008), 441–471. Google ScholarDigital Library
    29. Joshua B. Tenenbaum, Vin de Silva, and John C. Langford. 2000. A global geometric framework for nonlinear dimensionality reduction. Science 290, 5500 (2000), 2319.Google ScholarCross Ref
    30. Nuno Vasconcelos and Andrew Lippman. 2005. A multiresolution manifold distance for invariant image similarity. IEEE Transactions on Multimedia 7, 1 (2005), 127–142. Google ScholarDigital Library
    31. Elif Vural and Pascal Frossard. 2011. Discretization of parametrizable signal manifolds. IEEE Transactions on Image Processing 20, 12 (2011), 3621–3633. Google ScholarDigital Library
    32. Wenping Wang, Helmut Pottmann, and Yang Liu. 2006. Fitting B-spline curves to point clouds by curvature-based squared distance minimization. ACM Transactions on Graphics 25, 2 (2006), 214–238. Google ScholarDigital Library
    33. Kai Xu, Hanlin Zheng, Hao Zhang, Daniel Cohen-Or, Ligang Liu, and Yueshan Xiong. 2011. Photo-inspired model-driven 3D object modeling. ACM Transactions on Graphics 30, 4 (2011), 80.Google ScholarDigital Library
    34. Yong-Liang Yang, Yi-Jun Yang, Helmut Pottmann, and Niloy J. Mitra. 2011. Shape space exploration of constrained meshes. ACM Transactions on Graphics 30, 6, Article 124 (Dec. 2011), 12 pages. DOI:http://dx.doi.org/10.1145/2070781.2024158 Google ScholarDigital Library


ACM Digital Library Publication: