錢華明， 郎希開， 李 猛

(1.哈爾濱工程大學(xué) 自動化學(xué)院，黑龍江 哈爾濱 150001；2.中航光電科技股份有限公司，河南 洛陽 471003)

一種改進(jìn)的柵格星圖識別算法*

錢華明1， 郎希開1， 李 猛2

(1.哈爾濱工程大學(xué) 自動化學(xué)院，黑龍江 哈爾濱 150001；2.中航光電科技股份有限公司，河南 洛陽 471003)

針對傳統(tǒng)的柵格算法提取的特征模式不能反映其內(nèi)在相似程度進(jìn)而影響星圖識別準(zhǔn)確性的問題，提出了一種改進(jìn)的柵格算法。利用特征模式間的度量函數(shù)反映不同特征模式之間的相似程度，解決了傳統(tǒng)算法中由于位置量測誤差造成的影響。根據(jù)實際情況建立了仿真環(huán)境，進(jìn)行了仿真實驗。結(jié)果表明：當(dāng)星點位置噪聲大于1.5像素時，改進(jìn)算法的星圖識別成功率明顯高于現(xiàn)有的柵格算法；在存在“假星”的情況下改進(jìn)算法的星圖識別成功率優(yōu)于現(xiàn)有的算法，驗證了算法的有效性。

柵格算法； 特征模式； 相似程度； 度量函數(shù)

0 引 言

星敏感器是航天器完成航天任務(wù)的主要工作部件，為航天器提供高精度的姿態(tài)信息。利用星敏感器確定姿態(tài)的過程分為：星空拍攝、質(zhì)心提取、星圖識別和姿態(tài)計算4個步驟。星圖識別的實質(zhì)就是在星表中尋找與觀測星圖中觀測星相對應(yīng)的導(dǎo)航星[1]。星圖識別技術(shù)是星敏感器的關(guān)鍵技術(shù)之一，識別速度和識別成功率是衡量星圖識別算法的關(guān)鍵指標(biāo)。

目前,常用的星圖識別算法根據(jù)特征提取方式的不同可以分為兩大類：子圖同構(gòu)類算法和模式識別類算法[2]。子圖同構(gòu)類算法把星敏感器得到的觀測星圖看成是全天球星圖的子圖，以恒星作為頂點，利用恒星的星等以及它們之間的角距等信息，以線段、三角形、多邊形等作為基本元素來進(jìn)行星圖識別。三角形算法[3],多邊形角距匹配算法,匹配組算法[4]等算法都屬于這一類。模式識別類算法通過給觀測星構(gòu)建特征模式，在導(dǎo)航星庫中尋找與觀測星的特征模式最為相近的星。柵格算法[5]、基于統(tǒng)計特征的算法[6]為此類算法中具有代表性的算法。上述的算法中，三角形算法由于其算法結(jié)構(gòu)簡單、易于實現(xiàn)等優(yōu)點應(yīng)用最為廣泛,但也存在著諸多缺點，比如所需的導(dǎo)航數(shù)據(jù)庫大、匹配時間長、對噪聲的魯棒性較差。文獻(xiàn)[7]中對三角形算法、匹配組算法與柵格算法的性能做了詳細(xì)比較，結(jié)果表明柵格算法較傳統(tǒng)的基于子圖同構(gòu)的三角形算法和匹配組算法在魯棒性、存儲容量和識別時間等方面有很大的優(yōu)勢。但是柵格算法中提取的恒星特征模式不能反映內(nèi)在的相似程度，影響柵格算法的星圖識別成功率[8]。

針對上述問題，本文將能夠反映相似程度的度量函數(shù)引入到柵格算法中，通過觀測星特征模式和導(dǎo)航星特征模式之間的度量函數(shù)值來確定模式向量的相似程度，從而降低了星點位置誤差帶對識別成功率降低的影響，提高了改進(jìn)算法的魯棒性和精度。

1 算法描述

1.1 柵格算法

柵格算法的模式生成過程如圖1所示，可以分為以下幾步[7,8]:

1)選擇一顆待識別的觀測星作為主星并確定模式半徑pr。

2)平移選擇的主星及鄰域半徑pr內(nèi)的所有恒星，使主星位于視場中心。

3)確定近鄰星，即在確定的模式半徑pr內(nèi)，鄰域半徑br外尋找距離主星最近的星。

4)以主星為坐標(biāo)原點，主星與近鄰星的連線為坐標(biāo)軸，將星圖進(jìn)行旋轉(zhuǎn)，使得近鄰星位于x軸上。同時將星圖劃分成g×g柵格并生成長度為g2的特征模式向量v。觀測星的特征模式用g×g柵格cell(m,n)來表示，如果某個柵格內(nèi)有伴星，則其值為1，否則為0。每顆恒星的特征模式向量可以表示為v=(a1,a2,…,ak,…,ag)，k=1,2,…,g2，且有

(1)

式中m∈[1,g];n∈[1,g];k=(m-1)·g+n。

圖1 原始柵格算法

假設(shè)拍攝星圖中某觀測星j的特征模式為patj,導(dǎo)航星表中所有導(dǎo)航星特征模式的集合為{patj}，則星圖識別的實質(zhì)即為尋找

(2)

傳統(tǒng)柵格算法提取的模式向量并不能反映內(nèi)在的相似程度。圖2為g=8的柵格，設(shè)其特征模式為pat，則根據(jù)柵格的特征模式構(gòu)造原理，pat的第11，21，36，39，42，54個元素為1，其余的為0。但是由于星點位置誤差的影響，位于柵格邊緣的星可能由A位置移動到B位置。設(shè)此時構(gòu)造的特征模式為pat′，則pat′的第11，21，36，39，43，54個元素為1，其余的為0。此時pat和pat′的特征模式明顯不同，采用這種構(gòu)造方式，相似分布的特征提取出來的特征模式差別很大，無法在特征空間反映出其相似程度，將直接影響識別算法的成功率，當(dāng)星點位置誤差較大時，產(chǎn)生的影響將顯著增加，識別成功率將大幅降低。

圖2 g=8的柵格

1.2 改進(jìn)的柵格算法

假設(shè)拍攝星圖中某觀測星j的特征模式為patj，導(dǎo)航星表中所有導(dǎo)航星特征模式的集合為{pati}。pati和patj為將要比較的兩個特征模式。對pati來說，某一個柵格內(nèi)有伴星pati[m,n]=1，則在patj中離其位置最近的某個柵格中必有一顆星pati[m′,n′]=1。因此,某個柵格中pati[m,n]=1的度量函數(shù)可以這樣計算

(3)

式中a

如果某個柵格內(nèi)沒有伴星pati[m,n]=0，則其度量函數(shù)為0，即cost(pati[m,n]=0)=0。

同理，對patj來說，某一個柵格內(nèi)有伴星patj[m,n]=1，則在pati中離其位置最近的某個柵格中必有一顆星pati[m′,n′]=1。因此,某個柵格中patj[m,n]=1的度量函數(shù)為

(4)

式中a

如果某個柵格內(nèi)沒有伴星patj[m,n]=0，則其度量函數(shù)為0，即cost(patj[m,n]=0)=0。

分別對每一個pati和patj進(jìn)行相應(yīng)度量函數(shù)的計算，則在{pati}尋找觀測星j所對應(yīng)的導(dǎo)航星,即尋找

獲取滿足式(5)的最小pati后，可得導(dǎo)航星庫中與觀測星j所匹配的導(dǎo)航星。

從度量函數(shù)的構(gòu)建過程可以得出：對于兩個特征模式，如果二者相似度越大，則度量函數(shù)的值越??；如果相似度越小，則度量函數(shù)的值就越大。而對于正確匹配的兩個特征模式，經(jīng)過計算得到的度量函數(shù)值最小。因此，可以通過度量函數(shù)值的大小反映不同特征模式之間的相似程度，從而降低了星點位置誤差對識別成功率的影響，表明了改進(jìn)后的識別算法具有更強魯棒性。

2 星識別模式表的存儲和搜索方式

式(2)表示的匹配過程存在的顯著問題是冗余匹配過多、效率太低。對選取后的導(dǎo)航星進(jìn)行匹配，需要經(jīng)過N×g2次運算(N為所選用的導(dǎo)航星數(shù)目)，而且g2遠(yuǎn)遠(yuǎn)大于視場內(nèi)平均的恒星數(shù)量，顯然該識別方法耗時非常大。針對這個問題，本文設(shè)計了一個查找表LT來存儲導(dǎo)航星的特征模式，加快匹配速度[9]。

2.1 星識別模式

查找表包括g2項，標(biāo)記為LTi,i=1,2,…，g2，分別對應(yīng)于每個柵格。對于每個導(dǎo)航星，如果在柵格i中有伴星，則在LTi中增加一項記錄，該記錄存儲的是這個主星的標(biāo)號。按照此種方法，完成整個查找表的構(gòu)建。在構(gòu)建查找表的過程中，需要將同一項中重復(fù)出現(xiàn)的導(dǎo)航星編號去除。利用查找表來構(gòu)建導(dǎo)航數(shù)據(jù)庫結(jié)構(gòu)如圖3所示。在構(gòu)建特征模式時，對于每一顆恒星，分別記錄其伴星落在柵格內(nèi)的位置標(biāo)號，采用柵格內(nèi)的位置標(biāo)號來表示某顆導(dǎo)航星的特征模式。

圖3 導(dǎo)航數(shù)據(jù)庫結(jié)構(gòu)圖

2.2 搜索方式

利用查表進(jìn)行匹配時，其匹配過程示意圖如圖4所示。以觀測星S為例，假設(shè)星S的特征模式為(12,26，31，54，102，133)，則分別檢索查找表LTi中的12,26,31,54,102,133項記錄的導(dǎo)航星標(biāo)號，選出導(dǎo)航星標(biāo)號出現(xiàn)次數(shù)最多的導(dǎo)航星。經(jīng)過檢測，第454顆導(dǎo)航星匹配次數(shù)最多，將其記錄為初始匹配星。

圖4 查找過程

導(dǎo)航數(shù)據(jù)庫建立之后，對觀測星進(jìn)行識別。于某一視場內(nèi)選擇亮度最亮的α顆星進(jìn)行識別，文獻(xiàn)[11]指出當(dāng)星敏感器視場為12°,星等閾值不小于6MV時，其平均捕捉恒星數(shù)為13.8顆。結(jié)合仿真選用的星敏感器,本文選取α=10，對于每一顆觀測星，按照上述查找過程將導(dǎo)航星庫中出現(xiàn)次數(shù)大于閾值ξ的導(dǎo)航星挑選出來作為候選匹配星，候選匹配星可能不唯一。然后把觀測星的特征模式分別與候選匹配星的特征模式建立度量函數(shù)，度量函數(shù)值最小的匹配組為正確匹配的2個特征向量，即該導(dǎo)航星為觀測星正確匹配的星。按照同樣的方法對所有的α顆星進(jìn)行識別，如果有2顆及以上的星點識別成功，即認(rèn)為星圖識別成功;否則,即為失敗[6]。

3 仿真與分析

仿真中所用的基本星表是第谷第二星表(Tycho—2)，從中選取星等亮度大于7.0的星中篩選出5 404顆組成導(dǎo)航星表。

3.1 仿真條件設(shè)置

從1.1節(jié)中柵格算法原理可知，鄰域半徑br和柵格數(shù)目g共同決定柵格的形成，進(jìn)而決定其性能。當(dāng)g設(shè)置較大時，即量化等級較細(xì)，容易受星點位置噪聲干擾使產(chǎn)生錯誤匹配的可能性增加，而且計算量也很大；當(dāng)g設(shè)置較小時，多個星點目標(biāo)出現(xiàn)在同一個柵格內(nèi)的概率將增加，使得特征模式維數(shù)太低，達(dá)不到正常識別的要求。同理，br如果設(shè)置過大，雖然會使得識別算法對噪聲的魯棒性變強，但增加了近鄰星出現(xiàn)在視場之外的概率，使得正確選取近鄰星的概率降低，將直接影響到星圖識別成功率。因此，不合適大小的g和br都會使識別成功率下降，需要對恒星在視場中的分布情況進(jìn)行統(tǒng)計，然而根據(jù)統(tǒng)計結(jié)果來設(shè)置合理的柵格數(shù)目g和緩沖半徑br。

本文中選取的星敏感器視場為12°×12°，星等敏感極限為7.0星等，分辨率為512×512。對選取的基本星表進(jìn)行角距分布的統(tǒng)計。圖5為5 000次隨機(jī)視軸指向星點之間角距分布的統(tǒng)計結(jié)果分布圖。

圖5 星點之間角距分布統(tǒng)計

根據(jù)統(tǒng)計結(jié)果可以看出:星間角距中有99.9 %的角距大于0.3°，因此,選擇柵格大小為0.3°，可以保證絕大多數(shù)星分布在不同的柵格中，柵格數(shù)目g=12°/0.3°=40。同理，選擇鄰域半徑br=512/40=12.8像素。模式半徑pr可以設(shè)置為星敏感器的視場大小，即pr=12°。度量函數(shù)參數(shù)a=0，b=2，c=4，k=2，匹配閾值ξ=5。

3.2 仿真結(jié)果

圖6為星敏感器星等噪聲σ=0.2時，本文提出的算法和傳統(tǒng)算法的星圖識別成功率隨著位置噪聲變化的曲線。

圖6 識別成功率隨星等噪聲變化的曲線

從圖6可以看出，當(dāng)星點位置噪聲σ<1.5時,由于噪聲誤差較小,星點落到錯誤柵格內(nèi)的概率較低，改進(jìn)柵格算法的優(yōu)勢并沒有顯現(xiàn)出來，兩種識別算法的識別成功率相差不大；當(dāng)星點位置噪聲σ>1.5時，星點落到錯誤柵格內(nèi)的概率增加，原有柵格算法反映不出特征模式間的相似程度，影響了識別成功率。而改進(jìn)的柵格算法能很好地反映出特征向量的相似程度，對位置誤差有很強的魯棒性，當(dāng)星點位置噪聲σ=2.5時,也能達(dá)到94 %的正確率。從仿真結(jié)果可以看出，改進(jìn)的柵格算法相比于原有的柵格算法對位置噪聲具有更好的魯棒性。

圖7為位置噪聲σ=0.5像素、星等噪聲為σ=0.2星等時，兩種算法的星圖識別成功率隨著“假星”數(shù)變化的曲線。

圖7 識別成功率隨“假星”個數(shù)的變化曲線

從圖7 可以看出，本文改進(jìn)后柵格算法對“假星”同樣具有很好的魯棒性，而且在同等條件下，改進(jìn)后的柵格算法比原有的算法具有更高的識別成功率。

4 結(jié) 論

將度量函數(shù)的概念引入到傳統(tǒng)的柵格算法中，改進(jìn)算法可以通過特征模式之間的度量函數(shù)值的大小來判斷其相似度，消除了星點位置噪聲對星圖識別成功率的影響，提高了改進(jìn)算法的魯棒性。仿真結(jié)果表明:當(dāng)星點位置噪聲達(dá)到一定程度(σ>1.5)或存在“假星”的條件下，改進(jìn)的柵格算法的星圖識別成功率均要高于傳統(tǒng)的算法，說明了在魯棒性和精度方面，改進(jìn)算法比傳統(tǒng)算法有更好的表現(xiàn)。

但由于本文算法引入了度量函數(shù)，增加了比較計算環(huán)節(jié)，增加了計算量，使得改進(jìn)后的識別算法時間變長。下一步需對改進(jìn)算法的做進(jìn)一步優(yōu)化。

[1] 文 濤,王宏力,陸敬輝,等.基于星三角形外接圓的星圖識別算法[J]. 傳感器與微系統(tǒng),2012,31(2):74-76.

[2] 胡 坤,陳嘉鴻,謝元平.一種基于旋轉(zhuǎn)不變特征的星圖識別算法[J].光電工程,2015,42(6):20-26.

[3] 孫曉雄,王宏力,陸敬輝.一種基于星三角形的星圖識別算法[J].傳感器與微系統(tǒng),2009,28(12):8-10.

[4] Kosik J.Star pattern identification aboard an inertially stabilized spacecraft[J].Journal of Guidance,Control and Dynamics,1991,14(1):230-235.

[5] Udomkesmalee S,Alexander J,Tolivar F.Stochastic star identification[J].Journal of Guidance,Control and Dynamics,1994,17(6):1283-1286.

[6] Padgett C,Kreutz-Delgado K.A grid algorithm for autonomous star identification[J].IEEE Trans on Aerospace and Electronic System,1997,33(1):202-213.

[7] Padgett C,Kreutz-Delgado K,Udomkesmalee S.Evaluation of star identification techniques[J].Journal of Guidance,Control & Dynamics,1997,20(2):259-267.

[8] 張廣軍.星圖識別[M].北京:國防工業(yè)出版社,2011:99-100.

[9] Zhang G,Wei X,Jiang J.Full-sky autonomous star identification based on radial and cyclic features of star pattern[J].Image and Vision Computing,2008,26(7):891-897.

[10] 孫 龍.基于星敏感器的捷聯(lián)慣性/天文組合導(dǎo)航研究[D].哈爾濱：哈爾濱工程大學(xué),2015:41-42.

A modified grid algorithm for star map identification*

QIAN Hua-ming1, LANG Xi-kai1, LI Meng2

(1.College of Automation, Harbin Engineering University,Harbin 150001,China;2.China Aviation Optical-Electrical Technology Co Ltd,Luoyang 471003,China)

Considering that the characteristic pattern extracted by traditional grid algorithm can’t reflect its internal similarity degree,which can affect the accuracy of star map recognition,a modified grid algorithm is proposed.The algorithm uses the metric functions derived from the characteristic patterns to reflect the similarity degree between different characteristic patterns,which solves the problem exists in feature mode extraction because influence of the position measurement error.Simulation environment according to the real situation is set up.The results indicate the star map identification success rate of the proposed method is obviously higher than the traditional algorithm when the star point position error is greater than 1.5 pixels and the improved algorithm of star map recognition success rate is superior to the existing algorithms in the presence of“artificial star”,which shows the validation of the proposed algorithm.

grid algorithm; characteristic pattern; similarity degree; measurement function

2016—06—23

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

10.13873/J.1000—9787(2017)06—0150—04

V 448

A

1000—9787(2017)06—0150—04

錢華明(1965-)，男，博士，教授，博士生導(dǎo)師，主要從事組合導(dǎo)航、信息處理、傳感器技術(shù)與智能系統(tǒng)技術(shù)工作。

郎希開，通訊作者，E-mail:178708172@qq.com。