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

錢(qián)華明， 郎希開(kāi)， 李 猛

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

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

錢(qián)華明1， 郎希開(kāi)1， 李 猛2

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

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

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

0 引 言

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

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

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

1 算法描述

1.1 柵格算法

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

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

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

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

4)以主星為坐標(biāo)原點(diǎn)，主星與近鄰星的連線為坐標(biāo)軸，將星圖進(jìn)行旋轉(zhuǎn)，使得近鄰星位于x軸上。同時(shí)將星圖劃分成g×g柵格并生成長(zhǎng)度為g2的特征模式向量v。觀測(cè)星的特征模式用g×g柵格cell(m,n)來(lái)表示，如果某個(gè)柵格內(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è)拍攝星圖中某觀測(cè)星j的特征模式為patj,導(dǎo)航星表中所有導(dǎo)航星特征模式的集合為{patj}，則星圖識(shí)別的實(shí)質(zhì)即為尋找

(2)

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

圖2 g=8的柵格

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

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

(3)

式中a

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

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

(4)

式中a

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

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

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

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

2 星識(shí)別模式表的存儲(chǔ)和搜索方式

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

2.1 星識(shí)別模式

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

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

2.2 搜索方式

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

圖4 查找過(guò)程

導(dǎo)航數(shù)據(jù)庫(kù)建立之后，對(duì)觀測(cè)星進(jìn)行識(shí)別。于某一視場(chǎng)內(nèi)選擇亮度最亮的α顆星進(jìn)行識(shí)別，文獻(xiàn)[11]指出當(dāng)星敏感器視場(chǎng)為12°,星等閾值不小于6MV時(shí)，其平均捕捉恒星數(shù)為13.8顆。結(jié)合仿真選用的星敏感器,本文選取α=10，對(duì)于每一顆觀測(cè)星，按照上述查找過(guò)程將導(dǎo)航星庫(kù)中出現(xiàn)次數(shù)大于閾值ξ的導(dǎo)航星挑選出來(lái)作為候選匹配星，候選匹配星可能不唯一。然后把觀測(cè)星的特征模式分別與候選匹配星的特征模式建立度量函數(shù)，度量函數(shù)值最小的匹配組為正確匹配的2個(gè)特征向量，即該導(dǎo)航星為觀測(cè)星正確匹配的星。按照同樣的方法對(duì)所有的α顆星進(jìn)行識(shí)別，如果有2顆及以上的星點(diǎn)識(shí)別成功，即認(rèn)為星圖識(shí)別成功;否則,即為失敗[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è)置較大時(shí)，即量化等級(jí)較細(xì)，容易受星點(diǎn)位置噪聲干擾使產(chǎn)生錯(cuò)誤匹配的可能性增加，而且計(jì)算量也很大；當(dāng)g設(shè)置較小時(shí)，多個(gè)星點(diǎn)目標(biāo)出現(xiàn)在同一個(gè)柵格內(nèi)的概率將增加，使得特征模式維數(shù)太低，達(dá)不到正常識(shí)別的要求。同理，br如果設(shè)置過(guò)大，雖然會(huì)使得識(shí)別算法對(duì)噪聲的魯棒性變強(qiáng)，但增加了近鄰星出現(xiàn)在視場(chǎng)之外的概率，使得正確選取近鄰星的概率降低，將直接影響到星圖識(shí)別成功率。因此，不合適大小的g和br都會(huì)使識(shí)別成功率下降，需要對(duì)恒星在視場(chǎng)中的分布情況進(jìn)行統(tǒng)計(jì)，然而根據(jù)統(tǒng)計(jì)結(jié)果來(lái)設(shè)置合理的柵格數(shù)目g和緩沖半徑br。

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

圖5 星點(diǎn)之間角距分布統(tǒng)計(jì)

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

3.2 仿真結(jié)果

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

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

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

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

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

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

4 結(jié) 論

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

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

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

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

[3] 孫曉雄,王宏力,陸敬輝.一種基于星三角形的星圖識(shí)別算法[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] 張廣軍.星圖識(shí)別[M].北京:國(guó)防工業(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

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

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

V 448

A

1000—9787(2017)06—0150—04

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

郎希開(kāi)，通訊作者，E-mail:178708172@qq.com。