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

?

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

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

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

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

*國(guó)家自然科學(xué)基金資助項(xiàng)目(61401474)

0　引言

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

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

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

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

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

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

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

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

表1　部分最鄰近恒星星表

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

1．2星對(duì)的生成和存儲(chǔ)

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

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

2　三角形識(shí)別算法的描述

2．1特征查找過程

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

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

2．2三角形識(shí)別簡(jiǎn)化算法

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

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

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

圖2　觀測(cè)三角形示意圖

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

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

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

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

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

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

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

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

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

3．1模擬傳感器觀測(cè)視場(chǎng)

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

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

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

圖3　觀測(cè)星圖

3．2算法性能比較

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

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

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

表4　算法性能對(duì)照表

4　結(jié)束語

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

參考文獻(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］張磊，何昕，魏仲慧，等．三角形星圖識(shí)別算法［J］．光學(xué)精密工程，2010，18(2) : 458－463．

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

作者簡(jiǎn)介:范斌(1990－)，男，碩士，主要研究方向?yàn)榭臻g信息獲取與處理。

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

中圖分類號(hào):V448．22

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