鄭天宇 尹達(dá)一

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

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

中圖分類號(hào)： TN911.73?34； TP752.1 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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)測(cè)量部件如精細(xì)導(dǎo)星儀恒星星斑亞像元定位[3]、星敏感器星點(diǎn)定位、太陽(yáng)敏感器的太陽(yáng)光斑定位等。理想恒星星光在探測(cè)器焦面上成像為一高斯光斑，可以利用重心法[4?5]等方法計(jì)算出光斑的質(zhì)心位置。

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

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

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

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

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

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

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

式中，[t0]為積分時(shí)間。

曝光時(shí)間內(nèi)星斑沿焦平面某一方向運(yùn)動(dòng)，設(shè)高斯中心位置隨時(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所示。拖尾星斑跨越多個(gè)像素，且形狀較為復(fù)雜。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

參考文獻(xiàn)

[1] 樊巧云，張廣軍.離散噪聲圖像的光斑質(zhì)心算法及其硬件實(shí)現(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ā)展趨勢(shì)[J].中國(guó)光學(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] 曹小濤，孫天宇，趙運(yùn)隆，等.空間大口徑望遠(yuǎn)鏡穩(wěn)像系統(tǒng)發(fā)展現(xiàn)狀及趨勢(shì)[J].中國(guó)光學(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] 曹陽(yáng)，李保權(quán)，李海濤，等.像素位置偏差對(duì)質(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] 張濤，王宏力，陸敬輝，等.振動(dòng)模糊星圖的PSF函數(shù)估計(jì)及復(fù)原算法研究[J].傳感技術(shù)學(xué)報(bào)，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] 鹿瑞，武延鵬.動(dòng)態(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圖像處理在水果品級(jí)篩選技術(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實(shí)現(xiàn)實(shí)時(shí)提取恒星星像坐標(biāo)的方法[J].導(dǎo)航定位與授時(shí)，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.