基于特征图形匹配法的高效星图识别方法

李超兵，袁艳艳，王丹晔

北京航天自动控制研究所，北京 100859



基于特征图形匹配法的高效星图识别方法

李超兵*，袁艳艳，王丹晔

北京航天自动控制研究所，北京 100859

针对目前星敏感器使用的星图识别算法存在的冗余匹配、匹配时间长、识别率低等缺点，对星图识别算法进行了研究，提出了一种高效星图识别方法。该算法首先对传统星表进行处理，取出冗余信息，重新分配天区，使每个天区的导航星数目均匀，将分区以及处理后的星表信息重新存储并作为导航星库，然后通过对拍摄的图像进行处理并提取特征信息，与导航星库中的特征信息进行匹配，从而改善传统星图匹配算法出现冗余匹配、匹配时间过长及识别率低等缺点。完成算法设计后，选取视场为15°×15°的大视场星敏感器，对该算法进行仿真验证分析，可以发现该算法可以实现部分天区与拍摄星图匹配时间在20 ms以内，全天区星图的识别和匹配时间在1.5 s以内，识别率达到98%以上，印证了该算法可以提高识别的成功率并且缩短识别时间，使识别算法具有高效性。

星图识别；星表重构；图像处理；特征图形匹配；星敏感器；全天区

星敏感器作为姿态测量工具如今已经越来越广泛地应用于航天器中，星敏感器的发展越来越快，从早期星敏感器到第一代电荷耦合元件(Charge Coupled Device，CCD)星敏感器，然后发展到近期的第二代CCD星敏感器，目前研究正处于第二代CCD星敏感器和互补金属氧化物半导体(Complementary Metal Oxide Semiconductor，COMS)星敏感器的过渡时期，因此针对星敏感器的星图匹配算法也正迅速发展。星图识别的过程是：首先进行图像采集以及图像的预处理，然后对处理后的星图进行特征图形提取，最后将拍摄星图的特征图形与图库中的特征图形进行识别匹配[1]。

常用的面向星敏感器的星模式识别算法主要包括：对角距匹配算法、三角形角距匹配算法、多边形角距匹配算法、栅格算法、主星识别法及概率统计算法等。其中，应用最为广泛的是三角形角距匹配算法和主星识别算法，三角形角距匹配算法在实际使用当中相对容易，但是识别过程中采用的特征维数较少，会出现冗余匹配的情况；主星识别法在进行的过程当中不需要进行重复匹配，识别速度快，但是如果视野中有很多颗星星等相近时，会使识别成功率严重降低[2]。为了解决三角形角距匹配算法的搜索效率，在三角形匹配算法基础上，提出了K矢量算法、B矢量算法以及P矢量算法。这些方法提高了识别速度、识别成功率，具有对噪声的鲁棒性，占用内存比较小。近些年来发展起来的算法主要有：基于奇异值分解算法、基于遗传算法的方法和基于神经网络的算法等较新的星模式识别算法。但是这些算法实现起来比较复杂，而且需要的学习时间很长，无法在星敏感器中直接使用。

本文所设计的基于特征图形匹配的星图识别算法将特征图形匹配应用到星图识别算法中，使算法具有较高的识别率，而且通过对星表冗余信息的处理，提高识别效率，使得该算法具有高效性，具有广泛的应用前景。

1　星敏感器测星信息处理

1.1导航基本星表的选择以及重构

导航星表是星图匹配算法的基础，但是传统的导航星表导航星数目众多，会导致巨大的计算量，不利于算法的实时性[3]。因此，需要从基本星表中挑选出一部分具有代表性的导航星，利用其位置和亮度信息编制而成简易且高效的导航星表，这样可以令星图匹配算法的计算量减小，提高计算的效率。

目前在航天领域应用的星表多为编制星表，例如：史密松天体物理天文台星表(SAO)、第五基本星表(FKS)以及亮星星表(BSC)、导引星表(GSC)等。

卫星导航任务经常采用SAO星表，SAO星表中记录了大概26万颗恒星的信息，位置精度高，因此本文选择SAO星表作为基本星表。SAO星表采用二进制格式进行存储，每行数据的具体格式如表1所示。

表1　SAO星表数据格式

为了减少子星表的容量，需要对观测星进行处理，目前国内主流星敏感器大部分能观测到6.5星等的恒星，那么就按6.5的星等对星表过滤，提取星等达到6.5的9 040颗星的赤经、赤纬等信息就成了所需的参考星表。给定一个视场，只需要根据赤经、赤纬查找落于该视场内的星即可。处理后的星表包含的信息为：恒星编号、赤经、赤纬、星等4部分信息。

对于不同的星图匹配方法，星表的存储方法也不同，现有的存储方法主要有赤纬带法、重叠区域法、球矩阵法、重叠的球矩阵法等，由于这几类导航星表划分方式存在星点分布不均匀等问题，所以本文采用内接正方体星表划分方法。该方法的划分步骤具体如下：

(1)

其他5个天区的中心轴线和4个边界点的方向矢量依此类推。

图1　天区划分Fig.1　Area division

2)如图1(b)、(c)所示，将每一个大天区均匀地划分成N×N的小天区。这样整个天球球面将被划分为6个大天区、6×N×N个小天区，大小为(90/N)×(90/N)。

按照上述步骤划分天球并扫描每个天区的导航星，建立分区导航星表，记录每颗导航星的信息。

应用内接正方体星表划分的方法，将全天星图划分成6个区域，生成6个天区星表，每个星表的经纬度范围划分如表2所示。

表2　星表经纬度范围

依据该经纬度范围，得到6个导航星表。这种划分方法可以保证天区划分的均匀性。

然后再将每个天区分为6×6个子块，进一步减少所需存储空间，也使星图识别的匹配速度提高，除此之外还需要对导航星进行筛选，在保证星图识别准确性前提下尽量减少导航星数量。筛选原则如下：在每个子星表中选取最亮的6颗导航星，如果子星表中的导航星数目小于6，则不做任何处理。由于变光星的亮度不稳定，不适于作为导航星，因此需要将变光星剔除；除此之外，还需要考虑到每个子星表中任意两颗导航星之间的星光角距不易太小，因为距离太近的导航星可能引起误匹配，所以将星光角距小于阈值(0.1°)的导航星排除掉。经过筛选后的天区，导航星的分布变得更加均匀，有益于提高星图匹配的速度。

1.2拍摄图像预处理方法

星敏感器在天空中运作时，在特定天区所拍摄到的星空图片，要先进行星图处理，因此本节将介绍关于星图处理的基本方法。星图处理主要步骤包括灰度化、反白和拉伸3个步骤，具体过程如下：

(1)灰度化

灰度化就是将原来的32位彩色图像转变为8位的灰度图像。灰度图像占存储空间更小，便于以后进行处理。

(2)反白

反白的目的就是使图像中的黑色与白色进行转换，从而使星点的颜色偏黑，而背景的颜色偏白，这样可以方便后续的处理。图2给出了经过灰度化及反白处理后的部分大熊座。

图2　经过灰度化及反白处理后的部分大熊座Fig.2　Photo of Ursa after being grayed and inversed

(3)拉伸

拉伸处理可以有效地去除冗余信息、凸显有效信息，让图像中的星点更容易提取出来。拉伸处理的方法很多，这里主要介绍指数拉伸。

指数是对低灰度值进行压缩、对高灰度值进行拉伸，并会将所有灰度值小于某给定数值a的点的灰度值均变为1。示意如图3所示，其中x轴表示原图灰度值，y轴表示进行变换后的灰度值。计算公式如下：

(4)

式中：x为该点的灰度值。a、b、c用于调整曲线的位置和形状。

图3　指数拉伸示意Fig.3　Index stretching schematic diagram

经过多次试验最终选取参数值a=128、b=1.3、c=1.15。

接下来以狮子座的图片为例进行仿真。首先将拍摄的图片进行星图处理，拍摄的图片如图4所示，经过星图处理后的图片如图5所示。

图4　狮子座拍摄星图Fig.4　Photo of Leo

图5　狮子座处理后的星图Fig.5　Star catalog of handled Leo

然后将图像处理后的星图转变成为矩阵，将其中灰度值大于21的点，以数字0表示，灰度值小于20的点用数字1表示。

2　特征图形匹配算法

在进行天文导航时，如何将星敏感器拍摄到的星图与被导航星图特征正确匹配是天文导航研究的重点，星图匹配结果的好坏直接影响导航精度[4]。特征图形匹配包括特征图形矩阵的构造和特征图形匹配两部分，下面分别给出特征图形矩阵的构造方法及特征图形匹配方法的具体步骤。

2.1特征图形的构造及匹配

飞行器在太空中工作时，由于空间环境复杂，导航相机经常处于晃动状态，所拍摄到的星空图片有可能会存在畸变现象。为了解决这个问题，本文通过图论的基本原理构造特征图形。由于图论对于图形矩阵的表述方法是根据特征点之间的连通关系构建特征图形矩阵，而图形畸变不会改变特征点的连通关系。

图论的基本原理为：由n个特征点构成的图形，图形矩阵g中的第i行、第j列元素表征为第i个点与第j个点间的连通关系，若第i个点与第j个点是连通的，则图形矩阵中g(i,j)=1，若第i个点和第j个点不连通，则图形矩阵中g(i,j)=0。

(5)

由图论的基本原理可知，特征图形矩阵构建的关键在于特征点之间连通关系的确定，本文采用下面的方法建立图形特征点之间的连通关系[5-7]。

由于星点之间相对角距保持不变，可据此建立星点之间的角距矩阵：

(6)

矩阵D中的元素di,j表示第i个星点与第j个星点之间的角距，数学表示如下：

(7)

式中：si、sj为星点方向矢量。

(8)

对计数矩阵Cd每一列中的最大的元素进行筛选、排序，按筛选出的列最大元素的大小确定特征点之间的连通关系，即在图片Pn中，将最大的元素所对应的特征点与次最大元素所对应的特征点之间连通，以下依次连通下去。列最大元素如果小于2/3特征点个数，其所对应的特征点予以剔除，该连通规则考虑到了特征点之间的位置关系，又避免了由于个别特征点误匹配造成的匹配误差[8-10]。图片Pm中特征点的连通方法与此相同，下面给出连通规则的数学表述：

(9)

(10)

对ck序列按照从大到小的顺序排序[11-12]，以i表示图片Pn中的第i个特征点，记为nk；以j表示图片Pm中的第j个特征点，记为mk。ck序列排序结果如下：

(11)

从ck中就可以得到待匹配星点与导航星的一一对应关系，即图片Pn中的第na个特征点对应图片Pm中的第ma个特征点，以此类推，就可以得到待匹配星图中的星点与导航星图中的导航星的对应关系，从而实现了星图匹配的目的[13-15]。

2.2仿真算例及分析

由于选取的视场内的星点数对匹配时间和匹配成功率有一定影响，对此，针对选取不同特征星点数量进行仿真，观察算法的成功率以及运算时间。

表3　不同星点数运算时间与匹配成功率

通过表3可以看出，在选取的星点数目大于或等于6时，成功率为100%，并且星点数目越多，运算时间越长，因此选取星点数目为6可以使算法具有高效性。

对一天区中0°～E45°，0°～S35.264 4°范围内的9个子星表进行星图匹配仿真，仿真结果如图6～图7所示。

图6　星图数据库图片Fig.6　Picture of star catalog database

从每个子天区中提取最亮的6个星点构成特征图形与一天区的导航星表进行星图匹配，其中图6为该区域星表图片，图7为待匹配星图与导航星表子天区的匹配仿真结果。从仿真结果可以看出，9个子天区提取的6个特征点全部可以在导航星图中找到与之匹配的特征图形，并且匹配结果符合实际情况。

以一天区为例，进行星图识别仿真试验，取一天区36个子星图作为待匹配星图，以精简后一天区星表为待匹配数据库，进行仿真试验，仿真结果如表4所示。

图7　星图匹配仿真结果Fig.7　Simulation results of star map matching

星敏感器精度/(″)匹配成功组数试验组数成功率/%1036361001003636100200353697.22300333691.67400303686.11500253669.44

从以上的仿真试验中可以看出，当星敏感器测量误差在100″以内时，正确率可以达到100%。星敏感器的测量误差超过500″时，特征图形匹配算法的正确率会迅速下降。目前国内星敏感器的测量精度可以达到10″，因此，特征图形算法完全可以满足需求。

选取不同的拍摄照片噪声水平进行仿真，通过表5中，可以看出当噪声为50″以内时，匹配成功率依然符合要求，当图片噪声大于50″时，匹配成功率下降，因此设置拍摄照片噪声阈值为50″。

表5　不同拍摄噪声对应算法正确率

从以上仿真可以看出，特征图形匹配效果很好；并且能实现局部天区(15°×15°)的匹配时间在20 ms以内，全天区的识别和匹配时间在1.5 s以内，在识别时间与精确程度上高于传统方法，故该方法能够高效地实现识别任务。

3　结束语

本文的主要目标是对星敏感器星图匹配技术开展研究,完成导航星表的构建与处理方法设计、容错高效星图匹配算法设计，为天文导航提供星光矢量信息。

本文在SAO基本星表的基础上，利用内接正方体法划分天区，保证了天区划分的均匀性，在此基础上进行了合理的精简，设计出了实用高效的导航星表。

本文利用指数拉伸的方法，将经过灰度化和反白的拍摄星图合理地转换为数字星图，从而提取出图片中的星点信息，然后利用所得到的星点信息，组成特征图形矩阵，进行星图匹配，完成了容错性高，实时性良好的星图匹配算法设计，得到了较好的仿真分析结果，完成了导航解算的任务，证明了基于特征图形匹配的天文导航方法高效性。

References)

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

XING Y F， WANG J H. An improved star recognition algorithms based on singular value method[J].Intelligent Computer and Applications，2014，4(2)：21-24，28(in Chinese).

[2]张磊，何昕，魏仲慧，等. 基于星图识别的空间目标快速天文定位[J]. 光学精密工程，2014，22(11)：3074-3080.

ZHANG L，HE X，WEI Z H，et al. Fast celestial positioning for space objects based on star identification[J]. Optics and Precision Engineering，2014，22(11)：3074-3080(in Chinese).

[3]徐韬祜，孙华燕，张廷华，等. 基于星图模拟的星空目标提取[J]. 激光与红外，2015，45(1)：104-108.

XU T H，SUN H Y，ZHANG T H，et al. Space target extraction in star background image based on star image simulation[J]. Laser & Infrared，2015，45(1)：104-108(in Chinese).

[4]穆荣军，高铭阳，刘斌，等. 探月飞行器软着陆光学自主导航的特征图形匹配方法研究[J]. 空间科学学报，2014，34(6)：858-866.

MU R J，GAO M Y，LIU B，et al. Research on characterized graphics matching method of autonomous optical navigation for lunar explorer[J]. Chinese Journal of Space Science，2014，34(6)：858-866(in Chinese).

[5]刘晓平，何士双. 基于三角划分的多连通域图形匹配研究[J]. 工程图学学报，2010，31(1)：61-66.

LIU X P，HE S S， Research on graphics matching of multiply connected region based on triangulation[J]. Journal of Engineering Graphics，2010，31(1)：61-66(in Chinese).

[6]施航，朱志刚. 星敏感器星图处理研究[J]. 光学与光电技术，2014，12(6)：58-60.

SHI H，ZHU Z G. Image processing of star sensor[J]. Optics& Optoelectronic Technology，2014，12(6)：58-60(in Chinese).

[7]崔祥祥，王宏力，王永胜，等. 组合星图技术中的双星敏感器安装角度分析[J]. 光电工程，2013，40(12)：49-53.

CUI X X，WANG H L，WANG Y S，et al. Mounting angle between two star trackers in combined images technique[J]. Opto-Electronic Engineering，2013，40(12)：49-53(in Chinese).

[8]李旻珺，杨博，胡静. 星光折射导航星的改进三角识别捕获[J]. 航天控制，2012，30(1)：33-39.

LI M J，YANG B，HU J. The capture of grazing star based on the modified triangle identification algorithm[J]. Aerospace Control，2012，30(1)：33-39(in Chinese).

[9]陆敬辉，王宏力，孙渊，等. 应用相近模式向量的主星星图识别算法[J]. 红外与激光工程，2011，40(1)：164-168.

LU J H，WANG H L，SUN Y，et al. Main star identification algorithm based on similar pattern vectors[J]. Infrared and Laser Engineering，2011，40(1)：164-168(in Chinese).

[10]HO KOKI，NAKASUKA SHINICHI. Novel star identification method combining two star trackers with extended FOVs[C]. AIAA Guidance， Navigation，and Control Conference，August 2-5，2010，Toronto，Ontario，Canada.

[11]HASHMALL JOSEPH A. Star identification using a triplet algorithm[C]. 54th International Astronautical Congress of the International Astronautical Federation，the International Academy of Astronautics，and the International Institute of Space Law，September 29-October 3，2003，Bremen， Germany.

[12]KUMAR MRINAL，MORTARI DANIELE，JUNKINS JOHN. An analytical approach to star identification reliability[C]. AIAA Guidance， Navigation and Control Conference and Exhibit，August 18-21，2008，Honolulu，Hawaii.

[13]ROBERTS PETER，WALKER RODNEY. Application of a counter propagation neural network for star identification[C]. AIAA Guidance，Navigation，and Control Conference and Exhibit，August 15-18，2005，San Francisco，California.

[14]NEEDELMAN DAVID D，ALSTAD JAMES P，LAI PETER C，et al. Fast access and low memory star pair catalog for star pattern identification[J]. Journal of Guidance，Control，and Dynamics，2010，33(5)：1396-1403.

(编辑：车晓玲)

An efficient stellar map identification method based on characterized graphics matching method

LI Chaobing*，YUAN Yanyan,WANG Danye

Beijing Aerospace Automatic Control Research Institute，Beijing 100859，China

Nowadays, star pattern recognition methods used on star sensors have shortcomings of redundancy match, matching slow, low recognition rate，and so on. To overcome this，the star pattern recognition algorithm was studied，and a new algorithm was proposed. Firstly, redundancy information from traditional star catalog was extracted. The sky coverage was divided to make sure that different sky coverage has the similar navstar number. Secondly，feature information from the photo was extracted to match the feature information database. After the algorithm was designed, the star sensors with the field of view 15°×15° were selected and simulated. Simulation results show that the matching of the whole sky can be finished in 1.5 s by this algorithm, and the success rate can reach over 98%.

staller map identification；staller table reconstruction；image processing； characterized graphics matching； star sensor；whole sky coverage

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

2016-04-20；

2016-06-02；录用日期：2016-06-30；

时间：2016-08-0214:20:13

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

李超兵(1981-)，男，硕士，高级工程师，lcbpku@163.com，主要研究方向导航制导与控制

V249.32+3

A

http:∥zgkj.cast.cn

引用格式：李超兵，袁艳艳，王丹晔.基于特征图形匹配法的高效星图识别方法[J].中国空间科学技术，2016，36(4)：9-16.LICB，YUANYY,WANGDY.Anefficientstellarmapidentificationmethodbasedoncharacterizedgraphicsmatchingmethod[J].ChineseSpaceScienceandTechnology， 2016，36(4)：：9-16 (inChinese).