形狀比對在電腦圖學以及影像處理的研究領域上一直是基本且重要的問題，並且有廣泛的應用。在這篇論文中，我們提出一個有效的方法解決三維模型之間的比對。我們的方法同時具備全域性拓樸以及區域性幾何的特徵使得比對更為精準。首先，我們從三維模型中提取骨架(skeleton-graphs)，在提取的過程中將同時決定三維模型與骨架的對應。接著，對於skeleton-graph上每一個點，我們嵌入低維度的spherical harmonics做為幾何特徵。而包含拓樸與幾何特徵的skeleton-graph將被轉化為散布在多維度空間的點群，最後，我們在這個多維度的空間中透過兩群點之間的對位來找到對應。利用這個方法，我們的比對能夠克服三維模型的雜訊、位移、旋轉、簡化以及動作上的形變。

Shape matching is a fundamental and important research issue with many applications in computer graphics and visualization. In this paper, we introduce a novel approach for matching 3D polygonal models. Based on the integration of global topological and local geometric features in a shape descriptor, our approach can accurately match 3D models. The method first extracts the skeleton-graphs (a topological descriptor) from the polygon models using a mesh contraction operation. The vertex skeleton correspondence between 3D model and the skeleton graph is also generated in this process. The skeleton-graph of the 3D object is then enhanced by associating the graph nodes with the corresponding local geometries, which are represented by a small set of spherical harmonics (SHs) (a geometric descriptor). Finally, the skeleton-graph containing both topological and geometric features is utilized to point cloud in a multi-dimensional space for shape matching. The experimental results on various 3D models show that the proposed approach is very robust even under the surface disturbances of similarity transformation, noise addition, smoothing, simplification, and pose deformation.

[1][ATC*08] O.K.-C. Au , C.-L. Tai , H.-K. Chu , D. Cohen-Or and T.-Y. Lee: Skeleton extraction by mesh contraction, ACM Transactions on Graphics (TOG), Vol.27, 2008.
[2][ BL08] X. Bai and L.J. Latecki: Path Similarity Skeleton Graph Matching. IEEE Trans. On Pattern Analysis and Machine Intelligence, Vol. 30, pp.1282-1292, 2008.
[3][ BM92] P. J. Besl and N. D.McKay. A method for registration of 3-d shapes. PAMI, 14(2):239–256, Feb. 1992.
[4][ CTSO03] D. Y. Chen, X. P. Tian, Y. T. Shen, and M. Ouhyoung: On visual similarity based 3D model retrieval. Computer Graphics Forum (EUROGRAPHICS’03), vol. 22, no. 3, pp. 223–232, Sep. 2003.
[5][ CBC96] G. Cybenko, A. Bhasin and K. D. Cohen: Pattern Recognition of 3D CAD Objects: Towards an Electronic Yellow Pages of Mechanical Parts. International Journal of Intelligent Engineering Systems, Vol. 95, pp.1-13, 1996.
[6][FMK*03] T. Funkhouser, P. Mi , M. Kazhdan, J. Chen, A. Halderman, D. Dobkin and D. Jacobs: A search engine for 3D models. ACM Trans. Graph. 22, 1, 83-105, 2003.
[7][GC06] R. Gal and D. Cohen-Or: Salient geometric features for partial shape matching and similarity. ACM Transaction on Graphics 2006; 25(1): 130–150.
[8][HSKK01] M. Hilaga, Y. Shinagawa, T. Kohmura and T. L. Kunii: Topology matching for fully automatic similarity estimation of 3D shapes. In ACM SIGGRAPH 2001, Jul. 2001, pp. 203–212.
[9][HLD*08] J. Hua, Z. Lai, M. Dong, X. Gu and H. Qin: Geodesic Distance-Weighted Shape Vector Image Diffusion. IEEE Transactions on Visualization and Computer Graphics, Vol. 14, No. 6, pp. 1643-1650, 2008.
[10][JZ07] V. Jain and H. Zhang: A Spectral Approach to Shape-Based Retrieval of Articulated 3D Models. Computer-Aided Design, Vol. 39, pp. 398-407, 2007.
[11][KFR03] M. Kazhdan, T. Funkhouser and S. Rusinkiewicz: Rotation invariant spherical harmonic representation of 3D shape descriptors. in Proc. Eurographics Symp. Geometry Processing, 2003.
[12][KSDD03] Y. Keselman, A. Shokoufandeh, M. F. Demirci and S. Dickinson: Many-to-many graph matching via metric embedding. In Proceedings of Computer Vision and Pattern Recognition, pp. 850-857, 2003.
[13][KTMS05] I. Kolonias, D. Tzovaras, S. Malassiotis, and M. G. Strintzis, “Fast content-based search of VRML models based on shape descriptors,” IEEE Trans. Multimedia, vol. 7, no. 1, pp. 114–126, Feb. 2005.
[14][LBG*08] X. Li, Y. Bao, X. Guo, M. Jin, X. Gu and H. Qin: Global Optimal Surface Mapping for Shapes of Arbitrary Topology. to appear in IEEE Transactions on Visualization and Computer Graphics, Vol. 14, No. 4, pp. 805-819, 2008.
[15][MDA*08] A. Mademlis, P. Daras, A. Axenopoulos, D. Tzovaras and M.G. Strintzis: Combining Topological and Geometrical Features for Global and Partial 3-D Shape Retrieval. IEEE Transactions on Multimedia, Vol. 10, pp. 819-831, 2008.
[16][Mat99] J. Matousek: On embedding trees into uniformly convex Banach spaces. Israel Journal of Mathematics, 237:221-237, 1999.
[17][OFCD01] R. Osada, T. Funkhouser, B. Chazelle and D. Dobkin: Matching 3D models with shape distributions. In Proceedings of the International Conference on Shape Modeling & Applications. IEEE Computer Society Press, Los Alamitos, CA, 154, 2001.
[18][RTG00] Y. Rubner, C. Tomasi, and L. J. Guibas. The earth mover’s distance as a metric for image retrieval. International Journal of Computer Vision, 40(2):99–121, 2000.
[19][SV01] D. Saupe and D. V. Vranic: 3D model retrieval with spherical harmonics and moments. In Proceedings of the 23rd DAGM-Symposium on Pattern Recognition. Springer-Verlag, Berlin, Germany, pp. 392–397, 2001.
[20][SC06] L. Shen and M. K. Chung: Large-Scale Modeling of Parametric Surfaces Using Spherical Harmonics. Third International Symposium on 3D Data Processing, Visualization, and Transmission (3DPVT'06), pp. 294-301, 2006.
[21][SP04] R. W. Sumner and J. Popović: Deformation transfer for triangle meshes, ACM SIGGRAPH 2004, pp. 399-405, 2004.
[22][SDGD03] H. Sundar, D. Silver, N. Gagvani and S. Dickinson: Skeleton based shape matching and retrieval. In Shape Modelling Int., pp.130-139, 2003.
[23][VS01] D. V. Vranic and D. Saupe: 3D shape descriptor based on 3D fourier transform. In Proc. EURASIP Conf. Digital Signal Processing for Multimedia Communications and Services (ECMCS2001), Budapest, Hungary, Sep. 2001.
[24][VSR01] D. V. Vrani′c, D. Saupe and J. Richter: Tools for 3D-object retrieval: Karhunen-Loeve transform and spherical harmonics. In Proceedings of the 4th IEEE Workshop on Multimedia Signal Processing (MMSP ’01), pp. 293-298, 2001.
[25][WWJ*07] S. Wang, Y. Wang, M. Jin, X. D. Gu and D. Samaras: Conformal geometry and its applications on 3D shape matching, recognition, and stitching. IEEE Transaction on Pattern Analysis Machine Intelligence 2007; 29(7): 1209–1220.
[26][ZDA*07] D. Zarpalas, P. Daras, A. Axenopoulos, D. Tzovaras and M. G. Strintzis: 3D model search and retrieval using the spherical trace transform. EURASIP J. Adv. Signal Process., vol. 2007, no. 23912, p. 14, 2007.
[27][ ZSC*08] H. Zhang, A. Sheffer, D. Cohen-Or, Q. Zhou, O. van Kaick and A. Tagliasacchi: Deformation-Drive Shape Correspondence. Computer Graphics Forum, Vol. 27, No. 5, pp. 1431-1439, 2008.
[28][ ZHDQ08] G. Zou, J. Hua, M. Dong and H. Qin: Surface matching with salient keypoints in geodesic scale space. The Journal of Visualization and Computer Animation, Vol. 19, pp. 399-410, 2008.
[29][SU*91] S. Umeyama. Least-squares estimation of transformation parameters between two point patterns. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(4):376–380, April 1991.