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

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

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

2.1 天球剖分方法

1）用天球的內(nèi)接正八面體把球面均勻的分成8個(gè)區(qū)域S1～S8［5］，每個(gè)子區(qū)域稱為一個(gè)八分體，如圖1所示。正八面體的6個(gè)頂點(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

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

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

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

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

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

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

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

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

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

四分碼ak(k≥1)可以通過(guò)當(dāng)前區(qū)域在其父區(qū)域中的相對(duì)位置來(lái)編碼：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）是對(duì)為0的八分體作為初始球面三角形進(jìn)行2次剖分后的QTM編碼示意圖。其余7個(gè)區(qū)域的剖分與0區(qū)域類似。

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

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

天球上的每一個(gè)星點(diǎn)都由赤經(jīng)、赤緯來(lái)確定位置，因此赤經(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個(gè)邊鄰近：左鄰近三角形L（u）、右鄰近三角形R（u）和頂（上或下）鄰近三角形T（u），每種鄰近又可以按照鄰近的三角形是否在同一個(gè)八分體內(nèi)分為兩種情況。

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

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

如果左鄰近三角形在同一個(gè)八分體內(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)前三角形是其父三角形的左邊三角形，其左鄰近三角形為其父三角形的左鄰近三角形的頂邊三角形。

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

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

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

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

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

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

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

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

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

（3）對(duì)一個(gè)三角形的鄰近搜索包括邊鄰近搜索和角鄰近搜索

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了評(píng)價(jià)該星庫(kù)的性能，在計(jì)算機(jī)上進(jìn)行了仿真測(cè)試。測(cè)試時(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個(gè)方向；rand是范圍為（-1°，1°）的隨機(jī)數(shù)。

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

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

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

4 結(jié)論

本文把球面四元三角網(wǎng)（QTM）引入到導(dǎo)航星庫(kù)的劃分中，提出了一種基于經(jīng)緯度平分法的QTM導(dǎo)航星庫(kù)劃分方法，并采用行列逼近算法對(duì)各個(gè)天區(qū)進(jìn)行編碼。基于這種劃分方法構(gòu)造的導(dǎo)航星庫(kù)繼承了QTM劃分均勻、編碼方向一致、鄰域搜索高效，經(jīng)緯度平分法與經(jīng)緯度高度相關(guān)，行列逼近法編碼快速等特點(diǎn)。基于該星庫(kù)進(jìn)行的局部天區(qū)星圖識(shí)別仿真試驗(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］張廣軍．星圖識(shí)別［M］．北京：國(guó)防工業(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］．測(cè)繪學(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］．測(cè)繪學(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é)勝，侯妙樂(lè)，白建軍．全球離散格網(wǎng)的空間數(shù)學(xué)建模［M］．北京：測(cè)繪出版社，2007．ZHAOXue?sheng，HOUMiao?le，BAIJian?jun．Spatialdata modeling based on global discrete grid［M］．Beijing：Surveying and Mapping Press，2007．

［9］孔祥元，郭際明，劉宗全．大地測(cè)量學(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ù)。