袁晓波，张 超，时春霖

(1.信息工程大学 导航与空天目标工程学院，郑州 450001；2.北斗导航应用技术河南省协同创新中心,郑州 450001； 3.61206部队，北京 100042)



一种改进的基于K矢量的星图识别算法

袁晓波1,2，张 超1,2，时春霖1,3

(1.信息工程大学 导航与空天目标工程学院，郑州 450001；2.北斗导航应用技术河南省协同创新中心,郑州 450001； 3.61206部队，北京 100042)

为了提高星敏感器定姿中星图识别的精度和效率，基于K矢量原理和四边形匹配法则提出一种改进的星图匹配方法：首先基于K矢量查找法快速匹配星间角距，得到角距的匹配组合；再采用一种基于标识符的快速判别方法进行导航星的判别，得到4颗匹配成功的基准星；最后基于4颗基准星按四边形匹配法则完成全视场的匹配。实验结果表明，该方法具有良好的实时性和准确性。

星图识别；K矢量；四边形；标识符匹配

0 引言

姿态测量是航天器飞行的重大核心技术之一，对保证航天器准确入轨和变轨、高性能飞行、可靠对地通信、高精度对地观测，及顺利完成各种空间任务具有重要意义[1]。星敏感器作为一种高性能姿态敏感器，具有精度高、无误差积累、可自主标定和故障恢复等优点，在航天器姿态测量中拥有广泛的应用。

星图识别是星敏感器定姿系统的关键技术之一。星图识别可以看作是模式识别问题中的一种[2]，其实质是从星图星中提取识别特征，与从导航星表中提取的识别特征进行匹配，以确定星图星和星表星的对应关系。经过国内外学者多年的研究和工程实践，目前已发展出多种星图识别方法，大致可以分为2大类：一类是子图同构类算法，如三角形算法[3]、多边形算法[4]、匹配组算法[5]等；另一类是基于星模式的星图识别算法，如栅格算法[6-7]、字符串算法[8]、金字塔算法等[9]，此外还有奇异值分解法[10]、基于遗传算法的星图识别算法[11]、基于神经网络的算法[12]等较新的模式识别算法。衡量某种识别算法优劣与否的重要指标是实时性和准确率。以三角形算法为代表的子图同构类算法抑或匹配冗余大，抑或在解决冗余问题的同时增加了运算量，影响星敏感器姿态输出的实时性；以栅格法为代表的模式识别算法具有容错能力强、存储容量小的优点，但在特征提取上仍有不足，匹配准确率不高；以基于神经网络的识别算法为代表的新式算法虽然新颖，但过程复杂，不利于工程化。

K矢量查找法是一种通用的单调函数快速查找方法[13]，具有在大量数据中快速确定数据位置的特点；四边形匹配法基于4颗基准星，通过构造多个匹配三角形，提高了匹配的准确率[14]。基于此，本文提出了一种基于K矢量和四边形匹配法则的星图识别算法，并通过仿真星图和实测星图对算法的实时性和准确性进行了验证，并取得了良好效果。

1 星敏感器成像原理

如图1所示，星敏感器的成像模型一般为小孔成像。恒星(αi,δi)经星敏感器成像后在星图中的成像中心为(xi,yi)，分别计算恒星在恒星惯性系和星敏感器坐标系中的指向Ri、ri为：

(1)

(2)

二者存在唯一的关系ri=C·Ri。式中：(x0,y0)为像主点坐标；f为星敏感器的角距；C为恒星惯性矢量与像坐标矢量之间的转换矩阵。

2 基准星搜索

2.1 导航星库的编制

根据星敏感器敏感的极限星等、视场大小，从基础星表中筛选出星敏感器能捕捉到信号的恒星，通过剔除双星、变星、视位置计算，结合采用的匹配特征量，制成导航星库。首先根据星敏感器捕捉到信号的极限星等刷选出待检索的导航星，计算两两之间的角距的余弦值cosθij；再根据星敏感器的视场角对cosθij做进一步刷选，把提取出来的cosθij按升序排列。选依巴谷星表作为基础星表，按极限星等5.5、视场20.3°编制导航星库(见表1)，共选出2 827颗导航星，构成星对269 421对。

表1 导航星库

2.2K矢量原理

K矢量是指由一系列单调递增的元素构成的矢量，K矢量查找法是基于K矢量建立的一种快速的数据查找方法，具有在大量数据中快速查找目标元素索引位置的特点，其原理如下[13，15]：

在一个长度为n的单调递增向量s中，设首末端点分别为(1,s(1))、(n,s(n))，连接首末端点即可构成一条直线。考虑到计算误差等因素的存在，为了充分包含2个端点，需要让直线稍微倾斜一点。设ξ为计算误差，按ξ对直线进行倾斜，即连接首末点(1,s(1)-ξ)、(n,s(n)+ξ)，因此直线方程可以写成

z(x)=a1x+a0。

(3)

令K(1)=0、K(n)=n，其中向量K的形成规则为K(i)=j当s(i)≤z(i)

可以看出：K矢量实际表示为向量s中值小于a1x+a0的个数。

一旦K矢量建立好后，即可以估计任意范围[sa,sb]所对应的K矢量为

(4)

式中：⎣x 」表示小于x的最大整数；「x⎤表示大于x最小整数，ib、it分别表示3矢量检索的起始位置。当ib和it都计算完后，即可以计算出K矢量的起始位置

(5)

以上就完成了K矢量的建立与查找，下面将K矢量应用于星图识别中。

2.3 基准星的搜索匹配

将星间角距的余弦值cosθij按从小到大的顺序排序，构成单调递增的向量s，连接首尾点(1,(1))、(n,s(n))，平均步长为d=(s(n)-s(1))/(n-1)。为了将首尾点充分包含，这里按d/2对直线做一定的倾斜，即连接点(1,s(1)-d/2)、(n,s(n)+d/2)构成方程

cosθij=a1k+a0。

(6)

式中：a1=dn/(n-1)，为直线斜率；a0=s(1)-a1-d/2，为方程常数项。

考虑到测量误差的存在，只能确定角距余弦值的范围。假设测量误差为ξ，cosθij对应的K矢量为

(7)

将式(7)代入(5)式即可计算K矢量的起始位置。

根据K矢量的起始位置可得到待匹配角距在导航星库中可能的星对组合Cij(注：i、j分别表示匹配角距的2颗恒星的序号)。由于测量误差的存在，每个角距可能会得到多个匹配成功的星对组合，而无法得到唯一的匹配结果，还需结合其他角距的匹配结果进一步判断星图星与导航星的对应关系。

2.4 基准星的判断

一般而言，在C12、C13、C14、C23、C24、C34这6个集合中采用遍历的方法确定恒星的对应关系需要(n12·n13·n14·n23·n24·n34)次的比较运算，假设平均每条角距有10个匹配组合，则需要进行106次比较运算，这样十分耗时。为了避免无用的比较运算、提高匹配效率，这里采用一种基于标识符的简单快速的导航星判别方法来确定4颗导航星在星表中的位置(s1,s2,s3,s4)，其具体步骤为：

1)构造标识符矩阵H=01×n，n为星表星的总个数。

2)扫描C12，将C12中出现的恒星对应的标识符设置为1，即假如(i,j)∈C12，则H(i)=1,H(j)=1；记下标识符为1的匹配星序号设为s1，与之组成星对的另一颗星的星序号为s2。

3)扫描C13，对于C13中出现的恒星，其标识符在原来的基础上+1，即如果其标识符为0，则置为1，如果标识符为1，则置为2；记下与标识符为2的恒星组成星对的另一颗星的星序号s3。

4)扫描C14，对于C14中出现的恒星，其标识符在原来的基础上+1，记下与标识符为3的恒星组成星对的另一颗星的星序号s4。

5)扫描C23、C24、C34，如果星对组合满足(s2,s3)∈C23且(s2,s4)∈C24且(s3,s4)∈C34，则认为匹配成功。这样就得到了与(p1,p2,p3,p4)相对应的星表星组合(s1,s2,s3,s4)。

采用本方法的搜索量为n12+n13+n14+n23+n24+n34，搜索量比遍历组合的方法大大缩减，且通过步骤5)中3星两两组合验证的方法大大提高了识别的正确率。

3 基于基准星的全视场匹配

在得到4颗基准星的匹配结果后，为提高剩余星的匹配速率，由4颗基准星计算出一个概略姿态，根据概略姿态和星敏感器参数，进一步筛选星表。将待匹配的星图星与4颗基准星中的任意2颗星图星组成角距三角形，从星表中任意挑选1颗与这2颗星的星表星组成角距三角形，比较星图角距三角形与星表角距三角形的相似度。每颗待匹配星与4颗基准星组成6个角距三角形，当这6个角距三角形与星表角距三角形都匹配时，则认为该星匹配成功。

如图2，假设(p1,p2,p3,p4)为匹配成功的4颗星图星，(s1,s2,s3,s4)为对应的星表星，p为待匹配的星图星，s为检索的星表星，以ri表示p与pi的角距，Ri表示s与si之间的角距，评价星图三角形Δppipj与Δssisj的相似度标准为

(8)

设em为设定的判断限值，取10-6，当eij≥em时认为该星非星表对应星，该星表星匹配结束，取下一颗星表星进行匹配；当eij

4 实验与结果分析

4.1 计算机仿真

用STK(satellitetoolkit)软件内置的ALOS遥感卫星生成轨道和姿态数据，根据轨道和姿态数据及星敏安装矩阵计算星敏感器的指向，再根据星敏指向仿真得到300幅连续的星图。星敏感器的部分参数见表2。

表2 星敏感器参数

采用平方质心法提取星点，提取星点个数在14～23之间。按本文方法分别进行初始模式和跟踪模式下的匹配识别，实验环境为MATLAB 2014a、Intel i5处理器、8G内存、win7系统，星点测量误差为0.5个像素。匹配耗时如图3所示。实验表明，匹配成功率为100 %，单幅星图匹配耗时平均耗时0.072 6 s，最长耗时0.128 6 s。

4.2 实测星图实验

对100幅由某遥感卫星下传的连续星图进行同样的处理，统计匹配耗时，结果如图4所示。星敏感器部分性能参数见表3。

表3 某卫星星敏参数

提取星点个数在13～18之间。由于空间环境复杂，为保证匹配成功率，对星点的测量误差放大到1像素。实验表明，匹配成功率为100 %，匹配平均耗时0.089 9 s，最长0.206 5 s。

基于匹配结果，采用QUEST方法进行姿态解算，结果如图5。可以看出：3个姿态角变化平稳，基本呈线性，这与遥感卫星短时间内姿态变化缓慢是相对应的；同时也间接说明了匹配结果的正确性，因为如果存在误匹配的话，姿态角将会出现突变。

从以上2组实验可知，仿真实验和实测星图实验结果类似，均可实现100 %的准确率，且输出率可分别达到13 Hz左右和11 Hz左右，具有较好的实时性；同时说明仿真星图与实际星空较为符合，仿真过程较为合理，也验证了本文提出的星图匹配方法在实践中应用的可行性。

5 结束语

星图匹配是星敏感器定姿的基础，高效可靠的星图匹配算法是星敏感器实现实时、可靠地输出姿态的重要保证。基于K矢量查找法和四边形匹配法则，本文提出了一种匹配方法，并基于仿真星图和实测星图对方法进行了验证，结果表明该方法具有良好的实时性和准确性：在MATLAB2014a环境下，仿真星图和实测星图的匹配输出频率分别在13Hz、11Hz左右，均在10Hz以上，成功率100 %，具有较好的实时性和准确性，在效率更高的程序环境下会有更高的输出率。

[1] 张广军．星图识别[M].北京：国防工业出版社，2011:13-14.

[2]LIEBECC.Patternrecognitionofstarconstellationsforspacecraftapplications[J].IEEETransonAerospaace&ElectronicSystemMagazine,1993,8(1):31-39.

[3]LIEBECC.Startrackersforattitudedetermination[J].IEEETransonAerospaace&ElectronicSystemMagazine,1995,10(6):10-16.

[4] 蔡迎波，惠宝聚，孟士超.星图识别算法的设计与实现[J].光学与广电技术，2009，7(2)：37-39.

[5] 冉晓强，汶德胜，邱跃洪，等.一种新的三角形识别算法[J].光子学报，2009，38(7)：1867-1871.

[6]PADGETTC,KREUTZ-DELGADOK.Agridalgorithmforautonomousstaridentification[J].IEEETrans.onAerospaace&ElectronicSystems,1997,33(1):202-213.

[7] 唐武盛，杨建坤，文少军，等.全天自主星图识别网格算法问题分析与改进[J].激光与电子学进展，2016(2)：102-108.

[8] 许士文，李葆华，张迎春.用字符串匹配进行星图识别的导航库存储方法[J].哈尔滨工业大学学报，2005，37(6)：819-821.

[9] 李辉，王安国，张磊.改进金字塔算法用于小视场星图识别[J].应用光学，2013，34(2)：267-272.

[10]刑一凡，王建华.一种改进的基于奇异值分解的星图识别算法[J].智能计算机与应用，2014(2)：21-24.

[11]李立宏，张福恩，林涛.一种基于遗传算法的全天自主星图匹配算法[J].光电工程，2000，27(5)：15-18.

[12]马涛，孙红辉，肖松，等.基于BP神经网络的小样本星图识别算法[J].应用光学，2009，30(2)：252-256.

[13]邢飞，尤政，董瑛.基于导航星域和K矢量的快速星图识别算法[J].宇航学报，2010，31(10)：2302-2308.

[14]林涛，周建林，张钧萍，等.四边形全天自主识别算法[J].宇航学报，2000，21(2)：82-85.

[15]MORTARID,NETAB.K-vectorrangesearchingtechnique[EB/OL].(2015-06-30)[2016-07-21].https://www.researchgate.net/profile/D_Mortari.

A modified star map identification algorithm based onKvector

YUANXiaobo1,2,ZHANGChao1,2,SHIChunlin1,3

(1.Institute of Navigation & Aerospace, Information Engineering University, Zhengzhou 450001, China;2.Beidou Navigation Technology Collaborative Center of Henan, Zhengzhou 450001, China;3.Troops 61206, Beijing 100042, China)

In order to improve the accuracy and efficiency of identification of star map in the attitude determination of star sensors, the paper proposed a modified star map matching method based on Kvectorsearchingtechniqueandquadranglematchingalgorithm:firstly,theangulardistancebetweenstarsanditsrangewerematchedwiththeKvectorsearchingtechnique;secondly,anavstaridentificationalgorithmwasestablishedtodistinguishthenavstarbasedonanalgorithmofidentifier,andthengot4navstars;finally,theallfieldmatchingwasaccomplishedwiththe4navstarsbasedonquadranglematchingalgorithm.Experimentalresultshowedthattheproposedmethodwouldhaveagoodreal-timeperformanceandhighaccuracy.

star map identification; Kvector;quadrangle;identifiermatching

2016-08-29

国家自然科学基金项目(11373001，41504018)。

袁晓波(1992—)，男，江西宜春人，硕士研究生，研究方向为航天器定姿与自主导航。

张超(1972—)，男，吉林白城人，博士，教授，研究方向为天文测量与导航。

袁晓波，张超，时春霖.一种改进的基于K矢量的星图识别算法[J].导航定位学报,2017,5(2):55-59.(YUANXiaobo,ZHANGChao,SHIChunlin.AmodifiedstarmapidentificationalgorithmbasedonKvector[J].JournalofNavigationandPositioning,2017,5(2):55-59.)DOI：10.16547/j.cnki.10-1096.20170210.

P

A

2095-4999(2017)02-0055-05