臺灣博碩士論文加值系統

我們利用最小周長函數(Minimum Slice Perimeter function)，提出了一個三維網格骨架擷取演算法。最小周長函數是一個用來量測物體局部體積資訊的純量函數，藉由最小周長函數，我們可以找到每一個頂點的所相對的潛在骨架節點的所在位置，我們利用這些骨架節點的位置，將網格中的每一個點移動到它自己相對應的骨架節點的位置，可以將輸入的三維網格轉換至一個外觀上接近於骨架的網格，也就是所謂的骨架網格(skeleton mesh)，接著我們利用多層次精細度(LOD)簡化架構，來化簡這個骨架網格。我們利用多層次精細度簡化的目標是為了要保留骨架網格的整體外觀，並不同於傳統的多層次精細度化簡，它是專注於物體表面細節的維持。我們提出的演算法不僅僅簡單，並能夠有效的產生合理且不具多餘分支的骨架。

We propose a novel algorithm to extract curve-skeletons from 3D meshes using the minimum
slice perimeter (MSP) function. The MSP function is a scalar surface function to measure the
local volume information. Through the MSP function, we can find a potential skeleton position
to each vertex. We can transform the input mesh into a so called skeleton mesh whose shape
is close to a skeleton by moving each vertex to its corresponding potential skeleton positions.
After we obtain the skeleton mesh, we apply the LOD simplification to reduce the skeleton
mesh. Our LOD simplification aims to preserve the global shape of the skeleton mesh, rather
than local shape and features in traditional LOD simplification. The proposed algorithm is
simple yet effective in generating reasonably good curve skeletons that have no branches due to
surface noise.

1 Introduction 1
1.1 Contribution . . . . . . . . . . 3
1.2 Organization of the thesis . . . . . . 3
2 Related Work 4
2.1 Medial axis/surface . . . . . . . 4
2.2 Skeleton algorithms . . . . . . . . 6
2.2.1 Volumetric approaches . . . . . . 7
2.2.2 Geometric approaches . . . . . . . 10
3 Minimum Slice Perimeter Function 12
3.1 Introduction . . . . . . . . . . . 12
3.2 Error of MSP Slices . . . . . . . . . 15
4 Skeleton Extraction using MSP Function 21
4.1 Overview . . . . . . . . . . . . 22
4.2 Skeleton Mesh Computation . . . . . . 22
4.2.1 Repulsive Force Field Modeling . . . . 23
4.2.2 Deriving skeleton mesh . . . . . . . 23
4.3 Skeleton Mesh Simplification . . . . . . 27
4.3.1 LOD framework . . . . . . . . . 27
4.3.2 Error metrics . . . . . . . . . . 29
4.3.3 LOD Constraint . . . . . . . . . . 32
4.3.4 Replacement of the skeleton vertex . . 34
5 Results 35
5.1 MSP Computation Results . . . . . . 35
5.2 Preprocessing Time . . . . . . . . . 38
5.3 Skeleton Mesh Representation . .. . . . 40
5.4 Skeleton Results and comparison . . . . . 43
6 Conclusions 49
6.1 Summary . . . . . . . . . . . . 49
6.2 Limitations and Future works . . . . . . 50

[ABE07] D. Attali, J.-D. Boissonnat, and H. Edelsbrunner. Stability and computation of medial axes: a state of the art report. In B. Hamann T. Mぴoller and B. Russell, editors, Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration. 2007.
[AC97] N. Ahuja and J.-H. Chuang. Shape representation using a generalized potential field model. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(2):169–176, 1997.
[ACK00] N. Amenta, S. Choi, and R. K. Kolluri. The power crust, unions of balls, and the medial axis transform. Computational Geometry: Theory and Applications, 19:127–153, 2000.
[AHY94] G.H. Abdel-Hamid and Y. H. Yang. Multiresolution skeletonization: An electro-static field-based approach. In ICIP (1), pages 949–953, 1994.
[ATC+08] K. C. Au, C. L. Tai, H. K. Chu, D. C. Cohen-Or, and T. Y. Lee. Skeleton extraction by mesh contraction. In ACM SIGGRAPH 2008, pages 1–10. ACM, 2008.
[BA95] G. Bertrand and Z. Aktouf. Three-dimensional thinning algorithm using subfields. volume 2356, pages 113–124. SPIE, 1995.
[BKS01] I. Bitter, A. E. Kaufman, and M. Sato. Penalized-distance volumetric skeleton algorithm. IEEE Transactions on Visualization and Computer Graphics, 7(3):195–206, 2001.
[Blu67] H. Blum. A transformation for extracting new descriptors of shape. Models for the Perception of Speech and Visual Form, pages 362–380, 1967.
[BSB+00] I. Bitter, M. Sato, M. Bender, K. T. McDonnell, A. Kaufman, and M. Wan. Ceasar: Accurate and robust algorithm for extracting a smooth centerline. Washington, DC, USA, 2000. IEEE Computer Society.
[CCZ07] M. Couprie, D. Coeurjolly, and R. Zrour. Discrete bisector function and euclidean skeleton in 2d and 3d. Image Vision Comput., 25(10):1543–1556, 2007.
[CSM07] N. D. Cornea, D. Silver, and P. Min. Curve-skeleton properties, applications, and algorithms. IEEE Transactions on Visualization and Computer Graphics, 13(3):530–548, 2007.
[CSYB05] N.D. Cornea, D. Silver, X.S. Yuan, and R. Balasubramanian. Computing hierarchical curve-skeletons of 3d objects. 21(11):945–955, October 2005.
[CTK00] J. H. Chuang, C. H. Tsai, and M. C. Ko. Skeletonization of three-dimensional object using generalized potential field. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(11):1241–1251, 2000.
[DS06] T. K. Dey and J. Sun. Defining and computing curve-skeletons with medial geodesic function. In Proceedings of the fourth Eurographics symposium on Geometry processing, pages 143–152, Aire-la-Ville, Switzerland, 2006. Eurographics Association.
[DZ04] T. K. Dey and W. Zhao. Approximating the medial axis from the voronoi diagram with a convergence guarantee. Algorithmica, 38:387–398, 2004.
[GAHY96] T. Grigorishin, G. Abdel-Hamid, and Y. H. Yang. Skeletonization: An electrostatic field-based approach. Technical report, 1996.
[GB90] W. Gong and G. Bertrand. A simple parallel 3d thinning algorithm. volume i, pages 188–190 vol.1, Jun 1990.
[Gre03] R. Green. Spherical harmonic lighting: The gritty details. Archives of the Game Developers Conference, March 2003.
[HJWC09] T. C. Ho, H. X. Ji, S. K. Wong, and J. H. Chuang. Mesh skeletonization using minimum slice perimeter function. In Proceedings of CGW, 2009.
[Kon97] T. Y. Kong. Topology-preserving deletion of 1’s from 2-, 3- and 4-dimensional binary images. In DGCI, pages 3–18, 1997.
[KR89] T. Y. Kong and A. Rosenfeld. Digital topology: Introduction and survey. Computer Vision, Graphics, and Image Processing, 48(3):357–393, December 1989.
[LB01] C. Lohou and G. Bertrand. A new 3d 12-subiteration thinning algorithm based on p-simple points. Electronic Notes in Theoretical Computer Science, 46:33 – 52, 2001. IWCIA 2001, 8th International Workshop on Combinatorial Image Analysis.
[LL92] F. Leymarie and M.D. Levine. Simulating the grassfire transform using an active contour model. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(1):56–75, 1992.
[LWM+03] P. C. Liu, F. C. Wu, W. C. Ma, R. H. Liang, and M. Ouhyoung. Automatic animation skeleton construction using repulsive force field. In In Pacific Graphics, pages 409–413, 2003.
[Mor81] D. Morgenthaler. Three-dimensional simple points: serial erosion, parallel thinning, and skeletonization. Technical report, Computer Vision Lab, University of Maryland, 1981.
[MWL02] C. M. Ma, S. Y. Wan, and J. D. Lee. Three-dimensional topology preserving reduction on the 4-subfields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(12):1594–1605, 2002.
[OI92] R. Ogniewicz and M. Ilg. Voronoi skeletons: Theory and applications. In in Proc. Conf. on Computer Vision and Pattern Recognition, pages 63–69, 1992.
[OK95] R. L. Ogniewicz and O. Kbler. Hierarchic voronoi skeletons, 1995.
[PK98] K. Palagyi and A. Kuba. A 3d 6-subiteration thinning algorithm for extracting medial lines. Pattern Recognition Letters, 19(7):613 – 627, 1998.
[PK99a] K. Pal′agyi and A. Kuba. Directional 3d thinning using 8 subiterations. In DGCI, pages 325–336, 1999.
[PK99b] K. Pal′agyi and A. Kuba. A parallel 3d 12-subiteration thinning algorithm. Graphical Models and Image Processing, 61(4):199–221, 1999.
[Pud98] C. Pudney. Distance-ordered homotopic thinning: a skeletonization algorithm for 3d digital images. Comput. Vis. Image Underst., 72(3):404–413, 1998.
[RT95] J. M. Reddy and G. M. Turkiyyah. Computation of 3d skeletons using a generalized delaunay triangulation technique. Computer-Aided Design, 27(9):677–694, 1995.
[SBB+00] M. Sato, I. Bitter, M. A. Bender, A. E. Kaufman, and M. Nakajima. Teasar: Tree-structure extraction algorithm for accurate and robust skeletons. In Proceedings of the 8th Pacific Conference on Computer Graphics and Applications, page 281, Washington, DC, USA, 2000. IEEE Computer Society. [SC94] P. K. Saha and B. B. Chaudhuri. Detection of 3-d simple points for topology preserving transformations with application to thinning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(10):1028–1032, 1994.
[SLSK07] A. Sharf, T. Lewiner, A. Shamir, and L. Kobbelt. On-the-fiy curve-skeleton computation for 3d shapes. Comput. Graph. Forum, 26(3):323–328, 2007.
[SSCO08] L. Shapira, A. Shamir, and D. Cohen-Or. Consistent mesh partitioning and skeletonisation using the shape diameter function. Vis. Comput., 24(4):249–259, 2008.
[TVD08] J. Tierny, J.-P. Vandeborre, and M. Daoudi. Enhancing 3d mesh topological skeletons with discrete contour constrictions. The Visual Computing., 24(3):155–172, 2008.
[TZCO09] A. Tagliasacchi, H. Zhang, and D. Cohen-Or. Curve skeleton extraction from in-complete point cloud. ACM Transactions on Graphics, (Proceedings SIGGRAPH 2009), 28(3):1–9, 2009.
[WDK01] Mi. Wan, F. Dachille, and A. Kaufman. Distance-field based skeletons for virtual navigation. In Proceedings of the conference on Visualization ’01, pages 239–246, Washington, DC, USA, 2001. IEEE Computer Society.
[WML+03] F.-C. Wu, W. C. Ma, P. C. Liou, R. H. Laing, and M. Ouhyoung. Skeleton extraction of 3d objects with visible repulsive force, 2003.
[WML+06] F. C. Wu, W. C. Ma, R. H. Liang, B. Y. Chen, and M. Ouhyoung. Domain connected graph: the skeleton of a closed 3d shape for animation. The Visual Computer, 22(2):117–135, 2006.
[YBM04] Y. Yang, O. Brock, and R. N. Moll. Efficient and robust computation of an approximated medial axis. In In Proceedings of the ACM Symposium on Solid Modeling and Applications, pages 15–24, 2004.