基于特征圖形匹配法的高效星圖識別方法

李超兵，袁艷艷，王丹曄

北京航天自動控制研究所，北京 100859

?

基于特征圖形匹配法的高效星圖識別方法

李超兵*，袁艷艷，王丹曄

北京航天自動控制研究所，北京 100859

針對目前星敏感器使用的星圖識別算法存在的冗余匹配、匹配時間長、識別率低等缺點，對星圖識別算法進行了研究，提出了一種高效星圖識別方法。該算法首先對傳統星表進行處理，取出冗余信息，重新分配天區，使每個天區的導航星數目均勻，將分區以及處理后的星表信息重新存儲并作為導航星庫，然后通過對拍攝的圖像進行處理并提取特征信息，與導航星庫中的特征信息進行匹配，從而改善傳統星圖匹配算法出現冗余匹配、匹配時間過長及識別率低等缺點。完成算法設計后，選取視場為15°×15°的大視場星敏感器，對該算法進行仿真驗證分析，可以發現該算法可以實現部分天區與拍攝星圖匹配時間在20 ms以內，全天區星圖的識別和匹配時間在1.5 s以內，識別率達到98%以上，印證了該算法可以提高識別的成功率并且縮短識別時間，使識別算法具有高效性。

星圖識別；星表重構；圖像處理；特征圖形匹配；星敏感器；全天區

星敏感器作為姿態測量工具如今已經越來越廣泛地應用于航天器中，星敏感器的發展越來越快，從早期星敏感器到第一代電荷耦合元件(Charge Coupled Device，CCD)星敏感器，然后發展到近期的第二代CCD星敏感器，目前研究正處于第二代CCD星敏感器和互補金屬氧化物半導體(Complementary Metal Oxide Semiconductor，COMS)星敏感器的過渡時期，因此針對星敏感器的星圖匹配算法也正迅速發展。星圖識別的過程是：首先進行圖像采集以及圖像的預處理，然后對處理后的星圖進行特征圖形提取，最后將拍攝星圖的特征圖形與圖庫中的特征圖形進行識別匹配[1]。

常用的面向星敏感器的星模式識別算法主要包括：對角距匹配算法、三角形角距匹配算法、多邊形角距匹配算法、柵格算法、主星識別法及概率統計算法等。其中，應用最為廣泛的是三角形角距匹配算法和主星識別算法，三角形角距匹配算法在實際使用當中相對容易，但是識別過程中采用的特征維數較少，會出現冗余匹配的情況；主星識別法在進行的過程當中不需要進行重復匹配，識別速度快，但是如果視野中有很多顆星星等相近時，會使識別成功率嚴重降低[2]。為了解決三角形角距匹配算法的搜索效率，在三角形匹配算法基礎上，提出了K矢量算法、B矢量算法以及P矢量算法。這些方法提高了識別速度、識別成功率，具有對噪聲的魯棒性，占用內存比較小。近些年來發展起來的算法主要有：基于奇異值分解算法、基于遺傳算法的方法和基于神經網絡的算法等較新的星模式識別算法。但是這些算法實現起來比較復雜，而且需要的學習時間很長，無法在星敏感器中直接使用。

本文所設計的基于特征圖形匹配的星圖識別算法將特征圖形匹配應用到星圖識別算法中，使算法具有較高的識別率，而且通過對星表冗余信息的處理，提高識別效率，使得該算法具有高效性，具有廣泛的應用前景。

1　星敏感器測星信息處理

1.1導航基本星表的選擇以及重構

導航星表是星圖匹配算法的基礎，但是傳統的導航星表導航星數目眾多，會導致巨大的計算量，不利于算法的實時性[3]。因此，需要從基本星表中挑選出一部分具有代表性的導航星，利用其位置和亮度信息編制而成簡易且高效的導航星表，這樣可以令星圖匹配算法的計算量減小，提高計算的效率。

目前在航天領域應用的星表多為編制星表，例如：史密松天體物理天文臺星表(SAO)、第五基本星表(FKS)以及亮星星表(BSC)、導引星表(GSC)等。

衛星導航任務經常采用SAO星表，SAO星表中記錄了大概26萬顆恒星的信息，位置精度高，因此本文選擇SAO星表作為基本星表。SAO星表采用二進制格式進行存儲，每行數據的具體格式如表1所示。

表1　SAO星表數據格式

為了減少子星表的容量，需要對觀測星進行處理，目前國內主流星敏感器大部分能觀測到6.5星等的恒星，那么就按6.5的星等對星表過濾，提取星等達到6.5的9 040顆星的赤經、赤緯等信息就成了所需的參考星表。給定一個視場，只需要根據赤經、赤緯查找落于該視場內的星即可。處理后的星表包含的信息為：恒星編號、赤經、赤緯、星等4部分信息。

對于不同的星圖匹配方法，星表的存儲方法也不同，現有的存儲方法主要有赤緯帶法、重疊區域法、球矩陣法、重疊的球矩陣法等，由于這幾類導航星表劃分方式存在星點分布不均勻等問題，所以本文采用內接正方體星表劃分方法。該方法的劃分步驟具體如下：

(1)

其他5個天區的中心軸線和4個邊界點的方向矢量依此類推。

圖1　天區劃分Fig.1　Area division

2)如圖1(b)、(c)所示，將每一個大天區均勻地劃分成N×N的小天區。這樣整個天球球面將被劃分為6個大天區、6×N×N個小天區，大小為(90/N)×(90/N)。

按照上述步驟劃分天球并掃描每個天區的導航星，建立分區導航星表，記錄每顆導航星的信息。

應用內接正方體星表劃分的方法，將全天星圖劃分成6個區域，生成6個天區星表，每個星表的經緯度范圍劃分如表2所示。

表2　星表經緯度范圍

依據該經緯度范圍，得到6個導航星表。這種劃分方法可以保證天區劃分的均勻性。

然后再將每個天區分為6×6個子塊，進一步減少所需存儲空間，也使星圖識別的匹配速度提高，除此之外還需要對導航星進行篩選，在保證星圖識別準確性前提下盡量減少導航星數量。篩選原則如下：在每個子星表中選取最亮的6顆導航星，如果子星表中的導航星數目小于6，則不做任何處理。由于變光星的亮度不穩定，不適于作為導航星，因此需要將變光星剔除；除此之外，還需要考慮到每個子星表中任意兩顆導航星之間的星光角距不易太小，因為距離太近的導航星可能引起誤匹配，所以將星光角距小于閾值(0.1°)的導航星排除掉。經過篩選后的天區，導航星的分布變得更加均勻，有益于提高星圖匹配的速度。

1.2拍攝圖像預處理方法

星敏感器在天空中運作時，在特定天區所拍攝到的星空圖片，要先進行星圖處理，因此本節將介紹關于星圖處理的基本方法。星圖處理主要步驟包括灰度化、反白和拉伸3個步驟，具體過程如下：

(1)灰度化

灰度化就是將原來的32位彩色圖像轉變為8位的灰度圖像。灰度圖像占存儲空間更小，便于以后進行處理。

(2)反白

反白的目的就是使圖像中的黑色與白色進行轉換，從而使星點的顏色偏黑，而背景的顏色偏白，這樣可以方便后續的處理。圖2給出了經過灰度化及反白處理后的部分大熊座。

圖2　經過灰度化及反白處理后的部分大熊座Fig.2　Photo of Ursa after being grayed and inversed

(3)拉伸

拉伸處理可以有效地去除冗余信息、凸顯有效信息，讓圖像中的星點更容易提取出來。拉伸處理的方法很多，這里主要介紹指數拉伸。

指數是對低灰度值進行壓縮、對高灰度值進行拉伸，并會將所有灰度值小于某給定數值a的點的灰度值均變為1。示意如圖3所示，其中x軸表示原圖灰度值，y軸表示進行變換后的灰度值。計算公式如下：

(4)

式中：x為該點的灰度值。a、b、c用于調整曲線的位置和形狀。

圖3　指數拉伸示意Fig.3　Index stretching schematic diagram

經過多次試驗最終選取參數值a=128、b=1.3、c=1.15。

接下來以獅子座的圖片為例進行仿真。首先將拍攝的圖片進行星圖處理，拍攝的圖片如圖4所示，經過星圖處理后的圖片如圖5所示。

圖4　獅子座拍攝星圖Fig.4　Photo of Leo

圖5　獅子座處理后的星圖Fig.5　Star catalog of handled Leo

然后將圖像處理后的星圖轉變成為矩陣，將其中灰度值大于21的點，以數字0表示，灰度值小于20的點用數字1表示。

2　特征圖形匹配算法

在進行天文導航時，如何將星敏感器拍攝到的星圖與被導航星圖特征正確匹配是天文導航研究的重點，星圖匹配結果的好壞直接影響導航精度[4]。特征圖形匹配包括特征圖形矩陣的構造和特征圖形匹配兩部分，下面分別給出特征圖形矩陣的構造方法及特征圖形匹配方法的具體步驟。

2.1特征圖形的構造及匹配

飛行器在太空中工作時，由于空間環境復雜，導航相機經常處于晃動狀態，所拍攝到的星空圖片有可能會存在畸變現象。為了解決這個問題，本文通過圖論的基本原理構造特征圖形。由于圖論對于圖形矩陣的表述方法是根據特征點之間的連通關系構建特征圖形矩陣，而圖形畸變不會改變特征點的連通關系。

圖論的基本原理為：由n個特征點構成的圖形，圖形矩陣g中的第i行、第j列元素表征為第i個點與第j個點間的連通關系，若第i個點與第j個點是連通的，則圖形矩陣中g(i,j)=1，若第i個點和第j個點不連通，則圖形矩陣中g(i,j)=0。

(5)

由圖論的基本原理可知，特征圖形矩陣構建的關鍵在于特征點之間連通關系的確定，本文采用下面的方法建立圖形特征點之間的連通關系[5-7]。

由于星點之間相對角距保持不變，可據此建立星點之間的角距矩陣：

(6)

矩陣D中的元素di,j表示第i個星點與第j個星點之間的角距，數學表示如下：

(7)

式中：si、sj為星點方向矢量。

(8)

對計數矩陣Cd每一列中的最大的元素進行篩選、排序，按篩選出的列最大元素的大小確定特征點之間的連通關系，即在圖片Pn中，將最大的元素所對應的特征點與次最大元素所對應的特征點之間連通，以下依次連通下去。列最大元素如果小于2/3特征點個數，其所對應的特征點予以剔除，該連通規則考慮到了特征點之間的位置關系，又避免了由于個別特征點誤匹配造成的匹配誤差[8-10]。圖片Pm中特征點的連通方法與此相同，下面給出連通規則的數學表述：

(9)

(10)

對ck序列按照從大到小的順序排序[11-12]，以i表示圖片Pn中的第i個特征點，記為nk；以j表示圖片Pm中的第j個特征點，記為mk。ck序列排序結果如下：

(11)

從ck中就可以得到待匹配星點與導航星的一一對應關系，即圖片Pn中的第na個特征點對應圖片Pm中的第ma個特征點，以此類推，就可以得到待匹配星圖中的星點與導航星圖中的導航星的對應關系，從而實現了星圖匹配的目的[13-15]。

2.2仿真算例及分析

由于選取的視場內的星點數對匹配時間和匹配成功率有一定影響，對此，針對選取不同特征星點數量進行仿真，觀察算法的成功率以及運算時間。

表3　不同星點數運算時間與匹配成功率

通過表3可以看出，在選取的星點數目大于或等于6時，成功率為100%，并且星點數目越多，運算時間越長，因此選取星點數目為6可以使算法具有高效性。

對一天區中0°～E45°，0°～S35.264 4°范圍內的9個子星表進行星圖匹配仿真，仿真結果如圖6～圖7所示。

圖6　星圖數據庫圖片Fig.6　Picture of star catalog database

從每個子天區中提取最亮的6個星點構成特征圖形與一天區的導航星表進行星圖匹配，其中圖6為該區域星表圖片，圖7為待匹配星圖與導航星表子天區的匹配仿真結果。從仿真結果可以看出，9個子天區提取的6個特征點全部可以在導航星圖中找到與之匹配的特征圖形，并且匹配結果符合實際情況。

以一天區為例，進行星圖識別仿真試驗，取一天區36個子星圖作為待匹配星圖，以精簡后一天區星表為待匹配數據庫，進行仿真試驗，仿真結果如表4所示。

圖7　星圖匹配仿真結果Fig.7　Simulation results of star map matching

星敏感器精度/(″)匹配成功組數試驗組數成功率/%1036361001003636100200353697.22300333691.67400303686.11500253669.44

從以上的仿真試驗中可以看出，當星敏感器測量誤差在100″以內時，正確率可以達到100%。星敏感器的測量誤差超過500″時，特征圖形匹配算法的正確率會迅速下降。目前國內星敏感器的測量精度可以達到10″，因此，特征圖形算法完全可以滿足需求。

選取不同的拍攝照片噪聲水平進行仿真，通過表5中，可以看出當噪聲為50″以內時，匹配成功率依然符合要求，當圖片噪聲大于50″時，匹配成功率下降，因此設置拍攝照片噪聲閾值為50″。

表5　不同拍攝噪聲對應算法正確率

從以上仿真可以看出，特征圖形匹配效果很好；并且能實現局部天區(15°×15°)的匹配時間在20 ms以內，全天區的識別和匹配時間在1.5 s以內，在識別時間與精確程度上高于傳統方法，故該方法能夠高效地實現識別任務。

3　結束語

本文的主要目標是對星敏感器星圖匹配技術開展研究,完成導航星表的構建與處理方法設計、容錯高效星圖匹配算法設計，為天文導航提供星光矢量信息。

本文在SAO基本星表的基礎上，利用內接正方體法劃分天區，保證了天區劃分的均勻性，在此基礎上進行了合理的精簡，設計出了實用高效的導航星表。

本文利用指數拉伸的方法，將經過灰度化和反白的拍攝星圖合理地轉換為數字星圖，從而提取出圖片中的星點信息，然后利用所得到的星點信息，組成特征圖形矩陣，進行星圖匹配，完成了容錯性高，實時性良好的星圖匹配算法設計，得到了較好的仿真分析結果，完成了導航解算的任務，證明了基于特征圖形匹配的天文導航方法高效性。

References)

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

XING Y F， WANG J H. An improved star recognition algorithms based on singular value method[J].Intelligent Computer and Applications，2014，4(2)：21-24，28(in Chinese).

[2]張磊，何昕，魏仲慧，等. 基于星圖識別的空間目標快速天文定位[J]. 光學精密工程，2014，22(11)：3074-3080.

ZHANG L，HE X，WEI Z H，et al. Fast celestial positioning for space objects based on star identification[J]. Optics and Precision Engineering，2014，22(11)：3074-3080(in Chinese).

[3]徐韜祜，孫華燕，張廷華，等. 基于星圖模擬的星空目標提取[J]. 激光與紅外，2015，45(1)：104-108.

XU T H，SUN H Y，ZHANG T H，et al. Space target extraction in star background image based on star image simulation[J]. Laser & Infrared，2015，45(1)：104-108(in Chinese).

[4]穆榮軍，高銘陽，劉斌，等. 探月飛行器軟著陸光學自主導航的特征圖形匹配方法研究[J]. 空間科學學報，2014，34(6)：858-866.

MU R J，GAO M Y，LIU B，et al. Research on characterized graphics matching method of autonomous optical navigation for lunar explorer[J]. Chinese Journal of Space Science，2014，34(6)：858-866(in Chinese).

[5]劉曉平，何士雙. 基于三角劃分的多連通域圖形匹配研究[J]. 工程圖學學報，2010，31(1)：61-66.

LIU X P，HE S S， Research on graphics matching of multiply connected region based on triangulation[J]. Journal of Engineering Graphics，2010，31(1)：61-66(in Chinese).

[6]施航，朱志剛. 星敏感器星圖處理研究[J]. 光學與光電技術，2014，12(6)：58-60.

SHI H，ZHU Z G. Image processing of star sensor[J]. Optics& Optoelectronic Technology，2014，12(6)：58-60(in Chinese).

[7]崔祥祥，王宏力，王永勝，等. 組合星圖技術中的雙星敏感器安裝角度分析[J]. 光電工程，2013，40(12)：49-53.

CUI X X，WANG H L，WANG Y S，et al. Mounting angle between two star trackers in combined images technique[J]. Opto-Electronic Engineering，2013，40(12)：49-53(in Chinese).

[8]李旻珺，楊博，胡靜. 星光折射導航星的改進三角識別捕獲[J]. 航天控制，2012，30(1)：33-39.

LI M J，YANG B，HU J. The capture of grazing star based on the modified triangle identification algorithm[J]. Aerospace Control，2012，30(1)：33-39(in Chinese).

[9]陸敬輝，王宏力，孫淵，等. 應用相近模式向量的主星星圖識別算法[J]. 紅外與激光工程，2011，40(1)：164-168.

LU J H，WANG H L，SUN Y，et al. Main star identification algorithm based on similar pattern vectors[J]. Infrared and Laser Engineering，2011，40(1)：164-168(in Chinese).

[10]HO KOKI，NAKASUKA SHINICHI. Novel star identification method combining two star trackers with extended FOVs[C]. AIAA Guidance， Navigation，and Control Conference，August 2-5，2010，Toronto，Ontario，Canada.

[11]HASHMALL JOSEPH A. Star identification using a triplet algorithm[C]. 54th International Astronautical Congress of the International Astronautical Federation，the International Academy of Astronautics，and the International Institute of Space Law，September 29-October 3，2003，Bremen， Germany.

[12]KUMAR MRINAL，MORTARI DANIELE，JUNKINS JOHN. An analytical approach to star identification reliability[C]. AIAA Guidance， Navigation and Control Conference and Exhibit，August 18-21，2008，Honolulu，Hawaii.

[13]ROBERTS PETER，WALKER RODNEY. Application of a counter propagation neural network for star identification[C]. AIAA Guidance，Navigation，and Control Conference and Exhibit，August 15-18，2005，San Francisco，California.

[14]NEEDELMAN DAVID D，ALSTAD JAMES P，LAI PETER C，et al. Fast access and low memory star pair catalog for star pattern identification[J]. Journal of Guidance，Control，and Dynamics，2010，33(5)：1396-1403.

(編輯：車曉玲)

An efficient stellar map identification method based on characterized graphics matching method

LI Chaobing*，YUAN Yanyan,WANG Danye

Beijing Aerospace Automatic Control Research Institute，Beijing 100859，China

Nowadays, star pattern recognition methods used on star sensors have shortcomings of redundancy match, matching slow, low recognition rate，and so on. To overcome this，the star pattern recognition algorithm was studied，and a new algorithm was proposed. Firstly, redundancy information from traditional star catalog was extracted. The sky coverage was divided to make sure that different sky coverage has the similar navstar number. Secondly，feature information from the photo was extracted to match the feature information database. After the algorithm was designed, the star sensors with the field of view 15°×15° were selected and simulated. Simulation results show that the matching of the whole sky can be finished in 1.5 s by this algorithm, and the success rate can reach over 98%.

staller map identification；staller table reconstruction；image processing； characterized graphics matching； star sensor；whole sky coverage

10.16708/j.cnki.1000-758X.2016.0047

2016-04-20；

2016-06-02；錄用日期：2016-06-30；

時間：2016-08-0214:20:13

http:∥www.cnki.net/kcms/detail/11.1859.V.20160802.1420.004.html

李超兵(1981-)，男，碩士，高級工程師，lcbpku@163.com，主要研究方向導航制導與控制

V249.32+3

A

http:∥zgkj.cast.cn

引用格式：李超兵，袁艷艷，王丹曄.基于特征圖形匹配法的高效星圖識別方法[J].中國空間科學技術，2016，36(4)：9-16.LICB，YUANYY,WANGDY.Anefficientstellarmapidentificationmethodbasedoncharacterizedgraphicsmatchingmethod[J].ChineseSpaceScienceandTechnology， 2016，36(4)：：9-16 (inChinese).