鄭天宇 尹達(dá)一

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

關(guān)鍵詞： 質(zhì)心提取算法； 拖尾星斑； 單次掃描； 連通域標(biāo)記； 標(biāo)號回收； FPGA

中圖分類號： TN911.73?34； TP752.1 文獻(xiàn)標(biāo)識碼： 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

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

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

1 星斑拖尾機(jī)理分析

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

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

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

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

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

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

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

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

聯(lián)立式（1）～式（3）得拖尾星斑能量分布函數(shù)為：

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

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

2 單次掃描星斑質(zhì)心計算方法

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

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

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

在本文稱之為質(zhì)心信息（Centroid Information）。

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

2.1 連通域標(biāo)記方法

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

該方法的優(yōu)點是：發(fā)生像素合并時，小標(biāo)號的質(zhì)心信息合并到當(dāng)前行較大標(biāo)號，只需要掃描一次圖像。

2.2 標(biāo)號合并與質(zhì)心信息存儲

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

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

單次掃描連通域標(biāo)記的具體過程如下：

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

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

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

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

2.3 標(biāo)號回收機(jī)制

當(dāng)兩個子連通域合并后，小標(biāo)號地址的內(nèi)容將被清空。為了節(jié)省存儲資源，可以將其標(biāo)號回收并重復(fù)利用，減小內(nèi)存開銷。

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

3 單次掃描算法的FPGA硬件實現(xiàn)

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

標(biāo)記及存儲控制單元負(fù)責(zé)子連通域標(biāo)號分配和子連通域的合并，是單次掃描算法的核心單元。其硬件結(jié)構(gòu)如圖5所示。

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

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

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

4 FPGA測試及結(jié)果分析

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

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

5 結(jié) 論

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

參考文獻(xiàn)

[1] 樊巧云，張廣軍.離散噪聲圖像的光斑質(zhì)心算法及其硬件實現(xiàn)[J].光學(xué)精密工程，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] 梁斌，朱海龍，張濤，等.星敏感器技術(shù)研究現(xiàn)狀及發(fā)展趨勢[J].中國光學(xué)，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] 曹小濤，孫天宇，趙運隆，等.空間大口徑望遠(yuǎn)鏡穩(wěn)像系統(tǒng)發(fā)展現(xiàn)狀及趨勢[J].中國光學(xué)，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] 曹陽，李保權(quán)，李海濤，等.像素位置偏差對質(zhì)心定位精度的影響[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] 錢鋒，楊名宇，張曉沛.基于序列圖像提高光斑質(zhì)心定位精度[J].光學(xué)精密工程，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函數(shù)估計及復(fù)原算法研究[J].傳感技術(shù)學(xué)報，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] 鹿瑞，武延鵬.動態(tài)拖尾星圖模擬算法研究[J].空間控制技術(shù)與應(yīng)用，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圖像處理在水果品級篩選技術(shù)中的應(yīng)用[J].現(xiàn)代電子技術(shù)，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實現(xiàn)實時提取恒星星像坐標(biāo)的方法[J].導(dǎo)航定位與授時，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.