面向FPGA的连通域快速标记方法

王 凡，周国清，张荣庭，刘德全

1.天津大学 精密仪器与光电子工程学院，天津300072

2.天津大学 遥感研究中心，天津300072

3.桂林理工大学 广西空间信息与测绘重点实验室，广西 桂林541004

4.天津大学 微电子学院，天津300072

1 引言

我国海域辽阔，利用卫星对海面舰船目标进行检测在军用和民用领域均受到越来越多的重视，在卫星上完成舰船目标实时检测，可以避免星地传输和地面处理的巨大压力。在图像处理、目标检测、模式识别等领域，连通区域标记算法常作为目标候选区域特征提取环节的必要步骤而有着广泛应用。在基于光学遥感图像的舰船检测的工程应用中，使用现场可编程门阵列（Field Programmable Gate Array，FPGA）实现图像处理与目标检测等功能。与可以流水线实现的图像滤波、阈值分割等算法相比，连通域标记算法往往需要消耗更多的硬件资源与处理时间。因此，如何高效地实现连通域标记算法是满足实时性要求的关键。

Rosenfeld 等人[1]提出的两遍扫描算法是经典的连通域标记算法。赵菲等人[2]提出基于等价标号的二次扫描连通域标记算法，结合基于像素扫描方法和基于游程编码方法的优点，按像素逐行扫描，以线段形式进行标记。王尧等人[3]采用单次扫描的连通域标记算法，在扫描过程中记录当前元素邻域内的标号。凌璐祥[4]提出游程-连通域数据映射结构，采用三个双端口RAM作为保存媒介，分别保存当前行游程、上一行游程和连通域，无需建立等价表。黄金宝等人[5]提出基于轮廓跟踪的一次扫描连通域标记优化算法。王凯等人[6]设计了基于图像分块的连通域标记算法，将连通域标记与去噪处理相结合。冯海文等人[7]通过最小标号传播处理，将多次扫描算法改进为一次扫描算法。张国和等人[8]提出了一种适于硬件的快速连通域标记算法，该算法以游程为基本单位，采用一次扫描和等价游程对合并的方式完成连通域标记。谭许彬等人[9]设计一种基于FPGA的连通域标记电路，通过对图像进行一次像素扫描，标记连通域并统计参数信息。王凯等人[10]利用游程编码优化标号生成算法，减小临时标号数量和等价表长度，并基于FPGA实现。文献[11]提出游程和链表结合的连通域标记方法，以游程技术分配临时标签，再利用链表结构构造等价标签之间的关系。文献[12]设计了一个图像组件标记和特征提取模块并在FPGA上实现。文献[13]设计了基于FPGA的单次扫描连通域标记架构。文献[14]提出了一种通过将图像分割成切片来实现加速的单通道连通分量分析架构。文献[15-16]也提出了基于FPGA 的连通域标记方法设计。以上方法中一部分方法[1，2，6]需要对图像进行两次或多次扫描来完成连通域标记，导致了处理时间的增加，不利于满足实时性要求；一部分方法[3，5，7-12，14-16]则对图像进行一次扫描，但需要借助临时标记表来进行连通域标记，使得硬件资源的消耗量增加。

本文在对近些年的二值图像连通域标记算法进行总结与分析的基础上，设计一种基于游程的连通域快速标记算法，基于FPGA 实现，并作为遥感图像舰船检测硬件系统的一个模块。结合遥感图像舰船目标的特点，针对现有方法在重复扫描和临时标记表上花费较多的处理时间与硬件资源的问题，该方法以游程为单位对像素进行批量处理，不产生临时标记表，对图像进行一次扫描完成连通域标记。结合星上检测应用中对实时性的要求，设计基于FPGA的硬件架构，描述关键模块，对所设计的硬件模块从资源占用与时间消耗两方面进行优化设计，并进行仿真分析和实验验证。结果表明，该模块能高效实现连通域标记，与文献[9]相比运行速度提高了约1 倍，与文献[8]相比资源消耗显著降低，满足工程应用的要求。

2 二值图像连通域快速标记算法

2.1 算法基础

文献[17]将连通域标记算法分为一次扫描算法、二次扫描算法和多次扫描算法。目前常用的一次扫描算法通常是以游程为基本单位的处理方法，二次扫描算法和多次扫描算法通常是以像素为基本单位的处理方法。以像素为单位的描述方法需要逐像素处理，以游程为单位的描述方法则需要对像素进行批量处理，因此以游程为基本单位的处理方法往往比以像素为基本单位的处理方法更高效。

基于游程的算法将二值图像每一行中连续的前景像素视为一个游程，并记录游程的起点、终点、所在行以及赋予的标记；然后判断相邻行的游程是否存在连通，如果是则标记为等价对；之后遍历游程的标记，将等价对中的游程进行标记合并。对于二值图像，游程开始和结束的判定依据是：当目标像素与前一个像素的值构成“01”时，表示游程的开始；当目标像素与前一个像素的值构成“10”时，表示游程的结束。对于8 邻域连通情况，判断当前行的游程与上一行的游程是否连通的关系式如下：

其中，Y0、Y1表示当前行游程的起点和终点列坐标，y0、y1表示上一行游程的起点和终点列坐标。

当判定两个游程存在连通情况时，算法通常将这两个游程标记为等价对，并将等价关系存储到临时标记表中，再通过遍历临时标记表来完成等价对的标记统一。临时标记表的存在增加了方法的时间和资源消耗。

本文对多幅遥感图像中舰船目标的特点进行分析，如图1所示舰船目标的形状通常比较规则，不存在类似图2中的复杂的连通域情况，连通域中的游程通过相邻行之间的标记传递即可完成标记统一，因此不需要借助临时标记表。本文借鉴已有研究中一次扫描的算法，对连通域标记方法进行设计，以游程为单位对像素进行批量处理，不记录等价对，不产生标记表，在像素扫描过程中逐行地记录游程信息，同时并行地对已记录的游程进行标记合并处理。

图1 遥感图像中的舰船目标

图2 复杂的连通域

2.2 连通域快速标记算法设计

在图像连通域的描述中，常用4 邻域连通和8 邻域连通两种方法，因为8 邻域连通更为全面，通用性好[18]，所以本文以8邻域连通进行连通域快速标记的设计，采用光栅扫描的方式，以游程为基本单位对像素进行批量统计。如图3所示，本文设计的连通域快速标记算法包括游程记录、连通游程标记合并和连通域的特征提取几个主要环节。

图3 连通域标记算法流程图

（1）游程记录。对二值图像进行光栅扫描，即逐行地从左到右读入图像像素，判定行内的所有游程，并依次赋予游程不同的标记编号，将各个游程的标记编号、左右端点坐标和行坐标记录到数组mem_a 中。对于每行的开始处和结束处，若每行的第一个像素的值为1，则记录为一个游程的开始；若每行的最后一个像素的值为1，则记录为一个游程的结束。

（2）连通游程标记合并。从扫描到第三行像素起，将之前两行中的游程依次进行端点坐标的比较。若满足关系式（1），则判定游程连通，将上一行的游程标记赋予当前游程。若多个游程之间存在连通的情况，则将这些游程中的最小的标记赋予其他游程，如图4 和图5 所示。将所有的连通游程合并完成后，具有同一标记的游程便同属一个连通区域。

图4 相邻行游程之间可能存在的连通关系

图5 连通游程标记合并

（3）特征提取。对已完成标记合并的游程进行统计以提取连通域的特征，并且判断已经扫描过的图像中的连通域是否都完成了标记。如果没有完成，则继续第二步的等价游程标记合并；如果已完成，则将提取到的连通域特征输出。

3 基于FPGA的硬件架构设计

3.1 FPGA硬件结构

如图6所示为舰船目标检测环节的硬件架构，其中连通域标记是重要步骤，是进行特征提取的前提和基础。如图7所示为本文设计的基于FPGA的连通域快速标记模块的硬件架构，包括游程信息记录和连通游程标记合并两部分。本文采用1 000×500大小的光学遥感图像，对其中的舰船目标的连通区域进行快速标记。经过预处理和分割处理后的二值图像通过RAM读写模块以光栅扫描的方式逐个像素地输入到硬件电路中，以连续的两个像素数据为一组输入到游程信息记录模块。游程信息记录模块判断游程的开始和结束，生成游程标记，并将游程的标记、左右端点坐标与行坐标记录到存储器mem_a 中，将各行的游程数目累加起来记录到存储器k 中。从记录完第二行的游程开始，连通游程标记合并模块判断前两行的游程之间是否连通，将连通的游程进行标记合并，不连通的游程跳过。之后，连通域特征提取模块读取游程信息与游程连通判断结果，如果有连通域被记录完，则输出提取到的该连通域的特征。

图6 舰船目标检测环节的硬件架构

图7 连通域快速标记模块硬件架构

在连通域标记的电路中，游程信息记录模块和连通游程标记合并模块是关键模块，下文将分别进行详细的设计说明，并且对后续模块的设计思路进行简要说明。

3.2 游程信息记录模块

该模块的设计思路为：对输入的两个连续像素，依据它们的值判断游程的开始点和结束点；并根据RAM读写模块的读地址判断行坐标；数组mem_a 的一个元素对应一个游程的信息。

定义一个存储位宽为40位，存储深度为1 536的存储器mem_a，其每个存储单元存储一个游程的全部信息，高11 位存储游程的标记，之后9 位存储游程的行坐标，之后10位存储左端点坐标，最后10位存储右端点坐标。定义一个存储器地址信号j，其值在每存入一个游程信息后加1。定义一个行计数器信号i，其值在每读入一行像素数据后加1。定义一个存储位宽为11位，存储深度为500的存储器k，记录各行及其以前行的游程数目之和，即k[i]与k[i-1]之差为第i 行的游程数目。所定义的相关信号的信息如表1所示。

表1 游程信息记录模块的信号

该模块的工作过程为：通过读写控制模块依次读取图像像素，两个reg 型变量将相邻的两个像素进行存储，在同时传递给游程判断模块。当输入的相邻两个像素的值满足“01”的组合时，产生写使能信号，将当前的值为1的像素点的行坐标和列坐标，以及生成的标记值写入mem_a 存储器中；当输入的相邻两个像素的值满足“10”的组合时，产生写使能信号，将当前的值为1 的像素点的列坐标写入mem_a 存储器中，并使j 的值增加1。通过RAM的读地址对行坐标进行计数，并计算当前的列坐标；像素的行坐标、列坐标与存储地址的关系为：

其中，x 表示行坐标，y 表示列坐标，raddr 表示存储地址，实验用图像每行像素数量为1 000。mem_a 存储器在接受到写使能的信号后，记录当前游程的信息，当接收了游程开始点和结束点两次的写使能信号后，当前游程的全部信息才记录完毕。

3.3 连通游程标记合并模块

该模块的设计思路为：读取行计数信号，从行计数大于等于3起，从mem_a 存储器中读取前两行的游程信息，从左到右依次比较相邻行的游程的端点坐标，以判定游程是否连通，如果游程连通，则对标记进行合并。

定义两个integer型变量m 和n 作为从存储器mem_a中读取数据的地址，用于遍历各相邻行的游程，m 和n的取值范围如下所示；

定义两个计数器信号count_1 和count_2，用于判断游程连通情况时的时序控制；定义一个计数器信号num，用于记录游程之间存在连通情况的数目。信号的相关信息如表2所示。

表2 连通域标记合并模块的相关信号

该模块的工作过程为：根据行计数信号i 的值将存储器k 的值读取出来，经过计算得到m 与n 的值。连通判断模块读取mem_a[m]和mem_a[n]的信息并进行比较，若存在连通情况则将合并标记按对应的地址写入存储器mem_a 中，并使num 加1；若不存在连通情况则信号num 不变。

3.4 后续模块的处理

游程连通判别模块的行计数信号i 和连通计数信号num 输入到特征提取模块。随着信号i 每变化一次，特征提取模块从存储器mem_a 中依次读取各个游程的信息进行统计，以提取连通域的特征。同时对信号num进行一次比较，若其值不为0 且不变，则表明已有连通域被完整记录，将所提取的连通域的特征输出；若信号num 的值有变化，则表明当前涉及的连通域还没有被记录完整，继续进行特征提取。

目标判别模块对已提取的特征进行判断，将不满足条件的连通域排除，将满足条件的连通域框选出来。

4 实验分析

本文采用Xilinx 公司的Virtex-7 系列FPGA 作为硬件平台，采用Vivado设计套件作为开发环境。采用Verilog硬件描述语言进行连通域快速标记模块设计和仿真。图8 所示为连通域快速标记模块的仿真时序图。图9所示为存储器mem_a 的部分值的时序变化情况。如mem_a[259] 的初值为0，之后记录的游程信息为208349fa9c，经过连通游程标记合并后其值变为05e349fa9c，所记录的游程其标记由260变为47。

下文将从时间消耗、资源占用和处理结果等方面进行分析。

4.1 时间消耗

假设所处理的图像高为H ，宽为W ，每行所包含的游程数目不超过n，电路工作的时钟周期为clk，则两行游程连通情况的处理时间最大为(2n-1)×clk。每行像素数目为W ，读入一行像素的时间为W 个时钟周期。本文的连通域标记电路模块从扫描到第三行像素数据起，比较前两行游程的连通情况。在读完当前一行像素前，已经处理完前两行的游程连通情况。当一幅图像的全部像素被读入后，最多还需要(2n-1)×clk 的时间来处理最后两行的游程连通情况。因此，该连通域标记电路处理一幅图像的时间不超过(W×H+2n-1)×clk。

因为对二值图像的连通域标记必须要将图像至少扫描一遍，所以该处理环节的处理时间最少为扫描整幅图像的时间Tmin=W×H×clk 。本文的设计在处理时间上已无限接近Tmin，若图像最后一行的像素值均为0，则连通域标记的处理时间等于Tmin。文献[9]设计所需处理时间为t=(W×H×2+L×4)×clk，其中L 为连通域的最大上限。与文献[9]相比，本文的设计的处理时间提高了约1倍。

4.2 资源耗费

本文设计的连通域标记模块对资源的耗费主要在于对信息的存储，如表3所示，为对1 000×500大小的二值图像进行连通域标记所需的存储资源。其中，对于游程记录存储器mem_a 的定义，由于图像实际中的游程数远小于理论值W×H/4，根据对多幅舰船遥感图像中的游程数量统计定义一个合理存储深度的存储器，本文对1 000×500大小的图像定义的存储器深度为1 536位。

表3 存储资源耗费

对于游程信息的统计和整理，文献[8]的方法需要5个存储器记录临时标记集合中所有标记的排列顺序，1个存储器记录临时标记集合的结束点，1个存储器记录临时标记集合中所有标记的排列顺序。而本文方法只需要1个游程信息存储器和1个游程数目存储器即可完成游程的记录和整理，对存储资源的消耗更小。在图像大小为2 048×1 536 的情况下，两种方法的存储资源消耗如表4 所示，相比之下，本文的设计对资源的消耗大幅降低。

图8 连通域快速标记模块仿真时序图

图9 mem_a 中的部分值

表4 存储资源消耗对比

4.3 连通域标记处理结果

选取多幅舰船目标的遥感图像进行实验，其中部分结果如图10 所示，每行为一幅图像的二值图（左）和最终的舰船检测结果图（右）。图像大小均为1 000×500，工作频率为f=100 MHz，由于这两幅图像的最后一行像素中不存在游程，故在对整幅图像进行一次扫描的时间内，连通域标记操作也顺利完成，时间消耗为5 ms，满足工程应用中的实时性要求。

图10 二值图像及检测结果

5 总结

本文提出了一种面向遥感领域舰船目标检测的连通域标记方法及其硬件设计。本文采取的连通域标记策略，只需要扫描整幅图像一次，记录各行的游程信息并合并连通游程的标记，后续对连通域进行特征提取时依次统计相同标记下的游程信息即可。本文的方法不产生临时标记表，在像素扫描过程中对已记录的游程完成标记合并。在运行时间方面，本文的设计对于最后一行都是背景像素的图像可以在一次扫描像素的过程中完成连通域标记，对于最后一行包含游程的图像可以在一次扫描像素后的有限个时钟周期内完成连通域标记。在资源占用方面，本文的设计只需要一个游程信息存储器和一个游程数目存储器即可完成对全部游程的信息统计，不产生临时标记表，对存储资源的消耗很小。因此，本文提出的对于遥感图像舰船检测中的连通域标记方法和硬件设计是简洁高效的。