臺灣博碩士論文加值系統

近年來，3D風潮如同旱地驚雷般地在所有領域颳起一陣旋風，諸如遊戲、動畫、網路、機械、娛樂，大量的三維模型應運而生。如此大量的三維模型資料庫在搜尋上將造成相當大的問題。
一般關鍵字的搜尋方式不僅不直覺，而且隨著每個人主觀的分類不同，往往不能滿足我們在三維模型萃取上的需求。而傳統二維影像的搜尋、比對，其資訊僅止於顏色，較為容易處理。而三維模型則擁有相當多而且複雜的特性，至目前為止，仍未有可以稱作標準的處理方式。我們在此延伸skeletal matching的方式，建立一新的比對方式-拼圖式axis to axis的比對來解決三維模型相似度的比較問題。
本論文主要是利用表面距離來建立一個類似骨架的Reeb graph，Reeb graph能夠抵抗各種三維模型的旋轉、平移、縮放等等問題，並且概略地表示整個模型的骨架。而評比兩個模型相似度則可以透過簡單的評比兩個Reeb graph來達成，我們模擬人類拼圖的方式將較為特殊、容易辨識的部分先對應起來，藉此降低對應錯誤的機率，有別於一般深度優先（depth-first）或廣度優先(width-first)的循序對應方式，我們比對的順序將是依照發生對應錯誤的機率的順序來處理。
我們採用不同的表面距離估算方式來達到即使不需切割模型三角形也能估計出相當正確的表面距離值，並由此建立Reeb graph。最後採用拼圖式axis to axis的比對降低錯誤對應的發生，使三維模型萃取的結果更加合理。

Due to the fast development of three dimensional model in many fileds, like game, animation, network, mechanical engineering and entertainments, we believe that searching three dimensional models in database will become more important.
A traditional searching method, keyword searching, is not a stable method. Because the classify standard of each people is different, it can’t satisfy our requirement in three dimensional retrieval. In two dimensional image retrieval, the problem is easier because only one information, color, in a image. But in three dimensional model retrieval problem, there isn’t a standard function which can evaluate similarity between two models. We use a matching method to evaluate similarity between two skeletal graphs of models, namely 2-pass axis-to-axis matching method. The method is like a jigsaw puzzle.
We first use geodesic distance to establish a skeletal graph - Reeb graph. It can roughly represent the skeleton of model and invariant to translation, rotation, scaling. Then we match two Reeb graphs and evaluate similarity. When matching two Reeb graphs, a concept of matching significant node first is used. It is different to depth-first and width-first, and we will matching most significant node first.
We don’t need to subdivide triangles of model by using modified fast marching method, and we can approximate the geodesic distance. Building Reeb graph by geodesic distance and evaluating similarity between two Reeb graph by using our 2-pass axis-to-axis matching method.

第一章 導論……………………………………………………………1
1.1研究動機與目標………………………………………………1
1.2本論文之大綱內容……………………………………………2
1.3本論文的方法特性……………………………………………3
1.4研究創新與實用價值評述……………………………………4
第二章 相關工作………………………………………………………4
2.1 PCA方式………………………………………………………7
2.2 Shape Distribution方式……………………………………12
2.3 Flatten方式…………………………………………………15
2.4 Skeletal Matching方式……………………………………19
2.5 Topology Matching方式……………………………………21
2.5 Sketch方式…………………………………………………31
第三章 3D Model Retrieval方法大綱……………………………32
3.1 3D Model Retrieval的基本流程……………………………32
3.2本論文採用的3D Model Retrieval的基本架構流程及特性…34
第四章 計算Geodesic Distance……………………………………39
4.1相關工作……………………………………………………39
4.2 Fast Marching Methods………………………………42
4.3本論文用來計算geodesic distance的方法………………63
第五章 Matching 方式…………………………………………83
5.1相關理論及概念……………………………………………83
5.2 Matching概念和實作方式…………………………………90
5.3 Matching分析比較…………………………………………101
第六章 實驗結果及討論……………………………………………102
6.1實驗結果……………………………………………………102
6.2 討論…………………………………………………………112
第七章 結論及未來展望……………………………………………117
7.1 結論…………………………………………………………117
7.2 未來展望……………………………………………………117
參考資料………………………………………………………………119
附錄一…………………………………………………………………122

1.M. Hilaga, Y. Shinagawa, T. Kohmura, and T. Kunii. Topology Matching for Fully Automatic Similarity Estimation of 3D Shapes. ACM SIGGRAPH 2001 Proceedings, August 2001
2.J. A. Sethian. Fast Marching Methods. SIAM Review Vol. 41, No.2, pp.199-235
3.M. Novotni, R. Klein. Computing Geodesic Distances on Triangular Meshes. in proceedings of The 10-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision'2002 (WSCG'2002), February 2002
4.C. Zhang and T. Chen. Efficient Feature Extraction for 2D/3D Objects in Mesh Representation. ICIP 2001, Thessaloniki, Greece, Oct. 7-10, 2001.
5.D. V. Vranic’ and D. Saupe. 3D model retrieval. Proc. of Spring Conf. On Comp. Graph. and its Appl. (SCCG2000), Budmerice, Slovakia, pp.89-93, May 2000.
6.R. Osada, T. Funkhouser, B. Chazelle, and D. Dobkin. Matching 3D Models with Shape Distributions. in Shape Modeling International, Genova, Italy, May 2001.
7.Heung-Yeung Shum, Martial Hebert, Katsushi Ikeuchi. On 3D Shape Similarity. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR '96), June, 1996, pp. 526 - 531.
8.M. Novotni, R. Klein. A Geometric Approach to 3D Object Comparison. Proceedings of International Conference on Shape Modeling and Applications, May 2001, pages 167-175.
9.Dietmar Saupe, Dejan Vranic. 3D Model Retrieval with Spherical Harmonics and Moments. DAGM-Symposium 2001: 392-397.
10.D. Zhang and M. Hebert. Harmonic Maps and Their Applications in Surface Matching. IEEE Conference on Computer Vision and Pattern Recognition (CVPR '99), Vol. 2, 1999.
11.Ding-Yun Chen and Ming Ouhyoung . A 3D Object Retrieval System Based on Multi-Resolution Reeb Graph. 2002 Computer Graphics Workshop.
12.Michela Mortara, Michela Spagnuolo. Shape Blending Similarity Measures for Blending Polygonal Shapes. Computers & Graphics 25 (2001) 13}27
13.AnneVerroust, Francis Lazarus. Extracting Skeletal Curves from 3D Scattered Data. The Visual Computer (2000) 16:15–25
14.Barequet and Sharir. Partial Surface and Volume Matching in Three Dimensions. IEEETPAMI: IEEE Transactions on Pattern Analysis and Machine Intelligence, 19, 1997.
15.Volumetric Shape Matching and Visualization http://www.caip.rutgers.edu/~hsundar/vis02/vis02.html#barequet97partial
16.K. Siddiqi, A. Shokoufandeh, S. Dickinson, and S. Zucker. Shock Graphs and Shape Matching. International Journal of Computer Vision, 30:1-24, 1999.
17.Princeton Shape Retrieval and Analysis, 3D Model Search, http://shape.cs.princeton.edu/search.html , 2002
18.R. Osada, T. Funkhouser, B. Chazelle, and D. Dobkin. Shape Distributions. in ACM Transactions on Graphics, 2002.
19.Patrick Min, Joyce Chen and Thomas Funkhouser. A 2D Sketch Interface for a 3D Model Search Engine. SIGGRAPH 2002 Technical Sketch
20.Serge Belongie, Jitendra Malik and Jan Puzicha. Matching Shapes. Eighth IEEE International Conference on Computer Vision (July 2001)
21.Thomas B. Sebastian Philip N. Klein Benjamin B. Kimia. Recognition of Shapes by Editing Shock Graphs. ICCV 2001, pages 755-762
22.Motofumi T. Suzuki. A Search Engine for Polygonal Models to Support Development of 3D E-Learning Applications. The Tenth International World Wide Web Conference Poster Proceedings pp.182-183,Paper ID:1047, Hong Kong,　05/2001.
23.D. V. Vranic, D. Saupe, and J. Richter. Tools for 3D-object retrieval: Karhunen-Loeve Transform and spherical harmonics. In: Proceedings of the IEEE 2001 Workshop Multimedia Signal Processing, Cannes, France, pp. 293-298, October 2001.
24.G. Zigelman, R. Kimmel, N. Kiryati. Texture Mapping Using Surface Flattening via Multidimensional Scaling. IEEE Transactions on Visualization and Computer Graphics,April-June 2002 (Vol. 8, No. 2). pp. 198-207
25.M. Novotni, R. Klein. Geometric 3D Comparison - an Application. in proceedings of ECDL WS Generalized Documents 2001
26.Jen-Hui Chuang, Chi-Hao Tsai, Min-Chi Ko. Skeletonization of Three-Dimensional Object Using Generalized Potential Field. IEEE Transactions on Pattern Analysis and Machine Intelligence 22(11): 1241-1251 (2000)
27.P. J. Besl and N. D. McKay. A method for registration of 3-D shapes. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, vol. 14, no. 2, pp. 239-256, 1992.
28.ALT, H. and GUIBAS, L.J. Discrete Geometric Shapes: Matching, Interpolation, and Approximation - A Survey. Technical Reports der FU Berlin, Institut fur Informatik u. Mathematik. (1996)
29.R.C. Veltkamp. Shape Matching: Similarity Measures and Algorithms. Technical Report UU-CS-2001-03 January 2001
30.Motofumi T. Suzuki, Toshikazu Kato and Nobuyuki Otsu. A Similarity Retrieval of 3D Polygonal Models Using Rotation Invariant Shape Descriptors. IEEE International Conference on Systems, Man, and Cybernetics (SMC2000), pp2946-2952, Nashville, Tennessee,10/2000.
31.M. Hebert, K. Ikeuchi, H. Delingette. A Spherical Representation for Recognition of Free-Form Surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence July 1995 (Vol. 17, No. 7)
32.Yoshihisa Shinagawa, Tosiyasu L. Kunii, Yannick L. Kergosien. Surface Coding Based on Morse Theory. IEEE Computer Graphics and Applications September/October 1991 (Vol. 11, No. 5)
33.A Survey of Shape Analysis Techniques
34.Takashi Kanai and Hiromasa Suzuki. Approximate Shortest Path on a Polyhedral Surface Based on Selective Refinement of the Discrete Graph and Its Applications. Proc. IEEE Geometric Modeling and Processing 2000 (Theory and Applications), Hong Kong April 10-12, pp. 241-250, (2000)
35.Pankaj K. Agarwal, Sariel Har-Peled, Meetesh Karia. Computing Approximate Shortest Paths on Convex Polytopes. Algorithmica 33(2): 227-242 (2002)
36.J.C. Hart. Morse Theory for Implicit Surface Modeling. Mathematical Visualization, H-C Hege and K. Polthier, Eds., Springer-Verlag, Oct. 1998, pp. 257-268.
37.Douglas R. Heisterkamp, Prabir Bhattacharya. Matching of 3D Polygonal Arcs. IEEE Transactions on Pattern Analysis and Machine Intelligence 19(1): 68-73 (1997)
38.K. Varadarajan and P. K. Agarwal. Approximating shortest paths on a nonconvex polyhedron. In Proc. IEEE Symp. on Foundations of Comp. Sci., 1997.
39.Michael Kazhdan and Thomas Funkhouser. Harmonic 3D Shape Matching. SIGGRAPH 2002 Technical Sketch
40.M.G. Crandall and P.-L. Lions. Viscosity solutions of Hamilton-Jacobi equations. Trans. Amer. Math. Soc., 277 (1983), pp. 1-43.
41.H.N. Gabow, M.X. Goemans and D.P. Williamson, An Efficient Approximation Algorithm for the Survivable Network Design Problem, Mathematical Programming, 82, 13--40, 1998.
42. http://amp.ece.cmu.edu/projects/3DModelRetrieval/