Stratified helix information of medial-axis-points matching for 3D model retrieval

ABSTRACT

With the increase of the number of available 3D models, the need for retrieving models from large databases to help people to find them has gained prominence. In this paper, we propose a method for automatic similarity estimation of 3D shape using stratified helix information of Medial-axis-points, which makes use of critical Medial-axis-points of skeletal instead of medial axes structure, and combines statistic and coordinate information of the Medial-axis-points. Skeleton is useful for many tasks including 3D shape retrieval, virtual navigation, reduced-model formulation, visualization improvement, mesh repair, animation, etc. But it has a high computational cost when applied in similarity estimation of 3D shape. The primary motivation for our approach are that the computational cost is lower than general skeleton method because it does not construct the whole skeleton and the shape matching issue is simplified to compare two vectors which may be different in length. The key idea is described as three steps. Firstly, the pose of triangular three-dimensional models is normalized and voxelized to volumetric objects. Secondly, we represent the signature of objects as stratified helix information of Medial-axis-points built by both Medial-axis-points based on repulsive force field function and the distribution of its rays. Lastly, we evaluate the similarity of objects by using multi-level weighted Hausdorff distance. The contribution of this paper is to utilize a stratified helix structure for every Medial-axis-point to establish stratified helix information, and introduce a variant Hausdorff distance for similarity measure. We find that our method is fast and easy to imply for discriminating between classes of 3D models in a test database. Also, we demonstrate that our method can provides useful discrimination of three-dimensional shapes, which is suitable as a pre-classifier for a recognition or similarity retrieval system.

REFERENCES

• 1: Michael Kazhdan , Thomas Funkhouser , Szymon Rusinkiewicz, Rotation invariant spherical harmonic representation of 3D shape descriptors, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 2: Michael Kazhdan , Thomas Funkhouser, Harmonic 3D shape matching, ACM SIGGRAPH 2002 conference abstracts and applications, July 21-26, 2002, San Antonio, Texas [doi>10.1145/1242073.1242204]
• 3: Masaki Hilaga , Yoshihisa Shinagawa , Taku Kohmura , Tosiyasu L. Kunii, Topology matching for fully automatic similarity estimation of 3D shapes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.203-212, August 2001 [doi>10.1145/383259.383282]
• 4: Michael Kazhdan , Thomas Funkhouser , Szymon Rusinkiewicz, Symmetry descriptors and 3D shape matching, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057448]
• 5: A Survey of Content Based 3D Shape Retrieval Methods, Proceedings of the Shape Modeling International 2004, p.145-156, June 07-09, 2004 [doi>10.1109/SMI.2004.10]
• 6: Iyer, N, Jayanti, S, Lou, K, Kalyanaraman, Y, and Ramani, K. Three-Dimensional Shape Searching: State-of-the-Art Review and Future Trends. Computer-Aided Design, 37, 5 (Apr 2005), 509--530.
• 7: 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]
• 8: Thomas Funkhouser , Patrick Min , Michael Kazhdan , Joyce Chen , Alex Halderman , David Dobkin , David Jacobs, A search engine for 3D models, ACM Transactions on Graphics (TOG), v.22 n.1, p.83-105, January 2003 [doi>10.1145/588272.588279]
• 9: Jia, J, Qin, Z, and Lu, J. a Method for 3d Model Retrieval Using Grid Decomposition of Boundary Vertexes of 2d Projection. Chinese Journal of Computers, 29, 12 (2006), 2119--2129.
• 10: JIA, J, QIN, Z, LU, J, and SHI, Z W. Method for 3d Model Retrieval Using Circle Ray Decomposition of Projection Contour. Journal of System Simulation 18, 10 (2006), 2847--2851.
• 11: Chen, D Y and Ouhyoung, M. A 3d Object Retrieval System Based on Multi-Resolution Reeb Graph. In Proceedings of Computer Graphics Workshop. (Taiwan, June, 2002). 2002, 16--20.
• 12: Blum, H. A Transformation for Extracting New Descriptors of Shape. In Proceedings of the Symposium on Models for Perception of Speech and Visual Form. (Cambridge, MA, 1967). MIT Press, 1967, 362--380.
• 13: Cornea, N D, Silver, D, and Min, P. Curve-Skeleton Applications. IEEE Visualization' 2005, (2005), 95--102.
• 14: Chuang, J H. Potential-Based Modeling of Three-Dimensional Workspace for Obstacle Avoidance. IEEE Transactions on Robotics and Automation, 14, 5 (1998), 778--785.
• 15: Jen-Hi Chuang , Chi-Hao Tsai , Min-Chi Ko, Skeletonization of Three-Dimensional Object Using Generalized Potential Field, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.11, p.1241-1251, November 2000 [doi>10.1109/34.888709]
• 16: Pin-Chou Liu , Fu-Che Wu , Wan-Chun Ma , Rung-Huei Liang , Ming Ouhyoung, Automatic Animation Skeleton Construction Using Repulsive Force Field, Proceedings of the 11th Pacific Conference on Computer Graphics and Applications, p.409, October 08-10, 2003
• 17: Wu, F C, Ma, W C, and Ouhyoung, M. Skeleton Extraction of 3d Objects with Visible Repulsive Force. In Computer Graphics Workshop 2003. (Hua-Lien, Taiwan, 2003). 2003.
• 18: Pu Jiantao , Liu Yi , Xin Guyu , Zha Hongbin , Liu Weibin , Yusuke Uehara, 3D Model Retrieval Based on 2D Slice Similarity Measurements, Proceedings of the 3D Data Processing, Visualization, and Transmission, 2nd International Symposium, p.95-101, September 06-09, 2004 [doi>10.1109/3DPVT.2004.3]
• 19: Elmar Eisemann , Xavier Décoret, Fast scene voxelization and applications, Proceedings of the 2006 symposium on Interactive 3D graphics and games, March 14-17, 2006, Redwood City, California [doi>10.1145/1111411.1111424]
• 20: Zhao Dong , Wei Chen , Hujun Bao , Hongxin Zhang , Qunsheng Peng, Real-time Voxelization for Complex Polygonal Models, Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, p.43-50, October 06-08, 2004
• 21: Wu, X, Liu, W, and Wang, T. A New Method on Converting Polygonal Meshes to Volumetric Datasets. In Proceedings of 2003 IEEE International Conference on Robotics, Intelligent Systems and Signal Processing. (2003). 2003, 116--120.
• 22: Cornea, N D, Silver, D, Yuan, X, and Balasubramanian, R. Computing Hierarchical Curve-Skeletons of 3d Objects. The Visual Computer, 21, 11 (2005), 945--955.
• 23: Narendra Ahuja , Jen-Hui Chuang, Shape Representation Using a Generalized Potential Field Model, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.2, p.169-176, February 1997 [doi>10.1109/34.574801]
• 24: A. Globus , C. Levit , T. Lasinski, A tool for visualizing the topology of three-dimensional vector fields, Proceedings of the 2nd conference on Visualization '91, October 22-25, 1991, San Diego, California
• 25: The Princeton Shape Benchmark, Proceedings of the Shape Modeling International 2004, p.167-178, June 07-09, 2004 [doi>10.1109/SMI.2004.63]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Abstracting methods
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
medial-axis-points, multilevel weighted Hausdorff distance, similarity estimation of 3D shape, stratified helix information