低存儲資源開銷的多路快速星點質心提取方法

于文波， 江潔

(北京航空航天大學儀器科學與光電工程學院， 北京 100083)

星敏感器通過對視場內捕獲的恒星與內置導航星庫中的參考恒星進行匹配，進而確定載體姿態，是目前已知的最高精度姿態測量儀器[1-3]，在各類航天飛行器中獲得了廣泛應用[4-7]。星敏感器的信息處理過程主要包括星圖星點提取、星圖識別以及姿態解算3個階段。其中，星點提取是指在星圖中將成像星點的位置信息準確有效地提取出來，這是星敏感器后續工作的基礎。

目前，星點提取方法主要包括擬合法和質心法2類[8-9]。擬合法[10-11]將感光面上的成像近似看作高斯分布，然后利用高斯曲面對灰度分布進行擬合，獲得的高斯能量中心即為星點光斑的中心。但是上述方法均較為復雜，有些改進算法[12]還需要對星圖進行2次掃描才能完成高精度的星點提取，因此這類方法不適用于快速星點提取場合。傳統質心法[13]結構簡單，易于實現，因此獲得了廣泛的應用。但是，這種方法對噪聲較為敏感，且僅適用于規則形狀星點的質心提取。針對傳統質心法對噪聲敏感的問題，魏新國等[8]分析指出，帶閾值的質心法具有較高的定位精度和抗噪能力。樊巧云和張廣軍[14]在傳統質心法的基礎上，提出了一種簡單有效的抗單點像素噪聲的質心定位方法，并在現場可編程門陣列(FPGA)硬件系統上予以實現，取得了良好的效果。Wang等[15]提出了一種動態等價樹結構記錄并完成星點連通域融合的方法，該方法能夠有效提取不規則形狀星點的質心，從而提高了質心法的魯棒性。總之，質心法及其各種改進算法由于具有精度高、算法簡單、實時性好等優勢，因而成為星敏感器領域廣泛采用的星點提取方法。

然而，現有質心法在星點提取速度上仍存在一定不足。文獻[16]指出，在不改變其他參數情況下，若提高圖像探測器的像素分辨率，則星敏感器姿態測量精度相應提高。因此，目前大面陣圖像探測器，如分辨率為2 048像素×2 048像素，甚至更高的5 120像素×3 840像素，已逐步應用于星敏感器領域，這一情況進一步加劇了星點提取的負擔，現有方法的星點提取速度已成為限制星敏感器數據更新率提高的主要瓶頸。為此，鑒于FPGA具有并行處理能力，本文在傳統單路質心方法的基礎上，重點對多路快速星點質心提取方法進行研究。該方法在FPGA中采用多路掃描方式直接對大面陣星圖像素數據進行并行處理，非常適用于快速處理場合，其處理速度是相同主頻率下的傳統單路質心方法的若干倍。

1 多路快速星點質心提取方法

1.1 基本實現過程

現有的大面陣圖像探測器一般均具有多通道像素輸出能力。若一幅星圖的像素分辨率為2m行×2n列，則采用多通道像素傳輸過程如圖1所示。圖中，星圖全像面劃分為了w個2m行×l列像素的子像面，且w×l=2n，圖像像素按照每行w個通道并行輸出，即每周期輸出一行像素中的w個像素，故只需l個周期即可輸出一行像素，然后繼續輸出下行像素，直至全部像素數據輸出完畢為止。

在將星圖全像面劃分為w個通道進行輸出后，每個周期均有w個像素需要處理，此時，若采用多路快速星點質心提取方法可以直接對多通道輸出像素進行并行處理，而無需進行單行像素的拼接與緩存，從而大大減少了星點提取的處理時間。

圖2是多路快速星點質心提取方法的基本實現原理框圖。由圖可知，多路星點質心提取模塊由w個功能完全相同的單路質心提取子模塊組成。其中，每個單路子模塊均對應處理一個像素，同時，每一單路模塊均與其左右相鄰2個模塊建立了數據交換通道，以便完成邊界目標的有效提取。特別地，位于兩邊的單路模塊CH_1和CH_w，均僅存在一個分割邊界，但為了保持所有模塊的一致性，將其不存在分割邊界的交換通道的輸入置為零。

圖1 多通道像素傳輸過程Fig.1 Multichannel pixel transmission process

圖2 多路快速星點質心提取基本原理框圖Fig.2 Block diagram of basic principle of multichannel fast star centroid extraction

1.2 存在的問題

相比于現有的單路質心方法，多路方法能夠直接對多通道輸出像素數據進行并行處理，從而顯著提升星點提取的處理速度。然而，在實際應用中，多路方法不可避免的存在2個問題，即邊界星點目標融合問題以及冗余存儲資源占用問題。圖3是一幅星圖的局部示意圖，為了清晰顯示，對其進行了閾值化處理。

首先，由圖3可知，在多路快速星點質心提取過程中，處于通道邊界的相鄰像素恰好被各自對應的子模塊分別掃描計算，從而導致邊界上的星點目標被人為分割。因此，必須對邊界星點目標的各部分信息進行重新融合，否則將嚴重降低邊界星點的質心定位精度。其次，由于受到背景噪聲干擾，圖3中除包含一個星點目標外，還包含大量單點、雙點和多點噪聲目標，這些噪聲目標將消耗大量存儲資源。對于多路快速星點質心提取方法，為確保各單路模塊正確完整提取星點信息，各單路模塊的存儲資源開銷應與傳統單路質心方法相當，進而使得整個多路方法所使用的總存儲資源是傳統單路質心方法的若干倍。在此情況下，噪聲目標占用存儲資源的問題將使得多路方法的總存儲資源開銷急劇增加，嚴重時甚至由于總存儲資源不足而導致多路方法無法綜合實現。

圖3 局部星圖的閾值化結果Fig.3 Thresholding results of partial star image

針對上述2個問題，本文分別提出2種技術手段予以解決。首先，提出一種基于目標行方向有效長度的邊界目標信息融合方法，該方法通過利用目標行方向有效像素數目信息(即行方向有效長度)實時判定是否啟動邊界目標信息融合，能夠正確完成各種形狀邊界目標的信息融合。其次，提出一種動態雙指針循環映射機制，能夠對冗余存儲資源進行實時回收利用，大大提高了存儲資源的利用效率。

1.3 邊界目標融合

當采用多路快速星點質心提取方法時，星圖中除了具有傳統的內部目標外，還存在一定的邊界目標。為了正確融合邊界目標信息，本文提出一種基于目標行方向有效長度的邊界目標融合方法，該方法將復雜的信息融合過程轉化為直觀的行方向有效長度特征的判定過程，從而能夠正確完成各種形狀邊界目標的信息融合。

目標的行方向有效長度(以下簡稱為目標行有效長度)，指的是星圖實時掃描過程中目標當前行有效像素的個數，記做Lu，則Lu為非負整數。利用Lu信息可以對目標進行標記，其具體流程如圖4所示。圖中，記CP為當前像素標記，其左方像素標記為Lf，新標記值記為Nf，目標當前行位于上行Lu范圍內的第1個有效像素記為P1，其對應標記值記為LP1，其上行P1像素對應標記值為LP1(up)。由圖4可知，行有效長度標記法的本質是通過上行的Lu信息確定目標同一行的有效像素均采用相同標記，而與該行有效像素是否連續無關。

當采用多路快速星點提取方法時，若每個單路模塊內部均按照圖4所示的行有效長度標記法對星圖中的目標進行標記，則對于圖3中的邊界星點目標，其最終標記結果如圖5所示。圖中，白色像素部分表示星圖背景，深色(灰色與黑色)像素部分表示星點目標。其中，為了突出P1像素，將各行P1像素由灰色加深為黑色顯示，其標記值如白色字體所示。s1～s7與d1～d13分別為當前邊界星點目標所在位置的像素行號與列號。星點左右2個部分均采用順序標記方式,而為了加以區別，左側部分以阿拉伯數字順序標記,右側部分則以大寫英文字母順序標記。

基于行有效長度的邊界目標融合方法對于各種形狀目標的處理過程是相同的。以圖5所示星點目標為例，其融合過程的原理如圖6所示。圖6中，目標處于分割邊界時，同一行將會獲得左右2個行有效長度信息，分別記做LuL、LuR。

首先，如圖6中虛線框Q1所示，根據連通域特性，當目標在邊界2側首次出現連通像素時，表目標為邊界目標。其次，如虛線框Q2所示，在發現邊界目標后，當掃描至LuL=0或LuR=0時，表明邊界目標在左側或右側的部分信息掃描結束，此時在掃描結束一側的當前行中位于上行有效長度上的最后一個像素(該像素稱為融合像素，并記做M)處進行融合，將M像素側的信息融入至另一側信息中。最后，如虛線框Q3所示，利用式(1)可以對目標掃描是否結束進行判定，當目標左右2個行有效長度信息LuL和LuR均為0時，判定目標掃描結束，并將目標當前行中位于其上一行Lu上的最后一個像素稱為目標掃描結束像素，簡記為E像素。

圖4 行有效長度標記法流程圖Fig.4 Flowchart of marking method based on effective length in scanning direction

圖5 邊界目標標記結果示意圖Fig.5 Schematic diagram of marking results of boundary target

圖6 邊界目標融合原理示意圖Fig.6 Schematic diagram of fusion principle of boundary target

Lu=LuL+LuR=0

(1)

以上就是利用行有效長度信息進行邊界目標融合的基本原理，其本質是將復雜的信息融合判定過程轉化為直觀的行有效長度特征的判定過程，通過實時判斷邊界目標2側的LuL、LuR信息滿足至少一個為零時，即可獲得正確的目標融合時刻(M像素)，并在該時刻將目標2側信息進行融合，從而保證融合信息完整正確，且融合過程大為簡化。

1.4 存儲資源循環利用

在多路快速星點質心提取方法中，除星點目標信息外，還存在大量無效信息占用存儲資源。本文從存儲資源循環利用的角度出發，提出一種動態雙指針循環映射機制，能夠實時回收利用無效信息占用的存儲資源，當各單路模塊采用上述機制時，存儲資源開銷均大為減少，從而最終使得多路快速星點質心提取方法的總存儲資源開銷顯著減少，保證其在資源受限的FPGA芯片上依然可綜合實現。

1.4.1 噪聲目標判定

由圖3可知，噪聲目標和星點目標在大小上具有顯著區別，因而可以采用目標大小特征對噪聲目標進行剔除。然而，由于目標的大小、形狀存在隨機性，在星圖實時掃描中，傳統方法難以判定目標掃描何時結束；若判定錯誤，則可能誤回收有效星點信息的存儲資源，從而嚴重影響多路星點質心提取方法的性能。因此，準確判定目標掃描是否結束是正確回收無效信息占用存儲資源的前提，在準確判定目標掃描結束后，即可利用目標大小特征剔除噪聲目標，并回收其占用的存儲資源。

由圖6可知，行有效長度標記法能夠準確判定目標掃描是否結束。利用行有效長度信息判定噪聲目標掃描結束的結果如圖7所示，圖中E像素仍然表示目標掃描結束像素。

由圖6和圖7可知，當掃描至目標E像素時，判定當前目標掃描結束，此時，利用目標大小特征即可對噪聲目標進行剔除。記Kmin為星點目標像素數目最小值，若當前目標大小為Pnum，則判定其為有效星點目標的條件如式(2)所示，否則為噪聲目標，應回收其占用的存儲資源。一般來說，式(2)中的目標大小閾值Kmin由灰度分割閾值大小以及星圖中目標數量、大小等確定。

Pnum≥Kmin

(2)

圖7 噪聲目標掃描結束的判定結果Fig.7 Decision results of scan ending of noise target

1.4.2 動態雙指針循環映射

由以上分析可知，利用目標行有效長度Lu信息及Pnum信息能夠準確判定噪聲目標。在此基礎上，本文提出一種動態雙指針循環映射機制，能夠循環利用噪聲目標占用的存儲資源，從而有效減少各單路模塊的存儲資源開銷，最終使得多路快速星點質心提取方法的總存儲資源開銷顯著減少。值得注意的是，動態雙指針循環映射機制不僅能夠回收利用噪聲目標占用的存儲資源，對于單個目標占用多個標記情況，在對該目標各部分信息融合后，同樣可以將無效標記對應信息占用的存儲資源進行回收。因此，本文后續內容不再對噪聲目標信息和無效標記對應信息進行區分，而是統一稱為無效信息。

圖8是動態雙指針循環映射機制的工作原理圖。如圖8所示，目標信息存儲在星點信息存儲空間中，該存儲空間共可以存儲N個標記的信息，每個標記包含5組信息，即行有效長度Lu，像素灰度和∑f(x,y)，橫坐標與像素灰度乘積累加和∑xf(x,y)，縱坐標與像素灰度乘積累加和∑yf(x,y)，以及當前目標大小信息Pnum，∑f(x,y)、∑xf(x,y)和∑yf(x,y)的值為星點信息存儲空間中的對應數據。地址指針PA和PB分別為主映射指針和回收映射指針，其維度與星點信息存儲空間相同，即均為N維指針，且其功能始終保持動態循環交替轉換。隨著行有效長度標記法實時標記目標，標記空間中的標記值逐漸以自增1方式遞增，且標記值始終與主映射指針的地址一一對應，而該地址對應空間的存儲內容則指向星點信息存儲空間的地址，從而根據主映射指針的上述映射關系，不斷將不同標記值的目標信息存入對應的星點信息存儲空間中。

圖8 動態雙指針循環映射原理圖Fig.8 Schematic diagram of dynamic dual-pointer cyclic mapping

圖8(a)為初始循環映射關系示意圖。初始狀態下，PA作為主映射指針，其存儲內容與星點信息存儲空間的地址一一映射；PB作為回收映射指針，其存儲內容為回收的無效信息占用星點信息存儲空間的地址。假設標記1、Q-1、Q、Q+1和N分別為初始循環映射下的標記值，且滿足1

如圖8(b)所示，當標記值遞增至N+1時，初始循環映射結束，并開始第2次循環映射。此時，交換指針PA、PB的功能，并按照圖8(b)中主映射指針PB的映射關系對標記值對應目標進行信息存儲，PA則作為回收映射指針。第2次循環映射過程中，目標信息占用的存儲空間回收或保留的原理與圖8(a)所示初始循環映射過程完全相同。同理，當第2次循環映射結束后，再次交換指針PA、PB的功能，并如此循環往復，直至一幀星圖掃描結束時停止。

若每一次循環映射結束后得到的回收地址總數目用Wj表示，并為了便于描述，將初始狀態時存儲空間總數目N記做W0，則使用Wj可以描述第j+1次循環映射的可用地址總數目，其中，j=0, 1, 2, …,L。當j=0時，表示初始循環映射；當j=L時，表示第L+1次循環映射，或稱為最終循環映射。如圖9所示，整個動態雙指針循環映射過程實質上是對標記空間的動態壓縮映射過程。

當整幅星圖掃描結束時，利用質心法即可獲得星點目標的質心定位結果，(xc,yc)為星點目標的質心坐標，xc和yc的表達式為

(3)

圖9 動態空間壓縮映射原理圖Fig.9 Schematic diagram of dynamic space compression mapping

2 實驗測試與分析

為了驗證本文提出的多路快速星點質心提取方法(實驗中，多路快速星點提取方法以四路模塊為例，故此節簡稱為四路法)的資源使用情況、星圖處理速度和星點提取結果正確性等方面性能，本節進行了相關實驗測試，并對實驗結果進行了分析討論。

選取Xilinx公司Virtex5系列XC5VLX30型FPGA芯片(封裝：FF324，速度：1級)，分別對傳統單路質心方法、基于本文方法的改進單路法以及本文提出的四路法進行FPGA硬件實現。其中，傳統單路質心方法是指現有的采用連通域標記，并且不對存儲資源進行高效優化使用的星點提取方法；基于本文方法的改進單路法指的是采用目標行有效長度標記法和動態雙指針循環映射機制的改進單路質心方法；本文提出的四路法則是由多個功能完全一致的單路質心提取模塊組成，每個單路模塊均以上述改進單路法為基礎并結合了邊界目標融合功能，因此，四路法能夠對分割后的星圖全像面進行并行星點提取，同時還具有邊界星點目標正確融合與存儲資源高效循環利用特性。上述3種方法綜合實現后的FPGA資源使用情況如表1所示。

表1 3種方法的FPGA資源使用情況Table 1 FPGA resource usage of three methods

由表1可知，2種單路方法的邏輯資源(Slice Registers和Slice LUTs)均占用較少，但為了有效存儲星點信息，存儲資源(Block RAM/FIFO)均消耗較多，傳統單路質心方法和基于本文方法的改進單路法的存儲資源使用率分別為37.5%和15.6%。相比于傳統單路質心方法，基于本文方法的改進單路法采用了動態雙指針循環映射機制，能夠高效循環利用無效信息占用的存儲資源，因而總存儲資源使用量大為減少，僅為傳統單路質心方法的約二分之一。由以上實驗結果估算可知，當傳統單路質心方法直接擴展為四路星點提取方法時，其需要的總存儲資源在FPGA總存儲資源中的占比約為37.5%×4=150%>100%，顯然，由于存儲資源的瓶頸，所選用FPGA芯片已無法完成傳統單路質心方法到四路法的擴展實現。同時，由表1可知，本文提出的四路法由基于本文方法的改進單路法擴展實現，其邏輯資源與存儲資源均為改進單路法的4倍左右。其中，在存儲資源方面，由傳統單路質心方法直接擴展的四路法的存儲資源使用率約為150%，而本文提出的多路法為59.4%，僅占前者的約40%，表明所選用FPGA芯片仍然能夠有效實現本文提出的四路法。

表2是3種方法的處理速度情況表。如表2所示，由于基于本文方法的改進單路法占用存儲資源大為減少，邏輯復雜度有所降低，因而其最大綜合頻率較傳統單路質心方法略有提高；相比之下，由于四路法的邏輯實現最為復雜，因而其最大綜合頻率為3種方法中最低。在上述最大綜合頻率條件下，以分辨率為2m×2n=2 048像素×2 048像素的圖像探測器為例，可得上述3種方法能夠處理的極限星圖幀率如表2所示。由表2可知，四路法能夠處理的極限星圖幀率約為傳統單路質心方法的3.6倍。

下面對多路方法的星點質心提取結果正確性進行驗證，仍然以表1、表2中的四路法為例。整個實驗裝置如圖10所示，圖中，星敏感器固定在實驗平臺上，其視軸方向正對于動態多星模擬器視軸，以便能夠有效拍攝模擬器生成的星圖。

實驗中，采用單幀星圖曝光模式，然后FPGA將拍攝得到的原始星圖數據與四路法計算的對應星點質心數據一并上傳至上位機。需要注意的是，為了避免FPGA硬件字長的截斷誤差對質心定位結果的影響，實驗中FPGA上傳至上位機的星點質心數據為∑f(x,y)、∑xf(x,y)和∑yf(x,y) 共3項數據，以上數據均為整型變量，星點的質心結果(xc,yc)則在上位機MATLAB中根據式(3)計算得到。同時，上位機MATLAB軟件還對上傳的原始星圖數據進行處理，首先采用與上述基于FPGA的四路法完全相同的全局閾值進行目標分割，再以經典的四連通域標記法進行標記聚類，得到星點目標的∑f(x,y)、∑xf(x,y)和∑yf(x,y)共 3項信息，最終同樣按照式(3)對星圖中星點質心進行計算。

表2 3種方法的處理速度Table 2 Processing speed of three methods

圖10 實驗裝置Fig.10 Experimental setup

實驗拍攝了大量不同天區的星圖，選取248幅星圖進行計算，其中恰好包含邊界星點目標的星圖約占10%。當對全部248幅星圖進行計算時，可得基于FPGA的四路提取方法得到的星點質心數據∑f(x,y)、∑xf(x,y)和∑yf(x,y)(實際計算值)，與上位機MATLAB計算得到的對應星點質心數據(理論計算值)均相同。其中，圖11是任選的一幅某天區的星點質心提取結果示意圖，該星圖包含一個邊界星點目標R，紅線表示四路法的像面分割邊界；圖12是上述邊界星點目標R的局部放大圖。由圖11和圖12可知，基于FPGA的四路法得到的星點質心與上位機MATLAB計算得到的對應星點質心(理論計算值)完全一致，表明本文提出的四路法能夠正確提取單路模塊內部星點目標以及邊界星點目標的質心結果。

圖11 某天區的星點質心提取結果Fig.11 Extraction results of star centroid of sky map

圖12 邊界星點目標R的局部放大圖Fig.12 Partial enlarged drawing of boundary star target R

3 結 論

本文提出了一種多路星點質心提取方法，適用于快速處理場合，其處理速度是相同主頻率下的傳統單路質心方法的若干倍。為了驗證本文方法的性能，選取Xilinx公司的FPGA芯片進行實驗測試。

1) 實驗結果表明，基于本文方法改進單路法的總存儲資源使用量僅為傳統單路質心方法的約二分之一；同時，由傳統單路質心方法直接擴展的多路快速質心提取方法的存儲資源使用率約為150%，導致所選用FPGA芯片無法實現，而本文提出的多路快速質心提取方法僅為59.4%，表明在所選用的相同FPGA芯片上仍然能夠實現。

2) 在處理速度方面，本文提出的多路快速質心提取方法的極限星圖幀率為72.3 Hz，是傳統單路質心方法的約3.6倍。

3) 在星點提取結果正確性方面，對實際拍攝的248幅星圖進行計算，其中恰好包含邊界星點目標的星圖約占10%，經實驗驗證，本文的多路快速星點質心提取方法提取方法的質心結果與上位機MATLAB計算結果完全相同，從而表明了算法的正確性。