基于特征点的三维模型配准算法

◆徐磊

（辽宁大学 辽宁 110036）

1 引言

在计算机视觉研究领域中，三维物体配准技术是一项非常重要的基础研究。

三维模型配准可以分为两类：粗配准、精配准。粗配准可以在两个模型姿态未知的情况下，提供快速、高效的方式，完成两个模型之间的配准工作。同时粗配准还可以为精配准提供一个良好的初始位置条件，减少精配准迭代所需的时间消耗。精配准可以完成模型之间精细的配准，使模型之间的误差更小。

基于RANSAC的粗配准方法[1]利用“点云”数据间的重叠区域确定对应点，根据对应点求解待匹配点云间的刚体变换关系；一种是ICP算法（迭代最近点算法）[2]，一种是利用ICP的改进算法[3]。

2 基于特征点的三维模型配准算法

2.1 特征点提取

研究人员将网格顶点v的法向张量投票定义为与1环面相邻的加权协方差矩阵的和：

因为一个法向投票张量是一个对称的“正半定”二阶张量，它可以被分解为如下形式：

我们可以根据张量T的特征值，将三角网格上的一个顶点分类为角点，边上点和面上点，依据Shimizu等[4]的定义，如果顶点位于“拐角”或“锐边”上，边缘强度大约是1，如果它位于一个面上，则几乎为0。分类条件为：

2.2 模型粗配准（改进的4pcs算法）

算法概括：给定两个“点”集P，Q，不确定度δ，以及“点集”P与“点集”Q重叠度的预估f，结合本文章节2顶点特征提取，获得相应的特征“点集”S1，S2。我们的目标是找到一个刚性变换使得“点集”S1中的点尽可能多的与“点集”S2中的某些点的距离小于δ。

（1）在“点集”P的特征“点集”S1中选择一些共面4点对。

（2）对于给定的基础对X，我们可以定义放射不变比集合。从“点集”Q的特征“点集”S2中提取出所有满足e1=e2且在一定范围δ内的条件即与X相符合的4点集合。

（3）为了确认唯一的Ti，我们计算Ti（v），并且统计有多少点与“点集”S2之间的距离小于δ，最后得到最佳刚性变换矩阵T。

2.3 模型细配准（改进的ICP算法）

ICP算法核心是最小化一个目标函数：

可归纳为以下步骤：

给定两个“点集”P1，P2，每一次迭代，匹配程度都在提高。

步骤1.筛选：由P1中的点，在P2中搜索出其最近的点，组成一个点对；找出两个点集中所有的点对组成两个新点集。（随机筛选法与最近邻点法）

步骤2.计算重心：根据“点集”对，计算两个新点集的重心（均匀分配权重）。

步骤3.R、T优化：由新点集，计算出下一步计算的旋转矩阵R，和平移矩阵T。

步骤4.收敛：得到旋转矩阵和平移矩阵R、T，就可以计算“点集”P2进行刚体变换之后的新点集P21，由计算P2到P21的距离平方和，以连续两次距离平方和之差绝对值，作为是否收敛的依据。若小于阈值，就收敛，停止迭代（固定比例法）。

步骤5.重复：重复1-5，直到收敛或达到既定的迭代次数。

3 结果分析

从图1的配准结果来看快速4PCS粗配准算法能够将三维模型初步对齐，为细配准阶段提供良好的初始位置，而改进的ICP算法能够实现模型的进一步精确配准，从而实现模型的完全匹配。

图1 Dragon模型“先粗后细”配准结果，Armadillo模型“先粗后细”配准结果

4 总结

针对带有噪声的三维网格模型，本文提出了一种“先粗配再细配”的模型配准方法。该算法首先基于张量投票提取出模型的特征顶点，之后采用一种快速4PCS配准算法实现模型的粗配准，不仅可以避免算法陷入局部极值，而且大大提高了配准的精度；细配准算法则是通过改进ICP算法实现两个曲面的最终精确配准。在今后的研究中，要进一步优化算法的时间性能和配准精度。