臺灣博碩士論文加值系統

　　隨著3D模型在數位圖書館中的數量逐漸增加，我們需要一個搜尋系統去幫助人們找到他們所要的3D資料。對於3D模型資料庫的管理，首先要建立一個有效率的分類及搜尋方法，而捨棄傳統以文字為檢索鍵的方法。目前以3D模型本身的內容（content）為檢索鍵的搜尋方式是3D模型資料庫管理上的最佳利器!因此如何建立一個有效的3D模型搜尋系統，讓使用者可以利用此一系統快速地找到在大型3D模型資料庫中符合使用者個人期待的相似3D模型，是本篇論文首要目標。
　　在本論文中提出一個全新以形狀為基礎的3D模型特徵擷取演算法，並且具有相關性回饋（relevance feedback）的3D模型搜尋系統。所以本系統將包含三個部分，特徵擷取、3D 模型搜尋以及相關性回饋演算法。在特徵擷取的部份，本論文提出改良式D2與六立面圖特徵擷取法（elevation descriptor），六立面圖特徵擷取法的主要概念為收集3D模型在六個不同的視角下的立面形狀分布。本論文除了提出新的特徵擷取方法以外，還結合球形諧波（spherical harmonics）、MPEG-7的3D形狀頻譜描述（3D shape spectrum descriptor）來計算每一個3D模型的特徵。在搜尋的部份，先利用全部特徵在資料庫中找出與使用者想搜尋的3D模型相似度較高的模型回應給使用者，使用者再從這些3D模型中挑選其想要的結果。最後使用相關性回饋演算法，依照使用者的挑選，回應出最接近使用者所想要的3D模型。

摘要．．．．．．．．．．．．．．．．．．．．．．．．． 1
致謝．．．．．．．．．．．．．．．．．．．．．．．．． 2
目錄．．．．．．．．．．．．．．．．．．．．．．．．． 3
附圖目錄．．．．．．．．．．．．．．．．．．．．．．． 6
附表目錄．．．．．．．．．．．．．．．．．．．．．．．10
第一章 序論．．．．．．．．．．．．．．．．．．．．． 11
1.1 動機．．．．．．．．．．．．．．．．．．．．．．．13
1.2 論文架構．．．．．．．．．．．．．．．．．．．．．15
第二章 相關研究．．．．．．．．．．．．．．．．．．． 17
2.1 將三維模型轉換成多個二維剪影圖形．．．．．．．．．18
2.1.1 三維模型的調準與檢索系統．．．．．．．．．．．．18
2.2 主軸分析．．．．．．．．．．．．．．．．．．．．．20
2.2.1 二維與三維物件的特徵擷取比對描述．．．．．．．．23
2.2.2 三維物件的幾何比對．．．．．．．．．．．．．．．24
2.3 三維幾何形狀分佈．．．．．．．．．．．．．．．． 25
2.3.1 幾何形狀分佈的三維模型比對．．．．．．．．．．．26
2.3.2 三維形狀頻譜描述．．．．．．．．．．．．．．．．28
2.4 骨架對應．．．．．．．．．．．．．．．．．．．．．32
2.4.1 拓撲學比對方式的自動化三維形狀相似性評估．．．．34
2.4.2 多重解析里布圖的三維物件檢索系統．．．．．．．．35
2.5 球型諧波．．．．．．．．．．．．．．．．．．．．．36
2.5.1 球型諧波與矩量的三維模型檢索．．．．．．．．．．37
2.5.2 三維模型搜尋引擎．．．．．．．．．．．．．．．．38
第三章 三維模型特徵擷取．．．．．．．．．．．．．．． 43
3.1 改良式D2．．．．．．．．．．．．．．．．．．．．．43
3.2 六立面圖特徵擷取演算法．．．．．．．．．．．．．．47
第四章 三維模型檢索．．．．．．．．．．．．．．．．． 51
4.1 特徵向量比對方法．．．．．．．．．．．．．．．．．51
4.1.1 改良式D2的比對方法．．．．．．．．．．．．．．．51
4.1.2 六立面圖特徵向量的比對方法．．．．．．．．．．．53
4.2 相關性回饋演算法．．．．．．．．．．．．．．．．．57
第五章 實驗結果．．．．．．．．．．．．．．．．．．． 62
5.1 實驗環境．．．．．．．．．．．．．．．．．．．．．62
5.2 變形、旋轉、不同大小、不同解析度之實驗．．．．．．69
5.3 檢索普林斯頓形狀基準資料庫之實驗．．．．．．．．．74
第六章 結論與未來方向．．．．．．．．．．．．．．．． 79
參考文獻．．．．．．．．．．．．．．．．．．．．．．．80

[1] M. T. Maybury, “Intelligent multimedia information retrieval,” The AAAI Press, pp. 590, 1997.
[2] J. L. Shih and L. H. Chen, “A New System for Trademark Segmentation and Retrieval,” Image and Vision Computing, Vol. 19, pp. 1011-1018, 2001.
[3] J. L. Shih and L. H. Chen, “A Context-Based Approach for Color Image Retrieval,” International Journal of Pattern Recognition and Artificial Intelligence, Vol. 16, pp. 239-255, 2002.
[4] J. L. Shih and L. H. Chen, “Color Image Retrieval Based On Primary Color Moments”, IEE Proceedings-Vision, Image and Signal Processing, Vol. 149, No. 6, pp. 370-376, December 2002.
[5] QBIC, the IBM QBIC project, Demo: http://wwwqbic.almaden.ibm.com/.
[6] M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, and P. Yanker, “Query by image and video content: The QBIC system,” IEEE Computer, Vol. 28, No. 9, pp. 23-32, 1995.
[7] C. Faloutsos, R. Barber, M. Flickner, J. Hafner, W. Niblack, D. Petkovic, and W. Equitz, “Efficient and effective querying by image content,” J. Intell. Inform. Sys. Vol. 3, pp. 231-262, 1994.
[8] Virage, the project of Virage Inc., Demo: http://virage.com/.
[9] J. R. Bach, C. Fuller, A. Gupta, A. Hampapur, B. Horowitz, R. Humphrey, R. Jain, and C. F. Shu, “The Virage image search engine: An open framework for image management,” in Proc. of SPIE Storage and Retrieval for Still Image and Video Databases IV, pp. 76-87, San Jose, CA, USA, February 1996.
[10] MARs, the Multimedia analysis and retrieval system developed at University of Illinois at Urbana-Champaign.
[11] S. Mehrotra, Y. Rui, O. B. Michael, and T. S. Huang, “Supporting content-based queries over images in MARS,” in Proc. of IEEE Int. Conf. Multimedia Computing and Systems, pp. 632-633, 1997.
[12] Y. Rui, T. S. Huang, M. Ortega, and S. Mehrotra, “Relevance feedback: A power tool in interactive content-based image retrieval,” IEEE Tran. Circuits Systems Vedio Technol (Special Issue on Interactive Multimedia Systems for the internet), Vol. 8, No. 5, pp. 644-655, Sept. 1998.
[13] X. S. Zhou and T. S. Huang, “Image retrieval: feature primitives, feature representation, and relevance feedback,” in Proc. of IEEE Workshop on Content-Based Access of Image and Video Libraries, in Conjunction with CVPR'00, pp. 10-14, 2000.
[14] M. S. Lew, Principles of visual information retrieval, 2001.
[15] WebSEEk, the World Wide Web oriented text/image search engine.
[16] R. Smith and S. F. Chang, “Visually searching the web for content,” IEEE Trans. Multimedia, Vol. 4, No. 3, pp. 12-20, 1997.
[17] J. R. Smith and S. F. Chang, “VisualSEEk: a fully automated content-based image query system,” in Proc. of ACM Multimedia, Boston, MA, Nov. 1996.
[18] J. R. Smith and S. F. Chang, “Tools and techniques for color image retrieval,” SPIE Storage and Retrieval for Image and Video Database IV, Vol. 2670, 1996.
[19] A. Pentland, R. W. Picard and S. Sclaroff, “Photobook: Tools for content-based manipulation of image databases,” SPIE Storage and Retrieval Image and Video Databases II, Vol. 2185, pp. 6-10, San Jose, CA, Feb. 1993.
[20] C. Carson, S. Belongie, H. Greenspan, and J. Malik, “Region-based image querying,” in Proc. of IEEE Workshop on Content-Based Access of Image and Video Libraries, in Conjunction with CVPR'97, pp. 762-768, 1997.
[21] I. S. Hsieh and K. C. Fan, “Multiple classifiers for color flag and trademark image retrieval,” IEEE Tran. Image Processing, Vol. 10, No. 6, pp. 938-950, June 2001.
[22] T. Kato, T. Kurita, and H. Shimogaki, “Intelligent visual interaction with image database systems-toward multimedia personal interface,” J. Inform. Process. Vol. 14, No. 2, pp. 134-143, 1991.
[23] T. Kato, “Database architecture for content-based image retrieval,” SPIE Image Storage and Retrieval Systems, Vol. 1662, pp.112-122, 1992.
[24] Google, Demo: http://www.google.com/.
[25] Mesh name: Pig. Mesh format: 3DS Format. The 3D Model Collection, Demo: http://www.fantasticarts.com/3dmodels/index.htm.
[26] S. Brin and L. Page. “The anatomy of a large-scale hypertextual Web search engine,” Computer Networks and ISDN Systems, pp. 30(1-7):107-117, 1998.
[27] MPEG Video Group, “MPEG-7 Visual part of eXperimetation Model Version 9.0,” Doc. ISO/IEC JTC1/SC29/WG11/N3914, Pisa, January 2001.
[28] Y. Rui, T. S. Huang, M. Ortega, and S. Mehrotra, “Relevance feedback: A power tool in interactive content-based image retrieval,” IEEE Tran. Circuits Systems Vedio Technol (Special Issue on Interactive Multimedia Systems for the internet), Vol. 8, No. 5, pp. 644-655, Sept. 1998.
[29] G. Arfken, “Spherical Harmonics,” Mathematical Methods for Physicists, 3rd ed. Orlando, FL: Academic Press, pp. 680-685, 1985.
[30] T. Funkhouser, P. Min, M. Kazhdan, J. Chen, A. Halderman, D. Dobkin, and D. Jacobs “A Search Engine for 3D Models” in Proc. of ACM Transactions on Graphics, Vol. 22(1), pp. 83-105, January 2003.
[31] B. S. Manjunath, P. Salembier, and T. Sikora, “Introduction to MPEG-7 Multimedia Content Description Interface.” John Wiley & Sons Ltd., pp. 247-260, 2002.
[32] T. Igarashi, S. Matsuoka, and H. Tanaka, “Teddy: A Sketching Interface for 3D Freeform Design,” in Proc. of ACM SIGGRAPH, pp. 409-416, Los Angeles, USA, Aug. 1999.
[33] P. Min, J. Chen, and T. Funkhouser, “A 2D Sketch Interface for a 3D Model Search Engine,” SIGGRAPH 2002 Technical Sketches, pp. 138, July, 2002.
[34] D. Y. Chen and M. Ouhyoung, “A 3D Model Alignment and Retrieval System,” in Proc. of International Computer Symposium, Workshop on Multimedia Technologies, Vol. 2, pp. 1436-1443, Hualien, Taiwan, Dec. 2002.
[35] D. V. Vranic and D. Saupe, “3D Model Retrieval,” in Proc. of Spring Conference on Computer Graphics and its Applications (SCCG2000), Budmerice Manor, Slovakia, pp. 89-93, May 2000.
[36] C. Zhang and T. Chen, “Efficient Feature Extraction for 2D/3D Objects in Mesh Representation,” in Proc. of IEEE International Conference on Image Processing (ICIP), pp. 935-938, Thessaloniki, Greece, Oct. 2001.
[37] M. Novotni and R. Klein, “A Geometric Approach to 3D Object Comparison,” in Proc. of International Conference on Shape Modeling and Applications, May 2001, pp. 167-175.
[38] R. Osada, T. Funkhouser, B. Chazelle, and D. Dobkin “Shape Distributions,” ACM Transactionsons on Graphics, Vol. 21, No. 4, pp. 807-832, Oct. 2002.
[39] R. Osada, T. Funkhouser, B. Chazelle, and D. Dobkin, “Matching 3D models with shape distributions,” Shape Modeling International, pp. 154-166, May 2001.
[40] C. T. Loop, “Smooth Subdivision Surfaces Based on Triangles,” Master’s Thesis, Department of Mathematics, University of Utah, Salt Lake City, Utah, USA, 1987.
[41] M. Hilaga, Y. Shinagawa, T. Kohmura, and T. L. Kunii, “Topology Matching for Fully Automatic Similarity Estimation of 3D Shapes,” in Proc. of ACM SIGGRAPH, pp. 203-212, Los Angeles, USA, Aug. 2001.
[42] D. Y. Chen and M. Ouhyoung, “A 3D Object Retrieval System Based on Multi-Resolution Reeb Graph,” in Proc. of Computer Graphics Workshop, pp. 16, Tainan, Taiwan, June 2002.
[43] M. Ankerst, G. Kastenmller, H.P. Kriegel, and T. Seidl, “3D shape histograms for similarity search and classification in spatial databases,” in Proc. SSD, 1999.
[44] D. Saupe and D. V. Vrani, “3D model retrieval with spherical harmonics and moments,” DAGM 2001, pp. 392-397, 2001.
[45] Spherical Harmonic. Eric Weisstein’s world of Mathematics (Math World), Demo: http://mathworld.wolfram.com/.
[46] W. B. Frakes and R. Baeza-Yates, “Information Retrieval: Data Structure and Algorithms,” Prentice Hall, 1992.
[47] D. Harman, “Overview of the third Text REtrieval Conference (TREC-3),” in Proc. of the Third Text Retrieval Conference, pp.1-19, 1994.
[48] P. Srinivasan, “Query Expansion and MEDLINE,” Information Processing & Management, Vol. 32, No. 4, pp. 431-443, 1996.
[49] Y. Deng and B. S. Manjunath, “ An efficient low-dimensional color indexing scheme for region-based image reitrieval,” in Proc. of IEEE Int. Conf. Acoustics, Speech, and Signal Processing, Vol. 6, pp. 3017-3020, 1999.
[50] Princeton Shape Benchmark, http://shape.cs.princeton.edu/benchmark/.
[51] P. Shilane, P. Min, M. Kazhdan, and T. Funkhouser, “The Princeton Shape Benchmark,” in Proc. of Shape Modeling International, Genova, Italy, June 2004.
[52] B. Horn. “Extended Gaussian images,” in Proc. of the IEEE, Vol. 72(12), pp. 1671-1686, December 1984.
[53] S. Kang and K. Ikeuchi. “Determining 3-D object pose using the complex extended Gaussian image,” in Proc. of CVPR, pp. 580-585, June 1991.
[54] D. V. Vranic. “An improvement of rotation invariant 3D shape descriptor based on functions on concentric spheres,” in Proc. of IEEE International Conference on Image Processing (ICIP 2003), vol. 3, pp. 757-760, September 2003.
[55] D. Y. Chen, M. Ouhyoung, X. P. Tian, and Y. T. Shen. “On visual similarity based 3D model retrieval,” Computer Graphics Forum, Vol. 22, No. 3, pp. 223-232, 2003.