臺灣博碩士論文加值系統

近幾年許多資訊技術快速發展。三維重建也是熱門議題之一，卻在重建模型時，可能因外在因素而導致資料缺失，而造成三維模型重建結果部分點雲缺失，進而造成模型表面有空洞。如果重新擷取資料與三維模型重建，將會需花費過多的時間與人力成本。
本研究提出資料修補流程，利用K-D樹找尋各點限制範圍內的k個最近鄰居（K-Nearest Neighbors, KNN)，並且利用穩定的局部雜訊範圍偵測（Robust Local Noise Scale Estimation)計算各點所存在之最適平面，並對模型進行剃除離群值與雙邊濾波器（Bilateral Filter)降低雜訊。接著藉由各點所存在的最適平面，偵測空洞邊界上的點，並劃分修補範圍以進行局部移動性最小平方重建法（Local Moving Least Squares, LMLS）修補空洞。最後執行參數化攤平（Parameterization Mapping)，重建德勞內三角化（Delaunay Triangulation, DT)網格模型。

In recent years, technologies to analyze and process the various types of acquired data are being investigated and developed. 3D reconstruction and modelling is among one of the developing technologies that received a lot of attention lately. During the process of 3D reconstruction, a multitude of factors may cause loss of data or failure to acquire correct data, resulting in missing portions of the acquired 3D point cloud. The missing or incorrect data further causes holes or artifacts within the rendered 3D model. Therefore, it is desirable to develop methods to process the 3D point cloud such that the 3D models can be rendered in a more realistic manner.
In this work, we propose a process to perform 3D surface reconstruction based on local moving least squares and KD trees. In the proposed method, K-D tree is used to locate the kth nearest neighbors within the neighbourhood of a point, robust local noise scale estimation is used to calculate the best fitting surface for each point. Outlier removal and bilateral filter are used to reduce noise on the 3D model. The best fitting surface for each point is then used to determine the points on the boundaries of holes, and the area is repaired using local moving least squares. Finally, parameterization mapping is used and Delaunay triangulation of the 3D model is performed to produce the final mesh model.

致謝
摘要
ABSTRACT
目錄
圖目錄
符號定義

第一章 緒論
1.1前言
1.2研究目的
1.3研究方法
1.4論文架構

第二章 文獻探討

第三章 局部移動性最小平方重建法
3.1 資料前處理
3.1.1 利用KD-Tree找尋最近鄰居
3.1.2 平面估測與剃除離群值
3.1.3 雜訊平滑化
3.2 資料修補
3.2.1 空洞位置定義
3.2.2局部移動性最小平方重建法（LMLS）
3.3 德勞內三角化網格模型重建
3.3.1德勞內三角化
3.3.2參數化攤平

第四章 實驗結果與分析
4.1離群值剃除與雜訊平滑化
4.2空洞位置定義
4.3局部移動性最小平方重建法（LMLS）
4.4參數化攤平網格重建結果

第五章 結論與未來研究方向
5.1結論
5.2未來研究方向

參考文獻

[1]N. Amenta, M. Bern, and M. Kamvysselis, “A New Voronoi-Based Surface Reconstruction Algorithm,” in Proceedings of the 25th annual conference on Computer graphics and interactive techniques, 1998, pp.415-421.
[2]C. J. Carr, K. R. Beatson, B. J. Cherrie, J. T. Mitchell, R. W. Fright, C. B. McCallum, and R. T. Evans, “Reconstruction and Representation of 3D Objects with Radial Basis Functions,” in Proceedings of the 28th annual conference on Computer graphics and interactive techniques, 2001, pp. 67-76.
[3]M. Alexa, J. Behr, D. Cohen-Or, S. Fleishman, D. Levin, and T. C. Silva, “Computing and rendering point set surfaces,” IEEE Transactions on visualization and computer graphics, vol. 9, no. 1, pp. 3-15, 2003.
[4]M. Kazhdan, M. Bolitho and H. Hoppe, “Poisson Surface Reconstruction,” in Proceedings of the fourth Eurographics symposium on Geometry processing, vol. 7, 2006, pp. 61-70.
[5]J. Wang and M. M. Oliveira, “Filling holes on locally smooth surfaces reconstructed from point clouds,” Image and Vision Computing, vol. 25, no. 1, pp. 103-113, 2007.
[6]D. Doria and RJ. Radke, “Filling Large Holes in Lidar Data by Inpainting Depth Gradients," in Proceeding of IEEE Computer Vision and Pattern Recognition Workshops (CVPRW), 2012, pp. 65-72.
[7]P. Lancaster and K. Salkauskas, “Surfaces Generated by Moving Least Squares Methods,” Mathematics of computation, vol. 37, no. 155, pp.141-158, 1981.
[8]S. Fleishman, D. Cohen-Or and T. C. Silva, “Robust moving least-squares fitting with sharp features,” ACM transactions on graphics (TOG) , vol. 24, no. 3, pp. 544-552, 2005.
[9]H. Obermaier, M. Hering-Bertram, J. Kuhnert, and H. Hagen, “Generation of adaptive streak surfaces using moving least squares,” Proceedings of Dagstuhl Follow-Ups Scientific Visualization Seminar, vol. 2, 2011.
[10]L. J. Bentley, “Multidimensional binary search trees used for associative searching,” Communications of the ACM, vol. 18, no. 9, pp. 509-517, 1975.
[11]I. Wald and V. Havran, “On Building Fast KD-Trees for Ray Tracing, and on Doing that in O (N log N),” in Proceeding of IEEE Symposium on Interactive Ray Tracing, 2006, pp. 61-69.
[12]S. W. Huang, “Integration of LIDAR and Vision Based Approaches for Textured 3D Scene Reconstruction.” M. S. Thesis, Department of Computer Science and Information Engineering, National University of Kaohsiung, 2012.
[13]B. Li, R. Schnabel, R. Klein, Z. Cheng, G. Dang, and S. Jin, “Robust normal estimation for point clouds with sharp features,” Computers & Graphics, vol. 34, no. 2, pp. 94-106, 2010.
[14]C. Tomasi and R. Manduchi , “Bilateral Filtering for Gray and Color Images,” in
Proceedings of the International Conference on Computer Vision (ICCV) , 1998, pp. 839-846.
[15]C. Pal, A. Chakrabarti, and R. Ghosh, “A brief survey of recent edge-preserving smoothing algorithms on digital images,” Procedia Computer Science, pp. 1-40, 2015.
[16]S. Fleishman, I. Drori, and D. Cohen-Or, ”Bilateral mesh denoising.” ACM transactions on graphics (TOG), vol. 22, no. 3, pp. 950-953, 2003.
[17]H. G. Bendels, R. Schnabel and R. Klein, “Detecting Holes in Point Set Surfaces,” World Society for Computer Graphics( WSCG), vol. 14, no. 1-3, pp. 89-96, 2006.
[18]L. Truong‐Hong, F. D. Laefer, T. Hinks, and H. Carr, “Combining an Angle Criterion with Voxelization and the Flying Voxel Method in Reconstructing Building Models from LiDAR Data,” Computer‐Aided Civil and Infrastructure Engineering, vol. 28, no. 2, pp. 112-129, 2013.
[19]D. Levin, “The approximation power of moving least-squares,” Mathematic of Computation, vol. 67, no. 224, pp. 1517-1531, 1998.
[20]C. Y. Chen, “A Hierarchical Spatial Clustering Algorithm Based on Delaunay Triangulation.” M. S. Thesis, Department of Computer Science and Information Engineering, Feng Chia University, 2005.
[21]C. L. Lawson, “Generation of a triangular grid with applications to contour plotting,” California Institute of Technology Jet Propulsion Laboratory Technical Memorandum, no. 299, 1972.
[22]B. C. Chen, “Unorganized Point Cloud Reconstruction Using Mean-Shift,” Ph. D. Thesis, Department of Geomatics, National Cheng Kung University, 2007.
[23]M. S. Floater and M. Reimers, “Meshless parameterization and surface
reconstruction,” Computer Aided Geometric Design, vol. 18, no. 2, pp. 77–92, 2001.
[24]K. Hormann and M. Reimers, “Triangulating point clouds with spherical
topology,” Curve and Surface Design, pp. 215–224, 2002.