﻿ 计算Laplace网格变形的三维模型配准
«上一篇
 文章快速检索 高级检索

 哈尔滨工程大学学报  2018, Vol. 39 Issue (10): 1702-1708  DOI: 10.11990/jheu.201704070 0

### 引用本文

YANG Jun, ZHANG Yao. Registration between 3D models by calculation of Laplace mesh deformation[J]. Journal of Harbin Engineering University, 2018, 39(10), 1702-1708. DOI: 10.11990/jheu.201704070.

### 文章历史

Registration between 3D models by calculation of Laplace mesh deformation
YANG Jun, ZHANG Yao
School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China
Abstract: A new non-rigid registration algorithm is proposed to align two models with different postures, based on skeleton subspace and Laplace mesh deformation. The algorithm first aligns the parts of the source and target models having the same postures using iterative closest point, then applies the skeleton subspace deformation to calculate the control points required by the Laplace mesh deformation. Finally, non-rigid deformation is applied to the source model using the Laplace mesh deformation to fully align with target models. The results showed that the proposed algorithm can be applied to the registration of large scale deformable models, not only to aligning two complete models with different postures, but also to aligning partial and complete models.
Keywords: model registration    iterative closest point(ICP) algorithm    Laplace-Beltrami operator    skeleton subspace deformation    Laplace mesh deformation    non-rigid    complete model    partial model

1 模型配准算法 1.1 ICP算法

 $g\left( {\mathit{\boldsymbol{R}}, \mathit{\boldsymbol{T}}} \right) = \mathop \sum \limits_{i = 1}^N {\left\| {{\mathit{\boldsymbol{Q}}_i} - (\mathit{\boldsymbol{R}}{\mathit{\boldsymbol{P}}_i} + \mathit{\boldsymbol{T}})} \right\|^2}$ (1)

1.2 骨架子空间变形

 $- \mathit{\boldsymbol{L}}{w_j} + \mathit{\boldsymbol{D}}{w_j} = \mathit{\boldsymbol{D}}{p_j}$ (2)
 ${D_{ii}} = 1/{d_i}^2$ (3)
 ${p_{ij}} = \left\{ {\begin{array}{*{20}{l}} {1, }&{\left\| {{\mathit{\boldsymbol{v}}_i} - {\mathit{\boldsymbol{s}}_j}} \right\| = \mathop {\min }\limits_{k \in \left[ {1, \cdots , m} \right]} (\left\| {{\mathit{\boldsymbol{v}}_i} - {\mathit{\boldsymbol{s}}_k}} \right\|)}\\ {0, }&{其他} \end{array}} \right.$ (4)

1.3 Laplace网格变形

2004年，Sorkine等[16]将微分域坐标引入图像处理，由于其能够使变形后的图像保持内容的完整性、连贯性和光滑度，于是2005年，Igarash等[17]提出可以将微分域坐标推广到三维数据，用来处理三维模型，并从理论上论述了该想法的可行性。Sorkine等[18]受文献[17]算法的启发，成功将微分域融入模型表面的三角网格的处理中，这种算法可以保留模型的表面信息(如曲率，法向量等)，使模型表面始终保持光滑，并逐渐成为常用的网格编辑算法，即Laplace网格变形。文中对源模型应用Laplace网格变形，并使其与目标模型完全对齐。

1.3.1 Laplace-Beltrami算子

Laplace-Beltrami算子[19]是定义在黎曼流形上的二阶微分算子，是在欧式空间中的Laplace算子的一种推广，本质上描述了空间中某点坐标值与其邻域坐标均值差异这一特征。

 ${\mathit{\Delta }_s}p = 2{H_p}{\mathit{\boldsymbol{n}}_p}$ (5)

 ${\delta _i}(\delta _i^x, \delta _i^y, \delta _i^z) = \mathop \sum \limits_{j = N\left( i \right)} {\mathit{\boldsymbol{w}}_{ij}}({\mathit{\boldsymbol{v}}_i} - {\mathit{\boldsymbol{v}}_j})$ (6)
 ${w_{ij}} = \frac{{{\omega _{ij}}}}{{\mathop \sum \limits_{\left( {i, k} \right) \in E} {\omega _{ik}}}}$ (7)

1) ωij=1，表示均匀权重，则Laplace算子

 ${\delta _i} = \frac{1}{{{d_i}}}\mathop \sum \limits_{j \in N\left( i \right)} ({\mathit{\boldsymbol{v}}_i} - {\mathit{\boldsymbol{v}}_j})$ (8)

 $\mathop {\lim }\limits_{\left| \gamma \right| \to 0} \frac{1}{{\left| \gamma \right|}}{\smallint _{v \in \gamma }}({\mathit{\boldsymbol{v}}_i} - \mathit{\boldsymbol{v}}){\rm{d}}l\left( \mathit{\boldsymbol{v}} \right) = H({\mathit{\boldsymbol{v}}_i}){\mathit{\boldsymbol{n}}_i}$ (9)

2) ωij=cotα+cotβ，表示余切权重。2003年Meyer等[21]提出了用余切权重代替均匀权重，产生了Cotangent Laplace算子：

 ${\delta _i} = \mathop \sum \limits_{j \in N\left( i \right)} \left( {\cot \alpha + \cot \beta } \right)({\mathit{\boldsymbol{v}}_i} - {\mathit{\boldsymbol{v}}_j})$ (10)

Cotangent Laplace算子是Laplace-Beltrami算子与模型表面几何信息相结合的一种Laplace-Beltrami算子的离散化形式，能够更好地逼近曲面的局部特征。

1.3.2 Laplace网格变形

Laplace网格变形技术[22]由Alexa提出的，已成为目前流行的能量优化类的网格变形算法。

 ${\delta _i} = (\delta _i^{\left( x \right)}, \delta _i^{\left( y \right)}, \delta _i^{\left( z \right)}) = {\mathit{\boldsymbol{v}}_i} - \frac{1}{d}\mathop \sum \limits_{j \in N\left( i \right)} {\mathit{\boldsymbol{v}}_j}$ (11)

V为模型顶点的笛卡尔坐标矩阵，δ为模型顶点的Laplace坐标矩阵，在变形前需要将模型的笛卡尔坐标矩阵转化为Laplace坐标矩阵。已知笛卡尔坐标系与Laplace坐标系之间的线性变换可以表示为矩阵形式：δ=LV，其中L为Laplace算子，是笛卡尔坐标与Laplace坐标之间的转换矩阵，可以表示为L=1-D-1A。式中I为单位矩阵，D为对角矩阵(Dii=di)，A为连接矩阵。

 ${A_{ij}} = \left\{ {\begin{array}{*{20}{l}} {1, }&{\left( {i, j} \right) \in E}\\ {0, }&{其他} \end{array}} \right.$ (12)

 $\left( {\frac{\mathit{\boldsymbol{L}}}{{\omega {\mathit{\boldsymbol{I}}_{k \times k}}~|~0}}} \right)V = \left( {\begin{array}{*{20}{c}} \mathit{\boldsymbol{\delta }}\\ {\omega {c_{1:k}}} \end{array}} \right)$ (13)

 $\mathit{\boldsymbol{V}}' = \arg \min ({\left\| {\mathit{\boldsymbol{LV}} - \mathit{\boldsymbol{\delta }}} \right\|^2} + \mathop \sum \limits_{j \in C} {\omega ^2}|{v_j} - {c_j}{|^2})$ (14)

V'是变形后网格上顶点的新的笛卡尔坐标值。此最小二乘解的解析解可以表示为：

 $V' = {({\mathit{\boldsymbol{L}}^{'{\rm{T}}}}\mathit{\boldsymbol{L}}')^{ - 1}}{\mathit{\boldsymbol{L}}^{'{\rm{T}}}}\mathit{\boldsymbol{b}}$ (15)

1.4 模型配准

1) 采用改进的ICP算法，将两模型放置于同一位置，使模型姿态相同的部分完全对齐。

2) 根据执行完ICP算法后对应点对的位置误差确定执行骨架子空间变形技术所需的顶点坐标vi，并计算这些顶点在变形后的坐标$v{'_i} = \mathop \sum \limits_{j = 1}^m {W_{ij}}{t_j}{v_i}$

3) 将vi作为执行Laplace网格变形的控制点，由于vi被移动后的坐标为，则式(13)方程组右边向量约束条件为ci=v'i。求解式(13)，可得到变形后除控制点外其他顶点的笛卡尔坐标。

2 实验结果与分析

 Download: 图 1 两个人体模型的配准结果与迭代误差 Fig. 1 The registration results and iterative error of two human models
 Download: 图 2 穿衣服的两个人体模型的配准结果和迭代误差 Fig. 2 The registration results and iterative error of two human models wearing clothes
 Download: 图 3 两个马模型的配准结果和迭代误差 Fig. 3 The registration results and iterative error of two horse models
 Download: 图 4 完整与部分(缺少一条腿)马模型的配准结果和迭代误差 Fig. 4 The registration results and iterative error of the horse models(complete horse model vs horse model lacking of right foreleg)
 Download: 图 5 完整与部分(缺少部分背部)马模型的配准 Fig. 5 The registration results and iterative error of the horse models(complete horse model vs horse model lacking of partial back)
 Download: 图 6 穿衣服的完整与部分(缺少右臂)人体模型的配准结果和迭代误差 Fig. 6 The registration results and iterative error of two human models wearing clothes(complete human model vs human model lacking of right arm)

3 结论

1) 本文所提出的结合骨架子空间变形技术和Laplace网格变形的非刚性三维模型配准算法既可以配准姿态不同的两个完整模型，也可以配准姿态不同的整体与部分模型(缺少某个部件或带有孔洞的模型)。此外，本算法还可以构建两个模型间的稠密对应关系。

2) 在实验中发现如果只是简单地移动位置相差比较大的点，没有保留模型表面的信息(如法向量、曲率等)，形变后模型表面会有毛刺现象，但通过骨架子空间变形技术得到控制点，结合Laplace网格变形算法可以保留模型表面的基本信息，确保模型表面的光滑性。然而，由于本算法对配准精度要求比较高，只能设置大量的控制点来克服弯曲、毛刺或者锯齿等缺陷，操作繁琐，运行时间比较长。能够把模型简化再进行非刚性配准以提高配准速度的同时还要确保配准的精确度是未来研究的方向。

 [1] ZHANG Jing, YAN C H, CHUI C K, et al. Multimodal image registration system for image-guided orthopaedic surgery[J]. Machine vision and applications, 2011, 22(5): 851-863. DOI:10.1007/s00138-010-0302-z (0) [2] KIM E, GORDONOV T, LIU Y, et al. Reverse engineering to suggest biologically relevant redox activities of phenolic materials[J]. ACS chemical biology, 2013, 8(4): 716-724. DOI:10.1021/cb300605s (0) [3] MOGLIA A, FERRAR V, MORELLI L, et al. A systematic review of virtual reality simulators for robot-assisted surgery[J]. European urology, 2016, 69(6): 1065-1080. DOI:10.1016/j.eururo.2015.09.021 (0) [4] ZHANG Dongwen, LI Zhicheng, CHEN Ken, et al. An optical tracker based robot registration and servoing method for ultrasound guided percutaneous renal access[J]. Biomedical engineering online, 2013, 12: 47. DOI:10.1186/1475-925X-12-47 (0) [5] FINETTO C, ROSATI G, FACCIO M, et al. Implementation framework for a fully flexible assembly system (F-FAS)[J]. Assembly automation, 2015, 35(1): 114-121. DOI:10.1108/AA-03-2014-022 (0) [6] GELFAND N, MITRA N J, GUIBAS L J, et al. Robust global registration[C]//Proceedings of the 3th Eurographics Symposium on Geometry Processing. Switzerland, 2005: 197-206. http://dl.acm.org/citation.cfm?id=1281953 (0) [7] MITRA N J, FLORY S, OVSJANIKOV M, et al. Dynamic geometry registration[C]//Proceedings of the 5th Eurographics Symposium on Geometry Processing. Switzerland, 2007: 172-182. http://dl.acm.org/citation.cfm?id=1281991.1282015 (0) [8] LI Hao, SUMNER R W, PAULY M. Global correspondence optimization for non-rigid registration of depth scans[J]. Computer graphics forum, 2008, 27(5): 1421-1430. DOI:10.1111/cgf.2008.27.issue-5 (0) [9] 李俊, 程志全, 李宏华, 等. 一种面向大尺度变形的非刚性注册算法[J]. 计算机学报, 2011, 34(3): 539-547. LI Jun, CHENG Zhiquan, LI Honghua, et al. A non-rigid registration algorithm of large-scale deformable models[J]. Chinese journal of computers, 2011, 34(3): 539-547. (0) [10] MORITA K, KOBASHI S, WAKATA Y, et al. Non-rigid cerebral surface registration for neonates using ICP algorithm[J]. Transactions of the institute of systems, control and information engineers, 2016, 29(5): 195-201. DOI:10.5687/iscie.29.195 (0) [11] SERAFIN J, GRISETTI G. NICP: dense normal based point cloud registration[C]//Proceedings of 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems. Hamburg, Germany, 2015: 742-749. http://ieeexplore.ieee.org/document/7353455/ (0) [12] CHENG Shiyang, MARRAS I, ZAFEIRIOU S, et al. Active nonrigid ICP algorithm[C]//Proceedings of 2015 11th IEEE International Conference and Workshops on Automatic Face and Gesture Recognition. Ljubljana, Slovenia, 2015: 1-8. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=7163161 (0) [13] 杨军, 张瑶, 黄亮. 改进的ICP算法在三维模型配准中的研究[J]. 计算机科学与探索, 2018, 12(1): 153-162. YANG Jun, ZHANG Yao, HUANG Liang. Research on 3D model registration by improved ICP algorithm[J]. Journal of frontiers of computer science and technology, 2018, 12(1): 153-162. (0) [14] BESL P J, MCKAY N D. A method for registration of 3-D shapes[J]. IEEE transactions on pattern analysis and machine intelligence, 1992, 14(2): 239-256. DOI:10.1109/34.121791 (0) [15] MURAI A, ENDO Y, TADA M. Anatomographic volumetric skin-musculoskeletal model and its kinematic deformation with surface-based SSD[J]. IEEE robotics and automation letters, 2016, 1(2): 1103-1109. DOI:10.1109/LRA.2016.2524069 (0) [16] TAUBIN G. A signal processing approach to fair surface design[C]//Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques. New York, 1995: 351-358. http://dl.acm.org/citation.cfm?id=218473 (0) [17] IGARASHI T, MOSCOVICH T, HUGHES J F. As-rigid-as-possible shape manipulation[J]. ACM transactions on graphics, 2005, 24(3): 1134-1141. DOI:10.1145/1073204 (0) [18] SORKINE O, ALEXA M. As-rigid-as-possible surface modeling[C]//Proceedings of the 5th Eurographics Symposium on Geometry Processing. Aire-la-Ville, Switzerland, 2007: 109-116. http://dl.acm.org/citation.cfm?doid=1281991.1282006 (0) [19] UMEHARA M, YAMADA K. Differential geometry of curves and surfaces[J]. Undergraduate texts in mathematics, 2016, 2(4): 273-275. (0) [20] VODEV G. Uniform estimates of the resolvent of the laplace-beltrami operator on infinite volume riemannian manifolds with cusps[J]. Communications in partial differential equations, 2002, 27(7/8): 1437-1465. (0) [21] MEYER M, DESBRUN M, SCHRODER P, et al. Discrete differential-geometry operators for triangulated 2-manifolds[M]//HEGE H C, POLTHIER K. Visualization and Mathematics Ⅲ. Berlin, Heidelberg: Springer, 2003: 35-57. (0) [22] ALEXA M. Differential coordinates for local mesh morphing and deformation[J]. The visual computer, 2003, 19(2/3): 105-114. (0)