臺灣博碩士論文加值系統

隨著網際網路的迅速發展，使得3D模型在網路上供使用者存取的數量不斷的增加，因此需要一個有效的搜尋系統來幫助人們找到他們所要的3D資料。對於3D模型資料庫的管理，首先要建立一個有效率的分類及搜尋方法，而捨棄傳統以文字為檢索依據的方法。目前以3D模型本身的內容（content）為檢索依據的搜尋方式是3D模型資料庫管理上的最佳利器。因此如何建立一個有效的3D模型搜尋系統，讓使用者可以利用此一系統快速地找到在大型3D模型資料庫中符合使用者個人期待的相似3D模型，是本篇論文首要目標。
在本論文中提出了不同性質的投影特徵與其個別的衍生投影(derivative descriptor)特徵，以及3D模型資料庫的搜尋系統。因此本系統包含兩個部分，分別為特徵擷取和3D模型檢索。在特徵擷取的部分，提出了四種不同的投影特徵，其中包括了深度投影(elevation descriptor)、曲率投影(curvature descriptor)、徑度投影(radial descriptor)以及角度投影 (angle descriptor)，並取其個別特徵的投影圖來擷取衍生投影特徵，將這八種不同性質的投影特徵結合，來使得搜尋系統更加的完整。而在搜尋的部份，可利用特徵向量在資料庫中找出與使用者想搜尋的3D模型相似度較高的模型回應給使用者。

The advances in 3D data acquisition, graphics hardware, and 3D data modeling and visualizing techniques have led to the proliferation of 3D models. 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, eight projected shape features include elevation descriptor, curvature descriptor, radial descriptor, angle descriptor and their derivative descriptors will be used for 3D model retrieval. In order to get a better retrieval result, Dynamic Multi-Descriptor Fusion (DMDF) is used to combine these projected shape features. 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
Introduction..................................................................1
Chapter 2.....................................................................3
Related Work..................................................................3
2.1 View Based Methods........................................................3
2.1.1 Description with 2D Silhouette Contours.................................3
2.1.2 Lightfield Descriptor...................................................3
2.1.3 Principal Plane Analysis Descriptor.....................................4
2.1.4 Optimal Selection of 2D Views...........................................5
2.1.5 Grid Sphere and Dodecahedron............................................6
2.1.6 Depth Information Descriptor with DFT...................................6
2.1.7 Elevation Descriptor....................................................7
2.1.8 Curvature Maps Descriptor...............................................8
2.1.9 Principal Plane Descriptor..............................................8
2.1.10 The Spherical Trace Transform..........................................9
2.1.11 2D Depth Image Descriptor.............................................10
2.1.12 Shape Impact Descriptor...............................................11
2.1.13 Panoramic Views.......................................................12
2.1.14 Spatial Structure Circular Descriptor.................................12
2.1.15 Combination of PCA Plane Projections..................................13
2.2 Spatial Shape Feature Based Methods......................................14
2.2.1 Geometric Descriptor...................................................14
2.2.2 Cord-Based Descriptor..................................................15
2.2.3 Surface Penetration Map Descriptor.....................................15
2.2.4 Shape Histogram........................................................15
2.1.5 Shape Distribution.....................................................15
2.1.6 Extended D2 Descriptor.................................................16
2.1.7 Parameterized Statistics...............................................16
2.2.8 Grid D2 Descriptor.....................................................17
2.2.9 Surflet-Pair-Relation Histograms.......................................17
2.2.10 Shape Spectrum Descriptor.............................................18
2.2.11 Combined Angle and Distance Descriptor................................19
2.2.12 Distance Descriptor...................................................20
2.2.13 Sliced Histogram......................................................20
2.2.14 Probability Density-Based Shape Descriptor............................21
2.3 Frequency Based Methods..................................................22
2.3.1 Ray-Based Sampling with Spherical Harmonics Representation.............23
2.3.2 3D Zernike Moments.....................................................24
2.3.3 Rotation Descriptor....................................................24
2.3.4 The Concrete Radialized Spherical Projection Representation............25
Chapter 3....................................................................26
The Proposed Method for 3D Model Retrieval...................................26
3.1 Pre-Processing...........................................................26
3.1.1 3D model Normalization.................................................26
3.1.2 Alignment of 3D model..................................................27
3.2 The Projected Feature....................................................28
3.2.1 The Elevation Projection...............................................28
3.2.2 The Curvature Projection...............................................29
3.2.3 The Radial Distance Projection.........................................31
3.2.4 The Angle Projection...................................................32
3.2.5 The Derivative Projection..............................................34
3.2.6 Angular Radial Transformation..........................................36
3.3 The Feature Combination..................................................37
3.3.1 Feature Normalization..................................................37
3.3.2 Similarity Measurement.................................................38
3.3.3 Feature Combination Using Dynamic Multi-Descriptor Fusion(DMDF)........41
Chapter 4....................................................................42
Experimental result..........................................................42
4.1 Experiments on the First Database, the PSB Database......................43
4.2 Experiments on the Second Database, the ESB Database.....................49
4.3 Experiments on the Third Database, the SHREC-W Database..................53
4.4 Experiments on the Fourth Database, the NIST Database....................56
Chapter 5....................................................................59
Conclusion...................................................................59
Reference....................................................................60

[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, no. 1, 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]B.J. Super, H. Lu, “Evaluation of a hypothesizer for silhouette-based 3-D object recognition”, Pattern Recognition, Vol. 36, pp. 69-78, 2003.
[4]D.Y. Chen, X.P. Tian, Y.T. Shen, M. “Ouhyoung, On visual similarity based 3D model retrieval”, Computer Graphics Forum, Vol. 22, No. 3, pp. 223-232, 2003.
[5]D. Y. Chen and M. Ouhyoung, “A 3D Model Alignment and Retrieval System,” in Proc. of Int. Computer Symposium, Workshop on Multimedia Technologies, Vol. 2, pp. 1436-1443, Hualien, Taiwan, Dec. 2002.
[6]C.T. Kuo and S.C. Cheng, “3D model retrieval using principal plane analysis and dynamic programming”, Patten Recognition, Vol. 40, No. 2, pp. 742-755, 2007.
[7]T.F. Ansary, M. Daoudi, and J.P. Vandeborre, “A Bayesian 3-D Search Engine Using Adaptive Views Clustering”, in Proc. IEEE Transactions on Multimedia, Jan. 2007.
[8]T.F. Ansary, J.P. Vandeborre, and M. Daoudi, “A Bayesian approach for 3D models retrieval based on characteristic views”, in Proc. IEEE Int. Conf. Pattern Recognition, Cambridge, U.K., Aug. 2004.
[9]T.F. Ansary, J.P. Vandeborre, S. Mahmoudi and M. Daoudi, “A Bayesian framework for 3D models retrieval based on characteristic views”, in Proc. IEEE Int. Symp. 3D Data Processing, Visualization and Transmission, Thessaloniki, Greece, Sep. 2004.
[10]J.L. Shih, and H.Y. Chen, “3D model retrieval based on Grid Sphere and Dodecahedral Silhouette Descriptors”, Proceeding of Joint Conf. on Information Science, 2006.
[11]D.V. Vranic, “3D Model Retrieval”, Ph. D. Thesis, University of Leipzig, 2004.
[12]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.
[13]J.L. Shih, and H.Y. Chen, “A new 3D model retrieval approach based on the Shell Grid and Modified Elevation Descriptor”, Submission to Pattern Recognition.
[14]J. Assfalg, A.D. Bimbo, and P. Pala, “Content-based retrieval of 3D models through curvature maps: a CBR approach exploiting media conversion”, Proc. of Multimedia Tools and Applicat., Vol. 31, No. 1, pp. 29-50, 2006.
[15]J. Assfalg, A.D. Bimbo, and P. Pala, “Curvature maps for 3D CBR”, Proc. of Multimedia and Expo, Vol. 02, pp. 301-304, 2003.
[16]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.
[17]J.L. Shih and W.C. Wang, “”A 3D Model Retrieval Approach based on The Principal Plane Descriptor”, Proc. of Innovative Computing, Information and Control, 2007.
[18]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.
[19]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.
[20]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.
[21]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, Special Issue on: 3D Object Retrieval, 89, 2, pp. 177-192, 2010
[22]Y. Gao, Q.H. Dai, N.Y. Zhang, “3D Model Comparison Using Spatial Structure Circular Descriptor”, Pattern Recognition, Vol. 43, pp. 1142-1151, 2010.
[23]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, 2011.
[24]C. Zhang, 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.
[25]E. Paquet, A. Murching, T. Naveen, A. Tabatabai, M. Rioux, “Description of shape information for 2-D and 3-D objects”, Signal Processing: Image Communication 16, pp. 103-122, 2000.
[26]M. Yu, I. Atmosukarto, W.K. Leow, Z. Huang, R. Xu, “3D model retrieval with morphing-based geometric and topological feature maps”, Proc. of Computer Vision and Pattern Recognition, pp. 656-661, 2003.
[27]M. Ankerst, G. Kastenmuller, H.P. Kriegel, T. Seidl, “3D shape histograms for similarity search and classification in spatial databases”, Symposium on Large Spatial Databases, pp. 207–226, 1999.
[28]R. Osada, T. Funkhouser, B. Chazelle, D. Dobkin, “Shape distributions”, ACM Trans. on Graphics Vol. 21, No. 4, pp. 807-832, 2002.
[29]C.Y. Ip, D. Lapadat, L. Sieger, W.C. Regli, “Using shape distributions to compare solid models”, Proc. of Solid Modeling, pp. 273-280, 2002.
[30]C.Y. Ip, L.Sieger, W.C. Regli, A. Shokoufandeh, “Automated learning of model classifications”, Proc. of Solid Modeling, pp. 322-327, 2003.
[31]R. Ohbuchi, T. Minamitani, T. Takei, “Shape-similarity search of 3D models by using enhanced shape functions”, Proc. of Theory and Practice of Computer Graphics, pp. 97-104, 2003.
[32]R. Ohbuchi, T. Minamitani, T. Takei, “Shape-similarity search of 3D models by using enhanced shape functions”, Proc. of Computer Applicat. in Technology, pp. 70-85, Vol. 23, No. 2/3/4, 2005.
[33]R. Ohbuchi, T. Takei, “Shape-similarity comparison of 3D models using alpha shapes”, Proc. of Pacific Conf. on Computer Graphics and Applicat., 2003.
[34]R. Ohbuchi, Y. Hata, “Combining multiresolution shape descriptors for 3D model retrieval”, accepted, Proc. WSCG 2006, Plzen, Czech Republic, Jan. 30 ~Feb. 3, 2006.
[35]J.-L. Shih, C.-H. Lee, J.T. Wang, “3D object retrieval system based on grid D2”, Electronics Letters, Vol. 41, No. 4, pp. 23-24, 2005.
[36]E. Wahl, G. Hillenbrand, and G. Hirzinger, “Surflet-Pair-Relation Histograms-A Statistical 3D-Shape Representation for Rapid Classification”, Proc. of 3D Digital Imaging and Modeling, pp. 474-481, 2003.
[37]MPEG Video Group,” MPEG-7 Visual part of eXperimetation Model Version 9.0”, Doc. ISO/IEC JTC1/SC29/WG11/N3914, Pisa, January 2001.
[38]B. S. Manjunath, P. Salembier, and T. Sikora, “Introduction to MPEG-7 Multimedia Content Description Interface.” John Wiley & Sons Ltd., pp. 247-260, 2002.
[39]M. Reisert, H. Burkhardt, “Second order 3D shape features: An exhaustive study”. Computers & Graphics, Vol. 30, No. 2, pp. 197-206, 2006.
[40]D. V. Vranic and D. Saupe, “3D Model Retrieval”. Proc. of the Spring Conf. on Computer Graphics and its Applicat.s (SCCG2000), pp. 89-93, May 2000.
[41]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, pp. 240-247, 2009.
[42]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.
[43]D.V. Vranic, D. Saupe, J. RICHTER, “Tools for 3D-object retrieval: Karhunen-Loeve transform and spherical harmonics”, in Proc. of IEEE Workshop on Multimedia Signal, pp. 293-298, 2001.
[44]D. Saupe and D. V. Vranic, “3D model retrieval with spherical harmonics and moments”, DAGM 2001, pp. 392-397, 2001.
[45]M. Kazhdan, T. Funkhouser, S. Rusinkiewicz, “Rotation invariant spherical harmonic representation of 3D shape descriptors”, Symposium on Geometry Processing, 2003.
[46]M. Kazhdan, T. Funkhouser, “Harmonic 3D shape matching”, Proc. of SIGGRAPH, pp. 191, 2002.
[47]T. Funkhouser, P. Min, M. Kazhdan, J. Chen, A. Halderman, D. Dobkin, D. Jacobs, “A search engine for 3D models”, ACM Trans. Graphics, Vol. 22, No. 1, pp. 83-105, 2003.
[48]M. Novotni, R. Klein, “Shape retrieval using 3D Zernike descriptors”, Computer-Aided Design, Vol. 36, pp. 1047-1062, 2004.
[49]J.S. Pan, H. Luo, Z.M. Lu, and J.C. Harry Chang, “A new 3D shape descriptor based on rotation”, Proc. of Intelligent System Design and Applicat., Vol. 02, pp. 300-304, 2006.
[50]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.
[51]R. Fang, A. Godill, X. Li, and A. Wagan, “A New Shape Benchmark for 3D Object Retrieval,” Proc. Int. symposium on advances in visual computing, pp. 381-392, 2008.
[52]D. V. Vranic, “3D model retrieval,” Ph.D. Dissertation, University of Leipzig, Department of Computer Science, 2004.
[53]J.L. Shih, C.H. Lee, and C.H. Chuang, “A 3D Model Retrieval System Based On The Derivative Radial Distance”, Proc. of The 22th IPPR Conference On Computer Vision, Graphics and Image Processing (CVGIP) 2009.
[54]Y.W. Hou, “3D Model Retrieval Base on Dynamic Multi-Descriptor Fusion Algorithm”, M.Eng. Thesis, University of Chung-Hua, 2011.
[55]B. K. P. Horn, “Extended Gaussian Images,” Proc. IEEE, vol. 72, no. 12, pp. 1671-1686, Dec. 1984.
[56]H. Laga, H. Takahashi, and M. Nakajima, “Spherical Wavelet Descriptors for Content-Based 3D model Retrieval,” Proc. IEEE Int. Conf. on Shape Modeling and Applicat., 2006.
[57]M. Kazhdan, T. Funkhouser, and S. Rusinkiewicz, “Rotation invariant spherical harmonic representation of 3D shape descriptors,” Proc. Eurographics/ACM SIGGRAPH Symp. Geometry processing, pp. 156-164, 2003.
[58]T. Zaharia and F. J. Preteux, “Shape-Based Retrieval of 3D Mesh Models,” Proc. IEEE Int. Conf. on Multimedia and Expo, vol. 1, pp. 437-440, 2002.
[59]E. Paquet and M. Rioux, “Nefertiti: A Query by Content Software for Three-Dimensional Models Databases Management,” Proc. Int. Conf. Recent Advances in 3D Digital Imaging and Modeling, pp. 345-352, 1997.
[60]D. V. Vranic, “An Improvement of Rotation Invariant 3D Shape Descriptor Based on Functions on Concentric Spheres,” Proc. IEEE Int. Conf. Image Process., pp. 757-760, Sept. 2003.
[61]R. M. Rustamov, ”Template Based Shape Descriptor,” Proc. Eurographics Workshop on 3D Object Retrieval, 2009.
[62]P. Shilane, P. Min, M. Kazhdan, T. Funkhouser, “The Princeton Shape Benchmark”, Proc. of the Shape Modeling Applicat., pp. 167-178, 2004.
[63]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.
[64]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.
[65]R. Fang, A. Godill, X. Li, and A. Wagan, “A New Shape Benchmark for 3D Object Retrieval,” Proc. Int. symposium on advances in visual computing, pp. 381-392, 2008.