跳到主要內容

臺灣博碩士論文加值系統

(3.236.110.106) 您好!臺灣時間:2021/07/24 07:06
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳奕麟
研究生(外文):Yi-Lin Chen
論文名稱:三維片段隱式表面模型之漸進式重建
論文名稱(外文):Progressive Reconstruction of Piecewise Implicit Surface
指導教授:賴尚宏
指導教授(外文):Shang-Hong Lai
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:53
中文關鍵詞:表面重建隱式表面漸進式重建
外文關鍵詞:surface reconstructionimplicit surfaceradial basis functionprogressive reconstruction
相關次數:
  • 被引用被引用:1
  • 點閱點閱:113
  • 評分評分:
  • 下載下載:7
  • 收藏至我的研究室書目清單書目收藏:0
本論文發展了一套以Variational Implicit Surface為基礎,由緻密、精確三維座標點重建物體表面模型之快速演算法。物體表面模型重建乃科學與工程範疇中一重要之研究課題,並在諸如電腦圖學、視覺、CAD、醫學影像等領域中被廣泛應用。
傳統上,Variational Implicit Surface藉由建立單一的radial basis function並以其值域描述欲重建之物體表面,但其指數成長之複雜度使其不適用於處理日益龐大的資料量。本論文提出的片段式隱式表面(piecewise implicit surface)表示方法提供了一演算方法上的改進,並且能夠輕易處理包含數十萬以上資料點之模型。本論文乃基於divide-and-conquer之精神,將輸入資料適當地分割�(partitioning)為一組叢集(cluster),使得傳統方法得以輕易地施行於單一叢集,由此產生之區域表面最後組合成一完整之表面模型。
本論文提出之重建演算法主要包含兩部分:1) 分割隱式表面模型2) 漸進式重建(progressive reconstruction)演算法。本論文中證實了Variational Implicit Surface的可分割性,意謂在輸入資料經過適當分割之前提下,叢集數目並不影響重建之表面模型,分割隱式表面模型之用意僅在於降低複雜度。而在漸進式重建演算法中之關鍵元素,同時亦為本論文之另一主要貢獻,在於Schur complement formula的引入,憑藉其快速更新radial basis function係數之助益,片段式隱式表面模型乃成為一多重解析度(multi-resolution)之表示方法。論文最末亦展示了本物體表面重建演算法之效能與各式重建實例。
This thesis describes an efficient method for automatic reconstruction of closed, piecewise smooth and seamless surfaces from accurate and dense 3D points based on variational implicit surface. The problem of surface reconstruction arises in a diversity of applications in scientific and engineering domains such as computer graphics, animation, CAD, scientific visualization and medical imaging etc.
Traditionally, a variational implicit surface uses a single implicit function formulated as a sum of weighted radial basis functions to describe the unknown surface. However, the global support nature and exponential growth of the complexity of RBFs makes it infeasible for modeling data sets with more than only a few thousand points. The piecewise representation of implicit surfaces outlined in this thesis provides an algorithmic solution to the difficulties in handling large data sets faced by traditional approaches. The basic principle of our method is to partition the input data points into a set of clusters and apply the traditional method to them separately. The decomposed local implicit patches are then joined together to form the complete surface.
The reconstruction method has two major parts: 1) partitioning of the implicit surfaces and 2) progressive reconstruction. A key component in part 2 and another main contribution of this thesis is the introduction of a novel iterative refinement algorithm based on the Schur complement formula. The effectiveness of the proposed method is demonstrated by a number of experimental results of reconstructed surfaces from real-world scanning data.
List of Figures iii

List of Tables iv

Chapter 1 INTRODUCTION 1
1.1 PROBLEM STATEMENT 1
1.2 PREVIOUS WORKS 2
1.2.1 Generality: 2
1.2.2 Efficiency: 4
1.2.3 Flexibility: 6
1.2.4 Robustness: 7
1.3 OVERVIEW OF THE ALGORITHM 8
1.4 MAIN CONTRIBUTIONS 11
1.5 THESIS ORGANIZATION 11
Chapter 2 VARIATIONAL IMPLICIT SURFACE 13
2.1 MODELLING SURFACES WITH IMPLICIT FUNCTIONS 13
2.2 VARIATIONAL METHODS AND RADIAL BASIS FUNCTIONS 14
2.3 CONSTRAINT SPECIFICATION 19
2.4 APPROXIMATION VERSUS INTERPOLATION 20
2.5 COMPARISON OF VARIATIONAL METHODS WITH RELATED APPROACHES 22
Chapter 3 PARTITIONING OF IMPLICIT SURFACE 24
3.1 PARTITIONING 24
3.1.1 k-means clustering 25
3.1.2 Octree subdivision 26
3.1.3 Hierarchical BSP clustering 27
3.2 RBF CENTER PADDING 28
3.3 PIECEWISE IMPLICIT SURFACE 29
3.4 ALGORITHM COMPLEXITY 30
Chapter 4 PROGRESSIVE RECONSTRUCTION 32
4.1 PROGRESSIVE RECONSTRUCTION OF IMPLICIT SURFACES 32
4.2 SEED SETS SELECTION 34
4.3 ITERATIVE GREEDY ALGORITHM 36
Chapter 5 EXPERIMENTAL RESULTS 38
Chapter 6 CONCLUSIONS 46
6.1 SUMMARY 46
6.2 REMARKS ON THE PROPOSED RECONSTRUCTION METHOD 47
6.3 FUTURE DIRECTIONS 48
Bibliography 50
[1] N. Amenta, M. Bern, and M. Kamvysselis, "A New Voronoi-Based Surface Reconstruction Algorithm," In Proceedings of ACM SIGGRAPH, pp. 415-420, Aug. 1998.
[2] N. Amenta, S. Choi, T. K. Dey and N. Leekha, "A simple algorithm for homeomorphic surface reconstruction," In Proceedings of 16th. ACM Sympos. Comput. Geom., 213–222, 2000.
[3] R. K. Beatson and L. Greengard, "A short course on fast multipole methods," In Wavelets, Multilevel Methods and Elliptic PDEs, pp. 1-37, Oxford University Press, 1997.
[4] R. K. Beatson, W. A. Light, and S. Billings, "Fast solution of the radial basis function interpolation equations: Domain decomposition methods," SIAM J. Sci. Comput., vol. 22, no. 5, pp. 1717-1740, 2000.
[5] F. Bernardini, J. Mittleman, H. Rushmeier, and C. Silva, "The Ball-Pivoting Algorithm for Surface Reconstruction," IEEE Trans. Visualization and Computer Graphics, vol. 5, no. 4, pp. 349-359, Oct./Dec. 1999.
[6] J. F. Blinn, "A Generalization of Algebraic Surface Drawing," ACM Transactions on Graphics, 1(3), July 1982, pp. 135–256.
[7] J. Bloomenthal, "Polygonization of implicit surfaces," Computer-Aided Geometric Design 5, 4, 341-355, 1988.
[8] J. Bloomenthal, "An implicit surface polygonizer," In Graphics Gems IV, P. S. Heckbert, Ed. Academic Press, Cambridge, 324–349, 1994
[9] J. C. Carr, R.K. Beatson, J. B. Cherrie, T. J. Mitchell, W. R. Fright, and B. C. McCallum, "Reconstruction and Representation of 3D Objects with Radial Basis Functions," In Proceedings of ACM SIGGRAPH, pp. 67-76, Aug. 2001.
[10] J. C. Carr, R. K. Beatson, B. C. McCallum, W. R. Fright, T. J. McLennan and T. J. Mitchell, "Smooth surface reconstruction from noisy range data," ACM GRAPHITE 2003, pp119-126, 11-19 February 2003.
[11] P. Crossno and E. Angel, "Spiraling edge: Fast surface reconstruction from partially organized sample points," IEEE Visualization, pp. 317-324, October 1999.
[12] B. Curless and M. Levoy, "A Volumetric Method for Building Complex Models from Range Images," In Proceedings of ACM SIGGRAPH, pp. 303-312, Aug. 1996.
[13] T. K. Dey and J. Giesen, "Detecting undersampling in surface reconstruction," In Proceedings of 17th ACM Sympos. Comput. Geom, 257–263, 2001.
[14] T. K. Dey, J. Giesen and J. Hudson, "Delaunay Based Shape Reconstruction from Large Data," In IEEE Symposium on Parallel and Large Data Visualization, pp. 19-27, 2001.
[15] H. Q. Dinh, G. Turk and G. Slabaugh, "Reconstructing Surfaces by Volumetric Regularization Using Radial Basis Functions," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 24, No. 10, October 2002, pp. 1358-1371.
[16] H. Q. Dinh, G. Turk and G. Slabaugh, "Reconstructing surfaces using anisotropic basis functions," In International Conference on Computer Vision (ICCV) 2001, 606–613.
[17] H. Edelsbrunner and E. P. Mücke, "Three-Dimensional Alpha Shapes," ACM Trans. Graphics, vol. 13, no. 1, pp. 43-72, Jan. 1994.
[18] M. Gopi, S. Krishnan and C.T. Silva, "Surface Reconstruction based on Lower Dimensional Localized Delaunay Triangulation," In Proceedings of EUROGRAPHICS 2000, pp. 467-478.
[19] B. Heckel, A. E. Uva, and B. Hamann, "Clustering-Based Generation of Hierarchical Surface Models," IEEE Transactions on Visualization, Late Breaking Hot Topics Proceedings, pp. 41–44, 1998.
[20] H. Hoppe, "Surface Reconstruction from Unorganized Points," Ph.D. Thesis, Computer Science and Engineering, University of Washington, 1994.
[21] H. Hoppe, T. DeRose, and T. Duchamp, "Surface Reconstruction from Unorganized Points," In Proceedings of ACM SIGGRAPH, pp. 71-78, July 1992.
[22] D. Keren and C. Gotsman, "Fitting Curve and Surfaces with Constrained Implicit Polynomials," IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(1), pp. 21–31, 1999.
[23] L. P. Kobbelt, M. Botsch, U. Schwanecke and H.-P. Seidel, "Feature sensitive surface extraction from volume data," In Proceedings of ACM SIGGRAPH, pp. 57–66, 2001.
[24] M. Levoy, K. Pulli, B. Curless, S. Rusinkiewicz, D. Koller, L. Pereira, M. Ginzton, S. Anderson, J. Davis, J. Ginsberg, J. Shade and D. Fulk, "The digital Michelangelo project: 3D scanning of large statues," In Proceedings of ACM SIGGRAPH 2000, 131–144.
[25] W. E. Lorensen and H. E. Cline, "Marching Cubes: A High Resolution 3D Surface Construction Algorithm," In Proceedings of ACM SIGGRAPH, pp. 163-169, July 1987.
[26] B. Mederos, L. Velho and L. H. Figueiredo, "Moving Least Squares Multiresolution Surface Approximation," In Proceedings of IEEE SIBGRAPI, São Carlos, Brazil, October 12-15, 2003.
[27] D. D. Morris and T. Kanade, "Image-consistent surface triangulation," In Conf. Computer Vision and Pattern Recognition, volume 1, pp. 332–338, Hilton Head SC, USA, 2000.
[28] B. S. Morse, T. S. Yoo, P. Rheingans, D. T. Chen, and K. R. Subramanian, "Interpolating Implicit Surfaces from Scattered Data Using Compactly Supported Radial Basis Functions," Proc. of Shape Modeling Int’l Conf., pp. 89-98, May 2001.
[29] E. P. Mücke, "A Robust Implementation for Three-dimensional Delaunay Triangulations," International Journal of Computational Geometry & Applications, 8(2):255-276, 1998.
[30] S. Muraki, "Volumetric Shape Description of Range Data Using Blobby Model," In Proceedings of ACM SIGGRAPH, pp. 227–235, 1991.
[31] Y. Ohtake, A. Belyaev, M. Alexa, G. Turk, and H.-P. Seidel, "Multi-level partition of unity implicits," In Proceedings of ACM SIGGRAPH, pp. 463-470, 2003.
[32] D. V. Ouellette, "Schur complements and statistics," Linear Algebra Appl., 36, 187–295, 1981.
[33] M. Pauly, M. Gross and L. P. Kobbelt, "Efficient Simplification of Point-Sampled Surfaces," In Proceedings of IEEE Visualization, pp. 163-170, 2002.
[34] V. V. Savchenko, A. A. Pasko, O.G. Okunev, and T. L. Kunii, "Function Representation of Solids Reconstructed from Scattered Surface Points and Contours," Computer Graphics Forum, vol. 14, no. 4, pp. 181-188, 1995.
[35] L. G. Shapiro and G. C. Stockman, Computer Vision, Prentice Hall, Inc., Upper Saddle River, New Jersey, 2001.
[36] G. Taubin, "An Improved Algorithm for Algebraic Curve and Surface Fitting," In Proceedings of Fourth International Conference on Computer Vision, May 1993, pp. 658–665.
[37] I. Tobor, P. Reuter, and C. Schlick, "Efficient reconstruction of large scattered geometric datasets using the partition of unity and radial basis functions," Journal of WSCG, Vol. 12, No. 3, pp. 467-474, 2004.
[38] G. Turk and J. F. O’Brien, "Variational Implicit Surfaces," Technical Report 15, Georgia Inst. of Technology, 1999.
[39] G. Turk and J. F. O’Brien, "Modelling with Implicit Surfaces that Interpolate," ACM Transactions on Graphics, Vol. 21, No. 4, pp. 855-873, October 2002.
[40] G. Turk and J. F. O’Brien, "Shape Transformation Using Variational Implicit Functions," In Proceedings of ACM SIGGRAPH, pp. 335-342, Aug. 1999.
[41] G. Yngve and G. Turk, "Robust Creation of Implicit Surfaces from Polygonal Meshes," IEEE Trans. Visualization and Computer Graphics, Vol. 8, No. 4, pp. 346-359, October-December 2002.
[42] http://www.research.ibm.com/pieta/
[43] http://www.cyberware.com/samples/index.html
[44] http://www.cc.gatech.edu/projects/large_models/index.html
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top