臺灣博碩士論文加值系統

近年來隨著處理三維網格（後面稱為3D Mesh）技術的快速演進和廣泛使用，如電影及遊戲的3D動畫呈現或即時動態模擬等，都包含處理3D Mesh的技術，因此如何處理3D Mesh的相關技術將越來越受到人們的重視。而網格分段（Mesh Segmentation）對於3D Mesh的分析及理解是相當重要的一門技術，如逆向工程（Reverse engineering）和實例建模（Modeling by example）就是模型分析的應用。
根據前人的研究，利用模型中最遠的兩個特徵面為起點，再利用簡單的距離權重（Distance weight）便能求得具有意義的階層式網格分段模型。但在計算最遠特徵面時採用了最短路徑演算法，所以時間複雜度較高。因此我們提出了一個可以快速估測最遠特徵面的方法，以降低搜尋最短路徑時的時間複雜度。
另外，在我們的研究中還利用心理學中的突出部位（Part Salience）概念，以劃分模型中具有意義的部位（後面稱為Part），作為階層式網格分段的基礎。其中突出部位的概念包含了三個主要因素:突出度（Protrusion）、邊界強度（Boundary strength）以及視察對象的部位相對大小（Relative size）。我們利用突出度估測突出特徵，並搭配我們的快速估測方式求得最遠特徵面。再以兩個遠特徵面為起點執行區域成長（Region growing），並利用邊界強度的概念分割出模型中具有意義的Part，最後再採用迭代法（Iteration）對各Part細切，以產生階層式的網格分段效果。除此之外，為了避免模型出現過度分段（Over-segmentation）的Part，我們實作了突出部位概念裡的部位相對大小的方法，成功地避免產生過度分段的結果。
經由上述的方法，不僅可以得到一個有意義的分段效果，也可以避免因為執行最短路徑演算法所帶來的冗長計算時間。

As the graphics hardwares and associate technology greatly improved in these year, the related applications such as the computer games, the computer animation, 3D vision, virtual reality, etc., showed an explosive growth. As an important 3D mesh analyzing technique, mesh segmentation is intensively studied. .
We propose a novel hierarchical part-type mesh segmentation technique that utilizes salient features and iterative cut to derive a hierarchical part-type segmented model from a 3D mesh. By means of the concept of part salience borrowed from cognition science, the extent of protrusion, the strength of boundary, and the relative size of the parts are jointly considered by our work. Where in our work, we have proposed a new formula for the estimation of protrusion to help us finding initial features from the input mesh. By applying region growing from the farthest two features and the calculation of boundary strength, a proper cut maximizing the boundary strength is applied to a part from each iteration. .
Furthermore, most former studies applied shortest path algorithm in finding farthest features and only a few recent works have considered part salience. Since the calculation in finding the shortest path among feature points is time consuming, we have proposed a simple metric for the estimation of farthest features to eliminated the need of the shortest path calculations. To prevent from overly segmented, a threshold to the segmented parts considers both the relative size and part salience is given. According to our experimental results, the new approach is successful. .

中文摘要 1
Abstract 2
目 錄 3
圖 目 錄 4
1. 緒論 6
1.1. 研究背景 6
1.2. 文獻探討 7
1.3. 論文貢獻 9
1.4. 論文架構 10
2. 基本定義與相關研究 11
2.1. 基本定義 11
2.2. 相關研究 12
3. 演算法 24
3.1. 突出程度 25
3.1.1. 一階層的突出度 26
3.1.2. N階層的突出度 28
3.1.3. N階層的層級估測 29
3.2. 區域特徵點 30
3.3. 快速相對面演算法（FOFS,Fast Opposite Feature Selection） 31
3.4. 分段區塊的估測 32
3.4.1. 高斯映射 33
3.4.2. 區域成長演算法 35
3.5. 決定最終分段區域 37
3.6. 階層式分段 38
3.7. 邊界修正 39
3.8. 截止條件 41
4. 實驗與結果討論 42
5. 結論與未來展望 47
6. 參考文獻 49

[1] D. D. Hoffman and M. Singh, 1997, “Salience of visual parts”, Cognition, Volume 63, Issue 1, Pages 29–78, April. .
[2] M. Garland, A. Willmott, and P. S. Heckbert, 2001, “Hierarchical Face Clustering on Polygonal Surfaces”, Proceedings of the 2001 symposium on Interactive 3D graphics, Pages 49-58. .
[3] X. Li, T. W. Woon, T. S. Tan, and Z. Huang, 2001, “Decomposing Polygon Meshes for Interactive Applications”, Proceedings of the 2001 symposium on Interactive 3D graphics, Pages 35-42. .
[4] M. Hilaga, Y. Shinagawa, T. Kohmura, and T. L. Kunii, 2001, ” Topology Matching for Fully Automatic Similarity Estimation of 3D Shapes”, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, Pages 203-212. .
[5] B. Levy, S. Petitjean, N. Ray, and J. Maillot, 2002, “Least Squares Conformal Maps for Automatic Texture Atlas Generation”, ACM Transactions on Graphics (TOG) - Proceedings of ACM SIGGRAPH 2002, Volume 21, Issue 3, Pages 362-371, July. .
[6] S. Katz and A. Tal, 2003, “Hierarchical Mesh Decomposition using Fuzzy Clustering and Cuts”, SIGGRAPH '03 ACM SIGGRAPH 2003, Volume 22 Issue 3, Pages 954-961, July. .
[7] H. Carr, J. Snoeyink, and U. Axen, 2003, “Computing Contour Trees in All Dimensions”, Computational Geometry, Volume 24, Issue 2, Pages 75–94, February. .
[8] D. H. Kim, I. D. Yun, and S. U. Lee, 2005, “A new shape decomposition scheme for graph-based representation”, Pattern Recognition, Volume 38, Issue 5, Pages 673-689, May. .
[9] S. Valette, I. Kompatsiaris, and M. G. Strintzis, 2005, “A polygonal mesh partitioning algorithm based on protrusion conquest for perceptual 3D shape description”, Workshop towards Semantic Virtual Environments SVE 2005, Pages 68-76, March. .
[10] Y. Lee, S. Lee, A. Shamir, D. Cohen-Or, and HP. Seidel, 2005 “Mesh scissoring with minima rule and part salience”, Computer Aided Geometric Design, Volume 22, Issue 5, Pages 444-465, July. .
[11] M. Attene, B. Falcidieno, and M. Spagnuolo, 2006,” Hierarchical mesh segmentation based on fitting primitives”, The Visual Computer, Volume 22, Issue 3, Pages 181-193, March. .
[12] A. Agathos, I. Pratikakis, S. Perantonis, N. Sapidis, and P. Azariadis, 2007, ” 3D Mesh Segmentation Methodologies for CAD applications”, Computer-Aided Design and Applications, Volume 4, Issue 6, Pages 827-841. .
[13] HYS. Lin, HY. M. Liao, and JC. Lin, 2007, “Visual Salience-Guided Mesh Decomposition” , 2004 IEEE 6th Workshop on multimedia signal processing , Volume 9, Issue 1, Pages 46-57. .
[14] JY. Lee, JW. Choi, and H. Kim, 2007, ” Determination of Hand Surface Area by Sex and Body Shape using Alginate”, Journal of physiological anthropology, Volume 26, Issue 4, Pages 475-483. .
[15] A. Agathos, I. Pratikakis, S. Perantonis, and N. S. Sapidis, 2010, “Protrusion-oriented 3D Mesh Segmentation”, The Visual Computer, Volume 26, Issue 1, Pages 63-81,January. .
[16] H. Wang, T. Lu, O. KC. Au, and CL. Tai, 2014, “Spectral 3D mesh segmentation with a novel single segmentation field”, Graphical Models, Volume 76, Issue 5, Pages 440–456, September. .