CN112270704B - 一种基于数据链表结构的星点质心提取方法 - Google Patents

Abstract

一种基于数据链表结构的星点质心提取方法，涉及星敏感器中星点质心定位技术领域，解决现有星点质心提取时，采用游程编码方式提取星点质心坐标，需要构建等价表且多次轮询游程编码的问题。将高斯滤波处理后逐行输入的图像数据流进入初步标记模块，写游程编码链表和星点像素缓存。标记合并模块读取初次写入的游程编码链表并合并标记，进行数据链接，质心计算模块读取合并后的游程编码链表并根据缓存的星点像素值进行质心计算，本发明的方法只需对星图扫描一次，省去等价表的设置及合并过程，避免对游程编码的多次轮询。在质心计算时加快了游程编码的寻址速度，减少了质心计算时游程编码寻址的时间消耗，有助于提升星敏感器的姿态更新率。

Description

一种基于数据链表结构的星点质心提取方法

技术领域

本发明涉及星敏感器中星点质心定位技术领域，具体涉及一种基于数据链表结构的星点质心提取方法。

背景技术

随着航天技术的飞速发展，星敏感器也在向着更高速度、更高精度和抗干扰性更强的方向发展。星点提取是星图处理的开始，其提取坐标的准确率很大程度上决定了后续星图识别的准确率，影响星敏感器的定姿性能。星敏感器对星点质心提取过程中，算法的精度、运行时间、抗干扰性等方面都有着很严格的要求。如何快速准确地提取星点坐标一直是提升星敏感器性能的关键因素。

现有方法为提取星点质心坐标信息，首先要对星图中的星点进行分割和识别。星点的识别方法可以利用基本的图像处理方法，如连通域法、聚类法等。目前很多文献提供的星点质心提取方法很难避免多次扫描星图，而且由于标号冲突现象非常普遍，合并标号并提取质心的过程比较复杂，所以算法效率不高。但是，随着航天技术的发展，星敏感器对星点质心定位的实时性要求越来越高。

FPGA具有并行计算处理的优势，将星点提取算法用FPGA硬件实现已成为解决星敏感器输出帧频受限的一种有效途径。

发明内容

本发明为解决现有星点质心提取时，采用游程编码方式提取星点质心坐标，需要构建等价表且多次轮询游程编码的问题。有鉴于此，本发明的主要目的在于提供了一种基于数据链表结构的星点质心提取方法。

一种基于数据链表结构的星点质心提取方法，该方法由以下步骤实现：

步骤一、利用高斯滤波对星图图像进行去噪预处理；

步骤二、对步骤一进行去噪处理后的星图图像中星点像素逐行扫描，通过初步标记模块对星点连通域逐行进行游程编码，并存储在游程编码链表中；所述游程编码的记录格式为：记录每行星点连通区域的标号+起始行+起始列+终止列+下一相同标号的游程编码地址；

步骤三、采用标记合并模块对初步标记的游程编码进行合并，连通的游程的标号赋予该连通游程中标号的最小值，同一标号的游程编码将按从左到右从上到下的规则链接；

所述标记合并模块的具体实现过程为：

步骤三一、初始化游程编码读取地址为零；

步骤三二、顺序读取下一个游程编码，记录为当前行游程编码，判断是否最后一个游程编码，如果是，结束；如果否，执行步骤三三；

步骤三三、判断星图上一行是否存在游程编码，如果是，执行步骤三四；如果否，返回执行步骤三二；

步骤三四、判断星图上一行是否存在未遍历的游程编码，如果是，顺序读取星图上一行未遍历的游程编码，执行步骤三五；如果否，返回执行步骤三二；

步骤三五、判断星图上一行游程编码与当前行游程编码是否邻接，如果是，执行步骤三六；如果否，返回执行步骤三四；

步骤三六、判断游程编码是否第一次邻接，如果是，将当前游程编码地址记录在邻接游程编码链接寻址到的最后一个游程编码上，将当前游程编码标号更新为邻接游程编码标号，返回执行步骤三四；如果否，执行步骤三七；

步骤三七、判断邻接游程编码标号与当前游程编码标号是否相等，如果是，返回执行步骤三四；如果否，执行步骤三八；

步骤三八、判断当前行游程编码标号是否大于邻接游程编码标号，如果是，从上上一行开始读取游程编码，直到找到与当前行游程编码标号相等的游程编码，链接这个游程编码的地址到上一行判断的小标号游程编码，寻址到的最后一个游程编码上，最后按照大标号游程编码链接地址寻址，更新所有大标号的游程编码为小标号，返回执行步骤三四；如果否，执行步骤三九；

步骤三九、从上上一行开始读取游程编码，直到找到与邻接游程编码相同标号的游程编码，链接这个游程编码的地址到上一个，与当前行游程编码邻接的游程编码上；最后按照大标号游程编码链接地址寻址，更新所有大标号的游程编码为小标号，将当前行游程编码的地址链接到邻接游程编码寻址的最后一个游程编码中，返回执行步骤三四；

步骤四、顺序遍历游程编码链表，采用质心计算模块读取合并后的游程编码链表；根据游程编码链表的链接寻址连通的游程编码，根据游程编码存储的信息读取缓存的星点像素值进行质心计算，提取星点在星图中的坐标信息。

本发明的有益效果：本发明所述的方法结合星图特点及FPGA流水线处理结构，基于数据链表改进了标号合并过程，在传统游程编码的基础上增加链接地址，在质心计算时加快了游程编码的寻址速度，减少了质心计算时游程编码寻址的时间消耗，有助于提升星敏感器的姿态更新率。

本发明所述的方法采用数据链表与游程编码相结合的方式，将连通的单个星点数据链接在一起并按照特定方式存储。该方法采用FPGA进行模块化设计，充分发挥了硬件流水线实现的速度优势。本方法只需对星图扫描一次，省去了等价表的设置及其合并过程，也避免了对游程编码的多次轮询。

附图说明

为了更清楚地说明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图做简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明所述的一种基于数据链表结构的星点质心提取系统的结构框图；

图2为本发明所述的一种基于数据链表结构的星点质心提取方法中初步标记模块的流程图；

图3为本发明所述的一种基于数据链表结构的星点质心提取方法中标记合并模块的流程图；

图4中(a)、(b)、(c)、(d)和(e)分别为本发明所述的基于数据链表结构的星点质心提取方法中，游程编码合并的几种情况示意图；

图5为本发明所述的一种基于数据链表结构的星点质心提取方法中质心计算模块的流程图。

具体实施方式

具体实施方式一、结合图1至图5说明本实施方式，一种基于数据链表结构的星点质心提取方法，该方法基于星点质心提取系统实现，结合图1，该系统由FPGA实现，具体由初步标记模块、标记合并模块和质心计算模块组成；经高斯滤波处理后逐行输入的图像数据流进入初步标记模块，所述初步标记模块进行写游程编码链表和星点像素缓存；所述标记合并模块读取初步标记模块首次写入的游程编码链表并合并标记，进行数据链接，所述质心计算模块读取合并后的游程编码链表并根据缓存的星点像素值进行质心计算。

结合图2至图5说明本实施方式，星点质心提取方法的具体步骤为：

步骤一、利用高斯滤波对星图图像进行去噪预处理；

步骤二、对步骤一进行去噪处理后的星图图像中星点像素逐行扫描，通过初步标记模块对星点连通域逐行进行游程编码，并存储在游程编码链表中；所述游程编码的记录格式为：记录每行星点连通区域的标号+起始行+起始列+终止列+下一相同标号的游程编码地址；结合图2，所述初步标记模块的具体过程为：

步骤二一、在图像平均灰度值的基础上乘以一个系数作为分割阈值，初步标记中，下一相同标号的游程编码地址标记为零，初始化标号为1；

步骤二二、顺序接收逐行输入的图像数据流，读取星图图像的像素值；

步骤二三、判断是否为星图图像最后一个像素值，如果是，结束；如果否，执行步骤二四；

步骤二四、判断当前像素值是否大于分割阈值，如果是，记录游程编码起始行、起始列和标号，顺序接收像素值，执行步骤二五；如果否，返回步骤二二；

步骤二五、判断是否星图最后一个像素值，如果是，结束；如果否，执行步骤二六；

步骤二六、判断当前像素值是否小于等于分割阈值，如果是，记录游程编码的终止列，并写一次游程编码链表，标号+1后返回执行步骤二二；如果否，顺序接收下一像素值，返回执行步骤二五。

步骤三、采用标记合并模块对初步标记模块标记的游程编码进行合并，连通的游程的标号赋予该连通游程中标号的最小值，同一标号的游程编码将按从左到右从上到下的规则链接；具体实现过程结合图3；

步骤三一、初始化游程编码读取地址为零；

步骤三二、顺序读取下一个游程编码，记录为当前行游程编码，判断是否最后一个游程编码(读取到的游程编码链表值是否为零)，如果是，结束；如果否，执行步骤三三；

步骤三三、判断星图上一行是否存在游程编码，如果是，执行步骤三四；如果否，返回执行步骤三二；

步骤三四、判断星图上一行是否存在未遍历的游程编码，如果是，顺序读取星图上一行未遍历的游程编码，执行步骤三五；如果否，返回执行步骤三二；

步骤三五、判断星图上一行游程编码与当前行游程编码是否邻接，如果是，执行步骤三六；如果否，返回执行步骤三四；

步骤三六、判断游程编码是否第一次邻接，如果是，将当前游程编码地址记录在邻接游程编码链接寻址到的最后一个游程编码上，将当前游程编码标号更新为邻接游程编码标号，返回执行步骤三四；如果否，执行步骤三七；

步骤三七、判断邻接游程编码标号与当前游程编码标号是否相等，如果是，返回执行步骤三四；如果否，执行步骤三八；

步骤三八、判断当前行游程编码标号是否大于邻接游程编码标号，如果是，从上上一行开始读取游程编码，直到找到与当前行游程编码标号相等的游程编码，链接这个游程编码的地址到上一行判断的小标号游程编码，寻址到的最后一个游程编码上，最后按照大标号游程编码链接地址寻址，更新所有大标号的游程编码为小标号(合并标号)，返回执行步骤三四；如果否，执行步骤三九；

步骤三九、从上上一行开始读取游程编码，直到找到与邻接游程编码相同标号的游程编码，链接这个游程编码的地址到上一个，与当前行游程编码邻接的游程编码上；最后按照大标号游程编码链接地址寻址，更新所有大标号的游程编码为小标号，将当前行游程编码的地址链接到邻接游程编码寻址的最后一个游程编码中，返回执行步骤三四；

结合图4说明本实施方式，本实施方式中，正常星点经过高斯滤波后，几乎不存在上一行有多个邻域的情况，但拖尾星点可能会存在上一行有多个邻域的情况。下图代表上一行有多个邻接游程编码的情况，以及针对这些情况的执行效果。图中数字代表该游程编码标号，箭头代表游程编码链接的地址方向。每幅图左侧为待处理的情况，图右侧为处理后的结果。

当前行像素碰到上一行存在不止一个邻域，且新邻域标号比当前标号大，且上上一行无游程编码，如图4中(a)所示；当前行像素碰到上一行存在不止一个邻域，且新邻域标号比当前标号小，且上上一行有游程编码，如图4中(b)所示；当前行像素碰到上一行存在不止一个邻域，且新邻域标号比当前标号大，且上上一行有游程编码，如图4中(c)所示；当前行像素碰到上一行存在不止一个邻域，且新邻域标号比当前标号大，且上上一行有游程编码，如图4中(d)所示；当前行像素碰到上一行存在不止一个邻域，且新邻域标号与当前标号相等(该情况上上一行必有游程编码)，如图4中(e)所示。

步骤四、初步标记和标记合并后，同一连通域内的游程编码标号取决于其中的最小标号，游程编码地址链接满足从上到下从左到右的逻辑顺序。结合图5，质心计算模块的具体步骤如下：

步骤四一、初始化比对编码为零，游程编码读取地址为零；

步骤四二、顺序读取下一个游程编码，记录标号为当前游程编码标号；

步骤四三、判断是否最后一个游程编码，如果是，结束；如果否，执行步骤四四；

步骤四四、判断当前游程编码标号是否大于比对标号，如果是进入下一步；如果否，回到步骤四二；

步骤四五、按读取的游程编码记录的起始行、起始列和终止列寻址星点像素，将读取的像素数据代入质心计算公式，公式如下：

式中：(x₀,y₀)为质心坐标；F(x,y)表示坐标(x,y)像素点像素值；T代表分割阈值；s代表相同标号游程编码寻址的星点集合。

步骤四六、判断游程编码的链接地址是否为零，如果是，计算输出一次质心坐标，将当前游程编码标号赋值给比对标号，回到步骤四二；如果否，取游程编码的链接地址，寻址邻接的游程编码，返回步骤四五。

Claims (3)

1.一种基于数据链表结构的星点质心提取方法，其特征是：该方法由以下步骤实现：

步骤一、利用高斯滤波对星图图像进行去噪预处理；

步骤二、对步骤一进行去噪处理后的星图图像中星点像素逐行扫描，通过初步标记模块对星点连通域逐行进行游程编码，并存储在游程编码链表中；所述游程编码的记录格式为：记录每行星点连通区域的标号+起始行+起始列+终止列+下一相同标号的游程编码地址；

步骤三、采用标记合并模块对初步标记的游程编码进行合并，连通的游程的标号赋予该连通游程中标号的最小值，同一标号的游程编码将按从左到右从上到下的规则链接；

所述标记合并模块的具体实现过程为：

步骤三一、初始化游程编码读取地址为零；

步骤三二、顺序读取下一个游程编码，记录为当前行游程编码，判断是否最后一个游程编码，如果是，结束；如果否，执行步骤三三；

步骤三三、判断星图上一行是否存在游程编码，如果是，执行步骤三四；如果否，返回执行步骤三二；

步骤三四、判断星图上一行是否存在未遍历的游程编码，如果是，顺序读取星图上一行未遍历的游程编码，执行步骤三五；如果否，返回执行步骤三二；

步骤三五、判断星图上一行游程编码与当前行游程编码是否邻接，如果是，执行步骤三六；如果否，返回执行步骤三四；

步骤三六、判断游程编码是否第一次邻接，如果是，将当前游程编码地址记录在邻接游程编码链接寻址到的最后一个游程编码上，将当前游程编码标号更新为邻接游程编码标号，返回执行步骤三四；如果否，执行步骤三七；

步骤三七、判断邻接游程编码标号与当前游程编码标号是否相等，如果是，返回执行步骤三四；如果否，执行步骤三八；

步骤三八、判断当前行游程编码标号是否大于邻接游程编码标号，如果是，从上上一行开始读取游程编码，直到找到与当前行游程编码标号相等的游程编码，链接这个游程编码的地址到上一行判断的小标号游程编码，寻址到的最后一个游程编码上，最后按照大标号游程编码链接地址寻址，更新所有大标号的游程编码为小标号，返回执行步骤三四；如果否，执行步骤三九；

步骤三九、从上上一行开始读取游程编码，直到找到与邻接游程编码相同标号的游程编码，链接这个游程编码的地址到上一个，与当前行游程编码邻接的游程编码上；最后按照大标号游程编码链接地址寻址，更新所有大标号的游程编码为小标号，将当前行游程编码的地址链接到邻接游程编码寻址的最后一个游程编码中，返回执行步骤三四；

步骤四、顺序遍历游程编码链表，采用质心计算模块读取合并后的游程编码链表；根据游程编码链表的链接寻址连通的游程编码，根据游程编码存储的信息读取缓存的星点像素值进行质心计算，提取星点在星图中的坐标信息。

2.根据权利要求1所述的一种基于数据链表结构的星点质心提取方法，其特征在于：所述初步标记模块的具体标记步骤为：

步骤二一、设定星图图像的分割阈值，初步标记中，下一相同标号的游程编码地址标记为零，初始化标号为1；

步骤二二、顺序接收逐行输入的图像数据流，读取星图图像的像素值；

步骤二三、判断是否为星图图像最后一个像素值，如果是，结束；如果否，执行步骤二四；

步骤二四、判断当前像素值是否大于分割阈值，如果是，记录游程编码起始行、起始列和标号，顺序接收像素值，执行步骤二五；如果否，返回步骤二二；

步骤二五、判断是否星图最后一个像素值，如果是，结束；如果否，执行步骤二六；

步骤二六、判断当前像素值是否小于等于分割阈值，如果是，记录游程编码的终止列，并写一次游程编码链表，标号+1后返回执行步骤二二；如果否，顺序接收下一像素值，返回执行步骤二五。

3.根据权利要求1所述的一种基于数据链表结构的星点质心提取方法，其特征在于：所述质心计算模块的具体计算过程为：

步骤四一、初始化比对编码为零，游程编码读取地址为零；

步骤四二、顺序读取下一个游程编码，记录标号为当前游程编码标号；

步骤四三、判断是否最后一个游程编码，如果是，结束；如果否，执行步骤四四；

步骤四四、判断当前游程编码标号是否大于比对标号，如果是进入下一步；如果否，回到步骤四二；

步骤四五、按读取的游程编码记录的起始行、起始列和终止列寻址星点像素，将读取的像素数据代入质心计算公式；

步骤四六、判断游程编码的链接地址是否为零，如果是，计算输出一次质心坐标，将当前游程编码标号赋值给比对标号，回到步骤四二；如果否，取游程编码的链接地址，寻址邻接的游程编码，返回步骤四五。