1. 从工业视觉的痛点说起为什么要把连通域标记搬进FPGA先讲一个我实际遇到的场景。某工业视觉项目里前端是高速线阵相机后端要求把视野里每个工件的面积、外接矩形、质心实时统计出来帧率不能掉。一开始团队用CPU做检测算子本身跑得还行但一到连通域标记这一环就开始吃力——图像里几百上千个目标两次遍历全图还要维护标签等价关系CPU上的随机访存和迭代查找让处理时间变得不可控。最后不得已做了个取舍牺牲ROI区域的完整性只在小窗口里做标记带来的后果就是工件粘连时漏检。后来我们转向FPGA方案才真正把这个问题解掉。连通域标记Connected Component LabelingCCL的任务说穿了很简单把二值图像里相邻的前景像素归成一个个连通区域给每个区域发一个唯一编号。但这件事在FPGA上做好难度完全不在“算法思想”而在“流的架构”。因为它天然是一个带全局状态的逐像素运算——处理当前像素时既要看它左边、上边的邻居结果又要不断合并标签等价关系还要把最终编号在第二遍扫描时替换回去。这一连串操作如果不在架构层面设计好实现出来要么资源爆掉要么时序收敛不了要么跑到一半标签错乱各种“灵异现象”全来了。这篇文章就围绕我实际做过的FPGA连通域标记架构展开从算法怎么改造成流式、顶层模块怎么划分、Union-Find等价表怎么落地到行缓存和同步控制、资源优化、调试方法一条链路讲透。适合正在做实时图像处理、工业视觉加速的硬件工程师以及想了解FPGA上怎么处理“跨像素状态”这类问题的同学参考。先把我的核心观点放在前面FPGA做连通域标记本质上是拿“硬件上的固定流水”去模拟算法里的“全局归属关系”。架构设计的目标就两个——单位像素延迟恒定以及内存访问不随机。2. 二遍扫描算法的FPGA友好化改造2.1 算法回顾为什么第一遍要记等价表连通域标记的经典算法是二遍扫描我直接说它的流程。第一遍扫描图像对每个前景像素看邻域里有没有已经分配标签的像素如果有把这个像素归入邻域标签同时把邻域中出现的不同标签记成“等价”如果四周都没有就发一个新标签。第二遍扫描的时候把所有等价的临时标签全部归并成同一个最终标签输出结果。听上去不复杂但关键点在于第一遍“看邻居”的时候会频繁出现类似这样的局面当前像素的上方属于标签A左边属于标签B而A和B其实是同一个连通分量被断开的两个分支。第一遍扫描到这时根本不知道A、B是否连通只能先把它们记成等价关系留到第二遍再统一修正。这就是等价表存在的意义——它是第一遍留下的“欠账”第二遍负责还清。2.2 CPU和FPGA处理方式的本质差异如果这段逻辑在CPU上写你大概会维护一个Union-Find数组处理每个像素时做find、union整帧结束再扫一遍parent数组输出根标签非常直观。但放到FPGA上逐像素的“流式”输入决定了我们不能随机跳到图像的任意位置去读取标签也不能像软件一样在一棵多叉树上自由回溯。所以FPGA化的第一步是把算法改造成“单方向扫描可执行”。以8邻域为例第一遍处理像素p(i,j)的时候只需要知道左上、正上、右上、左边这四个已经处理过位置的标签配合当前行、上一行的标签缓存就能完成窗口判断。这是像素流式处理的前提我们永远只依赖已经流过的数据不回头。第二遍扫描则需要把整帧的临时标签重新读一遍。这就引出一个架构决策临时标签图要不要完整存下来要存而且至少存一整帧。最简单的做法是把第一遍产生的标签图写入片上存储或DDR帧结束、等价表收敛后第二遍再读出来做替换。付出的代价是输出会延迟约一帧但换来的是架构的绝对可控。对工业视觉应用来说固定延迟一帧远远好过不定延迟三帧五帧。一个常见的误区是试图在第一遍就完成所有标记省掉第二遍。这个想法在软件上可以用复杂的单遍算法实现但在FPGA上会让单像素周期的处理逻辑爆炸——因为你在一个时钟里既要做邻域判断、又要做Union-Find查询、还要应对合并传播时序根本收不了。我见过有团队硬做单遍结果资源占用翻了几倍主频却从200MHz掉到100MHz整帧吞吐反而不如两遍流水的方案。所以老老实实的二遍扫描反而更适合硬件。2.3 游程编码与像素级方案的选型改造算法的时候还有另一条路线先做行内的游程编码RLE把每一行的连续前景段压缩成“起点、终点、标签”再对游程做合并。这种方案的内存占用小很多尤其在目标稀疏的场景里游程数量远小于像素数。但代价是逻辑复杂度显著上升——游程合并时的跨行关系、游程分裂时的标签分配都要设计对应的状态机。我个人的判断是如果单帧前景像素占比不高、目标数量不大RLE方案确实香如果图像接近纹理密集或者目标极多RLE的优势就会消失还是像素级方案更稳。下面给个对比。方案内存占用单像素逻辑复杂度延迟特性适用场景像素级二遍扫描大全帧标签图低处理逻辑固定固定约一帧通用、目标密集、时序可控RLE游程合并小仅游程表高状态机复杂取决于游程数量目标稀疏、大图高分辨率我的建议是第一版架构先用像素级二遍扫描把全链路跑通确认系统的数据率和时序模型没问题再考虑是否往RLE方向做优化。很多项目其实做到像素级就够用了没必要给自己找额外复杂度。3. 顶层架构拆解五个模块一条流水3.1 数据流与模块组成整个架构我拆成五个独立模块按像素流串联前处理模块接收外部输入做二值化如果外部只给灰度输出1bit的前景标志流第一遍扫描模块邻域缓存 临时标签分配 等价关系合并标签图存储与帧同步模块把临时标签和最终标签图按帧管理协调两遍之间的延迟第二遍扫描模块读标签图查Union-Find根节点替换输出最终标签特征统计模块可扩展在第二遍逐像素替换的同时累加每个最终标签的面积、行列和、外接矩形范围等。如果你需要输出的是“标记后的图像”那么第五个模块可以不做直接在第二遍输出根标签即可。但大多数工业场景要的不是标签图本身而是每个目标的特征值所以把特征统计放在第二遍扫描阶段几乎是零成本扩展——反正字节流都要过一遍顺手累加几个寄存器即可。3.2 关键总线设计AXI-Stream与帧同步信号几个模块之间我用类似AXI-Stream的机制连接。数据通道上是像素灰度或二值标志tvalid/tready做握手tlast标记行尾tuser标记帧首。一个容易被忽略的细节是CCL模块内部是有“帧内状态”的比如当前在走第一遍还是第二遍、当前缓存的是哪一行的数据。这些状态必须由tuser对齐而不是靠计数器猜——因为上游DMA或采集接口可能在帧间隙插入空行计数方式很容易漂移。我习惯把帧同步信号拆成“帧开始”和“帧结束”两个脉冲配合行有效信号一起输入。内部状态机只在帧开始时复位标签计数器在帧结束时关闭写入、触发第二遍调度。这样无论外部如何抖动内部都不会跨帧串扰。3.3 两个处理阶段的乒乓控制因为第二遍要读第一遍写下的标签图架构上存在“读写同一块存储”的问题。我用的方案是双缓冲第一遍扫描写Buffer A的同时上一帧的Buffer B正在被第二遍扫描读取下一帧交换。这叫乒乓控制是图像流水里最常见也最可靠的做法。双缓冲的代价是存储量翻倍。对于标签图每个像素通常用一个字节就够临时标签数控制在255以内1080p一帧就是2MB左右双缓冲4MB。这在很多FPGA上是放不进BRAM的所以必须外挂DDR。第6章我会专门讲这个问题。模块连接拓扑如下文字描述不用画图输入像素流 - 前处理 - 第一遍扫描 - 标签图写端口DDR/BRAM - 帧切换 - 第二遍扫描 - 输出根标签/特征如果要细看第一遍和第二遍的内部状态可以继续往下拆。4. Union-Find等价表整个架构里最容易翻车的模块4.1 硬件上的Union-Find怎么设计二遍扫描的“第二遍替换”依赖第一遍留下的等价表。等价表的本质是一个数组parent[N]parent[i]指向i的父节点沿着父节点一路向上能找到根。两两标签等价时做union把其中一个根挂到另一个根下面。在FPGA上我拆成三块逻辑一个双端口RAM存放parent数组一个查找FSM负责沿着链找根一个合并FSM负责把两个根接起来。逐像素处理时的大致流程是步骤A读当前像素邻域内的几个临时标签L0、L1、L2……步骤B对每个非零标签做find(L)得到各自根步骤C如果多个根不同则做union保留最小根作为当前像素标签步骤D若所有邻域标签均为零则从标签计数器取新编号。如果每像素一个时钟周期完成那么步骤B的find操作必须在几个周期内完成。这就引出一个很现实的问题等价表里链深了怎么办软件上可以做路径压缩让以后的find更快但硬件上路径压缩需要回溯改写多个节点的父指针会打破流水节奏。我的工程做法是find时不做完整压缩只在union时把深度较浅的树挂到深度较深的树下按秩合并实测链深通常被限制在几步以内。然后用一个小容量缓存在合并路径上的关键节点顺手做一次父指针更新收益已经够了。4.2 标签分配的边界条件标签计数器从0开始0固定表示背景。第一遍遇到第一个前景像素时标签计数器自增1这个1就是第一个区域的临时标签。需要注意两个边界一是标签数量上限我用8bit存储标签理论上最多255个有效标签如果一帧图像里的独立连通域超过255溢出后两个区域会被错误合并。为了解决这个问题架构里加了一个溢出检测当标签计数器达到254时把后续分配流程停住标志位置位提示上层降低图像复杂度或改用更宽标签位宽比如12bit。另一个边界是“最大等价表深度”与片上RAM容量的匹配。parent数组深度至少要等于标签上限。如果把标签宽度定为12bitRAM深度就是4096用一块小BRAM就能放下存储标签图时单个像素也用12bit。这里的取舍要结合BRAM资源来定不能拍脑袋。4.3 一个必须防止的错误第一遍里把合并结果立即写回标签图前面提到第二遍要用“最终根标签”替换临时标签。那么第一遍写入标签图的到底是“临时标签”还是“合并后的根”我的答案是第一遍写入标签图时只写当前像素的第一遍结果——也就是步骤C里保留的那个最小根标签。不要试图在这一遍里立刻把整棵等价树的最终根传播到历史像素中因为在流式处理中历史像素已经流过改不回去了。你真正能做的是保证“当前像素的标签尽量是已知范围内等价树的最小根”。剩余的修正全部交给第二遍查parent数组完成。这一点是我见过FPGA CCL实现中排名第一的问题来源开发者总想在第一次扫描时把所有标签都变成最终标签结果发现后面的像素已经合并了新的等效关系前面的像素却还是旧标签整幅图最后看起来“一部分标了区域一部分没标”而且很难复现。正确的心理模型是第一遍只是“记录归属线索”第二遍才是“拍板”。4.4 特征统计如何搭第二遍顺风车第二遍扫描的过程中每个像素都能查到最终根标签root这时候顺手做特征统计特别简单面积area[root] 1外接矩形min_x[root]、max_x[root]、min_y[root]、max_y[root]做比较更新质心sum_x[root] x坐标sum_y[root] y坐标最后除以面积。统计数组用片上RAM深度与标签上限一致。每个像素一个维度的累加功耗和资源都可控。最终输出特征时把整个统计数组经AXI-Lite或DMA一次搬给CPU即可。这个“搭便车”的设计帮我省掉了一整轮独立的特征提取模块。5. 时序与同步行缓存、帧延迟和状态管理5.1 邻域窗口与行缓存配置第一遍扫描要访问当前像素左侧、上方三个位置8邻域。左侧的标签好办用寄存器把上一拍的结果存下来即可上方的标签则需要一行之前的数据。因此需要一个长度为“一行像素数”的延迟缓存把上一行的标签图存下来。我这里说的“行缓存”是标签缓存不是原始图像缓存。宽度等于标签位宽。对于1080p、12bit标签一行是1920个像素一行缓存需要1920×12bit约23Kbit用BRAM的1-2块就能搞定。如果标签位宽只有8bit那更省。需要特别提醒的是行缓存的写入要在上升沿记录当前像素标签读出则要提前一个周期把上一行对应位置的标签准备好。处理窗口的滑移和缓存读地址的偏移必须严格对齐否则会出现“当前行标签对应的是上一行的左邻居”这类错位导致连通关系判断错乱。这种bug极难肉眼发现只能靠黄金模型比对才能暴露。5.2 帧延迟模型与同步复位策略整个架构的延迟用帧来算更清晰第一遍扫描逐行流过整帧结束时最后一行的临时标签也写完延迟约为一帧减去几行第二遍扫描需要等第一遍完全结束后才能开始读第一行标签图延迟再加一帧特征统计随第二遍同步完成不额外增加延迟。所以从像素输入到最终标签/特征输出总延迟大约是两帧。对大多数视觉应用来说两帧固定延迟完全能接受。关键是要把这个延迟做成“恒定”而不是随图像内容变化。方法很简单每次tuser帧开始信号到来时启动一个全局帧计数器第二遍调度严格按帧计数触发无论图像有没有目标、目标多少都固定走完两遍流程。同步复位策略上也有一点经验不要把复位做成全局异步复位否则每个模块复位释放时间稍有差异第一遍和第二遍的帧对齐就会漂移。我用的是“帧同步脉冲模块级状态机使能”的软复位思路每个模块只在自己的使能窗口内工作窗口结束自动回到空闲态不需要外部复位信号反复拉。5.3 行首行尾的边界处理8邻域连通在图像边界会有特殊情形第一列像素没有“左邻居”和“左上邻居”最后一列像素没有“右上邻居”。处理不好时边界上的连通域会被错误分裂。我的做法是在状态机里生成列计数信号列首时把左邻居和左上邻居强制置0列尾时把右上邻居强制置0而不是让行缓存读到任何随机值。这属于典型的“边界小逻辑”但少了它整幅图每一行的边缘都会出现不该有的标签断点。6. 资源估算与吞吐优化从1080p60到更高分辨率6.1 一份典型资源清单我以一个具体配置为例1080p60fps输入像素时钟约148.5MHz8bit标签、255个标签上限、双缓冲标签图放DDR特征统计数组放BRAM。资源占用大致如下资源用量说明BRAM行缓存2-4块上一行标签宽度8bitBRAM统计数组1-2块area/min/max/质心双口等价表RAM1块小BRAM或分布式RAM深度256逻辑单元约占2%-5%主要是状态机和查找FSMDDR带宽每帧约4MB写4MB读双缓冲乒乓读写的合计带宽1080p60下DDR带宽需求约500MB/s对于典型DDR4或DDR3足够。如果换成QHD或者4K分辨率带宽按像素数线性增长4K60可能需要接近2GB/s这时候DDR带宽分配就会紧张需要跟其他IP核做仲裁。6.2 吞吐瓶颈与多像素并行单像素处理模型下一个像素周期完成一次邻域判断和一次Union-Find查找主频能做到150-200MHz就能满足1080p60。但如果目标是4K60像素吞吐接近600M像素/s单核处理不过来。此时有两条路一条是提高主频但FPGA时序收敛到300MHz以上非常困难另一条是把处理核复制成多个每个核负责图像的一个分块分块之间增加边界标签交换。后者的逻辑复杂度显著上升因为分块边界的连通域需要跨核合并等价表也要多份协作。我做过的经验是先用单核优化到位比如把find操作流水化把不必要的握手周期去掉通常能挤出不少吞吐实在不够再考虑分块。还有一个很实用的优化点前处理里提前做二值化。如果上游直接给二值图像CCL模块可以省掉内部的二值化状态时序上省一个周期。此外把“背景判断”前置到握手逻辑里当前像素是背景时直接tready拉高不进入标签分配FSM——看似不起眼但对稀疏目标图像能大幅降低等效处理延迟。6.3 标签图存储的三种策略对比标签图存放位置是资源分水岭。我把方案的取舍列一下全放BRAM小分辨率如VGA级别、标签数少的场景最爽读写延迟固定不占DDR带宽但分辨率一大就放不下。放DDR、按帧双缓冲最通用1080p和4K都行代价是DDR带宽和帧延迟控制要交给外部存储器接口。只放行缓冲、边扫边输出这种方案是“单遍直出”的变体内存开销最小但等价标签的最终修正会跨行传播需要很复杂的逻辑才能保证正确性我不太推荐。我的工程建议是如果FPGA里BRAM富余可以先做策略1快速验证算法正确性随后再平滑迁移到策略2。因为两者的模块接口几乎一样只是底层存储从BRAM换成了DDR控制器加AXI接口。7. 调试与验证把连通域错误“定位”到寄存器级7.1 从仿真开始黄金模型比对连通域标记的bug通常不是“完全不工作”而是“偶尔错一下”比如两个区域合并了、或者一个区域裂成两半。这种间歇性错误在板上极难定位所以我的第一道防线始终是仿真而且必须带“黄金模型”。做法很简单用Python写一个标准的二遍扫描CCL输入任意构造的图像得到标准标签图同样的图像送给RTL仿真把RTL输出的临时标签、最终标签逐像素比对一旦不一致就立刻报出坐标。构造测试图像的时候不要只用规则图形我一般会随机生成几百个大小不等的矩形、圆形、以及相互粘连的团块覆盖率比手画的高得多。7.2 常见信号异常的排查链路仿真比对报错之后按下面的链路逐级查基本能定位问题查行缓存对齐比对当前像素和它四邻域在RTL里的实际信号值看窗口是否错位查等价表把Union-Find的parent数组拉出来在报错坐标附近检查是否出现了“两个根未合并”或“链深度异常”查标签计数器确认标签分配顺序是否符合预期有没有在帧内被意外复位查帧同步确认第二遍的起始行号是否真的等于第一遍结束后的第一行还是差了一行。我用一个症状对照表总结一下症状最可能原因优先排查点同一区域被拆成多块行缓存窗口错位或边界处理缺失列首/列尾的邻居强制置0多个区域被合到一起等价表合并逻辑缺失或parent数组冲突Union-Find的root查找、按秩合并标签值大范围跳变不连续标签计数器复位策略错误帧开始脉冲是否干净输出比输入延迟正好两帧但图像整体偏移第二遍读地址与第一遍写地址不同步帧计数器和行计数器的复位时机7.3 一个让我印象深刻的bug有一次板级调试总线上报回来的连通域面积总和比实际前景像素少了十几个像素而且每次都少但少的区域不固定。仿真怎么测都过不了这个场景因为我的测试向量是静态的而板上的实时图像每帧都有微小的噪声变化。后来我把第一遍和第二遍的表征信号都抓进逻辑分析仪发现每次少像素的位置都发生在图像左上角一个固定区域。继续追到行缓存写入地址发现当第一遍扫描遇到“本行为全背景行”时为了省功耗我加了一个跳过写使能的逻辑整行没有前景就不写行缓存。但第二遍读的时候上一行的缓存仍然保留着更早的数据于是对应位置的“上方邻居”错误地引用了两行前的标签把不相邻的区域串了起来。修复方式极其简单删除那个跳过写使能的优化让行缓存无论背景还是前景都按行更新。但这件事给了我一个很深的教训——在流式图像处理里任何“根据图像内容做跳过”的优化都可能破坏时序结构除非你可以证明该跳过的行绝对不会影响后续判断。大多数时候固定行为比智能行为更可靠。7.4 上板验证的经验仿真全绿之后上板验证也有讲究。我习惯分三步走第一步用内部测试图案发生器喂“纯色背景固定形状”图像验证输出标签个数和面积是否与预期一致 第二步接真实传感器数据同时用上位机软件对同一帧图像做离线CCL和FPGA输出逐帧对比 第三步长期压测至少跑一晚上看有没有偶发性的标签异常。上位机离线对比这一步特别关键因为实时场景里没有标准答案只有软件算法作为参照。只要软件模型和FPGA硬件两个实现之间出现分歧就说明至少有一方逻辑不完整。通过这种方式我定位过好几处只在真实图像上才会触发的问题比如极长条形目标的等价链深度异常以及两条目标边界恰好同像素时的合并歧义。最后的实操建议我做了几个版本的FPGA连通域标记之后最大的体会是这个设计真正的坑从不在于“算法本身难”而在于流式架构对状态的严格约束。一个看似聪明的优化如果破坏了流式处理的时序一致性代价往往比收益大得多。如果让我给刚接触这块的人一个起步路径我会建议先用纯Python把二遍扫描和Union-Find完全跑通确认算法细节然后搭一个最简单的FPGA工程模块先不追求性能像素流怎么简单怎么来跑通之后再逐步加HR流水、DDR缓冲、特征统计。每次只改一个变量出了问题能立刻定位。扩展方向上如果目标真的是超高分辨率高帧率场景可以考虑把第一遍扫描拆成多个并行分块但一定要设计好分块间的等价标签交换如果目标是低功耗嵌入式场景则可以压缩标签位宽、合并统计数组。这些后续优化都有成熟思路但前提永远是先把基础的二遍扫描流水做稳定就像盖楼前先打地基——这个地基就是前面讲的行缓存、等价表、帧同步这三板斧。