改进ICP算法在点云精确配准中的应用

【摘要】逆向工程技术作为产品设计制作的一种手段，由于它的独特魅力，引起世界各国学术界和工业界的关注和高度重视。点云配准问题作为三维模型重建中的一个重要研究部分，已经得到越来越多的关注与研究，虽然当前存在着多种点云配准方法，但都存在一定的缺陷，在其存在的算法方面还存在着一些不足，对此国内外许多专家都在不断的努力，寻求更大的突破。本文对目前应用比较广泛的点云数据配准算法进行了深入细致的研究，最终实现了对原有的传统ICP算法进行了成功改进，使得改进后的ICP的算法在点云配准方面比传统ICP算法具有更好的配准效果。

【关键词】逆向工程技术；点云配准；ICP；特征点；三维模型重建

1. 引言

在测量工程的实际应用中，很难通过一次测量，完成物体完整表面的数据采集，往往所采集到的这些点云数据还存在着一定的旋转和平移错位，因此，通常会把物体表面分成多个局部的相互重叠的子区域，从不同的方向和视角进行测量，从而得到不同角度的、只覆盖物体部分表面的点云数据 [1]。

2. 点云数据的获取以及特性

（1）三维空间数据的特性。“数据”是指未经过加工的源数据或原始数据，点云数据的获取必须要通过测量手段、技术和方法，空间数据是指那些与地理分布有关的，反映现实世界各种现象以及其各种变化的数据[3]。由于三维信息存在着不确定性，而且它们会随着时间的变化而发生变化，因此三维空间数据的管理是已经非常复杂的事情，三维空间数据有三个特性，分别是时间特性、空间特性和尺度特性。

图1三维坐标变换示意图（2）三维空间数据的获取技术。三维空间信息的获取，实质上就是空间定位数据采集技术，目前有如下几种方式：天文测量技术、罗盘测量技术、大地测量观测技术、惯性测量技术和卫星定位技术等。

3. 点云数据的配准算法

3.1点云配准的原理。

3.1.1在逆向工程的研究中，通常可以将分块测量采集到的点云数据点集看作一个刚体，在这个基础上，空间点云配准的过程可以看成是在六自由度的无限连续参数空间内，对空间点云的整体搜素问题，因此空间点云配准的求解过程又可以归纳总结为相应的旋转矩阵T的求解问题[4]。

3.1.2假定同一个点，在o-x-y-z 坐标系中的定义为p（x，y，z） ，在坐标系O-X-Y-Z 中的定义为p'（x'，y'，z'） 。而刚体坐标变换所描述的就是该点分别在两个坐标系中不同的两种定义之间的关系问题，如图1所示。

3.1.3图1中所描述的坐标变换问题是由存在于三个欧拉旋转角θ，ψ，φ（0θπ，0ψ2π，0φ2π） 中的坐标旋转以及在三个坐标轴方向的三个分量xt =（o-O）x、yt =（o-O）y、zt =（o-O）z上的平移来共同决定的。该坐标转换问题的转换过程可以通过齐次矩阵T来描述：

T（θ，ψ，φ，xt，yt，zt ）= r11r12r13xt

r21r22r23yt

r31r32r33zt

0001 （1）

式中，旋转张量R的分量可用θ，ψ， 的函数来进行表达，即：

R（θ，ψ，φ）= r11r12r13

r13r22r23

r31r32r33= （2）

cosψcosφ-cosθsinψsinφ-cosψsinφ-cosθsinψcosφsinθsinψ

sinψcosφ+cosθcosψsinφ-sinψsinφ+cosθcosψcosφ-sinθcosψ

sinθsinφsinθcosφcosθ

3.1.4在上述计算中，我们给定六个刚体变换参数，分别为θ，ψ，φ，xt，yt，zt ，通过这六个刚体变换参数来求解变换矩阵T，而在齐次矩阵的三维点P=[x，y，z，1] 的计算上，就只需要做矩阵相乘的运算即可，可列等式：

p'=[T]p

从而得到

p'= x'

y'

z'

1=T（θ，ψ，φ，xt，yt，zt ）p= r11r12r13xt

r21r22r23yt

r31r32r33zt

0001 x

y

z

1 （3）

通过上述运算就可以得到其在O-X-Y-Z 坐标系中所对应的新位置 。 P'= [x'，y'，z'，1 ]

3.2经典ICP算法。ICP算法对它的实用对象要求并不严格，可以是点、曲线、隐式曲面、参数曲面等，其应用的关键是找点对，从理论上来看，当两个数据点集完全匹配的时候，目标函数应该为零[5]，但在实际应用中，点云数据无法避免的存在着噪声，所以两片点云之间并不总是能够达到理论上的匹配，因此当存在噪声和误差时，我们往往认为当目标函数最小的时候，能获得最佳配准解[6]。

F（R，T）=∑[RPi+T-P'i]2=min的求解过程实际上是一个高度的非线性求解问题。其实，并不存在一个关于P'i 的非常清楚的定义，因此我们需要一个与之非常接近的点，而这个点在空间点集 {qi}中可以找到，我们称这个最接近P'i 的点为 NearestPt（pi），当利用 来代替 P'i时，就可以将式 （2）中的等式修改为：

F（R，T） =∑[Rpi+T-NearestPt（pi）]2=min （4）

其中， NearestPt（pi）表示的是点集 {qi}中，通过Euclidean距离搜索出来的的最靠近{pi} 的一个点。

4. 改进ICP算法

4.1由于传统ICP点云配准算法对点云配准的初始位置要求非常严格，点云的初始位姿不能相差太大，否则在计算中会比较容易陷入局部最小解，但是在实际扫描中，不管是从仪器方面还是从技术方面来说，都并不能保证所有点云都有符合传统ICP点云配准算法对点云所要求的位姿[7]，因此，本文提出的算法是在传统ICP点云配准算法的基础上，首先采取三个基准的的坐标变换来提高点云数据的初始位置精度，然后进行ICP算法的配准。

4.2三点几何坐标变换方法为：首先根据点云数据的曲率特征，给出三个主方向最贴近的点作为测量基准点，这三个测量基准点的第一次测量坐标表示为 P1、 P2和 P3，当进行第二次测量时，这三个基准点的坐标变换为q1 、q2 和 q3 ，则上面所描述的刚体变换就可以通过三个步骤来进行实现：

4.2.1首先将 P1变换为q1：

4.2.2然后在只考虑方向的情况下，将矢量 （p2-p1）变换为矢量（q2 -q1 ）。

4.2.3最后进行的变换是，将包含 P1、P2 和 P3这三个点的平面转换到包含三点q1 、q2 和 q3 的平面。

以上所述可以用算法表示为：

Step1： 做三个矢量 （p2-p1）、 （p3-p1） 、 （q2 -q1 ）与 （q3 -q1 ）之间的计算；

Step2： 设定两个值，令V1 =p2-p1，W1= q2 -q1；

Step3： 作矢量V3 与 W3

V3=V1×（p3-p1）

W3=W1×（q3-q1 ） （5）

Step4： 作矢量V2与 W2

V2=V3×V1

W2=W3×V2 （6）

很容易看出，上述三个矢量V1 、V2 与 V3可以构成右手正交系，而另外三个矢量W1 、 W2与W3 也同样可以构成右手正交系。

Step5： 作单位矢量

v1=V11|V1|， v2=V21|V2|， v3=V31|V3|

W1=W11|W1|， W2=W21|W2|， W3=W31|W3| （7）

Step6： 把系统 [v]中的任一点Pi 变换到系统[w] 中，这种变换可以表示为下列变换关系式：

P'i =Pi R+T （8）

Step7： 由于[v] 和 [w]都是单位矢量矩阵，因此可以表示出[w]=[v]R ，于是所求的关于[w] 系统的旋转矩阵就相应的可以表示为：

R=[v]-1 [w] （9）

Step8： 使 P'l=ql和Pl=pl ，把这两个方程代入上述式中，可以得到平移矩阵T ；

T=q1-p1 [v]-1 [w] （10）

Step9： 最后可以将方程改写为：

P'=P[v]-1 [w]- P1[v]-1 [w] +q1 （11）

下图2给出的是三点坐标变换示意图：

实验模型，点数：2513/3200如下图3是实验原始点云，图4是初始配准后的点云数据结果图，图5是改进ICP算法精确配准后的点云数据结果图，可以看出，经过基于三个基准点进行初始配准后的点云数据的精确配准生成的效果图要比传统ICP算法的精度高。此模型的目的是为了对改进ICP算法作出进一步验证。

6. 总结与展望

6.1本文对测量点云数据的获取，数据特性以及获取方式进行了简要的说明，论述了点云数据的配准过程，提出一种改进点云配准算法，使得改进后的ICP的算法在点云配准方面比传统ICP算法具有更好的配准效果。并通过实验证明，改进后的ICP算法具有比原来传统的ICP算法更快的配准速度、更高的配准精度、以及更小的误差率，从而验证了配准效果和算法稳定性。

6.2但是由于本文的研究时间有限，并且资料方面存在这一些不足的地方，因此还存在的一些缺陷，要从根本上解决点云数据配准所存在的问题，还迫切需要更多、更深入的研究。

参考文献

[1]刘大杰，陶本藻.实用测量数据处理方法[M].北京：测绘出版社，2000：79～81.

[2]王霄，刘会霞，梁佳洪等.逆向工程技术及其应用[M].化学工业出版社，2009，30～32.

[3]李清泉，杨必胜，史文中等.三维空间数据的实时获取、建模与可视化[M].武汉大学出版社，2003，2～13.

[4]BeslP J， MckayN D. A method for registration of 3-d shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1992，14（2）： 239～256.

[5]ALTH，BRASS P，GODAU M，ETAL. Computing the Hausdorff distance of geometric patterns and shapes[J].Discrete and Computational Geometry，Special Issue-The Goodman-Pollack-Festschrift，2003.65～76.

[6]Rosen holm D，Torelegard K.Three-dimensional absolute orientation of stereo models using digital elevation models. Photo-grammetric Engineering and Remote Sensing， 1988， 54（10）：1385～1389.

[7]BlaisG，LevineM D.Registeringmultiview range data to create 3D computer graphics[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1995， 17（8）： 820～824.

[8]LI Q，Griffiths J G.Iterative closest geometric objects registration[J].Computers and Mathematics with Applications，2000，40（10）：1171～1188.

[9]张学昌，习俊通，严隽琪.基于点云数据的复杂型面数字化检测技术研究[J].计算机集成制造系统，2005，11（5）：727～731.

[10]Chen Y， Medioni G. Object modeling by registration of multiple range images[A]. In： Proceeding of the 1991 IEEE International Conference on Robotics and Automation [C]， Sacramento， CA，USA， 1991： 2724～2729.

[11]Rusinkiewicz S， Levoy M. Efficient variants of the ICP algorithm In 3D Digital Imaging and Modeling[C]. IEEE Computer Society Press，2001，145～152.

[12]Johnson A， E，Kang S B.Registration and Integration of Textured 3D Data[J].Image and Vision Computing，1999，17：135～147.

[13]戴静兰，陈志杨，叶修梓. ICP算法在点云配准中的应用[J].中国图像图形学报，2007，12（3）：517～521.

[14]张爱武，宋小鹏. 基于VTK的室外场景三维重建[D].首都师范大学，硕士学位论文，2006.5.15.

[文章编号]1619-2737（2014）01-03-267

[作者简介] 李艳芳，工作单位：武汉航道学校，职称：助理讲师，职务：航道工程教研室教师，研究方向：3“S”。

4.2三点几何坐标变换方法为：首先根据点云数据的曲率特征，给出三个主方向最贴近的点作为测量基准点，这三个测量基准点的第一次测量坐标表示为 P1、 P2和 P3，当进行第二次测量时，这三个基准点的坐标变换为q1 、q2 和 q3 ，则上面所描述的刚体变换就可以通过三个步骤来进行实现：

4.2.1首先将 P1变换为q1：

4.2.2然后在只考虑方向的情况下，将矢量 （p2-p1）变换为矢量（q2 -q1 ）。

4.2.3最后进行的变换是，将包含 P1、P2 和 P3这三个点的平面转换到包含三点q1 、q2 和 q3 的平面。

以上所述可以用算法表示为：

Step1： 做三个矢量 （p2-p1）、 （p3-p1） 、 （q2 -q1 ）与 （q3 -q1 ）之间的计算；

Step2： 设定两个值，令V1 =p2-p1，W1= q2 -q1；

Step3： 作矢量V3 与 W3

V3=V1×（p3-p1）

W3=W1×（q3-q1 ） （5）

Step4： 作矢量V2与 W2

V2=V3×V1

W2=W3×V2 （6）

很容易看出，上述三个矢量V1 、V2 与 V3可以构成右手正交系，而另外三个矢量W1 、 W2与W3 也同样可以构成右手正交系。

Step5： 作单位矢量

v1=V11|V1|， v2=V21|V2|， v3=V31|V3|

W1=W11|W1|， W2=W21|W2|， W3=W31|W3| （7）

Step6： 把系统 [v]中的任一点Pi 变换到系统[w] 中，这种变换可以表示为下列变换关系式：

P'i =Pi R+T （8）

Step7： 由于[v] 和 [w]都是单位矢量矩阵，因此可以表示出[w]=[v]R ，于是所求的关于[w] 系统的旋转矩阵就相应的可以表示为：

R=[v]-1 [w] （9）

Step8： 使 P'l=ql和Pl=pl ，把这两个方程代入上述式中，可以得到平移矩阵T ；

T=q1-p1 [v]-1 [w] （10）

Step9： 最后可以将方程改写为：

P'=P[v]-1 [w]- P1[v]-1 [w] +q1 （11）

下图2给出的是三点坐标变换示意图：

实验模型，点数：2513/3200如下图3是实验原始点云，图4是初始配准后的点云数据结果图，图5是改进ICP算法精确配准后的点云数据结果图，可以看出，经过基于三个基准点进行初始配准后的点云数据的精确配准生成的效果图要比传统ICP算法的精度高。此模型的目的是为了对改进ICP算法作出进一步验证。

6. 总结与展望

6.1本文对测量点云数据的获取，数据特性以及获取方式进行了简要的说明，论述了点云数据的配准过程，提出一种改进点云配准算法，使得改进后的ICP的算法在点云配准方面比传统ICP算法具有更好的配准效果。并通过实验证明，改进后的ICP算法具有比原来传统的ICP算法更快的配准速度、更高的配准精度、以及更小的误差率，从而验证了配准效果和算法稳定性。

6.2但是由于本文的研究时间有限，并且资料方面存在这一些不足的地方，因此还存在的一些缺陷，要从根本上解决点云数据配准所存在的问题，还迫切需要更多、更深入的研究。

参考文献

[1]刘大杰，陶本藻.实用测量数据处理方法[M].北京：测绘出版社，2000：79～81.

[2]王霄，刘会霞，梁佳洪等.逆向工程技术及其应用[M].化学工业出版社，2009，30～32.

[3]李清泉，杨必胜，史文中等.三维空间数据的实时获取、建模与可视化[M].武汉大学出版社，2003，2～13.

[4]BeslP J， MckayN D. A method for registration of 3-d shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1992，14（2）： 239～256.

[5]ALTH，BRASS P，GODAU M，ETAL. Computing the Hausdorff distance of geometric patterns and shapes[J].Discrete and Computational Geometry，Special Issue-The Goodman-Pollack-Festschrift，2003.65～76.

[6]Rosen holm D，Torelegard K.Three-dimensional absolute orientation of stereo models using digital elevation models. Photo-grammetric Engineering and Remote Sensing， 1988， 54（10）：1385～1389.

[7]BlaisG，LevineM D.Registeringmultiview range data to create 3D computer graphics[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1995， 17（8）： 820～824.

[8]LI Q，Griffiths J G.Iterative closest geometric objects registration[J].Computers and Mathematics with Applications，2000，40（10）：1171～1188.

[9]张学昌，习俊通，严隽琪.基于点云数据的复杂型面数字化检测技术研究[J].计算机集成制造系统，2005，11（5）：727～731.

[10]Chen Y， Medioni G. Object modeling by registration of multiple range images[A]. In： Proceeding of the 1991 IEEE International Conference on Robotics and Automation [C]， Sacramento， CA，USA， 1991： 2724～2729.

[11]Rusinkiewicz S， Levoy M. Efficient variants of the ICP algorithm In 3D Digital Imaging and Modeling[C]. IEEE Computer Society Press，2001，145～152.

[12]Johnson A， E，Kang S B.Registration and Integration of Textured 3D Data[J].Image and Vision Computing，1999，17：135～147.

[13]戴静兰，陈志杨，叶修梓. ICP算法在点云配准中的应用[J].中国图像图形学报，2007，12（3）：517～521.

[14]张爱武，宋小鹏. 基于VTK的室外场景三维重建[D].首都师范大学，硕士学位论文，2006.5.15.

[文章编号]1619-2737（2014）01-03-267

[作者简介] 李艳芳，工作单位：武汉航道学校，职称：助理讲师，职务：航道工程教研室教师，研究方向：3“S”。

4.2三点几何坐标变换方法为：首先根据点云数据的曲率特征，给出三个主方向最贴近的点作为测量基准点，这三个测量基准点的第一次测量坐标表示为 P1、 P2和 P3，当进行第二次测量时，这三个基准点的坐标变换为q1 、q2 和 q3 ，则上面所描述的刚体变换就可以通过三个步骤来进行实现：

4.2.1首先将 P1变换为q1：

4.2.2然后在只考虑方向的情况下，将矢量 （p2-p1）变换为矢量（q2 -q1 ）。

4.2.3最后进行的变换是，将包含 P1、P2 和 P3这三个点的平面转换到包含三点q1 、q2 和 q3 的平面。

以上所述可以用算法表示为：

Step1： 做三个矢量 （p2-p1）、 （p3-p1） 、 （q2 -q1 ）与 （q3 -q1 ）之间的计算；

Step2： 设定两个值，令V1 =p2-p1，W1= q2 -q1；

Step3： 作矢量V3 与 W3

V3=V1×（p3-p1）

W3=W1×（q3-q1 ） （5）

Step4： 作矢量V2与 W2

V2=V3×V1

W2=W3×V2 （6）

很容易看出，上述三个矢量V1 、V2 与 V3可以构成右手正交系，而另外三个矢量W1 、 W2与W3 也同样可以构成右手正交系。

Step5： 作单位矢量

v1=V11|V1|， v2=V21|V2|， v3=V31|V3|

W1=W11|W1|， W2=W21|W2|， W3=W31|W3| （7）

Step6： 把系统 [v]中的任一点Pi 变换到系统[w] 中，这种变换可以表示为下列变换关系式：

P'i =Pi R+T （8）

Step7： 由于[v] 和 [w]都是单位矢量矩阵，因此可以表示出[w]=[v]R ，于是所求的关于[w] 系统的旋转矩阵就相应的可以表示为：

R=[v]-1 [w] （9）

Step8： 使 P'l=ql和Pl=pl ，把这两个方程代入上述式中，可以得到平移矩阵T ；

T=q1-p1 [v]-1 [w] （10）

Step9： 最后可以将方程改写为：

P'=P[v]-1 [w]- P1[v]-1 [w] +q1 （11）

下图2给出的是三点坐标变换示意图：

实验模型，点数：2513/3200如下图3是实验原始点云，图4是初始配准后的点云数据结果图，图5是改进ICP算法精确配准后的点云数据结果图，可以看出，经过基于三个基准点进行初始配准后的点云数据的精确配准生成的效果图要比传统ICP算法的精度高。此模型的目的是为了对改进ICP算法作出进一步验证。

6. 总结与展望

6.1本文对测量点云数据的获取，数据特性以及获取方式进行了简要的说明，论述了点云数据的配准过程，提出一种改进点云配准算法，使得改进后的ICP的算法在点云配准方面比传统ICP算法具有更好的配准效果。并通过实验证明，改进后的ICP算法具有比原来传统的ICP算法更快的配准速度、更高的配准精度、以及更小的误差率，从而验证了配准效果和算法稳定性。

6.2但是由于本文的研究时间有限，并且资料方面存在这一些不足的地方，因此还存在的一些缺陷，要从根本上解决点云数据配准所存在的问题，还迫切需要更多、更深入的研究。

参考文献

[1]刘大杰，陶本藻.实用测量数据处理方法[M].北京：测绘出版社，2000：79～81.

[2]王霄，刘会霞，梁佳洪等.逆向工程技术及其应用[M].化学工业出版社，2009，30～32.

[3]李清泉，杨必胜，史文中等.三维空间数据的实时获取、建模与可视化[M].武汉大学出版社，2003，2～13.

[4]BeslP J， MckayN D. A method for registration of 3-d shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1992，14（2）： 239～256.

[5]ALTH，BRASS P，GODAU M，ETAL. Computing the Hausdorff distance of geometric patterns and shapes[J].Discrete and Computational Geometry，Special Issue-The Goodman-Pollack-Festschrift，2003.65～76.

[6]Rosen holm D，Torelegard K.Three-dimensional absolute orientation of stereo models using digital elevation models. Photo-grammetric Engineering and Remote Sensing， 1988， 54（10）：1385～1389.

[7]BlaisG，LevineM D.Registeringmultiview range data to create 3D computer graphics[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1995， 17（8）： 820～824.

[8]LI Q，Griffiths J G.Iterative closest geometric objects registration[J].Computers and Mathematics with Applications，2000，40（10）：1171～1188.

[9]张学昌，习俊通，严隽琪.基于点云数据的复杂型面数字化检测技术研究[J].计算机集成制造系统，2005，11（5）：727～731.

[10]Chen Y， Medioni G. Object modeling by registration of multiple range images[A]. In： Proceeding of the 1991 IEEE International Conference on Robotics and Automation [C]， Sacramento， CA，USA， 1991： 2724～2729.

[11]Rusinkiewicz S， Levoy M. Efficient variants of the ICP algorithm In 3D Digital Imaging and Modeling[C]. IEEE Computer Society Press，2001，145～152.

[12]Johnson A， E，Kang S B.Registration and Integration of Textured 3D Data[J].Image and Vision Computing，1999，17：135～147.

[13]戴静兰，陈志杨，叶修梓. ICP算法在点云配准中的应用[J].中国图像图形学报，2007，12（3）：517～521.

[14]张爱武，宋小鹏. 基于VTK的室外场景三维重建[D].首都师范大学，硕士学位论文，2006.5.15.

[文章编号]1619-2737（2014）01-03-267

[作者简介] 李艳芳，工作单位：武汉航道学校，职称：助理讲师，职务：航道工程教研室教师，研究方向：3“S”。