一種自主星圖識別算法

賈蒙楊

(中國空間技術研究院通信衛星事業部，北京 100094)

一種自主星圖識別算法

賈蒙楊

(中國空間技術研究院通信衛星事業部，北京 100094)

為了改善星敏感器系統的星圖識別實時性和可靠性，文章在研究現有的星圖識別相關技術基礎后，提出了基于特征向量投影法的算法核心，并在這一核心的基礎上完成了星圖識別算法和導航星圖數據庫的改進設計。最后編寫仿真測試軟件對此算法程序進行了性能測試，測試結果表明，文章提出的自主星圖識別算法在星圖識別實時性和可靠性方面都較以往算法有了提高。

星敏感器；星圖識別；特征向量投影法

1 引言

星敏感器系統是實現航天器自主姿態控制的關鍵系統，它依靠自主星圖識別技術實現對航天器姿態的實時自主監測。隨著航天技術的不斷發展，航天器的任務也隨之越來越多樣化，許多新的航天任務如空間交會對接、空間激光通信[1]等都對航天器進行姿態控制實時性提出了更高的要求。因此，在現有星敏感器系統的技術基礎上，需要發展可靠性和運行效率更高的自主星圖識別技術。

從地球或附近某一點向宇宙空間中任意方向看去，不論觀察點如何移動或變換姿態，兩顆任意恒星間的角距總是不變的，這就使得天球上的一對恒星具有了一定的特征性，自主星圖識別技術就是利用這種特征性，設計星圖識別算法程序和導航星數據庫，事先對恒星圖像的自主模式識別。經過近幾十年的發展，星圖識別算法和導航星圖數據庫都有了多種設計思路，用以滿足不同的任務需求。

導航星庫是利用特征性并根據星圖識別算法的需求，從全天恒星中經過刪選和優化設計而得到的一種星圖數據庫。在這個數據庫中，恒星數量必須盡可能少，以保證導航星庫不會過大，可以適應硬件容量并能支持算法快速高效運行。但恒星數量也不能過少，必須保證數據庫對天球的均勻覆蓋，并且還需滿足相機任意視場中的恒星數量足夠多這一要求。

目前對導航星圖數據庫的設計方法，國內外都有研究。主要的研究方向是優化數據結構，縮減數據庫容量等，如自組織導航星選擇方法[2]、二維精簡索引法[3]、字符串制定法[4]等。下面簡要介紹2種通用性較高的基礎性設計。

(1)星等加權方法[5]是基于恒星越亮被星敏感器捕獲到的概率越大這一前提提出的。根據恒星的星等給每顆恒星賦予不同的權值。對低星等的恒星賦予較高的權值，使星等低的恒星被選作導航星的概率較大。在挑選導航星時，先從標準星表中選出有可能成為導航星的恒星構成候選導航星表，然后按星等大小由低到高依次將導航星按其原有的位置信息追加到導航星表中。但在實際使用中，由于空間相機視場范圍有限，而整個星庫的加權值又是固定的，很可能在一個視場圖像中不能獲取足夠數量的導航星，導致匹配識別失敗，而在下一視場中恒星數量過多，又會導致運算量過大失去實時性，簡而言之，用該方法設計的數據庫無法兼顧覆蓋率和實時性，用途受限。

(2)回歸選取方法[5]將傳統星等閾值過濾算法中的靜態閾值用動態星等閾值代替。結果表明，用該方法所選取的導航星表導航星數量少、分布均勻性好，同時還能適應多種任務的導航星選取要求，具有較強的通用性。但這種方法本身比較復雜，所需的參數較多，且對參數選擇的敏感性較大，不容易得到最優結果，使導航星庫設計難度較大。

以上2種思路都是基于對恒星的數量進行篩選達到優化數據庫容量的目的，但是對恒星數量做出過多刪減，會影響恒星數據的覆蓋性。因此如何最大化地兼顧導航星圖數據庫的容量和覆蓋性，是本文研究工作的目標之一。

星圖識別算法的工作原理是，通過相機視場中的數顆恒星所具有的模式唯一的特征來匹配星圖數據庫中的恒星特征，繼而解算出相機當前指向和姿態。目前比較通用的星圖識別算法是三角形匹配算法[6]及其改進算法[7-8]。

三角形匹配算法的基本原理是，利用恒星對角距的特征性，在導航星庫中匹配同一視場下3顆恒星組成的三角形的角距。星三角形的角距特性應該是模式唯一的[6]，導航星庫中有唯一的對應星三角形，根據這個對應關系就可判定相機的觀測姿態和指向。三角形匹配算法的缺點是運算量較大且特征維數只有一維，在測量誤差較大時，冗余匹配導致星圖識別成功率迅速降低[9-11]。

針對上述缺陷，參考文獻中提出了一種增加特征維度的改進算法[11]，該算法將恒星亮度作為第二個特征加入了匹配算法。在算法運行過程中先匹配亮度再匹配角距，此法對運算量沒有明顯的增加。但這種方法局限性很大，因為根據現有相機的成像能力，無法對恒星進行準確的亮度計量，誤差一般會達到0.5星亮度左右，造成新的冗余匹配，降低了匹配結果的可靠性。此外，三角形算法的運算量較大，影響了星圖識別的實時性。

另一種改進思路是提高三角形匹配的效率。在三角形匹配的過程中原本是對星對角距的比對，一個星三角形至少需要比對3個數值才能完成匹配。作為改進，T算法[9]構造了一個特征量T=b+k×ln(a+ca)，其中a，b，c為三角形的三邊長，k為常系數。T值具有旋轉、平移不變性。這樣，匹配一個三角形只需要比對一個數值T，大大提高了匹配速度。未來如能進一步建立索引進行快速T值搜索，這種算法的效率就會更高。此算法要求星圖數據庫中也有對應的星三角形T值，因此這種算法需要與星圖數據庫并行設計。此外，T算法雖然精簡了運算量，但在實際應用中存在測量誤差的情況下，其可靠性并不能保證，需要做進一步優化。

以上兩種思路，分別從提高識別可靠性和識別速度的角度出發，對三角形算法做了一定的改進。然而在未來多樣化的航天任務中，可能需要一種兼顧速度和可靠性的新算法，這也是本文研究工作的目標之一。

2 星圖識別程序的改進思路

以工作在地球同步軌道的星敏感器為應用平臺，本章嘗試設計出一套適用的星圖識別程序。以現有的三角形星圖匹配算法及其配套導航星圖數據庫為基礎，使用一套核心優化算法對這兩部分進行聯合優化設計，達到同時提高星圖匹配可靠性及匹配速度的目的。

在仿真驗算和三個方法性能比較中，取星敏感器的識別范圍為赤經0°～360°，赤緯-54°～54°，視場范圍定為10°×10°。根據SAO標準星表，此范圍內共記錄恒星258 997顆。一般用于星敏感器的空間相機可以記錄亮度在6.0星等以上的恒星，在此亮度范圍內共有5103顆恒星。

在實際工程應用中，星圖識別算法與星圖數據庫兩者的關系是密不可分的，對于特定的一種星圖識別算法，往往需要專門設計一種優化的星圖數據庫，以保證程序運行效率盡可能高。

本文在三角形匹配算法的基礎上，使用一套基本算法思路，同時完成導航星圖數據庫和星圖識別算法的改進設計，使程序的兩部分運行在統一的核心算法下，達到速度、可靠性和硬件資源利用率的最大化優化。

2.1 導航星圖數據庫設計

導航星圖數據庫的主要設計目標是，使星圖數據庫達到覆蓋率高、數據量小、模式唯一等3個指標。基于典型的航天器硬件環境以及星敏感器系統的任務場景，導航星圖數據庫應達到如下指標。

(1)覆蓋率：任意觀測姿態和視軸指向下，相機視場中的恒星數目不小于4顆的概率大于99%，不小于5顆的概率大于98%；

(2)數據量：星圖數據庫的總容量小于1 Mbyte；

(3)模式唯一性：在構建的所有導航三角形中，每個三角形的形態特征都可以用一組特征數據作唯一的表達。

為了尋求導航恒星三角形的形態特征，現對這5103顆恒星進行如下兩步處理：①導航星三角形的選取；②特征星表構建。

2.1.1 導航星三角形的選取

為了縮減導航星數據庫的規模，需要對星三角形的數量進行篩選。對于一個視場下的恒星，任選其中3顆組成三角形，可以得到這3顆恒星在天體坐標系下的單位方向矢量r1,r2,r3，其中|r1|=1,|r2|=1,|r3|=1，設r1r2夾角為α，r2r3夾角為β，r1r3夾角為γ，如圖1所示，由r1,r2,r3所構建的平面三角形邊長a、b、c為

(1)

對于參考星表中的5103顆恒星，分別以每顆恒星為主星m，以主星位置為視軸，在10°×10°的視場內提取恒星，被提取的恒星作為從星s，如圖2所示，根據公式組1可以計算出主星與視場中任意從星的距離Dm-s，由于視場大小約束，主星與從星的最大夾角為5°，由于星敏感器焦面成像分辨率的限制，主星與從星的最小夾角設定為0.6°。這樣計算出的主從星間距離將會很小，不方便后續計算，為此，將所求得距離乘以100(不影響后續恒星識別)。這樣處理后，當主從星的夾角為0.6°時，Dm-s≈1.047；當主從星的夾角為5°時，Dm-s≈8.728。導航三角形的構造規則是：首先篩選出與主星距離Dm-s滿足1≤Dm-s≤8.728的從星，然后將篩選出的從星到主星的距離排序，保留距離主星最近的四顆恒星(不夠四顆恒星的全部保留)s1、s2、s3、s4分別與主星m構成導航三角形：m-s1-s2，m-s1-s3，m-s1-s4，m-s2-s3。剔除重復的三角形后，在全部目標天區一共構造出9803個導航三角形,且覆蓋了所有5103顆恒星。

圖1 恒星矢量示意圖Fig.1 Vectors from observation point to target star

圖2 恒星提取示意圖Fig.2 Selection of master/slave stars

2.1.2 特征星表的構建

傳統的平面三角形匹配法，是使用相機圖像中的觀測星三角形與星圖數據庫中的導航三角形進行邊長比對，每個三角形需要比對三條邊的邊長，典型情況下，需要比對3～6次。典型的相機圖像含有5～10顆恒星，按照上文的三角形構建法，將含有很多個觀測三角形，比對次數則將達到數十次。如果能把每個觀測三角形比對次數縮減為1次，那么匹配時間將大大縮短。為了達到這一目的，需對剛才構建的9803個導航三角形進行主成分分析。

對于2.1.1節中構建的導航三角形，取其中任意一個，可以用一個標志向量ti來唯一標識，ti=[aibici]T，其中ai,bi,ci為三角形的三邊長，1≤i≤9803，所有導航三角形標志向量可構造矩陣M=[t1t2… tn]，M為3×n矩陣，n=9803，對矩陣M進行主成分分析，步驟如下：

(2)構造零均值矩陣Q=[φ1φ2… φn]，φi=ti-t，1≤i≤n,n=9803；

(3)計算協方差矩陣C=QQT的特征值，取最大特征值對應的特征向量umax，該向量代表矩陣M的主成分方向，本文稱其為投影直線，記為L。

對于2.1.1節中構建的任意一個導航三角形標志向量,在投影直線上的特征投影值可用以表示為

(2)

式中：pi為第i個導航三角形標志向量在投影直線上的投影值，1≤i≤9803。

對于每一個導航三角形，它的標志向量在投影直線L上有唯一的投影值，將所有導航三角形的投影值按從小到大排序編號并建立索引，設定索引值為f。表1為特征星表中的一部分，其中f為索引值，p為標志向量的特征投影值，i1、i2、i3為星號，a、b、c為導航三角形三邊長。

表1 特征值索引表(部分)

圖3 特征向量空間分布圖
Fig.3 Distribution of eigenvector

圖3為2.1.2節中所構建的導航三角形標志向量ti的空間分布情況，紅色直線為投影直線。圖4為直角坐標系中特征投影值與索引值的對應關系示意，從圖3，4可以看出，每一個導航三角形對應的標志向量在投影直線中都有且只有唯一的特征投影值與之對應。從表1可以看出，即使有的特征投影值很接近，但它們對應的索引值不同。由此滿足了導航星庫的模式唯一性要求。

圖4 特征向量投影值平面分布
Fig.4 Distribution of eigenvalue

經過本節所述的數據處理，完成了特征向量投影法導航星庫的構建，導航星庫由兩部分組成：第一部分是導航三角形及其特征投影值索引庫，第二部分是全體導航三角形的主成分向量umax及其所在的投影直線L。由于經過2.1.1節導航三角形的篩選，限制了導航三角形的總數，由此達到了縮減數據庫容量的目的，編程結果顯示數據庫容量為0.743Mbyte，符合預期指標。

2.2 星圖識別算法設計

在星敏感器拍攝獲得任一幅星圖后，將根據所拍星圖中的恒星來構建觀測三角形，獲取其標志向量的投影值，并與星圖數據庫中的特征投影值進行比對。

星圖識別過程由兩部分組成：第一部分是從星敏感器拍攝的星圖中獲取觀測三角形向量投影值；第二部分是用求解的投影值與導航星庫中的特征投影值比對，完成觀測三角形的匹配識別。

2.2.1 求取觀測三角形的投影值

星敏感器拍攝星圖后，按照2.1.1節給出的方法，在圖像內構建觀測三角形。

(3)

(4)

由此可以得到相機拍攝的觀測三角形的特征投影值，簡稱為觀測投影值。

2.2.2 匹配識別

(5)

3 算法程序性能測試

使用C++語言和openCV視覺運行庫實現星圖識別算法程序，并編寫程序用以生成仿真相機圖像。使用仿真圖像模擬了相機在各種成像條件下拍攝的星圖，并加入了一定的干擾。用10 000幀隨機仿真圖像作為輸入，測試了本文特征向量投影(EPM)算法的星圖識別成功率和識別速度，并引用了傳統平面三角形匹配法和P向量算法(一種目前較先進的星圖識別算法，使用了另一種三角形標志向量作為對比參數，并使用恒星星等數據作為第二個參考維度)的測試結果進行對比。

3.1 星圖數據庫覆蓋性驗證

圖5是對導航星圖數據庫覆蓋性的測試結果統計。可以看出，由于本文提出的數據庫設計方法并未對恒星數量做出任何刪減，所以恒星在全天區的覆蓋性較好。在10 000幀隨機圖像中，含有7顆或以上恒星的概率為95%，含有5顆或以上恒星的概率為98.5%，含有4顆或以上恒星的概率為99.5%。

圖5 單一視場恒星數量統計
Fig.5 Probability distribution of star’s contents in single-frame

3.2 視場中恒星個數對識別率的影響

如圖6所示的恒星個數對識別率的影響曲線可以看出，在恒星數目較少的情況下，平面三角形算法的識別率高于本文算法和P向量算法，而本文算法識別算法明顯優于P向量算法，當視場中恒星數目為5顆的時候，平面三角形算法識別率97.3%，本文算法識別率為87.2%，而P向量的識別率為68.1%；當視場中恒星數目為7的時候，平面三角形算法的識別率為99.2%，本文算法的識別率為95.3%，而P向量的識別率為90.6%；當恒星數目大于7顆的時候，本文算法和P向量算法識別率趨于100%，而平面三角形算法的識別率存在小幅度的跳躍，然后慢慢趨于100%。而一個視場中恒星數目大于7的概率為95%以上。在大多數情況下，本文算法的目標識別率與平面三角形算法和P向量算法十分接近，均趨近于100%。

圖6 恒星個數對識別率的影響曲線Fig.6 Relationship between recognition rate and number of stars

3.3 恒星位置偏移對識別率的影響

隨機產生10 000幀星圖，分別為其加上隨機方向0～2個像素的位置偏移，統計在不同的位置偏移情況下(統計視場內恒星個數為5顆以上的星圖)，這3種算法的識別率變化情況，圖7為3種算法在不同位置偏移情況下識別率的比較曲線。從圖中可以看出，在加入0～2個像素的位置偏移的過程中，3種算法識別率均呈現出下降趨勢；具體從各個算法上分析，本文算法識別率從99.3%下降為96.7%,P向量算法識別率從98.9%下降為96.2%，平面三角形算法受位置偏移影響較大，識別率下降幅度最大，識別率從99.1%下降到94.1%。

圖7 位置噪聲對識別率影響曲線Fig.7 Location-bias’s effect on the recognition rate

3.4 星等誤差對識別率的影響

對上述隨機產生的10 000幀星圖，分別為其加上0到0.5的星等誤差，加上星等誤差后的恒星星等小于0星等記為0星等，大于6星等記為6星等，統計在不同的星等誤差情況下(統計視場內恒星個數為5顆以上的星圖)這3種算法的識別率變化情況，圖8為3種算法在不同星等下識別率的比較曲線，從圖中可以看出，本文算法和平面三角形算法對于星等誤差均不敏感，均能夠保證高識別率，原因在于兩種算法利用的都是導航星所構成三角形的形態特征來進行星圖識別。

圖8 星等測量誤差對識別率影響曲線Fig.8 Recognition rate effected by star magnitude’s diviation

3.5 假星干擾對識別率的影響

對上述隨機產生的10 000幀星圖，對上述星圖分別添加0～6個假目標，統計在不同的數目的假目標干擾下(統計視場內恒星個數為5顆以上的星圖)這3種算法的識別率變化情況，圖9為3種算法在不同數目的假目標影響下識別率的比較曲線。隨著添加的假目標數目的增加，3種算法識別率均呈現出下降趨勢，平面三角形算法的識別率下降最為明顯，當假目標數目為0時，其識別率為99.1%；當假目標數目為1時，其識別率僅為56.8%，由此看出，在有假目標存在的情況下，平面三角形算法魯棒性很差。在假目標數目從0增加到6顆時，本文算法識別率由99.3%下降為91.6%，P向量算法則從98.9%下降為82.7%，由此可見，在有假目標干擾的情況下，本文算法魯棒性明顯優于其他兩種算法。

圖9 假目標對識別率的影響曲線Fig.9 Recognition rate effected by fake target

3.6 平均識別時間

使用10 000幀隨機星圖對3種算法的識別速度進行測試，統計其總識別時間并計算每幀圖像的平均識別時間。測試結果為：平面三角形算法平均識別時間為1.12 s，P算法7.63 ms，本文算法7.48 ms，本文算法識別速度最快。

3.7 綜合指標對比

隨機產生10 000幀星圖，對上述星圖分別添加2個隨機位置假目標，統計3種算法的識別率和平均識別時間，如表2所示。

表2 綜合測試結果匯總

本文算法的識別率97.4%，P向量的識別率為95.2%，平面三角形的識別率為53.3%。對于平面三角形算法，其星圖數據庫由于存儲了每顆導航星所能組成的所有三角形數目，即使加入了視場約束條件，容量也達到178 Mbyte，遠遠大于前2種算法所需的存儲空間，本文算法所需的存儲空間比P向量算法的存儲空間多38.3%，但是識別時間略短于P向量算法，本文算法實時性和可靠性較優。

4 結束語

本文通過一種基于特征向量投影法的設計方法，同時對平面三角形識別算法和導航星圖數據庫進行改進，設計了一種新的星圖識別程序算法。經仿真測試驗證：本文算法導航星庫具有全天99.5%的覆蓋率，且容量小于1 Mbyte；無噪聲和干擾情況下，在95%的全天視場中識別率接近100%；在有位置噪聲、星等噪聲和假星干擾情況下，本文算法魯棒性優于傳統三角形匹配法和P向量算法；平均識別時間為3種算法中最短。此算法具有更高的匹配速度，在復雜干擾條件下有更好的抗干擾性能，且數據庫容量小，達到了兼顧實時性、適用性和可靠性的設計目的。

References)

[1]謝木軍，馬佳光，傅承毓, 等. 空間光通信中的精密跟蹤瞄準技術[J]. 光電工程，2000，27(1): 3

Xie Mu Jun, Ma Jia Guang, Fu Cheng Yu, et al. Precision tracking and pointing technologies in space optical communication[J]. Opto-Electronic Engineering, 2000,27(1),3 (in Chinese)

[2]Hye-Young K，Junkins J L．Self-organizing guide star selection algorithm for star tracker: thinning method[C]// IEEE on Aerospace Conference Proceedings. New York: IEEE, 2002

[3]鄭萬波，劉智，郝志航. 二維精簡索引分層導航星庫的構造[J]. 吉林大學學報(信息科學版)，2003，21(2): 123-127

Zheng Wan Bo, Liu Zhi, Hao Zhi Hang. Construction of delaminating guide star data base with 2-D condensed index [J]. Journal of Jilin University (Information Science Edition), 2003, 21(2): 123-127 (in Chinese)

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

Xu Shi Wen, Li Bao Hua, Zhang Ying Chun, et al. A storing navigation star database method for star map recognition using character match[J]. Journal of Harbin Institute of Technology, 2005, 37(6): 819-821 (in Chinese)

[5]鄭勝，吳偉仁，田金文.一種新的導航星選取算法研究[J]. 宇航學報，2004，25(1): 35-40

Zheng Sheng, Wu Weiren, Tian Jinwen. A novel regression selection algorithm of guide star[J]. Journal of Astronautics,2004,25(1): 35-40 (in Chinese)

[6]劉朝山，馬瑞平，肖稱貴. 星圖匹配制導中的關鍵技術[J]. 宇航學報，2006，27(1): 31-35

Liu Chaoshan, Ma Ruiping, Xiao Chenggui. Star pattern matching for celestial guidance[J]. Journal of Astronautics, 2006，27(1): 31-35 (in Chinese)

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

[8]M S School. Star-field identification for autonomous attitude determination[J]. Journal of Guidance Control and Dynamics, 1997, 18(1): 61-65

[9]李立宏，林濤. 一種改進的全天自主三角形星圖識別算法[J]. 光學技術，2000，26(4): 372-374

Li Lihong, Lin Tao. Improved all-sky autonomous triangle star-field identification algorithm [J]. Optics and Precision Engineering, 2000，26(4): 372-374 (in Chinese)

[10]鄭勝，吳偉仁，田金文.一種新的全天自主幾何結構星圖識別算法[J]. 光電工程，2004，31(3): 4-7

Zheng Sheng, Wu Weiren, Tian Jinwen. A novel all-sky autonomous triangle-based star map recognition algorithm[J]. Opto-Electronic Engineering, 2004, 31(3): 4-7 (in Chinese)

[11]賀鵬程.一種改進的三角形識別算法[J]. 艦船電子工程，2012，32(4): 42-44,61

He Pengcheng. An improved triangle matching recognition algorithm[J]. Ship Electronic Engineering, 2012, 32(4): 42-44, 61 (in Chinese)

(編輯：張小琳)

An Algorithm for Autonomous Star Field Identification

JIA Mengyang

(Institute of Telecommunication Satellite, China Academy ofSpace Technology, Beijing 100094, China)

Researches on several existing star pattern recognition technologies are carried out in this article. To improve the efficiency and reliability of star sensor system, a new advanced star pattern match algorithm—based on the essential algorithm named Eigenvector Projection Method(EPM)—is designed, programmed, and tested in this article. This algorithm is designed to reduce data capacity of the star database and to improve the speed of processing. According to the test results, this new algorithm has successfully improved the efficiency and reliability of the star map recognition system.

star tracker；star pattern matching；EPM

2016-11-04；

2016-11-22

賈蒙楊，男，碩士，工程師，研究方向為圖像處理。Email: kerr_1@126.com。

TP75

A

10.3969/j.issn.1673-8748.2016.06.016