基于三角形匹配的星圖識(shí)別算法及優(yōu)化

郭 磊 ，李保權(quán) ，曹 陽(yáng) ，桑 鵬

（1.中國(guó)科學(xué)院國(guó)家空間中心北京100190；2.中國(guó)科學(xué)院大學(xué)北京100190）

星敏感器是以恒星為參照物進(jìn)行姿態(tài)測(cè)量的敏感設(shè)備，它通過(guò)觀(guān)測(cè)天球上的恒星位置來(lái)確定飛行器相對(duì)于天球坐標(biāo)系的三軸姿態(tài)，為飛行器姿態(tài)控制系統(tǒng)提供準(zhǔn)確的依據(jù)[1]。由于恒星的張角很小（最大恒星的張角為0.05角秒，一般在毫角秒量級(jí)），并且恒星的影像是在真空中提取的恒星赤經(jīng)赤緯又是精確已知的，所以星敏感器稱(chēng)得上是航天器中絕對(duì)姿態(tài)測(cè)量精度最高的設(shè)備[2]。對(duì)于姿態(tài)精度要求較高的飛行器，星敏感器有著不可替代的作用。星敏感器的工作過(guò)程主要包括星表的預(yù)處理，星象檢測(cè)，星圖識(shí)別，以及姿態(tài)獲取。而整個(gè)算法的核心即是星圖識(shí)別，星圖識(shí)別的效率和正確率直接決定了整個(gè)星敏感器的工作性能。目前，已經(jīng)出現(xiàn)的星圖識(shí)別算法有三角形算法，匹配組算法，柵格算法，多邊形角距算法，奇異值分解算法，神經(jīng)網(wǎng)絡(luò)算法和遺傳算法等[3]。真正應(yīng)用比較成熟且經(jīng)過(guò)工程驗(yàn)證識(shí)別效果的是三角形算法。三角形算法是最早的星圖識(shí)別算法的變體，屬于子圖匹配方法家族的成員，它試圖匹配一個(gè)由觀(guān)測(cè)星點(diǎn)作為3個(gè)頂點(diǎn)構(gòu)建的三角形[4]。由幾何知識(shí)我們知道全等三角形可以用兩種方法驗(yàn)證：邊角邊或者邊邊邊。使用邊角邊時(shí)，可以計(jì)算三角形兩邊的長(zhǎng)度和它們之間的夾角，并與星表中的條目相比較，由正弦定理可知，角度與對(duì)應(yīng)邊長(zhǎng)成正比，本質(zhì)上還是邊邊邊；邊邊邊則是用到三角邊的長(zhǎng)度，采用這種方法，星表需要包含在整個(gè)夜空中能觀(guān)察到的所有恒星組成的三角形的信息，星表中存儲(chǔ)的三角形的數(shù)目與星敏感器傳感器的敏感度和相機(jī)的FOV成比例，對(duì)于性能較好的傳感器，星敏感器的精度更高，星表中存貯的信息會(huì)非常多，這樣需要很長(zhǎng)的搜索時(shí)間[5]。因此優(yōu)化星表很有必要，一個(gè)例子就是在圖像中選擇最亮的3個(gè)星點(diǎn)組成的三角形進(jìn)行匹配，而不是隨機(jī)選擇3個(gè)星點(diǎn)。然而為了增加精度，更為理想的做法是將星圖中的所有三角形都進(jìn)行匹配，而不僅僅是一個(gè)三角形[6]。亮度信息可以存儲(chǔ)在星表中加速星表搜索。由于測(cè)量誤差的存在，當(dāng)搜索匹配的三角形時(shí)需要一定的容錯(cuò)度，但容錯(cuò)度會(huì)導(dǎo)致一些三角形匹配錯(cuò)誤，為了防止這種情況的發(fā)生，需要驗(yàn)證匹配的方法，或者對(duì)于每個(gè)匹配的三角形嘗試匹配鄰近的第4個(gè)亮點(diǎn)[7]。

1 導(dǎo)航星庫(kù)制作

導(dǎo)航星庫(kù)包括兩部分，一個(gè)星列表和星對(duì)距離列表。這兩個(gè)列表通過(guò)程序生成并存儲(chǔ)在星敏感器的緩存中。下面介紹兩個(gè)星表的內(nèi)容：星列表包含所有亮度高于某個(gè)規(guī)定星等的恒星，在我們?cè)O(shè)計(jì)的星敏感器中該星等閾值定為5.75，但同時(shí)存儲(chǔ)了星等高于7等的所有恒星，并在程序中預(yù)留好接口，通過(guò)發(fā)送指令可以隨時(shí)修改閾值。星列表?xiàng)l目包括每顆恒星的ID，赤經(jīng)赤緯，以及星等。星表原始數(shù)據(jù)來(lái)源第谷星表經(jīng)過(guò)程序處理后，剔除了所有亮度低于5.75星等的恒星。接下來(lái)又將每顆恒星的赤經(jīng)赤緯都變換成了迪卡爾ECI單位適量下的坐標(biāo)值[8]。除此之外，包括第谷星表在內(nèi)的大多星表一般只給了恒星在J2000.0歷元的平位置（平赤經(jīng)和平赤緯），而我們觀(guān)測(cè)的恒星位置則是恒星的地心真赤道視位置坐標(biāo)，由于恒星的自行，地球的歲差章動(dòng)等等影響，這兩種坐標(biāo)有些許的差異[9]。為了使得到的結(jié)果更加準(zhǔn)確，我們對(duì)第谷表中的恒星在J2000.0歷元的平位置進(jìn)行了修正，加上了自行改正，周年視差改正，光行差改正，歲差和章改正之后，得到了恒星地心真赤道坐標(biāo)[10]。星列表部分如圖1所示。

圖1 星列表存儲(chǔ)結(jié)構(gòu)

星表的第二部分為星對(duì)的間距表，為獲得此表，需計(jì)算3 999顆恒星中每?jī)蓚€(gè)恒星之間的距離，計(jì)算公式如下：

其中x，y，z為恒星Si和恒星Sj在ECI單位向量上的分量。

1）間距表中的每個(gè)條目由兩顆恒星的序號(hào)和他們之間的角距（弧度）組成，并按角距的升序排列。為保持恒該星表的簡(jiǎn)潔高效，需注意以下幾點(diǎn)：

2）每個(gè)恒星對(duì)只算做一個(gè)條目，與恒星的順序無(wú)關(guān)。

3）僅當(dāng)星間距小于星敏感器的視場(chǎng)角時(shí)將恒星對(duì)列入表中。

4）僅在星間距足夠大，兩顆恒星能被獨(dú)立識(shí)別時(shí)，將恒星對(duì)列入表中[11]。

5）當(dāng)星間距過(guò)小時(shí)可以視為一顆恒星也可以視為兩顆恒星，且當(dāng)相距7個(gè)像素的恒星對(duì)則應(yīng)被視為各自獨(dú)立[12]。

6）充分利用星表中恒星ID不太大的特點(diǎn)，用short類(lèi)型取代int，即一個(gè)整數(shù)可以表示兩個(gè)恒星ID（高16位a1，低16位a2），一方面減少星表體積，另一方面提高了cache命中率，從硬件層面上提高算法效率。

7）星間距表的最終版本包括119570個(gè)條目，第一列中整數(shù)表示一個(gè)星對(duì)（a1，a2），第二列表示相互之間角距大小。如圖2所示。

圖2 星間距表存儲(chǔ)結(jié)構(gòu)

2 算法描述

通常三角形識(shí)別過(guò)程是，從待測(cè)星圖中取出三個(gè)恒星點(diǎn)，組成三角形，例如圖3中（ABC），每條邊（AB，AC，BC）對(duì)應(yīng)在星間距列表中找到對(duì)應(yīng)的間距范圍（a1，a2）（b1，b2）（c1，c2）。這其中，由于星間距對(duì)排列是按照是恒星間的角距大小升序排列的，所以直接用二分法就可以在O（log（n））的時(shí)間復(fù)雜度下找到對(duì)應(yīng)的角距大小的上下限[13]。本文中為了進(jìn)一步提高整體算法運(yùn)行效率，且由于此查詢(xún)算法調(diào)用次數(shù)較多，所以決定用哈希表實(shí)現(xiàn)導(dǎo)航星表中恒星對(duì)間距與下標(biāo)之間的對(duì)應(yīng)，這樣即可以在O（1）的時(shí)間復(fù)雜度下找到對(duì)應(yīng)上下限。

由三角形幾何性質(zhì)可知，三角形匹配本質(zhì)上是尋找（a1，a2）（b1，b2）（c1，c2）邊之間的首尾相相接，也即是三個(gè)星對(duì)之間ID值首尾相同即可，傳統(tǒng)匹配算法即是利用三個(gè)集合之間星對(duì)坐標(biāo)進(jìn)行兩兩比對(duì)，假定AB對(duì)應(yīng)的恒星對(duì)（a1，a2）數(shù)量為n1，AC對(duì)應(yīng)的恒星（b1，b2）數(shù)量為n2，BC對(duì)應(yīng)的恒星對(duì)（c1，c2）數(shù)量為n3。比對(duì)過(guò)程即是，各個(gè)坐標(biāo)對(duì)進(jìn)行比對(duì)；易知只需要進(jìn)行比23的次數(shù)，時(shí)間復(fù)雜度為O（n1）*O（n2）*O（n3），如圖1所示[14]；再加上后來(lái)的四面體頂點(diǎn)檢驗(yàn)以及其余待測(cè)星點(diǎn)驗(yàn)證，三角形匹配調(diào)用次數(shù)有可能會(huì)達(dá)到數(shù)十次，顯然此時(shí)效率遠(yuǎn)不能達(dá)到項(xiàng)目要求。

圖3 傳統(tǒng)三角形匹配過(guò)程

文中即對(duì)此進(jìn)行了針對(duì)性?xún)?yōu)化：降低時(shí)間復(fù)雜度；由數(shù)據(jù)結(jié)構(gòu)知識(shí)可知，遍歷是相當(dāng)?shù)托У?；改變的方式包括排序后二分查找，或者哈希表定位[15]。本文兩種方法都用到了，具體做法是利用哈希表存儲(chǔ)（a1，a2）星間距對(duì)，由于可能有（a1，a3）或者（a2，a3）的出現(xiàn)，故選擇用拉鏈法處理沖突，處理如圖4所示。由于hashtable原來(lái)為NULL，所以當(dāng)hashtable[b1]!=NULL時(shí)，即b1與a1相同。接下來(lái)只需要比較b2a2是否與c1c2或c2c1相等即可。為提高效率，避免盲目遍歷，先進(jìn)行快速排序然后進(jìn)行二分查找。這兩個(gè)函數(shù)都可以直接調(diào)用庫(kù)函數(shù)，不用手動(dòng)實(shí)現(xiàn)。計(jì)數(shù)排序是目前最快排序，但由于數(shù)值較大，排序所需空間復(fù)雜度會(huì)很可觀(guān)，故放棄使用[16]；易知新算法時(shí)間復(fù)雜度為O（nlogn）遠(yuǎn)小于原來(lái)的O（n3）。

圖4 存儲(chǔ)星對(duì)的hashtable

由于三角形特征維數(shù)少，冗余匹配和和錯(cuò)誤匹配很難避免，故引入第四顆星，即圖5中D星，在已識(shí)別的三角形ABC中，通過(guò)對(duì)AD和BD的檢索來(lái)驗(yàn)證D星點(diǎn)，成功識(shí)別三角形ABD[17]。接著在對(duì)AD和CD進(jìn)行同樣檢索，成功識(shí)別三角形ACD。由于D是同一頂點(diǎn)，此時(shí)實(shí)際上是一個(gè)四面體。由此便可以大大降低匹配冗余率和錯(cuò)誤率，接著為了進(jìn)一步確定導(dǎo)航三角形，進(jìn)入驗(yàn)證識(shí)別環(huán)節(jié)，對(duì)待測(cè)星表中余下的潛在星點(diǎn)，逐一進(jìn)行四面體驗(yàn)證檢測(cè)，如圖5所示。最后為避免極端鏡像情況出現(xiàn)，又對(duì)三角形的三邊順序利用向量乘積的大小進(jìn)行驗(yàn)證。待測(cè)星圖中與導(dǎo)航星圖中的大小值完全一樣即可避免三角鏡像情況的出現(xiàn)，進(jìn)一步降低了匹配錯(cuò)誤率[18]。

星圖識(shí)別總的流程如圖6所示。

3 結(jié)果分析

將文獻(xiàn)中的傳統(tǒng)三角形算法和本文中提出的改進(jìn)算法分別編程實(shí)現(xiàn)，并對(duì)500幅實(shí)拍星圖進(jìn)行匹配驗(yàn)證，在匹配門(mén)限為0.02°時(shí)原始算法的成功匹配率即給出正確姿態(tài)角的比例是76.8%（384/500）；而改進(jìn)后的正確率達(dá)到99.2%（496/500）；在匹配門(mén)限為0.04°時(shí)原始算法的成功匹配率即給出正確姿態(tài)角的比50.2%（251/500）；而改進(jìn)后的正確率達(dá)到96.4%（488/500）；并且在ubuntu系統(tǒng)下CPU 1.8 GHz，內(nèi)存2G平均時(shí)間由原來(lái)的4 s左右降到目前的3 ms左右；其中隨機(jī)一幅星圖的匹配結(jié)果如圖7所示。

從圖7可以看到，在加了像素閾值的限制后，匹配更加精確甚至可以達(dá)到完全匹配；在提供姿態(tài)角都是正確結(jié)果的前提下，算法效率有了質(zhì)的提高。

圖5 四面體檢測(cè)示意圖

圖6 星圖識(shí)別算法總體流圖

圖7 傳統(tǒng)算法與改進(jìn)后效果對(duì)比圖

4 結(jié)論

綜合500幅星圖匹配結(jié)果可以看出本文所提出的改進(jìn)方案不僅提高了星圖識(shí)別的正確率而且大幅度提升了算法效率。通過(guò)深入分析算法執(zhí)行過(guò)程，同時(shí)在數(shù)據(jù)存儲(chǔ)以及算法時(shí)間復(fù)雜度方面著手，從邏輯層面的算法剪枝到實(shí)現(xiàn)層面的數(shù)據(jù)結(jié)構(gòu)替代都進(jìn)行了針對(duì)性?xún)?yōu)化，最終提高了算法的正確率和實(shí)時(shí)性，也提高了其全天球適應(yīng)性。

參考文獻(xiàn)：

[1]梁斌，朱海龍，張濤，等.星敏感器技術(shù)研究現(xiàn)狀及發(fā)展趨勢(shì)[J].中國(guó)光學(xué)，2016（1）：16-29.

[2]Padgett C，Kreutzdelgado K，Udomkesmalee S.Evaluation of Star Identification Techniques[J].Journal of Guidance Control&Dynamics，2012，20（2）：259-267.

[3]蹤華，汪渤，周志強(qiáng)，等.一種基于模式匹配的自主星圖識(shí)別算法[J].北京理工大學(xué)學(xué)報(bào)，2015（10）：1032-1037.

[4]Balodis J，Zarin? A，Haritonova D，et al.Parame?ters for automated star identification[J].Geodesy&Cartography，2014，40（4）：163-170.

[5]He A X，Wang C C，Zhang H N.A Star Map Recognition Method Based on Multi-Layers SOFM Network[J].Applied Mechanics&Materials，2013（411-414）：1011-1014.

[6]李超兵，袁艷艷，王丹曄.基于特征圖形匹配法的高效星圖識(shí)別方法[J].中國(guó)空間科學(xué)技術(shù)，2016，36（4）：9-16.

[7]韓艷麗，劉峰.基于三角形匹配的空間小目標(biāo)檢測(cè)算法[J].紅外與激光工程，2014，43（9）：3134-3140.

[8]時(shí)圣革，雷肖劍，于長(zhǎng)海.星圖識(shí)別三角形算法綜述[J].光電技術(shù)應(yīng)用，2014，29（5）：1-6.

[9]賀鵬程.一種改進(jìn)的三角形識(shí)別算法[J].艦船電子工程，2012，32（4）：42-44.

[10]趙臻，高穎慧，王平.基于星圖識(shí)別算法的空間小目標(biāo)識(shí)別[J].重慶理工大學(xué)學(xué)報(bào)自然科學(xué)版，2011，25（4）：97-101.

[11]胡敏，賀曉佳，王曉華.快速區(qū)域質(zhì)心圖像匹配算法[J].電子測(cè)量與儀器學(xué)報(bào)，2011，25（5）：455-462.

[12]陸敬輝，王宏力，孫淵，等.三角形內(nèi)切圓的星圖識(shí)別算法[J].紅外與激光工程，2011，40（4）：752-756.

[13]魏新國(guó)，徐佳，張廣軍.星敏感器質(zhì)心定位的S曲線(xiàn)誤差補(bǔ)償[J].光學(xué)精密工程，2013（4）：849-857.

[14]賈輝，楊建坤，李修建，等.星敏感器高精度星點(diǎn)提取系統(tǒng)誤差分析及補(bǔ)償方法研究[J].中國(guó)科學(xué)：技術(shù)科學(xué)，2011（1）：69-76.

[15]曹南.用于大地天文測(cè)量的恒星視位置算法研究[D].西安：西安科技大學(xué)，2014.

[16]王萌萌.適用于皮納衛(wèi)星的微型星敏感器設(shè)計(jì)與測(cè)試[D].杭州：浙江大學(xué)，2014.

[17]鄭循江.輕小型高動(dòng)態(tài)星敏感器技術(shù)研究[D].上海：上海交通大學(xué)，2012.

[18]蹤華，高曉穎，姬曉琴，等.一種自主星圖識(shí)別方法 [P].CN103335648A，2013.