点云配准RANSAC算法研究改进

吴俊秀，陈桂芬，李岳，朱海忱

（长春理工大学 电子信息工程学院，长春 130022）

近年来，得益于三维点云数据技术的发展，机器视觉技术获得了迅猛发展，三维点云数据实际应用也越来越受到各方的关注，目前在逆向工程、计算机视觉、文物数字化等领域三维点云数据处理技术已得到了广泛推广。三维点云数据配准是点云数据处理的关键技术，它的主要原理是把不同位置的点云通过重叠部分的信息，变换到同一个位置［1-2］。三维点云配准技术从点云位置来分可分为粗配准技术和精配准技术。粗配准技术主要用于配准两个位置相差很大的点云，在粗配准技术方面曾有Fischler提出了RANSAC算法［1］，主要思想是不考虑点云位置间距离的相差大小，都能实现配准，但该算法运算复杂度高、运算时间长、配准精度差、配准效率低，并不适合大规模点云配准。精配准技术用于已经粗配准好的点云，其中包括Besl等人提出了的ICP［3-17］算法，以及Zhang等在它的基础上的改进算法，Granger等［3］把EM（Expectation Maximization algorithm）算法应用到ICP上的改进，Gold等人［4］也提出Softassign的配准算法。这一类算法虽然在搜寻特征点方面有些进步，但还是无法做到将无关点及误匹配点剔除和校正。

鉴于上述问题，本文从配准精度和配准效率等方面进行研究，在点云配准过程中通过交比不变的约束方式，将无关点进行剔除，将错误点进行校正，改进了RANSAC求解仿射变换矩阵的方法。提出一种改进的RANSAC快速点云配准算法，提高了配准速度和精度，节省了配准时间。

1 点云配准RANSAC算法

求源点云和目标点云的旋转平移矩阵（刚性矩阵或欧式变换）是点云配准过程［7］的核心，将源点云变换到目标点云相同的坐标系下，通常可以表示为：

其中，pt,ps就是源点云和目标点云中的一对对应点。图1为点云配准原理图，点云一与点云二相互重叠，重叠部分中临近点之间的变换关系就是其中的R与T旋转平移矩阵，即两个集中点的对应关系，也是配准的核心问题。

图1 点云配准的原理图

RANSAC算法首先选择少而有效的初始数据集合，再从一定容差范围中尽可能地扩大初始数据集合。

2 交比不变模型相关定理

在射影变换中，有一个基本的不变量，称为交比不变量，在剔除和校正错误的点云匹配点对中［6］，需要用到交比（Equality of Cross Ratio）恒定性原理［1］，也就是射影变换保持点列的交比不变性。

定理1 已知A,B,C，三点在直线l上，把C作为参考点，于是有点A,B与点C之间的距离比值就是一个位置比值，如图2所示，即：

图2 定理示意图

定理2 已知在直线上的A,B,C,D，C,D四点作为参考点，同理由式（2）得到两个简单比值的比值，即为交比比值：

定理3 以投影中心O为参考条件下，在三维空间中的四个点A,B,C,D存在四个对应点A1,B1,C1,D1，他们也是共线的。而且点A,B,C,D的交比在三维空间投影下基本不受影响，即交比比值恒定。即：

推理 由定理3可知，图像中的不变点通常用到交比比值恒定原理。平面标定模板内有四个点在一条直线上：q1=(x1,y1),q2=(x2,y2),q3=(x3,y3),q4=(x4,y4)，从而得到四个点的交比：

RANSAC算法虽然是应用最为广泛的点云配准方法，但是由于RANSA算法是按照几何关系一致性来随机选择多对对应点作为控制点将点云配准，然后再将以上过程迭代多次，以此来确保最大概率获得较优的匹配效果，这样计算过程颇为耗时，误匹配率较高，因此RANSAC点云配准算法一般只能获得一个不准确的配准结果。鉴于此，本文提出基于交比不变原理选取样本集改进RANSAC算法。

3 基于交比不变的改进RANSAC实现

将交比不变的性质应用在RANSAC算法中，作为采集目标图像局内点的约束条件。针对误匹配点多，计算效率低的问题，在检测得出目标图像中的局内点坐标后，通过交比不变原则对目标图像中配准错误的局外点坐标进行校正，增加局内点的个数，有效地解决传统算法找寻最优仿射矩阵效率低下的缺点。

交比不变的RANSAC改进算法配准目标点云的具体步骤如下：

（1）假设随机选择一组个数为n的匹配点作为参考样本，N为全部数据点数，θ为这n个数据点符合该模型的概率，即：

（2）通过上述参考样本得到参考模型M，用全部数据点检验模型参数，得到该模型的局内点数n′。

（3）预先设定误差阈值δ，小于δ，该模型区域为目标点云特征点区域；大于δ，重新计算目标点云特征点区域。

（4）根据所选目标点云区域两特征点间的梯度值，设源点云图像中第i个特征点的坐标为(xi,yi)，i=1,2,...,n，中心特征点坐标为(xc,yc)，两特征点间的距离可表示为：

源点云图像中n个特征点坐标间的距离矩阵为：

通过设置目标点云的中心点坐标与源点云的中心点坐标之间的距离阈值，来评估配准误差，当目标点云的中心点坐标与源点云的中心点坐标之间的距离大于设定阈值时，重复上述第（3）步到第（4）步，直到满足设定阈值。

（5）对目标点云中各特征点的坐标位置进行评定。设新的配准目标点云中的特征点坐标为各特征点坐标间的距离为，计算方法同步骤（4）。则新的配准目标各特征点间的距离比与源点云各特征点间的距离比的比值：

若eij=0，则表示新配准的目标点云特征点定位错误，需要对其进行坐标位置校正。

（6）若目标点云与源点云临近两点的距离比大于设定的阈值时，即认为定位错误，同时对目标点云的点坐标距离比做一次遍历检查，对不符合条件的点，通过交比不变原则进行校正，即将符合交比条件的点重新设置为特征点。假设配准的目标图像有m个点定位正确，n个点定位错误。r,s,t为m个正确定位点中的3个随机的互异共线的点，v为n个错误定位点中与r,s,t共线的点。r,s,t,v分别对应源点云中第1、2、3、4四个点。则由定理1得：

根据交比不变原则，可以对错误配准的目标点云坐标点进行校正，对校正后的点再次进行评定，若符合要求则进行下一步，否则重复第（5）步操作。

（7）经过K次重复操作之后，在校正完成后的匹配点对中选取6对对应点，计算旋转平移矩阵初值H。

（8）再利用迭代最近点算法ICP（Iterative Cloest Point，），在已知旋转平移矩阵初值H的情况下，进一步精配准，得到更加精确的旋转平移矩阵［12］。假设P、M是两个点集，P为目标点云的点集，M为源点云的点集，其基本步骤如下［2］：

（1）匹配模型中进行匹配的数据点的选取采样，即从P中取点集pi。

（2）两模型中有对应关系的匹配点的选择，再在M中找出距离pi最近的对应点集mi。

（3）匹配点对的估计误差的选取，通过最小二乘法计算mi中最近点之间最小二乘意义下的配准参数R和t，并计算估计误差d：

（4）更新数据远匹配的点对，使用R和t对数据点集pi中所有点进行更新，获得更新后的数据点集pk。

（5）迭代停止度量准则的选择，对数据点集合Pk重复上述（2）-（4），直到两次迭代之间的估计误差d变化小于阈值δ，停止迭代。

（6）通过最优化方法的重复迭代，此时可以得到两个点云的配准结果，从中选取6对对应点，计算精确的旋转平移矩阵H′。

4 仿真实验及其结果分析

4.1 仿真实验

本节通过对来自斯坦福大学的点云数据库中的点云数据进行实验，来评估本文算法的性能。实验平台为Windows7 64位操作系统，Visual Studio 2013 Visual C++win32控制台应用程序，开源点云库pcl1.8.0。本实验平台为开放式平台，适用于一切实验环境。实验中点云数据来源于斯坦福大学点云数据库中bunny0和bunny045点云数据，表1为点云数量及实验参数，表2为改进RANSAC算法和SAC-IA+ICP算法配准过程所获得的旋转平移矩阵。

表1 实验参数

4.2 实验结果与分析

从实验结果表3可见，对于同一点云样本且实验参数设置相同时，使用SAC-IA+ICP配准算法，平均配准时间为5.5449s，粗配准时间为2.837s；而使用改进RANSAC算法通过对相应误匹配点对的校正和去除，提高了运算速度和精度，所以平均配准时间缩短为4.344s，粗配准时间减少到2.043s。

表2 点云转换仿射矩阵

表3 准确度和时间的实验结果对比

由表4可知，使用SAC-IA+ICP配准算法，平均误差距离为0.526cm，而使用改进RANSAC算法平均误差距离减少到0.500cm；而且改进RANSAC算法配准过程中在x、y、z方向上旋转角度也比传统算法减小了不少。可见本文算法在配准过程中配准角度有所减小，配准时间有所减少。

表4 精配准旋转角度及配准平均误差距离对比

图3与图4是随着阈值的增加，两种算法的平均误差距离以及精准配准时间的关系曲线图。从图中可以看出，阈值与配准速度先成正比关系，随着阈值的减小，精配准时间减小，在阈值到1.3左右时达到最小，之后开始增大。但在任何阈值下，改进RANSAC算法的平均误差距离和精准配准时间均比传统算法要小，可见本文算法的鲁棒性和配准效率均比SAC-IA+ICP算法要好。

图3 阈值与平均误差距离关系曲线图

图4 阈值与精配准时间距离关系曲线图

图5是随着配准次数的增加，SAC-IA+ICP算法和本文算法在配准时间上的比较。可以看出，随着配准迭代次数的增加，改进RANSAC算法配准所需的时间在逐步下降，而SAC-IA+ICP算法所需的时间正在加大；且从整体上看，在任何配准迭代次数下，本文算法所需时间都比所以SAC-IA+ICP少。加大配准次数是降低配准平均时间的决定因素，改进RANSAC算法的配准效率更高，而且在在多次配准下具有一定优势。

图5 配准次数与配准时间曲线图

5 结语

本文通过提出一种基于交比不变的RANSAC快速点云配准算法，解决点云配准过程中经常出现的误配准点和无关配准点问题。实验表明，通过校正误匹配点对和剔除无关匹配点对，改进RANSAC快速点云配准算法减少了不必要的特征点匹配过程，有效缩短配准目标在复杂场景中配准时间，成功减小配准误差距离，使得配准的效率和精度得到有效提高。本文所阐述的算法对提高点云配准的准确性具有重要意义，同时在机器视觉运用中，可有效提高机器视觉在复杂环境下的配准效率，在逆向工程中，同样可大大提高其重构精度。