在三維影像的研究中，如何對點雲物件做有效的特徵值萃取是在三維影像研究主題中重要的一個關鍵，三維點雲的資料量龐大，必需透過精確有效率的方法進行物件處理，達到取得必要關鍵性特徵資訊將能降低後續在儲存與運算程序上成本。現今搜尋技術中文字搜尋為一維索引，圖片搜尋是二維索引，本論文開發立體物件搜尋方法，達到提升應用上的速度進而提升效率。本實驗演算法建基於三維物件骨架編碼對立體模型物件檢索，研究架構主要執行三階段程序：階段1，使用基於reeb graph圖形之三維網格骨架萃取法對目標物件建構以備下一階段編碼之骨架結果;階段2，對已建構生成的物件骨架進行資料編碼，統計與分析骨架各種分支點數量，終端點之數量，階段式層級的骨架長度與平均角度量統計並分析;階段3，使用LLCS法將物件與資料庫樣本做相似度比對。
依序排序出相似度高至低的相似度。本篇的方法不拘限於特定三維物體，應用性較為廣泛，但是須注意的一點為此物體必須要是封閉的完整三維物件才可使用，為避免物體姿勢變化所影響，所以我們加入階層的角度變化特徵質來修正此情況，其相似性結果可用於後續應用如分割、立體物品辨識等等有不錯的資訊提供。

For the sake of extracting effective features from point cloud model is a major topic in the research of 3D computer graphics. Because the quantity of data in 3D model is too large, so a new method, which is proposed in the thesis, is necessary for data reduction. It will improve the efficient of computation and response time of retrieval. The overview of retrieval system develops from words search. In other words, the way looks like search in one dimension. The research flow of 3D model retrieval is popular in recent year. A novel retrieval method base on skeleton chain code is fast and accurate. Another benefit is against the rotation and scaling with multi-resolution. The research which we propose has three stages. Stage one, a skeleton model extraction base on the reeb graph theory. Stage two, we calculate and analyze the terminal points, branch type, number of branch type and edge length in each layer. We convert the 3D model to regular chain code with a summary of the features. Finally, there is a similarity comparison method present. The method likes a sifter. The result is sieved over and over again. It stops when all layers are already done. In the thesis, an experimental model must be none-broken and whole closed. A conclusion supports the application which likes segmentation.

[1] Zhang, C. and Chen, T., “Efficient feature extraction for 2d3d objects in mesh representation,” ICIP 2001, Thessaloniki, Greece, Oct. 7-10(2001)
[2] 鍾國亮，影像處理與電腦視覺第四版，東華，臺北，民國九十五年。
[3] 冬陽，3D遊戲程式設計，宸宇，臺北，民國九十二年。
[4] 施長治，「使用邊角特徵於表格文件辨識之研究」，碩士論文，國立台灣科技大學，台北市(2004)。
[5] Kuo, S., Cross, G. R., “A two-step string-matching procedure,” Pattern Recognition, Vol.24, pp. 711-716(1991)
[6] Varadarajan, K. and Agarwal, P.K., “Approximating shortest paths on a nonconvex polyhedron,” Proc. IEEE Symp. Fundation of Computer Science, FL (1997)
[7] Hilaga, M., Shingagawa, Y., Kohmura, T. and Kunii, T., “Topology matching for fully automatic similarity estimation of 3d shapes,” Proc. of the 28th annual conference on Computer graphics and interactive techniques, NY, USA(2001)
[8] Kolonias, I., Tzovaras, D., Malassiotis, S. and Gerassimos, M., “Fast content-based search of VRML models based on shape descriptors,” Proc. Image Processing, vol. 2, pp. 133-136 (2001)
[9] Bespalov, D., Regli, W.C., Shokoufandeh, A., “Reeb Graph Based Shape Retrieval for CAD,” IDETC/CIE2003, Chicago, Illinois, USA(2003)
[10] Min, P., Chen, J. and Funkhouser, F., “A 2D Sketch Interface for a 3D Model Search Engine,” Proc. Siggraph (2002).
[11] Saupe, D., Vrenic, D., “3d model retrieval with spherical harmonics and moments,” DAGM-Symposium, pp392-397(2001)
[12] Samet, H., Kochut, A., “Octree approximation and compression methods,” 3DPVT, pp460-469 (2002)
[13] Tierny, J., Philip, J., Daoudi, M., “Invariant High Level Reeb Graphs of 3D Polygonal Meshes,” 3D Data Processing, Visualization, and Transmission, pp105-112 NC (2006)
[14] D. V. Vrani’c and D. Saupe, “3D model retrieval,” SCCG 2000, ComeniusUniversity Press, Budmerice Slovakia, (2000)
[15] Suzuki, M., Kato, T. and Otsu, N., “A similarity retrieval of 3D polygonal models using rotation invariant shape descriptors,” Proc of SMC2000, pp.2946-2952, Nashville, TN (2000)
[16] Osada, R., Funkhouser, T., Chazelle, B. and Dobkin, D., “Shape Distributions,” ACM Trans. Graph, Vol. 21, no. 4, pp.807-832 (2002).
[17] Siddiqi, K., Shokoufandeh, A., J. Dickinson, S., and W. Zucker, S., “Shock Graphs and Shape Matching,” International Journal of Computer Vision, Vol. 35, no. 1, pp. 13-32 (1999)
[18] Sundar, H., Silver, D., Gagvani, N. and Dickinson, S., “Skeleton based shape matching and retrieval,” Proc. Shape Model International, pp. 130-139 (2003)
[19] Siddiqi, K., Shokoufandeh, A., Dickinson, S. and Zucker, S., “Shock graphs and shpape matching,” Computer Vision, pp. 222-229 (1998)
[20] Shockoufandeh, A., Dickinson, S.J., Siddiqi, K. and Zucker, S.W.,” Indexing using a Spectral Encoding of Topological Structure,” Proc. Computer Vision Pattern Recognition, vol. 2, pp.491-497 (1999)
[21] Bai, X. and Latecki, L.J. “Path similarity skeleton graph matching,” IEEE Transaction on, Pattern Analysis and Machine Intelligence, vol. 30, issue. 7, pp. 1282-1292 (2008)
[22] Cornea, N.D., Demirci, M.F., Silver, D., Shokoufandeh, A., Dickinson, S.J. and Kantor, P.B. “3D object retrieval using many-to-many matching of curve skeletons,” Conf. Shape Modeling and Applications, pp.366-371, USA (2005)
[23] Yu, M., Atmosukarto, I., Leow, W.K., Huang, Z. and Xu, R., “3D model retrieval with morphing-based geometric and topological feature maps,” Proc. Computer Vision and Pattern Recognition, vol. 2, pp. 656-661, (2003)
[24] Tung, T. and Schmitt, F., “Augmented Reeb Graphs for Content-based Retrieval of 3D Mesh Models,” Proc. Shape Modeling Application, pp.157-166, (2004)
[25] Tierny, J., Vandeborre, J.P. and Daoudi, M., “3D Mesh Skeleton Extraction Using Topological and Geometrical Analyses,” Proc. 14th Pacific Graphics, pp. 85-94, (2006)
[26] Mademlis, A., Daras, P., Tzovaras, D. and Strintzis, M.G., “Combining Topological and Geometrical Features for Global and Partial 3-D Shape Retrieval,” IEEE Transactions on Multimedia, Vol. 10, pp. 819-831, (2008)
[27] Gong, F. and Kang, C.,” 3D Mesh Skeleton Extraction Based on Feature Points,” Conf. ICCET ’09, vol. 1, pp.326-329, (2009)
[28] Manjunath, B.S., Ohm, J. R., Vasudevan, V. V., Yamada, A., “Color and texture descriptions,” IEEE. Transactions on Circuits and System for Video Technology, vol. 11, No.6, June (2001)