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

袁曉波，張 超，時春霖

(1.信息工程大學 導航與空天目標工程學院，鄭州 450001；2.北斗導航應用技術河南省協同創新中心,鄭州 450001； 3.61206部隊，北京 100042)

?

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

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

(1.信息工程大學 導航與空天目標工程學院，鄭州 450001；2.北斗導航應用技術河南省協同創新中心,鄭州 450001； 3.61206部隊，北京 100042)

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

星圖識別；K矢量；四邊形；標識符匹配

0 引言

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

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

K矢量查找法是一種通用的單調函數快速查找方法[13]，具有在大量數據中快速確定數據位置的特點；四邊形匹配法基于4顆基準星，通過構造多個匹配三角形，提高了匹配的準確率[14]。基于此，本文提出了一種基于K矢量和四邊形匹配法則的星圖識別算法，并通過仿真星圖和實測星圖對算法的實時性和準確性進行了驗證，并取得了良好效果。

1 星敏感器成像原理

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

(1)

(2)

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

2 基準星搜索

2.1 導航星庫的編制

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

表1 導航星庫

2.2K矢量原理

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

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

z(x)=a1x+a0。

(3)

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

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

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

(4)

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

(5)

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

2.3 基準星的搜索匹配

將星間角距的余弦值cosθij按從小到大的順序排序，構成單調遞增的向量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)構成方程

cosθij=a1k+a0。

(6)

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

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

(7)

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

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

2.4 基準星的判斷

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

1)構造標識符矩陣H=01×n，n為星表星的總個數。

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

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

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

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

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

3 基于基準星的全視場匹配

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

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

(8)

設em為設定的判斷限值，取10-6，當eij≥em時認為該星非星表對應星，該星表星匹配結束，取下一顆星表星進行匹配；當eij

4 實驗與結果分析

4.1 計算機仿真

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

表2 星敏感器參數

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

4.2 實測星圖實驗

對100幅由某遙感衛星下傳的連續星圖進行同樣的處理，統計匹配耗時，結果如圖4所示。星敏感器部分性能參數見表3。

表3 某衛星星敏參數

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

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

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

5 結束語

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

[1] 張廣軍．星圖識別[M].北京：國防工業出版社，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] 蔡迎波，惠寶聚，孟士超.星圖識別算法的設計與實現[J].光學與廣電技術，2009，7(2)：37-39.

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

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

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

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

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

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

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

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

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

[14]林濤，周建林，張鈞萍，等.四邊形全天自主識別算法[J].宇航學報，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

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

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

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

袁曉波，張超，時春霖.一種改進的基于K矢量的星圖識別算法[J].導航定位學報,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