鄭國揚臺灣大學：資訊工程學研究所高海峰Kao, Hai-FengHai-FengKao2007-11-262018-07-052007-11-262018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/53982在這個世界上有很多物體是由更小形狀更簡單的部份所組成的。如果可以找出這些物體的是由哪些部分所組成，將有助於物件的搜尋和檢索。在本論文中，我們試著把一個物體投影在二維平面上的形狀的各個部份的結構給找出來。和之前的作品不同的地方在於我們把這個抽象的問題轉化為數學上最佳化的問題，並提出一個多項式時間內的演算法來解決這個問題。這個演算法也可以整合對該類物體有關的知識或加入其他的限制來達到更好的效果。There are many objects which are composed of several primitive parts. It’s always beneficial to find the inherent structure of objects when dealing with the recognition, searching or indexing issues of the objects. This thesis aims to recover the intuitive and natural parts from the 2D shapes of objects. This thesis is different from the previous approaches via characterizing the traditional shape decomposition problem as an optimization problem. Building on the foundation of visual salience, our work shows that, the optimal solution of shape decomposition can be solved efficiently by dynamic programming when a set of pre-defined constraints is satisfied.Chapter 1 Introduction 3 1.1 Motivation and Goal.........................................3 1.2 Shape Decomposition.........................................5 1.2.1 Definition of Parts.......................................5 1.2.2 The non-uniqueness of shape decomposition.................7 1.2.3 Criteria for good shape decomposition algorithm...........8 1.3 Dissertation Overview.......................................9 Chapter 2 Review on Previous Work 11 2.1 Overview...................................................11 2.2 Visual Salience and Minimum Rule...........................11 2.2.1 The Minima Rule..........................................12 2.2.2 Boundary Strength........................................14 2.2.3 Relative Size............................................17 2.2.4 Protrusion...............................................17 2.3 The Extensions from Visual Salience........................18 2.4 Other Works on 2D Shape Decomposition......................20 Chapter 3 Optimization Formulation for Shape Decomposition .23 3.1 Overview...................................................23 3.2 The Optimization Formulation for Shape Decomposition.......23 3.3 The Star Shapes............................................25 3.4 Shape Decomposition for Star Shapes........................26 3.4.1 Decomposition............................................26 3.4.2 The Determination of Start Point.........................31 3.4.3 The Determination of Cut Number..........................31 3.5 The Computation Difficulty of the Optimization Formulation.32 Chapter 4 Experiment 35 4.1 Overview...................................................35 4.2 The Salience Function......................................35 4.3 Experiment Results.........................................36 4.4 Discussion.................................................43 Chapter 5 Discussion and Conclusions 47 5.1 The Extensions of Star Shape Decomposition.................47 5.2 Limitations of Star Shape Decomposition....................48 5.3 Comparison with Previous Work..............................48 5.4 Conclusion.................................................49 Bibliography.....................51957743 bytesapplication/pdfen-US形狀分割形狀分解動態規劃物件檢索shape segmentationshape decompositiondynamic programmingobject retrievalthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53982/1/ntu-95-R93922043-1.pdf