臺灣博碩士論文加值系統

隨著近年來網際網路及3D技術的迅速發展，使得3D模型在網路上的數量不斷增加，並且被廣泛的使用。因此需要建立一個有效的搜尋系統來幫助使用者能夠搜尋出所需要的3D模型。然而，在眾多的3D模型資料庫中，首先要建立一個有效率的分類及搜尋方法，並且捨棄傳統以文字為檢索依據的方法。目前以3D模型本身的內容（content）為檢索依據的搜尋方式是3D模型資料庫管理上的最佳利器。因此如何建立一個有效的3D模型搜尋系統，讓使用者可以利用此系統快速地找到在大型3D模型資料庫中符合使用者個人期待的相似3D模型，是本篇論文首要目標。
在本論文中提出了以三維頻譜特徵 (3D spectral feature) 和三維倒頻譜特徵 (3D cepstral feature)為基礎之三維模型檢索系統。首先，利用網格主軸分析演算法 (Grid-based Principal Components Analysis, GPCA)，將模型擺正。接著為避免三維模型中空的內部影響特徵擷取，並對三維模型內部做填補的動作，利用反向距離轉換 (The inverse of the distance transform) 來進行模型的填補，然後將填補後之三維模型做三維傅立葉轉換 (3D discrete Fourier transform)後得到三維頻譜 (3D spectral)，其中再針對三維頻譜使用五種不同的切割方法，包括均勻切割 (uniform subband decomposition)、對數切割 (logarithmic subband decomposition )、球型切割 (spherical subband decomposition )、八區塊切割 (octave subband decomposition ) 及互補式八區塊切割 (complement octave subband decomposition)，之後計算每個頻譜區塊內的能量總和值，再做反向三維傅立葉轉換進而得到三維倒頻譜特徵。為了使得搜尋系統更加的完整，將這些不同頻譜切割的特徵進行結合。而在搜尋的部份，可利用特徵向量在資料庫中找出與使用者想搜尋的3D模型相似度較高的模型回應給使用者。
預計將採用五種資料庫來驗證系統的效能，分別為普林斯頓 (Princeton Shape Benchmark ) 、Purdue Engineering Shape Benchmark (ESB)、SHREC Watertight (SHREC-W)、National Institute of Standards and Technology (NIST) 和2011 Shape Retrieval Contest of Non-rigid 3D Watertight Meshes (SHREC’11)。

With the recent advancement in computer graphic, 3D models have become widely used in computer aided design, computer animations, electronic commerce, digital library, and so on. The searching for specific 3D models becomes an important issue. Techniques for effective and efficient content-based 3D model retrieval have therefore become an essential research topic. In this thesis, five subband decomposition methods, include uniform subband decomposition, logarithmic subband decomposition, spherical subband decomposition, octave subband decomposition and complement octave subband decomposition will be employed to divide the 3D spectrum and 3D cepstrum into a number of different features. Thus, 3D spectral features and 3D cepstrum features will be used for 3D model retrieval. In order to get a better retrieval result, the global features and the local features will be combined. In the search section, respond to the user from the best match between query model and match model in the database. Experimental results show the proposed methods produce good performances.

摘 要 i
ABSTRACT ii
致 謝 iii
Contents iv
List of Tables vi
List of Figures viii
Chapter 1 1
Chapter 2 2
Chapter 3 11
3.1 Pre-Processing 11
3.1.1 3D Model Normalization 11
3.1.2 Function of the Distance Transform 12
3.2 The Spectral Feature Extraction 14
3.2.1 The 3D Spectral Feature Extraction 16
3.2.2 The 3D Uniform Subband Feature Extraction 17
3.2.3 The 3D Logarithmic Subband Feature Extraction 18
3.2.4 The 3D Spherical Subband Feature Extraction 19
3.2.5 The 3D Polar Uniform Subband Feature Extraction 20
3.2.6 The 3D Polar logarithmic Subband Feature Extraction 21
3.2.7 The Polar 3D Spectral Feature Extraction 22
3.2.8 The Polar 3D Uniform Subband Feature Extraction 23
3.2.9 The Polar 3D Logarithmic Subband Feature Extraction 23
3.2.10 The Local 3D Feature Extraction 24
3.2.11 The Complement Local 3D Spectral Feature Extraction 25
3.3 The Cepstral Feature Extraction 26
3.3.1 The 3D Cepstral Feature Extraction 27
3.3.2 The 3D Uniform Subband Cepstral Feature Extraction 28
3.3.3 The 3D Logarithmic Subband Cepstral Feature Extraction 28
3.3.4 The 3D Spherical Subband Cepstral Feature Extraction 29
3.3.5 The 3D Polar Uniform Subband Cepstral Feature Extraction 29
3.3.6 The 3D Polar Logarithmic Subband Cepstral Feature Extraction 30
3.3.7 The Polar 3D Cepstral Feature Extraction 30
3.3.8 The Polar 3D Uniform Subband Cepstral Feature Extraction 31
3.3.9 The Polar 3D Logarithmic Subband Cepstral Feature Extraction 31
3.3.10 The Local 3D Cepstral Feature Extraction 32
3.3.11 The Complement Local 3D Cepstral Feature Extraction 33
3.4 The Feature Combination 34
Chapter 4 36
4.1 Experiments on the First Database, the PSB Database 37
4.2 Experiments on the Second Database, the ESB Database 42
4.3 Experiments on the Third Database, the SHREC-W Database 44
4.4 Experiments on the Fourth Database, the NIST Database 46
4.5 Experiments on the Fifth Database, the SHREC”11 Database 48
Chapter 5 51
Reference 52
Appendix A 59
Appendix B 65
Appendix C 71
Appendix D 77
Appendix E 83

[1] T. Funkhouser, P. Min, M. Kazhdan, J. Chen, A. Halderman, D. Dobkin, and D. Jacobs, “A Search Engine for 3D Models,” ACM Trans. on Graphics, Vol. 22, pp. 83-105, 2003.
[2] N. Iyer, S. Jayanti, K. Lou, Y. Kalyanaraman, and K. Ramani, “Three-Dimensional Shape Searching: state-of-the-art review and future trends,” Computer-Aided Design, Vol. 37, No. 5, pp. 509-530, 2005.
[3] P. Shilane, P. Min, M. Kazhdan and T. Funkhouser, “The Princeton Shape Benchmark,” in Proc. of the Shape Modeling Applicat, pp. 167-178, 2004.
[4] S. Jayanti, K. Kalyanaraman, N. Iyer, and K. Ramani, “Developing an Engineering Shape Benchmark for CAD Models,” Computer-Aided Design, Vol. 38, No. 9, pp. 939-953, Sept. 2006.
[5] R. C. Veltkamp and F. B. ter Haar, eds., “SHREC 2007: 3D Shape Retrieval Contest,” Technical Report UUCS-2007-015, pp. 5-10, June 2007.
[6] R. Fang, A. Godill, X. Li, and A. Wagan, “A New Shape Benchmark for 3D Object Retrieval,” in Proc. of Int. symposium on advances in visual computing, pp. 381-392, 2008.
[7] 2011 Shape Retrieval Contest of Non-rigid 3D Watertight Meshes (SHREC’11) database：http://www.itl.nist. gov/iad/vug/sharp/contest/2011/NonRigid.
[8] Z. Lian, A. Godil, B. Bustos, M. Daoudi, J. Hermans, and S. Kawamura, eds., “A comparison of methods for non-rigid 3D shape retrival,” Pattern Recognition, Vol. 46, pp. 449-461, 2013.
[9] Y. C. Pu, W. C. Du, C. H. Huang and C. K. Lai, “Invariant Feature Extraction for 3D Model Retrieval: An Adaptive Approach Using Euclidean and Topological Metrics,” Computers and Mathematics with Applications, Vol. 64, pp. 1217-1225, 2012.
[10] S. Kawamura, K. Usui, T. Furuya and R. Ohbuchi, “Local Geometrical Feature with Soatial Context for Shape-Base 3D Model Retrieval,” in Proc. of the 5th Eurographics conference on 3D Object Retrieval, pp. 55-58, 2012.
[11] Y. Ohishi, T. Furuya and R. Ohbuchi, “Non-rigid 3D Model Retrieval Using Set of Local Statistical Feature,” in Proc. of 2012 IEEE Int. Conf. on Multimedia and Expo Workshops (ICMEW) , Sep 26, 2012.
[12] X. Pan, Q. You, Z. Liu and Q. H. Chen, “3D shape retrieval by Poisson histogram,” Pattern Recognition Letters, Vol. 32, Issue 6, pp. 787-794, 2011.
[13] Y. S. Park, Y. I. Yun and J. S. Choi, “A New Shape Descriptor Using Sliced Image Histogram for 3D Model Retrieval,” IEEE Transactions on Consumer Electronics, Vol. 55, Issue 1, pp.240-247, 2009.
[14] M. Reisert and H. Burkhardt, “Second Order 3D Shape Features: An Exhaustive Study,” Computers &; Graphics, Vol. 30, No 2, pp. 197-206, 2006
[15] J. L. Shih, C.H. Lee and J. T. Wang, “3D Object Retrieval System Based on Grid D2,” Electronics Letters, Vol. 41, No. 4, pp. 23-24, 2005.
[16] C. Y. Ip, L. Sieger, W. C. Regli and A. Shokoufandeh, “Automated Learning of Model Classifications,” in Proc. of Solid Modeling, pp. 322-327, 2003.
[17] C. Y. Ip, D. Lapadat, L. Sieger and W. C. Regli, “Using Shape Distributions to Compare Solid Models,” in Proc. of Solid Modeling, pp. 273-280, 2002.
[18] E. Wahl, G. Hillenbrand and G. Hirzinger, “Surflet-Pair-Relation Histograms-A Statistical 3D-Shape Representation for Rapid Classification,” in Proc. of 3D Digital Imaging and Modeling, pp. 474-481, 2003.
[19] R. Osada, T. Funkhouser, B. Chazelle and D. Dobkin, “Shape Distributions,” ACM Transactions on Graphics (TOG), Vol. 21, No. 4 , pp. 807-832, 2002.
[20] B. S. Manjunath, P. Salembier and T. Sikora, “Introduction to MPEG-7 Multimedia Content Description Interface,” John Wiley &; Sons Ltd, pp. 247-260, 2002.
[21] MPEG Video Group, ”MPEG-7 Visual part of eXperimetation Model Version 9.0,” Doc. ISO/IEC JTC1/SC29/WG11/N3914, January 2001.
[22] T. Zaharia and F. J. Preteux, “Shape-Based Retrieval of 3D Mesh Models,” in Proc. of IEEE Int. Conf. on Multimedia and Expo, Vol. 1, pp. 437-440, 2002.
[23] C. Zhang and T. Chen, “Efficient Feature Extraction for 2D/3D Objects in Mesh Representation,” in Proc. of IEEE Int. Conf. on Image Processing (ICIP), Thessaloniki, Greece, pp. 935-938 ,2001.
[24] 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
[25] M. Ankerst, G. Kastenmuller, H. P. Kriegel and T. Seidl, “3D Shape Histograms for Similarity Search and Classification in Spatial Databases,” Symposium on Large Spatial Databases, pp. 207–226, 1999.
[26] H. Dutagac, B. Sankur and Y. Yemez, “Subspace Methods for Retrieval of General 3D Models,” Computer Vision and Image Understanding, Vol. 114, No. 8, pp. 865-886, 2010.
[27] C. B. Akgul, B. Sankur, Y. Yemez and F. Schmitt, “3D Model Retrieval Using Probability Density-Based Shape Descriptors,” IEEE Transactions on Pattern Analysis And Machine Intelligence, Vol. 31, No. 6, pp. 1117-1133, June 2009.
[28] P. Papadakis, I. Pratikakis, S. Perantonis and T. Theoharis, “Efficient 3D Shape Matching and Retrieval Using a Concrete Radialized Spherical Projection Representation,” Pattern Recognition, Vol. 40, pp. 2437-2452, 2007.
[29] H. Laga, H. Takahashi and M. Nakajima, “Spherical Wavelet Descriptors for Content-Based 3D Model Retrieval,” in Proc. of IEEE Int. Conf. on Shape Modeling and Applicat, 2006.
[30] L. Ying, L. Demanet and E. Candes, “3D Discrete Curvelet Transform,” Wavelets XI, Vol. 5914, No. 1, pp. 351-361, Sep 2005.
[31] M. Kazhdan, T. Funkhouser and S. Rusinkiewicz, “Rotation Invariant Spherical Harmonic Representation of 3D Shape Descriptors,” Symposium on Geometry Processing, 2003.
[32] D. V. Vranic, D. Saupe and J. Richter, “Tools for 3D-object Retrieval : Karhunen-Loeve Transform and Spherical Harmonics,” in Proc. of IEEE Workshop on Multimedia Signal Processing, pp. 293-298, 2001.
[33] D. V. Vranic and D. Saupe, “3D Shape Descriptor Based on 3D Fourier Transform,” in Proc. of EURASIP Conf. on Digital Signal Processing for Multimedia Communications and Services (ECMCS 2001) (editor K. Fazekas), Budapest, Hungary, pp. 271-274, Sep 2001.
[34] Y. Gao, J. Tang, R. Hong, S. Yan, Q. Dai, N. Zhang and T. S. Chua, “Camera Constraint-free View-based 3-D Object Retrieval,” IEEE Transactions on Image Processing, Vol. 21, No. 4, pp. 2269-2281, 2012.
[35] Y. Gao, M. Wang, D. Tao, R. Ji and Q. Dai, ”3D Object Retrieval and Recognition with Hypergraph Analysis,” IEEE Transactions on Image Processing, Vol. 21 , No. 9, Pages 4290-4303, Sept. 2012.
[36] Q. Xiao, H. Wang, F. Li and Y. Gao, “3D Object Retrieval Based on a Graph Model Descriptor,” Neurocomputing, Vol. 74, No. 17, Pages 3486-3493, 2011.
[37] Y. Gao, Q.H Dai, M. Wang and N. Zhang, “3D Model Retrieval Using Weighted Bipartite Graph Matching,” Signal Processing: Image Communication, Vol. 26, No. 1, pp. 39-47, 2011.
[38] J. L. Shih, C. H. Lee and C. H. Chuang, “A 3D Model Retrieval Approach Based on the Combination of PCA Plane Projections,” Journal of Information Technology and Applications, Vol. 5, No. 2, pp. 46-102, 2011.
[39] Q. Zhang, J. Jia and H. Li, “A GPU Based 3D Object Retrieval Approach Using Spatial Shape Information,” ISM’10, 2010 IEEE International Symposium on Multimedia, pp.212-219, 2010.
[40] Z. Lian, A. Godil and X. Sun, “Visual Similarity Based 3D Shape Retrieval Using Bag-of-Features,” 2010 Shape Modeling International Conference, 2010.
[41] Y. Gao, Q. H. Dai and N. Y. Zhang, “3D Model Comparison Using Spatial Structure Circular Descriptor,” Pattern Recognition, Vol. 43, pp. 1142-1151, 2010.
[42] P. Papadakis, I. Pratikakis, T. Theoharis and S. Perantonis, “PANORAMA: A 3D Shape Descriptor Based on Panoramic Views for Unsupervised 3D Object Retrieval,” Int. Journal of Computer Vision, Vol. 89, pp. 177-192, 2010.
[43] A. Mademlis, P. Daras, D. Tzovaras and M.G. Strintzis, “3D Object Retrieval Using the 3D Shape Impact Descriptor,” Pattern Recognition, Vol. 42, pp. 2447-2459, 2009.
[44] J. L. Shih and H. Y. Chen, “A 3D Model Retrieval Approach Using the Interior and Exterior 3D Shape Information,” Multimedia Tools and Applications, Vol. 43, pp. 45-62, 2008.
[45] A. Tatsuma and M. Aono, “Multi-Fourier Spectra Descriptor and Augmentation with Spectral Clustering for 3D Shape Retrieval,” The Visual Computer: International Journal of Computer Graphics, Vol. 25, No. 8, pp. 785-804, June 2009.
[46] C. T. Kuo and S. C. Cheng, “3D Model Retrieval Using Principal Plane Analysis and Dynamic Programming,” Pattern Recognition, Vol. 40, No. 2, pp. 742-755, 2007.
[47] J. L. Shih and W. C. Wang, “A 3D Model Retrieval Approach Based on The Principal Plane Descriptor,” in Proc. of Innovative Computing, Information and Control, 2007.
[48] D. Zarpalas, P. Daras, A. Axenopoulos, D. Tzovaras and M. G. Strintzis, “3D Model Search and Retrieval Using the Spherical Trace Transform,” EURASIP Journal on Applied Signal Processing, Vol. 2007, pp. 207-207, 2007.
[49] M. Chaouch and A. Verroust-Blondet, “A New Descriptor for 2D Depth Image Indexing and 3D Model Retrieval,” in Proc. of IEEE Int. Conf. on Image Processing (ICIP 2007), Vol. 6, pp. 373-376, 2007.
[50] J. L. Shih, C. H. Lee and J. T. Wang, “A New 3D Model Retrieval Approach Based on the Elevation Descriptor,” Pattern Recognition, Vol. 40, No. 1, pp. 283-295, 2007.
[51] J. Assfalg, A. D. Bimbo and P. Pala, “Content-based Retrieval of 3D Models Through Curvature Maps: A CBR Approach Exploiting Media Conversion,” in Proc. of Multimedia Tools and Applicat, Vol. 31, No. 1, pp. 29-50, 2006.
[52] J. L. Shih and H. Y. Chen, “3D Model Retrieval Based on Grid Sphere and Dodecahedral Silhouette Descriptors,” in Proc. of Joint Conf. on Information Science, 2006.
[53] J. Ricard, D. Coeurjolly and A. Baskurt, “ART Extension for Description, Indexing and Retrieval of 3D Objects,” Pattern Recognition, Vol. 3, pp.79-82, 2004.
[54] D. V. Vranic, “3D Model Retrieval,” Ph. D. Thesis, University of Leipzig, 2004.
[55] D. Y. Chen, X. P. Tian, Y. T. Shen and M. Ouhyoung, “On Visual Similarity Based 3D Model Retrieval,” Computer Graphics Forum, Vol. 22, No. 3, pp. 223-232, 2003.
[56] J. Assfalg, A. D. Bimbo and P. Pala, “Curvature Maps for 3D CBR,” in Pro. of Multimedia and Expo, Vol. 02, pp. 301-304, 2003.
[57] J. Assfalg, A. D. Bimbo and P. Pala, “Retrieval of 3D Objects Using Curvature Maps and Weighted Walkthroughs,” Proc. of Image Analysis and Processing, pp. 348-353, 2003.
[58] B. J. Super and H. Lu, “Evaluation of a Hypothesizer For Silhouette-based 3-D Object Recognition,” Pattern Recognition, Vol. 36, pp. 69-78, 2003.
[59] Y. Liu, X. D. Zhang, Z. M. Li and H. Li, “Extended Cone-curvature Based Salient Points Detection and 3D Model Retrieval,” Multimedia Tools and Applications, Vol. 64, pp. 671-693, 2013.
[60] M. C. Chang and B. B. Kimia, “Measuring 3D Shape Similarity by Graph-based Matching of the Medial Scaffolds,” Special issue on 3D Imaging and Modelling, Vol. 115, No. 5, pp. 707-720, 2011.
[61] T. Tung and F. Schmitt, “The Augmented Multiresolution Reeb Graph Approach for Content-Based Retrieval of 3D Shapes,” International Journal of Shape Modeling, Vol. 11, No. 1, 2005
[62] H. Sundar, D. Silver, N. Gagvani and S. Dickinson, “Skeleton Based Shape Matching and Retrieval,” in Proc. of Shape Modeling International, pp. 130-139, 2003.
[63] B. K. P. Horn, “Extended Gaussian Images,” in Proc. of IEEE, Vol. 72, No. 12, pp. 1671-1686, Dec. 1984.
[64] E. Paquet and M. Rioux, “Nefertiti: A Query by Content Software for Three-Dimensional Models Databases Management,” in Proc. of Int. Conf. Recent Advances in 3D Digital Imaging and Modeling, pp. 345-352, 1997.
[65] D. V. Vranic, “An Improvement of Rotation Invariant 3D Shape Descriptor Based on Functions on Concentric Spheres,” in Proc. of IEEE Int. Conf. Image Process, pp. 757-760, 2003.
[66] T. F. Ansary, M. Daoudi and J.P. Vandeborre, “A Bayesian 3-D Search Engine Using Adaptive Views Clustering,” in Proc. of IEEE Transactions on Multimedia, Jan. 2007.
[67] R. M. Rustamov, “Template Based Shape Descriptor,” in Proc. of Eurographics Workshop on 3D Object Retrieval, 2009.
[68] M. Jovic, Y. Hatakeyama, F. Dong and K. Hirota, “Image Retrieval Based on Similarity Score Fusion From Feature Similarity Ranking Lists,” in Proc. of 3rd Int. Conf. Fuzzy Systems and Knowledge Discovery, pp. 461-470, 2006.
[69] F. S. Roberts, “Discrete Mathematical Models with Applications to Social, Biological, and Environmental Problems,” Prentice Hall, 1976.
[70] N. Haque, “Image Ranking for Multimedia Retrieval,” Ph.D. thesis, School of Computer Science and Information Technology, Royal Melbourne Institute of Technology, 2003.
[71] C. H. Lee, J. L Shih, C. H. Chou, K. M. Yu and C. Y. Hung, “3D Model Retrieval Using 2D Cepstral Features,” in Proc. of. IEEE Int. Conf. Acoustics, Speech and Signal Processing (ICASSP), pp. 2365 – 2368, 2012.