基于相关点漂移和动态形变图的三维形状非刚性对准方法

摘要

本发明提出一种基于相关点漂移和动态形变图的三维形状非刚性对准方法，首先，对三维形状和和其动态形变图进行相关点漂移，来进行初步校准；接着，对于初步对准的三维形状，通过均匀向下采样建立起每个三维形状的动态形变图；最后，通过优化建立的基于动态形变图的能量函数，实现三维形状的精确对准。该对准方法是一种全局的方法，可以对通用物体的完整或不完整三维模型以及CAD模型进行自动对准。

说明书

技术领域

本发明涉及三维形状的非刚性自动对准的方法，具体为一种基于相关点漂移和动 态形变图的三维形状非刚性对准方法。

背景技术

真实准确的数字化重建现实生活中物体是计算机视觉研究领域的一个重要问题， 而物体的对准是在计算机中真实重建现实生活中物体的一个重要步骤。三维形状对准 的目的就是找到两个或者多个三维形状的顶点之间准确的对应关系，通过减小对应顶 点之间的距离使物体发生形变。三维形状的刚性形变的对准已经成为一种很成熟的技 术，并且已经在很多商业软件中成功应用。然而，当现实生活中,存在着大量的非刚性 物体,当这些非刚性物体发生非刚性形变时，许多基于三维形状刚性形变对准的重建的 假设和方法已经不再适用，非刚性形变物体的对准已经成为一个急需解决的技术问题。

在目前国内外公开的文献中，Tingbo Hou,Hong Qin，“Robust Dense Registration of  Partial Nonrigid Shapes”：IEEE TRANSACTIONS ON VISUALIZATION AND  COMPUTER GRAPHICS2011中提出了一种基于热核坐标(HKCs)的对准办法，通 过热核坐标确定图形中点的邻域，从而确保对准过程中的顶点周围的几何相容性。该 方法通过计算多个热源的热核来确定HKCs索引点，然后以索引点的级数大小作为对 准过程中寻找对应点的依据。在具体实现时，首先通过特征检测和匹配确定热核的热 源，然后通过增长的方法逐步的对齐热源之外的其他点。Andriy Myronenko,Xubo  Song，“Point Set Registration:Coherent Point Drift”：IEEE TRANSACTIONS ON  PATTERN ANALYSIS AND MACHINE INTELLIGENCEE,2010中提出了一种基于相 关点漂移算法的点云概率对准概率模型。该模型将目标点云中的点源点云中的点看作 是由高斯混合模型产生的数据点，目标点云看作是高斯混合模型中各个模型的中心。 通过计算源点云中的点与目标点云中每个单高斯模型中心对应的后验概率，依据后验 概率的大小从而确定源点云和目标点云之间点的对应关系。Thomas Fabry，Dirk  Smeets，Dirk Vandermeulen，Paul Suetens，“3D non-rigid point cloud based surface  registration based on mean shift”：WSCG2010中提出了一种基于mean shift的无结构 点云的对准办法。通过对形变建立不同的正则化模型，来进行三维点云的对准。Qi-Xing  Huang，Bart Adams，Martin Wicke，Leonidas J.Guibas，“Non-Rigid Registration under  Isometric Deformations”：Eurographics Symposium on Geometry Processing2008中解决 了等体积三维形状的对准问题。

但上述几种三维形状的对准方法有几点不足：

(1)基于热核坐标的部分形变对准方法要求对准物体不能有大的缺失，并且只能应 对局部的较小的形变。

(2)基于相关点漂移的对准算法虽然能够应对较大的形变，但其对象为点云，且由 于没有考虑到三维形状点与点之间的连接关系,对准过程中不能保证三维形状 的几何特性,容易产生畸变,对准精度有限。

(3)基于mean shift的对准算法，除具有(2)的缺陷外，还存在着不能应对非均匀采 样和非自然形变的问题。

(4)基于等体积物体的非刚性对准，要求三维形状必须为完整的且体积想等的三维 形状。

发明内容

为了克服现有对准方法性能差，易产生畸变，对三维形状完整性要求高，适用范 围小，对准精度低的问题，本发明提供一种基于相关点漂移和动态形变图相结合的改 进的三维形状非刚性形变的自动对准方法，该对准方法是一种全局的方法，可以对通 用物体的完整或不完整三维模型以及CAD模型进行自动对准。首先，对三维形状和 和其动态形变图进行相关点漂移，来进行初步校准；接着，对于初步对准的三维形状， 通过均匀向下采样建立起每个三维形状的动态形变图；最后，通过优化建立的基于动 态形变图的能量函数，实现三维形状的精确对准。

本发明解决其技术问题所采用的技术方案为：

所述一种基于相关点漂移和动态形变图的三维形状非刚性对准方法，其特征在于： 包括以下几个步骤：

步骤1：相关点漂移的点云对准：

提取源三维形状顶点集作为数据集，提取目标三维形状顶点集作为高斯混合模型 中单高斯模型的中心集；通过期望最大化算法计算数据集中的点与高斯混合模型中单 高斯模型的中心的对应关系；

步骤2：三维形状的向下采样：

使用边融合方法，对源三维形状进行均匀向下采样，构建出源三维形状的动态形 变图；

步骤3：动态形变图的形变驱动：

步骤3.1：将步骤2获得的动态形变图中的每个顶点作为一个节点，对于动态形 变图的第i个节点x_i，赋给该节点旋转矩阵A_i，平移矩阵b_i，并且初始化A_i＝I_3×3，I 表示单位阵，b_i＝(0,0,0)^T；

步骤3.2：建立能量优化函数E_rigid，E_smooth，E_fit，其表达式分别为：

$\left(\begin{array}{c}{E}_{\mathrm{rigid}}=\underset{x_i}{\Sigma }\{{\left[{\left(a_1^i\right)}^T{a}_2^i\right]}^2+{\left[{\left(a_1^i\right)}^T{a}_3^i\right]}^2+{\left[{\left(a_2^i\right)}^T{a}_3^i\right]}^2\\ {[1-{\left(a_1^i\right)}^T{a}_3^i]}^2{+[1-{\left(a_1^i\right)}^T{a}_2^i]}^2+[1-{\left(a_2^i\right)}^T{a}_3^i]{\}}^2\end{array}\right)$

$E_{\mathrm{fit}}=\underset{(v_i,c_i)\in C}{\Sigma }{\alpha }_{\mathrm{point}}{\left|\right|{\tilde{v}}_i-c_i\left|\right|}_2^2+{\alpha }_{\mathrm{plane}}{n}_{c_i}^T{\left|\right|{\tilde{v}}_i-c_i\left|\right|}_2^2$

其中，分别为A_i的列向量；

r_i和r_j分别表示第i个节点x_i和第j个节点x_j形变影响的区域，表示 均一化的权重系数，

ω(x_i,x_j,r_i+r_j)＝max(0,(1-d²(x_i,x_j)/(r_i+r_j)²)³)，d(x_i,x_j)为节点x_i，x_j间的欧式距离；

α_point＝0.1，α_plane＝1，v_i为源三维形状上的点经 过动态形变图映射后其对应的新的坐标位置，c_i表示原目标三维形状上与v_i的对应点， 为c_i的法向量，C表示所有对应点对(v_i,c_i)组成的集合；

步骤3.3：用高斯牛顿法最小化E_tot＝E_fit+α_smoothE_smooth+α_rigidE_rigid，其中α_smooth＝50， α_rigid＝100，得到E_tot取得最小值时，源三维形状上的各个点经过动态形变图映射后其对 应的新的坐标位置，对准过程结束。

有益效果

本发明的有益效果是：

本发明实现了一种三维形状的非刚性形变的自动对准的方法，该方法通过使用相 关点漂移算法结合动态形变图技术，在不依赖任何几何特征的情况下，可以自动对准 发生非刚性形变的完整和不完整的三维形状。其优点在于：

1)不使用任何几何特征，避免了三维形状几何特征的繁琐计算。

2)对准的三维形状不仅可以是完整的封闭的形状，也可以是不完整的三维形状

3)整个对准过程自动化。

4)对准方法可以完成较大的非刚性形变的三维形状的对准。

实验结果表明，本发明提出的三维自形状非刚性形变自动对准的方法具有鲁棒性 强，对准精度高，自动化程度高，应用范围广的优点。

附图说明

图1为该发明实现的总流程图。

图2相关点漂移算法流程图。

图3为边融合方法示意图。

图4动态形变图驱动形变流程图。

图5为对准结果的展示。

具体实施方式

附图1是本发明实现三维形状非刚性对准的总流程，该对准过程包含了基于相关 点漂移的初步对准和基于动态采样图的精细对准。在初步对准阶段，提取三维形状的 顶点位置，保留三维形状的面信息，将三维形状的顶点集看作相关点漂移算法中的需 对准的点云集合，在使用相关点漂移算法将两个三维形状的顶点进行对准后，恢复保 留的面信息，从而实现三维形状的初步非刚性对准。在精选对准阶段，首先，对初步 对准的三维形状，在指定动态采样图的面数情况下，通过边融合的方法，均匀向下采 样获得动态形变图，并且通过K近邻搜索法建立动态形变图的顶点(为和三维形状的 顶点区别，下文中称动态形变图的顶点为节点)和原三维形状顶点之间的对应关系， 然后通过不断优化建立的能量函数，使动态形变图的形状不断发生形变，同时利用节 点和顶点之间的对应关系，将动态形变图的形变映射到原始的三维形状上，直至对准 精度满足对准要求。

结合附图，具体实施步骤以下做详细说明。

步骤1：相关点漂移的点云对准：

本步骤即进行原始三维形状的初步对准。

如图2所示，原始三维形状的初步对准是通过相关点漂移算法来实现的。提取源 三维形状顶点集X作为数据集，源三维形状即原始的需对准的三维形状，提取目标三 维形状顶点集Y作为高斯混合模型中单高斯模型的中心集；通过期望最大化算法(EM 算法)计算数据集中的点与高斯混合模型中单高斯模型的中心的的后验概率，从而确 立源三维形状顶点和目标三维形状之间的对应关系，利用所得的对应关系，将两个三 维形状进行非刚性对准：

具体来说，相关点漂移算法的步骤为：

1)初始化系数矩阵W＝0，协方差σ²，参数ω(0≤ω≤1)，β>0，λ>0。其中ω， β，λ为三个自由参数。其中ω反映了顶点集合中噪声点所占的比例，β，λ反映了顶 点集合的光滑化和正则化。β决定了模型的平滑性的正则化，即高斯滤波器的宽度。λ 代表了极大似然估计法拟合和正则化之间的权衡。W＝W_M×D＝(w₁,····,w_M)^T，D是数据 集的维数，本发明中D＝3，N，M分别为源三维形状顶点和目标三维形状顶点的个数。 x_n，y_m分别为源三维形状和目标三维形状的顶点坐标。

2)构建核矩阵G_M×M，其中矩阵元素

3)EM算法优化：

E步：计算后验概率矩阵P，其元素表达式为：

$p(m,n)=\frac{{\exp }^{-\frac{1}{{2\sigma }^2}{\left|\right|x_n-(y_m+G(m,·)w)\left|\right|}^2}}{\underset{k=1}{\overset{M}{\Sigma }}{\exp }^{-\frac{1}{{2\sigma }^2}{\left|\right|x_n-(y_k+G(k,·)w)\left|\right|}^2}+\frac{\omega }{1-\omega }\frac{{\left({2\mathrm{\pi \sigma }}^2\right)}^{D/2}M}{N}}$

后验概率p_(m,n)表示了顶点x_n和y_m之间的对应概率，G(m,·)代表了核矩阵G的第m 行。

M步：有以下公式优化求解P：

(G+λσ²d(P1)^-1)W＝d(P1)^-1PX-Y

N_P＝1^TP1

T＝Y+GW

${\sigma }^2=\frac{1}{N_{p}D}(\mathrm{tr}\left(X^{T}d\left(P^{T}1\right)X\right)-2\mathrm{tr}\left({\left(\mathrm{PX}\right)}^{T}T\right)+\mathrm{tr}\left(T^{T}d\left(P1\right)T\right)$

其中1表示元素全为1的列向量，d表示对角阵，tr表示向量的迹。

4)重复步骤3)，直至收敛：

当算法收敛后，三维形状点之间的对应关系由后验概率矩阵P中的元素p_(m,n)给 出，p_(m,n)的值越大，表示其相应的x_n和y_m之间的对应关系越强。对准后的三维形 状的顶点位置T由T＝Y+GW得到。

步骤2：三维形状的向下采样：

使用边融合方法，对源三维形状进行均匀向下采样，构建出源三维形状的动态形 变图。

如图3所示，以消去V0，V1为例，说明边融合方法的具体实施步骤如下：

1)确定新的顶点位置，即图3右边图中的顶点V，V为V0，V1的中点；

2)根据顶点和面的邻接关系找到原图中包含V1顶点(比如面A)的所有面；

3)用新的顶点V替换原始面中的V1；

4)重复步骤2和步骤3替换V0。

通过边融合方法向下采样便可获得与源三维形状相对应的动态形变图。使用动态 形变图来驱动源三维形状的非刚性对准可以减少变量个数，降低运算量，缩短运算时 间，提高三维形状非刚性对准的效率。

步骤3：动态形变图的形变驱动：

本步骤将步骤2中获得的动态形变图中的每个顶点定义为一个节点，通过优化需 校准的动态形变图和源三维形状之间的能量关系，驱动动态形变图的节点发生相容性 形变，通过K近邻搜索建立每个动态形变图中的每个节点和源三维形状中每个顶点的 对应的关系，根据节点与其源三维形状对应顶点之间的距离关系，确定其对源三维形 状顶点形变的影响大小，将动态形变图的形变依据一定准则映射到源三维形状上。这 样，在驱动源三维形状的形变对准的过程中避免了三维形状的畸变，保证了的需对准 的三维形状之间的几何相容性。通过使用向下采样的动态形变图来驱动源三维形状的 形变，减小了计算量，缩短了计算时间，提高了对准效率。

如图4所示，当获得初始校准的三维形状和动态采样图后，我们采用以下步骤进 行动态形变图驱动三维形状形变：

步骤3.1：将步骤2获得的动态形变图中的每个顶点作为一个节点，对于动态形 变图的第i个节点x_i，赋给该节点旋转矩阵A_i，平移矩阵b_i，并且初始化A_i＝I_3×3，I表 示单位阵，b_i＝(0,0,0)^T；

步骤3.2：建立能量优化函数E_rigid，E_smooth，E_fit，其表达式分别为：

$\left(\begin{array}{c}{E}_{\mathrm{rigid}}=\underset{x_i}{\Sigma }\{{\left[{\left(a_1^i\right)}^T{a}_2^i\right]}^2+{\left[{\left(a_1^i\right)}^T{a}_3^i\right]}^2+{\left[{\left(a_2^i\right)}^T{a}_3^i\right]}^2\\ {[1-{\left(a_1^i\right)}^T{a}_3^i]}^2{+[1-{\left(a_1^i\right)}^T{a}_2^i]}^2+[1-{\left(a_2^i\right)}^T{a}_3^i]{\}}^2\end{array}\right)$

$E_{\mathrm{fit}}=\underset{(v_i,c_i)\in C}{\Sigma }{\alpha }_{\mathrm{point}}{\left|\right|{\tilde{v}}_i-c_i\left|\right|}_2^2+{\alpha }_{\mathrm{plane}}{n}_{c_i}^T{\left|\right|{\tilde{v}}_i-c_i\left|\right|}_2^2$

其中，分别为A_i的列向量，E_rigid项描述了A_i的单位正交性；

r_i和r_j分别表示第i个节点x_i和第j个节点x_j形变影响的区域，表示 均一化的权重系数，

ω(x_i,x_j,r_i+r_j)＝max(0,(1-d²(x_i,x_j)/(r_i+r_j)²)³)，d(x_i,x_j)为节点x_i，x_j间的欧式距离， E_smooth项描述了每个节点与其周围节点形变具有相容性，最小化E_smooth保证了整个三维 形状在对准过程中表面的光滑性；

α_point＝0.1，α_plane＝1，v_i为源三维形状上的点经 过动态形变图映射后其对应的新的坐标位置，c_i表示原目标三维形状上与v_i的对应点， 为c_i的法向量，C表示所有对应点对(v_i,c_i)组成的集合，E_fit描述了需对准的三维形 状点与点及点与平面之间的距离；

步骤3.3：用高斯牛顿法最小化E_tot＝E_fit+α_smoothE_smooth+α_rigidE_rigid，其中α_smooth＝50， α_rigid＝100，得到E_tot取得最小值时，源三维形状上的各个点经过动态形变图映射后其对 应的新的坐标位置，对准过程结束。

最小化E_tot的目的为1)保证A_i的单位正交性，使三维形状不会发生扭曲畸变，2) 使每个节点与其周围节点形变具有相容性，确保整个三维形状在对准过程中表面光滑， 3)不断缩小需对准的三维形状点与点及点与平面之间的距离，使三维形状朝着目标方 向发生形变，最终完成三维形状的非刚性对准。

为避免高斯牛顿的局部收敛性，当高斯牛顿法取得最小值或者迭代次数达到一定 次数时，将α_smooth，α_rigid分别减半，重新优化，直至α_rigid<0.1或者迭代次数大于指定 次数时，优化停止，对准过程结束。

将对准后的结果导入到3维形状显示软件中进行分层和分颜色显示，可以直观的 观察对准的结果和误差。本发明的几组不同数据的实验结果如附图5所展示。由图5 可以看出，本发明不仅可以应对较少缺失的三维形状，也能应对具有较大缺失的三维 形状，并且对准的结果能够较好的保证原始三维形状的形状和几何特征，避免了对准 过程中畸变，对准后的三维形状几乎与目标三维形状完全重合。因而本发明具有较强 的适应性、稳定性和精确性。

以上整体所述是本发明的非刚性对准实施方式，本领域技术人员在不脱离本发明 原理的前提下，可以做出若干改进，包括改变优化能量函数，优化动态形变图的构造 方法等，本发明的范围由所附权利要求书及其等同限定。