上面級(jí)快速星圖匹配算法研究

李超兵，李蘭蘭，溫亞北京航天自動(dòng)控制研究所，北京100859

上面級(jí)快速星圖匹配算法研究

李超兵＊，李蘭蘭，溫亞
北京航天自動(dòng)控制研究所，北京100859

現(xiàn)有星圖匹配算法存在搜索時(shí)間慢、算法實(shí)時(shí)性差的問(wèn)題。為了滿(mǎn)足上面級(jí)實(shí)時(shí)性的要求，文章采用K矢量查找算法來(lái)提高查找快速性，選擇星對(duì)角矩作為星圖匹配的特征量，構(gòu)造星對(duì)角矩矢量，采用星棱錐星圖匹配算法進(jìn)行星圖識(shí)別。最后采用上下位機(jī)的形式進(jìn)行仿真分析，結(jié)果表明采用該星棱錐快速星圖匹配算法成功率在99%以上，識(shí)別時(shí)間最長(zhǎng)約為100ms，平均時(shí)間在15ms以?xún)?nèi)。該算法能夠滿(mǎn)足上面級(jí)對(duì)匹配算法快速性和高精度的要求。

上面級(jí)；天文導(dǎo)航；星對(duì)角距；星圖匹配；K矢量查找算法；星棱錐算法

運(yùn)載火箭上面級(jí)是航天運(yùn)輸系統(tǒng)的重要組成部分，它是在基礎(chǔ)級(jí)火箭上面增加的相對(duì)獨(dú)立的一級(jí)（或多級(jí)），上面級(jí)具有較強(qiáng)的任務(wù)適應(yīng)性，其工作段通常已經(jīng)進(jìn)入了地球軌道，能夠完成軌道滑行、軌道機(jī)動(dòng)、有效載荷的分離與部署等任務(wù)，是提高運(yùn)載火箭性能和增強(qiáng)任務(wù)適應(yīng)能力的有效途徑。目前較為先進(jìn)的上面級(jí)：美國(guó)的通用半人馬座，該上面級(jí)2002年首飛，真空推力達(dá)到198.4kN，采用液氫／液氧推進(jìn)劑；俄羅斯的KVRB，該上面級(jí)目前正在研制，真空推力達(dá)到102.9kN，采用液氧／煤油推進(jìn)劑；歐洲的ESC－A，該上面級(jí)2002年首飛，真空推力達(dá)到64.8kN，采用液氫／液氧推進(jìn)劑［1－2］。先進(jìn)上面級(jí)一般具有獨(dú)立于運(yùn)載火箭和有效載荷的制導(dǎo)、導(dǎo)航與控制系統(tǒng)，能夠多次啟動(dòng)、長(zhǎng)時(shí)間工作、自主飛行，具備多星發(fā)射和軌道機(jī)動(dòng)、軌道部署的能力［3］。

由于上面級(jí)工作時(shí)間長(zhǎng)于基礎(chǔ)級(jí)火箭，可達(dá)30min至數(shù)天不等，上面級(jí)多采用慣性導(dǎo)航系統(tǒng)，但是慣性導(dǎo)航系統(tǒng)的誤差會(huì)隨時(shí)間增長(zhǎng)，因此純慣性導(dǎo)航不能滿(mǎn)足上面級(jí)對(duì)高精度導(dǎo)航的要求，而天文導(dǎo)航是通過(guò)測(cè)量自然天體相對(duì)航天器的矢量方向來(lái)實(shí)現(xiàn)定位導(dǎo)航，具有直接、自然、可靠、精確的優(yōu)點(diǎn)，且導(dǎo)航誤差不隨時(shí)間積累［4］，因此天文導(dǎo)航系統(tǒng)能夠滿(mǎn)足上面級(jí)對(duì)高精度的要求，天文導(dǎo)航的重點(diǎn)是星圖匹配算法。

星圖匹配算法主要應(yīng)用于星敏感器的初始姿態(tài)捕獲。星敏感器具有兩種工作模式：初始姿態(tài)捕獲模式和跟蹤模式［5－6］。姿態(tài)捕獲模式需要在沒(méi)有先驗(yàn)信息的條件下獲取載體的姿態(tài)，是星圖匹配的最關(guān)鍵技術(shù)［7－8］。常見(jiàn)的星圖匹配算法包括：三角形及其改進(jìn)算法［9－10］、基于神經(jīng)網(wǎng)絡(luò)的星圖匹配算法、基于遺傳算法的星圖匹配算法、基于奇異值分解的星圖匹配算法

等［11－12］。

無(wú)論采用何種星圖匹配算法，都不可避免地要對(duì)導(dǎo)航特征庫(kù)進(jìn)行查找，經(jīng)典的對(duì)導(dǎo)航特征庫(kù)查找算法有順序查找和二分查找，其算法的時(shí)間復(fù)雜度分別為O（n）和O（log2n）［13］，運(yùn)算量較大，實(shí)時(shí)性難以滿(mǎn)足。為了提高查找的快速性以滿(mǎn)足上面級(jí)實(shí)時(shí)性的要求，本文主要研究基于K矢量查找的星棱錐快速星圖匹配算法。

1 快速星圖匹配算法

1.1 K矢量查找算法

Mortari等人提出了K矢量查找技術(shù)［14］，本文將該查找技術(shù)運(yùn)用在星圖匹配算法上，可以大大提高匹配速度，節(jié)省查找時(shí)間。該查找技術(shù)的核心是構(gòu)造單調(diào)的K矢量查找表，建立K矢量與導(dǎo)航特征量的映射關(guān)系。

設(shè)y是升序排列的長(zhǎng)度為n的向量，y＝［ymin…ymax］T，定義ξ為一小量，過(guò)點(diǎn)（1，ymin－ξ）和（n，ymax＋ξ）作一條直線。該直線的方程為：

式中：m，q分別為該直線的斜率和截距：

實(shí)際上，K（i）表示向量y中小于z（i）的元素?cái)?shù)目。

如圖1所示，對(duì)10個(gè)元素構(gòu)成的向量（圖中×點(diǎn)）進(jìn)行K矢量構(gòu)造，圖中過(guò)直線上點(diǎn)z（i）的小橫線可以指示K矢量，即小橫線之下向量y元素的個(gè)數(shù)為K矢量元素的取值：｛0，2，2，3，3，5，6，8，9，10｝。

圖1 K矢量構(gòu)造示例Fig.1 Example of Kvector construction

如果觀測(cè)值落入的范圍為［ya，yb］，則其對(duì)應(yīng)的K矢量元素序號(hào)為：

式中：?x」表示小于x的最大整數(shù)，「x?表示大于x的最小整數(shù)。當(dāng)jb、jt計(jì)算出來(lái)之后，則可以計(jì)算kst和ke：

對(duì)圖1而言，jb＝6，jt＝9，代入式（5）可得kst＝6，ke＝9，這意味著可能的取值在向量y的序號(hào)為kst和ke，即量測(cè)值必然落入y（kst）～y（ke）。由上述分析可知，通過(guò)K矢量查找技術(shù)能夠減少搜索時(shí)間，因?yàn)閮H僅通過(guò)式（4）和式（5）即可確定出可能取值的上下限，這兩個(gè)式子的時(shí)間復(fù)雜度均為O（1）。

1.2 星對(duì)角距的K矢量構(gòu)造與查找

在星圖圖像中可以作為星圖匹配特征信息為星點(diǎn)的坐標(biāo)和星點(diǎn)的亮度，分別對(duì)應(yīng)于星表中天球坐標(biāo)系下導(dǎo)航星的坐標(biāo)（赤經(jīng)和赤緯）和星等。星等常被認(rèn)為是一種不可靠的信息量，由于圖像傳感器的頻譜響應(yīng)特性的差異，儀器星等和視星等并不一致。此外有些恒星的星等并不是固定不變的。因此，在星圖匹配中盡量少用星等信息進(jìn)行判別。

實(shí)際中，常常用星間角距作為特征匹配量，因?yàn)榻蔷嗖坏梢酝ㄟ^(guò)觀測(cè)星圖準(zhǔn)確計(jì)算出來(lái)，而且相對(duì)于天空中的恒星而言，相互間角距隨時(shí)間改變很小，可以認(rèn)為其在非常小的門(mén)限內(nèi)變化。此外，角距在坐標(biāo)變換中保持不變，是一種可靠的特征量。

基于上述分析，本文采用星對(duì)角距作為特征值，首先將所有導(dǎo)航星可能組成的星對(duì)角距的余弦值按從小到大做成數(shù)據(jù)庫(kù)，顯然，角距的最小值?min與星敏感器CCD的測(cè)量精度有關(guān)，本文中?。?/p>

式中：?FOV為CCD視場(chǎng)角度；N＝max（Nx，Ny），Nx，Ny為CCD相機(jī)像素平面x，y軸向像素?cái)?shù)目；14來(lái)自像素窗口大小，最大值與其視場(chǎng)?FOV相關(guān)。

假設(shè)兩顆導(dǎo)航星在導(dǎo)航星庫(kù)編號(hào)為i、j，兩顆導(dǎo)航星在天球坐標(biāo)系下的矢量為ri、rj，則其角距的余弦值：

定義矢量Sp為導(dǎo)航星對(duì)角距數(shù)據(jù)庫(kù)，其每一個(gè)元素由兩顆導(dǎo)航星編號(hào)及角距余弦值組成。Sp的元素按照星對(duì)角距余弦值升序排列。如果兩顆導(dǎo)航星的角距余弦值滿(mǎn)足：

則須將其信息加入到導(dǎo)航星對(duì)角距數(shù)據(jù)庫(kù)Sp中，其中航天器星敏感器一般采用大視場(chǎng)，視場(chǎng)范圍14°～20°不等。

根據(jù)第1.1節(jié)介紹的K矢量查找技術(shù)，可以連接兩個(gè)端點(diǎn)［1，Sp（1）·cosθ］與［n，Sp（n）·cosθ］，兩端點(diǎn)之間有n－1個(gè)間隔，可以得到平均每個(gè)元素Sp（k）所占間隔為：

過(guò)點(diǎn)1，Sp（1）·cosθ－D／2［

其中：按照式（3）構(gòu)造K矢量。K（i）表示向量Sp中小于（a1i＋a0）的元素?cái)?shù)目。

如果兩顆導(dǎo)航星（p，q）在CCD上成像構(gòu)成星對(duì)，其角距量測(cè)值為θ，測(cè)量誤差為ε，則導(dǎo)航星（p，q）在建立的K矢量查找表中的位置為：

利用式（5）可求得：

式中：kst和ke為查找值在矢量Sp的索引范圍，即星對(duì)角距值落在［θ－ε，θ＋ε］的可能值的集合為：

ε的選取對(duì)K矢量查找有直接影響：過(guò)小則可能查找失敗，過(guò)大則查找結(jié)果過(guò)多影響后面的匹配速度，甚至匹配失敗。本文采用一種工程中ε的選取方法［11］，即

式中：σs（1σ）為單星測(cè)量精度。

式中：σc為質(zhì)心提取精度，亞像素的質(zhì)心提取精度可取0.1像素。

由上述分析可以看出，對(duì)給定的星對(duì)角距量測(cè)值θ，測(cè)量誤差ε，可以通過(guò)K矢量查找技術(shù)迅速給出CCD上成像為該角距的可能星對(duì)集合：｛Sp（kst），Sp（kst＋1），…，Sp（ke）｝為星圖匹配奠定基礎(chǔ)。

1.3 基于K矢量查找的快速星棱錐星圖匹配算法

星棱錐識(shí)別算法即金字塔算法，該方法并不依賴(lài)導(dǎo)航星的星等信息，如圖2所示為星棱錐識(shí)別算法采用的基準(zhǔn)星結(jié)構(gòu)，該星棱錐包含一個(gè)基準(zhǔn)星三角（采用i、j、k表示），還有一顆確認(rèn)星r。

圖2 星棱錐Fig.2 Star pyramid

假設(shè)星圖內(nèi)共有n顆觀測(cè)星，星棱錐識(shí)別法的算法流程如圖3所示，具體步驟為：

1）如果n＜3，無(wú)法進(jìn)行星圖匹配；如果n＝3，不能構(gòu)成星棱錐，算法退化為驗(yàn)證星三角形是否唯一，在這里要注意排除鏡像三角形的影響。解決方法為：3顆觀測(cè)星觀測(cè)三角形的標(biāo)號(hào)為i、j、k，相應(yīng)的3顆來(lái)自導(dǎo)航星庫(kù)的導(dǎo)航星構(gòu)成的導(dǎo)航三角形標(biāo)號(hào)為I、J、K，如果滿(mǎn)足：rk）］則認(rèn)為觀測(cè)三角形不是鏡像三角形。

2）如果n＞3，在所有星三角中選取一個(gè)匹配唯一的三角形［i，j，k］，作為基準(zhǔn)三角形，開(kāi)展步驟3）；若所有三角形均不滿(mǎn)足要求，則星圖匹配失?。淮瞬襟E中也可以使用式sgn［bTi（bj×bk）］＝sgn［rTi（rj×rk）］對(duì)鏡像三角形進(jìn)行剔除。

3）如果步驟2）找到了一個(gè)高置信度的基準(zhǔn)三角形［i，j，k］，則在剩余星中找一顆參考星r驗(yàn)證基準(zhǔn)三角形［i，j，k］，如果找到的r使星棱錐［i，j，k，r］匹配唯一，則轉(zhuǎn)入步驟4）；否則轉(zhuǎn)到步驟2），重新確定一個(gè)基準(zhǔn)三角形。4）如果步驟3）成功地構(gòu)建了星棱錐［i，j，k，r］，則這4顆星具有極高的置信度，接著就可以用其中的3顆基準(zhǔn)星［i，j，k］對(duì)剩余的其他星p進(jìn)行驗(yàn)證，如果能通過(guò)驗(yàn)證則認(rèn)為星p是正常星；不能通過(guò)驗(yàn)證，則認(rèn)為星p是假星。

星棱錐匹配算法的基本準(zhǔn)則就是：嚴(yán)格根據(jù)先驗(yàn)信息建立高置信度的唯一匹配，寧可匹配失敗也不能輸出低置信度的識(shí)別結(jié)果。因?yàn)楝F(xiàn)代的姿態(tài)估計(jì)算法能夠容忍數(shù)據(jù)更新率的不足，卻不能忍受錯(cuò)誤的星圖匹配結(jié)果。

星棱錐匹配的基礎(chǔ)是三角形識(shí)別，下面簡(jiǎn)要說(shuō)明其原理。如圖2所示，對(duì)3顆觀測(cè)星［i，j，k］，其兩兩組成的角距分別為?ij，?jk，?ki，在角矩?cái)?shù)據(jù)庫(kù)Sp中按照式（12）、式（13）查找，可以得到3個(gè)星對(duì)集合：

圖3 星棱錐匹配算法流程Fig.3 Procedure of star pyramid matching algorithm

3個(gè)集合的構(gòu)成元素分別簡(jiǎn)寫(xiě)為Sp1、Sp2、Sp3，每個(gè)元素的組成見(jiàn)式（7）：即由兩顆星編號(hào)num1和num2星對(duì)角距余弦值cosθnum1，num2組成，為（cosθnum1，num2，num1，num2）。三角形匹配成功的一個(gè)的條件為：

2 仿真分析

本文設(shè)計(jì)采用如圖4所示的仿真結(jié)構(gòu)進(jìn)行星圖快速匹配算法的仿真。CCD參數(shù)如表1所示。仿真下位機(jī)采用DSP6713進(jìn)行星圖匹配算法和定姿算法的仿真。上位機(jī)進(jìn)行星圖模擬仿真及定姿結(jié)果顯示。星圖模擬包括導(dǎo)航星庫(kù)的建立及恒星星等的灰度模擬，星圖的模擬主要是將導(dǎo)航星的天球坐標(biāo)轉(zhuǎn)換到星敏感器坐標(biāo)系下，可以通過(guò)姿態(tài)矩陣實(shí)現(xiàn)，如圖5所示。本文的星圖模擬采用SAO原始星表，篩選出5等星作為導(dǎo)航星庫(kù)。并將該導(dǎo)航星庫(kù)作為下位機(jī)星圖匹配算法的參考星庫(kù)。

整個(gè)仿真過(guò)程如下：設(shè)計(jì)了一條1 800s的飛行器飛行軌跡。上位機(jī)模擬飛行過(guò)程中觀測(cè)到星圖的變化，每秒模擬一張星敏感器拍攝的星圖，如圖6所示，從星圖中進(jìn)行星點(diǎn)質(zhì)心提取，并通過(guò)網(wǎng)絡(luò)將星圖質(zhì)心坐標(biāo)信息發(fā)送給下位機(jī)；下位機(jī)進(jìn)行星圖匹配和定姿運(yùn)算，匹配完成后，下位機(jī)將匹配結(jié)果發(fā)送給上位機(jī)，上位機(jī)將識(shí)別時(shí)間進(jìn)行存儲(chǔ)和顯示。

表1 星敏感器CCD光學(xué)參數(shù)取值Table 1 Optical parameters of CCD

圖4 仿真系統(tǒng)結(jié)構(gòu)框圖Fig.4 Diagram of simulation system

圖5 星圖模擬的流程Fig.5 Procedure of star map simulation

圖6 上位機(jī)模擬產(chǎn)生的星圖（反色顯示）Fig.6 Star map produced by host computer

飛行過(guò)程中共生成1 800張照片，識(shí)別成功率100%，具體結(jié)果如圖7～圖10所示：識(shí)別時(shí)間的均值與標(biāo)準(zhǔn)差分別為μ＝12.4ms，σ＝22ms，且識(shí)別時(shí)間在50ms以?xún)?nèi)的占95%以上。

圖7 視場(chǎng)內(nèi)觀測(cè)星數(shù)概率分布Fig.7 Normal probability of star number

圖8 識(shí)別時(shí)間概率分布Fig.8 Normal probability of identification time

圖9 識(shí)別時(shí)間Fig.9 Identification time

圖10 識(shí)別結(jié)果（0為成功，1為失?。〧ig.10 Result of identification

3 結(jié)束語(yǔ)

本文研究了K矢量查找算法與星棱錐快速星圖匹配算法，并進(jìn)行仿真分析，由仿真結(jié)果可得出以下結(jié)論：本文設(shè)計(jì)的上面級(jí)快速星圖匹配算法的成功率在99%以上，DSP6713運(yùn)行算法時(shí)識(shí)別最大時(shí)間約為100ms，平均時(shí)間在15ms以?xún)?nèi)，能夠達(dá)到上面級(jí)天文導(dǎo)航系統(tǒng)對(duì)星圖匹配算法快速性和高精度的要求，為天文導(dǎo)航系統(tǒng)的工程應(yīng)用奠定了基礎(chǔ)。但是本文只考慮了視場(chǎng)中沒(méi)有假星的情況，工程應(yīng)用中情況復(fù)雜，很可能出現(xiàn)假星，當(dāng)視場(chǎng)中出現(xiàn)假星的情況，本文中設(shè)計(jì)的上面級(jí)快速星圖匹配算法是否還有如此高的速度和精度還需要進(jìn)一步驗(yàn)證。

（

）

［1］ 馬昆.上面級(jí)發(fā)展現(xiàn)狀及趨勢(shì)分析［J］.導(dǎo)彈與航天運(yùn)載技術(shù)，2013，329（6）：24－28.MA K.Development status and trend analysis of upper stages［J］.Missiles and Space Vehicles，2013，329（6）：24－28（in Chinese）.

［2］ 林木.運(yùn)載火箭上面級(jí)功能與技術(shù)發(fā)展分析［J］.上海航天，2013，178（3）：33－38.LIN M.Functional and technical progress of upper stage for launchers［J］.Aerospace Shanghai，2013，178（3）：33－38（in Chinese）.

［3］ 張利賓.火箭上面級(jí)導(dǎo)航、中途修正與姿態(tài)控制研究［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，2010.ZHANG L B.Study on navigation，midcourse correction and attitude control of launch vehicle upper stage［D］.Harbin：Harbin institute of technology，2010（in Chinese）.

［4］ 張利賓.運(yùn)載火箭上面級(jí)慣性與天文組合導(dǎo)航系統(tǒng)設(shè)計(jì)［J］.光學(xué)精密工程，2010，18（11）：2473－2481.ZHANG L B.Design of INS／CNS integrated navigation system for launch vehicle upper stage［J］.Optical Precision Engineering，2010，18（11）：2473－2481（in Chinese）.

［5］ 賈輝.高精度星敏感器星點(diǎn)提取與星圖識(shí)別研究［D］.長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2010.JIA H.Star centroid estimation and star identification of high accuracy star tracker［D］.Changsha：National University of Defense Technology，2010（in Chinese）.

［6］ 劉美瑩.CCD天文觀測(cè)圖像的星圖識(shí)別和天文定位方法研究［D］.西安：中國(guó)科學(xué)院研究生院（西安光學(xué)精密機(jī)械研究所），2010.LIU M Y.Research on CCD star map identification and celestial position［D］.Xi′an：Xi′an Institute of Optics and Precision Mechanics，Chinese Academy of Sciences，2010（in Chinese）.

［7］ GONG J Q，MA J，TIAN J W，et al.A flower algorithm for autonomous star pattern recognition［C］.47thAIAA Aerospace Sciences Meeting including the New Horizons Forum and Aerospace Exposition，Aerospace Sciences Meetings，Orlando，F(xiàn)lorida，5－8 January，2009.

［8］ CAMPBELL M E，et al.A celestial orientation system based on star pattern recognition［J］.Journal of Spacecraft and Rockets，2009，2（6）：962－963.

［9］ PALADUGU L.Intelligent star pattern recognition for attitude determination：the"Lost in Space"problem［J］.Journal of Aerospace Computing，Information，and Communication，2009，3（11）：538－549.

［10］ COLE C L，J L CRASSIDIS，et al.Fast star－pattern recognition using planar triangles［J］.Journal of Guidance，Control，and Dynamics，2009，29（1）：64－71.

［11］ 張力軍.基于多視場(chǎng)星敏感器的航天器姿態(tài)確定方法研究［D］.長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2011.ZHANG L J.Spacecraft attitude determination for multiple fields of view star sensors［D］.Changsha：National University of Defense Technology，2011（in Chinese）.

［12］ 邢飛，尤政，董瑛，等.基于導(dǎo)航星域和K矢量的快速星圖識(shí)別算法［J］.宇航學(xué)報(bào)，2010，31（10）：2302－2308.XING F，YOU Z，DONG Y，et al.A rapid star identification algorithm based－on navigation star domain and K－vector［J］.Journal of Astronautics，2010，31（10）：2302－2308（in Chinese）.

［13］ THOMAS H CORMEN，CHARLSE E LEISERON，RONALD L.Introduction to algorithm［M］.Rivest and Clifford Stein：The MIT Press，2001.

［14］ MORTARI D，NETA B.K－vector range searching techniques［C］∥The 10th Annual AIAA／AAS Space Flights Mechanics Meeting，Paper AAS 00－128，Clearwaters，F(xiàn)L.，23－26Jan.，2000.

（編輯：車(chē)曉玲）

Research on quick star identification algorithm of upper stage

LI Chaobing＊，LI Lanlan，WEN Ya
Beijing Aerospace Automatic Control Institute，Beijing 100859，China

Present star identification algorithms have the problem of real－time calculation.In order to meet the navigation requirement of the upper stage，the Kvector search algorithm was employed，the inter－star angles as the matching feature quantity were selected and the star pyramid matching algorithm was used.Finally，simulation results indicate that the success rate of this algorithm is more than 99%，the maximum time of identification is about 100ms，and the average time is less than 15ms.The algorithm can meet the matching speed and precision requirements of the upper stage.

upper stage；celestial navigation；inter－star angles；star identification；Kvector search algorithm；pyramid algorithm

V249.32＋3

A

10.16708／j.cnki.1000－758X.2017.0053

2016－11－23；

2017－05－08；錄用日期：2017－06－29；網(wǎng)絡(luò)出版時(shí)間：2017－08－11 10：47：51

http：∥kns.cnki.net／kcms／detail／11.1859.V.20170811.1047.007.html

＊通訊作者：李超兵（1981－），男，碩士，高級(jí)工程師，lcbpku＠163.com，研究方向?yàn)楹教炱鲗?dǎo)航制導(dǎo)與控制

李超兵，李蘭蘭，溫亞.上面級(jí)快速星圖匹配算法研究［J］.中國(guó)空間科學(xué)技術(shù)，2017，37（4）：56－62.

LI C B，LI L L，WEN Y.Research on quick star identification algorithm of upper stage［J］.Chinese Space Science and Technology，2017，37（4）：56－62（in Chinese）.