“Indexing 3D Scenes Using the Interaction Bisector Surface” by Zhao, Wang and Komura

  • ©Xi Zhao, He Wang, and Taku Komura

Conference:


Type(s):


Title:

    Indexing 3D Scenes Using the Interaction Bisector Surface

Session/Category Title:   Layout Building & Scenes

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    The spatial relationship between different objects plays an important role in defining the context of scenes. Most previous 3D classification and retrieval methods take into account either the individual geometry of the objects or simple relationships between them such as the contacts or adjacencies. In this article we propose a new method for the classification and retrieval of 3D objects based on the Interaction Bisector Surface (IBS), a subset of the Voronoi diagram defined between objects. The IBS is a sophisticated representation that describes topological relationships such as whether an object is wrapped in, linked to, or tangled with others, as well as geometric relationships such as the distance between objects. We propose a hierarchical framework to index scenes by examining both the topological structure and the geometric attributes of the IBS. The topology-based indexing can compare spatial relations without being severely affected by local geometric details of the object. Geometric attributes can also be applied in comparing the precise way in which the objects are interacting with one another. Experimental results show that our method is effective at relationship classification and content-based relationship retrieval.

References:


    1. L. A. Alexandre. 2012. 3D descriptors for object and category recognition: A comparative evaluation. In Proceedings of the IEEE Workshop on Color-Depth Camera Fusion in Robotics at the RSJ International Conference on Intelligent Robots and Systems (IROS’12).
    2. N. Amenta, S. Choi, and R. K. Kolluri. 2001. The power crust. In Proceedings of the 6th ACM Symposium on Solid Modeling and Applications. 249–266.
    3. D. Attali, J.-D. Boissonnat, and H. Edelsbrunner. 2009. Stability and computation of medial axes – A state-of-the-art report. In Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration, T. Miller, B. Hamann, and R. D. Russell, Eds., Springer, 109–125.
    4. C. B. Barber, D. P. Dobkin, and H. Huhdanpaa. 1996. The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22, 4, 469–483.
    5. S. Belongie, J. Malik, and J. Puzicha. 2002. Shape matching and object recognition using shape contexts. IEEE Trans. Pattern Anal. Mach. Intell. 24, 4, 509–522.
    6. B. E. Boser, I. M. Guyon, and V. N. Vapnik. 1992. A training algorithm for optimal margin classifiers. In Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory. ACM Press, New York, 144–152.
    7. C.-C. Chang and C.-J. Lin. 2011. LIBSVM: A library for support vector machines. ACM Trans. Intell. Syst. Technol. 2, 3, 27:1–27:27. http://www. csie.ntu.edu.tw/cjlin/libsvm.
    8. M.-C. Chang and B. B. Kimia. 2011. Measuring 3d shape similarity by graph-based matching of the medial scaffolds. Comput. Vis. Image Understand. 115, 5, 707–720.
    9. C. Cortes and V. Vapnik. 1995. Support-vector networks. Mach. Learn. 20, 3, 273–297.
    10. T. Culver, J. Keyser, and D. Manocha. 1999. Accurate computation of the medial axis of a polyhedron. In Proceedings of the 5th ACM Symposium on Solid Modeling and Applications. 179–190.
    11. C. J. A. Delfinado and H. Edelsbrunner. 1995. An incremental algorithm for betti numbers of simplicial complexes on the 3-sphere. Comput. Aided Geom. Des. 12, 7, 771–784.
    12. G. Elber and M.-S. Kim. 1997. The bisector surface of freeform rational space curves. In Proceedings of the 13th Annual Symposium on Computational Geometry. ACM Press, New York, 473–474.
    13. M. Fisher and P. Hanrahan. 2010. Context-based search for 3d models. ACM Trans. Graph. 29, 6, 182.
    14. M. Fisher, D. Ritchie, M. Savva, T. Funkhouser, and P. Hanrahan. 2012. Example-based synthesis of 3d object arrangements. ACM Trans. Graph. 31, 6, 135.
    15. M. Fisher, M. Savva, and P. Hanrahan. 2011. Characterizing structural relationships in scenes using graph kernels. ACM Trans. Graph. 30, 4.
    16. S. Giannarou and T. Stathaki. 2007. Object identification in complex scenes using shape context descriptors and multi-stage clustering. In Proceedings of the 15th International Conference on Digital Signal Processing. 244–247.
    17. E. B. Goldstein. 2010. Sensation and perception. www.CengageBrain.com.
    18. L. A. Goodman and W. H. Kruskal. 1954. Measures of association for cross classifications. J. Amer. Statist. Assoc. 67, 338, 732–764.
    19. Z. Harchaoui and F. Bach. 2007. Image classification with segmentation graph kernels. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR’07). 1–8.
    20. J. Hartung, G. Knapp, and B. K. Sinha. 2011. Statistical Meta-Analysis with Applications, Vol. 738. http://www.wiley.com/WileyCDA/WileyTitle/productCd-0470290897.htm.
    21. T. Hastie, R. Tibshirani, and J. Friedman. 2009. The Elements of Statistical Learning. Springer, New York.
    22. T. Imai. 1996. A topology oriented algorithm for the voronoi diagram of polygons. In Proceedings of the 8th Canadian Conference on Computational Geometry. Carleton University Press, 107–112.
    23. E. Kalogerakis, S. Chaudhuri, D. Koller, and V. Koltun. 2012. A probabilistic model for component-based shape synthesis. ACM Trans. Graph. 31, 4, 55.
    24. C.-M. Kim, C. I. Won, Y. Cho, D. Kim, S. Lee, J. Bhak, and D.-S. Kim. 2006. Interaction interfaces in proteins via the voronoi diagram of atoms. Comput.-Aided Des. 38, 11, 1192–1204.
    25. D. MacDonald, J. Lang, and M. McAllister. 2006. Evaluation of colour image segmentation hierarchies. In Proceedings of the 3rd Canadian Conference on Computer and Robot Vision (CRV’06). 27.
    26. W. Massey. 1991. A Basic Course in Algebraic Topology. Vol. 127, Springer.
    27. L. Paraboschi, S. Biasotti, and B. Falcidieno. 2007. Comparing sets of 3d digital shapes through topological structures. In Graph-Based Representations in Pattern Recognition, F. Escolano and M. Vento, Eds., Lecture Notes in Computer Science, vol. 4538, Springer, 114–125.
    28. A. Rabinovich, A. Vedaldi, C. Galleguillos, E. Wiewiora, and S. Belongie. 2007. Objects in context. In Proceedings of the 11th IEEE International Conference on Computer Vision (ICCV’07).
    29. R. Rusu, Z. Marton, N. Blodow, and M. Beetz. 2008a. Learning informative point classes for the acquisition of object model maps. In Proceedings of the 10th International Conference on Control, Automation, Robotics and Vision (ICARCV’08). 643–650.
    30. R. B. Rusu, Z. C. Marton, N. Blodow, and M. Beetz. 2008b. Persistent point feature histograms for 3d point clouds. Intell. Auton. Syst. 10, Ias-10, 119.
    31. T. B. Sebastian, P. N. Klein, and B. B. Kimia. 2001. Recognition of shapes by editing shock graphs. In Proceedings of the 5th IEEE International Conference on Computer Vision (ICCV’01). 755–762.
    32. L. Shapira, S. Shalom, A. Shamir, D. Cohen-Or, and H. Zhang. 2010. Contextual part analogies in 3d objects. Int. J. Comput. Vis. 89, 2–3, 309–326.
    33. E. C. Sherbrooke, N. M. Patrikalakis, and E. Brisson. 1995. Computation of the medial axis transform of 3-d polyhedra. In Proceedings of the 3rd ACM Symposium on Solid Modeling and Applications. 187–200.
    34. P. Shilane, P. Min, M. Kazhdan, and T. Funkhouser. 2004. The princeton shape benchmark. In Proceedings of the IEEE International Conference on Shape Modeling Applications. 167–178.
    35. S. P. Smith and R. Dubes. 1980. Stability of a hierarchical clustering. Pattern Recogn. 12, 3, 177–187.
    36. A. Sud, M. Foskey, and D. Manocha. 2007. Homotopy-preserving medial axis simplification. Int. J. Comput. Geom. Appl. 17, 05, 423–451.
    37. J. K. T. Tang, J. C. P. Chan, H. Leung, and T. Komura. 2012. Retrieval of interactions by abstraction of spacetime relationships. Comput. Graph. Forum 31, 2.
    38. O. van Kaick, K. Xu, H. Zhang, Y. Wang, S. Sun, A. Shamir, and D. Cohen-Or. 2013a. Co-hierarchical analysis of shape structures. ACM Trans. Graph. 32, 4, 69.
    39. O. van Kaick, H. Zhang, and G. Hamarneh. 2013b. Bilateral maps for partial matching. Comput. Graph. Forum 32, 6, 189–200.
    40. Y. Wang, K. Xu, J. Li, H. Zhang, A. Shamir, L. Liu, Z.-Q. Cheng, and Y. Xiong. 2011. Symmetry hierarchy of man-made objects. Comput. Graph. Forum 30, 2, 287–296.
    41. L.-F. Yu, S.-K. Yeung, C.-K. Tang, D. Terzopoulos, T. F. Chan, and S. J. Osher. 2011. Make it home: Automatic optimization of furniture arrangement. ACM Trans. Graph. 30, 4, 86:1–86:12.
    42. Y. Zheng, D. Cohen-Or, and N. J. Mitra. 2013a. Smart variations: Functional substructures for part compatibility. Comput. Graph. Forum 32, 2, 195–204.
    43. Y. Zheng, C.-L. Tai, E. Zhang, and P. Xu. 2013b. Pairwise harmonics for shape analysis. IEEE Trans. Vis. Comput. Graph. 19, 7, 1172–1184.

ACM Digital Library Publication:


Overview Page: