幾何定位應用中恒星三角形識別簡化算法*

范　斌，鄧新蒲，楊俊剛，陳　軍，馬　超(國防科技大學電子科學與工程學院，湖南長沙410073)

?

幾何定位應用中恒星三角形識別簡化算法*

范斌，鄧新蒲，楊俊剛，陳軍，馬超
(國防科技大學電子科學與工程學院，湖南長沙410073)

摘要:為了滿足幾何定位應用對恒星識別的需求，從導航星的選取、導航特征庫的構造及識別算法的實現等方面對傳統三角形識別算法進行改進。首先，結合幾何定位傳感器跟蹤恒星的特性，提出導航星的快速選取方法。接著建立以星對角距和星對星等差為特征量的導航星特征庫。然后，在改進的三角形識別算法的基礎上，對觀測三角形特征向量進一步簡化。最后，在幾何定位的應用場景中對傳統三角形識別算法、三角形識別簡化算法進行仿真比較。實驗結果表明:在幾何定位的應用場景中，三角形識別簡化算法識別成功率、識別效率較高。能夠滿足幾何定位應用對恒星識別算法效率、可靠性的要求。

關鍵詞:恒星識別;導航星數據庫;三角形識別算法

*國家自然科學基金資助項目(61401474)

0　引言

恒星作為重要的特征信息在幾何定位技術中有著重要應用。而要實現基于恒星特征點的幾何定位，恒星的快速、準確提取與識別是關鍵。恒星識別本質上是一個模式識別問題，典型的恒星識別算法包括:基于圖形同構的算法［1］、基于星群的方法［2］以及基于神經網絡的方法［3］等。

目前，針對星敏感器的恒星識別算法已經比較成熟，而應用在幾何定位方面的恒星識別算法的參考文獻則相對較少。兩者在本質上都是將從星圖提取的恒星與導航星庫中的恒星進行匹配識別。但是幾何定位技術中恒星識別也有其固有的特點。幾何定位中，傳感器跟蹤深空背景的規律性比較強，傳感器的視場能夠根據衛星平臺的位置、姿態等信息進行預估，同時幾何定位中傳感器視場大小、靈敏度大小以及對算法的時間要求與星敏感器相比也有一定差異。

三角形識別算法是目前常用的恒星識別算法［4］，它是一種基于圖形同構的典型算法，其思想是使得由觀測恒星組成的三角形模式唯一地與導航星數據庫中的同構三角形匹配。為了提高三角形算法的實時性和魯棒性，同時滿足幾何定位中恒星識別的需求，本文從導航星的選取、導航特征庫的構造及識別算法的實現等方面對傳統三角形識別算法進行改進。結合幾何定位中傳感器視場能被預估的特性，提出了導航星的快速選取方法。通過對三角形識別算法的分析發現，識別過程中基本的運算單元是星對，由于星對的特征維數太低，需要將星對兩兩相交組成特征維數更高的導航三角形作為導航特征庫的基本單元。然而，幾何定位中經過導航星的快速選取，用于識別的導航星的數量大大減小，傳統三角形識別算法中作為基本判決單元的三角形必定包含大量的冗余信息，這將明顯降低識別算法的效率。于是可以考慮將導航星對作為導航特征庫的基本單元，同時對觀測三角形進行簡化處理，只保留觀測三角形部分信息。通過對傳統三角形識別算法的簡化，在保證算法識別成功率的同時，盡量提高算法的效率。

1　導航星數據庫的構造

導航星數據庫的建立是星圖識別的基礎工作。導航星數據庫由導航星與導航特征庫組成。導航星數據庫的設計不僅直接決定了存儲的容量，而且直接影響識別算法的效率與精度。導航星來源于基本星表，導航特征庫則是由導航星生成的特征向量組成。下面將從導航星的快速選取到星對的生成及存儲對導航星數據庫的構造進行描述。

1．1導航星的快速選取

傳感器跟蹤深空背景，以恒星位置作為幾何定位的參考矢量，星表中僅有極少數的恒星位于傳感器視場內。因此，對存在于傳感器視場內的恒星進行識別時，并不需要遍歷整個恒星星表。同時，為了滿足實時的幾何定位需求，遍歷整個星表也是不可取的。為解決這個問題，實現傳感器視場內恒星的快速選取，建立了包含各顆恒星及以其鄰近的50顆星為基本單元的表格［5］，如表1所示。

導航星的選取過程如圖1所示。該方法利用上一次的識別結果完成當前時刻搜索的初始化［6］。首先，當傳感器跟蹤開始時，需要遍歷整個導航星表確定距離視線最近的恒星，同時將該恒星對應的50顆臨近恒星選取出來進行恒星識別。在進行下一次恒星搜索時，便只需要在上一次選取出的50顆臨近恒星中進行搜索確定距離視軸最近的恒星，它所對應的50顆臨近恒星又可以被選取出來進行恒星識別。如此循環往復，當傳感器視線被地球遮擋或者在深空快速移動時，傳感器視線可能已經不在當前最鄰近的50顆恒星內，此時則需要重新對整個恒星星表進行搜索。

表1　部分最鄰近恒星星表

圖1　導航星的快速選取算法

1．2星對的生成和存儲

一般來說，傳統的三角形識別算法直接存儲導航三角形。三角形識別算法本質上是利用三角形三條邊的同構信息，各三角形之間必然存在公共邊，為了避免存儲冗余信息，可以采用直接存儲星對角距的形式來實現三角形識別算法［7］。相同數量的導航星生成星對的數量要遠遠少于導航三角形的數量，因此其存儲容量將大大減小，識別算法的計算量也將大大減少。但是僅僅由星對角距構成的導航星特征庫維數太低，導航星數據庫中除了存儲恒星位置信息外，還存儲了導航星的亮度信息。因此，還可以將導航星對星等差作為識別特征。為了描述導航星對，同時為了計算方便，對星對包含的兩顆恒星按星等升序排列，并定義如下:

為進一步提高星對搜索效率，對星對角距升序排列，并按照星對角距大小將星對等間隔劃分成各個區段，同時引入索引向量，索引向量中存儲各個區段的起始位置，這樣根據星對角距便能很快通過索引向量查找到其在導航特征庫中的位置，從而減少識別過程中特征量比較的次數，提高搜索效率。例如: Index［10］=203，Index［11］= 390，表示星對角距從203顆星到390顆星大于10小于11。

2　三角形識別算法的描述

2．1特征查找過程

由于系統噪聲及恒星提取誤差的存在，觀測星圖中星對角距與導航特征庫中相匹配的星對角距之間必然存在一定偏差。在進行識別時需要設定一個判決門限來容許這種偏差。判決門限的設置受限于恒星的位置精度和星等精度。為了盡量避免恒星的漏匹配和誤匹配，本文算法角距判決門限設為εp= 5σp，星等判決門限設為εm= 5σm，其中σp與σm為位置和星等的測量均方誤差。三角形識別過程中需要將觀測三角形的每一條邊與導航星對進行比較，找出其中滿足如式(1)所示閾值條件的導航星對。

在1．2小節，恒星特征庫中引入了索引向量，在特征查找過程中索引向量的引入可以大大簡化特征查找的過程。當觀測恒星兩點之間的角距差為fd時，則通過fd±εd確定角距的范圍區間［m，n］，再根據該區間即可利用索引向量求出特征查找的范圍。

2．2三角形識別簡化算法

三角形識別算法利用三角形各邊相互之間的約束關系，可以刪除一大批誤匹配，大大提高識別成功率。

在幾何定位中，通過導航星的快速選取，用于匹配的導航星的數量大大減少。而在星敏感器恒星識別中廣泛應用的三角形識別算法，則將三角形作為導航特征庫的基本單元。隨著用于匹配的導航星的數量減少，三角形特征量的冗余也就相應增大。在1．2小節，已經通過將星對作為導航特征庫的基本單元對三角形識別算法進行了改進。為了對三角形識別算法做進一步簡化，由導航三角形到導航星對的簡化得到啟發，在觀測三角形的建立過程中也可借鑒類似的思想。考慮到觀測三角形與導航星對的比較是觀測三角形的三邊分別遍歷導航星對，不妨對觀測三角形進一步簡化，只保留三角形的兩邊信息，建立如圖2所示的觀測三角形結構。

圖2中，a、b、c分別表示3顆觀測恒星，ab、ac分別表示由3顆觀測恒星組成的星對。觀測三角形模式結構體定義如下:

圖2　觀測三角形示意圖

其中star_a，star_b，star_c表示3顆按照星等升序排列的觀測恒星。

在簡化觀測三角形與引入導航星對的基礎上進行恒星的識別。其算法描述如下:

1)觀測星圖的篩選:當傳感器拍攝到觀測星圖后，首先需要判斷觀測星圖中是否存在大于等于3顆的觀測恒星。只有當觀測恒星的數量大于等于3時才能利用三角形識別算法進行匹配。

2)記錄與觀測三角形相匹配的候選導航星對:取觀測三角形的兩邊ab、ac，通過索引向量判斷其在導航星對特征庫中的搜索范圍，在該搜索范圍中搜索滿足星對角距和星等差判決門限的導航星對，記錄到寬度為3的二維數組中，其記錄格式見表2。

表2　候選導航星對記錄數組

3)篩選滿足約束關系的導航星對:三角形的兩邊ab、ac交于公共點a，即與a對應的導航星應該出現2次或2次以上，所以與a對應的出現次數少于2的候選導航星及由該星組成的導航星對將作為整體被剔除，即候選導航星對將被置為0。剔除結果見表3。

表3　導航星對剔除結果

4)識別結果:依據ab、ac交于一點的約束條件，將數組中余下的候選導航星組成三角形，即可得由(22，26，37)組成的三角形為識別結果。

3　仿真結果及分析

3．1模擬傳感器觀測視場

仿真試驗以GEO衛星搭載的掃描相機作為傳感器。掃描相機的視場為8°×8°，像元數為4000×4000。

試驗中用兩種服從均值為零的正態分布來模擬誤差的影響。一種是恒星的位置誤差，另一種是恒星的星等誤差。

仿真時，首先選擇依巴谷星表作為基本星表，依據傳感器的探測能力，提取星等小于6的恒星為導航星。接著隨機產生一個視軸位置，從導航星中選取所有可能處于該視場內的恒星，然后加入一定的位置誤差和星等誤差，最后將這些觀測恒星投影到掃描相機的像平面上。觀測星圖如圖3所示。

圖3　觀測星圖

3．2算法性能比較

試驗環境為: Inter Core i5-4570 CPU 3．2GHz，4GB內存，Windows7 64位操作系統。

本試驗在不同的位置誤差和星等誤差條件下，隨機產生1000個視軸位置［8］。采用傳統三角形識別算法和三角形識別簡化算法分別進行仿真，并對識別時間、識別成功率進行統計。仿真結果見表4。

從表4中可以看出，在相同的方位噪聲和星等噪聲條件下三角形識別簡化算法的識別成功率略低于傳統三角形識別算法，但是耗時卻遠遠少于傳統三角形識別算法耗時。例如，當不加方位噪聲和星等噪聲時，傳統的三角形識別算法耗時為0．1399s，識別成功率為98．9%，而三角形識別簡化算法的耗時僅為0．0140s，識別成功率為98．4%。當方位噪聲為0．005，星等噪聲為0時，傳統的三角形識別算法耗時為0．2749s識別成功率為80．8%，而三角形識別簡化算法的耗時僅為0．0237s，識別成功率為78．4%。當方位噪聲為0．003，星等噪聲為0．5時，傳統的三角形識別算法耗時為0．1875s，識別成功率為86．4%，而三角形識別簡化算法的耗時僅為0．0185s，識別成功率為84．4%。隨著方位噪聲及星等噪聲的增加，兩種算法的耗時都相應減少，識別成功率也相應降低。

表4　算法性能對照表

4　結束語

本文依據幾何定位中恒星識別的特點，從導航星的選取、導航特征庫的構造及識別算法的實現等方面對傳統三角形識別算法進行改進。首先結合幾何定位中傳感器視場能夠預估的特性，提出導航星的快速選取方法，大大降低了對后續處理算法的性能要求。然后對導航特征庫及觀測三角形模式進行簡化，改進識別過程中查找、記錄及剔除的方式。實驗結果表明:該算法在相同方位噪聲、星等噪聲的條件下能夠減少處理時間，并具有較高的識別成功率。

參考文獻:

［1］Liebe CC．Pattern recognition of star constellations for spacecraft applications［J］．IEEE，Aerospace and Electronics Systems Magazine，1993，8(1) : 31－39．

［2］CurtisP，Kenneth KD．A grid algorithm for autonomous star identification［J］．IEEE，Aerospace and Electronics Systems Magazine，1997，33(1) : 202－213．

［3］Accardo D．Rufino G．Star field feature characterization for initial acquisition by neural networks［C］∥IEEE，Aerospace Conference Proceedings 2002，2002: 2319－2330．

［4］Liebe CC．Star tracker for attitude determination［J］．IEEE Trans．on Aerospace and Electronic System，1995，31(1) : 10 －16．

［5］Thomas MC，Chang KC．Sensor calibration using in－situ celestial observations to estimate bias in space-based missile tracking［J］．IEEE Trans．On Aerospace and Electronics Systems，2012，4(1) : 1403－1427．

［6］SamannMA，MortariD，Junkins JL．Recursive mode star identification algorithms［J］．IEEE Trans．on Aerospace and Electronic Systems，2005，41(4) : 1246－1254．

［7］張磊，何昕，魏仲慧，等．三角形星圖識別算法［J］．光學精密工程，2010，18(2) : 458－463．

［8］鄭勝，吳偉仁，田金文，等．一種基于三角形幾何結構的星圖識別算法［J］．光學技術，2004，30(1) : 70－73．

Simplification of star triangle identification algorithm for geometrical location

Fan Bin，Deng Xinpu，Yang Jungang，Chen Jun，Ma Chao
(College of Electronic Science and Engineering，National University of Defense Technology，Changsha 410073，Hunan，China)

Abstract:In order to meet the requirement of geometrical location for star identification，the traditional triangle identification algorithm is modified in selection of guide star，construction of database of star characteristic and algorithm implementation．First，based on the sensor feature in geometrical location，rapid star selection algorithm is proposed．The database of star characteristic including star pairs angular distances and magnitude difference is constructed．Then，based on the modification of triangle identification，observation triangle feature vectors are simplified．Finally，in the scenario of geometrical location，traditional triangle identification algorithm，and simplification of triangle identification algorithm are simulated and compared．The simulation results show that the simplification of triangle algorithm can lower the mismatches probability，increase the speed of identification，and can meet the star identification algorithm’s demand for efficiency and reliability．

Key words:star identification; database of star characteristic; triangle identification algorithm

作者簡介:范斌(1990－)，男，碩士，主要研究方向為空間信息獲取與處理。

收稿日期:2015－11－12; 2016－01－05修回。

中圖分類號:V448．22

文獻標識碼:A