本論文基於描述物體局部形變的簡易模型提出一套有效率的3D非剛性匹配演算法，並透過主曲率之運算進行脊檢測。由於採用結構光的深度相機在邊緣的影像品質較差，常造成在高曲率區域的幾何形狀與實際情況有所落差，本論文透過在3D模板上檢測脊點，並估計模板與實際數據的形變差異後，可將模板與脊點擬合至實際數據。
本論文採用主成分分析(Principal component analysis, PCA)的方式來估計主曲率以降低雜訊對曲率的影響，並經由凸面與凹面的判定來區分脊點與谷點，之後提取高曲率凸面作為感興趣區域。為了找到脊點，即表面上曲率的局部最大值，可透過主曲率方向定義的搜索空間下來得到最大曲率的脊點，最後再使用曲線擬合來得到連續且平滑的脊曲線。
3D非剛性匹配最佳化的求解空間包含對齊與形變的變因，因此較剛性匹配困難許多。本論文提出一個基於骨架變形的低自由度模型來描述目標數據的局部形變，低自由度模型可避免過度擬合的情況發生。此外，因初始對齊與形變有助於建立可靠的對應點，可避免最佳化落入局部最小值並加速收斂，本論文因此設計了一套初始化流程，由低自由度的解作為初始點，並在過程中提高自由度來依序進行最佳化，進而提升非剛性匹配的穩定性與準確性，最後透過不同形變的物體來測試非剛性匹配的效能。

This thesis presents a fast 3D nonrigid registration algorithm based on a simplified model to represent partially deformed objects, and an efficient algorithm to detect ridges employed via determining principal curvatures of 3D objects. Since structured light 3D sensing suffers from quite poor edge reconstruction, it usually leads to poor geometry in high-curvature regions. To solve this problem, we try to detect ridges from a 3D template model, and then register both of the template model and its ridges to the real data.
We adopted principal component analysis (PCA) based method to estimate principal curvatures, which greatly can eliminate the effect of noise. Next, we determined either convex or concave surfaces to distinguish between ridges and valleys, and select high curvature region as the region of interest (ROI). To find ridge points, the local maximum of curvature on surface, the search space defined by principal directions is used to get points with maximum curvature. Finally, curve fitting is used to generate a smooth and continuous ridge curve to meet our requirement.
Nonrigid registration is a challenging optimization problem since the solution space includes both alignment and deformation, which is much harder than the rigid registration. We designed a low degrees of freedom (DoF) model defined by using straight skeleton to represent partial deformation of objects. The proposed schemes can efficiently solve the optimization of registration and prevent overfitting. Moreover, a proper initialization for registration can help derive more reliable correspondences which can avoid stuck in local minimum and help converge faster during optimization. We also proposed to initialize a functional model from low-to-high DoF for improving the stability and accuracy of registration. We have demonstrated and evaluated results by including objects with various deformation.

[1] Teng-Feng Diao. “Multiple Depth Cameras Calibration and Fusion Algorithm for Object Reconstruction,” National Cheng Kung University, Taiwan, R.O.C. Thesis for Master of Science, 2019
[2] Y. Ohtake, A. Belyaev, and H. P. Seidel, “Ridge-valley lines on meshes via implicit surface fitting,” in ACM Trans. Graphics, vol. 23, 2004, pp. 609–612
[3] S. Gumhold, X. Wang, and R. MacLeod, “Feature extraction from point clouds,” in Proc. 10th Int. Meshing Roundtable, 2001, pp. 293– 305.
[4] M. Pauly, R. Keiser, and M. Gross, “Multi-scale feature extraction on point-sampled surfaces,” in Computer Graphics Forum, vol. 22, 2003, pp. 281–289.
[5] C. Choi, A. J. Trevor, and H. I. Christensen, “RGB-D edge detection and edge-based registration,” in Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst. (IROS), 2013, pp. 1568–1575.
[6] W. Wang, H. Pottmann, Y. Liu, “Fitting B-spline curves to point clouds by curvature-based squared distance minimization,” ACM Transactions on Graphics, 25 (2) (2006), pp. 214-238
[7] T. Morwald, J. Balzer, M. Vincze, “Modeling connected regions in arbitrary planar point clouds by robust B-spline approximation,” Robot. Auton. Syst., 76 (2016), pp. 141-151
[8] G. K. Tam, Z.-Q. Cheng, Y.-K. Lai, F. C. Langbein, Y. Liu, D. Marshall, R. R. Martin, X.-F. Sun, and P. L. Rosin, “Registration of 3D point clouds and meshes: A survey from rigid to nonrigid,” IEEE Trans. Visual. Comput. Graphics, vol. 19, no. 7, pp. 1199–1217, Jul. 2013.
[9] N.J. Mitra et al., “Dynamic Geometry Registration,” Proc. Symp. Geometry Processing (SGP), pp. 173-182, 2007.
[10] B.J. Brown and S. Rusinkiewicz, “Global Non-Rigid Alignment of 3-D Scans,” ACM Trans. Graphics, vol. 26, p. 21, 2007.
[11] Y. Pekelny and C. Gotsman, “Articulated Object Reconstruction and Markerless Motion Capture from Depth Video,” Computer Graphics Forum, vol. 27, pp. 243-253, 2008.
[12] W. Chang and M. Zwicker, “Automatic Registration for Articulated Shapes,” Proc. Symp. Geometry Processing (SGP), vol. 27, pp. 1459-1468, 2008.
[13] W. Chang and M. Zwicker, “Global Registration of Dynamic Range Scans for Articulated Model Reconstruction,” ACM Trans. Graphics, vol. 30, pp. 26:1-26:15, 2011.
[14] Radu Bogdan Rusu and Steve Cousins. 3D is here: Point Cloud Library (PCL). In 2011 IEEE International Conference on Robotics and Automation, pages 1–4. IEEE, May 2011.
[15] R. B. Rusu, N. Blodow and M. Beetz, "Fast point feature histograms (FPFH) for 3D registration", Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2009.
[16] P.J. Besl, N.D. McKay, “A method for registration of 3-D shapes,” IEEE Trans. PAMI, 14 (1992), pp. 239-256
[17] ALLEN B., CURLESS B., POPOVIC Z.: Articulated body deformation from range scan data. In ACM SIGGRAPH (2002), pp. 612–619.
[18] Michael Kazhdan and Hugues Hoppe: Screened poisson surface reconstruction. ACM Trans. Graph. (TOG) 32(3), 29 (2013).
[19] B. Allen et al., “The Space of Human Body Shapes: Reconstruction and Parameterization from Range Scans,” Proc. ACM SIGGRAPH, pp. 587-594, 2003.
[20] D. Anguelov et al., “The Correlated Correspondence Algorithm for Unsupervised Registration of Nonrigid Surfaces,” Proc. Neural Information Processing Systems (NIPS), vol. 17, pp. 33-40, 2004.
[21] R.W. Sumner and J. Popovic, “Deformation Transfer for Triangle Meshes,” Proc. ACM SIGGRAPH, pp. 399-405, 2004.
[22] H. Li et al., “Robust Single-View Geometry and Motion Reconstruction,” ACM Trans. Graphics, vol. 28, pp. 1-10, 2009.
[23] CAZALS, F., AND POUGET, M. 2008. Algorithm 889: Jet fitting 3: A generic c++ package for estimating the differential properties on sampled surfaces via polynomial fitting. ACM Trans. Math. Softw. 35, 3, 1–20.
[24] The stanford bunny. https://www.cc.gatech.edu/~turk/bunny/bunny.html. Accessed: 2020-07-08
[25] The mechanical part model. http://visionair.ge.imati.cnr.it/ontologies/shapes AIM@SHAPE Shape Repository. Accessed: 2020-07-08
[26] Robert W. Sumner, Johannes Schmid, and Mark Pauly. Embedded deformation for shape manipulation. In ACM SIGGRAPH 2007 papers, SIGGRAPH ’07, New York, NY, USA, 2007. ACM.
[27] K. Zampogiannis, C. Fermuller, and Y. Aloimonos, “Cilantro: A lean, versatile, and efficient library for point cloud data processing,” in Proceedings of the 26th ACM International Conference on Multimedia, ser. MM ’18. New York, NY, USA: ACM, 2018, pp. 1364–1367
[28] R. Szeliski. Computer Vision: Algorithms and Applications. 2010.