上面級快速星圖匹配算法研究

李超兵，李蘭蘭，溫亞北京航天自動控制研究所，北京100859

上面級快速星圖匹配算法研究

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

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

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

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

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

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

等［11－12］。

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

1 快速星圖匹配算法

1.1 K矢量查找算法

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

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

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

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

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

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

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

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

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

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

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

實際中，常常用星間角距作為特征匹配量，因為角距不但可以通過觀測星圖準(zhǔn)確計算出來，而且相對于天空中的恒星而言，相互間角距隨時間改變很小，可以認(rèn)為其在非常小的門限內(nèi)變化。此外，角距在坐標(biāo)變換中保持不變，是一種可靠的特征量。

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

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

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

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

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

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

過點1，Sp（1）·cosθ－D／2［

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

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

利用式（5）可求得：

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

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

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

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

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

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

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

圖2 星棱錐Fig.2 Star pyramid

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

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

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

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

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

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

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

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

2 仿真分析

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

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

表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 上位機模擬產(chǎn)生的星圖（反色顯示）Fig.6 Star map produced by host computer

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

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

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

圖9 識別時間Fig.9 Identification time

圖10 識別結(jié)果（0為成功，1為失敗）Fig.10 Result of identification

3 結(jié)束語

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

（

）

［1］ 馬昆.上面級發(fā)展現(xiàn)狀及趨勢分析［J］.導(dǎo)彈與航天運載技術(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］ 林木.運載火箭上面級功能與技術(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］ 張利賓.火箭上面級導(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］ 張利賓.運載火箭上面級慣性與天文組合導(dǎo)航系統(tǒng)設(shè)計［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］ 賈輝.高精度星敏感器星點提取與星圖識別研究［D］.長沙：國防科學(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天文觀測圖像的星圖識別和天文定位方法研究［D］.西安：中國科學(xué)院研究生院（西安光學(xué)精密機械研究所），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］ 張力軍.基于多視場星敏感器的航天器姿態(tài)確定方法研究［D］.長沙：國防科學(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矢量的快速星圖識別算法［J］.宇航學(xué)報，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.

（編輯：車曉玲）

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ò)出版時間：2017－08－11 10：47：51

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

＊通訊作者：李超兵（1981－），男，碩士，高級工程師，lcbpku＠163.com，研究方向為航天器導(dǎo)航制導(dǎo)與控制

李超兵，李蘭蘭，溫亞.上面級快速星圖匹配算法研究［J］.中國空間科學(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）.