一個視覺物體或一個三維模型的骨架，是一種可以揭示該物體或模型的拓樸結構的呈現方式，因此骨架可以被應用在諸多場合當中，例如形狀分析和電腦動畫。近年來，有許多針對從一個物體當中抽取骨架的研究工作。然而，大多數的研究著重於完整和乾淨的資料（儘管這些研究當中，有一些有將缺失值考慮在內），但在實務上，我們經常要處理不完整和不潔淨的資料，就像資料裡面可能有缺失值和雜訊。在本論文中，我們研究雜訊處理，而且我們將焦點放在針對帶有雜訊的點雲資料進行前置處理，以便生成相應物體的骨架。在我們提出的方法當中，我們首先識別可能帶有雜訊的資料點，然後降低雜訊值的影響。為了識別雜訊，我們將監督式學習用在以密度和距離作為特徵的資料上。為了降低雜訊值的影響，我們採用三角形表面和投影。這個前置處理方法是有彈性的，因為它可以搭配任何能夠從點雲資料當中抽取出物體的骨架的工具。我們用數個三維模型和多種設定進行實驗，而結果顯示本論文所提出的前置處理方法的有效性。與未經處理的模型（也就是原始模型加上雜訊）相比，在從帶有雜訊的點雲資料當中產生物體的骨架之前，如果我們先使用本論文所提出的前置處理方法，那麼我們可以得到一個包含更多原來的物體的拓撲特徵的骨架。我們的貢獻如下：第一，我們展示了機器學習可以如何協助電腦圖學。第二、針對雜訊識別，我們提出使用距離和密度做為學習過程中要用的特徵。第三、我們提出使用三角表面和投影，以減少在做雜訊削減時所需要花費的時間。第四、本論文提出的方法可以用於改進三維掃描。

The skeleton of a visual object or a 3D model is a representation that can reveal the topological structure of the object or the model, and therefore it can be used in various applications such as shape analysis and computer animation. Over the years there have been many studies working on the extraction of the skeleton of an object. However, most of those studies focused on complete and clean data (even though some of them took missing values into account), while in practice we often have to deal with incomplete and unclean data, just as there might be missing values and noise in data. In this thesis, we study noise handling, and we put our focus on preprocessing a noisy point cloud for the generation of the skeleton of the corresponding object. In the proposed approach, we first identify data points that might be noise and then lower the impact of the noisy values. For identifying noise, we use supervised learning on data whose features are density and distance. For lowering the impact of the noisy values, we use triangular surfaces and projection. The preprocessing method is flexible, because it can be used with any tool that can extract skeletons from point clouds. We conduct experiments with several 3D models and various settings, and the results show the effectiveness of the proposed preprocessing approach. Compared with the unprocessed model (which is the original model with the added noise), if we apply the proposed preprocessing approach to a noisy point cloud before using a tool to generate the skeleton, we can obtain a skeleton that contains more topological characteristics of the model. Our contributions are as follows: First, we show how machine learning can help computer graphics. Second, we propose to use distance and density as features in learning for noise identification. Third, we propose to use triangular surfaces and projection to save execution time in noise reduction. Fourth, the proposed approach could be used to improve 3D scanning.

[1] Junjie Cao, Tagliasacchi A., Olson M., and Hao Zhang. 2010. “Point Cloud Skeletons via
Laplacian Based Contraction,” Shape Modeling International Conference (SMI): 187-197.
[2] S. Wang, J. Wu, M. Wei, and X. Ma. 2012. “Robust curve skeleton extraction for vascular
structures,” Graphical Models 74(4):109-120.
[3] M. Raptis, D. Kirovski, and H. Hoppe. 2011. “Real-time classification of dance gestures
from skeleton animation,” Eurographics Symposium on Computer Animation: 147-156.
[4] R. Schnabel, R. Wessel, R. Wahl, and R. Klein. 2008. “Shape Recognition in 3D
Point-Clouds,” The International Conference in Central Europe on Computer Graphics,
Visualization and Computer Vision. Vol.2.
[5] Aleksey G., Vladimir G. K., and Thomas Funkhouser. 2009. “Shape-based recognition of
3D point clouds in urban environments,” IEEE 12th International Conference on
Computer Vision: 2154-2161.
[6] Alexander V., Roman S., and Konrad Schindler. 2012. “Implicit shape models for object
detection in 3d point clouds,” ISPRS Annals of the Photogrammetry, Remote Sensing and
Spatial Information Sciences. Volume I-3.
[7] Marco Livesu, Fabio Guggeri, and Riccardo Scateni. 2012. “Reconstructing the
Curve-Skeletons of 3D Shapes Using the Visual Hull,” IEEE Transactions on
Visualization and Computer Graphics 18(11): 1891-1901.
[8] J. C. Carr, R. K. Beatson, J. B. Cherrie, T. J. Mitchell, W. R. Fright, B. C. McCallum, and
T. R. Evans. 2001. “Reconstruction and representation of 3D objects with radial basis
functions,” SIGGRAPH '01 Proceedings of the 28th annual conference on Computer
graphics and interactive techniques: 67-76, 2001.
[9] Michael W, Philipp J., Qixing H., Martin B., and Leonidas Guibas. 2007.
“Reconstruction of Deforming Geometry from Time-Varying Point Clouds,” SGP '07
Proceedings of the fifth Eurographics symposium on Geometry processing: 49-58.
[10] D. F. Lu, H. K. Zhao, M. Jiang, S. L. Zhou, and T. Zhou. 2005 “A Surface
Reconstruction Method for Highly Noisy Point Clouds,” Variational, Geometric, and
Level Set Methods in Computer Vision: 283-294
[11] N. J. Mitra, and A. Nguyen. 2003. “Estimating surface normals in noisy point cloud data,”
SCG '03 Proceedings of the nineteenth annual symposium on Computational geometry:
322-328.
[12] J. C. Carr, R. K. Beatson, T. J. Mitchell, W. R. Fright, B. C. McCallum, and
B. C. McCallum. 2003. “Smooth surface reconstruction from noisy range data,”
Proceedings of the 1st international conference on Computer graphics and interactive
techniques: 119-126.
[13] H. K. Jankowski, and L. I. Stanberry. 2012. “Identifying Skeleton Curves in Noisy Data,”
Communications in Statistics - Simulation and Computation 41(6): 852-864.
[14] Alexander Bucksch, and Roderik Lindenbergh. 2008. “CAMPINO — A skeletonization
method for point cloud processing,” ISPRS Journal of Photogrammetry & Remote Sensing
63: 115-127.
[15] Wei Jiang, Kai Xu, Zhi-Quan Cheng, Ralph R. Martin, and Gang Dang. 2013. “Curve
skeleton extraction by coupled graph contraction and surface clustering,” Graphical
Models 75 :137-148.
[16] Mathieu B., Saïda B., Boubakeur B., and Erwan Guillou. 2014. “Ongoing human action
recognition with motion capture,” Pattern Recognition 47: 238-247.
[17] Luca Rossi, and Andrea Torsello. 2014. “Coarse-to-fine skeleton extraction for high
resolution 3D meshes,” Computer Vision and Image Understanding 118: 140-152.
[18] Oscar Kin-Chung Au, Chiew-Lan Tai, Hung-Kuo Chu, Daniel Cohen-Or, and Tong-Yee
Lee. 2008. “Skeleton Extraction by Mesh Contraction,” ACM Transactions on Graphics,
Vol. 27, No. 3, Article 44.
[19] N. D. Cornea, Deborah S., and Patrick Min. 2007. “Curve-Skeleton Properties,
Applications and Algorithms,” IEEE Transactions on Visualization and Computer
Graphics 13(3): 530-548.
[20] Andr´e Sobiecki, Haluk C. Yasan, Andrei C. Jalba, and Alexandru C. Telea. 2013.
“Qualitative Comparison of Contraction-Based Curve Skeletonization Methods,”
Mathematical Morphology and Its Applications to Signal and Image Processing, 425-439.
[21] Clement Menier, Edmond Boyer, and Bruno Raffin. 2006. “3D Skeleton-Based Body Pose
Recovery,” 3rd International Symposium on 3D Data Processing, Visualization and
Transmission (DPVT '06): 389-396.
[22] Joohyuk Lee, Hyojoo Son, Changmin Kim, and Changwan Kim. 2013. “Skeleton-based
3D reconstruction of as-built pipelines from laser-scan data,” Automation in Construction
35: 199-207.
[23] Sen Wang, Jianhuang Wu, Mingqiang Wei, and Xin Ma. 2012. “Robust curve skeleton
extraction for vascular structures,” Graphical Models 74: 109-120.
[24] Sang Min Yoon, and Arjan Kuijper. 2013. “Human action recognition based on skeleton
splitting,” Expert Systems with Applications 40: 6848-6855.
[25] Lulu Chen, Hong Wei, and James Ferryman. 2013. “A survey of human motion analysis
using depth imagery,” Pattern Recognition Letters 34: 1995-2006.
[26] Andrea Tagliasacchi, Hao Zhang, and Daniel Cohen-Or. 2009. “Curve skeleton extraction
from incomplete point cloud,” ACM Transactions on Graphics 28(3), Article 71.
[27] Oscar Kin-Chung Au, Chiew-Lan Tai, Hung-Kuo Chu, Daniel Cohen-Or, and Tong-Yee
Lee. 2008. “Skeleton extraction by mesh contraction”, SIGGRAPH '08 27(3), No. 44.
[28] Andrei S., Thomas L., Gil S., Sivan T., and Daniel Cohen-Or. 2007. “Interactive
topology-aware surface reconstruction,” ACM Transactions on Graphics 26(3), No.43.
[29] Leonard R. Herrmann. 1976. “Laplacian-isoparametric grid generation scheme,” Journal
of the Engineering Mechanics Division 102 (5): 749–756.
[30] Olga S., Daniel C.O., Yaron L., Marc A., Christian R., and Hans-Peter Seidel. 2004.
“Laplacian Surface Editing,” SGP '04 Proceedings of the 2004 Eurographics/ACM
SIGGRAPH symposium on Geometry processing: 175-184.
[31] Andrea Tagliasacchi, Daniel Cohen-Or, and Hao Zhang. 2009. “Curve skeleton extraction
from incomplete point cloud,” ACM Transactions on Graphics 28(3), No.71.
[32] Lior S., Ariel S., and Daniel Cohen-Or. 2008. “Consistent mesh partitioning and
skeletonization using the shape diameter function,” International Journal of Computer
Graphics 24(4): 249–259.
[33] 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:
35–42.
[34] Oliver S., Alexander B., and Hans-Peter Seidel. 2005. “Robust filtering of noisy scattered
point data,” SPBG'05 Proceedings of the Second Eurographics / IEEE VGTC conference
on Point-Based Graphics: 71-77.
[35] Evangelos K., Derek N., Patricio S., and Karan Singh. 2009. “Extracting lines of curvature
from noisy point clouds,” Computer-Aided Design 41: 282-292.
[36] Mona Mahmoudi, and Guillermo Sapiro. 2009. “Three-dimensional point cloud
recognition via distributions of geometric distances,” Graphical Models 71: 22-31.
[37] Pingbo T., Daniel H., Burcu A., Robert L., and Alan Lytle. 2010. “Automatic
reconstruction of as-built building information models from laser-scanned point clouds: A
review of related techniques,” Automation in Construction 19: 829-843.
[38] Yong-Jin Liu, Dong-Liang Zhang, and Matthew Ming-Fai Yuen. 2010. “A survey on CAD
methods in 3D garment design,” Computers in Industry 61: 576-593.
[39] H. Woo, E. Kang, Semyung Wang, and Kwan H. Lee. 2002. “A new segmentation method
for point cloud data,” International Journal of Machine Tools & Manufacture 42: 167-178.
[40] Tamal K. Dey, and Samrat Goswami. 2004. “Provable Surface Reconstruction from Noisy
Samples,” Proceedings of the twentieth annual symposium on Computational geometry:
330-339.
[41] Facundo Mémoli, and Guillermo Sapiro. 2005. “A Theoretical and Computational
Framework for Isometry Invariant Recognition of Point Cloud Data,” Foundations of
Computational Mathematics 5(3): 313-347.
[42] Wei Jiang, Kai Xu, Zhi-Quan Cheng, and Hao Zhang. 2013. “Skeleton-based intrinsic
symmetry detection on point clouds,” Graphical Models 75: 177-188.
[43] Luke O., Faramarz F. S., Mario C. S., and Joaquim A. Jorge. 2009. “Sketch-based
modeling: survey,” Computers & Graphics 33: 85-103.
[44] Peter Axelsson. 1999. “Processing of laser scanner data—algorithms and applications,”
ISPRS Journal of Photogrammetry & Remote Sensing 54: 138-147.
[45] Hadi Fadaifard, George Wolberg, and Robert Haralick. 2013. “Multiscale 3D feature
extraction and matching with an application to 3D face recognition,” Graphical Models
75: 157-176.
[46] Gary K.L. Tam, Zhi-Quan Cheng, Yu-Kun Lai, Frank C. Langbein, Yonghuai Liu, David
Marshall, Ralph R. Martin, Xian-Fang Sun, and Paul L. Rosin. 2013. “Registration of 3D
Point Clouds and Meshes: A Survey From Rigid to Non-Rigid Gary,” IEEE Transactions
on Visualization and Computer Graphics 19 (7): 1199-1217.
[47] Mark Pauly, Niloy J. Mitra, and Leonidas J. Guibas. 2004. “Uncertainty and variability in
point cloud surface data,” SPBG'04 Proceedings of the First Eurographics conference on
Point-Based Graphics: 77-84.
[48] Mincheol Yoon, Yunjin Lee, Seungyong Leea, Ioannis Ivrissimtzis, and Hans-Peter Seidel.
2007. “Surface and normal ensembles for surface reconstruction,” Computer-Aided
Design 39: 408-420.
[49] Ravish Mehra, Pushkar Tripathi, Alla Sheffer, and Niloy J. Mitra. 2010. “Visibility of
noisy point cloud data,” Computers & Graphics 34(3): 219-230.
[50] Jean-Emmanuel Deschaud, and Francois Goulette. 2010. “A Fast and Accurate Plane
Detection Algorithm for Large Noisy Point Clouds Using Filtered Normals and Voxel
Growing,” Proceedings of 3D Processing, Visualization and Transmission Conference.
[51] Iat-Fai Leong, Jing-Jing Fang, and Ming-June Tsai. 2007. “Automatic body feature
extraction from a marker-less scanned human body,” Computer-Aided Design 39:
568-582.
[52] Jonathan Dinerstein, Parris K. Egbert, and David Cline. 2007. “Enhancing computer
graphics through machine learning: a survey,” Visual Compute 23: 25-43.
[53] Kecman, Vojislav. 2001. “Learning and Soft Computing,” MIT Press, Cambridge, MA.
[54] Suykens, J.A.K., Van Gestel, T., De Brabanter,J., De Moor, B., and Vandewalle, Joos.
2002. “Least Squares Support VectorMachines,” World Scientific, Singapore.
[55] Scholkopf, B., and Smola, A.J., 2002. “Learningwith Kernels,” MIT Press, Cambridge,
MA.
[56] Cristianini, N., and Shawe-Taylor, J. 2000. “An Introduction to Support Vector Machines
and Other Kernel-based Learning Methods,” First Edition (Cambridge: Cambridge
University Press).
[57] Mitchell, T. 1997. “Machine Learning,” McGraw Hill.
[58] Vangelis M., Ion A., and Geogios P. 2006. “Spam Filtering with Naive Bayes - Which
Naive Bayes?” Third Conferenceon Email and Anti-Spam.
[59] George H. John and Pat Langley. 1995. “Estimating continuous distributions in bayesian
classifiers” the Eleventh Conference on Uncertainty in Artificial Intelligence.
[60] Coppersmith, D., S. J. Hong, and J. R. M.Hosking. 1999. “Partitioning Nominal Attributes
in Decision Trees,” Data Mining and Knowledge Discovery 3: 197–217.