一種改進RANSAC校驗的失效衛(wèi)星位姿估計回環(huán)檢測方法

程向紅，李丹若，曹 毅，牟金震

（1.微慣性儀表與先進導(dǎo)航技術(shù)教育部重點實驗室，南京 210096；2.東南大學(xué) 儀器科學(xué)與工程學(xué)院，南京 210096；3.上海市空間智能控制技術(shù)重點實驗室 上海 201109）

如何實現(xiàn)失效衛(wèi)星的修理或清除，是目前空間技術(shù)發(fā)展的重要方向?？臻g衛(wèi)星在長期失效后，由于能量的不斷耗散，通常圍繞最大慣性主軸進行緩慢的自旋運動[1]。服務(wù)航天器需識別失效衛(wèi)星并估計其位姿，為后續(xù)的抓捕或清除提供條件。視覺傳感器具有體積小，低功耗，可靠性高等優(yōu)點，十分適合空間在軌服務(wù)的應(yīng)用場景[2]。視覺SLAM（Simultaneous Localization and Mapping）技術(shù)作為一種解決未知運動目標相對位姿測量的有效手段，時常被國內(nèi)外研究者遷移用于解決空間失效衛(wèi)星位姿估計問題[3]。而在SLAM求解位姿的過程中，長時間連續(xù)觀測會帶來累積誤差增大、位姿解算不收斂等難題。回環(huán)檢測是消除累積誤差的有效手段，是失效衛(wèi)星位姿估計問題的熱點與難點。同時，利用回環(huán)檢測粗略求得失效衛(wèi)星的自旋角速度，對后續(xù)的接近或抓捕十分重要[4]。

基于詞袋模型（Bag of word,BoW）的回環(huán)檢測算法是失效衛(wèi)星回環(huán)檢測的主流[5]。該方法通過預(yù)訓(xùn)練好的詞典庫生成圖像的詞袋向量，計算向量相似度來完成回環(huán)檢測[6]。但是，該算法的性能嚴重依賴于預(yù)訓(xùn)練提取生成的詞典庫，對空間復(fù)雜多變的場景適應(yīng)性差。

隨著深度學(xué)習(xí)技術(shù)在圖像上的廣泛應(yīng)用，基于深度學(xué)習(xí)的回環(huán)檢測成為當(dāng)前的研究熱點。2015年X Zhang等人利用預(yù)先訓(xùn)練的CNN模型提取高質(zhì)量圖像特征用于回環(huán)檢測[7]。深度學(xué)習(xí)提取出的全局特征雖具有良好的不變性，但其計算量大等缺陷也十分明顯。Shahbazi等人則將局部敏感哈希圖像檢索算法遷移至回環(huán)檢測中，快速對比圖像的相似性，獲得回環(huán)檢測結(jié)果[8]。清華大學(xué)的Gao等人則提出一種輕量級地實時快速深度學(xué)習(xí)架構(gòu)，利用較少的參數(shù)實現(xiàn)系統(tǒng)資源的高利用率，實現(xiàn)深度學(xué)習(xí)端對端檢測[9]。盡管如此，此類方法應(yīng)用至失效衛(wèi)星中依舊存在較多誤檢測。原因是：失效衛(wèi)星繞慣量主軸做自旋運動。部分失效衛(wèi)星的受觀測面相似度較高。在衛(wèi)星周期性旋轉(zhuǎn)進出視場時，深度學(xué)習(xí)提取的全局特征會因忽略局部空間關(guān)系導(dǎo)致算法精度不高。

RANSAC算法常用于圖像匹配。只是該算法通過迭代求解最優(yōu)模型，精度雖高，但應(yīng)用在空間失效衛(wèi)星中，仍有許多不足。

綜上所述，本文針對空間失效衛(wèi)星的特殊應(yīng)用場景，提出一種基于改進RANSAC（Random Sample Consensus）校驗的失效衛(wèi)星回環(huán)檢測方法，使用深度學(xué)習(xí)提取全局和局部特征，引入改進的RANSAC算法進行回環(huán)候選幀校驗，從而提高回環(huán)檢測在空間場景光照變化時的穩(wěn)定性。

1 回環(huán)檢測方法設(shè)計

傳統(tǒng)回環(huán)檢測方法往往遵循這一模式：提取圖像特征并描述，進行相似圖像檢索并提速，完成回環(huán)幀輸出。面對失效衛(wèi)星特殊的應(yīng)用環(huán)境，本文設(shè)計方法流程如圖1所示。與傳統(tǒng)流程不同的是，本文在方法最后增添了改進RANSAC圖像匹配校驗這一步。

圖1 算法流程Fig.1 Algorithm flow chart

本文使用HF-Net（Hierarchical Feature Network）多任務(wù)網(wǎng)絡(luò)，直接輸出圖像的3種特征：關(guān)鍵點，局部特征，全局特征[10]。

隨后，使用HF-Net輸出的全局特征進行圖像相似度對比。全局特征的特征維數(shù)高，直接對比計算量大，算法的運行效率低下。針對這一問題，本文借鑒圖像檢索領(lǐng)域的HNSW（Hierarchical Navigable Small World）算法，快速進行圖像對比，記錄高相似性圖像的索引，建立圖像回環(huán)幀候選集合[11]。

失效衛(wèi)星回環(huán)檢測的應(yīng)用場景復(fù)雜多變。僅比較全局特征，無法滿足回環(huán)檢測的精度要求。而局部特征雖對環(huán)境變化敏感，卻具有良好的區(qū)分性。因此，使用圖像局部特征，完成對當(dāng)前幀與候選幀集合的圖像匹配校驗，匹配程度最高的則為回環(huán)幀。

標準RANSAC算法采用隨機選點法，在選點計算最優(yōu)模型時，會不斷計算出效果較差的模型并拋棄。若特征點質(zhì)量較差，則會產(chǎn)生大量無效模型，造成模型浪費和計算資源的無端消耗。因此，本文對RANSAC算法進行改進，縮減RANSAC運行時間，獲取較為準確的圖像回環(huán)檢測結(jié)果。改進RANSAC算法成功應(yīng)用在失效衛(wèi)星回環(huán)檢測中，提升了回環(huán)檢測的效果。

2 回環(huán)候選幀檢索

2.1 HNSW算法

在檢索領(lǐng)域中，近鄰圖是最樸素的圖算法，它由簡單的頂點和邊構(gòu)建。最基礎(chǔ)的近鄰圖技術(shù)需從隨機某點出發(fā)，計算當(dāng)前點的友節(jié)點與目標點的距離，跳入距目標點最近的友節(jié)點再次出發(fā)。如此反復(fù)迭代，不斷逼近。NSW（Navigable Small World）算法則對近鄰圖技術(shù)進行了優(yōu)化。近鄰圖技術(shù)最重要的缺點在于，隨機選擇的出發(fā)點若是與目標點距離很遠，則會迭代多次，浪費時間。為此，NSW算法增加了高速公路機制。即在初始構(gòu)圖過程，查找到距離新點最近的點，連接新點到這些點。

HNSW算法是在NSW算法的基礎(chǔ)上，結(jié)合跳表提出的。跳表是用于有序元素序列快速搜索查找的一個數(shù)據(jù)結(jié)構(gòu)，實質(zhì)就是一種可以進行二分查找的有序鏈表。如圖2所示，在跳表的查詢過程中，先查最高層，后查次高層，如此遞推直至第一層確定結(jié)果。如此操作可以有效縮減時間復(fù)雜度。

圖2 跳表結(jié)構(gòu)示意圖Fig.2 Skip List structure diagram

跳表思想融入進NSW算法，即為層狀結(jié)構(gòu)的HNSW算法。該算法貪婪地遍歷來自上層的元素，直到達到局部最小值。之后，切換到較低層，從上層最小值對應(yīng)的低層元素重新開始遍歷。該過程在每一層中重復(fù)。這一結(jié)構(gòu)顯著降低了計算復(fù)雜度。

2.2 回環(huán)候選幀集合

HF-Net提取當(dāng)前圖像的全局特征后，在HNSW圖內(nèi)展開快速檢索，使用余弦距離，比較當(dāng)前特征和臨近特征的相似度。隨即將當(dāng)前全局特征插入進HNSW圖中，重新構(gòu)圖。最后，記錄較高相似度圖像的圖像索引，稱為回環(huán)候選幀集合。

3 回環(huán)候選幀校驗

3.1 基于網(wǎng)格運動統(tǒng)計的打分器

3.2 改進RANSAC算法

傳統(tǒng)RANSAC算法進行圖像匹配時，首先，從樣本點集中隨機采樣多于4個特征點，估計兩張圖像的單應(yīng)矩陣模型參數(shù)；其次，根據(jù)模型計算內(nèi)點的數(shù)目；重復(fù)以上步驟，確定最終的圖像匹配特征點。

以上分析可知，RANSAC 算法迭代次數(shù)多，計算時間長。因此，應(yīng)用一種結(jié)合網(wǎng)格打分器的優(yōu)化RANSAC算法。針對RANSAC隨機選點導(dǎo)致迭代次數(shù)多的問題，首先，將圖像進行網(wǎng)格化。利用網(wǎng)格支持度對網(wǎng)格打分。根據(jù)失效衛(wèi)星數(shù)據(jù)特點，剔除圖像邊界的特征點；根據(jù)網(wǎng)格打分器，剔除分數(shù)較低的網(wǎng)格。利用RANSAC算法，從保留下來的匹配中抽取優(yōu)質(zhì)特征點作為樣本點，再對樣本點進行迭代計算，最終求得圖像的單應(yīng)矩陣及對應(yīng)匹配點。

3.3 確定回環(huán)幀

在本文回環(huán)檢測算法的校驗過程中，當(dāng)前圖像分別與每一個回環(huán)候選幀進行匹配，首先使用運行速度較快的網(wǎng)格打分器進行篩選。若剔除劣質(zhì)點后剩余點不足初始點數(shù)的0.1倍，直接停止匹配校驗，回環(huán)權(quán)重置0，從而防止后續(xù)RANSAC計算浪費計算資源。若剩余點符合條件，則繼續(xù)利用RANSAC進行計算。最后，計算正確匹配對數(shù)占據(jù)初始點數(shù)的百分比，即回環(huán)權(quán)重。權(quán)重最高的圖像幀即為當(dāng)前圖像的最優(yōu)回環(huán)幀。

4 實驗與結(jié)果

本文進行仿真實驗如下：首先，在失效衛(wèi)星圖像上，對比了RANSAC算法以及改進的RANSAC算法的正確率與耗時。其次，在牛津公開數(shù)據(jù)集上，通過與缺乏改進RANSAC校驗的算法對比，說明改進RANSAC校驗在回環(huán)檢測中的有效性；最后，在失效衛(wèi)星數(shù)據(jù)集上，驗證所提方法對光照變化的空間場景具有高適應(yīng)性與穩(wěn)定性。

4.1 圖像匹配校驗算法仿真結(jié)果

HF-Net利用SuperPoint提取特征點。首先，將SuperPoint與流行的ORB算法進行對比。對同一張失效衛(wèi)星圖像提取500個特征點時，SuperPoint耗時110.8 ms，ORB耗時66.5 ms，效率遠低于ORB。但SuperPoint算法在極端光照條件下的穩(wěn)定性遠超ORB算法。具體如圖3所示。圖3(a)為特征點提取示意圖，右側(cè)SuperPoint算法能夠提取更均勻的特征點；圖3(b)為ORB匹配結(jié)果，圖3(c)為SuperPoint匹配結(jié)果，SuperPiont的匹配結(jié)果更準確。

圖3 ORB與SuperPiont對比Fig.3 Comparison of ORB and SuperPoint

為驗證改進RANSAC的性能，抽選三組失效衛(wèi)星圖像，每組包含4張圖片。三組圖像代表失效衛(wèi)星應(yīng)用中可能存在的不同場景或變化：（1）弱紋理的衛(wèi)星模型；（2）光照變化；（3）旋轉(zhuǎn)變化。對三組圖像分別提取500特征點后進行暴力匹配。而后分別使用RANSAC算法和改進算法剔除誤匹配。具體實驗方法為：將每組圖像中的第一幀圖像作為標準圖像，將其后三幀分別與標準圖像進行暴力匹配，而后利用算法剔除誤匹配，計算算法剔除后的匹配正確率和算法耗時。本文實驗采用的電腦處理器型號為i7-11700KF，操作系統(tǒng)為Ubuntu 18.04。

各算法正確率以及平均時間消耗如表1所示。表格中的耗時不包括特征提取與暴力匹配所耗時間，計算五次取平均值。由表中結(jié)果可以看出，在弱紋理的失效衛(wèi)星場景中，改進算法的匹配正確率略高于RANSAC算法，耗時稍有減少。

表1 失效衛(wèi)星圖像的算法匹配結(jié)果Tab.1 Image matching results for failure satellites

而面對光照變化時，改進算法與RANSAC算法的正確率都明顯下降，兩個算法的耗時差距明顯。原因在于，弱光照環(huán)境下暴力匹配獲取的匹配點對質(zhì)量較差。在改進算法中對質(zhì)量較差的點進行了快速篩選，留給后續(xù)RANSAC隨機抽樣的點對量少且更優(yōu)質(zhì)，能夠較快結(jié)束迭代；而傳統(tǒng)RANSAC則需不斷迭代剔除質(zhì)量差的匹配點。由此可見，匹配點的質(zhì)量對RANSAC算法的耗時影響很大，匹配點質(zhì)量好時，RANSAC算法只是耗時略長；質(zhì)量差時，兩算法耗時則有明顯差距。本特征提取與匹配實驗中，改進算法匹配耗時比RANSAC平均減少約6.58 ms，可以使回環(huán)檢測更高效。

4.2 牛津公開數(shù)據(jù)集回環(huán)檢測實驗結(jié)果

為驗證本文回環(huán)算法對不同場景具有高適應(yīng)性，首先使用牛津數(shù)據(jù)集進行算法驗證。該數(shù)據(jù)集包括兩個場景，New College和City Center，以及相應(yīng)的真值文件。數(shù)據(jù)集的每個場景又可分為左右相機拍攝而成的兩組。為了方便表述，將New College場景分割成New College-Left與New College-Right；同理，將City Center場景分割成City Center-Left與City Center-Right。如圖4為四個數(shù)據(jù)集示例圖片，依次為New College-Left、New College-Right、City Center-Left、City Center-Right。

圖4 牛津數(shù)據(jù)集圖片F(xiàn)ig.4 The Oxford dataset images

回環(huán)檢測算法使用準確率P和召回率R對檢測結(jié)果進行評價。準確率P代表算法判斷出的所有回環(huán)中正確回環(huán)所占的比例，召回率R則代表算法檢測出的正確回環(huán)數(shù)與所有正確回環(huán)數(shù)的比值。以此作為回環(huán)檢測的評價指標，將所提方法與BoW算法和HF-Net算法進行對比。BoW算法通過最新版的DBoW3庫進行實現(xiàn)。使用HF-Net算法代指所提方法去掉校驗時的回環(huán)算法，以此來驗證回環(huán)候選幀校驗的有效性。三種算法在四個數(shù)據(jù)集上的Precision-Recall曲線如圖5所示。

圖5 牛津數(shù)據(jù)集回環(huán)實驗結(jié)果對比Fig.5 Results of experiments on the Oxford dataset

準確率是回環(huán)檢測最看重的指標。三種算法在四個數(shù)據(jù)集上100%準確率下的最大召回率如表2所示，其中，所提方法表現(xiàn)均為最優(yōu)，與HF-Net相比，局部特征的加入使得算法性能提升良好。BoW算法需隨場景變化更新詞典庫，且在實際工程使用時，常伴隨圖像增強等針對性操作。因此在本實驗中，BoW算法表現(xiàn)一般。

表2 100%準確率下的最大召回率（單位：%）Tab.2 Maximum recall at 100% precision（Unit:%）

聯(lián)系數(shù)據(jù)集進行分析。如圖4所示，New College-Right中光照變化劇烈；City Center處于白天，City Center-Right中因陽光過于劇烈出現(xiàn)少數(shù)“鏡頭光暈”的現(xiàn)象。在此類場景下，基于深度學(xué)習(xí)提取特征的優(yōu)勢，HF-Net算法100%準確率下的召回率均超過BoW算法。但在總體上，HF-Net算法精度不及所提方法，甚至在New College-Left上遠不及BoW算法。原因即是深度學(xué)習(xí)全局特征缺乏對局部空間位置關(guān)系的敏感，而New College-Left中存在大量不同位置的相似圖片，算法極易發(fā)生誤檢。由此可知，深度學(xué)習(xí)全局特征搭配局部特征圖像校驗是很有必要的。

4.3 空間失效衛(wèi)星數(shù)據(jù)集回環(huán)檢測實驗結(jié)果

利用不同的衛(wèi)星模型與復(fù)雜的照射光源模擬空間環(huán)境，制作失效衛(wèi)星數(shù)據(jù)集，如圖6所示。該數(shù)據(jù)集可分為四個子數(shù)據(jù)集，分別為：衛(wèi)星模型A以5 °/s角速度勻速旋轉(zhuǎn)；衛(wèi)星模型A以10 °/s的角速度勻速旋轉(zhuǎn)；衛(wèi)星模型A以20 °/s的角速度勻速旋轉(zhuǎn)；衛(wèi)星模型B以10 °/s角速度旋轉(zhuǎn)。

圖6 數(shù)據(jù)集圖片 Fig.6 Dataset images

因失效衛(wèi)星穩(wěn)定自旋，使用失效衛(wèi)星旋轉(zhuǎn)周數(shù)來評價回環(huán)檢測的效果，具體方法如下：對每一個子數(shù)據(jù)集，統(tǒng)計在失效衛(wèi)星最后一周的旋轉(zhuǎn)中，平均每幀圖像應(yīng)檢測到的回環(huán)幀數(shù)目，以及所提方法與BoW算法平均檢測到的回環(huán)幀數(shù)目。實驗將檢測結(jié)果的準確性放在首位，盡可能減少錯檢誤檢，結(jié)果如表3所示。

表3 失效衛(wèi)星數(shù)據(jù)集回環(huán)檢測結(jié)果Tab.3 Results of the failure satellites dataset

BoW需利用預(yù)訓(xùn)練的詞典庫獲取詞袋向量。預(yù)訓(xùn)練的圖像數(shù)據(jù)場景越多，詞典庫越豐富，BoW效果越好。針對失效衛(wèi)星的應(yīng)用場景，本實驗利用1000張失效衛(wèi)星模型圖片（其中基于衛(wèi)星模型A的圖片占比90%），有針對性地訓(xùn)練了BoW詞典庫，生成了相應(yīng)的詞典壓縮文件。利用BoW進行回環(huán)檢測時，需提前加載該文件。實驗分析可知，BoW算法隨模型角速度的增加效果變差。此類圖像中普遍存在運動模糊與強反光情況，導(dǎo)致提取的特征點質(zhì)量較差。而BoW算法對模型A 10 °/s數(shù)據(jù)集的檢測結(jié)果要比模型B略好，也進一步說明了BoW對預(yù)訓(xùn)練詞典庫的依賴。

所提方法在無預(yù)訓(xùn)練的條件下取得較好的檢測結(jié)果。在處理衛(wèi)星模型A的20 °/s數(shù)據(jù)集時，進行五次實驗取平均值得到結(jié)果：所提方法對單獨圖像幀進行檢索對比的平均時間48.8 ms，完成全部回環(huán)檢測的時間則為192.6 s（包括SuperPoint特征提?。oW算法則為143.9 ms和253.8 s（包括ORB特征提取，不包括詞典庫預(yù)訓(xùn)練）。所提方法在準確的同時兼顧了處理速度，和BoW算法相比縮減時間24.1%左右。

利用所提方法粗略計算數(shù)據(jù)集角速度，說明所提方法的準確性。具體方法為：對某一圖像Ip，與Ip相近卻不相鄰的圖像Il，兩幀的時間戳分別為tp，tl。若圖像Ip與Il的回環(huán)權(quán)重高于自主設(shè)定的閾值，則可計算該段角速度w=360/(tp-tl)。由此，針對以上五個失效衛(wèi)星數(shù)據(jù)集，在每個數(shù)據(jù)集的后半部分，隨機抽取五張圖像。記錄每張圖像的時間戳tp；在每張圖像的回環(huán)候選幀集合中，挑選合適的圖像，記錄時間戳tl，代入公式求解角速度。計算五張圖像的結(jié)果并求取平均值，可獲得五個失效衛(wèi)星數(shù)據(jù)集的角速度。本文所提方法求解為：5.04 °/s、8.05 °/s、10.02 °/s、12.04 °/s和20.09 °/s。

5 結(jié)論

本文提出了一種基于改進RANSAC校驗的空間失效衛(wèi)星回環(huán)檢測方法。實驗結(jié)果表明：1）回環(huán)候選幀校驗在回環(huán)檢測中很有必要，且改進算法耗時比RANSAC算法平均減少6.58 ms；2）在牛津數(shù)據(jù)集上，本方法與無校驗的方法對比，100%準確率下的最大召回率提升了30.6%，說明改進RANSAC校驗在回環(huán)檢測中的有效性；3）在失效衛(wèi)星數(shù)據(jù)集上，驗證了本方法對光照變化的空間場景具有高適應(yīng)性與穩(wěn)定性，且和BoW算法相比縮減時間24.1%。