基于QTM的导航星库划分方法

赵启坤，严小军

（北京航天控制仪器研究所，北京100039）

基于QTM的导航星库划分方法

赵启坤，严小军

（北京航天控制仪器研究所，北京100039）

为了提高星敏感器观测星的检索速度，提出了一种基于球面四元三角网（Quaternary Triangular Mesh，QTM）的导航星库划分方法。该方法首先利用天球的内接正八面体把全天球划分成8个子天区，然后在每个子天区中进行与经纬度相关的剖分和编码，最后扫描恒星星表，把每颗导航星信息划归到相应的子天区内存储。利用此星库进行的局部天球星图识别仿真实验表明该星库具有很高的检索效率。

星敏感器；导航星星库；球面四元三角网；星图识别

0 引言

在星敏感器星图识别中，合适的导航星库组织结构可以快速从导航星表中提取出需要检索的导航星信息，以提高星图识别效率。在组织导航星库时一般采取的方法是把天球按一定的规则划分成若干子区域，与某一子区域有关的识别模式用相应的数据文件分别存储或用数据文件的特定部分存储。然而目前主流的划分方法还存在两个不足：一方面各个子区域的覆盖面积的差异会导致各个子区域内导航星数目存在差别，导航星信息在各个子块中的搜索效率有较大差异；另一方面各个子区域缺乏高效的索引机制，赤经、赤纬与子区域地址码的转换比较繁琐，子区域的邻近索引不能直接利用地址码进行。

本文首先采用基于球面四元三角网的空间剖分方法对导航星库进行剖分，以保证剖分出的各个子块形状和面积基本相同；然后对各个子块进行与经纬度相关的编码，提高子块的检索效率和邻近搜索效率；最后利用局部天区星图识别算法对模拟的150幅星图进行识别，验证本方法的性能。

1 常用的导航星库划分方法

现有的导航星库划分方法主要有赤纬带法［1］、圆锥法［2］、球矩阵法［3］、内接正六面体法等方法［4］。各种划分方法和优缺点如表1所示。

表1　现有的导航星库划分方法Table 1 Star catalog partition methods

2 基于球面四元三角网（QTM）的导航星库划分方法

本文提出了一种基于球面四元三角网的导航星库划分方法，本方法主要包括以下几个步骤：天球剖分、利用QTM对剖分后的天区进行编码、利用QTM码在全天球范围内进行邻近检索。

2.1 天球剖分方法

1）用天球的内接正八面体把球面均匀的分成8个区域S1～S8［5］，每个子区域称为一个八分体，如图1所示。正八面体的6个顶点在天球坐标系中的坐标如表2所示。

图1　内接正八面体剖分球面Fig.1 Spherical facet based on octahedron

表2　正八面体顶点在天球坐标系中的坐标Table 2 Vertex coordinates ofregular octahedron in celestial coordinate system

正八面体各个边在天球上的投影与赤道、0°经线、180°经线、东经90°线、西经90°线重合，可以方便地确定天球上的某一点在哪个八分体上。

图2　三角形剖分示意图Fig.2 Triangle subdivisions

2）对于S1～S88个八分体，按照图2所示的方法将其划分为4N个小区域。整个天球就被划分为8×4N个小区域。

如图3所示，对球面三角形进行递归剖分的方法分为两种，一种是取大圆弧的中点（图3中的M1点）作为新剖分三角形的一个顶点，这种方法称为大弧平分法；另一种方法是取经纬线的中点（图3中的M2点）作为新剖分三角形的一个顶点，这种方法被称为经纬度平分法。大弧平分法得到的球面三角形比较均匀，形状、大小也最接近，缺点是计算比较复杂。经纬度平分法虽然在三角形的相似性上有一些损失，但是保证了数据与经纬度关联的特性，有利于数据的编码和索引。在导航星库中星的坐标都是与经纬度相关联的，因此为了快速索引导航星，本文采用经纬度平分法对球面三角形的各个面进行细分。

图3　大弧平分法和经纬度平分法Fig.3 The methods of triangulation

2.2 利用QTM对天球进行编码

在利用QTM对天球编码时，一个QTM位置码由一个八分码（0～7）和若干个四分码（0～3）组成。在第k个剖分层次，球面三角形A的编码可以表示为：a0a1a2…ak。其中，a0是八分码，a1～ak是k个四分码。

八分码a0代表8个八分体之一，这8个八分体的编码如图4所示。

图4　内接正八面体剖分球面的初始编码Fig.4 Initial partition and coding of spherical facet based on octahedron

四分码ak(k≥1)可以通过当前区域在其父区域中的相对位置来编码：0表示当前区域在其父区域的中间，该三角形区域称为中间三角形；1表示当前区域在其父区域的上面（或者下面），该三角形区域称为顶边三角形；2表示当前区域在其父区域的左边，该三角形区域称为左边三角形；3表示当前区域在其父区域的右边，该三角形区域称为右边三角形，如图5（a）所示。图5（b）是对为0的八分体作为初始球面三角形进行2次剖分后的QTM编码示意图。其余7个区域的剖分与0区域类似。

图5　QTM编码示意图Fig.5 Subdivision and QTM coding

2.3 QTM地址码与赤经赤纬的相互转换

天球上的每一个星点都由赤经、赤纬来确定位置，因此赤经赤纬与QTM编码之间的相互转换是完成星点快速搜索的关键。

在现有的QTM编码与赤经、赤纬的转换算法中，ZOT（Zenithal Ortho Triangular）投影法转换速度快，但生成的编码缺乏方向性；ETP（Equal⁃Triangles Projection）投影法生成的编码具有固定的方向性，但转换速度慢。赵学胜等提出的行列逼近法（Cavalcade Approach Method，CAM）［6］是一种从赤经、赤纬到QTM码的快速转换方法。该方法基于经纬度平分法，根据位置区域的行列以及地址码的方向进行层次递归，转换速度较快，因此本文选择行列逼近法进行QTM地址码与赤经、赤纬的相互转换。

2.4 基于QTM编码的邻近检索

在QTM格网中邻近三角形的定义为：具有公共边的为边邻近Edge⁃adjacent（三角形）；只具有公共顶点的为角邻近（也称为顶点邻近，Vertex⁃adja⁃cent）三角形。

（1）边邻近三角形的搜索

在QTM格网中所有三角形具有3个边邻近：左邻近三角形L（u）、右邻近三角形R（u）和顶（上或下）邻近三角形T（u），每种邻近又可以按照邻近的三角形是否在同一个八分体内分为两种情况。

下面以左邻近搜索为例介绍边邻近三角形的搜索算法，如图6所示。

图6　对八分体剖分两次的左邻域搜索示意图Fig.6 Searching sketch map of octant splited two times on the left neighborhood

如果左邻近三角形在同一个八分体内部：

1）如果当前三角形区域地址码的最后一位是0，也即当前三角形是其父三角形的中间三角形，其左邻近三角形为其父三角形的左边三角形；

2）如果当前三角形区域地址码的最后一位是3，也即当前三角形是其父三角形的右边三角形，其左邻近三角形为其父三角形的中间三角形；

3）如果当前三角形区域地址码的最后一位是1，也即当前三角形是其父三角形的顶边三角形，其左邻近三角形为其父三角形的左邻近三角形的右边三角形；

4）如果当前三角形区域地址码的最后一位是2，也即当前三角形是其父三角形的左边三角形，其左邻近三角形为其父三角形的左邻近三角形的顶边三角形。

如果左邻近三角形不在同一个八分体内部：

1）计算当前八分体左侧的八分体的八分码：

2）所有为2的四分码变为3，其余四分码保持不变：

这样就得到了三角形左邻近三角形的QTM编码，算法的流程图如图7所示。

对于右邻近和顶邻近搜索有类似的流程，在此不再赘述。

（2）角邻近三角形的搜索

三角形在八分体的最上、最左、最右侧时，角邻近三角形有7个，如图8（a）所示；在其他位置时，角邻近三角形有9个，如图8（b）所示。

对角邻近三角形搜索可以转换为边邻近三角形的搜索。以图8（b）为例，编号为1的三角形与当前三角形（U）的关系可以表示为：

式中，U1代表编号为1的三角形，U代表当前三角形，代表当前三角形的顶邻近三角形，代表当前三角形的左邻近三角形。

（3）对一个三角形的邻近搜索包括边邻近搜索和角邻近搜索

由图7和图8可知，三角形的边邻近搜索只是简单的二进制操作，而角邻近搜索可以转换为7个（或9个）边邻近搜索。因此，邻近搜索的效率非常高。已知一个天区的QTM编码时，可以通过邻近搜索算法迅速计算出与该三角形相邻的所有三角形的QTM编码。

图8　角邻近三角形Fig.8 Vertex⁃adjacent triangles

3 基于QTM划分的导航星库在星图识别中的应用与分析

以10°×10°的视场为例，利用QTM法划分导航星库，并基于划分后的星库做局部天区星图识别，以验证该划分方法的性能。

对每一个八分体Si利用经纬度平分法细分3次，全天球区域被划分成了512（8×43）个小三角形天区；扫描导航星库，将每颗导航星都划归到相应的子天区；按照QTM编码的方式为每一个天区建立如表3所示的索引表。

表3　天区索引表Table 3 Index of sub⁃sky

对其中一个八分体进行统计分析，球面三角形顶点之间夹角的最小值为11．25°，顶点与对边中点夹角的最小值为7．94°，如表4所示。因此，任意一个视场角小于15．88°×15．88°的视场都可以利用该视场中心所在的三角形天区及其12邻近（或10邻近）天区完全覆盖。

表4　八分体内三角形顶点夹角大小的统计分析Table 4 Statistic and analysis for the angles in octant

在载体运动角速度比较小时，利用上一时刻视轴的所在天区及其邻近天区中包含的导航信息组成实时导航星库；当载体运动角速度比较大时，利用之前几个时刻的视轴方向和运动信息估计当前时刻的视轴方向，组建实时导航星库。利用这种方法把星图识别的搜索范围缩减为整个导航星库的13/512≈2．5％。

采用QTM划分导航星库后，星图识别的流程如下：

1）第一帧星图的视轴方向由全天球星图识别计算得出（或者由程序给定）；

2）根据上一时刻的视轴方向或者之前几个时刻的视轴方向构建（或更新）实时星库；

3）利用实时星库，进行局部天区星图识别；

4）如果局部天区星图识别未能成功识别则转入全天球星图识别。

下面以三角形识别为例，对视轴为BoreSight1（Ra=282．09°，Dec=-28．77°，Roll=40．06°，10°×10°圆形视场，极限星等为6．0等）的视场分别采用全天球星图识别法与QTM划分导航星库的局部天区星图识别法进行识别以比较两种方法在识别效率上的差异，识别中星角距的匹配误差设置为0．001rad（0．057°）。在进行局部天区星图识别之前，首先对视轴为BoreSight0（Ra=280．60°，Dec =-28．95°，Roll=38．94°）的视场进行全天球星图识别以建立实时星库。

在BoreSight1视场中共有10颗导航星，选取其中最亮的3颗待识别星（S1、S2、S3）组成的3个待匹配星对和待匹配星三角形进行匹配，待匹配星对和待匹配星三角形的匹配结果如表5所示。

表5　对BoreSight1视场中最亮的三颗星进行识别的结果Table 5 Identify result of the three brightest stars in BoreSight1

由表5可以看出，采用QTM对导航星库进行划分后，一方面大大减少了与每个待匹配星对相匹配的星对数量；另一方面减少了待匹配三角形出现冗余匹配的可能性，算法的运行时间得以减少。

为了评价该星库的性能，在计算机上进行了仿真测试。测试时假设星敏感器初始姿态为Bore⁃Sight0（Ra=280．60°，Dec=-28．95°，Roll= 38．94°），第i时刻姿态为：

式中，j取0、1、2，分别代表视轴的Ra、Dec、Roll 3个方向；rand是范围为（-1°，1°）的随机数。

测试总共进行了150步，每一步都会根据当前的姿态产生一幅星图模拟星敏感器采集到的观测星图，测试结果如图9所示。

图9　150次星图识别所用时间Fig.9 Elapsed time of star identification

除去第1次识别采用全天球星图识别外，其余149次均用QTM分区的局部天区星图识别完成，证明了QTM分区、编码及邻域搜索算法的正确性。采用QTM分区的局部天区星图识别每次识别时间最短为0．34ms，最长为8．5ms，平均识别时间为1．9ms，且有84％的匹配时间小于2．0ms，相对于全天球星图识别来说识别时间少了1个数量级。以文献［4］为例，采用内接正六面体划分导航星表的改进三角形星图识别方法做一次全天球星图识别需要的平均时间为8．4ms。

4 结论

本文把球面四元三角网（QTM）引入到导航星库的划分中，提出了一种基于经纬度平分法的QTM导航星库划分方法，并采用行列逼近算法对各个天区进行编码。基于这种划分方法构造的导航星库继承了QTM划分均匀、编码方向一致、邻域搜索高效，经纬度平分法与经纬度高度相关，行列逼近法编码快速等特点。基于该星库进行的局部天区星图识别仿真试验也验证了这种方法的高检索效率。

［1］Bone J W．On⁃orbit star processing using multi⁃star star trackers［J］．Proceedings of the SPIE，1994：6⁃14．

［2］Ju G，Kim H，Pollock T，et al．Digistar：a low⁃cost micro star tracker［C］．AIAA Space Technology Conference＆Exposition，Albuquerque，1999．

［3］Roelof W H，Van B．True⁃sky demonstration of an auton⁃omous star tracker［J］．Proceedings of the SPIE，1994：204⁃216．

［4］张广军．星图识别［M］．北京：国防工业出版社，2011．ZHANG Guang⁃jun．Staridentification［M］．Beijing：Na⁃tional Defense Industry Press，2011．

［5］Randall D A，RinglerTD，HeikesRP．Climate modeling with spherical geodesic grids［J］．Computing in Science and Engineering，2002，4（5）：32⁃40．

［6］赵学胜，陈军．QTM地址码与经纬度坐标的快速转换算法［J］．测绘学报，2003，32（3）：272⁃277．ZHAO Xue⁃sheng，CHEN Jun．Fast translation algorithm between QTM code and longitude／latitude coordination［J］．Acta Geodaeticaet Cartographica Sinica，2003，32（3）：272⁃277．

［7］白建军，孙文彬，赵学胜．基于QTM的WGS⁃84托球面层次剖分及其特点分析［J］．测绘学报，2011，40（2）：243⁃248．BAI Jian⁃jun，SUN Wen⁃bin，ZHAO Xue⁃sheng．Charac⁃teranalysis and hierarchical partition of WGS⁃84 ellipsoidal facet based on QTM［J］．Acta Geodaetica et Cartographica Sinica，2011，40（2）：243⁃248．

［8］赵学胜，侯妙乐，白建军．全球离散格网的空间数学建模［M］．北京：测绘出版社，2007．ZHAOXue⁃sheng，HOUMiao⁃le，BAIJian⁃jun．Spatialdata modeling based on global discrete grid［M］．Beijing：Surveying and Mapping Press，2007．

［9］孔祥元，郭际明，刘宗全．大地测量学基础［M］．武汉：武汉大学出版社，2001．KONG Xiang⁃yuan，GUO Ji⁃ming，LIU Zong⁃quan．Foun⁃dationofgeodesy［M］．Wuhan：WuhanUniversity Press，2001．

A Method for Guide Star Catalog Partition Based on QTM

ZHAO Qi⁃kun，YAN Xiao⁃jun
（Beijing Institute of Aerospace Control Devices，Beijing 100039）

In order to improve the efficiency of star sensor during retrieving the guide star，a method for star catalog partition which based on quaternary triangular mesh was proposed．The approach first utilizes the regular inscribed regular octahedron in the celestial sphere and divided the sphere into eight sub regions，then split and encoded in each sub regions associated with the latitude and longitude，finally scanning the guide star database，each navigation information was storage in the corresponding sub region．The star identification used this star catalog shows that the designed star catalog has high retrieval efficiency．

star sensor；guide star catalog；quaternary triangular mesh（QTM）；star identification

U666．1

A

1674⁃5558（2016）03⁃01223

10．3969／j．issn．1674⁃5558．2016．06．014

2016⁃01⁃04

赵启坤，男，硕士，导航、制导与控制专业，研究方向为星光组合导航技术。