一種改進的基于K矢量的星圖識別算法

袁曉波，張 超，時春霖

(1.信息工程大學(xué) 導(dǎo)航與空天目標(biāo)工程學(xué)院，鄭州 450001；2.北斗導(dǎo)航應(yīng)用技術(shù)河南省協(xié)同創(chuàng)新中心,鄭州 450001； 3.61206部隊，北京 100042)

?

一種改進的基于K矢量的星圖識別算法

袁曉波1,2，張 超1,2，時春霖1,3

(1.信息工程大學(xué) 導(dǎo)航與空天目標(biāo)工程學(xué)院，鄭州 450001；2.北斗導(dǎo)航應(yīng)用技術(shù)河南省協(xié)同創(chuàng)新中心,鄭州 450001； 3.61206部隊，北京 100042)

為了提高星敏感器定姿中星圖識別的精度和效率，基于K矢量原理和四邊形匹配法則提出一種改進的星圖匹配方法：首先基于K矢量查找法快速匹配星間角距，得到角距的匹配組合；再采用一種基于標(biāo)識符的快速判別方法進行導(dǎo)航星的判別，得到4顆匹配成功的基準(zhǔn)星；最后基于4顆基準(zhǔn)星按四邊形匹配法則完成全視場的匹配。實驗結(jié)果表明，該方法具有良好的實時性和準(zhǔn)確性。

星圖識別；K矢量；四邊形；標(biāo)識符匹配

0 引言

姿態(tài)測量是航天器飛行的重大核心技術(shù)之一，對保證航天器準(zhǔn)確入軌和變軌、高性能飛行、可靠對地通信、高精度對地觀測，及順利完成各種空間任務(wù)具有重要意義[1]。星敏感器作為一種高性能姿態(tài)敏感器，具有精度高、無誤差積累、可自主標(biāo)定和故障恢復(fù)等優(yōu)點，在航天器姿態(tài)測量中擁有廣泛的應(yīng)用。

星圖識別是星敏感器定姿系統(tǒng)的關(guān)鍵技術(shù)之一。星圖識別可以看作是模式識別問題中的一種[2]，其實質(zhì)是從星圖星中提取識別特征，與從導(dǎo)航星表中提取的識別特征進行匹配，以確定星圖星和星表星的對應(yīng)關(guān)系。經(jīng)過國內(nèi)外學(xué)者多年的研究和工程實踐，目前已發(fā)展出多種星圖識別方法，大致可以分為2大類：一類是子圖同構(gòu)類算法，如三角形算法[3]、多邊形算法[4]、匹配組算法[5]等；另一類是基于星模式的星圖識別算法，如柵格算法[6-7]、字符串算法[8]、金字塔算法等[9]，此外還有奇異值分解法[10]、基于遺傳算法的星圖識別算法[11]、基于神經(jīng)網(wǎng)絡(luò)的算法[12]等較新的模式識別算法。衡量某種識別算法優(yōu)劣與否的重要指標(biāo)是實時性和準(zhǔn)確率。以三角形算法為代表的子圖同構(gòu)類算法抑或匹配冗余大，抑或在解決冗余問題的同時增加了運算量，影響星敏感器姿態(tài)輸出的實時性；以柵格法為代表的模式識別算法具有容錯能力強、存儲容量小的優(yōu)點，但在特征提取上仍有不足，匹配準(zhǔn)確率不高；以基于神經(jīng)網(wǎng)絡(luò)的識別算法為代表的新式算法雖然新穎，但過程復(fù)雜，不利于工程化。

K矢量查找法是一種通用的單調(diào)函數(shù)快速查找方法[13]，具有在大量數(shù)據(jù)中快速確定數(shù)據(jù)位置的特點；四邊形匹配法基于4顆基準(zhǔn)星，通過構(gòu)造多個匹配三角形，提高了匹配的準(zhǔn)確率[14]?；诖耍疚奶岢隽艘环N基于K矢量和四邊形匹配法則的星圖識別算法，并通過仿真星圖和實測星圖對算法的實時性和準(zhǔn)確性進行了驗證，并取得了良好效果。

1 星敏感器成像原理

如圖1所示，星敏感器的成像模型一般為小孔成像。恒星(αi,δi)經(jīng)星敏感器成像后在星圖中的成像中心為(xi,yi)，分別計算恒星在恒星慣性系和星敏感器坐標(biāo)系中的指向Ri、ri為：

(1)

(2)

二者存在唯一的關(guān)系ri=C·Ri。式中：(x0,y0)為像主點坐標(biāo)；f為星敏感器的角距；C為恒星慣性矢量與像坐標(biāo)矢量之間的轉(zhuǎn)換矩陣。

2 基準(zhǔn)星搜索

2.1 導(dǎo)航星庫的編制

根據(jù)星敏感器敏感的極限星等、視場大小，從基礎(chǔ)星表中篩選出星敏感器能捕捉到信號的恒星，通過剔除雙星、變星、視位置計算，結(jié)合采用的匹配特征量，制成導(dǎo)航星庫。首先根據(jù)星敏感器捕捉到信號的極限星等刷選出待檢索的導(dǎo)航星，計算兩兩之間的角距的余弦值cosθij；再根據(jù)星敏感器的視場角對cosθij做進一步刷選，把提取出來的cosθij按升序排列。選依巴谷星表作為基礎(chǔ)星表，按極限星等5.5、視場20.3°編制導(dǎo)航星庫(見表1)，共選出2 827顆導(dǎo)航星，構(gòu)成星對269 421對。

表1 導(dǎo)航星庫

2.2K矢量原理

K矢量是指由一系列單調(diào)遞增的元素構(gòu)成的矢量，K矢量查找法是基于K矢量建立的一種快速的數(shù)據(jù)查找方法，具有在大量數(shù)據(jù)中快速查找目標(biāo)元素索引位置的特點，其原理如下[13，15]：

在一個長度為n的單調(diào)遞增向量s中，設(shè)首末端點分別為(1,s(1))、(n,s(n))，連接首末端點即可構(gòu)成一條直線?？紤]到計算誤差等因素的存在，為了充分包含2個端點，需要讓直線稍微傾斜一點。設(shè)ξ為計算誤差，按ξ對直線進行傾斜，即連接首末點(1,s(1)-ξ)、(n,s(n)+ξ)，因此直線方程可以寫成

z(x)=a1x+a0。

(3)

令K(1)=0、K(n)=n，其中向量K的形成規(guī)則為K(i)=j當(dāng)s(i)≤z(i)

可以看出：K矢量實際表示為向量s中值小于a1x+a0的個數(shù)。

一旦K矢量建立好后，即可以估計任意范圍[sa,sb]所對應(yīng)的K矢量為

(4)

式中：?x 」表示小于x的最大整數(shù)；「x?表示大于x最小整數(shù)，ib、it分別表示3矢量檢索的起始位置。當(dāng)ib和it都計算完后，即可以計算出K矢量的起始位置

(5)

以上就完成了K矢量的建立與查找，下面將K矢量應(yīng)用于星圖識別中。

2.3 基準(zhǔn)星的搜索匹配

將星間角距的余弦值cosθij按從小到大的順序排序，構(gòu)成單調(diào)遞增的向量s，連接首尾點(1,(1))、(n,s(n))，平均步長為d=(s(n)-s(1))/(n-1)。為了將首尾點充分包含，這里按d/2對直線做一定的傾斜，即連接點(1,s(1)-d/2)、(n,s(n)+d/2)構(gòu)成方程

cosθij=a1k+a0。

(6)

式中：a1=dn/(n-1)，為直線斜率；a0=s(1)-a1-d/2，為方程常數(shù)項。

考慮到測量誤差的存在，只能確定角距余弦值的范圍。假設(shè)測量誤差為ξ，cosθij對應(yīng)的K矢量為

(7)

將式(7)代入(5)式即可計算K矢量的起始位置。

根據(jù)K矢量的起始位置可得到待匹配角距在導(dǎo)航星庫中可能的星對組合Cij(注：i、j分別表示匹配角距的2顆恒星的序號)。由于測量誤差的存在，每個角距可能會得到多個匹配成功的星對組合，而無法得到唯一的匹配結(jié)果，還需結(jié)合其他角距的匹配結(jié)果進一步判斷星圖星與導(dǎo)航星的對應(yīng)關(guān)系。

2.4 基準(zhǔn)星的判斷

一般而言，在C12、C13、C14、C23、C24、C34這6個集合中采用遍歷的方法確定恒星的對應(yīng)關(guān)系需要(n12·n13·n14·n23·n24·n34)次的比較運算，假設(shè)平均每條角距有10個匹配組合，則需要進行106次比較運算，這樣十分耗時。為了避免無用的比較運算、提高匹配效率，這里采用一種基于標(biāo)識符的簡單快速的導(dǎo)航星判別方法來確定4顆導(dǎo)航星在星表中的位置(s1,s2,s3,s4)，其具體步驟為：

1)構(gòu)造標(biāo)識符矩陣H=01×n，n為星表星的總個數(shù)。

2)掃描C12，將C12中出現(xiàn)的恒星對應(yīng)的標(biāo)識符設(shè)置為1，即假如(i,j)∈C12，則H(i)=1,H(j)=1；記下標(biāo)識符為1的匹配星序號設(shè)為s1，與之組成星對的另一顆星的星序號為s2。

3)掃描C13，對于C13中出現(xiàn)的恒星，其標(biāo)識符在原來的基礎(chǔ)上+1，即如果其標(biāo)識符為0，則置為1，如果標(biāo)識符為1，則置為2；記下與標(biāo)識符為2的恒星組成星對的另一顆星的星序號s3。

4)掃描C14，對于C14中出現(xiàn)的恒星，其標(biāo)識符在原來的基礎(chǔ)上+1，記下與標(biāo)識符為3的恒星組成星對的另一顆星的星序號s4。

5)掃描C23、C24、C34，如果星對組合滿足(s2,s3)∈C23且(s2,s4)∈C24且(s3,s4)∈C34，則認(rèn)為匹配成功。這樣就得到了與(p1,p2,p3,p4)相對應(yīng)的星表星組合(s1,s2,s3,s4)。

采用本方法的搜索量為n12+n13+n14+n23+n24+n34，搜索量比遍歷組合的方法大大縮減，且通過步驟5)中3星兩兩組合驗證的方法大大提高了識別的正確率。

3 基于基準(zhǔn)星的全視場匹配

在得到4顆基準(zhǔn)星的匹配結(jié)果后，為提高剩余星的匹配速率，由4顆基準(zhǔn)星計算出一個概略姿態(tài)，根據(jù)概略姿態(tài)和星敏感器參數(shù)，進一步篩選星表。將待匹配的星圖星與4顆基準(zhǔn)星中的任意2顆星圖星組成角距三角形，從星表中任意挑選1顆與這2顆星的星表星組成角距三角形，比較星圖角距三角形與星表角距三角形的相似度。每顆待匹配星與4顆基準(zhǔn)星組成6個角距三角形，當(dāng)這6個角距三角形與星表角距三角形都匹配時，則認(rèn)為該星匹配成功。

如圖2，假設(shè)(p1,p2,p3,p4)為匹配成功的4顆星圖星，(s1,s2,s3,s4)為對應(yīng)的星表星，p為待匹配的星圖星，s為檢索的星表星，以ri表示p與pi的角距，Ri表示s與si之間的角距，評價星圖三角形Δppipj與Δssisj的相似度標(biāo)準(zhǔn)為

(8)

設(shè)em為設(shè)定的判斷限值，取10-6，當(dāng)eij≥em時認(rèn)為該星非星表對應(yīng)星，該星表星匹配結(jié)束，取下一顆星表星進行匹配；當(dāng)eij

4 實驗與結(jié)果分析

4.1 計算機仿真

用STK(satellitetoolkit)軟件內(nèi)置的ALOS遙感衛(wèi)星生成軌道和姿態(tài)數(shù)據(jù)，根據(jù)軌道和姿態(tài)數(shù)據(jù)及星敏安裝矩陣計算星敏感器的指向，再根據(jù)星敏指向仿真得到300幅連續(xù)的星圖。星敏感器的部分參數(shù)見表2。

表2 星敏感器參數(shù)

采用平方質(zhì)心法提取星點，提取星點個數(shù)在14～23之間。按本文方法分別進行初始模式和跟蹤模式下的匹配識別，實驗環(huán)境為MATLAB 2014a、Intel i5處理器、8G內(nèi)存、win7系統(tǒng)，星點測量誤差為0.5個像素。匹配耗時如圖3所示。實驗表明，匹配成功率為100 %，單幅星圖匹配耗時平均耗時0.072 6 s，最長耗時0.128 6 s。

4.2 實測星圖實驗

對100幅由某遙感衛(wèi)星下傳的連續(xù)星圖進行同樣的處理，統(tǒng)計匹配耗時，結(jié)果如圖4所示。星敏感器部分性能參數(shù)見表3。

表3 某衛(wèi)星星敏參數(shù)

提取星點個數(shù)在13～18之間。由于空間環(huán)境復(fù)雜，為保證匹配成功率，對星點的測量誤差放大到1像素。實驗表明，匹配成功率為100 %，匹配平均耗時0.089 9 s，最長0.206 5 s。

基于匹配結(jié)果，采用QUEST方法進行姿態(tài)解算，結(jié)果如圖5。可以看出：3個姿態(tài)角變化平穩(wěn)，基本呈線性，這與遙感衛(wèi)星短時間內(nèi)姿態(tài)變化緩慢是相對應(yīng)的；同時也間接說明了匹配結(jié)果的正確性，因為如果存在誤匹配的話，姿態(tài)角將會出現(xiàn)突變。

從以上2組實驗可知，仿真實驗和實測星圖實驗結(jié)果類似，均可實現(xiàn)100 %的準(zhǔn)確率，且輸出率可分別達到13 Hz左右和11 Hz左右，具有較好的實時性；同時說明仿真星圖與實際星空較為符合，仿真過程較為合理，也驗證了本文提出的星圖匹配方法在實踐中應(yīng)用的可行性。

5 結(jié)束語

星圖匹配是星敏感器定姿的基礎(chǔ)，高效可靠的星圖匹配算法是星敏感器實現(xiàn)實時、可靠地輸出姿態(tài)的重要保證。基于K矢量查找法和四邊形匹配法則，本文提出了一種匹配方法，并基于仿真星圖和實測星圖對方法進行了驗證，結(jié)果表明該方法具有良好的實時性和準(zhǔn)確性：在MATLAB2014a環(huán)境下，仿真星圖和實測星圖的匹配輸出頻率分別在13Hz、11Hz左右，均在10Hz以上，成功率100 %，具有較好的實時性和準(zhǔn)確性，在效率更高的程序環(huán)境下會有更高的輸出率。

[1] 張廣軍．星圖識別[M].北京：國防工業(yè)出版社，2011:13-14.

[2]LIEBECC.Patternrecognitionofstarconstellationsforspacecraftapplications[J].IEEETransonAerospaace&ElectronicSystemMagazine,1993,8(1):31-39.

[3]LIEBECC.Startrackersforattitudedetermination[J].IEEETransonAerospaace&ElectronicSystemMagazine,1995,10(6):10-16.

[4] 蔡迎波，惠寶聚，孟士超.星圖識別算法的設(shè)計與實現(xiàn)[J].光學(xué)與廣電技術(shù)，2009，7(2)：37-39.

[5] 冉曉強，汶德勝，邱躍洪，等.一種新的三角形識別算法[J].光子學(xué)報，2009，38(7)：1867-1871.

[6]PADGETTC,KREUTZ-DELGADOK.Agridalgorithmforautonomousstaridentification[J].IEEETrans.onAerospaace&ElectronicSystems,1997,33(1):202-213.

[7] 唐武盛，楊建坤，文少軍，等.全天自主星圖識別網(wǎng)格算法問題分析與改進[J].激光與電子學(xué)進展，2016(2)：102-108.

[8] 許士文，李葆華，張迎春.用字符串匹配進行星圖識別的導(dǎo)航庫存儲方法[J].哈爾濱工業(yè)大學(xué)學(xué)報，2005，37(6)：819-821.

[9] 李輝，王安國，張磊.改進金字塔算法用于小視場星圖識別[J].應(yīng)用光學(xué)，2013，34(2)：267-272.

[10]刑一凡，王建華.一種改進的基于奇異值分解的星圖識別算法[J].智能計算機與應(yīng)用，2014(2)：21-24.

[11]李立宏，張福恩，林濤.一種基于遺傳算法的全天自主星圖匹配算法[J].光電工程，2000，27(5)：15-18.

[12]馬濤，孫紅輝，肖松，等.基于BP神經(jīng)網(wǎng)絡(luò)的小樣本星圖識別算法[J].應(yīng)用光學(xué)，2009，30(2)：252-256.

[13]邢飛，尤政，董瑛.基于導(dǎo)航星域和K矢量的快速星圖識別算法[J].宇航學(xué)報，2010，31(10)：2302-2308.

[14]林濤，周建林，張鈞萍，等.四邊形全天自主識別算法[J].宇航學(xué)報，2000，21(2)：82-85.

[15]MORTARID,NETAB.K-vectorrangesearchingtechnique[EB/OL].(2015-06-30)[2016-07-21].https://www.researchgate.net/profile/D_Mortari.

A modified star map identification algorithm based onKvector

YUANXiaobo1,2,ZHANGChao1,2,SHIChunlin1,3

(1.Institute of Navigation & Aerospace, Information Engineering University, Zhengzhou 450001, China;2.Beidou Navigation Technology Collaborative Center of Henan, Zhengzhou 450001, China;3.Troops 61206, Beijing 100042, China)

In order to improve the accuracy and efficiency of identification of star map in the attitude determination of star sensors, the paper proposed a modified star map matching method based on Kvectorsearchingtechniqueandquadranglematchingalgorithm:firstly,theangulardistancebetweenstarsanditsrangewerematchedwiththeKvectorsearchingtechnique;secondly,anavstaridentificationalgorithmwasestablishedtodistinguishthenavstarbasedonanalgorithmofidentifier,andthengot4navstars;finally,theallfieldmatchingwasaccomplishedwiththe4navstarsbasedonquadranglematchingalgorithm.Experimentalresultshowedthattheproposedmethodwouldhaveagoodreal-timeperformanceandhighaccuracy.

star map identification; Kvector;quadrangle;identifiermatching

2016-08-29

國家自然科學(xué)基金項目(11373001，41504018)。

袁曉波(1992—)，男，江西宜春人，碩士研究生，研究方向為航天器定姿與自主導(dǎo)航。

張超(1972—)，男，吉林白城人，博士，教授，研究方向為天文測量與導(dǎo)航。

袁曉波，張超，時春霖.一種改進的基于K矢量的星圖識別算法[J].導(dǎo)航定位學(xué)報,2017,5(2):55-59.(YUANXiaobo,ZHANGChao,SHIChunlin.AmodifiedstarmapidentificationalgorithmbasedonKvector[J].JournalofNavigationandPositioning,2017,5(2):55-59.)DOI：10.16547/j.cnki.10-1096.20170210.

P

A

2095-4999(2017)02-0055-05