郭 磊 ，李保權 ，曹 陽 ，桑 鵬

（1.中國科學院國家空間中心北京100190；2.中國科學院大學北京100190）

星敏感器是以恒星為參照物進行姿態(tài)測量的敏感設備，它通過觀測天球上的恒星位置來確定飛行器相對于天球坐標系的三軸姿態(tài)，為飛行器姿態(tài)控制系統(tǒng)提供準確的依據(jù)[1]。由于恒星的張角很?。ㄗ畲蠛阈堑膹埥菫?.05角秒，一般在毫角秒量級），并且恒星的影像是在真空中提取的恒星赤經(jīng)赤緯又是精確已知的，所以星敏感器稱得上是航天器中絕對姿態(tài)測量精度最高的設備[2]。對于姿態(tài)精度要求較高的飛行器，星敏感器有著不可替代的作用。星敏感器的工作過程主要包括星表的預處理，星象檢測，星圖識別，以及姿態(tài)獲取。而整個算法的核心即是星圖識別，星圖識別的效率和正確率直接決定了整個星敏感器的工作性能。目前，已經(jīng)出現(xiàn)的星圖識別算法有三角形算法，匹配組算法，柵格算法，多邊形角距算法，奇異值分解算法，神經(jīng)網(wǎng)絡算法和遺傳算法等[3]。真正應用比較成熟且經(jīng)過工程驗證識別效果的是三角形算法。三角形算法是最早的星圖識別算法的變體，屬于子圖匹配方法家族的成員，它試圖匹配一個由觀測星點作為3個頂點構建的三角形[4]。由幾何知識我們知道全等三角形可以用兩種方法驗證：邊角邊或者邊邊邊。使用邊角邊時，可以計算三角形兩邊的長度和它們之間的夾角，并與星表中的條目相比較，由正弦定理可知，角度與對應邊長成正比，本質上還是邊邊邊；邊邊邊則是用到三角邊的長度，采用這種方法，星表需要包含在整個夜空中能觀察到的所有恒星組成的三角形的信息，星表中存儲的三角形的數(shù)目與星敏感器傳感器的敏感度和相機的FOV成比例，對于性能較好的傳感器，星敏感器的精度更高，星表中存貯的信息會非常多，這樣需要很長的搜索時間[5]。因此優(yōu)化星表很有必要，一個例子就是在圖像中選擇最亮的3個星點組成的三角形進行匹配，而不是隨機選擇3個星點。然而為了增加精度，更為理想的做法是將星圖中的所有三角形都進行匹配，而不僅僅是一個三角形[6]。亮度信息可以存儲在星表中加速星表搜索。由于測量誤差的存在，當搜索匹配的三角形時需要一定的容錯度，但容錯度會導致一些三角形匹配錯誤，為了防止這種情況的發(fā)生，需要驗證匹配的方法，或者對于每個匹配的三角形嘗試匹配鄰近的第4個亮點[7]。

1 導航星庫制作

導航星庫包括兩部分，一個星列表和星對距離列表。這兩個列表通過程序生成并存儲在星敏感器的緩存中。下面介紹兩個星表的內容：星列表包含所有亮度高于某個規(guī)定星等的恒星，在我們設計的星敏感器中該星等閾值定為5.75，但同時存儲了星等高于7等的所有恒星，并在程序中預留好接口，通過發(fā)送指令可以隨時修改閾值。星列表條目包括每顆恒星的ID，赤經(jīng)赤緯，以及星等。星表原始數(shù)據(jù)來源第谷星表經(jīng)過程序處理后，剔除了所有亮度低于5.75星等的恒星。接下來又將每顆恒星的赤經(jīng)赤緯都變換成了迪卡爾ECI單位適量下的坐標值[8]。除此之外，包括第谷星表在內的大多星表一般只給了恒星在J2000.0歷元的平位置（平赤經(jīng)和平赤緯），而我們觀測的恒星位置則是恒星的地心真赤道視位置坐標，由于恒星的自行，地球的歲差章動等等影響，這兩種坐標有些許的差異[9]。為了使得到的結果更加準確，我們對第谷表中的恒星在J2000.0歷元的平位置進行了修正，加上了自行改正，周年視差改正，光行差改正，歲差和章改正之后，得到了恒星地心真赤道坐標[10]。星列表部分如圖1所示。

圖1 星列表存儲結構

星表的第二部分為星對的間距表，為獲得此表，需計算3 999顆恒星中每兩個恒星之間的距離，計算公式如下：

其中x，y，z為恒星Si和恒星Sj在ECI單位向量上的分量。

1）間距表中的每個條目由兩顆恒星的序號和他們之間的角距（弧度）組成，并按角距的升序排列。為保持恒該星表的簡潔高效，需注意以下幾點：

2）每個恒星對只算做一個條目，與恒星的順序無關。

3）僅當星間距小于星敏感器的視場角時將恒星對列入表中。

4）僅在星間距足夠大，兩顆恒星能被獨立識別時，將恒星對列入表中[11]。

5）當星間距過小時可以視為一顆恒星也可以視為兩顆恒星，且當相距7個像素的恒星對則應被視為各自獨立[12]。

6）充分利用星表中恒星ID不太大的特點，用short類型取代int，即一個整數(shù)可以表示兩個恒星ID（高16位a1，低16位a2），一方面減少星表體積，另一方面提高了cache命中率，從硬件層面上提高算法效率。

7）星間距表的最終版本包括119570個條目，第一列中整數(shù)表示一個星對（a1，a2），第二列表示相互之間角距大小。如圖2所示。

圖2 星間距表存儲結構

2 算法描述

通常三角形識別過程是，從待測星圖中取出三個恒星點，組成三角形，例如圖3中（ABC），每條邊（AB，AC，BC）對應在星間距列表中找到對應的間距范圍（a1，a2）（b1，b2）（c1，c2）。這其中，由于星間距對排列是按照是恒星間的角距大小升序排列的，所以直接用二分法就可以在O（log（n））的時間復雜度下找到對應的角距大小的上下限[13]。本文中為了進一步提高整體算法運行效率，且由于此查詢算法調用次數(shù)較多，所以決定用哈希表實現(xiàn)導航星表中恒星對間距與下標之間的對應，這樣即可以在O（1）的時間復雜度下找到對應上下限。

由三角形幾何性質可知，三角形匹配本質上是尋找（a1，a2）（b1，b2）（c1，c2）邊之間的首尾相相接，也即是三個星對之間ID值首尾相同即可，傳統(tǒng)匹配算法即是利用三個集合之間星對坐標進行兩兩比對，假定AB對應的恒星對（a1，a2）數(shù)量為n1，AC對應的恒星（b1，b2）數(shù)量為n2，BC對應的恒星對（c1，c2）數(shù)量為n3。比對過程即是，各個坐標對進行比對；易知只需要進行比23的次數(shù)，時間復雜度為O（n1）*O（n2）*O（n3），如圖1所示[14]；再加上后來的四面體頂點檢驗以及其余待測星點驗證，三角形匹配調用次數(shù)有可能會達到數(shù)十次，顯然此時效率遠不能達到項目要求。

圖3 傳統(tǒng)三角形匹配過程

文中即對此進行了針對性優(yōu)化：降低時間復雜度；由數(shù)據(jù)結構知識可知，遍歷是相當?shù)托У模桓淖兊姆绞桨ㄅ判蚝蠖植檎?，或者哈希表定位[15]。本文兩種方法都用到了，具體做法是利用哈希表存儲（a1，a2）星間距對，由于可能有（a1，a3）或者（a2，a3）的出現(xiàn)，故選擇用拉鏈法處理沖突，處理如圖4所示。由于hashtable原來為NULL，所以當hashtable[b1]!=NULL時，即b1與a1相同。接下來只需要比較b2a2是否與c1c2或c2c1相等即可。為提高效率，避免盲目遍歷，先進行快速排序然后進行二分查找。這兩個函數(shù)都可以直接調用庫函數(shù)，不用手動實現(xiàn)。計數(shù)排序是目前最快排序，但由于數(shù)值較大，排序所需空間復雜度會很可觀，故放棄使用[16]；易知新算法時間復雜度為O（nlogn）遠小于原來的O（n3）。

圖4 存儲星對的hashtable

由于三角形特征維數(shù)少，冗余匹配和和錯誤匹配很難避免，故引入第四顆星，即圖5中D星，在已識別的三角形ABC中，通過對AD和BD的檢索來驗證D星點，成功識別三角形ABD[17]。接著在對AD和CD進行同樣檢索，成功識別三角形ACD。由于D是同一頂點，此時實際上是一個四面體。由此便可以大大降低匹配冗余率和錯誤率，接著為了進一步確定導航三角形，進入驗證識別環(huán)節(jié)，對待測星表中余下的潛在星點，逐一進行四面體驗證檢測，如圖5所示。最后為避免極端鏡像情況出現(xiàn)，又對三角形的三邊順序利用向量乘積的大小進行驗證。待測星圖中與導航星圖中的大小值完全一樣即可避免三角鏡像情況的出現(xiàn)，進一步降低了匹配錯誤率[18]。

星圖識別總的流程如圖6所示。

3 結果分析

將文獻中的傳統(tǒng)三角形算法和本文中提出的改進算法分別編程實現(xiàn)，并對500幅實拍星圖進行匹配驗證，在匹配門限為0.02°時原始算法的成功匹配率即給出正確姿態(tài)角的比例是76.8%（384/500）；而改進后的正確率達到99.2%（496/500）；在匹配門限為0.04°時原始算法的成功匹配率即給出正確姿態(tài)角的比50.2%（251/500）；而改進后的正確率達到96.4%（488/500）；并且在ubuntu系統(tǒng)下CPU 1.8 GHz，內存2G平均時間由原來的4 s左右降到目前的3 ms左右；其中隨機一幅星圖的匹配結果如圖7所示。

從圖7可以看到，在加了像素閾值的限制后，匹配更加精確甚至可以達到完全匹配；在提供姿態(tài)角都是正確結果的前提下，算法效率有了質的提高。

圖5 四面體檢測示意圖

圖6 星圖識別算法總體流圖

圖7 傳統(tǒng)算法與改進后效果對比圖

4 結論

綜合500幅星圖匹配結果可以看出本文所提出的改進方案不僅提高了星圖識別的正確率而且大幅度提升了算法效率。通過深入分析算法執(zhí)行過程，同時在數(shù)據(jù)存儲以及算法時間復雜度方面著手，從邏輯層面的算法剪枝到實現(xiàn)層面的數(shù)據(jù)結構替代都進行了針對性優(yōu)化，最終提高了算法的正確率和實時性，也提高了其全天球適應性。

參考文獻：

[1]梁斌，朱海龍，張濤，等.星敏感器技術研究現(xiàn)狀及發(fā)展趨勢[J].中國光學，2016（1）：16-29.

[2]Padgett C，Kreutzdelgado K，Udomkesmalee S.Evaluation of Star Identification Techniques[J].Journal of Guidance Control&Dynamics，2012，20（2）：259-267.

[3]蹤華，汪渤，周志強，等.一種基于模式匹配的自主星圖識別算法[J].北京理工大學學報，2015（10）：1032-1037.

[4]Balodis J，Zarin? A，Haritonova D，et al.Parame?ters for automated star identification[J].Geodesy&Cartography，2014，40（4）：163-170.

[5]He A X，Wang C C，Zhang H N.A Star Map Recognition Method Based on Multi-Layers SOFM Network[J].Applied Mechanics&Materials，2013（411-414）：1011-1014.

[6]李超兵，袁艷艷，王丹曄.基于特征圖形匹配法的高效星圖識別方法[J].中國空間科學技術，2016，36（4）：9-16.

[7]韓艷麗，劉峰.基于三角形匹配的空間小目標檢測算法[J].紅外與激光工程，2014，43（9）：3134-3140.

[8]時圣革，雷肖劍，于長海.星圖識別三角形算法綜述[J].光電技術應用，2014，29（5）：1-6.

[9]賀鵬程.一種改進的三角形識別算法[J].艦船電子工程，2012，32（4）：42-44.

[10]趙臻，高穎慧，王平.基于星圖識別算法的空間小目標識別[J].重慶理工大學學報自然科學版，2011，25（4）：97-101.

[11]胡敏，賀曉佳，王曉華.快速區(qū)域質心圖像匹配算法[J].電子測量與儀器學報，2011，25（5）：455-462.

[12]陸敬輝，王宏力，孫淵，等.三角形內切圓的星圖識別算法[J].紅外與激光工程，2011，40（4）：752-756.

[13]魏新國，徐佳，張廣軍.星敏感器質心定位的S曲線誤差補償[J].光學精密工程，2013（4）：849-857.

[14]賈輝，楊建坤，李修建，等.星敏感器高精度星點提取系統(tǒng)誤差分析及補償方法研究[J].中國科學：技術科學，2011（1）：69-76.

[15]曹南.用于大地天文測量的恒星視位置算法研究[D].西安：西安科技大學，2014.

[16]王萌萌.適用于皮納衛(wèi)星的微型星敏感器設計與測試[D].杭州：浙江大學，2014.

[17]鄭循江.輕小型高動態(tài)星敏感器技術研究[D].上海：上海交通大學，2012.

[18]蹤華，高曉穎，姬曉琴，等.一種自主星圖識別方法 [P].CN103335648A，2013.