Unsupervised learning from a corpus for shape-based 3D model retrieval

ABSTRACT

Arguably the most important issues in shape-based 3D model retrieval are methods to extract powerful yet compact shape features and methods to properly and promptly compare the shape features. In this paper, we explore a method to improve feature distance computation by employing unsupervised learning of the subspace of 3D shape features from a corpus. We employ an algorithm called Laplacian Eigenmaps proposed by Belkin, et al. to learn a manifold spanned by shape features of 3D models in the corpus. The learned manifold is approximated by an RBF network, onto which shape features are projected. Distances among shape features can then be computed effectively on the learned manifold. We combine this learning-based distance-computation method with a method to extract multiresolution shape features proposed by Ohbuchi, et al. Our experimental evaluation showed that the proposed method could significantly improve retrieval performance. Learning alone improved performance of two shape features we tried by about 5%. A combination of learning and multiresolution shape feature allowed about 10% gain in performance. As an example, the trained, multiresolution version of the SPRH gained 10% over the original single resolution, untrained SPRH shape feature.

REFERENCES

• 1: Indriyati Atmosukarto , Wee Kheng Leow , Zhiyong Huang, Feature Combination and Relevance Feedback for 3D Model Retrieval, Proceedings of the 11th International Multimedia Modelling Conference (MMM'05), p.334-339, January 12-14, 2005 [doi>10.1109/MMMC.2005.39]
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: Mikhail Belkin , Partha Niyogi, Laplacian Eigenmaps for dimensionality reduction and data representation, Neural Computation, v.15 n.6, p.1373-1396, June 2003 [doi>10.1162/089976603321780317]
• 4: Paul Bratley , Bennett L. Fox , Harald Niederreiter, Programs to generate Niederreiter's low-discrepancy sequences, ACM Transactions on Mathematical Software (TOMS), v.20 n.4, p.494-495, Dec. 1994 [doi>10.1145/198429.198436]
• 5: Benjamin Bustos , Daniel Keim , Dietmar Saupe , Tobias Schreck , Dejan Vranic, Automatic Selection and Combination of Descriptors for Effective 3D Similarity Search, Proceedings of the IEEE Sixth International Symposium on Multimedia Software Engineering (ISMSE'04), p.514-521, December 13-15, 2004
• 6: Chen, S., C.F.N. Cowan, P. M. Grant, Orthogonal Least Squares Learning Algorithm for Radial Basis Function Networks, IEEE Trans. on Neural Networks, 2(2), pp. 302--309, (1991)
• 7: D.-Y. Chen, X.-P. Tian, Y.-T. Shen, M. Ouhyoung, On Visual Similarity Based 3D Model Retrieval, Computer Graphics Forum, 22(3), pp. 223--232, (2003).
• 8: Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994 [doi>10.1145/174462.156635]
• 9: Michael Elad , Ayellet Tal , Sigal Ar, Content based retrieval of VRML objects: an iterative and interactive approach, Proceedings of the sixth Eurographics workshop on Multimedia 2001, p.107-118, September 08-09, 2001, Manchester, UK
• 10: Simon Haykin, Neural Networks: A Comprehensive Foundation, Prentice Hall PTR, Upper Saddle River, NJ, 1998
• 11: Xiaofei He , Wei-Ying Ma , Hong-Jiang Zhang, Learning an image manifold for retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027532]
• 12: Iyer, N., Kalyanaraman, Y., Lou, K., Jayanti, S., Ramani, K., A Reconfigurable, Intelligent 3D Engineering Shape Search System Part I: Shape Representation, Proc. ASME DETC '03, 23rd CIE Conf. (2003).
• 13: M. Iyer, S. Jayanti, K. Lou, Y. Kalyanaraman, K. Ramani, Three Dimensional Shape Searching: State-of-the-art Review and Future Trends, Computer Aided Design, 5(15), pp. 509--530, (2005).
• 14: G. Leifman, R. Meir, A. Tal, Semantic-oriented 3d shape retrieval using relevance feedback, The Visual Computer (Pacific Graphics), 21(8-10), pp. 865--875, October 2005.
• 15: Rong Liu, Varun Jain, Hao Zhang, Sub-sampling for Efficient Spectral Mesh Processing, Proc. CGI 2006, LNCS 4035, pp. 172--184, Springer-Verlag, (2006).
• 16: M. Novotni, G.-J. Park, R. Wessel, R. Klein Evaluation of Kernel Based Methods for Relevance Feedback in 3D Shape Retrieval, Proc. The Fourth International Workshop on Content-Based Multimedia Indexing (CBMI'05), (2005).
• 17: NTU 3D Model Database ver.1 http://3d.csie.ntu.edu.tw/
• 18: Ryutarou Ohbuchi , Tsuyoshi Takei, Shape-Similarity Comparison of 3D Models Using Alpha Shapes, Proceedings of the 11th Pacific Conference on Computer Graphics and Applications, p.293, October 08-10, 2003
• 19: Ryutarou Ohbuchi, Takahiro Minamitani, Tsuyoshi Takei, Shape-similarity search of 3D models by using enhanced shape functions, International Journal of Computer Applications in Technology (IJCAT), 23(3/4/5), pp. 70--85, (2005).
• 20: Ryutarou Ohbuchi, Yushin Hata, Combining Multiresolution Shape Descriptors for 3D Model Retrieval, Proc WSCG 2006 (2006).
• 21: Robert Osada , Thomas Funkhouser , Bernard Chazelle , David Dobkin, Shape distributions, ACM Transactions on Graphics (TOG), v.21 n.4, p.807-832, October 2002 [doi>10.1145/571647.571648]
• 22: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical Recipes in C: The Art of Scientific Computing, Cambridge University Press, New York, NY, 1992
• 23: S.T. Roweis, L.K. Saul, Nonlinear Dimensionality Reduction by Locally Linear Embedding, Science, 290(5500), pp. 2323--2326, (2000).
• 24: The Princeton Shape Benchmark, Proceedings of the Shape Modeling International 2004 (SMI'04), p.167-178, June 07-09, 2004 [doi>10.1109/SMI.2004.63]
• 25: A Survey of Content Based 3D Shape Retrieval Methods, Proceedings of the Shape Modeling International 2004 (SMI'04), p.145-156, June 07-09, 2004 [doi>10.1109/SMI.2004.10]
• 26: J. B. Tanenbaum, V. de Silva, J.C. Langford, A Global Geometric Framework for Nonlinaer Dimensionality Reduction, Science, 290(5500), pp. 2319--2323, (2000).
• 27: R. C. Veltkamp, R. Ruijsenaars, Michela Spagnuolo, R. Van Zwol, F. ter Haar, SHREC2006 3D Shape Retrieval Contest, Utrecht University Dept. Information and Computing Sciences Technical Report UU-CS-2006-030 (ISSN: 0924-3275) http://give-lab.cs.uu.nl/shrec/shrec2006/index.html
• 28: E. Wahl, U. Hillenbrand, G. Hirzinger, Surflet-Pair-Relation Histograms: A Statistical 3D-Shape Representation for Rapid Classification, Proc. 3DIM 2003, pp. 474--481, (2003).

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis
          Subjects: Object recognition

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
content-based retrieval, manifold learning, shape-based 3D model retrieval