在本論文中，我們提出三維物件之分解、表示、檢索等技術，來處理三維空間計算機圖學上之相關應用。在第一項的研究中，我們提出一個架構在PCA及布林邏輯運算上的三維物件分解技術，它可自動地將物件做有意義的切割。現行的分解技術大多數係採用由上而下的方式來處理，但是這種方式是很難可以有系統地找出三維物件的主要軀幹，然後再做切割。因此，我們結合三維物件中每個三角平面重心的空間絕對座標與其相對於整個物件的距離程度，而形成一個四維的特徵向量。經過PCA的轉換後，我們可以有系統地辨認出三維物件中所有突出的部份，再利用布林邏輯運算可以精確地找到物件的主要軀幹並將軀幹以外的部份自動切割出來。在第二項的研究中，我們提出一個架構在Isomap manifold上的三維物件表示技術，用以搜尋或存取資料庫中之三維物件。因為Isomap的轉換具有兩個優點：一是它會保留住物件整體的結構，同時也保留住各突出部份之間的幾何關係。從認知心理學的觀點來看，分佈在Isomap manifold上的資料可視為此三維物件中之顯著且有意義的特徵向量的集合。然後將這些資料利用圓柱座標的關係投影成兩個二維空間的特徵圖，結果顯示，以此特徵圖為基底可以有效地檢索出資料庫中相對應的三維物件。

In this dissertation, we propose two mesh processing techniques for 3-D graphics-related applications. First, to automatically segment a 3-D mesh-based object, we propose a mesh decomposition scheme based on PCA (Principal Component Analysis) and Boolean operations. It is well known that most of the existing 3-D mesh-based decomposition schemes are bottom-up approaches. With a bottom-up decomposition strategy, it is difficult to devise a systematic way to determine the main body of an arbitrary 3-D object. In this work, we combine the 3-D coordinates and the protrusion degrees of the dual vertices of a 3-D mesh object to form a set of 4-D feature vectors. Then, we perform PCA on the set of 4-D feature vectors derived from the 3-D mesh-based object. After PCA transformation, we can identify all the salient components of an arbitrary 3-D object and precisely separate the salient components of the 3-D object from its main body automatically.
Second, to improve the search/retrieval process of 3-D object in the network environment, we propose a compact 3-D object representation scheme which transforms a 3-D object from the original space into a new coordinate frame by using the Isomap (Isometric feature mapping) method. The transformation process preserves the structure of an object’s salient parts as well as the geometrical relationships between the parts. From the viewpoint of cognitive psychology, the data distributed on the Isomap manifold can be regarded as a set of significant features of a 3-D mesh-based object. To perform efficient matching, we project the Isomap domain’s 3-D object onto two 2-D maps. We then use the two 2-D feature descriptors as the basis for measuring the degree of similarity between two arbitrary 3-D mesh-based objects. The results of experiments demonstrate that the proposed method is very effective in retrieving similar 3-D models.

[1] Hsueh-Yi Lin, Hong-Yuan Mark Liao, and Ja-Chen Lin, “Visual Salience-Guided Mesh Decomposition,” IEEE Transactions on Multimedia, Vol. 9, No. 1, pp. 47-56, 2007.
[2] M. Hilaga, Y. Shingawa, T. Kohmura, and T. L. Kunii, “Topology matching for fully automatic similarity estimation of 3-D shapes,” in Proc. SIGGRAPH, Los Angeles, CA, 2001, pp. 203-212.
[3] H. Yagou, Yu. Ohtake, and A. G. Belyaev, “Mesh smoothing via mean and median filtering applied to face normals,” in Proceedings of Geometric Modeling and Processing 2002, pp. 124-131, Tokyo, July 2002.
[4] L. Kobbelt, S. Campagna, J. Vorsatz, and H.-P. Seidel, “Interactive multi-resolution modeling on arbitrary meshes,” in Computer Graphics (Proceedings of SIGGRAPH 98), pp. 105-114, 1998.
[5] Jolliffe, I.T., Principal Component Analysis, 2nd Ed., Springer, 2002.
[6] Christopher M. Bishop, Neural Networks for Pattern Recognition, Oxford University Press, Oxford, 1995.
[7] S. Katz, G. Leifman and A. Tal “Mesh segmentation using feature point and core extraction,” Visual Comput., Vol. 21, No. 8-10, pp. 865-875, 2005.
[8] S. Katz & A. Tal “Hierarchical Mesh Decomposition using fuzzy clustering and cuts,” in Proc. SIGGRAPH, San Diego, CA, 2003, pp. 954-961.
[9] E. Zuckerberger, A. Tal, and S. Shlafman, “Polyhedral surface decomposition with applications,” Computers and Graphics, Vol.26, No. 5, pp. 733-743, 2002.
[10] X. Li, T. W. Woon, T. S. Tan, and Z. Huang, “Decomposing polygon meshes for interactive applications,” in Proc. ACM Symp. Interactive 3-D Graphics, 2001, pp. 35-42.
[11] Rong Liu and Hao Zhang, “Segmentation of 3D meshes through spectral clustering,” in Pacific Conf. Computer Graphics and Applications, Seoul Korea, Oct. 6-8, 2004, pp. 298-305.
[12] Alan Mangan and Ross Whitaker, “Partitioning 3D surface meshes using watershed segmentation,” IEEE Transaction on Visualization and Computer Graphics, Vol. 5, No. 4, pp. 308-321, 2001.
[13] S. Shlafman, A. Tal, and S. Katz, “Metamorphosis of polyhedral surfaces using decomposition,” in Proc. EUROGRAPHICS, 2002, pp. 219-228.
[14] Y. Zhou and Z. Huang, “Decomposing polygon meshes by means of critical points,” in Proc. MMM, 2004, pp. 187-195.
[15] M. Attene, S. Katz, M. Mortara, G. Patane, M. Spagnuolo, and A. Tal, “Mesh segmentation – A comparative study,” in IEEE International conference on Shape Modeling and Applications, 2006.
[16] S. Schaefer, and C. Yuksel, “Example-Based Skeleton Extraction,” Eurographics Symposium on Geometry Processing, 2007, pp. 1-10.
[17] T-Y Lee, Y-S Wang, and T-G Chen, “Segmenting a Deforming Mesh into Near-Rigid Components,” The Visual Computer, Vol. 22, No. 9-11, pp. 729-739, 2006.
[18] T-Y Lee, P-H Lin, S-U Yan, and C-H Lin, “Mesh decomposition using motion information from animation sequences,” Computer Animation and Virtual Worlds, Vol. 16, No. 3-4, pp. 519-529, 2005.
[19] D. L. James, and C. D. Twigg, “Skinning Mesh Animations,” ACM Transactions on Graphics, Vol. 24, Issue 3, pp. 399-407, 2005.
[20] Yubin Yang, Hui Lin and Yao Zhang, “Content-Based 3-D Model Retrieval: A Survey,” IEEE Transactions on Systems, Man, and Cybernetics—Part C: Applications and Reviews, Vol. 37, No. 6, pp. 1081-1098, 2007.
[21] Hsueh-Yi Sean Lin, Ja-Chen Lin, and Hong-Yuan Mark Liao, “3-D Shape Retrieval Using Cognitive Psychology-based Principles,” Proceedings of the Seventh IEEE International Symposium on Multimedia, pp. 287-294, 2005.
[22] Ilias Kolonias, Dimitrios Tzovaras, Stratos Malassiotis and Michael Gerassimos Strintzis, “Fast Content-Based Search of VRML Models Based on Shape Descriptors,” IEEE Transactions on Multimedia, Vol. 7, No.1, pp. 114-126, 2005.
[23] M. Yu, I. Atmosukarto, W. K. Leow, Z. Huang, and R. Xu, “3D Model Retrieval with Morphing-Based Geometric and Topological Feature Maps,” Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.
[24] D. Vranić and D. Saupe, “3D Shape Descriptor Based on 3D Fourier Transform,” Proceedings of EURASIP Conference on Digital Signal Processing Multimedia Communication Services (ECMCS 2001), Budapest, Hungary.
[25] J. Tangelder and R. C. Veltkamp, “Polyhedral Model Retrieval Using Weighted Point Sets,” International Journal of Image and Graphics, Vol. 3, No. 1, pp. 209-229, 2003.
[26] E. Praun and H. Hoppe, “Spherical Parameterization and Re-meshing,” ACM Transaction on Graphics, Vol. 22, No. 3, pp. 340-349, 2003.
[27] M. Kazhdan, T. Funkhouser, and S. Rusinkiewicz, “Rotation Invariant Spherical Harmonic Representation of 3D Shape Descriptors,” Eurographics Symposium on Geometry Processing, pp. 156-165, 2003, Aachen, Germany.
[28] John M. Lee, Introduction to Topological Manifolds, 1st Ed., Springer-Verlag, 2000.
[29] J. B. Tenenbaum, V. de Silva, and J. C. Langford, “A Global Geometric Framework for Nonlinear Dimensionality Reduction,” Science, Vol. 290, pp. 2319-2323, 2000.
[30] P. Moon and D. E. Spencer, Field Theory Handbook: Including Coordinate Systems, Differential Equations and Their Solutions, 3rd Ed., Springer, 1988.
[31] M. Garland and P. S. Heckbert, “Surface Simplification Using Quadric Error Metrics,” International Conference on Computer Graphics and Interactive Techniques, pp. 209-216, 1997.
[32] D. D. Hoffman and M. Singh, “Salience of visual parts,” Cognition, Vol. 63, pp. 29-78, 1997.
[33] R. Gal and D. Cohen-Or, “Salient Geometric Features for Partial Shape Matching and Similarity,” ACM Transaction on Graphics, Vol. 25, No. 1, pp. 130-150, 2006.
[34] S. Biasotti, S. Marini, M. Spagnuolo, and B. Falcidieno, “Sub-part correspondence by structural descriptors of 3D shapes,” Computer-Aided Design, Vol. 38, Issue 9, pp. 1002-1019, 2006.
[35] Y. Liu, H. Zha, and H. Qin, “A Compact Representation and New Algorithms for 3D Partial Shape Retrieval,” Proceedings of IEEE Computer Society Conference on CVPR, Vol. 2, pp. 2025-2032, 2006.