空间非合作目标的多视角点云配准算法研究

郭瑞科，王立，朱飞虎，吴云

北京控制工程研究所，北京 100190



空间非合作目标的多视角点云配准算法研究

郭瑞科，王立*，朱飞虎，吴云

北京控制工程研究所，北京 100190

为了提高相邻视角间稀疏扫描点云数据配准的速度和精度，实现多视角点云精确配准，提出一种基于KD-Tree点云均匀采样简化算法，并且对传统四点算法(4-Points Congruent Sets Algorithm, 4PCS)中的阈值参数进行了统一，确定了各误差阈值参数和点云密度之间的关系，通过基于姿态校正的方法有效解决了对称视角点云引起的误配准问题。仿真结果表明，该方法能够快速、有效地实现卫星稀疏点云的配准。

非合作目标；多视角；点云数据；配准；四点算法

空间非合作目标的在轨服务技术可实现对目标航天器的在轨维护、空间垃圾碎片清理、抓捕或破坏敌方军事卫星等，具有很高的民用意义和军事价值。在这些在轨服务任务中，服务航天器在跟踪、接近和抓捕目标时，需要实现航天器和目标间的相对位置和姿态测量。相比较于传统的合作目标，非合作目标上没有光标线或者角反射器等配合标志，无法提供显著、可靠的参考信息，这就给非合作航天器的准确位姿测量带来了极大的挑战。特别是对于完全未知的空间目标，需要首先在轨建立三维模型，然后利用所重构的三维模型实现六自由度位姿估计和特征识别。因而如何对未知目标进行三维重构，便成为了非合作在轨服务的一项关键技术。

激光扫描敏感器通过获取目标表面的点云数据，得到目标三维模型，具有精度高、不受光照影响的优点。由于敏感器视场角的限制，要得到目标完整的三维模型，需要从多个视角对目标进行扫描，将不同视角得到的点云数据配准到同一坐标系下，因而需要研究多视角点云的配准。点云配准一般包括全局配准和精确配准两个步骤，全局配准缩小两片点云之间的旋转和平移错位，为精确配准提供比较好的初值。对于多视角点云数据的配准，某些视角需要多次旋转平移才能配准到统一坐标系下，实现整体配准，进而重构出目标点云模型。

Wolfson等[1]提出的几何哈希算法，可以用于点云数据的全局配准，但是需要建立哈希表，占用内存空间比较大，不适合空间应用。Rusu等[2]提出的FPFH基于局部几何特征的全局配准方法，计算速度快，但是依赖点云的邻域特征，导致稀疏点云数据估计曲率等特征误差较大。Guo等[3]提出一种外形生长的多视角点云配准算法，选择一个种子外形，迭代地进行两两点云配准，进而实现模型重构，该算法过于依赖两两配准的精度，运算量较大。

本文针对空间目标需要内存占用小、宜使用稀疏点云进行配准的特点，采用基于改进四点算法的全局配准方法，具有速度快的优点，可以得到满足精度的全局配准结果。将全局配准的结果作为精确配准的初值，保证收敛精度的同时，提高配准的效率。通过引入航天器姿态连续变化的约束条件，可以有效处理对称视角点云误配准的问题,使用连续变换的方法实现多视角点云的配准。

1　点云数据的简化

激光扫描敏感器的测量精度高，尤其是在近距离扫描时，采用高效的李萨茹扫描方式(图1)，获取的单幅扫描数据点数多达数万到数十万。这样大的数据量对于星载计算机有限的存储空间和计算能力带来了比较大的挑战。从图1可以看到边缘点云密度高于中间部分，而且点云都集中在扫描线上，因而并不是所有的点都可用于配准。其中冗余的点云数据如果都参与配准，不仅会降低计算速度，增加内存使用，而且点越多，越难从中找到符合特征的点对，影响配准的精度。

图1　李萨茹扫描方式Fig.1　Lissajous scan pattern

为了解决上述问题，必须对测量的点云数据进行精简，以提高计算速度，减少存储空间，提高配准精度等。考虑到所处理的对象为卫星点云，在空间模型重建中对时效性要求较高，本文提出一种基于KD-Tree点云均匀采样算法对点云数据进行精简。

KD-Tree是三维数据中常用的一种数据格式，可以快速实现K最近邻域的搜索[4]。在基于KD-Tree点云均匀采样算法中，首先利用KD-Tree对点云数据建立空间拓扑结构，搜索点集中每个点的K最近邻域，计算该点与K个最近邻点的重心，用该重心代替这点，最后对所得到的点集均匀采样，可以得到简化的稀疏点云。

图2是从一个视角扫描得到的单幅原始卫星模型点云，包含10 171个数据点，采用上述简化算法，K取4，采样率设置为7%。图3是简化后的点云，数据点数为710，可以看到数据得到精简，卫星模型的特征也可以比较好地保留。

图2　原始点云Fig.2　Original point cloud

图3　简化后的点云Fig.3　Simplified point cloud

2　基于改进四点算法的全局配准　 算法

对于两片三维点云的配准，至少需要从各自点云中选取对应不共线的三点，才能计算出二者的刚体变换矩阵。若待配准两片点云P(Data数据集)、Q(Model数据集)分别有m、n个点，在P、Q中选取对应的三点计算旋转平移矩阵，时间复杂度可达O(m3n3)。Irani等[5]采用基于随机采样一致性(Random Sample Consensus，RANSAC)的方法配准，可以降低复杂度到O(n3lg n)，然而对于空间应用，时间复杂度还是太高。考虑在P点云中选取更多的共面点(5个或者以上)，则在Q点云中能成功选择到正确的对应点集的概率急剧降低，难以实现配准[6]。

四点算法(4-Points Congruent Sets Algorithm，4PCS)是Aiger等[7]于2008年提出的一种基于RANSAC法则的全局配准算法，可成功用于三维点云数据的配准，时间复杂度只有O(n2)。本文针对原始四点算法中阈值参数比较多的情况，通过点云密度对阈值参数进行了统一，简化了多视角点云配准时的阈值参数设置；针对该算法处理对称点云时成功率低的问题，提出了基于姿态连续变化来校正对称引起误配准的方法，有效提高了点云配准的成功率。

2.1四点算法

四点算法在每次的迭代中，在P数据集中随机寻找不在同一条直线上的共面4点，根据共面4点的两条对角线交点将线段所分的比例r1、r2在刚体变换中的不变性(见图4)，在Q数据集中选取对应的共面4点(见图5)，这两对共面4点组成一致共面4点集，利用该一致共面4点集可以计算出旋转矩阵R和平移矩阵T。4点算法不需要计算复杂的几何特征，速度快，对噪声具有比较高的鲁棒性。

图4　P中所选的共面4点[7]Fig.4　Four (approximately) coplanar points extracted formP

图5　Q中对应的共面一致4点Fig.5　Affine invariant congruent 4 points extracted formQ

四点算法中，Q点集中候选点对可以用共面4点长度来筛选：

(1)

式中：δ1为寻找近似长度相等线段a′b′与ab的误差阈值。根据不变量r1、r2可以确定可能的交点e′：

(2)

式中： q1、q2是从点集Q找到的长度符合线段对应的候选共面4点。近似相等交点所对应的点对即组成Q点集中的共面一致4点。利用点集(a,b,c,d)和(a′,b′,c′,d′)可以计算对应的欧氏变换矩阵，用所得到的欧氏变换矩阵作用与点集P，验证在一定阀值下，P点集中成功配准到Q点集的点数目，即一致性度量。

2.2四点算法的阈值参数设置方法

文中所配准的点云数据是从完全非合作目标扫描所得到的，全局配准中没有点云数据的先验知识，同时四点算法中涉及的误差阈值参数众多，这给算法中的阈值参数设置带来了挑战。在轨模型重建中需要多次点云配准，每次配准的两幅点云特征都有所差别，如果分别设定这些阈值参数，可能会费时费力，甚至会导致不能成功配准。

点云数据密度是稀疏点云的关键几何特征，待配准点云的密度τ，本文通过计算点云中所有点K最近邻域距离的平均值来确定，该值越小，表示点云密度越大，反之则越小。一般三维散乱点云的最近邻域点数可设置为6，即前后左右上下6个方向，这样可以比较好地保持点云的三维特征，准确确定它的局部几何特征。本文中待配准的点云是经过简化的卫星点云，卫星太阳翼和本体部分以平面特征为主，因而最近邻域点数设置为4，即只选取沿平面方向的4个点，能比较好地保留卫星点云特征，准确估计点云数据密度。本文通过确定点云密度与各误差阈值参数的关系，对误差阈值参数进行了统一。

上述四点算法中涉及的参数有：在Q点集中筛选候选对应点对时的误差阈值δ1；选取近似相等交点时的误差阈值，‖e1-e2‖<δ2；一致性度量时的距离误差阈值δ3。

本文通过仿真试验确定了各误差阈值δi与点云密度τ之间的关系，有效提高了配准算法的稳定性和自动化程度：

(3)

2.3对称视角的校正

对于卫星等对称性比较高的航天器，某些视角的点云是对称的，配准时会出现沿某个本体轴翻转180°的情况，这就为正确配准带来了挑战。考虑到相邻视角的点云姿态变换角度不会太大，根据配准得到的旋转矩阵可以计算出相邻视角点云间的相对姿态，对于姿态角过大的情况进行识别、校正，就可以有效解决对称情况下配准偏差的问题。

多视角点云配准中，每对相邻视角点云之间都存在旋转矩阵R，据此可以定义P数据集所在视角测量坐标系相对Q数据集所在视角测量坐标系的姿态。常用的姿态描述方式有欧拉轴/角式，有4个参数，转轴的单位矢量在参考坐标系中的3个方向余弦ex、ey、ez及绕此轴的转角Φ；欧拉角式，采用3-1-2旋转顺序，转角分别是ψ、φ、θ。上述姿态参数与旋转矩阵存在如下关系[7]：

(4)

(5)

设Vo、Vb分别是矢量V在观测坐标系和本体坐标系的值，存在转换矩阵R，绕x轴的基元旋转记为Rx，误配准的旋转矩阵记为Rw。Vo=RVb，

(6)

对绕本体x轴翻转180°的误配准情况，有Vo=R·Rx(π)·Vb，因而Rw=R·Rx(π)，其中

可以得到误配准的姿态角，ψw=-ψ，φw=φ，θw=θ，即姿态角只有符号变化，绝对值大小没有变化，对于绕y轴或者z轴的翻转有类似的结果，这个特点可以用到校正中。

设校正后的欧拉轴/角参数是exc、eyc、ezc、Φc，旋转矩阵是Rcorrection，σ是角度阈值，误配校正算法如下：

1)判断欧拉转角是否大于阈值，如果Φ>σ则需校正，执行下一步；

3)找到最大的三轴欧拉角对应的旋转轴，记为k，令ekc=ek；

4)找到最小的三轴欧拉角对应的旋转轴，记为j，令ejc=ej；第三个转轴eic=ei；

6)使用校正的旋转矩阵Rcorrection更新点云数据，作为精确配准的初值。

3　基于ICP算法的精确配准算法

Besl和McKay于1992年提出了点到点的迭代最近点(Iterated Closest Points，ICP)算法，ICP算法是在两个点集中搜索最近的点对，以这些最近点对作为控制点来估算旋转变换矩阵和平移变换矩阵，并将这个坐标变换作用到待配准点集上，迭代进行这一操作过程，直到正确匹配[9]。

由于待配准的两幅点云只有部分区域是重合的，在搜索最近点对的时候，不可避免地会存在错误的匹配点对。为了消除这些错误匹配点对对精确配准结果的影响，需要剔除这些错误匹配点对。点云数据密度是稀疏点云的关键几何特征，全局配准时已经估计过点云的密度。对于部分重叠的两片点云，只有使用重叠区域的最近点对，才能准确计算出两者之间的变换矩阵，而非重叠区域的最近点对距离偏大。本文采取距离阈值的方法来剔除错误匹配点对，即认为搜索的最近点距离大于点云密度一定倍数的点对为错误匹配点对。

4　多视角点云的配准

分析多个视角点云的配准方法：直接将相邻两个视角点云依次配准，每次配准后都去除重叠部分，合并成一幅点云，直到配准到最后一个视角,见图6。经过实际配准试验发现，随着已配准点云幅数的增加，合并起来的视角所组成的点云数目增大，重叠率降低，配准精度并没有提高，反而难以配准，花费时间过大。

图6　多视角扫描Fig.6　Multiple-view scan

考虑这样的方法：每次都只配准相邻的两个视角，再用所得到的变换矩阵计算得到最终的配准结果。具体说明如下：

1)假设试验相邻视角相差45°，共有8幅点云需配准成完整的点云模型，分别是0°、45°、90°、135°、180°、225°、270°、315°视角下的点云数据，最终所有视角点云都配准到0°视角。

2)记315°视角点云配准到270°视角下的变换矩阵为R1、T1，270°视角点云配准到225°视角下的变换矩阵为R2、T2，依次类推，45°配准到0°的变换矩阵为R7、T7。记315°、270°、225°、45°、0°视角下的点云数据分别为X315、X270、X225、X45、X0，有X270=R1X315+T1，X225=R2X270+T2，…，X0=R7X45+T7，即45°视角点云经过一次变换R7、T7，就可以变换到0°视角；

3)315°视角的点云变换到0°视角可以由下式计算得到:

(7)

其他视角点云变换到0°视角由类似的公式可以得到。

所有视角点云都统一到0°视角之后，采用文献[10]中的平差方法，降低整体误差，再合并重合部分的点云，就可以得到完整的点云模型。

5　试验仿真

本文仿真试验使用某卫星仿真点云数据，点云相邻视角间隔分为45°数据为0°、45°、90°、135°、180°、225°、270°、315°这8个视角下的点云。不同视角下的点云数目有所变化，测试算法的有效性和鲁棒性。在主频为3.20 GHz，内存为4 GB，WINXP操作系统的PC机上，以7.8.0版本的Matlab为平台进行算法仿真。配准误差定义为均方根误差(Root Mean Square Error，RMSE)：

(8)

式中：N为两块待配准点云重叠部分点数目；pi、qj分别为点云中重叠区域的点。

5.1相邻视角的配准效果

对于相邻视角点云的配准，选取90°和45°视角下的点云数据，分别作为Model点云和Data点云，相应的数据点数1 136、1 204。

图7(b)所示为粗配准的点云，蓝色为Model点云，红色为Data点云，二者有部分重叠区域。可以看到两幅点云基本配准，沿滚转轴方向仍有偏差，配准误差为0.138 9。为了近一步提高点云配准精度，使用改进的ICP算法进行优化，可以看到两片点云已经重合，配准误差降低到0.093 8。

图7　90°视角点云配准向45°视角结果Fig.7　Pair-wise registration result

5.2对称视角配准的校正

本体点云对称，误配准如图8(b)所示，Data点云绕本体轴旋转了180°，采用算法校正之后，可以得到图8(c)所示的正确配准结果。

对所有两两相邻视角点云进行配准，图9所示为未采用校正算法和采用校正算法后，配准成功率的比较，可以看到有对称视角点云(45°和225°视角点云)的配准成功率均有明显提高，整体成功率平均提高31.52%。

图8　对称点云误配准的校正Fig.8　Mis-registration correction of symmetry point cloud

图9　各视角的配准成功率Fig.9　Success rate of adjacent point cloud registration

5.3噪声对配准误差的影响

对上述90°和45°视角下的点云数据添加均值为零、方差变化的高斯噪声，验证算法在噪声影响下的有效性，如图10所示。可以看到经改进的四点算法在噪声标准差小于0.15 m时能保证配准误差小于0.14 m，且整体精度优于原4PCS算法。然而在噪声过大(超过0.15 m)时，两种算法配准误差都变大。

图10　噪声对配准误差的影响Fig.10　RMSE under variable noise

5.4整体配准结果

尝试对多个相邻视角进行了配准，无噪声情况下，从图11可以看到文中改进的配准算法精度都高于4PCS算法。不同相邻视角误差有所变化，是因为不同相邻视角的点云密度有所不同，都在比较小的区域里面波动。

将所有视角点云统一到同一个视角中，由于相邻视角点云存在重叠部分，这样直接得到的点云模型存在大量重叠部分。需要合并重叠部分，才能用于后续的曲面重建等处理。对比图12和图13，可以看到点云数目从11 060降低到3 532，点云得到了简化，同时模型的特征也较好地保存下来。

图11　相邻视角的配准误差Fig.11　RMSE of adjacent point cloud registration

图12　统一到同一坐标系下，未去除重叠部分Fig.12　Multiple-view point cloud in a global coordinate system with overlap section

图13　去除重叠部分点云Fig.13　Removing the point cloud of overlap section

6　结束语

两幅点云的配准是多幅点云配准的基础和关键。针对空间非合作目标，点云的配准算法要兼顾精确性、快速性和内存占用大小等因素。本文针对卫星扫描点云数据，提出基于KD-Tree点云均匀采样简化算法，在保持卫星特征的情况下较好地实现了点云简化。对于卫星稀疏点云数据，使用基于改进四点算法进行全局配准，将全局配准结果作为精确ICP配准的初值，实现了点云数据的配准。对于四点算法中误差阈值参数多的情况，给出了误差阈值参数与点云数据密度之间的关系，有效提高算法的稳定性。提出根据卫星姿态变化的连续性，解决卫星点云中存在对称视角导致误配的问题。对多视角点云进行了配准，实现了卫星点云模型重构。

References)

[1]WOLFSON H, RIGOUTSOS I. Geometric hashing: an overview[J]. IEEE Computer Science and Engineering, 1997, 4(4):10-21.

[2]RUSU R B. Fast point feature histograms (FPFH) for 3D registration[C]∥Robotics and Automation, 2009.ICRA 09.IEEE International Conference, Kobe, May 12-17, 2009:3212-3217.

[3]GUO Y L, SOHEL F, BENNAMOUN M. An accurate and robust range image registration algorithm for 3D object modeling[J]. IEEE Transactions on Multimedia, 2014, 16(5): 1377-1390.

[4]BENTLEY J L. Multidimensional binary search trees used for associative searching[J]. Communications of the ACM, 1975, 18(9): 509-517.

[5]IRANI S, RAGHAVAN P. Combinatorial and experimental results for randomized point matching algorithms[J]. Computational Geometry, 1999, 12(1-2): 17-31.

[6]YAO L,RUGGERI,TADDEI P, et al. Robust surface registration usingN-points approximate congruent sets[J]. EURASIP Journal on Advances in Signal Processing, 2011(1): 72.

[7]AIGER D, NILOY M J. 4-Points congruent sets for robust pairwise surface registration[J].ACM Transactions on Graphics (TOG), 2008, 27(3): 85-94.

[8]吕振铎, 雷拥军. 卫星姿态测量与确定[M]. 北京: 国防工业出版社, 2013: 30-35.

[9]BESL P J, MCKAY N D. A method for registration of 3D shape[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.

[10]李彩林, 郭宝云, 季铮. 多视角三维激光点云全局优化整体配准算法[J]. 测绘学报, 2015, 44(2): 183-189.

LI C L, GUO B Y, JI Z. Global optimization and whole registration algorithm of multi-view 3D laser point cloud[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(2): 183-189(in Chinese).

(编辑：高珍)

Research on registration algorithm of multiple-view point cloud for non-cooperative spacecraft

GUO Ruike, WANG Li*, ZHU Feihu, WU Yun

Beijing Institute of Control Engineering, Beijing 100190, China

The point cloud data registration is one of the key technical aspects of three-dimensional reconstruction for non-cooperative spacecraft. To solve the pair-wise registration issue of sparse point cloud, and align the multiple-view point cloud accurately,an optimization registration method was presented. A novel point cloud simplification algorithm using uniform sampling was proposed based on KD-Tree and the uniform relation of the threshold parameters in the 4PCS(4-Points Congruent Sets) algorithm was established via the density of the point cloud. By using the mis-registration correction method based on attitude,the mis-registration problem of the symmetry point cloud was solved.The results show that the proposed algorithm can effectively achieve good alignments of the sparse point cloud of the satellite, besides, the stability and the success rate of the algorithm is also improved.

non-cooperative spacecraft; multiple-view;point cloud data; registration;4-points congruent sets

10.16708/j.cnki.1000-758X.2016.0055

2016-03-28；

2016-05-20；录用日期：2016-08-22；

时间：2016-09-2113:41:18

http:∥www.cnki.net/kcms/detail/11.1859.V.20160921.1341.003.html

国家重点基础研究发展计划(973)(2013CB733100)

郭瑞科(1989-)，男，硕士研究生，ruikeguo@163.com,研究方向为空间图像处理

王立(1977-)，男，研究员，bheart@263.net，研究方向为空间图像处理、模式识别以及视觉导航

V391.41

A

http:∥zgkj.cast.cn

引用格式：郭瑞科,王立,朱飞虎,等. 空间非合作目标的多视角点云配准算法研究[J].中国空间科学技术, 2016,36(5)：

32-39.GUORK,WANGL,ZHUFH,etal.Researchonregistrationalgorithmofmultiple-viewpointcloudfornon-cooperativespacecraft[J].ChineseSpaceScienceandTechnology, 2016,36(5)：32-39(inChinese).