單次掃描星斑質心提取算法及FPGA驗證

鄭天宇 尹達一

摘 要： 在FPGA中實現了一種新的星點質心提取算法，對星提取和連通域標記進行了研究。對拖尾星斑以行為單位劃分子連通域，逐像素掃描將子連通域動態合并。利用標號回收機制降低片上資源占用率。最終，設計算法的硬件結構，并將算法在FPGA中實現，對拖尾星圖進行了星提取。仿真與測試結果表明，該算法能夠通過一次掃描提取出星斑質心信息，不需要圖像緩存，在125 MHz時鐘下數據吞吐率達到了1 Gbit/s。針對512×512面陣探測器處理速度可達到476 f/s，滿足星圖質心提取算法實時性的要求。

關鍵詞： 質心提取算法； 拖尾星斑； 單次掃描； 連通域標記； 標號回收； FPGA

中圖分類號： TN911.73?34； TP752.1 文獻標識碼： A 文章編號： 1004?373X（2018）14?0019?05

Star spot centroid extraction algorithm with a single scan and its FPGA verification

ZHENG Tianyu1，2，3， Yin Dayi1，2

（1. Key Laboratory of Infrared Detection and Imaging Technology of the Chinese Academy of Sciences， Shanghai 200083， China；

2. Shanghai Institute of Technical Physics of the Chinese Academy of Sciences， Shanghai 200083， China；

3. University of Chinese Academy of Sciences， Beijing 100049， China）

Abstract： A new star spot centroid extraction algorithm is implemented in FPGA to study the star extraction and connected domain labeling. Trailing star spots are divided into sub?connected domains by action unit， and the sub?connected domains are dynamically merged by means of pixel?by?pixel scanning. The label recycling mechanism is used to reduce the occupation rate of on?chip resources. The hardware structure of the algorithm is designed， and the algorithm is realized in FPGA， so as to perform star extraction of the trailing star map. The simulation and test results show that the algorithm can extract star spot centroid information with a single scan， and does not need image buffering； the data throughput rate reaches 1 Gbit/s with the 125 MHz clock； as for the 512×512 area array detector， its processing speed can reach to 476 f/s， which can satisfy the real?time requirement of the star map centroid extraction algorithm.

Keywords： centroid extraction algorithm； trailing star spot； single scan； connected domain labeling； label recycling；

FPGA

光斑圖像是圖像處理中常見的圖像信息，光斑質心是光斑圖像的重要特征[1?2]，常用于航空航天技術中姿態測量部件如精細導星儀恒星星斑亞像元定位[3]、星敏感器星點定位、太陽敏感器的太陽光斑定位等。理想恒星星光在探測器焦面上成像為一高斯光斑，可以利用重心法[4?5]等方法計算出光斑的質心位置。

實際飛行中航天器的旋轉、移動、抖動等運動使探測器曝光過程中星點移動導致星圖中星斑存在拖尾現象。一個星斑的能量在視軸移動方向上跨越多個像素[6?7]，給星提取和星斑質心的計算帶來難度。為了得到拖尾星斑全部能量信息，利用星斑的連續性將連通域標記算法和質心計算結合在一起[8]，隨著圖像的掃描，動態計算質心信息。但對于形狀復雜的拖尾星斑，現有算法一般需要二次掃描星圖，降低了數據更新率。近年來FPGA由于其并行處理的優勢，在高速圖像采集處理系統中的應用愈漸廣泛[9?10]。本文主要針對有拖尾星斑的星圖進行快速星斑質心提取。

1 星斑拖尾機理分析

載體靜止時，恒星在焦平面上的像為近似高斯函數的星斑，其能量分布可以用二維高斯函數來表示，如下：

[I（x，y）=Φ2πσ2PSFexp-（x-x0）2+（y-y0）22σ2PSF] （1）

式中：[Ix，y]是坐標為[x，y]的像元接收到的恒星輻射功率；[Φ]為探測器接收到的全部恒星輻射功率；[σPSF]為彌散斑束腰寬度。

最終輸出圖像為高斯函數下各像素在空間和時間上的三重積分如下：

[I=0t0m-0.5m+0.5n-0.5n+0.5Ix，ydxdydt] （2）

式中，[t0]為積分時間。

曝光時間內星斑沿焦平面某一方向運動，設高斯中心位置隨時間變化的函數為：

[x0=fxt， y0=fyt] （3）

聯立式（1）～式（3）得拖尾星斑能量分布函數為：

[I=0t0m-0.5m+0.5n-0.5n+0.5Φ×t02πσ2exp-（x-fxt）22σ2×exp-（y-fyt）22σ2dxdydt] （4）

原始星斑與拖尾星斑如圖1所示。拖尾星斑跨越多個像素，且形狀較為復雜。

2 單次掃描星斑質心計算方法

星斑的質心坐標可以通過求其像空間的1階矩與0階矩的比值來求得[4]。質心計算公式如式（5）所示。式中，[fx，y]表示圖像中[x，y]處像素的灰度值。為了求解質心橫縱坐標[x0]，[y0]，需要存儲的信息為：

[fx，y·x，fx，y·y，fx，y]

[x0=fx，y·xfx，yy0=fx，y·yfx，y] （5）

在本文稱之為質心信息（Centroid Information）。

單次掃描星斑質心計算方法就是在標記過程中將屬于同一星斑的質心信息累加到一起，整幅圖像標記完成后計算各個星斑的質心坐標，星斑分配的標號作為質心信息的存儲地址。

2.1 連通域標記方法

傳統連通域標記算法存在對復雜形狀提取連通域時需要二次掃描的問題。質心提取算法在累加完當前像素的質心信息后其標號及存儲空間可以釋放。由此提出一種新方法：當掃描到有效像素后，賦給其一新標號并將標號進行水平傳遞。隨著掃描的進行，最終屬于同一像斑的星像素在水平方向上被分割成了幾個子連通區域，每個區域被分配了一個唯一的標號。星斑標記的結果如圖2所示，相鄰行的若干個子連通域共同組成了一個有效星斑。

該方法的優點是：發生像素合并時，小標號的質心信息合并到當前行較大標號，只需要掃描一次圖像。

2.2 標號合并與質心信息存儲

從圖2所示的星斑標記結果可以看出，在圖像的列方向相鄰行存在兩個不同標號子連通域相遇的情況，此時會發生標號合并，標號合并具體的操作對象是存儲器中的質心信息，將屬于同一星斑的質心信息進行累加。

本文提出一種小標號向大標號合并的方法，從而對整幅圖像只需要一次掃描就可以提取到所有星斑的質心信息。當掃描窗口內發生表1中幾種情況時需要標號合并。定義操作[T（arg1，arg2）]，表示將[arg1]地址存儲的數據與[arg2]地址存儲的數據相加后放回到[arg2]地址的存儲單元中，完成合并。C_L，L_L，UL_L，U_L，UR_L分別表示當前像素，當前像素的左方、左上、上方、右上像素的標號。

單次掃描連通域標記的具體過程如下：

1） 當掃描到一個有效像素時，如果其上方八連通域沒有被標記過的像素，則分配給其一個新的標號，并且將其質心信息存儲到以標號為地址的存儲單元。

2） 當掃描到一個有效像素時，如果其左方標號不為0，其他鄰域為0，則將左方像素標號復制給該像素，并將該像素碼值累加到存儲單元。

3） 當掃描到一個有效像素且其鄰域標號滿足表1所示時，發生表1中的合并操作，將存儲單元中的質心信息合并。

可以利用FPGA的并行運算特性，將上述決策過程表示為一個組合邏輯，使其可以在一個時鐘時間內完成合并操作。

2.3 標號回收機制

當兩個子連通域合并后，小標號地址的內容將被清空。為了節省存儲資源，可以將其標號回收并重復利用，減小內存開銷。

圖3是圖2所示拖尾星斑的一個連通域合并及存儲過程。圖3分別演示了第2，3行和最后一行的合并及存儲過程。由圖3可知，標號回收方法的提出，整個星斑由原來的8個標號減少到1個，極大地節省了存儲空間。

3 單次掃描算法的FPGA硬件實現

算法硬件各模塊之間的接口如圖4所示，其由三部分組成：連通域標記及存儲控制單元、質心信息存儲單元和標號生成單元。

標記及存儲控制單元負責子連通域標號分配和子連通域的合并，是單次掃描算法的核心單元。其硬件結構如圖5所示。

該單元的輸入為當前像素灰度值、待分配標號；輸出為質心信息及寫入地址、合并地址。當前有效像素的標號由其周圍四個像素的標號來決定，標記過程如第2.2節所述流程進行處理。組合邏輯負責整個連通域標記及合并操作的控制。當星斑子連通域合并時，除了要給出當前像素的累加地址外還要給出被合并標號的地址merge_addr，通知存儲單元完成質心信息合并；同時，為了避免多次合并現象的發生，建立一個標號翻譯表來記錄已經發生合并的一對標號。緩存標號在進入UR_L前會先查找標號翻譯表中的記錄，如果標號翻譯表中有相應的記錄，則將自身替換為記錄中的值，如沒有記錄則直接輸出。模塊中有行、列計數器來計算當前像素的坐標，經過乘法器算出質心信息。存儲單元硬件結構如圖6所示。

質心信息存儲單元包含三個相同結構的存儲器分別用于存儲[fx，y·x]，[fx，y·y]，[fx，y]，為了在一個時鐘內實現質心信息的存取與累加，存儲單元采用雙口RAM，可以實現不同地址單元同時讀/寫。存儲器內部組合邏輯負責控制數據的讀寫操作。以[fx，y]存儲單元舉例，wr_addr為累加完的數據的寫入地址，其值與標號模塊傳遞過來的inf_addr相等。merge_addr表示合并地址，當merge_addr[≠0]時表示發生合并，否則表示不發生合并。不發生合并時，各信號如表2第1行所示，輸入的像素值與inf_addr地址中的內容累加。發生合并時merge_addr[≠0]，inf_addr和merge_addr中的內容被取出與輸入的像素值[fx，y]累加后寫入到inf_addr地址中，完成合并。此時各地址如表2第2行所示。

標號生成單元負責標號生成和標號回收，標號回收可以極大地減小資源的消耗。標號生成單元優先使用FIFO中存儲的回收標號，當FIFO為空時標號寄存器中的值加1，并輸出給新標號?？刂菩盘柕淖饔檬菕呙枰粋€子連通域時，當前像素的標號復制自其左方的標號，此時控制標號產生單元不產生新的標號。硬件結構見圖7。

4 FPGA測試及結果分析

為了驗證本文算法的有效性和在FPGA上運行的性能，使用Verilog HDL語言在Xilinx virtex?6 平臺上實現了算法。實驗中在ROM中存儲一幅512×512大小模擬星圖，在125 MHz的時鐘下順序讀取。星圖中在不同位置隨機產生了9個帶星點漂移的星斑，其中水平方向、豎直方向、45°方向各三個。同時為了模擬真實星圖，圖像加入高斯噪聲。模擬星圖如圖8所示。

對于本文9個模擬的星斑，本文算法計算得到的質心參數與理論值完全一致，驗證了該算法的有效性。為了驗證算法的性能，在XC6VLX240T?1FF1156芯片上實現了算法并進行資源分析和靜態時序分析，結果如表4所示。由表可知，本文算法資源消耗少、工作頻率高。本文將相關文獻算法的性能統一轉換為數據吞吐率和需要的存儲空間，以此衡量算法的優劣。表5是不同算法間的比較，由表可知，本文算法在速度和算法面積資源消耗上具有較大優勢。測試平臺如圖9所示，其由XC6VLX240T FPGA電路板、調試器、上位機以及電源組成。本算法在XC6VLX240T?1FF1156測試平臺上成功在125 MHz時鐘下運行，數據吞吐率達到1 Gbit/s。

5 結 論

本文分析了拖尾星斑的產生機理，提出一種只需要一次掃描圖像就可以提取出有效星斑質心的算法。星斑質心提取算法速度快、數據更新率高且質心信息計算值與理論值完全相等。同時，標號回收機制的首次使用，可以極大地減少芯片內部資源的占用率。算法在FPGA器件上實現，最高時鐘頻率達到125 MHz；對于具有[512×512]面陣探測器，可以實現476 Hz的數據更新率。后面還會進一步優化組合邏輯，合理分配流水線，提高算法的運行頻率，提高數據吞吐量，從而滿足更大面陣、更高幀頻質心定位的要求。

參考文獻

[1] 樊巧云，張廣軍.離散噪聲圖像的光斑質心算法及其硬件實現[J].光學精密工程，2011，19（12）：2992?2998.

FAN Qiaoyun， ZHANG Guangjun. Spot centroiding algorithm for discrete noise image and its hardware implementation [J]. Optics and precision engineering， 2011， 19（12）： 2992?2998.

[2] 梁斌，朱海龍，張濤，等.星敏感器技術研究現狀及發展趨勢[J].中國光學，2016，9（1）：16?29.

LIANG Bin， ZHU Hailong， ZHANG Tao， et al. Research status and development tendency of star tracker technique [J]. Chinese journal of optics， 2016， 9（1）： 16?29.

[3] 曹小濤，孫天宇，趙運隆，等.空間大口徑望遠鏡穩像系統發展現狀及趨勢[J].中國光學，2014，7（5）：739?748.

CAO Xiaotao， SUN Tianyu， ZHAO Yunlong， et al. Current status and development tendency of image stabilization system of large aperture space telescope [J]. Chinese journal of optics， 2014， 7（5）： 739?748.

[4] 曹陽，李保權，李海濤，等.像素位置偏差對質心定位精度的影響[J].紅外與激光工程，2016，45（12）：302?307.

CAO Yang， LI Baoquan， LI Haitao， et al. Pixel displacement effects on centroid position accuracy [J]. Infrared and laser engineering， 2016， 45（12）： 302?307.

[5] 錢鋒，楊名宇，張曉沛.基于序列圖像提高光斑質心定位精度[J].光學精密工程，2016，24（11）：2880?2888.

QIAN Feng， YANG Mingyu， ZHANG Xiaopei. Improvement of localization accuracy of spot centroid based on sequential images [J]. Optics and precision engineering， 2016， 24（11）： 2880?2888.

[6] 張濤，王宏力，陸敬輝，等.振動模糊星圖的PSF函數估計及復原算法研究[J].傳感技術學報，2016，29（8）：1234?1238.

ZHANG Tao， WANG Hongli， LU Jinghui， et al. Research on PSF function estimation and restoration algorithm for vibration fuzzy star image [J]. Chinese journal of sensors and actuators， 2016， 29（8）： 1234?1238.

[7] 鹿瑞，武延鵬.動態拖尾星圖模擬算法研究[J].空間控制技術與應用，2016，42（4）：57?62.

LU Rui， WU Yanpeng. An approach of star image simulation for strapdown star sensor [J]. Aerospace control and application， 2016， 42（4）： 57?62.

[8] AZIZABADI M， BEHRAD A， GHAZNAVI?GHOUSHCHI M B. VLSI implementation of star detection and centroid calculation algorithms for star tracking applications [J]. Journal of real?time image processing， 2014， 9（1）： 127?140.

[9] 程光偉，劉東明.FPGA圖像處理在水果品級篩選技術中的應用[J].現代電子技術，2016，39（2）：89?91.

CHENG Guangwei， LIU Dongming. Application of FPGA image processing in fruit grade screening technique [J]. Modern electronics technique， 2016， 39（2）： 89?91.

[10] 李葆華，曾慶雙，張同雙.一種基于FPGA實現實時提取恒星星像坐標的方法[J].導航定位與授時，2015，2（1）：46?51.

LI Baohua， ZENG Qingshuang， ZHANG Tongshuang. An obtaining star locations method with FPGA for star sensor [J]. Navigation positioning and timing， 2015， 2（1）： 46?51.