郑天宇 尹达一

摘 要： 在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.