左向梅，韩鹏程

（西北工业大学航空学院，陕西 西安710072）

0 引言

计算机视觉在自动化生产的装配线上得到了很好的应用，能够用于识别零部件，在产品检验方面有着成功的应用。真实准确的数字化重建现实生活中的物体，是计算机视觉研究领域的一个重要问题，而物体的对准是在计算机中实现物体重建的一个重要步骤。三维形状对准的目的就是找到2个或者多个三维形状的顶点之间准确的对应关系，通过减小对应顶点之间的距离使物体发生形变。然而，在现实生活中存在着大量的非刚性物体，当这些非刚性物体发生非刚性形变时，许多基于三维形状刚性形变对准的重建假设和方法已经不再适用，非刚性形变物体的对准已经成为一个急需解决的技术问题。

刚性对准只需要根据一些对应关系就可以定义一个候选刚性变换来进行假设测试，非刚性情况下还需要变形和对准信息，因为它没有足够的先验假设，经常需要很多更加可靠的对应来定义变换。此外，非刚性对准还需要考虑变形，因此，相比于刚性对准，非刚性对准更加困难。

为了克服现有对准方法性能差，易产生畸变，对三维形状完整性要求高，适用范围小，对准精度低的问题［1－3］，提出了基于相关点漂移和动态形变图相结合的三维形状非刚性形变的自动对准方法。

1 相关点漂移

相关点漂移（CPD）［2］是一种基于概率的点集非刚性配准算法，该算法被视为基于速度场运动一致性约束的最大似然估计问题。在CPD算法中，一个点集作为高斯混合模型的内核，另一个点集作为高斯混合模型的数据，采用确定性退火的EM算法［4－5］对最大似然估计进行优化，从而找到2个点集的对应关系与非刚性变换，即内核点集向数据点集配准。这种方法可以估计复杂的非线性和非刚性变换，而且在含有噪声和溢出点的情况下有较强的鲁棒性。

方法中，将源模型的顶点看作数据集Y＝（y1，…，yM）T，将目标模型的顶点看作产生数据集的高斯混合模型的中心（内核点集）X＝（x1，…，xN）T，通过EM［4－5］算法计算数据集中的点，对应混合高斯模型中心的后验概率，从而确立源三维形状顶点和目标三维形状之间的对应关系，利用所得的对应关系，将2个三维形状进行非刚性粗对准。

GM×M为对称方阵；W＝WM×D＝（w1，…，wM）T为高斯内核矩阵；D为点云集的维数，取D＝3；N，M分别为源三维形状顶点和目标三维形状顶点的个数；tr为向量的迹；λ为常数。

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

a．初始化系数矩阵W＝0，协方差σ2，参数ω（0≤ω≤1），β＞0，λ＞0。

b．构建核矩阵GM×M，矩阵元素gij＝G（yi，yj）

c．EM算法优化。通过高斯混合模型聚类的EM 算法推导，能得到式（1）的上界［6］，即

G（m，·）表示G的第m 行。最小化Q就相当于最小化式（1）的能量函数。

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

后验概率pmn表示了顶点xn和ym之间的对应概率。

在M步中，优化求解W，对式（2）关于W 求导，得到方程：

1为元素全为1的列向量；d为对角阵。两边同乘以σ2G－1，得到方程的线性系统，即

从式（5）中解出W。

d．重复步骤c，直至收敛。

当算法收敛后，三维形状点之间的对应关系由后验概率矩阵给出，相应的对准后的三维形状T＝T（Y，W）＝Y＋GW。

2 形变图驱动模型对准

2．1 构建动态形变图

图模型本身的形变方式是通过对每一个结点应用对应的仿射变换，因此，对于结点自身，有槇gj＝gj＋tj。

对于原始模型上的任意顶点vi，其形变后的位置槇vi可以通过图模型每个结点的形变加权求和得到，也就是将形变图结点的变换外推到模型上每个顶点，即

ωj（vi）是与vi和gj之间距离d（gj，vi）相关的权值，ωj（vi）＝max｛0，［1－d2（gj，vi）／r2i］3｝。

该点的法向量也被相似变形：

这里使用边融合技术，在指定向下采样的三维模型面个数情况下，实现均匀采样，从而构建出原始三维模型的动态形变图，用来驱动三维形状的对准。

使用动态形变图来驱动原始三维形状的非刚性对准可以减少变量个数，降低运算量，缩短运算时间，提高三维形状非刚性对准的效率。手模型与其形变如图1所示。

图1 手模型及其形变

2．2 动态形变图驱动模型对准

通过求解形变图的变形来驱动原始模型的变形。在非刚性对准中，需要对图模型的结点求解未知的旋转变换和平移变换（Ri，ti）。保留特征的变形场可以通过使用下面的能量最大化局部刚性得到：

r1，r2，r3为Ri的列向量，上式从正交和单位长度方面测量了列向量的偏差。还需要额外的正则项确保变形的光滑性：

Esmooth项描述了每个节点与其周围节点形变具有相容性。最小化Esmooth保证了整个三维形状在对准过程中表面的光滑性。

引用非刚性ICP算法［6］思想，迭代计算最近点对应关系，随后进行修剪和变形步骤。为了避免非线性优化中的局部最小化，采用逐渐放松形变模型的正则能量系数的策略［7］。

尤其是免门票的方式可以吸引更多的消费者，这也代表着当前旅游发展模式的方向，可以扩大旅游资源的利用效率，企业员工、游客、社区居民可在园区内共享优美环境、共享改革开放的成果，这也是全域旅游的目标导向之一。

因为输入数据在时间上具有一致性，所以重复地在源模型和目标模型之间使用最近点对应来决定最优的形变。为了获得较准匹配，对应能量由点到点和点到面的度量组成，以避免在特征较少区域出现的不正确对应：

αpoint＝0．1，αplane＝1，槇vi为原始源模型上的点经过动态形变图映射后对应的新的坐标位置；ci为原始目标模型上与槇vi对应的点；C为所有对应点对组成的集合；Efit描述了需要对准的三维模型点与点及点与平面之间的距离。

为了求解（Ri，ti），建立目标能量函数：

初始化时取高的权值αsmooth＝50，αrigid＝100，此后通过最小化式（12），交替地进行对应点对的计算和形变。

2．3 高斯－牛顿法优化目标函数

使用高斯牛顿法最小化目标函数（7），高斯牛顿法源于无约束优化的牛顿算法。非线性最小二乘优化问题中的目标函数形式比较特殊，可以得到其雅克比矩阵的具体形式，将其代入牛顿法的迭代公式中，就可得到高斯牛顿法。

算法的具体步骤如下：

a．给定初始点x（0），精度σ＞0，置k＝0。

b．计算f（xk），S（xk）。

f．置x（k＋1）＝x（k）＋x。

g．检验终止原则，否则令k＝k＋1，转步骤b。

通过上述优化过程，保证了Ri的单位正交性，使三维模型不会发生扭曲畸变；使每个结点与其周围结点的形变具有相容性，确保这个三维模型在对准工程中表面光滑；不断缩小需对准的点与点及点与平面之间的距离，使三维模型朝着目标方向发生形变，最终完成三维形状的非刚性对准。

3 实验结果

用多组实验数据验证了方法的有效性，所有实验均在Inter Core（TM）2 Duo E7500 CPU，2 GB内存的Windows XP操作系统上，基于Matlab平台进行。其中，源模型和目标模型均为由Kinect对人体运动进行拍摄拼接得到的三维模型［8］。

在实验中，对于不同模型，CPD的参数选择对于实验结果影响较大。如图2所示，图2a为源模型与目标模型；在图2b中，β＝2．0，λ＝1．0；在图2c中，β＝3．0，λ＝1．0。由此可以看出，CPD的β参数影响对准后源模型的光滑性，β越大，光滑性越好。模型描述及实验结果如表1所示。

由表1可以看出，对于中等数据和大数据模型，算法都能在相对较短的时间内取得较好的配准精度。形变图结点数目对实验速度和精度有一定影响，点数越多，时间越长，匹配精度越高。

图2 CPD参数影响

表1 模型描述及实验结果

4 结束语

提出了三维形状的非刚性形变自动对准方法，通过使用相关点漂移算法结合动态形变图技术，在不依赖任何几何特征的情况下，可以自动对准发生非刚性形变的完整或不完整的三维模型。实验结果表明，即使对数据缺失比较严重或者形变较大的模型，此方法也能取得较好的效果，具有鲁棒性强、对准精度高、自动化程度高和应用范围广等优点。

［1］ Hou T，Qin H．Robust dense registration of partial nonrigid shapes［J］．IEEE Transactions on Visualization and Computer Graphics，2012，18（8）：1268－1280．

［2］ Myronenko A，Song X．Point set registration：coherent point drift［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（12）：2262－2275．

［3］ Fabry T，Smeets D，Vandermeulen D，et al．3D non－rigid point cloud based surface registration based on mean shift［C］．Proceedings 18th International Conference on Computer Graphics，Visualization and Computer Vision，2010．121－128．

［4］ 张祥德，唐青松．确定性退火技术在点配准中的应用［J］．东北大学学报（自然科学版），2003，24（11）：1119－1122．

［5］ 王 源，陈亚军．基于高斯混合模型的EM学习算法［J］．山西师范大学学报（自然科学版），2005，19（1）：46－49．

［6］ Allen B，Curless B，Popovi Z．The space of human body shapes：reconstruction and parameterization from range scans［J］．ACM Transactions on Graphics，2003，22（3）：587－594．

［7］ Sumner R W，Schmid J，Pauly M．Embedded deformation for shape manipulation［J］．ACM Transactions on Graphics，2007，26（3）：80－86．

［8］ Vlasic D，Peers P，Baran I，et al．Dynamic shape capture using multi－view photometric stereo［J］．ACM Transactions on Graphics，2009，28（5）：174－185．