“Characterizing structural relationships in scenes using graph kernels” by Fisher, Savva and Hanrahan

Modeling virtual environments is a time consuming and expensive task that is becoming increasingly popular for both professional and casual artists. The model density and complexity of the scenes representing these virtual environments is rising rapidly. This trend suggests that data-mining a 3D scene corpus could be a very powerful tool enabling more efficient scene design. In this paper, we show how to represent scenes as graphs that encode models and their semantic relationships. We then define a kernel between these relationship graphs that compares common virtual substructures in two graphs and captures the similarity between their corresponding scenes. We apply this framework to several scene modeling problems, such as finding similar scenes, relevance feedback, and context-based model search. We show that incorporating structural relationships allows our method to provide a more relevant set of results when compared against previous approaches to model context search.

1. Bach, F. R., Lanckriet, G. R. G., and Jordan, M. I. 2004. Multiple kernel learning, conic duality, and the smo algorithm. In Proceedings of the 21st international conference on machine learning, ACM, New York, NY, USA, ICML ’04. Google Scholar
2. Bao, S., Sun, M., and Savarese, S. 2010. Toward coherent object detection and scene layout understanding. In CVPR, 65–72.Google Scholar
3. Borgwardt, K., Ong, C., Schönauer, S., Vishwanathan, S., Smola, A., and Kriegel, H. 2005. Protein function prediction via graph kernels. Bioinformatics 21, 47–56. Google ScholarDigital Library
4. Chaudhuri, S., and Koltun, V. 2010. Data-driven suggestions for creativity support in 3D modeling. ACM Transactions on Graphics 29 (December), 183:1–183:10. Google ScholarDigital Library
5. Chen, D., Tian, X., Shen, Y., and Ouhyoung, M. 2003. On visual similarity based 3D model retrieval. In Computer graphics forum, vol. 22, 223–232.Google Scholar
6. Cristianini, N., and Shawe-Taylor, J. 2000. An introduction to support vector machines: and other kernel-based learning methods. Cambridge University Press. Google Scholar
7. Feist, M. 2000. On in and on: An investigation into the linguistic encoding of spatial scenes. UMI, Ann Arbor, Michigan.Google Scholar
8. Fisher, M., and Hanrahan, P. 2010. Context-based search for 3D models. ACM Transactions on Graphics 29 (December), 182:1–182:10. Google ScholarDigital Library
9. Funkhouser, T., Min, P., Kazhdan, M., Chen, J., Halderman, A., Dobkin, D., and Jacobs, D. 2003. A search engine for 3D models. ACM Transactions on Graphics 22, 1, 83–105. 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. In ACM Transactions on Graphics, vol. 23, ACM, 652–663. Google ScholarDigital Library
11. Gal, R., Sorkine, O., Mitra, N., and Cohen-Or, D. 2009. iWIRES: An analyze-and-edit approach to shape manipulation. In ACM SIGGRAPH 2009 papers, ACM, 1–10. Google Scholar
12. Galleguillos, C., Rabinovich, A., and Belongie, S. 2008. Object categorization using co-occurrence, location and appearance. In CVPR, 1–8.Google Scholar
13. Gartner, T., Flach, P., and Wrobel, S. 2003. On graph kernels: Hardness results and efficient alternatives. In Proceedings of the 16th Annual Conference on Learning Theory, 129–143.Google Scholar
14. Goldfeder, C., and Allen, P. 2008. Autotagging to improve text search for 3D models. In JCDL ’08: Proceedings of the 8th ACM/IEEE-CS Joint Conference on Digital Libraries, ACM, New York, NY, USA, 355–358. Google Scholar
15. Gupta, A., Efros, A., and Hebert, M. 2010. Blocks world revisited: Image understanding using qualitative geometry and mechanics. Computer Vision–ECCV, 482–496. Google Scholar
16. Habegger, B., and Debarbieux, D. 2006. Integrating Data from the Web by Machine-Learning Tree-Pattern Queries. On the Move to Meaningful Internet Systems, 941–948. Google Scholar
17. Harchaoui, Z., and Bach, F. 2007. Image classification with segmentation graph kernels. In CVPR, 1–8.Google Scholar
18. Kashima, H., Tsuda, K., and Inokuchi, A. 2004. Kernels for graphs. Kernel methods in computational biology, 155–170.Google Scholar
19. Lazebnik, S., Schmid, C., and Ponce, J. 2006. Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories. In CVPR, vol. 2, 2169–2178. Google ScholarDigital Library
20. Lipman, Y., Chen, X., Daubechies, I., and Funkhouser, T. 2010. Symmetry factored embedding and distance. ACM Transactions on Graphics 29 (July), 103:1–103:12. Google ScholarDigital Library
21. Mahé, P., Ueda, N., Akutsu, T., Perret, J.-L., and Vert, J.-P. 2004. Extensions of marginalized graph kernels. In 21st international conference on machine learning, ACM, New York, NY, USA, ICML ’04, 70–77. Google Scholar
22. Merrell, P., Schkufza, E., and Koltun, V. 2010. Computer-generated residential building layouts. ACM Transactions on Graphics 29 (December), 181:1–181:12. Google ScholarDigital Library
23. Novotni, M., and Klein, R. 2003. 3D Zernike descriptors for content based shape retrieval. In 8th ACM symposium on solid modeling and applications, ACM, 216–225. Google Scholar
24. Papadakis, P., Pratikakis, I., Trafalis, T., Theoharis, T., and Perantonis, S. 2008. Relevance feedback in content-based 3D object retrieval: A comparative study. Computer-Aided Design and Applications Journal 5, 5, 753–763.Google ScholarCross Ref
25. Paraboschi, L., Biasotti, S., and Falcidieno, B. 2007. 3D scene comparison using topological graphs. Eurographics Italian Chapter, Trento (Italy), 87–93.Google Scholar
26. Platt, J. 1999. Fast training of support vector machines using sequential minimal optimization. In Advances in Kernel Methods, MIT press, 185–208. Google ScholarDigital Library
27. Ramon, J., and Gärtner, T. 2003. Expressivity versus efficiency of graph kernels. In 1st International Workshop on Mining Graphs, Trees and Sequences, 65–74.Google Scholar
28. Russell, B., and Torralba, A. 2009. Building a database of 3d scenes from user annotations. CVPR, 2711–2718.Google Scholar
29. Russell, B., Torralba, A., Murphy, K., and Freeman, W. 2008. LabelMe: a database and web-based tool for image annotation. International Journal of Computer Vision 77, 1, 157–173. Google ScholarDigital Library
30. Salton, G., and Buckley, C. 1988. Term-weighting approaches in automatic text retrieval. In Information Processing and Management, 513–523. Google Scholar
31. Shawe-Taylor, J., and Cristianini, N. 2004. Kernel methods for pattern analysis. Cambridge University Press. Google Scholar
32. Shechtman, E., and Irani, M. 2007. Matching local self-similarities across images and videos. In CVPR, 1–8.Google Scholar
33. Tangelder, J., and Veltkamp, R. 2008. A survey of content based 3D shape retrieval methods. Multimedia Tools and Applications 39, 3, 441–471. Google ScholarDigital Library
34. Xu, Y., and Kemp, C. 2010. Constructing spatial concepts from universal primitives. Proceedings of the 32nd Annual Conference of the Cognitive Science Society, 1–6.Google Scholar