臺灣博碩士論文加值系統

面對日益龐大的三維模型資料庫 (3D model database)，需要一個快速有效的內容檢索 (content-based retrieval) 方法協助管理。本研究以投影深度圖 (projection depth map) 與動差不變量 (moment invariants) 為基礎，探討三維模型的特徵萃取 (feature extraction) 及內容檢索 (content-based retrieval) 方法。本研究分成離線運算和線上檢索等兩個階段，在離線運算階段，我們對每個資料庫模型的位置與大小進行正規化，再將攝影機設置在包覆模型的正十二面體 (dodecahedron) 的二十個頂點及三個方向，並進行正交投影 (orthographic projection) 而得到六十張投影深度圖 (projection depth map)，接著計算每張投影深度圖的二維動差不變量以產生第一組特徵向量，再計算每個模型的三維動差不變量以產生第二組特徵向量；在線上檢索階段，使用者可以任選三維模型做為查詢模型 (query model)，系統會以二維或三維動差不變量為基礎，自動比對查詢模型與資料庫模型，並於一秒內回覆最相似的資料庫模型；此外，若使用者輸入二值化影像，系統會對每個模型進行局部比對，並結合搜尋演算法快速逼近輸入查詢影像，進而找出具有相似投影的三維模型。實驗結果展示本研究所提出的三維模型檢索方法的正確性與高效率。

In this study, we purpose a new content-based approach to retrieving 3D models from a database, based on projection depth maps and moment invariants. Our system can be divided into offline and online stages. In the offline stage, the location and size of each model is normalized first. For each normalized model and its circumscribed dodecahedron, sixty projection depth maps are obtained at the twenty vertices and with three directions. Afterward, 2D and 3D moment invariants are computed for each map and constitute two feature vectors respectively. In the online stage, a user can choose a 3D model as the query. Our system can match the query with each 3D model in the database and reply the most similar models within 1 second. If a user inputs a binary image as the query, our system can extract 2D moment invariants from the query and perform partial matching with each 3D model. A logarithmic searching strategy is proposed to improve the efficiency of partial matching. Accordingly, the 3D models with through similar projection maps will be retrieved. Experimental results show that the proposed approach is effective and efficient.

中文摘要 i
英文摘要 ii
誌謝 iii
目錄 v
表目錄 vii
圖目錄 viii
第一章 緒論 1
1.1 研究動機與目的 1
1.2 論文架構 2
第二章 文獻探討 3
2.1 以拓撲特性為基礎的相似比對 5
2.1.1 以骨架為基礎 5
2.1.2 Reeb Graph 5
2.2 以形狀為基礎的相似比對 7
2.2.1 形狀分佈 7
2.2.2 球型泛波 8
2.2.3 點密度 10
2.3 以影像為基礎的相似比對 10
2.3.1 二維傅立葉轉換 11
2.3.2 基於輪廓圖 12
2.3.3 基於視覺相似的影像 14
第三章 研究方法 17
3.1 系統架構 17
3.2 模型正規化 19
3.2.1 平移 20
3.2.2 縮放 20
3.3 特徵擷取 21
3.3.1 二維動差不變量萃取 22
3.3.2 三維動差特徵萃取 25
3.4 相似性計算 28
3.5 局部比對 29
第四章 實驗結果 35
4.1 系統環境和使用者介面介紹 35
4.2 三維模型資料庫 37
4.3 實驗結果與討論 38
4.3.1 效能評估 38
4.3.2 局部比對及投影點搜尋 45
第五章 結論與未來研究 49
參考文獻 50

[1]Google 3Dwarehouse , http://sketchup.google.com/3dwarehouse/.
[2]S. Brin and L. Page, "The anatomy of a large-scale hypertextual Web search engine," Compute Network and ISDN Systems, Vol. 30, No. 7, pp. 107-117, 1998.
[3]B. Bustos, D. Keim, D. Saupe, and T. Schreck, "Content-Based 3D Object Retrieval," ComputerGraphics & Applications, Vol. 27, No. 4, pp. 22–27, 2007.
[4]T. Funkhouser, M. Kazhdan, P. Min, and P. Shilane, "Shape-Based Retrieval and Analysis of 3D Models," Communication of the ACM, pp. 58-64, 2005.
[5]D. V. Vranic and D. Saupe, "3D Model Retrieval," Proceedings of Spring Conference on Computer Graphics and its Applications, pp. 89-93, 2000.
[6]D. V. Vranic, D. Saupe, and J. Richter, "Tools for 3D-object retrieval : Karhunen-Loeve transform and spherical harmonics," IEEE Workshop Multimedia Signal Processing, pp. 293-298, 2001.
[7]M. Novotni and R. Klein, "A Geometric Approach to 3D Object Comparison," International Conference on Shape Modeling and Applications, pp. 167-175, 2001.
[8]J. W. Tangelder and R. C. Veltkamp, "A Survey of Content Based 3D Shape Retrieval Methods," Shape Modeling International, pp. 145-156, 2004.
[9]H. Sundar, D. Silver, N. Gagvani, and S. Dickenson, "Skeleton based shape matching and retrieval," Shape Modeling International, pp. 130-139, 2003.
[10]H. Masaki, S. Yoshihisa, and K. Taku, "Topology matching for fully automatic similarity estimation of 3D shapes," Proceedings of ACM SIGGRAPH , pp. 203-212, 2001
[11]D. Y. Chen and M. Ouhyoung, "A 3D object retrieval system based on multi-resolution reeb graph," Computer Graphics Workshop, pp. 16-20, 2002.
[12]O. Robert, T. Funkhouser, C. Bernard, and D. Dobkin, "Shape distributions," ACM Transaction on Graphics, Vol. 21, No. 4, pp. 807-832, 2002.
[13]O. Robert, F. Thomas, C. Bernard, and D. Dobkin, "Matching 3D Models with Shape Distributions," Shape Modeling and Applications, pp. 154-166, 2001.
[14]M. Kazhdan, T. Funkhouser, and S. Rusinkiewicz, "Rotation invariant spherical harmonic representation of 3D shape descriptors," Symposium on Geometry Processing, 2003.
[15]T. Funkhouser, P. Min, M. Kazhdan, J. Chen, A. Halderman, D. Dobkin, and D. Jacobs, "A Search Engine for 3D Models," ACM Transactions on Graphics, Vol. 22, No. 1, pp. 83-105, 2003.
[16]C. T. Zahn and R. Z. Roskies, "Fourier descriptors for plane closed curves," IEEE Transactions on Computers, pp. 269-281, 1972.
[17]S. Motofumi, K. Toshikazu, and O. Nobuyuki, "A similarity retrieval of 3D polygonal models using rotation invariant shape descriptors," IEEE International Conference on Systems, pp. 2946-2952, 2000.
[18]R. Ohbuchi, M. Nakazawa, and T. Takei, "Retrieval 3D Shape based on their appearance," ACM SIGMM International Workshop on Multimedia Information Retrieval, pp. 39-45, 2003.
[19]M. Patrick, J. Chen, and F. Thomas, "A 2D sketch interface for a 3D model search engine," ACM SIGGRAPH 2002 Technical Sketch, pp. 138, 2002.
[20] J. Pu, Y. Liu, G. Xin, H. Zha, W. Liu, and U.Yusuke, "3D Model Retrieval Based on 2D Slice Similarity Measurements," Proceedings of the 2nd International Symposium on 3D Data Processing, 2004.
[21]D. Y. Chen and M. Ouhyoung, "A 3D Model Alignment and Retrieval System," International Computer Symposium, pp. 1436-1443, 2002.
[22]D. Y. Chen and M. Ouhyoung, "On Visual similarity based 3D model retrieval," Computer Graphics Forum, Vol. 22, No. 3, pp. 223-232, 2003.
[23]R. Ohbuchi, T. Otagiri, M. Ibato, and T. Takei, "Shape-Similarity Search of Three-Dimensional Models Using Parameterized Statistics," Proceedings of the Pacific Graphics, pp.265-274, 2002
[24]Y. Rui, T. S. Huang, and S. F. Chang, "Image Retrieval: Current Techniques, Promising Directions and Open Issues," Journal of Visual Communication and Image Representation, Vol.10, No. 1, pp. 39-62, 1999.
[25]M. K. Hu, "Visual pattern recognition by moment invariants," IEEE Transactions Information Theory, Vol.8, No.2, pp.179-187, 1962.
[26]P. Raveendran, S. Omatu, and O. S. Huat, "Moment Invariant Features used as Inputs to a Neural Network to Recognize Numerals," IEEE TENCON International Conference on EC3-Energy, Vol. 1, pp. 141-143, 1991.
[27]A. McAulay, A. Coker, and K. Sauhan, "Effect of Noise in Moment Invariant Neural Network Aircraft Classification," IEEE Transactions on Pattern Analysis and Machine intelligence, pp. 743-749, 1991.
[28]F. A. Sadjadi and E. L. Hall, "Three-Dimensional Moment Invariants", IEEE Transactions on Pattern Analysis and Machine Intelligence, 127-136, 1980.
[29]J. R. Jain and A. K. Jain, "Displacement measurement and its application in interframe image coding," IEEE Transactions Communication, vol. COM-299, no.12, pp. 1799-1808, 1981.
[30]Princeton University, Princeton Shape Retrieval and Analysis Group, 3D Models search Engine, http://shape.cs.princeton.edu/search.html.
[31]P. Shilane, P. Min, M. Kazhdan , and T. Funkhouser, "The Princeton shape benchmark," Proceedings of the Shape Modeling Applications, pp. 167-178, 2004.
[32]Y. Deng and B. S. Manjunath, "An effcient low-dimensional color indexing scheme for region-based image retrieval," IEEE International Conference on Speech and Signal Processing, Vol. 6, pp. 3017-3020, 1999.
[33]J. T. Wang and J. L. Shih, "Shape-Based 3D Model Retrieval System based on Elevation Descriptor ", Proceeding of The CVGIP, 2004.