基于局部敏感哈希的導航星庫快速搜索算法

朱海龍, 梁斌, 張濤

(清華大學 自動化系, 北京 100084)

星敏感器具有姿態測量精度高、自主工作能力強和可靠性高等優點，已經成為各類航天器首選姿態測量設備。根據工作場景不同，星敏感器的工作模式可以分為全天球自主工作模式和星跟蹤模式2種[1]。在初次進入工作狀態或者故障恢復后，星敏感器沒有任何先驗姿態信息，進入全天球自主工作模式。此時星敏感器通過其光學系統獲取星圖，計算出星點在星圖中位置，然后構造出識別模式，并且與導航星數據庫中存儲的識別模式進行搜索匹配，識別出星圖中的導航星，進而確定航天器瞬時姿態信息。在得到先驗姿態信息后，星敏感器就進入星跟蹤工作模式，此時星敏感器可以利用在全天球自主工作模式下獲取的先驗姿態信息和航天器的運動方程，快速更新航天器姿態信息。可以看出，如何在全天球自主工作模式下準確快速地識別出導航星是星敏感器穩定可靠工作的關鍵。

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

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

1 導航星庫構建

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

1.1 有序星點集星圖識別模式

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

圖1 有序星點集星圖識別模式

在選定主星點s0后,利用s0近鄰算法,選取s0(s0小于星敏感器視場角的一半)范圍內到星點s0最近的s0顆星,選擇s0顆星中距離星點s0最近的星為參考星點s0。以s0為起點,按照順時針順序對s0顆星排序,就可以得到星點s0的有序星點集s0。對于s0中每個星點s0,都可以用星點之間的角距表示其特征s0。可以分為以下幾種情況:

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

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

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

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

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

1.2 星圖識別數據庫

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

圖2 有序星點集星圖識別數據庫

根據1.1節對有序星點集星圖識別模式的定義,星角距存在重復現象。因此,為了降低星圖識別數據庫的存儲量,每個星點的有序星點集模式特征F(i)的存儲格式如圖3所示。其中,k表示主星點s的最近鄰星點數量,Di(i=1,…,k)表示每顆近鄰星點的信息,包含星編號、到主星點的角距e0i和到下一顆近鄰星點的角距ei,i+1。

圖3 單星點有序星點集識別模式存儲格式

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

星圖識別的本質是在星圖識別數據庫中搜索匹配星圖中構造的識別模式,由于導航星數量眾多且每個星圖識別模式中包含多個星點特征,因此需要設計快速搜索算法提高星圖識別速度。此外,由于實際星圖中獲得的識別模式存在誤差,因此可以把星圖識別模式在星圖識別數據庫內的搜索匹配過程認為是最近鄰搜索問題。本文提出適用于星圖識別數據庫快速搜索的局部敏感哈希算法,可以在存在誤差的情況下,快速搜索匹配星圖識別模式,進而識別出導航星,提高星圖識別速度。

2.1 星圖識別局部敏感哈希映射原理

(1)

式中，n′和n分別表示實際角距與理想角距對應的量化值,則當n′∈{n-1,n,n+1}時,就可以認為該星角距匹配成功。假設有N個角距同時匹配成功時可以認為該星圖識別模式匹配成功,則在星圖識別數據庫中就會存在有3N個星角距量化值組合判定星圖識別模式匹配成功。

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

2.2 哈希表建立過程

根據所需要識別的角距數量的不同,可以把星圖識別數據庫中的星圖識別模式組合成3N個可以匹配的識別模式。圖5給出了利用局部敏感哈希原理對星圖識別數據庫內識別模式的哈希表建立過程,具體的實現過程如下:

圖5 星圖識別數據庫哈希表建立過程

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

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

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

4) 為了壓縮存儲空間,把Arr[N]i中的數利用CRC32轉換為32位整數Hi

5) 采用整數哈希函數對Hi進行散列,每個哈希表key值對應的value是有序星點集模式的中心星點對應的星編號的集合,即

(2)

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

按照上述哈希表的建立過程,對每個導航星對應的星圖識別模式逐個轉換,就可以建立星圖識別數據庫對應的哈希表。

2.3 哈希表搜索過程

建立了星圖識別數據庫以及對應的哈希表之后,就可以進行星圖識別。在得到實際星圖后,通過星點質心定位算法確定星圖中恒星的位置,構造每個星點的有序星點集識別模式,然后按照局部敏感哈希映射原理,得到有序星點集識別模式對應的哈希值,在星圖識別數據庫內搜索匹配,完成星圖識別。具體的哈希表搜索過程如圖6所示。

圖6 哈希表搜索過程

具體的搜索過程可以表示為:

1) 在星圖中構造有序星點集模式,并選擇其中N個角距作為搜索特征;

2) 以Δ為基準量化N個選定角距,然后按照順序存入對應的數組Arr[N]′中;

3) 把Arr[N]′利用CRC32方式編碼壓縮,得到對應的32位整數H′;

4) 采用建立哈希表時使用的整數哈希函數對H′進行散列,得到對應的哈希值key′;

5) 查找導航星數據庫哈希表,是否存在與key′對應的哈希值。若不存在,則識別失敗。如果存在,檢查此哈希值對應的星編號集合是否唯一,如果唯一,則星圖識別成功;如果不唯一,則在對應的集合內進行線性搜索,進行星圖識別。

在建立的星圖識別數據庫哈希表中,每一個星圖識別模式都存在多個哈希值。通過建立這種“一對多”的星圖識別方式,可以在星圖識別模式存在誤差的情況下,快速匹配星圖識別模式,識別出導航星。

3 仿真實驗結果與分析

3.1 仿真條件

仿真實驗中選擇Sky2000星表中亮度高于7.0等星作為導航星,共有11 003顆導航星,建立有序星點集識別模式的半徑為r=5°,仿真計算機的CPU為Intel Core i7-4770MQ,仿真環境為Microsoft VS2008,其他仿真參數如表1所示。

表1 仿真實驗參數

通過蒙特卡羅方法隨機生成1 000個視場指向并仿真星圖。根據分析可知,角距誤差限Δ和需要識別的角距數量N是影響哈希表最主要因素。根據仿真條件可知,單個像元對應的角距為:

(3)

仿真中以像素對應的角距為基準進行量化。在哈希表中,如果哈希值對應的主星點編號不唯一,定義此哈希值存在沖突,定義存在沖突的哈希值數量與占總哈希值數量的比值為沖突率。

3.2 仿真結果

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

表2 Δ=epixel條件下不同角距數量的仿真結果

表3 Δ=2epixel條件下不同角距數量的仿真結果

表4 Δ=3epixel條件下不同角距數量的仿真結果

通過仿真結果可以看出:

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

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

3.3 仿真結果分析

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

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

表5 哈希搜索算法性能對比分析

4 結 論

星敏感器是以恒星為探測目標的高精度姿態測量設備,具備獨獨立自主工作能力強和可靠性高等有點,已經廣泛應用在各類航天器。其中星圖識別是影響星敏感器獲取初始姿態速度的關鍵步驟。基于傳統哈希算法的星圖識別算法是目前已有算法中識別速度最快的,為進一步提高星圖識別速度,本文提出基于局部敏感哈希的快速星圖識別算法,在考慮星圖識別誤差的影響情況下,建立星角距的局部敏感映射關系,以星圖識別角距誤差限為基準,量化星圖識別模式中角距,利用整數哈希函數建立“一對多”的星圖識別模式哈希表,可以通過哈希表直接快速匹配星圖識別識別模式,提高星圖識別速度。總體上講,本文提出的基于局部敏感哈希的快速星圖識別算法具有以下特點:

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

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

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