幾何定位應(yīng)用中恒星三角形識別簡化算法*

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

?

幾何定位應(yīng)用中恒星三角形識別簡化算法*

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

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

關(guān)鍵詞:恒星識別;導(dǎo)航星數(shù)據(jù)庫;三角形識別算法

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

0　引言

恒星作為重要的特征信息在幾何定位技術(shù)中有著重要應(yīng)用。而要實現(xiàn)基于恒星特征點的幾何定位，恒星的快速、準(zhǔn)確提取與識別是關(guān)鍵。恒星識別本質(zhì)上是一個模式識別問題，典型的恒星識別算法包括:基于圖形同構(gòu)的算法［1］、基于星群的方法［2］以及基于神經(jīng)網(wǎng)絡(luò)的方法［3］等。

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

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

1　導(dǎo)航星數(shù)據(jù)庫的構(gòu)造

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

1．1導(dǎo)航星的快速選取

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

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

表1　部分最鄰近恒星星表

圖1　導(dǎo)航星的快速選取算法

1．2星對的生成和存儲

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

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

2　三角形識別算法的描述

2．1特征查找過程

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

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

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

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

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

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

圖2　觀測三角形示意圖

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

在簡化觀測三角形與引入導(dǎo)航星對的基礎(chǔ)上進(jìn)行恒星的識別。其算法描述如下:

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

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

表2　候選導(dǎo)航星對記錄數(shù)組

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

表3　導(dǎo)航星對剔除結(jié)果

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

3　仿真結(jié)果及分析

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

仿真試驗以GEO衛(wèi)星搭載的掃描相機(jī)作為傳感器。掃描相機(jī)的視場為8°×8°，像元數(shù)為4000×4000。

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

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

圖3　觀測星圖

3．2算法性能比較

試驗環(huán)境為: Inter Core i5-4570 CPU 3．2GHz，4GB內(nèi)存，Windows7 64位操作系統(tǒng)。

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

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

表4　算法性能對照表

4　結(jié)束語

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

參考文獻(xiàn):

［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］．光學(xué)精密工程，2010，18(2) : 458－463．

［8］鄭勝，吳偉仁，田金文，等．一種基于三角形幾何結(jié)構(gòu)的星圖識別算法［J］．光學(xué)技術(shù)，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

文獻(xiàn)標(biāo)識碼:A