一种改进RANSAC校验的失效卫星位姿估计回环检测方法

程向红，李丹若，曹 毅，牟金震

（1.微惯性仪表与先进导航技术教育部重点实验室，南京 210096；2.东南大学 仪器科学与工程学院，南京 210096；3.上海市空间智能控制技术重点实验室 上海 201109）

如何实现失效卫星的修理或清除，是目前空间技术发展的重要方向。空间卫星在长期失效后，由于能量的不断耗散，通常围绕最大惯性主轴进行缓慢的自旋运动[1]。服务航天器需识别失效卫星并估计其位姿，为后续的抓捕或清除提供条件。视觉传感器具有体积小，低功耗，可靠性高等优点，十分适合空间在轨服务的应用场景[2]。视觉SLAM（Simultaneous Localization and Mapping）技术作为一种解决未知运动目标相对位姿测量的有效手段，时常被国内外研究者迁移用于解决空间失效卫星位姿估计问题[3]。而在SLAM求解位姿的过程中，长时间连续观测会带来累积误差增大、位姿解算不收敛等难题。回环检测是消除累积误差的有效手段，是失效卫星位姿估计问题的热点与难点。同时，利用回环检测粗略求得失效卫星的自旋角速度，对后续的接近或抓捕十分重要[4]。

基于词袋模型（Bag of word,BoW）的回环检测算法是失效卫星回环检测的主流[5]。该方法通过预训练好的词典库生成图像的词袋向量，计算向量相似度来完成回环检测[6]。但是，该算法的性能严重依赖于预训练提取生成的词典库，对空间复杂多变的场景适应性差。

随着深度学习技术在图像上的广泛应用，基于深度学习的回环检测成为当前的研究热点。2015年X Zhang等人利用预先训练的CNN模型提取高质量图像特征用于回环检测[7]。深度学习提取出的全局特征虽具有良好的不变性，但其计算量大等缺陷也十分明显。Shahbazi等人则将局部敏感哈希图像检索算法迁移至回环检测中，快速对比图像的相似性，获得回环检测结果[8]。清华大学的Gao等人则提出一种轻量级地实时快速深度学习架构，利用较少的参数实现系统资源的高利用率，实现深度学习端对端检测[9]。尽管如此，此类方法应用至失效卫星中依旧存在较多误检测。原因是：失效卫星绕惯量主轴做自旋运动。部分失效卫星的受观测面相似度较高。在卫星周期性旋转进出视场时，深度学习提取的全局特征会因忽略局部空间关系导致算法精度不高。

RANSAC算法常用于图像匹配。只是该算法通过迭代求解最优模型，精度虽高，但应用在空间失效卫星中，仍有许多不足。

综上所述，本文针对空间失效卫星的特殊应用场景，提出一种基于改进RANSAC（Random Sample Consensus）校验的失效卫星回环检测方法，使用深度学习提取全局和局部特征，引入改进的RANSAC算法进行回环候选帧校验，从而提高回环检测在空间场景光照变化时的稳定性。

1 回环检测方法设计

传统回环检测方法往往遵循这一模式：提取图像特征并描述，进行相似图像检索并提速，完成回环帧输出。面对失效卫星特殊的应用环境，本文设计方法流程如图1所示。与传统流程不同的是，本文在方法最后增添了改进RANSAC图像匹配校验这一步。

图1 算法流程Fig.1 Algorithm flow chart

本文使用HF-Net（Hierarchical Feature Network）多任务网络，直接输出图像的3种特征：关键点，局部特征，全局特征[10]。

随后，使用HF-Net输出的全局特征进行图像相似度对比。全局特征的特征维数高，直接对比计算量大，算法的运行效率低下。针对这一问题，本文借鉴图像检索领域的HNSW（Hierarchical Navigable Small World）算法，快速进行图像对比，记录高相似性图像的索引，建立图像回环帧候选集合[11]。

失效卫星回环检测的应用场景复杂多变。仅比较全局特征，无法满足回环检测的精度要求。而局部特征虽对环境变化敏感，却具有良好的区分性。因此，使用图像局部特征，完成对当前帧与候选帧集合的图像匹配校验，匹配程度最高的则为回环帧。

标准RANSAC算法采用随机选点法，在选点计算最优模型时，会不断计算出效果较差的模型并抛弃。若特征点质量较差，则会产生大量无效模型，造成模型浪费和计算资源的无端消耗。因此，本文对RANSAC算法进行改进，缩减RANSAC运行时间，获取较为准确的图像回环检测结果。改进RANSAC算法成功应用在失效卫星回环检测中，提升了回环检测的效果。

2 回环候选帧检索

2.1 HNSW算法

在检索领域中，近邻图是最朴素的图算法，它由简单的顶点和边构建。最基础的近邻图技术需从随机某点出发，计算当前点的友节点与目标点的距离，跳入距目标点最近的友节点再次出发。如此反复迭代，不断逼近。NSW（Navigable Small World）算法则对近邻图技术进行了优化。近邻图技术最重要的缺点在于，随机选择的出发点若是与目标点距离很远，则会迭代多次，浪费时间。为此，NSW算法增加了高速公路机制。即在初始构图过程，查找到距离新点最近的点，连接新点到这些点。

HNSW算法是在NSW算法的基础上，结合跳表提出的。跳表是用于有序元素序列快速搜索查找的一个数据结构，实质就是一种可以进行二分查找的有序链表。如图2所示，在跳表的查询过程中，先查最高层，后查次高层，如此递推直至第一层确定结果。如此操作可以有效缩减时间复杂度。

图2 跳表结构示意图Fig.2 Skip List structure diagram

跳表思想融入进NSW算法，即为层状结构的HNSW算法。该算法贪婪地遍历来自上层的元素，直到达到局部最小值。之后，切换到较低层，从上层最小值对应的低层元素重新开始遍历。该过程在每一层中重复。这一结构显著降低了计算复杂度。

2.2 回环候选帧集合

HF-Net提取当前图像的全局特征后，在HNSW图内展开快速检索，使用余弦距离，比较当前特征和临近特征的相似度。随即将当前全局特征插入进HNSW图中，重新构图。最后，记录较高相似度图像的图像索引，称为回环候选帧集合。

3 回环候选帧校验

3.1 基于网格运动统计的打分器

3.2 改进RANSAC算法

传统RANSAC算法进行图像匹配时，首先，从样本点集中随机采样多于4个特征点，估计两张图像的单应矩阵模型参数；其次，根据模型计算内点的数目；重复以上步骤，确定最终的图像匹配特征点。

以上分析可知，RANSAC 算法迭代次数多，计算时间长。因此，应用一种结合网格打分器的优化RANSAC算法。针对RANSAC随机选点导致迭代次数多的问题，首先，将图像进行网格化。利用网格支持度对网格打分。根据失效卫星数据特点，剔除图像边界的特征点；根据网格打分器，剔除分数较低的网格。利用RANSAC算法，从保留下来的匹配中抽取优质特征点作为样本点，再对样本点进行迭代计算，最终求得图像的单应矩阵及对应匹配点。

3.3 确定回环帧

在本文回环检测算法的校验过程中，当前图像分别与每一个回环候选帧进行匹配，首先使用运行速度较快的网格打分器进行筛选。若剔除劣质点后剩余点不足初始点数的0.1倍，直接停止匹配校验，回环权重置0，从而防止后续RANSAC计算浪费计算资源。若剩余点符合条件，则继续利用RANSAC进行计算。最后，计算正确匹配对数占据初始点数的百分比，即回环权重。权重最高的图像帧即为当前图像的最优回环帧。

4 实验与结果

本文进行仿真实验如下：首先，在失效卫星图像上，对比了RANSAC算法以及改进的RANSAC算法的正确率与耗时。其次，在牛津公开数据集上，通过与缺乏改进RANSAC校验的算法对比，说明改进RANSAC校验在回环检测中的有效性；最后，在失效卫星数据集上，验证所提方法对光照变化的空间场景具有高适应性与稳定性。

4.1 图像匹配校验算法仿真结果

HF-Net利用SuperPoint提取特征点。首先，将SuperPoint与流行的ORB算法进行对比。对同一张失效卫星图像提取500个特征点时，SuperPoint耗时110.8 ms，ORB耗时66.5 ms，效率远低于ORB。但SuperPoint算法在极端光照条件下的稳定性远超ORB算法。具体如图3所示。图3(a)为特征点提取示意图，右侧SuperPoint算法能够提取更均匀的特征点；图3(b)为ORB匹配结果，图3(c)为SuperPoint匹配结果，SuperPiont的匹配结果更准确。

图3 ORB与SuperPiont对比Fig.3 Comparison of ORB and SuperPoint

为验证改进RANSAC的性能，抽选三组失效卫星图像，每组包含4张图片。三组图像代表失效卫星应用中可能存在的不同场景或变化：（1）弱纹理的卫星模型；（2）光照变化；（3）旋转变化。对三组图像分别提取500特征点后进行暴力匹配。而后分别使用RANSAC算法和改进算法剔除误匹配。具体实验方法为：将每组图像中的第一帧图像作为标准图像，将其后三帧分别与标准图像进行暴力匹配，而后利用算法剔除误匹配，计算算法剔除后的匹配正确率和算法耗时。本文实验采用的电脑处理器型号为i7-11700KF，操作系统为Ubuntu 18.04。

各算法正确率以及平均时间消耗如表1所示。表格中的耗时不包括特征提取与暴力匹配所耗时间，计算五次取平均值。由表中结果可以看出，在弱纹理的失效卫星场景中，改进算法的匹配正确率略高于RANSAC算法，耗时稍有减少。

表1 失效卫星图像的算法匹配结果Tab.1 Image matching results for failure satellites

而面对光照变化时，改进算法与RANSAC算法的正确率都明显下降，两个算法的耗时差距明显。原因在于，弱光照环境下暴力匹配获取的匹配点对质量较差。在改进算法中对质量较差的点进行了快速筛选，留给后续RANSAC随机抽样的点对量少且更优质，能够较快结束迭代；而传统RANSAC则需不断迭代剔除质量差的匹配点。由此可见，匹配点的质量对RANSAC算法的耗时影响很大，匹配点质量好时，RANSAC算法只是耗时略长；质量差时，两算法耗时则有明显差距。本特征提取与匹配实验中，改进算法匹配耗时比RANSAC平均减少约6.58 ms，可以使回环检测更高效。

4.2 牛津公开数据集回环检测实验结果

为验证本文回环算法对不同场景具有高适应性，首先使用牛津数据集进行算法验证。该数据集包括两个场景，New College和City Center，以及相应的真值文件。数据集的每个场景又可分为左右相机拍摄而成的两组。为了方便表述，将New College场景分割成New College-Left与New College-Right；同理，将City Center场景分割成City Center-Left与City Center-Right。如图4为四个数据集示例图片，依次为New College-Left、New College-Right、City Center-Left、City Center-Right。

图4 牛津数据集图片Fig.4 The Oxford dataset images

回环检测算法使用准确率P和召回率R对检测结果进行评价。准确率P代表算法判断出的所有回环中正确回环所占的比例，召回率R则代表算法检测出的正确回环数与所有正确回环数的比值。以此作为回环检测的评价指标，将所提方法与BoW算法和HF-Net算法进行对比。BoW算法通过最新版的DBoW3库进行实现。使用HF-Net算法代指所提方法去掉校验时的回环算法，以此来验证回环候选帧校验的有效性。三种算法在四个数据集上的Precision-Recall曲线如图5所示。

图5 牛津数据集回环实验结果对比Fig.5 Results of experiments on the Oxford dataset

准确率是回环检测最看重的指标。三种算法在四个数据集上100%准确率下的最大召回率如表2所示，其中，所提方法表现均为最优，与HF-Net相比，局部特征的加入使得算法性能提升良好。BoW算法需随场景变化更新词典库，且在实际工程使用时，常伴随图像增强等针对性操作。因此在本实验中，BoW算法表现一般。

表2 100%准确率下的最大召回率（单位：%）Tab.2 Maximum recall at 100% precision（Unit:%）

联系数据集进行分析。如图4所示，New College-Right中光照变化剧烈；City Center处于白天，City Center-Right中因阳光过于剧烈出现少数“镜头光晕”的现象。在此类场景下，基于深度学习提取特征的优势，HF-Net算法100%准确率下的召回率均超过BoW算法。但在总体上，HF-Net算法精度不及所提方法，甚至在New College-Left上远不及BoW算法。原因即是深度学习全局特征缺乏对局部空间位置关系的敏感，而New College-Left中存在大量不同位置的相似图片，算法极易发生误检。由此可知，深度学习全局特征搭配局部特征图像校验是很有必要的。

4.3 空间失效卫星数据集回环检测实验结果

利用不同的卫星模型与复杂的照射光源模拟空间环境，制作失效卫星数据集，如图6所示。该数据集可分为四个子数据集，分别为：卫星模型A以5 °/s角速度匀速旋转；卫星模型A以10 °/s的角速度匀速旋转；卫星模型A以20 °/s的角速度匀速旋转；卫星模型B以10 °/s角速度旋转。

图6 数据集图片 Fig.6 Dataset images

因失效卫星稳定自旋，使用失效卫星旋转周数来评价回环检测的效果，具体方法如下：对每一个子数据集，统计在失效卫星最后一周的旋转中，平均每帧图像应检测到的回环帧数目，以及所提方法与BoW算法平均检测到的回环帧数目。实验将检测结果的准确性放在首位，尽可能减少错检误检，结果如表3所示。

表3 失效卫星数据集回环检测结果Tab.3 Results of the failure satellites dataset

BoW需利用预训练的词典库获取词袋向量。预训练的图像数据场景越多，词典库越丰富，BoW效果越好。针对失效卫星的应用场景，本实验利用1000张失效卫星模型图片（其中基于卫星模型A的图片占比90%），有针对性地训练了BoW词典库，生成了相应的词典压缩文件。利用BoW进行回环检测时，需提前加载该文件。实验分析可知，BoW算法随模型角速度的增加效果变差。此类图像中普遍存在运动模糊与强反光情况，导致提取的特征点质量较差。而BoW算法对模型A 10 °/s数据集的检测结果要比模型B略好，也进一步说明了BoW对预训练词典库的依赖。

所提方法在无预训练的条件下取得较好的检测结果。在处理卫星模型A的20 °/s数据集时，进行五次实验取平均值得到结果：所提方法对单独图像帧进行检索对比的平均时间48.8 ms，完成全部回环检测的时间则为192.6 s（包括SuperPoint特征提取）。BoW算法则为143.9 ms和253.8 s（包括ORB特征提取，不包括词典库预训练）。所提方法在准确的同时兼顾了处理速度，和BoW算法相比缩减时间24.1%左右。

利用所提方法粗略计算数据集角速度，说明所提方法的准确性。具体方法为：对某一图像Ip，与Ip相近却不相邻的图像Il，两帧的时间戳分别为tp，tl。若图像Ip与Il的回环权重高于自主设定的阈值，则可计算该段角速度w=360/(tp-tl)。由此，针对以上五个失效卫星数据集，在每个数据集的后半部分，随机抽取五张图像。记录每张图像的时间戳tp；在每张图像的回环候选帧集合中，挑选合适的图像，记录时间戳tl，代入公式求解角速度。计算五张图像的结果并求取平均值，可获得五个失效卫星数据集的角速度。本文所提方法求解为：5.04 °/s、8.05 °/s、10.02 °/s、12.04 °/s和20.09 °/s。

5 结论

本文提出了一种基于改进RANSAC校验的空间失效卫星回环检测方法。实验结果表明：1）回环候选帧校验在回环检测中很有必要，且改进算法耗时比RANSAC算法平均减少6.58 ms；2）在牛津数据集上，本方法与无校验的方法对比，100%准确率下的最大召回率提升了30.6%，说明改进RANSAC校验在回环检测中的有效性；3）在失效卫星数据集上，验证了本方法对光照变化的空间场景具有高适应性与稳定性，且和BoW算法相比缩减时间24.1%。