趙啟坤，嚴(yán)小軍

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

基于QTM的導(dǎo)航星庫劃分方法

趙啟坤，嚴(yán)小軍

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

為了提高星敏感器觀測星的檢索速度，提出了一種基于球面四元三角網(wǎng)（Quaternary Triangular Mesh，QTM）的導(dǎo)航星庫劃分方法。該方法首先利用天球的內(nèi)接正八面體把全天球劃分成8個子天區(qū)，然后在每個子天區(qū)中進(jìn)行與經(jīng)緯度相關(guān)的剖分和編碼，最后掃描恒星星表，把每顆導(dǎo)航星信息劃歸到相應(yīng)的子天區(qū)內(nèi)存儲。利用此星庫進(jìn)行的局部天球星圖識別仿真實(shí)驗(yàn)表明該星庫具有很高的檢索效率。

星敏感器；導(dǎo)航星星庫；球面四元三角網(wǎng)；星圖識別

0 引言

在星敏感器星圖識別中，合適的導(dǎo)航星庫組織結(jié)構(gòu)可以快速從導(dǎo)航星表中提取出需要檢索的導(dǎo)航星信息，以提高星圖識別效率。在組織導(dǎo)航星庫時(shí)一般采取的方法是把天球按一定的規(guī)則劃分成若干子區(qū)域，與某一子區(qū)域有關(guān)的識別模式用相應(yīng)的數(shù)據(jù)文件分別存儲或用數(shù)據(jù)文件的特定部分存儲。然而目前主流的劃分方法還存在兩個不足：一方面各個子區(qū)域的覆蓋面積的差異會導(dǎo)致各個子區(qū)域內(nèi)導(dǎo)航星數(shù)目存在差別，導(dǎo)航星信息在各個子塊中的搜索效率有較大差異；另一方面各個子區(qū)域缺乏高效的索引機(jī)制，赤經(jīng)、赤緯與子區(qū)域地址碼的轉(zhuǎn)換比較繁瑣，子區(qū)域的鄰近索引不能直接利用地址碼進(jìn)行。

本文首先采用基于球面四元三角網(wǎng)的空間剖分方法對導(dǎo)航星庫進(jìn)行剖分，以保證剖分出的各個子塊形狀和面積基本相同；然后對各個子塊進(jìn)行與經(jīng)緯度相關(guān)的編碼，提高子塊的檢索效率和鄰近搜索效率；最后利用局部天區(qū)星圖識別算法對模擬的150幅星圖進(jìn)行識別，驗(yàn)證本方法的性能。

1 常用的導(dǎo)航星庫劃分方法

現(xiàn)有的導(dǎo)航星庫劃分方法主要有赤緯帶法［1］、圓錐法［2］、球矩陣法［3］、內(nèi)接正六面體法等方法［4］。各種劃分方法和優(yōu)缺點(diǎn)如表1所示。

表1　現(xiàn)有的導(dǎo)航星庫劃分方法Table 1 Star catalog partition methods

2 基于球面四元三角網(wǎng)（QTM）的導(dǎo)航星庫劃分方法

本文提出了一種基于球面四元三角網(wǎng)的導(dǎo)航星庫劃分方法，本方法主要包括以下幾個步驟：天球剖分、利用QTM對剖分后的天區(qū)進(jìn)行編碼、利用QTM碼在全天球范圍內(nèi)進(jìn)行鄰近檢索。

2.1 天球剖分方法

1）用天球的內(nèi)接正八面體把球面均勻的分成8個區(qū)域S1～S8［5］，每個子區(qū)域稱為一個八分體，如圖1所示。正八面體的6個頂點(diǎn)在天球坐標(biāo)系中的坐標(biāo)如表2所示。

圖1　內(nèi)接正八面體剖分球面Fig.1 Spherical facet based on octahedron

表2　正八面體頂點(diǎn)在天球坐標(biāo)系中的坐標(biāo)Table 2 Vertex coordinates ofregular octahedron in celestial coordinate system

正八面體各個邊在天球上的投影與赤道、0°經(jīng)線、180°經(jīng)線、東經(jīng)90°線、西經(jīng)90°線重合，可以方便地確定天球上的某一點(diǎn)在哪個八分體上。

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

2）對于S1～S88個八分體，按照圖2所示的方法將其劃分為4N個小區(qū)域。整個天球就被劃分為8×4N個小區(qū)域。

如圖3所示，對球面三角形進(jìn)行遞歸剖分的方法分為兩種，一種是取大圓弧的中點(diǎn)（圖3中的M1點(diǎn)）作為新剖分三角形的一個頂點(diǎn)，這種方法稱為大弧平分法；另一種方法是取經(jīng)緯線的中點(diǎn)（圖3中的M2點(diǎn)）作為新剖分三角形的一個頂點(diǎn)，這種方法被稱為經(jīng)緯度平分法。大弧平分法得到的球面三角形比較均勻，形狀、大小也最接近，缺點(diǎn)是計(jì)算比較復(fù)雜。經(jīng)緯度平分法雖然在三角形的相似性上有一些損失，但是保證了數(shù)據(jù)與經(jīng)緯度關(guān)聯(lián)的特性，有利于數(shù)據(jù)的編碼和索引。在導(dǎo)航星庫中星的坐標(biāo)都是與經(jīng)緯度相關(guān)聯(lián)的，因此為了快速索引導(dǎo)航星，本文采用經(jīng)緯度平分法對球面三角形的各個面進(jìn)行細(xì)分。

圖3　大弧平分法和經(jīng)緯度平分法Fig.3 The methods of triangulation

2.2 利用QTM對天球進(jìn)行編碼

在利用QTM對天球編碼時(shí)，一個QTM位置碼由一個八分碼（0～7）和若干個四分碼（0～3）組成。在第k個剖分層次，球面三角形A的編碼可以表示為：a0a1a2…ak。其中，a0是八分碼，a1～ak是k個四分碼。

八分碼a0代表8個八分體之一，這8個八分體的編碼如圖4所示。

圖4　內(nèi)接正八面體剖分球面的初始編碼Fig.4 Initial partition and coding of spherical facet based on octahedron

四分碼ak(k≥1)可以通過當(dāng)前區(qū)域在其父區(qū)域中的相對位置來編碼：0表示當(dāng)前區(qū)域在其父區(qū)域的中間，該三角形區(qū)域稱為中間三角形；1表示當(dāng)前區(qū)域在其父區(qū)域的上面（或者下面），該三角形區(qū)域稱為頂邊三角形；2表示當(dāng)前區(qū)域在其父區(qū)域的左邊，該三角形區(qū)域稱為左邊三角形；3表示當(dāng)前區(qū)域在其父區(qū)域的右邊，該三角形區(qū)域稱為右邊三角形，如圖5（a）所示。圖5（b）是對為0的八分體作為初始球面三角形進(jìn)行2次剖分后的QTM編碼示意圖。其余7個區(qū)域的剖分與0區(qū)域類似。

圖5　QTM編碼示意圖Fig.5 Subdivision and QTM coding

2.3 QTM地址碼與赤經(jīng)赤緯的相互轉(zhuǎn)換

天球上的每一個星點(diǎn)都由赤經(jīng)、赤緯來確定位置，因此赤經(jīng)赤緯與QTM編碼之間的相互轉(zhuǎn)換是完成星點(diǎn)快速搜索的關(guān)鍵。

在現(xiàn)有的QTM編碼與赤經(jīng)、赤緯的轉(zhuǎn)換算法中，ZOT（Zenithal Ortho Triangular）投影法轉(zhuǎn)換速度快，但生成的編碼缺乏方向性；ETP（Equal?Triangles Projection）投影法生成的編碼具有固定的方向性，但轉(zhuǎn)換速度慢。趙學(xué)勝等提出的行列逼近法（Cavalcade Approach Method，CAM）［6］是一種從赤經(jīng)、赤緯到QTM碼的快速轉(zhuǎn)換方法。該方法基于經(jīng)緯度平分法，根據(jù)位置區(qū)域的行列以及地址碼的方向進(jìn)行層次遞歸，轉(zhuǎn)換速度較快，因此本文選擇行列逼近法進(jìn)行QTM地址碼與赤經(jīng)、赤緯的相互轉(zhuǎn)換。

2.4 基于QTM編碼的鄰近檢索

在QTM格網(wǎng)中鄰近三角形的定義為：具有公共邊的為邊鄰近Edge?adjacent（三角形）；只具有公共頂點(diǎn)的為角鄰近（也稱為頂點(diǎn)鄰近，Vertex?adja?cent）三角形。

（1）邊鄰近三角形的搜索

在QTM格網(wǎng)中所有三角形具有3個邊鄰近：左鄰近三角形L（u）、右鄰近三角形R（u）和頂（上或下）鄰近三角形T（u），每種鄰近又可以按照鄰近的三角形是否在同一個八分體內(nèi)分為兩種情況。

下面以左鄰近搜索為例介紹邊鄰近三角形的搜索算法，如圖6所示。

圖6　對八分體剖分兩次的左鄰域搜索示意圖Fig.6 Searching sketch map of octant splited two times on the left neighborhood

如果左鄰近三角形在同一個八分體內(nèi)部：

1）如果當(dāng)前三角形區(qū)域地址碼的最后一位是0，也即當(dāng)前三角形是其父三角形的中間三角形，其左鄰近三角形為其父三角形的左邊三角形；

2）如果當(dāng)前三角形區(qū)域地址碼的最后一位是3，也即當(dāng)前三角形是其父三角形的右邊三角形，其左鄰近三角形為其父三角形的中間三角形；

3）如果當(dāng)前三角形區(qū)域地址碼的最后一位是1，也即當(dāng)前三角形是其父三角形的頂邊三角形，其左鄰近三角形為其父三角形的左鄰近三角形的右邊三角形；

4）如果當(dāng)前三角形區(qū)域地址碼的最后一位是2，也即當(dāng)前三角形是其父三角形的左邊三角形，其左鄰近三角形為其父三角形的左鄰近三角形的頂邊三角形。

如果左鄰近三角形不在同一個八分體內(nèi)部：

1）計(jì)算當(dāng)前八分體左側(cè)的八分體的八分碼：

2）所有為2的四分碼變?yōu)?，其余四分碼保持不變：

這樣就得到了三角形左鄰近三角形的QTM編碼，算法的流程圖如圖7所示。

對于右鄰近和頂鄰近搜索有類似的流程，在此不再贅述。

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

三角形在八分體的最上、最左、最右側(cè)時(shí)，角鄰近三角形有7個，如圖8（a）所示；在其他位置時(shí)，角鄰近三角形有9個，如圖8（b）所示。

對角鄰近三角形搜索可以轉(zhuǎn)換為邊鄰近三角形的搜索。以圖8（b）為例，編號為1的三角形與當(dāng)前三角形（U）的關(guān)系可以表示為：

式中，U1代表編號為1的三角形，U代表當(dāng)前三角形，代表當(dāng)前三角形的頂鄰近三角形，代表當(dāng)前三角形的左鄰近三角形。

（3）對一個三角形的鄰近搜索包括邊鄰近搜索和角鄰近搜索

由圖7和圖8可知，三角形的邊鄰近搜索只是簡單的二進(jìn)制操作，而角鄰近搜索可以轉(zhuǎn)換為7個（或9個）邊鄰近搜索。因此，鄰近搜索的效率非常高。已知一個天區(qū)的QTM編碼時(shí)，可以通過鄰近搜索算法迅速計(jì)算出與該三角形相鄰的所有三角形的QTM編碼。

圖8　角鄰近三角形Fig.8 Vertex?adjacent triangles

3 基于QTM劃分的導(dǎo)航星庫在星圖識別中的應(yīng)用與分析

以10°×10°的視場為例，利用QTM法劃分導(dǎo)航星庫，并基于劃分后的星庫做局部天區(qū)星圖識別，以驗(yàn)證該劃分方法的性能。

對每一個八分體Si利用經(jīng)緯度平分法細(xì)分3次，全天球區(qū)域被劃分成了512（8×43）個小三角形天區(qū)；掃描導(dǎo)航星庫，將每顆導(dǎo)航星都劃歸到相應(yīng)的子天區(qū)；按照QTM編碼的方式為每一個天區(qū)建立如表3所示的索引表。

表3　天區(qū)索引表Table 3 Index of sub?sky

對其中一個八分體進(jìn)行統(tǒng)計(jì)分析，球面三角形頂點(diǎn)之間夾角的最小值為11．25°，頂點(diǎn)與對邊中點(diǎn)夾角的最小值為7．94°，如表4所示。因此，任意一個視場角小于15．88°×15．88°的視場都可以利用該視場中心所在的三角形天區(qū)及其12鄰近（或10鄰近）天區(qū)完全覆蓋。

表4　八分體內(nèi)三角形頂點(diǎn)夾角大小的統(tǒng)計(jì)分析Table 4 Statistic and analysis for the angles in octant

在載體運(yùn)動角速度比較小時(shí)，利用上一時(shí)刻視軸的所在天區(qū)及其鄰近天區(qū)中包含的導(dǎo)航信息組成實(shí)時(shí)導(dǎo)航星庫；當(dāng)載體運(yùn)動角速度比較大時(shí)，利用之前幾個時(shí)刻的視軸方向和運(yùn)動信息估計(jì)當(dāng)前時(shí)刻的視軸方向，組建實(shí)時(shí)導(dǎo)航星庫。利用這種方法把星圖識別的搜索范圍縮減為整個導(dǎo)航星庫的13/512≈2．5％。

采用QTM劃分導(dǎo)航星庫后，星圖識別的流程如下：

1）第一幀星圖的視軸方向由全天球星圖識別計(jì)算得出（或者由程序給定）；

2）根據(jù)上一時(shí)刻的視軸方向或者之前幾個時(shí)刻的視軸方向構(gòu)建（或更新）實(shí)時(shí)星庫；

3）利用實(shí)時(shí)星庫，進(jìn)行局部天區(qū)星圖識別；

4）如果局部天區(qū)星圖識別未能成功識別則轉(zhuǎn)入全天球星圖識別。

下面以三角形識別為例，對視軸為BoreSight1（Ra=282．09°，Dec=-28．77°，Roll=40．06°，10°×10°圓形視場，極限星等為6．0等）的視場分別采用全天球星圖識別法與QTM劃分導(dǎo)航星庫的局部天區(qū)星圖識別法進(jìn)行識別以比較兩種方法在識別效率上的差異，識別中星角距的匹配誤差設(shè)置為0．001rad（0．057°）。在進(jìn)行局部天區(qū)星圖識別之前，首先對視軸為BoreSight0（Ra=280．60°，Dec =-28．95°，Roll=38．94°）的視場進(jìn)行全天球星圖識別以建立實(shí)時(shí)星庫。

在BoreSight1視場中共有10顆導(dǎo)航星，選取其中最亮的3顆待識別星（S1、S2、S3）組成的3個待匹配星對和待匹配星三角形進(jìn)行匹配，待匹配星對和待匹配星三角形的匹配結(jié)果如表5所示。

表5　對BoreSight1視場中最亮的三顆星進(jìn)行識別的結(jié)果Table 5 Identify result of the three brightest stars in BoreSight1

由表5可以看出，采用QTM對導(dǎo)航星庫進(jìn)行劃分后，一方面大大減少了與每個待匹配星對相匹配的星對數(shù)量；另一方面減少了待匹配三角形出現(xiàn)冗余匹配的可能性，算法的運(yùn)行時(shí)間得以減少。

為了評價(jià)該星庫的性能，在計(jì)算機(jī)上進(jìn)行了仿真測試。測試時(shí)假設(shè)星敏感器初始姿態(tài)為Bore?Sight0（Ra=280．60°，Dec=-28．95°，Roll= 38．94°），第i時(shí)刻姿態(tài)為：

式中，j取0、1、2，分別代表視軸的Ra、Dec、Roll 3個方向；rand是范圍為（-1°，1°）的隨機(jī)數(shù)。

測試總共進(jìn)行了150步，每一步都會根據(jù)當(dāng)前的姿態(tài)產(chǎn)生一幅星圖模擬星敏感器采集到的觀測星圖，測試結(jié)果如圖9所示。

圖9　150次星圖識別所用時(shí)間Fig.9 Elapsed time of star identification

除去第1次識別采用全天球星圖識別外，其余149次均用QTM分區(qū)的局部天區(qū)星圖識別完成，證明了QTM分區(qū)、編碼及鄰域搜索算法的正確性。采用QTM分區(qū)的局部天區(qū)星圖識別每次識別時(shí)間最短為0．34ms，最長為8．5ms，平均識別時(shí)間為1．9ms，且有84％的匹配時(shí)間小于2．0ms，相對于全天球星圖識別來說識別時(shí)間少了1個數(shù)量級。以文獻(xiàn)［4］為例，采用內(nèi)接正六面體劃分導(dǎo)航星表的改進(jìn)三角形星圖識別方法做一次全天球星圖識別需要的平均時(shí)間為8．4ms。

4 結(jié)論

本文把球面四元三角網(wǎng)（QTM）引入到導(dǎo)航星庫的劃分中，提出了一種基于經(jīng)緯度平分法的QTM導(dǎo)航星庫劃分方法，并采用行列逼近算法對各個天區(qū)進(jìn)行編碼?；谶@種劃分方法構(gòu)造的導(dǎo)航星庫繼承了QTM劃分均勻、編碼方向一致、鄰域搜索高效，經(jīng)緯度平分法與經(jīng)緯度高度相關(guān)，行列逼近法編碼快速等特點(diǎn)?；谠撔菐爝M(jìn)行的局部天區(qū)星圖識別仿真試驗(yàn)也驗(yàn)證了這種方法的高檢索效率。

［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］．北京：國防工業(yè)出版社，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］趙學(xué)勝，陳軍．QTM地址碼與經(jīng)緯度坐標(biāo)的快速轉(zhuǎn)換算法［J］．測繪學(xué)報(bào)，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］白建軍，孫文彬，趙學(xué)勝．基于QTM的WGS?84托球面層次剖分及其特點(diǎn)分析［J］．測繪學(xué)報(bào)，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］趙學(xué)勝，侯妙樂，白建軍．全球離散格網(wǎng)的空間數(shù)學(xué)建模［M］．北京：測繪出版社，2007．ZHAOXue?sheng，HOUMiao?le，BAIJian?jun．Spatialdata modeling based on global discrete grid［M］．Beijing：Surveying and Mapping Press，2007．

［9］孔祥元，郭際明，劉宗全．大地測量學(xué)基礎(chǔ)［M］．武漢：武漢大學(xué)出版社，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

趙啟坤，男，碩士，導(dǎo)航、制導(dǎo)與控制專業(yè)，研究方向?yàn)樾枪饨M合導(dǎo)航技術(shù)。