一种快速全天星图识别算法

程会艳，钟红军，王 龙，杨 君，郑 然

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

一种快速全天星图识别算法

程会艳，钟红军，王 龙，杨 君，郑 然

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

对星敏感器全天识别算法进行了研究，综合考虑三角形匹配识别法和四面体识别法的优缺点，提出一种改进的快速全天星图识别算法.该算法通过优化导航星对角距筛选方法，节省存储空间；同时引入K矢量法用于加快星图识别中角距匹配的速度；在三角形识别不唯一时，引入第四颗观测星进行四面体识别，提高识别成功率；并在三角形识别结束后增加投影验证功能以避免误识别.仿真结果表明，该算法合理有效，可节省存储空间，减小星图识别时间，提高识别正确率，具有很好的实用价值.

星敏感器;快速星图识别；K矢量；投影验证

0 引 言

星敏感器是通过敏感恒星辐射来测定航天器相对于天球坐标系的三轴姿态，其作为一种高精度的姿态测量装置，被广泛应用到各种航天器中.随着航天器对姿态控制要求的提高，星敏感器的研究方向主要向着运算速度快，体积小，功耗低，高精度和高度智能自主的方向发展[1-2].

星图识别算法是星敏感器的核心技术之一，其根据有无初始姿态分为全天星图识别和局部星图识别.其中全天星图识别不需要任何姿态信息，通过全天星图对比完成自主识别，是星敏感器实现全天自主姿态输出的基础，识别难度比局部星图识别大很多，是星图识别的核心研究内容.

星图识别算法一般分为两大类：第一类方法将视场内的观测星图看作是整个天球星图中的一个子图，通常利用的信息是星对角距，或者三颗星相互间的角距信息，这类方法有三角形算法、四面体识别算法和多边形角距算法等[3-4]；第二类方法认为每颗星都具有其不同的模式，这一模式主要有邻域伴星的信息构成(如其几何分布特性)，这类方法比较典型的有网格法和极坐标匹配法[5-6].

其中三角形算法和极坐标匹配法是到目前为止应用比较成熟的两种星图识别方法.三角形算法原理简单，易于实现，但是其误匹配较多，所需存储空间也比较大[7-8]；极坐标匹配法的识别概率高，误识别率低，但该方法需要为每颗导航星建立模版，所需存储空间大，识别时间长，实时性较差.

为此本文提出了一种全天快速星图识别算法，可显著减小星图识别时间和存储空间，降低误识别概率，具有很好实用性.该算法首先对用于星图匹配的导航星对角距表进行预处理，减小存储空间和匹配速度；其次，该算法引入K矢量方法用于查找匹配角距[3,7-8]，加快角距查找的速度，减小识别时间；同时在三角形识别不唯一的情况下，引入第四颗观测星，进行四面体识别，提高识别成功率；最后，在匹配识别唯一时，进行姿态计算，根据计算的姿态进行投影验证，避免误识别.

1 改进的星图识别算法

在星敏感器的星对角距测量精度较高的情况下，三角形匹配具有很高的识别成功率，但由于其特征维数较低，在测量精度较低的情况下，冗余匹配导致识别成功率迅速降低.增加特征维数是解决冗余匹配的有效方法之一，由于观测星亮度的测量存在较大的误差，而且会增加导航星表的容量.因此考虑通过增加角距数量来以降低冗余匹配的概率，即相对于三角形模式，通过增加一颗观测星组成空间四面体，获得3个具有相同顶点的角距.在匹配时，可以认为该空间四面体由一个三角形和一个公共顶点构成，识别过程仍然使用三角形模式特征，同时保持星对角距信息表不变.

为此，本文将三角形匹配与四面体匹配识别方法相结合，引入投影验证来提高识别正确率，提出了一种改进的全天星图识别算法.该算法首先按照三角形匹配方法进行匹配识别，之后对识别结果进行判断，如果三角形识别唯一，则根据识别结果计算姿态，再根据姿态进行投影验证，若投影验证成功，则匹配识别成功；若投影验证失败，则重新选择三角形进行匹配识别；如果三角形识别不唯一，则再增加一颗观测星信息，采用四面体识别方法进行匹配识别，若匹配识别结果唯一，则识别成功；若匹配识别结果不唯一，则重新选择三角形进行三角形匹配识别.算法实现的具体过程如下：

1)生成星图匹配识别所需的导航星对角距表(具体生成方法见2节)；

2)将所有观测星按照星点能量从大到小进行排序；

3)根据观测星能量选择三颗观测星，组成观测星三角形；

4)对观测星三角形进行三角形匹配识别；

为了加快匹配识别的速度，利用K矢量法查找满足角距匹配阈值的导航星对角距，具体查找方法见第3节，之后按照三角形匹配识别方法进行匹配识别.

5)对三角形匹配识别结果进行判断，若三角形匹配识别唯一，则根据识别结果计算当前姿态，之后执行步骤8)；若三角形识别不唯一，则顺序执行下一步骤；

6)从剩余观测星中根据能量信息选择一颗观测星与前面的三颗观测星组成空间四面体，按照四面体匹配识别方法进行匹配识别.

为了加快角距查找的速度，在四面体匹配过程中利用K矢量法查找满足角距匹配阈值的导航星对角距；

7)对四面体匹配识别结果进行判断，若四面体匹配识别结果唯一，则执行步骤(10)；否则执行步骤3)；

8)根据计算姿态进行投影验证.

投影验证过程如下：

a)首先根据计算的姿态遍历导航星表，将视场内导航星投影在成像面上；

b)计算成像面上所有导航星与观测星之间夹角；

c)根据投影设置的角距阈值对计算的导航星与观测星夹角进行判断，统计满足投影角距阈值的角距个数Nangle；

d)若Nangle的数值大于等于角距个数阈值，则认为投影验证成功；若Nangle的数值小于角距个数阈值，则认为投影验证失败.

9)对投影验证结果进行判断，若投影验证成功，则顺序执行下一步骤，否则执行步骤(3)；

10)匹配识别成功，结束识别.若导航星表较大，导航星数较多时，为了进一步提高识别正确率，可在四面体识别后增加投影验证，对识别结果进行确认.

2 生成导航星星对角距表

星对角距的定义为两颗导航星矢量相对于地心的夹角，通常用角距的余弦值来表示.由于直接存储所有的导航星的星对角距会带来存储容量庞大且冗余匹配多等问题，为此，首先需对星对角距进行预处理，以减小存储空间，加快识别速度.

导航星星对角距生成的过程如下：

首先根据星敏感器的视场和视场内导航星数阈值进行筛选，生成导航星对角距.

记星敏感器的视场大小为ω，若星敏感器视场为20°×20°，则ω为20°.记导航星数阈值为Thr_Nstar，用于限制视场内的导航星数，表示用于星图识别的视场内导航星数最大值.若视场内导航星数小于Thr_Nstar，则取Thr_Nstar为实际视场内导航星数；若视场内导航星数大于Thr_Nstar，则取Thr_Nstar为提前设置的阈值，保持不变.

若导航星表中星数较少时，根据视场筛选后得到的导航星星对角距也较少，其所占存储空间较小；若导航星表中星数较多时，则根据视场筛选得到的角距个数仍然很多，需要占用较大的存储空间，且只根据视场筛选得到的导航星对角距表中存在一部分角距其满足视场条件但在星图识别过程中并没有用到这些角距对.为了减小存储空间，得到有效的星对角距，本文提出一种新的星对角距筛选方法.

该方法筛选的过程如下：首先初始化导航星对角距表；之后遍历全天球所有天区，对于任一给定的光轴指向，将导航星表中导航星根据视场大小和光轴指向进行投影，得到视场内导航星；然后对视场内导航星按照星等从小到大进行排序，选择前Thr_Nstar颗导航星，并计算两两之间的星对角距；最后对计算的星对角距进行判断，若星对角距表中存在该对星对角距，则重新计算下一个星对角距.若星对角距表中不存在该对星对角距，则将该星对角距存入导航星对角距表中.以此类推，遍历完全天球所有天区指向，得到的导航星表即为筛选后满足条件的有效导航星对角距表.

经过筛选后得到的导航星对角距个数大幅减少(相对于只根据视场筛选得到的角距个数)，同时也减少了冗余角距个数，节省了存储空间，加快匹配识别的速度.

导航星对角距表中包含满足条件的星对角距，以及组成该星对的每颗导航星在导航星信息表中的存储位置即导航星序号.

为了方便角距查找，加快查找速度，减少角距匹配的时间，对导航星对角距表进行排序，得到全天星图识别所需的导航星对角距表.

3 角距查找方法

由于星敏感器系统存在各种误差，观测角距并不能完全等同于对应导航星之间的真实角距，通常需根据星敏感器的测量精度，设置合理的门限值，在门限值的范围内对观测角距进行匹配，为此需根据观测角距查找满足角距匹配阈值的导航星对角距，用于匹配识别.

目前最为常用的角距查找方法是折半查找法，该方法实现简单，查找准确率高，但该方法的查找长度与星对角距表中的角距个数成对数关系，当星敏感器的星等灵敏度比较高时，星对信息表中的角距个数大幅增加，查找次数的增加会导致识别时间增加.本文采用目前查找速度较快的K矢量方法，该方法所需的查找时间不受角距信息表容量的影响，因此其使用不受星敏感器视场和星等灵敏度的影响，使用范围广，对于大容量的星对角距表在查找时间上有很大优势.

K矢量算法可以看作拟和曲线方法的一种，其通过拟和曲线来确定数组K，有效克服拟和曲线精度低的缺点.一定视场条件下，角距余弦值的分布介于直线和余弦曲线之间，可用余弦曲线和直线来模拟角距余弦值的分布.下面说明用直线来模拟角距余弦值分布的方法，其构造过程如图1所示.

以图1为例说明K矢量查找算法，记S为从小到大排序后的星对夹角余弦值，其包含10个元素的角距信息表，即数组S的维数m等于10，其角距分布如图1中点所示，Is和Js也是m维数组，和数组S中的元素相对应，代表了组成候选星对的两颗导航星在导航星信息表中的编号.在查找匹配角距之前需要先计算查找中所需的参数D,a0,a1和整型数组K，其计算方法见参考文献[7].

设观测角距的余弦值为cosν，角距匹配门限值为ε，识别过程需要分别确定cos(ν-ε)和cos(ν+ε)对应角距信息表中的角距，其查找过程如下：

首先计算kstart和kend的值，其中

lbot=bot{[cos(v+ε)-a0]/a1}
ltop=top{[cos(v-ε)-a0]/a1}
kstart=K(lbot)+1
kend=K(ltop)

说明：bot{x}代表小于x的最大整数；top{x}代表大于x的最小整数；kstart表示cos(ν+ε)在星对信息表中的位置；kend表示cos(ν-ε)在星对信息表中的位置.

对观测角距cosν进行匹配:ya=cos(ν+ε)，其对应lbot=4，由K矢量的构成K(lbot)=3，kstart=4；yb=cos(ν-ε)，其对应ltop=9，由K矢量的构成K(ltop)=9，kend=9.以ε作为角距匹配门限的cosν，其对应的角距范围从S(4)到S(9).

4 仿真结果与分析

4.1仿真条件

以某卫星在轨所用的国产星敏感器为例，该星敏感器视场为20°×20°，在MATLAB7.0仿真平台下利用其实测星图中的1 000幅星图为例，进行算法仿真验证.仿真中所用的具体参数设置如下：

1)设置视场内导航星数阈值Thr_Nstar=15；

2)(设置)投影验证时满足角距匹配的角距个数阈值Nangle=5；

3)匹配识别时角距阈值为60″.

4.2仿真结果

根据以上仿真条件，对实测的1 000幅星图分别用三角形匹配法、极坐标匹配法和本文提出的快速算法进行仿真，主要是测试算法的全天识别时间、识别正确率和存储空间.

考虑到实测星图无法获得其真实姿态，由于极坐标匹配法可靠性相对较高，为此，以极坐标匹配法识别结果计算的姿态为基准，对三角形匹配法和本文的改进算法计算的识别结果进行验证.

仿真得到3种算法每幅星图识别的识别时间分别如图2～4所示，同时对3种算法的误识别概率和存储空间进行统计，其结果如表1所示.

表1 3种匹配识别算法的测试结果Tab.1 Test results of the three match algorithms

对比图2～4和表1可以看出，改进算法的识别时间相对于三角形匹配法由于增加了投影验证功能其识别时间有所增加，但增加量很小(表中总识别时间为1 000幅星图的识别时间).对比可知，本文提出的改进算法相对于极坐标匹配法其识别时间大幅度减小，识别正确率因增加投影验证功能并没有降低；三角形匹配法的识别时间与本文所提出的算法的识别时间相当，但其存在误识别(1 000幅星图中有2次误识别).

本文仿真中所用的导航星表中导航星数为3 000 多颗，三角形匹配识别要预先存储识别所需的角距表，其根据视场筛选得到星对角距个数为60 000 多个，占用存储空间约0.46 MB；改进算法也需预先存储导航星对角距表，利用文中第3部分的角距筛选方法生成的星对角距个数为20 000多个，相对于只根据视场筛选其角距个数大幅度减少，占用存储空间也大幅降低，其星对角距占用存储空间约0.15 MB；极坐标匹配法需要预先存储用于星图识别的导航星极坐标模版和索引，其所占存储空间为0.52 MB，相对于改进算法其占用存储空间相对较大.

5 结 论

本文对星敏感器全天星图识别算法进行深入研究，结合三角形匹配算法和四面体匹配算法提出了提出一种快速全天星图识别算法.由仿真结果可知：本文提出的算法合理有效，与极坐标匹配法相比，其识别正确率与极坐标匹配法相当，但在存储空间和识别时间上有很大优势(平均识别时间由6 s减少到0.1 s以下，存储空间由0.5 MB减小到0.15 MB).相对于目前成熟的三角形匹配法，两种算法的识别时间相当，但该改进算法的识别正确率和识别成功率得到显著提高，具有较强的工程实用价值.

[1] 张广军,魏新国,江洁. 一种改进的三角形星图识别算法[J]. 航空学报, 2006,27(6):18-25 ZHANG G J,WEI X G,JIANG J.A modified triangle star pattern recognition algorithm[J]. Acta Aeronautica ET Astronautica Sinica, 2006,27(6):18-25.

[2] 张仁斌,王鹿,李钢.一种基于三角形的快速星图识别方法[C].第三届全国虚拟仪器学术交流大会论文集.桂林：中国仪器仪表协会，2009.

[3] 邢飞,尤政,董瑛.基于导航星域和K矢量的快速星图识别算法[J].宇航学报,2010,31(10):28-35. XING F,YOU Z,DONG Y.A rapid star identification algorithm based-on navigation star domain and K-vector[J].Journal of Astronautics,2010,31(10):28-35.

[4] GWANGUEOK J U. Autonomous star sensing, pattern identification and attitude determination for spacrcraft: an analytical and experimental study[D]. Dissertation of Texas A&M University, 2001.

[5] 郑万波，基于星敏感器的全天自主分层星识别算法研究[D].长春：中国科学院长春光学精密机械与物理研究所，2003.

[6] 海峰，袁家虎，毛羽国.快速星图匹配算法的研究[J].光电工程，1998,25(6): 70-74.

[7] 张晨，陈朝阳，沈绪榜.基于角距分布的星表快速查找算法[J].计算机工程与应用，2004,40(9):16-18. ZHANG C,CHEN Z Y,SHEN X B.angular distance distribution-based search-less algorithm for star list[J].Computer Engineering and Applications，2004,40(9):16-18.

[8] 应磊.星敏感器全天球快速定向识别算法研究[D].北京：北京控制工程研究所，2007.

AFastAlgorithmofAll-SkyStarMapAutomatedIdentification

CHENG Huiyan, ZHONG Hongjun, WANG Long, YANG Jun, ZHEN Ran

(BeijingInstituteofControlEngineering,Beijing100190，China)

The method of space objects recognition with star pattern algorithm is discussed. An all-sky map recognition algorithm is carried out based on the research of triangle algorithm and tetrahedral algorithm. Firstly, the algorithm optimizes the method of creating angular distance table in order to save vacuum. Then, theKvector method is used to increase the speed of angle-pair matching in star pattern. Tetrahedron algorithm is introduced when the results of triangle recognition are not unique. The projection validation is increased after the triangle recognition in order to overcome error match. Simulation is carried out. The result shows that the algorithm proposed in this paper is effective, which can not only improve the speed of star pattern recognition, but also increase the rate of correct recognition. Thus, the algorithm has great practical value.

star sensor； star map identification;Kvector; projective validation

V448

：A

： 1674-1579(2017)04-0073-06

10.3969/j.issn.1674-1579.2017.04.013

2016-09-13

程会艳(1984—)，女，工程师，研究方向为星敏感器图像处理算法；钟红军(1978—)，男，研究员，研究方向为星敏感器电路设计；王龙(1985—)，男，工程师，研究方向为星敏感器电路设计；杨君(1980—)，男，工程师，研究方向为星敏感器电路设计；郑然(1982—)，男，工程师，研究方向为星敏感器软件算法设计.