Johannes Aßfalg
ABSTRACT
Classification of 3D objects remains an important task in many areas of data management such as engineering, medicine or biology. As a common preprocessing step in current approaches to classification of voxelized 3D objects, voxel representations are transformed into a feature vector description.In this article, we introduce an approach of transforming 3D objects into feature strings which represent the distribution of voxels over the voxel grid. Attractively, this feature string extraction can be performed in linear runtime with respect to the number of voxels. We define a similarity measure on these feature strings that counts common k-mers in two input strings, which is referred to as the spectrum kernel in the field of kernel methods. We prove that on our feature strings, this similarity measure can be computed in time linear to the number of different characters in these strings. This linear runtime behavior makes our kernel attractive even for large datasets that occur in many application domains. Furthermore, we explain that our similarity measure induces a metric which allows to combine it with an M-tree for handling of large volumes of data. Classification experiments on two published benchmark datasets show that our novel approach is competitive with the best state-of-the-art methods for 3D object classification.
- M. Ankerst, G. Kastenmüller, H.-P. Kriegel, and T. Seidl. 3D Shape Histograms for Similarity Search and Classification in Spatial Databases. In Proceedings of the 6th International Symposium on Spatial Databases, pages 207--226, 1999. Google Scholar
Digital Library
- A. Ben-Hur, D. Horn, H. Siegelmann, and V. Vapnik. A support vector method for hierarchical clustering. In T. K. Leen, T. G. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems 13, pages 367--373. MIT Press, 2001.Google Scholar
- H. Berman, J. Westbrook, Z. Feng, G. Gilliland, T. Bhat, H. Weissig, I. Shindyalov, and P. Bourne. The protein data bank. Nucleic Acids Research, 28:235--242, 2000.Google ScholarCross Ref
- C. J. C. Burges. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2(2):121--167, 1998. Google ScholarDigital Library
- D.-Y. Chen, X.-P. Tian, Y.-T. Shen, and M. Ouhyoung. On Visual Similarity Based 3D Model Retrieval. In Computer Graphics Forum, volume 22, pages 223--232, 2003. Google ScholarDigital Library
- P. Ciaccia, M. Patella, and P. Zezula. M-tree: An efficient access method for similarity search in metric spaces. In VLDB '97: Proceedings of the 23rd International Conference on Very Large Data Bases, pages 426--435, 1997. Google ScholarDigital Library
- H. Drucker, C. J. C. Burges, L. Kaufman, A. J. Smola, and V. Vapnik. Support vector regression machines. In M. C. Mozer, M. I. Jordan, and T. Petsche, editors, Advances in Neural Information Processing Systems 9, pages 155--161, Cambridge, MA, 1997. MIT Press.Google Scholar
- T. Funkhouser, P. Min, M. Kazhdan, J. Chen, A. Halderman, D. Dobkin, and D. Jacobs. A search engine for 3d models. In ACM Transactions on Graphics, pages 83--105, 2003. Google ScholarDigital Library
- D. Haussler. Convolutional kernels on discrete structures. Technical Report UCSC-CRL-99-10, Computer Science Department, UC Santa Cruz, 1999.Google Scholar
- T. S. Jaakkola and D. Haussler. Exploiting generative models in discriminative classifiers. In M. S. Kearns, S. A. Solla, and D. A. Cohn, editors, Advances in Neural Information Processing Systems 11, pages 487--493. MIT Press, 1999. Google ScholarDigital Library
- T. Joachims. Making large-scale SVM learning practical. In B. Schölkopf, C. J. C. Burges, and A. J. Smola, editors, Advances in Kernel Methods - Support Vector Learning, pages 169--184, Cambridge, MA, 1999. MIT Press. Google ScholarDigital Library
- I. Jolliffe. Principal Component Analysis. Springer, 1986.Google ScholarCross Ref
- A. Kaufman. An Algorithm for 3D Scan-Conversion of Polygons. In Proc. Eurographics, pages 197--208, 1987.Google Scholar
- M. Kazhdan, T. Funkhouser, and S. Rusinkiewicz. Rotation invariant spherical harmonic representation of 3d shape descriptors. In Symposium on Geometry Processing, pages 167--175, 2003. Google ScholarDigital Library
- H.-P. Kriegel, P. Kröger, Z. Mashael, M. Pfeifle, M. Pötke, and T. Seidl. Effective Similarity Search on Voxelized CAD Objects. In Proc. 8th Int. Conf. on Database Systems for Advanced Applications, Kyoto, Japan, pages 27--36, 2003. Google ScholarDigital Library
- C. Leslie, E. Eskin, and W. S. Noble. The spectrum kernel: A string kernel for SVM protein classification. In Proceedings of the Pacific Symposium on Biocomputing, pages 564--575, 2002.Google Scholar
- C. Leslie, E. Eskin, J. Weston, and W. S. Noble. Mismatch string kernels for SVM protein classification. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems 15, volume 15, Cambridge, MA, 2002. MIT Press.Google Scholar
- L. Liao and W. S. Noble. Combining pairwise sequence similarity and support vector machines for remote protein homology detection. In RECOMB, pages 225--232, 2002. Google ScholarDigital Library
- S. Mika, G. Rätsch, J. Weston, B. Schölkopf, and K.-R. Müller. Fisher discriminant analysis with kernels. In Y.-H. Hu, J. Larsen, E. Wilson, and S. Douglas, editors, Neural Networks for Signal Processing IX, pages 41--48. IEEE, 1999.Google Scholar
- R. Osada, T. Funkhouser, B. Chazelle, and D. Dobkin. Matching 3D Models with Shape Distributions. In International Conference on Shape Modeling and Applications, pages 154--166, 2001. Google ScholarDigital Library
- G. Rätsch, S. Sonnenburg, and B. Schölkopf. Rase: recognition of alternatively spliced exons in c.elegans. Bioinformatics, 21 Suppl 1:i369--i377, Jun 2005. Google ScholarDigital Library
- B. Schölkopf. Support Vector Learning. R. Oldenbourg Verlag, Munich, 1997. Download: http://www.kernel-machines.org.Google Scholar
- B. Schölkopf and A. Smola. Learning with Kernels. MIT Press, Cambridge, MA, 2002.Google Scholar
- B. Schölkopf, A. J. Smola, and K.-R. Müller. Kernel principal component analysis. In B. Schölkopf, C. J. C. Burges, and A. J. Smola, editors, Advances in Kernel Methods - Support Vector Learning, pages 327--352. MIT Press, Cambridge, MA, 1999. Google ScholarDigital Library
- J.-L. Shih, C.-H. Lee, and J. Wang. 3D object retrieval system based on grid D2. Electronics Letters, 41(4), 2005.Google ScholarCross Ref
- P. Shilane, P. Min, M. Kazhdan, and T. Funkhouser. The Princeton Shape Benchmark. In Shape Modeling International, Genova, Italy, 2004.Google ScholarCross Ref
- S. Sonnenburg, G. Rätsch, and B. Schölkopf. Large scale genomic sequence svm classifiers. In International Conference on Machine Learning, 2005. Google ScholarDigital Library
- S. Sonnenburg, G. Rätsch, and B. Schölkopf. A General and Efficient Multiple Kernel Learning Algorithm. In Neural Information Processing Systems, 2005.Google Scholar
- V. Vapnik. Statistical Learning Theory. John Wiley and Sons, New York, 1998. Google ScholarDigital Library
- S. V. N. Vishwanathan and A. J. Smola. Fast kernels for string and tree matching. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems 15, pages 569--576. MIT Press, Cambridge, MA, 2003.Google ScholarDigital Library
- C. Watkins. Dynamic alignment kernels. CSD-TR-98- 11, Royal Holloway, University of London, Egham, Surrey, UK, 1999.Google Scholar
- A. Zien, G. Rätsch, S. Mika, B. Schölkopf, T. Lengauer, and K.-R. Müller. Engineering Support Vector Machine Kernels That Recognize Translation Initiation Sites. Bioinformatics, 16(9):799--807, Sept. 2000.Google Scholar
Index Terms
- 3DString: a feature string kernel for 3D object classification on voxelized data
Recommendations
Length-weighted string kernels for sequence data classification
Various sequence-similarity kernels, the string kernels, have been introduced for use with support vector machines (SVMs) in a discriminative approach to the sequence data classification problems. In these applications, string kernels are asked to be ...
Action recognition by using kernels on aclets sequences
We propose a string kernel based method for action recognition.The similarity between strings is evaluated by a soft alignment kernel.The experiments have been performed over three standard datasets. In this paper we propose a method for human action ...
3D Object Classification by Fuzzy KNN and Bayesian Decision
IIH-MSP '09: Proceedings of the 2009 Fifth International Conference on Intelligent Information Hiding and Multimedia Signal ProcessingThis paper presents a fuzzy KNN and Bayesian decision based classification method for determining whether a 3D object belongs to human class. To achieve efficiency and simplicity, the view having maximum area is used to substitute a 3D shape, which is ...
Comments