《电子技术应用》

一种快速的三维点云自动配准方法

来源:微型机与应用2013年第6期
谢冬香, 刘先勇
((西南科技大学 信息工程学院, 四川 绵阳 621000))
摘要: 采用主成分分析方法(PCA)定义了简单的数学模型和轴向确定方法等来实现配准。大量实验证明,算法能够快速实现任意形状、大小及位置的两片点云配准。

Abstract:

摘  要:采用主成分分析方法(PCA)定义了简单的数学模型和轴向确定方法等来实现配准。大量实验证明,算法能够快速实现任意形状、大小及位置的两片点云配准。
关键词:点云处理; 配准; 主轴旋转法; 轴向确定

    在机器视觉众多应用领域中,如立体匹配、图像配准和形状识别等,点云配准操作一直都是一个关键步骤。点云配准就是将一片点云(测试点集)的坐标匹配到另一片点云(参考点集)的坐标下,从而达到两片点云坐标的一致性,其配准精度直接影响后续误差分析的可靠性。目前,常用的配准方法有遗传算法、最小二乘匹配方法、三点对齐法以及ICP算法。遗传算法和最小二乘匹配方法需要多次迭代处理,计算复杂度高并且配准时间长;三点对齐法实现原理简单,能够很快地实现初始配准,但必须准确地确定出3对基准点的对应关系[1];ICP算法是一种众所周知的算法[2],传统的ICP算法虽简单,但在实际应用中具有限制性,因为它假设每一个点都可以在对应的点集中找到对应点,当两模型数据不一样时,该假设就不成立。
     在配准过程中,涉及旋转和平移矩阵的求取,EGGERT D W等人对比了奇异值分解法(SVD)、正交矩阵法(OM),单四元素法(UQ)以及双四元素法(DQ)4种当前流行和最有效算法的鲁棒性和精确度[3],运用分离算法测试了4种算法的稳定性。在非退化数据点集的情况下,大多数情况SVD和UQ是相似的,少量情况下是SVD更好一点,OM对于平面数据点集不稳定,而DQ算法则没有一种情况比其他3种算法好。基于这些测试结果,本文采用SVD来得到旋转矩阵。
1 本文算法
    主成分分析方法(PCA)的基本思想是,采用统计方法,对多变量表示数据点集合寻找尽可能少的正交矢量表征数据信息特征。本文采用PCA定义了简单的数学模型和轴向确定方法等。本文配准算法简单、稳定可靠、计算速度快且计算复杂度小。

    其中, n代表点集的个数。根据定义2、定义3计算惯量矩阵I,由定义4可以得到参考点集和测试点集的惯量矩阵I1、I2的特征值和特征向量。以I1为例,得到正交特征向量V1、V2和V3,以这3个特征向量建立坐标系有8种情况,首先规定坐标系必须满足右手规则,便可去掉4种情况。2008年张树森采用包围盒到去掉配准方向相反的情况,该方法计算速度非常慢[4]。本文先找到最大特征值对应的正交特征向量V1,然后寻找点集中离质心最远的点,如果此点与特征向量V1的夹角小于90°,则u1=V1,反之,u1=-V1,同理可以求得u2,u3=u1×u2,大大提高了配准速度。
    得到了参考点集和测试点集的正交特征向量后,旋转平移变换就转换为求取两组正交向量组的变换。由此可以得到待SVD分解的两点集相关矩阵为[5]:
    
2 测试效果
    以下所有测试实验均是在CPU为2.52 GHz,内存为3.50 GB的环境下进行的,采用了C++语言和OpenCV 2.3.1基础库,并在VS 2008软件平台上编译运行。为了验证算法的稳定性,测试选用了不同的形状,图3所示为3种典型模型的配准效果。其中,模型1为绵阳铁牛科技扫描的点云,模型2和模型3的点云采用的是Geomagic Qualify 12中的模型。从图3可以看到,这3种模型都可以实现配准。

    表1为各种模型的两片配准模型的点云个数和粗配准所需要的时间,可以看出,点云数据在几十万的情况下,配准时间全都是ms级。

    实验结果证明,本文采用的配准方法算法简单、稳定可靠、计算速度快且计算复杂度小,对实现大量点云快速配准具有使用价值。
参考文献
[1] 严平,孙肖霞.基于CAD模型的涡轮叶片误差检测系统[J].北京航空航天大学学报, 2008,34(10):1159-1162.
[2] BESL P J, MCKAY N D. A method for registration of 3-D shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence (S0162-8828),1992,2(14):239-256.
[3] EGGERT D W, LORUSSO A, FISHER R B. Estimating  3-D rigid body transformations: a comparison of four major algorithms[J]. Machine Vision and Applications (S0932-8092),1997,9:272-290.
[4] 张树森,李玮,程俊廷.基于逆向工程的三维测量点云数据与CAD数模配准算法研究[J].制造技术与机床,2008(3);114-117.
[5] APLPERT M, BRADSHAW J G. The principal axes transformation-a method for image registration[J]. The Journal  of Nuclear Medicine(S0161-5505),1990(31):1717-1722.

继续阅读>>