光电工程  2019, Vol. 46 Issue (11): 180540      DOI: 10.12086/oee.2019.180540     
RANSAC算法在空间目标光电跟踪中的应用研究
严灵杰1,2,3 , 黄永梅1,2,3 , 张涯辉1,2 , 唐涛1,2 , 夏运霞1,2     
1. 中国科学院光束控制重点实验室,四川 成都 610209;
2. 中国科学院光电技术研究所,四川 成都 610209;
3. 中国科学院大学,北京 100049
摘要:基于光电跟踪设备对空间目标进行跟踪测量时,由于电磁干扰、云层遮挡或者地影等因素的影响,造成空间目标成像在设备视场中无法提取,严重时甚至导致系统闭环跟踪不能平稳进行。此时可以采用理论引导的方式,利用预测轨迹继续进行跟踪搜索。本文将广泛用于计算机视觉领域特征提取的随机抽样一致性(RANSAC)算法引入轨迹预测,并根据观测数据分布的特点进行改进提出WRANSAC算法,用于实时处理有限的历史观测数据,进行轨迹预测。引入该算法后,在对空间目标轨迹预测时,对历史观测数据的容错能力提高,对模型的敏感性降低,预测结果的准确性和鲁棒性远远优于最小二乘法。通过对比预测轨迹和实际轨迹,证明了该算法的有效性。
关键词参数估计    随机抽样一致性    损失函数    空间目标    轨迹预测    
Research on the application of RANSAC algorithm in electro-optical tracking of space targets
Yan Lingjie1,2,3, Huang Yongmei1,2,3, Zhang Yahui1,2, Tang Tao1,2, Xia Yunxia1,2     
1. Key Laboratory of Beam Control, Chinese Academy of Sciences, Chengdu, Sichuan 610209, China;
2. Institute of Optics and Electronics, Chinese Academy of Sciences, Chengdu, Sichuan 610209, China;
3. University of Chinese Academy of Sciences, Beijing 100049, China
Abstract: When the electro-optic tracking system is used for space target tracking, it is difficult to extract the target from the field of view occasionally due to the impact of electromagnetic interference, cloud cover or earth shadow etc., and the closed-loop tracking system can barely work in severe cases. At this point the predicted orbit can be used to guide the system to ensure smooth scanning and tracking. In this paper, random sample consensus (RANSAC) algorithm is introduced, which has been widely used in feature extraction in computer vision, to achieve higher prediction accuracy. The loss function of RANSAC algorithm is improved and the WRANSAC algorithm is proposed according to the distribution of observed data, which is used to deal with the limited observation data in real time to track the space target. After the algorithm is adopted, the fault tolerance of observation data is improved and the sensitivity of the model is reduced. The accuracy and robustness of the prediction results are much better than that of the least squares method. The validity of the WRANSAC algorithm is proved by the comparison between the predicted trajectory and the actual trajectory.
Keywords: parameter estimation    RANSAC    loss function    space target    orbit prediction    

1 引言

对空间碎片(后称空间目标)的监视和测量是当前光电跟踪测量设备的一个重要工作,在对中、高轨空间目标进行跟踪测量时,由于目标距离远,等效星等较高,为了提升设备的探测能力,一般光电探测器的口径设计较大[1];为了抑制大气信道的杂光,探测器视场一般较小基本为角分量级。在空间目标被云层遮挡或者进入地影或者半影等情况时,由于目标在设备视场中无法提取,严重时甚至导致系统闭环跟踪不能平稳进行。在此情况下,如果采用理论轨道数据进行理论引导,虽然可以在短时间内保持对目标的指向,但却丢弃了此前跟踪过程中的大量高精度观测数据。在没有多站对空间目标进行交汇测量定轨的情况下,通过预测轨迹来引导跟踪是解决该问题的一个重要途径之一[2-3]。本文以无法交汇测量的单站为背景,对利用短弧段观测数据的实时预测跟踪算法进行研究。

在对空间目标的预测跟踪中,准确的模型是保证精确性和平稳性的基础。李涛[4]对Singer统计模型和机动目标当前模型两种经典跟踪模型进行对比,证明了对超出匀速和匀加速范围的目标的运动,使用Singer统计模型会产生较大的模型误差;魏刚[5]基于Kalman滤波和一步预测理论建立目标运动数学模型,并提出了一种拟线性目标方位预测算法,但是该算法仅针对水平直线运动目标,且预测精度只能达到角分级。潘晓刚[6]推导了基于非线性变换的轨道预报算法,可以在没有准确观测数据时为光电跟瞄设备提供理论引导,并证明该算法比常规扩展卡尔曼滤波更有效,预报60 s的精度可以达到20",但是该算法只能进行短时预报,不能应对目标丢失时间较长的场景。

随机抽样一致性(random sample consensus,RANSAC)算法[7-8]是在计算机视觉领域内应用最广泛的Robust估计算法之一,本文将RANSAC算法引入轨迹预测领域,并针对经典RANSAC算法计算效率较低和对阈值较为敏感的问题进行改进,提出WRANSAC算法,利用单站短弧段观测数据实现实时高精度目标跟踪。

2 坐标系的选择

空间目标的运动特性分析参见文献[9],本文不再赘述。单站式光电跟踪系统提供的是目标的方位和俯仰数据,然而由于测站选址的不同,使得空间目标在站心地平系中的运动规律并不明显。经过实测数据分析,当测站的经度由121 °E变为76 °E时,在站心地平系中运动轨迹的方位角和俯仰角的相关性分别为0.9860和0.9994,当测站的纬度由39.6 °N变为40 °S时,在站心地平系中运动轨迹的方位角和俯仰角的相关性分别为0.9036和-0.9998,空间目标在站心地平系中[9-11]的运动规律与站址的选择的相关性较大,因此站心地平系并不是处理轨道数据的最优坐标系。

如果把空间目标视为类似于恒星的无穷远目标,经过实测数据分析,当测站的经度由121 °E变为76 °E时,在赤道坐标系[12-13]中运动轨迹的赤经和赤纬的相关性分别为0.9006和1.0000,当测站的纬度由39.6 °N变为40 °S时,在赤道坐标系中运动轨迹的赤经和赤纬的相关性分别为1.0000和0.9999。在赤道坐标系中空间目标的运动轨迹呈现非常明显的正弦趋势,而且在测站的经度和纬度改变时,空间目标运动轨迹的变化规律基本不变。且当测站确定后,赤道坐标系内的赤经、赤纬位置和地平系下的方位、俯仰位置一一对应。因而基于以上分析,本文选择赤道坐标系作为预测跟踪数据处理的坐标系。

3 RANSAC算法的分析 3.1 RANSAC算法简介

对目标轨迹进行预测跟踪时,最小二乘法是最常用的方法之一,不过由于使用整个样本空间且每个样本相同的权值,容易形成奇异的方程组是最小二乘法的通病。由Fishler和Bolles在1981年提出的RANSAC算法,能够处理错误率超过50%的数据,是目前最有效的鲁棒估计算法之一,在计算机视觉领域应用广泛,如特征匹配、模型选择、基础矩阵估计等[14-15]

在RANSAC算法中,要求在一定的置信概率之下,U组抽样数据中至少有一组全为内点[16-17]。根据式(1)可以获得满足上述要求的最小抽样组数U

$ 1 - {(1 - {(1 - \varepsilon )^m})^U} = P, $ (1)

其中:P为置信概率,m为模型参数辨识所需要的最小数据量,ε为外点在原始数据中所占的比例(即数据错误率)。

图 1所示,当P=0.99时,m值分别为4、7、8时对应的Uε的变化曲线。由图可知,在Pm确定时,Uε的增加呈指数增长。

图 1 最小抽样次数随数据错误率变化曲线图 Fig. 1 Minimum sampling frequency changing with data error rate
3.2 RANSAC算法流程

RANSAC算法通过反复挑选全部数据中的一组随机子集来完成模型的筛选[18-19]。假设被选中的子集均为内点,并使用以下步骤进行验证:

1) RANSAC算法为了保证在一定的置信概率P下至少可以选出1组不包含外点的抽样样本,抽样的次数应该足够大。由数据错误率ε和置信概率P计算最小抽样数U的公式为

$ U = \frac{{\log (1 - P)}}{{\log (1 - {{(1 - \varepsilon )}^m})}}, $ (2)

其中:ε是数据集中外点的比例,m是样本的大小。

2) 用所有原始数据集验证抽样样本集对应的模型参数的质量;RANSAC算法通过使代价函数J最小化来挑选最优模型。

$ J = \sum\limits_{d \in D} {L(E(d;S))} , $ (3)

其中:D是原始数据集,L是损失函数,E是与L对应的误差函数,S是辨识的模型参数。

RANSAC算法使用0-1损失函数:

$ {L_{\rm{R}}}(e) = \left\{ {\begin{array}{*{20}{c}} 0&{\left| e \right| \le t}\\ 1&{\left| e \right| > t} \end{array}} \right., $ (4)

其中:e为误差值,t为用于区分内点和外点的误差阈值。

3) 根据内点的数量及方差值来挑选出最优模型;

4) 用最优模型参数计算得到的所有内点来辨识最终模型的参数。

3.3 改进的RANSAC算法

经典RANSAC算法中使用的0-1损失函数,虽然计算量小、收敛速度快,但是对误差阈值非常敏感。M估计抽样一致性算法(M-estimator sample consensus, MSAC)[11]使用有界损失函数LM来解决0-1损失函数对阈值敏感的问题:

${L_{\rm{M}}}(e) = \left\{ {\begin{array}{*{20}{c}} {\frac{{\left| e \right|}}{t}}&{\left| e \right| \le t}\\ 1&{\left| e \right| > t} \end{array}} \right.。$ (5)

本文提出一种基于正弦函数的损失函数Ls

$ {L_{\rm{s}}}(e) = \left\{ {\begin{array}{*{20}{c}} {\frac{1}{2}\cos \left( {\frac{e}{{2t}}} \right) + \frac{1}{2}}&{\left| e \right| \le t}\\ 1&{\left| e \right| > t} \end{array}} \right.。$ (6)

图 2所示的三类损失函数曲线中,LMLR相比考虑了阈值范围内的误差,因而准确性更高。考虑到较小的误差通常是由内点的噪声导致,较大的误差可能受外点影响,但实际中内点和外点之间的界限一般是不精确的,所以LsLM的基础上进行改进,增大对较大误差的惩罚,减小对较小误差的惩罚,而且Ls有连续的一阶导数,在阈值附近变化更为平缓,进一步减轻了算法对阈值的敏感性,提高了算法的鲁棒性和准确性。改进后的算法称为WRANSAC算法。

图 2 损失函数曲线图 Fig. 2 Loss function curve

WRANSAC的算法流程图如图 3所示,WRANSAC算法采用Ls损失函数来计算代价函数,可以更准确和高效地评价模型的有效性。在通过抽样样本筛选模型的过程中,如果当前内点集代价函数比之前的小,则用当前内点集更新最优内点集,直至迭代次数达到设定的最大值之后退出模型选择循环。最后根据损失函数值定义所有内点的权值,用提纯后得到的加权最优内点集来计算最终模型的参数。

图 3 WRANSAC算法流程图 Fig. 3 Flow chart of the WRANSAC algorithm
4 实验及结果分析

实验通过光电跟踪设备对任选空间目标2 h的观测数据来预测接下来15 min、30 min和72 min (地影最长时间是72 min)目标在第二赤道坐标系中的运动轨迹。为了模拟真实场景中的误差,对数据叠加幅值为3"的高斯白噪声。实验参数设置为:置信概率P=0.995,数据错误率ε=0.03,计算模型需要的最小数据量m=4,RANSAC算法中用以区分内点和外点的阈值设置为$t = 3\sigma $,其中$\sigma$是所叠加高斯白噪声的标准差。

最终算法的最小抽样次数是3,得到的最优内点集有76个观测点,内点集的代价函数柱状图和对应的权值柱状图如图 4图 5所示。

图 4 内点代价函数柱状图 Fig. 4 Histogram of interior point cost function

图 5 内点权值柱状图 Fig. 5 Histogram of internal point weights

使用上述参数重复进行仿真20次,预测结果的误差特性如表 1所示。

表 1 15 min、30 min和72 min预测误差特性 Table 1 Prediction error statistics for 15/30/72 minutes
预测时长/min 算法 sin LSQ RANSAC WRANSAC
15 最大值/(″) 34.9151 29.1957 19.5649 17.0257
最小值/(″) -6.9270 -10.8216 -17.7444 -16.8968
均值/(″) 15.1429 0.1934 2.4577 0.9701
方差 124.3353 90.9505 59.9375 57.9286
30 最大值/(″) 36.3312 32.0761 11.1779 10.8932
最小值/(″) -13.1593 -18.8263 -23.3834 -21.5939
均值/(″) 13.0059 -0.6765 -2.0592 -4.6598
方差 218.0527 163.9206 84.8496 82.1343
72 最大值/(″) 6.6790 286.3128 26.8620 17.7788
最小值/(″) -120.0175 -207.9139 -19.1023 -18.0916
均值/(″) -32.2389 6.0681 0.7308 -0.7330
方差 602.6599 15953.6643 118.8533 89.7496

图 6 预测72 min的轨迹图 Fig. 6 Prediction of 72 minutes

图 7 预测72 min的误差分布图 Fig. 7 The error distribution for the prediction of 72 minutes

通过对比四种算法:标准正弦函数法、最小二乘法、RANSAC算法和改进的RANSAC算法,可以得出:

1) 当预测时间较短时,几种算法的精度和稳定性接近,没有明显的发散趋势,标准正弦函数预测的精度可以控制在35"以内,其它算法预测精度可以控制在30"以内,WRANSAC算法和RANSAC算法相比最小二乘算法预测精度提升1"~2",预测的稳定性提高约3.35%;

2) 当预测时间较长时,最小二乘法和标准正弦函数法受观测数据中外点的影响有明显的发散趋势,而RANSAC和WRANSAC算法的鲁棒性比较好,预测的精度仍然可以保持在27"以内,WRANSAC算法相比RANSAC算法预测精度提升1"~9",预测的稳定性提高约24.49%;

3) WRANSAC算法通过2 h的观测数据预测72 min的轨迹,预测精度可以控制在27"以内,保证光电跟踪系统的稳定跟踪,有效对抗云层遮挡和地影等因素的干扰。

5 结论

本文在RANSAC算法的基础上,对其损失函数进行了改进,并将其用于光电跟踪设备对空间目标的监测和跟踪。经典RANSAC算法中使用的0-1损失函数,虽然计算量小、收敛速度快,但是对误差阈值非常敏感。本文提出的WRANSAC算法,采用基于正弦函数的损失函数,增大了对阈值范围内较大误差的惩罚,减轻了对较小误差的惩罚,更接近实际数据分布的规律。实验结果表明,在最大迭代次数允许和模型阶次确定时,WRANSAC算法总是能够计算出模型最优解,利用已获得的2 h的观测数据预测72 min的空间目标轨迹误差可以控制在27"以内,而且算法的实时性和鲁棒性优于最小二乘法,经实验验证该算法可以保证光电跟踪系统对空间目标的稳定跟踪,有效对抗电磁干扰、云层遮挡和地影等因素的干扰。

参考文献
[1]
Ma J G. The basic technologies of the acquisition, tracking and pointing systems[J]. Opto-Electronic Engineering, 1989(3): 1-42.
马佳光. 捕获跟踪与瞄准系统的基本技术问题[J]. 光学工程, 1989(3): 1-42 [Crossref]
[2]
Cai H Y, Ding L, Huang Z H, et al. An accurate calibration method of the ball screen projection point targets tracking system[J]. Opto-Electronic Engineering, 2018, 45(8): 170656.
蔡怀宇, 丁蕾, 黄战华, 等. 球幕点目标投影跟踪系统的精确标定方法[J]. 光电工程, 2018, 45(8): 170656 [Crossref]
[3]
Zhang P L, Wang J J. Research of LEO satellite orbit prediction for vehicle-borne optical measuring equipment[J]. Mathematics in Practice and Theory, 2015, 45(6): 128-132.
张沛露, 王建军. 车载跟瞄设备低轨卫星预测方法研究[J]. 数学的实践与认识, 2015, 45(6): 128-132 [Crossref]
[4]
Li T, Zhang J C. The tracking accurancy analysis of single maneuvering targets[J]. Journal of Projectiles, Rockets, Missiles and Guidance, 2004, 24(2): 94-96.
李涛, 张金成. 单机动目标跟踪精度分析[J]. 弹箭与制导学报, 2004, 24(2): 94-96 [Crossref]
[5]
Wei G, Jiang C F, Yang K T. Precision azimuth prediction method for electro-optical tracking[J]. Opto-Electronic Engineering, 2006, 33(5): 6-11.
魏刚, 江传富, 杨坤涛. 方位角准确预测法在光电跟踪中的应用研究[J]. 光电工程, 2006, 33(5): 6-11 [Crossref]
[6]
Pan X G, Zhou H Y, Wang J Q, et al. Orbit prediction algorithm of LEO satellite based on optical measurement in short arc with single station[J]. Acta Astronomica Sinica, 2009, 50(4): 445-458.
潘晓刚, 周海银, 王炯琦, 等. 基于单站短弧段光学观测的低轨卫星轨道预报算法[J]. 天文学报, 2009, 50(4): 445-458 [Crossref]
[7]
Choi S, Kim T, Yu W. Robust video stabilization to outlier motion using adaptive RANSAC[C]//2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, St. Louis, MO, USA, 2009: 1897-1902.
[8]
Chum O, Matas J. Optimal randomized RANSAC[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(8): 1472-1482. [Crossref]
[9]
Huang Z F, Wang J Z, Chen Z P. Motion characteristics analysis of space target and stellar target in opto-electronic observation[J]. Opto-Electronic Engineering, 2012, 39(4): 67-72.
黄宗福, 汪金真, 陈曾平. 光电探测中空间目标和恒星目标运动特性分析[J]. 光电工程, 2012, 39(4): 67-72 [Crossref]
[10]
Luo H, Mao Y D, Yu Y, et al. A method of GEO targets recognition in wide-field opto-electronic telescope observation[J]. Opto-Electronic Engineering, 2017, 44(4): 418-426.
罗浩, 毛银盾, 于涌, 等. 利用超大视场光电望远镜观测GEO中的目标识别方法[J]. 光电工程, 2017, 44(4): 418-426 [Crossref]
[11]
Cen M, Fu C Y, Liu X F, et al. Position prediction method for satellite tracking based on error-space estimate[J]. Opto-Electronic Engineering, 2007, 34(6): 15-19.
岑明, 傅承毓, 刘兴法, 等. 误差空间估计的卫星跟踪位置预测[J]. 光电工程, 2007, 34(6): 15-19 [Crossref]
[12]
Cheng W L, Wang X J, Wan Z J, et al. Research and implementation of target tracking algorithm in compression domain on miniaturized DSP platform[J]. Opto-Electronic Engineering, 2017, 44(10): 972-982.
程卫亮, 王向军, 万子敬, 等. 压缩域目标跟踪算法在小型化DSP平台上的研究与实现[J]. 光电工程, 2017, 44(10): 972-982 [Crossref]
[13]
Li Z W, Zhang T, Sun M G. Fast recognition and precise orientation of space objects in star background[J]. Optics and Precision Engineering, 2015, 23(2): 589-599.
李振伟, 张涛, 孙明国. 星空背景下空间目标的快速识别与精密定位[J]. 光学精密工程, 2015, 23(2): 589-599 [Crossref]
[14]
Xu M, Lu J. Distributed RANSAC for the robust estimation of three-dimensional reconstruction[J]. IET Computer Vision, 2012, 6(4): 324-333. [Crossref]
[15]
Chen F X, Wang R S. Fast RANSAC with preview model parameters evaluation[J]. Journal of Software, 2005, 16(8): 1431-1437.
陈付幸, 王润生. 基于预检验的快速随机抽样一致性算法[J]. 软件学报, 2005, 16(8): 1431-1437 [Crossref]
[16]
Hast A, Nysjö J, Marchetti A. Optimal RANSAC-towards a repeatable algorithm for finding the optimal set[J]. Journal of WSCG, 2013, 21(1): 21-30.
[17]
Chum O, Matas J, Kittler J. Locally optimized RANSAC[C]//Proceedings of 25th DAGM Symposiumon Pattern Recognition, Magdeburg, Germany, 2003, 2781: 236-243.
[18]
Subbarao R, Meer P. Beyond RANSAC: user independent robust regression[C]//2006 Conference on Computer Vision and Pattern Recognition Workshop (CVPRW'06), New York, NY, USA, 2006.
[19]
Xiao C B, Feng D Z, Feng X W. Fast RANSAC algorithm with resample optimization[J]. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(4): 606-613.
肖春宝, 冯大政, 冯祥卫. 重抽样优化的快速随机抽样一致性算法[J]. 计算机辅助设计与图形学学报, 2016, 28(4): 606-613 [Crossref]