基于局部敏感哈希的導(dǎo)航星庫(kù)快速搜索算法

朱海龍, 梁斌, 張濤

(清華大學(xué) 自動(dòng)化系, 北京 100084)

星敏感器具有姿態(tài)測(cè)量精度高、自主工作能力強(qiáng)和可靠性高等優(yōu)點(diǎn)，已經(jīng)成為各類航天器首選姿態(tài)測(cè)量設(shè)備。根據(jù)工作場(chǎng)景不同，星敏感器的工作模式可以分為全天球自主工作模式和星跟蹤模式2種[1]。在初次進(jìn)入工作狀態(tài)或者故障恢復(fù)后，星敏感器沒(méi)有任何先驗(yàn)姿態(tài)信息，進(jìn)入全天球自主工作模式。此時(shí)星敏感器通過(guò)其光學(xué)系統(tǒng)獲取星圖，計(jì)算出星點(diǎn)在星圖中位置，然后構(gòu)造出識(shí)別模式，并且與導(dǎo)航星數(shù)據(jù)庫(kù)中存儲(chǔ)的識(shí)別模式進(jìn)行搜索匹配，識(shí)別出星圖中的導(dǎo)航星，進(jìn)而確定航天器瞬時(shí)姿態(tài)信息。在得到先驗(yàn)姿態(tài)信息后，星敏感器就進(jìn)入星跟蹤工作模式，此時(shí)星敏感器可以利用在全天球自主工作模式下獲取的先驗(yàn)姿態(tài)信息和航天器的運(yùn)動(dòng)方程，快速更新航天器姿態(tài)信息?？梢钥闯?，如何在全天球自主工作模式下準(zhǔn)確快速地識(shí)別出導(dǎo)航星是星敏感器穩(wěn)定可靠工作的關(guān)鍵。

目前，已經(jīng)有許多全天球自主工作模式下的星圖識(shí)別算法提出，典型的算法有三角形識(shí)別算法[2]、Pyramid識(shí)別算法[3]和柵格識(shí)別算法[4]等。在這些算法及其改進(jìn)算法中，導(dǎo)航星數(shù)據(jù)庫(kù)的搜索速度是決定星圖識(shí)別算法效率的核心因素。Liebe提出的三角形算法中選用"邊角邊"識(shí)別模式，直接建立星圖識(shí)別數(shù)據(jù)庫(kù)，通過(guò)直接遍歷搜索進(jìn)行星圖識(shí)別[5]。由于三角形識(shí)別模式維度較低，在導(dǎo)航星數(shù)量多的情況下會(huì)導(dǎo)致誤匹配率高和識(shí)別速度慢。為提高星圖識(shí)別的魯棒性，Mortari等人提出Pyramid星圖識(shí)別算法，通過(guò)增加一個(gè)角距來(lái)判斷星圖識(shí)別的唯一性。為了提高星圖識(shí)別速度，Mortari等人對(duì)星角距升序排列，提出k-vector區(qū)域搜索算法[6]，該算法的搜索速度比遍歷查找算法提高了10～50倍。張廣軍等人提出基于徑向和環(huán)向特征的星圖識(shí)別算法[7]，該算法在星點(diǎn)位置誤差1個(gè)像素的情況下識(shí)別成功率達(dá)到97.57%，并且通過(guò)線性數(shù)據(jù)庫(kù)搜索方法，提高了星圖識(shí)別速度。江潔等人對(duì)張廣軍等人提出算法進(jìn)行改進(jìn)[8]，提出冗余徑向和環(huán)向特征識(shí)別模式，通過(guò)冗余編碼方式，降低星等和星點(diǎn)位置噪聲對(duì)星圖識(shí)別的影響，但是在識(shí)別速度方面略慢于張廣軍等人提出的算法。楊君等人通過(guò)2級(jí)壓縮技術(shù)將導(dǎo)航星分布的二維數(shù)組壓縮成一維數(shù)組，然后建立Hash映射實(shí)現(xiàn)導(dǎo)航星表快速搜索，實(shí)現(xiàn)了導(dǎo)航星表的無(wú)冗余存儲(chǔ)，提高導(dǎo)航星的搜索速度[9]。張磊等人在改進(jìn)三角形識(shí)別算法過(guò)程中，用哈希方法散列星角距和相對(duì)星等差，提高了識(shí)別速度[10]。熊雪等人在研究多視場(chǎng)星圖識(shí)別技術(shù)中，利用哈希查找的方法快速訪問(wèn)分塊存儲(chǔ)的星對(duì)角距，識(shí)別速度提高了11倍左右[11]。Rao等人利用星角距值在坐標(biāo)系 軸的投影建立哈希函數(shù)，進(jìn)而提高星角距數(shù)據(jù)庫(kù)的搜索速度[12]。郭磊利用雙哈希表方式存儲(chǔ)和訪問(wèn)導(dǎo)航星數(shù)據(jù)庫(kù)，利用拉鏈法處理沖突，降低哈希表沖突率，并提高了搜索速度[13]。利用哈希表建立和訪問(wèn)導(dǎo)航星數(shù)據(jù)庫(kù)，時(shí)間復(fù)雜度能夠達(dá)到O(1)，明顯優(yōu)于遍歷查找方法、二分查找方法和k-vector區(qū)域搜索方法，這些方法的時(shí)間復(fù)雜度分別是O(n),O(log(n))和O(k)。但是哈希搜索算法是一種典型的空間換時(shí)間的方法，導(dǎo)航星數(shù)據(jù)庫(kù)的存儲(chǔ)量會(huì)隨著訪問(wèn)時(shí)間的降低而快速增加。因此如何在提高導(dǎo)航星數(shù)據(jù)庫(kù)搜索速度的同時(shí)盡可能降低導(dǎo)航星數(shù)據(jù)庫(kù)的存儲(chǔ)容量，是本文主要的研究方向。

由于星圖成像存在各種噪聲，在已有的星圖識(shí)別算法中，通常是建立“一對(duì)一”的星圖識(shí)別模式數(shù)據(jù)庫(kù)，即在星圖識(shí)別數(shù)據(jù)庫(kù)中有且僅有一個(gè)識(shí)別模式與星圖中構(gòu)造的識(shí)別模式對(duì)應(yīng)匹配。因此，這種方式建立的數(shù)據(jù)庫(kù)在受到噪聲影響時(shí)，不僅影響星圖識(shí)別成功率，還影響星圖識(shí)別速度。本文選用有序星點(diǎn)集作為星圖識(shí)別模式，考慮角距誤差對(duì)星圖識(shí)別速度的影響，提出基于局部敏感哈希的快速星圖識(shí)別算法，以角距誤差限為基準(zhǔn)對(duì)星圖識(shí)別數(shù)據(jù)庫(kù)中星角距進(jìn)行量化，建立實(shí)際角距與待匹配角距之間的映射關(guān)系，利用整數(shù)哈希函數(shù)散列得到的映射值，把每個(gè)識(shí)別模式的中心星點(diǎn)對(duì)應(yīng)的編號(hào)對(duì)應(yīng)于多個(gè)哈希值，建立“一對(duì)多”的星圖識(shí)別模式數(shù)據(jù)庫(kù)，即在星圖識(shí)別數(shù)據(jù)庫(kù)中，存在多個(gè)識(shí)別模式與星圖中構(gòu)造的識(shí)別模式匹配，可以有效提高星圖識(shí)別的速度。

1 導(dǎo)航星庫(kù)構(gòu)建

星圖識(shí)別模式及其數(shù)據(jù)庫(kù)是影響搜索速度的基礎(chǔ)因素，本文選用有序星點(diǎn)集(ordered star points set,OSPS)作為星圖識(shí)別模式，建立星圖識(shí)別數(shù)據(jù)庫(kù)。

1.1 有序星點(diǎn)集星圖識(shí)別模式

星點(diǎn)s0的有序星點(diǎn)集星圖識(shí)別模式如圖1所示,定義pat(s0,S,Fi)(i=0,…,k)為星點(diǎn)s0的有序星點(diǎn)集星圖識(shí)別模式,其中s0為主星點(diǎn),S為主星點(diǎn)s0的有序星點(diǎn)集,Fi(i=0,…,k)為S中每個(gè)星點(diǎn)的特征。

圖1 有序星點(diǎn)集星圖識(shí)別模式

在選定主星點(diǎn)s0后,利用s0近鄰算法,選取s0(s0小于星敏感器視場(chǎng)角的一半)范圍內(nèi)到星點(diǎn)s0最近的s0顆星,選擇s0顆星中距離星點(diǎn)s0最近的星為參考星點(diǎn)s0。以s0為起點(diǎn),按照順時(shí)針順序?qū)0顆星排序,就可以得到星點(diǎn)s0的有序星點(diǎn)集s0。對(duì)于s0中每個(gè)星點(diǎn)s0,都可以用星點(diǎn)之間的角距表示其特征s0?？梢苑譃橐韵聨追N情況:

1) 主星點(diǎn)s0的特征為F0={e0,i}(i=1,…,k);

2) 參考星點(diǎn)s1的特征為F1={ek,1,e0,1,e1,2};

3) 星點(diǎn)si(2≤i≤k-1)的特征為Fi={ei-1,i,e0,i,ei,i+1}

4) 星點(diǎn)sk的特征為Fk={ek-1,k,e0,k,ek,1}

其中,e表示星點(diǎn)之間的距離星角距,下腳標(biāo)表示星點(diǎn)的編號(hào)。按照星點(diǎn)有序集S中星點(diǎn)的順序把每個(gè)星點(diǎn)的特征Fi組合起來(lái),就可以得到星點(diǎn)s0的有序星點(diǎn)集星圖識(shí)別模式pat(s0,S,Fi)(i=0,…,k)。

1.2 星圖識(shí)別數(shù)據(jù)庫(kù)

在星敏感器光電系統(tǒng)探測(cè)范圍內(nèi),按照一定原則篩選后的恒星是可用于星圖識(shí)別的導(dǎo)航星。假設(shè)可用于星圖識(shí)別的導(dǎo)航星的數(shù)量為M,按照恒星編號(hào)順序排列后,可以得到星敏感器的星圖識(shí)別數(shù)據(jù)庫(kù)如圖2所示。其中第1列為主星點(diǎn)的編號(hào),第2列和第3列分別是主星點(diǎn)的赤經(jīng)和赤緯,第4列為主星點(diǎn)的有序星點(diǎn)集模式特征F(i)(i=1,…,M)。

圖2 有序星點(diǎn)集星圖識(shí)別數(shù)據(jù)庫(kù)

根據(jù)1.1節(jié)對(duì)有序星點(diǎn)集星圖識(shí)別模式的定義,星角距存在重復(fù)現(xiàn)象。因此,為了降低星圖識(shí)別數(shù)據(jù)庫(kù)的存儲(chǔ)量,每個(gè)星點(diǎn)的有序星點(diǎn)集模式特征F(i)的存儲(chǔ)格式如圖3所示。其中,k表示主星點(diǎn)s的最近鄰星點(diǎn)數(shù)量,Di(i=1,…,k)表示每顆近鄰星點(diǎn)的信息,包含星編號(hào)、到主星點(diǎn)的角距e0i和到下一顆近鄰星點(diǎn)的角距ei,i+1。

圖3 單星點(diǎn)有序星點(diǎn)集識(shí)別模式存儲(chǔ)格式

2 局部敏感哈希快速搜索算法

星圖識(shí)別的本質(zhì)是在星圖識(shí)別數(shù)據(jù)庫(kù)中搜索匹配星圖中構(gòu)造的識(shí)別模式,由于導(dǎo)航星數(shù)量眾多且每個(gè)星圖識(shí)別模式中包含多個(gè)星點(diǎn)特征,因此需要設(shè)計(jì)快速搜索算法提高星圖識(shí)別速度。此外,由于實(shí)際星圖中獲得的識(shí)別模式存在誤差,因此可以把星圖識(shí)別模式在星圖識(shí)別數(shù)據(jù)庫(kù)內(nèi)的搜索匹配過(guò)程認(rèn)為是最近鄰搜索問(wèn)題。本文提出適用于星圖識(shí)別數(shù)據(jù)庫(kù)快速搜索的局部敏感哈希算法,可以在存在誤差的情況下,快速搜索匹配星圖識(shí)別模式,進(jìn)而識(shí)別出導(dǎo)航星,提高星圖識(shí)別速度。

2.1 星圖識(shí)別局部敏感哈希映射原理

(1)

式中，n′和n分別表示實(shí)際角距與理想角距對(duì)應(yīng)的量化值,則當(dāng)n′∈{n-1,n,n+1}時(shí),就可以認(rèn)為該星角距匹配成功。假設(shè)有N個(gè)角距同時(shí)匹配成功時(shí)可以認(rèn)為該星圖識(shí)別模式匹配成功,則在星圖識(shí)別數(shù)據(jù)庫(kù)中就會(huì)存在有3N個(gè)星角距量化值組合判定星圖識(shí)別模式匹配成功。

圖4 局部敏感哈希映射原理示意圖

2.2 哈希表建立過(guò)程

根據(jù)所需要識(shí)別的角距數(shù)量的不同,可以把星圖識(shí)別數(shù)據(jù)庫(kù)中的星圖識(shí)別模式組合成3N個(gè)可以匹配的識(shí)別模式。圖5給出了利用局部敏感哈希原理對(duì)星圖識(shí)別數(shù)據(jù)庫(kù)內(nèi)識(shí)別模式的哈希表建立過(guò)程,具體的實(shí)現(xiàn)過(guò)程如下:

圖5 星圖識(shí)別數(shù)據(jù)庫(kù)哈希表建立過(guò)程

1) 選擇星圖識(shí)別的角距誤差限Δ和需要識(shí)別的角距數(shù)量N;

2) 在星圖識(shí)別模式中,選擇需要量化的N個(gè)角距,并且按照公式(1)進(jìn)行量化,得到量化后的角距值n1,…,ni,…,nN;

3) 把每一個(gè)角距量化值集合{ni-1,ni,ni+1}按照角距選擇順序排列組合,然后以16位形式存儲(chǔ)到數(shù)組Arr[N]i中;

4) 為了壓縮存儲(chǔ)空間,把Arr[N]i中的數(shù)利用CRC32轉(zhuǎn)換為32位整數(shù)Hi

5) 采用整數(shù)哈希函數(shù)對(duì)Hi進(jìn)行散列,每個(gè)哈希表key值對(duì)應(yīng)的value是有序星點(diǎn)集模式的中心星點(diǎn)對(duì)應(yīng)的星編號(hào)的集合,即

(2)

在角距量化的過(guò)程中,每一個(gè)角距通過(guò)公式(1)轉(zhuǎn)換為一個(gè)16位的整數(shù),在選擇N個(gè)量化角距的情況下,量化后的識(shí)別模式需要占用的存儲(chǔ)空間為16×N位,因此為了壓縮存儲(chǔ)空間,本文采用了CRC32編碼的方式,把量化后的識(shí)別模式Arr[N]i轉(zhuǎn)換成32位的整數(shù)Hi。然后,本文引用STLport 5.2版本中的整數(shù)哈希函數(shù),把由識(shí)別模式轉(zhuǎn)換得到的32位整數(shù)Hi散列到哈希表中。

按照上述哈希表的建立過(guò)程,對(duì)每個(gè)導(dǎo)航星對(duì)應(yīng)的星圖識(shí)別模式逐個(gè)轉(zhuǎn)換,就可以建立星圖識(shí)別數(shù)據(jù)庫(kù)對(duì)應(yīng)的哈希表。

2.3 哈希表搜索過(guò)程

建立了星圖識(shí)別數(shù)據(jù)庫(kù)以及對(duì)應(yīng)的哈希表之后,就可以進(jìn)行星圖識(shí)別。在得到實(shí)際星圖后,通過(guò)星點(diǎn)質(zhì)心定位算法確定星圖中恒星的位置,構(gòu)造每個(gè)星點(diǎn)的有序星點(diǎn)集識(shí)別模式,然后按照局部敏感哈希映射原理,得到有序星點(diǎn)集識(shí)別模式對(duì)應(yīng)的哈希值,在星圖識(shí)別數(shù)據(jù)庫(kù)內(nèi)搜索匹配,完成星圖識(shí)別。具體的哈希表搜索過(guò)程如圖6所示。

圖6 哈希表搜索過(guò)程

具體的搜索過(guò)程可以表示為:

1) 在星圖中構(gòu)造有序星點(diǎn)集模式,并選擇其中N個(gè)角距作為搜索特征;

2) 以Δ為基準(zhǔn)量化N個(gè)選定角距,然后按照順序存入對(duì)應(yīng)的數(shù)組Arr[N]′中;

3) 把Arr[N]′利用CRC32方式編碼壓縮,得到對(duì)應(yīng)的32位整數(shù)H′;

4) 采用建立哈希表時(shí)使用的整數(shù)哈希函數(shù)對(duì)H′進(jìn)行散列,得到對(duì)應(yīng)的哈希值key′;

5) 查找導(dǎo)航星數(shù)據(jù)庫(kù)哈希表,是否存在與key′對(duì)應(yīng)的哈希值。若不存在,則識(shí)別失敗。如果存在,檢查此哈希值對(duì)應(yīng)的星編號(hào)集合是否唯一,如果唯一,則星圖識(shí)別成功;如果不唯一,則在對(duì)應(yīng)的集合內(nèi)進(jìn)行線性搜索,進(jìn)行星圖識(shí)別。

在建立的星圖識(shí)別數(shù)據(jù)庫(kù)哈希表中,每一個(gè)星圖識(shí)別模式都存在多個(gè)哈希值。通過(guò)建立這種“一對(duì)多”的星圖識(shí)別方式,可以在星圖識(shí)別模式存在誤差的情況下,快速匹配星圖識(shí)別模式,識(shí)別出導(dǎo)航星。

3 仿真實(shí)驗(yàn)結(jié)果與分析

3.1 仿真條件

仿真實(shí)驗(yàn)中選擇Sky2000星表中亮度高于7.0等星作為導(dǎo)航星,共有11 003顆導(dǎo)航星,建立有序星點(diǎn)集識(shí)別模式的半徑為r=5°,仿真計(jì)算機(jī)的CPU為Intel Core i7-4770MQ,仿真環(huán)境為Microsoft VS2008,其他仿真參數(shù)如表1所示。

表1 仿真實(shí)驗(yàn)參數(shù)

通過(guò)蒙特卡羅方法隨機(jī)生成1 000個(gè)視場(chǎng)指向并仿真星圖。根據(jù)分析可知,角距誤差限Δ和需要識(shí)別的角距數(shù)量N是影響哈希表最主要因素。根據(jù)仿真條件可知,單個(gè)像元對(duì)應(yīng)的角距為:

(3)

仿真中以像素對(duì)應(yīng)的角距為基準(zhǔn)進(jìn)行量化。在哈希表中,如果哈希值對(duì)應(yīng)的主星點(diǎn)編號(hào)不唯一,定義此哈希值存在沖突,定義存在沖突的哈希值數(shù)量與占總哈希值數(shù)量的比值為沖突率。

3.2 仿真結(jié)果

星角距誤差限和選擇匹配的星角距數(shù)量是影響本文算法的主要參數(shù)。利用本文提出的算法,對(duì)仿真生成的1 000幅星圖進(jìn)行識(shí)別,可以得到在不同角距誤差限和選用不同角距匹配數(shù)量情況下的結(jié)果如表2～表4所示。

表2 Δ=epixel條件下不同角距數(shù)量的仿真結(jié)果

表3 Δ=2epixel條件下不同角距數(shù)量的仿真結(jié)果

表4 Δ=3epixel條件下不同角距數(shù)量的仿真結(jié)果

通過(guò)仿真結(jié)果可以看出:

1) 在同樣星角距誤差限的情況時(shí),選用星角距的數(shù)量為N=1和N=2時(shí),雖然哈希表占用存儲(chǔ)空間比較低,但是哈希表的沖突率比較高,最大沖突數(shù)量也比較高。在N=3和N=4時(shí),哈希表的沖突比較低,每個(gè)哈希值最大沖突數(shù)量為3,平均查找次數(shù)基本接近與1,但哈希表占用存儲(chǔ)空間比較大;

2) 在選擇同樣匹配星角距數(shù)量情況下,隨著星角距誤差限的增大,哈希表沖突率、最大沖突數(shù)量、平均查找次數(shù)增多、哈希表占用的存儲(chǔ)空間以及平均星圖識(shí)別雖然都是呈現(xiàn)遞增的趨勢(shì),但是影響不顯著。

3.3 仿真結(jié)果分析

通過(guò)仿真結(jié)果可以看出,角距誤差限Δ在不同的情況下,對(duì)搜索速度結(jié)果影響不顯著。因此本文提出算法可以提高星圖識(shí)別對(duì)角距誤差限的容忍能力和魯棒性。在選擇角距數(shù)量N=1和N=2時(shí),由于存在比較高的沖突率和最大沖突數(shù)量,不適合選擇建立哈希表。在N=4的情況下,哈希表的沖突率和最大沖突數(shù)量都是最低的,但對(duì)應(yīng)的哈希表占用存儲(chǔ)空間也非常大。雖然在N=3的情況下建立哈希表的沖突率相對(duì)于N=4的情況下略高,但是最大沖突數(shù)、平均查找次數(shù)以及平均星圖識(shí)別時(shí)間都非常接近,而且哈希表占用的存儲(chǔ)空間僅為N=4的情況下的30%,因此選擇N=3是比較適合建立導(dǎo)航星快速搜索哈希表。

本文提出的局部敏感哈希搜索算法的時(shí)間復(fù)雜度為O(1),與傳統(tǒng)哈希算法相同。但是傳統(tǒng)算法建立的是星圖識(shí)別模式中角距對(duì)應(yīng)的哈希表,因此對(duì)整個(gè)星圖識(shí)別模式匹配過(guò)程,至少需要完成多個(gè)角距的搜索匹配。本文提出算法則需要完成一次搜索就可以完成星圖識(shí)別模式的匹配。雖然本文提出算法在時(shí)間復(fù)雜度上與傳統(tǒng)哈希算法一樣都是O(1),但是在星圖識(shí)別過(guò)程中,本文提出算法的識(shí)別速度優(yōu)于傳統(tǒng)哈希算法。在星圖識(shí)別模式中需要匹配角距數(shù)量N=3的情況下,本文搜索算法與傳統(tǒng)哈希算法的對(duì)比結(jié)果如表5所示。

表5 哈希搜索算法性能對(duì)比分析

4 結(jié) 論

星敏感器是以恒星為探測(cè)目標(biāo)的高精度姿態(tài)測(cè)量設(shè)備,具備獨(dú)獨(dú)立自主工作能力強(qiáng)和可靠性高等有點(diǎn),已經(jīng)廣泛應(yīng)用在各類航天器。其中星圖識(shí)別是影響星敏感器獲取初始姿態(tài)速度的關(guān)鍵步驟?；趥鹘y(tǒng)哈希算法的星圖識(shí)別算法是目前已有算法中識(shí)別速度最快的,為進(jìn)一步提高星圖識(shí)別速度,本文提出基于局部敏感哈希的快速星圖識(shí)別算法,在考慮星圖識(shí)別誤差的影響情況下,建立星角距的局部敏感映射關(guān)系,以星圖識(shí)別角距誤差限為基準(zhǔn),量化星圖識(shí)別模式中角距,利用整數(shù)哈希函數(shù)建立“一對(duì)多”的星圖識(shí)別模式哈希表,可以通過(guò)哈希表直接快速匹配星圖識(shí)別識(shí)別模式,提高星圖識(shí)別速度?？傮w上講,本文提出的基于局部敏感哈希的快速星圖識(shí)別算法具有以下特點(diǎn):

1) 雖然本文提出算法的時(shí)間復(fù)雜度與傳統(tǒng)哈希算法相同,但是在需要匹配同樣星角距數(shù)量情況下,本文提出算法的識(shí)別速度比傳統(tǒng)哈希算法快3.4倍左右,哈希表占用內(nèi)存量約為傳統(tǒng)哈希算法1.3倍;

2) 本文提出快速星圖識(shí)別算法在識(shí)別速度方面有很好的魯棒性,受到星角距誤差影響比較小;

3) 考慮工程應(yīng)用的情況,可以選擇星角距誤差限為1個(gè)像素對(duì)應(yīng)角距,角距數(shù)量N=3,此時(shí)星圖識(shí)別過(guò)程中哈希表的沖突率為0.74%,平均搜索次數(shù)為1.007 4,星圖平均識(shí)別時(shí)間22 μs,哈希表存儲(chǔ)容量904 kB。