低存储资源开销的多路快速星点质心提取方法

于文波， 江洁

(北京航空航天大学仪器科学与光电工程学院， 北京 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计算结果完全相同，从而表明了算法的正确性。