基于三角形匹配的星图识别算法及优化

2018-04-07李保权

电子设计工程 2018年5期

郭磊，李保权，曹阳，桑鹏

（1.中国科学院国家空间中心北京100190；2.中国科学院大学北京100190）

星敏感器是以恒星为参照物进行姿态测量的敏感设备，它通过观测天球上的恒星位置来确定飞行器相对于天球坐标系的三轴姿态，为飞行器姿态控制系统提供准确的依据[1]。由于恒星的张角很小（最大恒星的张角为0.05角秒，一般在毫角秒量级），并且恒星的影像是在真空中提取的恒星赤经赤纬又是精确已知的，所以星敏感器称得上是航天器中绝对姿态测量精度最高的设备[2]。对于姿态精度要求较高的飞行器，星敏感器有着不可替代的作用。星敏感器的工作过程主要包括星表的预处理，星象检测，星图识别，以及姿态获取。而整个算法的核心即是星图识别，星图识别的效率和正确率直接决定了整个星敏感器的工作性能。目前，已经出现的星图识别算法有三角形算法，匹配组算法，栅格算法，多边形角距算法，奇异值分解算法，神经网络算法和遗传算法等[3]。真正应用比较成熟且经过工程验证识别效果的是三角形算法。三角形算法是最早的星图识别算法的变体，属于子图匹配方法家族的成员，它试图匹配一个由观测星点作为3个顶点构建的三角形[4]。由几何知识我们知道全等三角形可以用两种方法验证：边角边或者边边边。使用边角边时，可以计算三角形两边的长度和它们之间的夹角，并与星表中的条目相比较，由正弦定理可知，角度与对应边长成正比，本质上还是边边边；边边边则是用到三角边的长度，采用这种方法，星表需要包含在整个夜空中能观察到的所有恒星组成的三角形的信息，星表中存储的三角形的数目与星敏感器传感器的敏感度和相机的FOV成比例，对于性能较好的传感器，星敏感器的精度更高，星表中存贮的信息会非常多，这样需要很长的搜索时间[5]。因此优化星表很有必要，一个例子就是在图像中选择最亮的3个星点组成的三角形进行匹配，而不是随机选择3个星点。然而为了增加精度，更为理想的做法是将星图中的所有三角形都进行匹配，而不仅仅是一个三角形[6]。亮度信息可以存储在星表中加速星表搜索。由于测量误差的存在，当搜索匹配的三角形时需要一定的容错度，但容错度会导致一些三角形匹配错误，为了防止这种情况的发生，需要验证匹配的方法，或者对于每个匹配的三角形尝试匹配邻近的第4个亮点[7]。

1 导航星库制作

导航星库包括两部分，一个星列表和星对距离列表。这两个列表通过程序生成并存储在星敏感器的缓存中。下面介绍两个星表的内容：星列表包含所有亮度高于某个规定星等的恒星，在我们设计的星敏感器中该星等阈值定为5.75，但同时存储了星等高于7等的所有恒星，并在程序中预留好接口，通过发送指令可以随时修改阈值。星列表条目包括每颗恒星的ID，赤经赤纬，以及星等。星表原始数据来源第谷星表经过程序处理后，剔除了所有亮度低于5.75星等的恒星。接下来又将每颗恒星的赤经赤纬都变换成了迪卡尔ECI单位适量下的坐标值[8]。除此之外，包括第谷星表在内的大多星表一般只给了恒星在J2000.0历元的平位置（平赤经和平赤纬），而我们观测的恒星位置则是恒星的地心真赤道视位置坐标，由于恒星的自行，地球的岁差章动等等影响，这两种坐标有些许的差异[9]。为了使得到的结果更加准确，我们对第谷表中的恒星在J2000.0历元的平位置进行了修正，加上了自行改正，周年视差改正，光行差改正，岁差和章改正之后，得到了恒星地心真赤道坐标[10]。星列表部分如图1所示。

图1 星列表存储结构

星表的第二部分为星对的间距表，为获得此表，需计算3 999颗恒星中每两个恒星之间的距离，计算公式如下：

其中x，y，z为恒星Si和恒星Sj在ECI单位向量上的分量。

1）间距表中的每个条目由两颗恒星的序号和他们之间的角距（弧度）组成，并按角距的升序排列。为保持恒该星表的简洁高效，需注意以下几点：

2）每个恒星对只算做一个条目，与恒星的顺序无关。

3）仅当星间距小于星敏感器的视场角时将恒星对列入表中。

4）仅在星间距足够大，两颗恒星能被独立识别时，将恒星对列入表中[11]。

5）当星间距过小时可以视为一颗恒星也可以视为两颗恒星，且当相距7个像素的恒星对则应被视为各自独立[12]。

6）充分利用星表中恒星ID不太大的特点，用short类型取代int，即一个整数可以表示两个恒星ID（高16位a1，低16位a2），一方面减少星表体积，另一方面提高了cache命中率，从硬件层面上提高算法效率。

7）星间距表的最终版本包括119570个条目，第一列中整数表示一个星对（a1，a2），第二列表示相互之间角距大小。如图2所示。

图2 星间距表存储结构

2 算法描述

通常三角形识别过程是，从待测星图中取出三个恒星点，组成三角形，例如图3中（ABC），每条边（AB，AC，BC）对应在星间距列表中找到对应的间距范围（a1，a2）（b1，b2）（c1，c2）。这其中，由于星间距对排列是按照是恒星间的角距大小升序排列的，所以直接用二分法就可以在O（log（n））的时间复杂度下找到对应的角距大小的上下限[13]。本文中为了进一步提高整体算法运行效率，且由于此查询算法调用次数较多，所以决定用哈希表实现导航星表中恒星对间距与下标之间的对应，这样即可以在O（1）的时间复杂度下找到对应上下限。

由三角形几何性质可知，三角形匹配本质上是寻找（a1，a2）（b1，b2）（c1，c2）边之间的首尾相相接，也即是三个星对之间ID值首尾相同即可，传统匹配算法即是利用三个集合之间星对坐标进行两两比对，假定AB对应的恒星对（a1，a2）数量为n1，AC对应的恒星（b1，b2）数量为n2，BC对应的恒星对（c1，c2）数量为n3。比对过程即是，各个坐标对进行比对；易知只需要进行比23的次数，时间复杂度为O（n1）*O（n2）*O（n3），如图1所示[14]；再加上后来的四面体顶点检验以及其余待测星点验证，三角形匹配调用次数有可能会达到数十次，显然此时效率远不能达到项目要求。

图3 传统三角形匹配过程

文中即对此进行了针对性优化：降低时间复杂度；由数据结构知识可知，遍历是相当低效的；改变的方式包括排序后二分查找，或者哈希表定位[15]。本文两种方法都用到了，具体做法是利用哈希表存储（a1，a2）星间距对，由于可能有（a1，a3）或者（a2，a3）的出现，故选择用拉链法处理冲突，处理如图4所示。由于hashtable原来为NULL，所以当hashtable[b1]!=NULL时，即b1与a1相同。接下来只需要比较b2a2是否与c1c2或c2c1相等即可。为提高效率，避免盲目遍历，先进行快速排序然后进行二分查找。这两个函数都可以直接调用库函数，不用手动实现。计数排序是目前最快排序，但由于数值较大，排序所需空间复杂度会很可观，故放弃使用[16]；易知新算法时间复杂度为O（nlogn）远小于原来的O（n3）。

图4 存储星对的hashtable

由于三角形特征维数少，冗余匹配和和错误匹配很难避免，故引入第四颗星，即图5中D星，在已识别的三角形ABC中，通过对AD和BD的检索来验证D星点，成功识别三角形ABD[17]。接着在对AD和CD进行同样检索，成功识别三角形ACD。由于D是同一顶点，此时实际上是一个四面体。由此便可以大大降低匹配冗余率和错误率，接着为了进一步确定导航三角形，进入验证识别环节，对待测星表中余下的潜在星点，逐一进行四面体验证检测，如图5所示。最后为避免极端镜像情况出现，又对三角形的三边顺序利用向量乘积的大小进行验证。待测星图中与导航星图中的大小值完全一样即可避免三角镜像情况的出现，进一步降低了匹配错误率[18]。

星图识别总的流程如图6所示。

3 结果分析

将文献中的传统三角形算法和本文中提出的改进算法分别编程实现，并对500幅实拍星图进行匹配验证，在匹配门限为0.02°时原始算法的成功匹配率即给出正确姿态角的比例是76.8%（384/500）；而改进后的正确率达到99.2%（496/500）；在匹配门限为0.04°时原始算法的成功匹配率即给出正确姿态角的比50.2%（251/500）；而改进后的正确率达到96.4%（488/500）；并且在ubuntu系统下CPU 1.8 GHz，内存2G平均时间由原来的4 s左右降到目前的3 ms左右；其中随机一幅星图的匹配结果如图7所示。

从图7可以看到，在加了像素阈值的限制后，匹配更加精确甚至可以达到完全匹配；在提供姿态角都是正确结果的前提下，算法效率有了质的提高。