FPGA连通域标记CCL：游程编码、等价表与上板避坑

简介：面向FPGA图像处理开发者的一套二值图像连通域标记算法实现工程，聚焦实时性要求较高的嵌入式视觉场景。算法仅需片上缓存若干行图像数据，即可在固定行延时内输出标记结果，全程不依赖外部SRAM或DDR，适合资源受限的前端流水线部署。压缩包共592个文件，约1.82MB，以tcl脚本、vhd与v/sv源码、sh与bat批处理、do仿真脚本及txt说明为主，另含ucf/xdc约束、xise/gise工程文件与ngc网表，覆盖综合、仿真、约束与板级验证的完整链路，asy与sym文件则为IP核与符号封装提供支持。已有1659人学习下载。读者可从中获得可综合的Verilog/VHDL源码、仿真与综合脚本、时序约束模板及工程配置流程，便于对照理解行缓存调度、标记合并与延时控制的具体实现，并直接复用到自有FPGA视觉项目中。

1. 从一条 1080p 产线说起：这份 FPGA 连通域代码包解决的是什么问题

产线上做表面缺陷检测，相机每秒吐 60 帧 1080p 二值图，工控机上一遍连通域标记要几十毫秒，帧立刻就堆起来了。把 FPGA 算法流水线化、让连通域标记跟着像素时钟走，是这类场景里最直接的一条路。这份连通域代码.zip 给的就是一套可综合的硬件实现：像素流进、游程编码、等价表合并、标号流出，中间不留帧缓存。它适合已经能写 Verilog、正在找一份能仿真能上板能改参数的 CCL 参考实现的人，也适合拿它当课程设计或项目预研的底座。它不教你语法，它把连通域在硬件里的数据通路和边界条件摊开给你看。

2. 拆开代码包：像素流、游程流、标号流的三段式结构

拿到一个 CCL 的 RTL 包，先别急着看顶层端口。先确认它走的是哪条技术路线——逐像素标记、游程编码、还是分块并行。这三条路在资源、延迟、可扩展性上差得很远，选错了后面全是返工。这份代码走的是游程（run-length）路线，也是工业检测场景里最常见的一种：前景稀疏、分辨率高、行内连续段多，用游程把像素压缩一遍，后面的等价表规模立刻降一到两个数量级。

2.1 顶层数据通路：为什么中间要插一层游程

逐像素做 CCL 的思路很直白：每个像素看左、上两个邻居（4 连通）或左上、上、右上三个邻居（8 连通），能并就并，不能并就开新标号。问题是这要求你随时能读到上一行的标号，一行 1920 个 16bit 标号就是 30Kb，还得支持随机访问，BRAM 端口根本不够用。更要命的是等价关系会跨行传播，一条斜线能把整幅图的标号串成一条长链，查找根的路径深度不可控。

游程路线把问题换了个维度。先在行内把连续的前景像素压成[x0, x1]这样一段，一条游程只需要记起止列和一个临时标号。游程和游程之间的连通判断只做区间重叠比较，不涉及逐像素访问。上一行的游程列表按x0升序存在一小块 BRAM 里，本行游程也是升序产生的，两边用双指针归并扫一遍就够，复杂度是 O(n+m) 而不是 O(W×H)。

代价是输出形态变了。逐像素方案可以做到输入输出同序、延迟固定；游程方案在扫描完整幅图之前，没办法确定每个游程的最终根标号，因为后面出现的游程可能把前面两个等价类合并掉。所以中间一定有一层「临时标号 + 等价关系」，最终标号要么靠片内状态机回写，要么把等价表吐给后级。

我一般会把代码包里的模块按这个顺序理一遍：

像素输入 (8bit 灰度 + hsync/vsync/de) │ ├─ 二值化 (阈值可配，输出 1bit) │ ├─ 行内游程编码 (run_length_encoder) │ └─ 输出: {y, x0, x1, tmp_label} │ ├─ 游程归并 + 等价表更新 (run_merge / union_find) │ └─ 输出: 等价对 (a, b) 或直接写 parent[] │ └─ 标号输出 (label_writer) ├─ 模式 A: 输出临时标号流，等价表交给后级 └─ 模式 B: 片内缓存游程表，帧末合并后回写

模式 A 的延迟小、BRAM 省，但后级必须能接受「同一区域在不同行上标号不同」这件事；模式 B 用起来舒服，可一旦分辨率上去，游程表的存储量会很难看。以 1080p 为例，假设每行平均 32 条游程，1080 行就是 34560 条，每条记x0(11) + x1(11) + label(16) = 38bit，接近 160KB，片内 BRAM 根本放不下，必须外挂存储。所以绝大多数能上板的实现都是模式 A，把合并这件事推到帧末或者干脆推给 CPU。

提示：拿到包先搜一下顶层有没有frame_done或者eq_flush这类信号。有，说明它至少考虑了帧末合并；没有，说明它只输出临时标号，别指望直接拿到最终结果。

2.2 游程编码模块：行缓冲到底要不要，边界怎么收

很多人第一次写游程编码会本能地加一个整行 line buffer，其实没必要。行内游程只依赖当前像素和前一个像素的状态，一个 1bit 的run_active寄存器就够。真正需要缓存的是「上一行的游程列表」，那是给归并模块用的，不是给编码模块用的。

核心逻辑就是一个上升沿开游程、下降沿闭游程的状态机：

// 行内游程编码：de 有效期间逐像素推进 // H_ACTIVE 为行有效像素数，x_cnt 为列计数 always @(posedge clk or negedge rst_n) begin if (!rst_n) begin run_active <= 1'b0; run_start <= {XW{1'b0}}; run_valid <= 1'b0; end else if (de) begin if (bin_pix && !run_active) begin // 0 -> 1，开一条新游程 run_active <= 1'b1; run_start <= x_cnt; end else if (!bin_pix && run_active) begin // 1 -> 0，闭合游程并输出 run_active <= 1'b0; run_valid <= 1'b1; run_end <= x_cnt - 1'b1; end else if (x_cnt == H_ACTIVE - 1 && run_active) begin // 行末强制闭合，这是最容易被漏掉的一条分支 run_active <= 1'b0; run_valid <= 1'b1; run_end <= x_cnt; end end end

三个地方值得盯着看。第一，x_cnt - 1在x_cnt = 0时会下溢，虽然正常流程下!bin_pix && run_active不可能在x_cnt = 0成立（游程至少有一个像素），但复位后第一拍的残留状态会让它发生，所以run_active必须在vsync或者de下降沿清一次。第二，行末那条分支不能省，一条游程顶到行尾时没有下降沿，不强制闭合就会丢一段，表现出来就是图像右边缘的区域少一块。第三，run_valid只拉高一拍，下游必须能接住，或者改成握手。

参数上只有两个要定：XW = $clog2(H_ACTIVE)，1080p 下是 11；YW = $clog2(V_ACTIVE)，也是 11。别图省事全用 16bit，等价表和游程表都是按条数乘位宽算容量的，省下来的每一位都是 BRAM。

2.3 等价表：并查集上硬件，还是老老实实记等价对

这是整个包里最见功力的地方。软件里并查集随便写，路径压缩一加，均摊复杂度接近常数。硬件里不行，find是一次次串行跳 BRAM，每次读有一到两拍延迟，最坏情况下一條链能跳几十次，时序和延迟都不可控。

代码包里通常能看到两种实现。一种是真并查集，parent[]存 BRAM，find用状态机迭代，跳数上限写死成 8 或者 16，超了就直接把当前节点当根——这会引入极低概率的错误合并，但在实际图像里几乎不会触发，因为等价链的深度通常不超过 4。另一种是等价对表，遇到(a, b)冲突就往表里写一条，帧末统一做一次离线合并，好处是写路径简单、时序好收敛，坏处是后处理跑不掉。

并查集的查找状态机大概长这样：

// 迭代式 find，最多 MAX_HOP 跳，防止病态链拖死流水线 localparam MAX_HOP = 8; always @(posedge clk or negedge rst_n) begin if (!rst_n) begin state <= S_IDLE; end else case (state) S_IDLE: if (find_req) begin cur <= find_label; hop <= 0; state <= S_RD; // 发起第一次 BRAM 读 end S_RD: begin // BRAM 读延迟 1 拍，这里等数据回来 par <= parent_dout; state <= S_CMP; end S_CMP: begin if (par == cur || hop == MAX_HOP - 1) begin root <= cur; // 到根，或跳数耗尽强制截断 state <= S_DONE; end else begin cur <= par; hop <= hop + 1; state <= S_RD; end end S_DONE: begin find_ack <= 1'b1; state <= S_IDLE; end endcase end

MAX_HOP是这里最关键的参数。设小了，长链会被截断，产生「本该合并却没合并」的错标；设大了，单次查找的延迟上去，如果上游是背靠背产生游程的流水线，很快就会被反压。我的经验值是 8，配合「按秩合并」或者「小标号优先」的 union 策略，实际触发截断的概率低到可以忽略。另外parent的 BRAM 用一个简单双口就够，一口读一口写，读优先模式要配对，否则同一拍读写同一地址会读到旧值。

parent的初始化也别忘。BRAM 上电内容是随机的，parent[i] = i这个自反关系必须在帧起始或者复位时刷一遍。深度 2048 的话刷一遍要 2048 拍，1080p 一行 2200 拍，放在行消隐里刚好，但很多包图省事只在全局复位时刷，结果第二帧开始就出鬼标号。

3. 上板之前先把仿真跑穿：Python 黄金模型与逐级比对

RTL 写完直接上板看画面，是最费时间的调试方式。连通域这东西出错的表现又特别隐蔽——标号错了一位，画面上看就是某块区域颜色不对，你根本判断不了是游程编码漏了、等价表溢出了、还是合并顺序有问题。合理的做法是在仿真阶段就把中间结果全部拉出来，和一份 Python 参考模型逐级对齐。

3.1 用 30 行 Python 造一份可信的黄金参考

参考模型不需要快，需要的是「绝对不会错」。所以别用现成的库函数直接出结果，自己写一遍 BFS，邻域定义和 RTL 严格对齐，4 连通就是 4 个方向，8 连通就是 8 个方向。

import numpy as np from collections import deque NB8 = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] NB4 = [(-1,0),(0,-1),(0,1),(1,0)] def ccl_label(binary, conn=8): """输入 HxW 的 0/1 数组，输出 int32 标号图，背景为 0""" h, w = binary.shape labels = np.zeros((h, w), dtype=np.int32) nb = NB8 if conn == 8 else NB4 cur = 0 for y in range(h): for x in range(w): if binary[y, x] and labels[y, x] == 0: cur += 1 labels[y, x] = cur q = deque([(y, x)]) while q: cy, cx = q.popleft() for dy, dx in nb: ny, nx = cy + dy, cx + dx if 0 <= ny < h and 0 <= nx < w \ and binary[ny, nx] and labels[ny, nx] == 0: labels[ny, nx] = cur q.append((ny, nx)) return labels

比对标号的时候有个必须绕开的坑：标号的具体数值没有意义，只有分区关系有意义。你的 RTL 可能从 1 开始分配，Python 也从 1 开始，但两边扫描顺序不同，同一个区域的编号大概率对不上。直接np.array_equal会得到满屏红。正确的比法是建一个双向映射，检查「RTL 里标号相同的任意两个像素，在 Python 里也相同」：

def same_partition(a, b): """a/b 为两张标号图，判断是否表达同一个分区""" fwd, rev = {}, {} for va, vb in zip(a.ravel(), b.ravel()): if va in fwd and fwd[va] != vb: return False if vb in rev and rev[vb] != va: return False fwd[va], rev[vb] = vb, va return True

这个函数一跑，很多「看着像错了其实没错」的误报立刻消失，省下的时间够你把真正的 bug 找出来。

3.2 Testbench：激励怎么造，超时怎么兜

激励不要只用随机噪声。随机图很难覆盖游程的极端情况，比如整行全 1、整行全 0、单像素宽的对角线、贴边区域、棋盘格。我一般会准备一组固定场景加一组随机场景，固定场景负责覆盖边界，随机场景负责跑回归。

initial begin // 从文件读入激励，每行一个十六进制像素值 $readmemh("frame_1920x1080.hex", img_mem); // 逐行驱动 de / hsync，行消隐和场消隐按真实时序留够 for (int y = 0; y < V_ACTIVE; y++) begin for (int x = 0; x < H_ACTIVE; x++) begin de <= 1'b1; din <= img_mem[y*H_ACTIVE + x]; @(posedge clk); end de <= 1'b0; repeat (H_BLANK) @(posedge clk); end end

超时保护是必须加的。CCL 的状态机一旦进了死循环（等价表溢出后回绕、find 跳数没收敛），仿真会一直跑下去，你以为在算，其实早卡死了。写一个计数器，超过3 * H_TOTAL * V_TOTAL拍还没等到frame_done，直接$fatal报出来，比等半小时强。

输出侧建议同时落两份文件：一份是最终标号流，一份是中间量——每条游程的{y, x0, x1, tmp_label}，每个等价对(a, b)。这两份文件在 Python 里能直接和参考模型对比，定位速度比看波形快一个量级。

3.3 观测点：波形看什么，打印看什么

波形不是给你从头看到尾的，是给你在已经缩小范围之后确认假设的。真正高效的调试顺序是：先比中间文件，定位到是游程层错了还是合并层错了，再开波形看那几拍。

三个关键观测点：run_valid拉高时run_start和run_end是否和 Python 算出来的一致；eq_wr_en有效时写入的等价对有没有出现「自己和自己」这种无效对；frame_done之后parent[]里的根数量是否等于 Python 的连通域个数。第三个尤其管用，它把「标号分配错」和「合并漏了」这两种完全不同的故障直接分开了。

4. 参数怎么定：位宽、深度、BRAM 预算与时序收敛

一份 CCL 代码能不能直接改成你项目要的样子，取决于它的参数化程度。理想情况下，改分辨率、改连通性、改最大标号数都只动parameter，不动逻辑。实际拿到的包往往只参数化了一半，剩下的写死在 case 或者位宽里，得自己补。

4.1 位宽：每一位都是 BRAM

坐标和标号的位宽是资源的大头，尤其是游程表和等价表，都是「条数 × 位宽」的乘积。用$clog2推，别手写 16。

LBLW这块要留余量。1080p 的缺陷图理论上最多能有H*W/2个独立区域（棋盘格），但实际上限受游程表深度约束，MAX_LABEL = MAX_RUN就够了。如果等价表深度是 2048，LBLW = 11理论上够，但为了避免溢出回绕，一般还是给 16。

4.2 行缓冲和等价表的 BRAM 账

真正占 BRAM 的是这几块，按 1080p、单口 18Kb 块估算：

「上一行游程表深度按一行最多游程数设」这句话值得单独说。很多人一看 1920 宽就设 1920 深，白白浪费 7 倍 BRAM。实际一行最多能有多少条游程？最坏情况是10101010...，960 条。所以要么按 1024 设并接受极端图超限，要么加溢出计数值告警。我一般设 1024，同时在溢出时拉一个run_overflow状态位到寄存器，软件读回来能看到。

4.3 时序：并查集是路径最长的那个模块

100MHz 以下基本不用操心，148.5MHz 的 1080p60 像素时钟就要认真算账了。最长的组合路径通常出现在find的比较分支和 BRAM 输出的直连上。两个改法：把parent_dout打一拍再用，接受多一拍延迟；或者把find的迭代拆成多个周期，状态机里本来就可以拆。

跨时钟域是另一个雷区。像素时钟和配置总线时钟大概率不同源，阈值、分辨率、连通性这些配置寄存器必须做同步，别用两级触发器糊弄多 bit 信号。简单做法是配置寄存器只在vsync下降沿之后、de上升沿之前更新，靠帧边界天然隔离。

注意：综合报告里的 BRAM 推断数对不上时，先看是不是被推成了分布式 RAM。parent[]这种带异步读的数组，在部分工具里会掉到 LUTRAM，资源瞬间爆掉，加个(* ram_style = "block" *)属性按住它。

5. 避坑记录：五个让我返工的现场

下面这几条都是实际踩出来的，不是从手册上抄的。每条的排查顺序都是「先看现象、再定位原因、最后给改法」，照这个顺序走能省不少时间。

5.1 标号全对但比对全红：分区一致性被当成数值一致性

现象：仿真跑完，把 RTL 输出的标号图和 Python 结果叠在一起看，区域形状完全一致，肉眼找不出差别，但逐像素比对报了几万个不一致。

原因：RTL 的标号分配顺序和 Python 的 BFS 顺序不同。Python 从左到右扫，第一个连通域拿 1；RTL 可能因为游程合并顺序，第一个区域拿了 7、第二个拿了 3。数值不同不代表分区不同。

解决：比对函数换成等价类映射，也就是 3.1 节那个same_partition。再进一步，可以在 RTL 输出侧加一个「标号归一化」后处理，把标号按首次出现顺序重排成 1、2、3……，这样和 Python 直接逐像素比也不会误报，代价是多一块小映射表。

5.2 对角线上的两个像素被并成一个区域：4 连通和 8 连通没对齐

现象：一张只有单像素宽对角线的测试图，参考模型算出 N 个区域，RTL 算出 N/2 个，合并过头了。

原因：8 连通判断里，游程区间比较要往外扩 1 像素，也就是a0 - 1 <= b1 && b0 - 1 <= a1。这个「扩 1」如果没做，8 连通会退化成 4 连通；反过来，如果 4 连通的代码里误抄了扩 1 的写法，4 连通就变成了 8 连通。两种错都会让对角线场景直接翻车，而且只在斜线密集的图上才看得出来。

解决：把邻域定义做成一个parameter CONN_8 = 1，扩 1 的量写成CONN_8 ? 1 : 0，别在两处分支里各写一遍。另外注意a0 - 1在a0 = 0时会下溢成11'h7FF，比较结果直接反了。正确写法是先判断a0 == 0，或者把坐标扩一位做有符号比较。

5.3 第二帧开始标号乱飞：BRAM 里的等价关系没清干净

现象：第一帧完全正常，第二帧开始出现大量不该合并的区域，第三帧更糟，复位一下又好。

原因：parent[]在 BRAM 里，掉电内容和上电内容都不受你控制。只在全局复位时刷一次parent[i] = i，之后每帧新分配的标号直接复用旧槽位，旧的父子关系还留在里面，find一查就跳到上一帧的根上去了。

解决：两种改法选一个。稳妥的是每帧在vsync期间刷一遍parent[]，深度 2048 就是 2048 拍，行消隐里完全够；省资源的是加一个「帧版本号」，每个槽位多存几位版本，版本不匹配就当自己是根。第一种简单，我一般先用第一种跑通，再考虑优化。

5.4 图像右下角总是少一块区域：行末游程没闭合

现象：所有测试图里，紧贴右边界的连通域要么丢了，要么面积少一截，往左挪一个像素就正常。

原因：2.2 节那段代码里的行末强制闭合分支被漏了。一条游程从行中间一直延伸到第 1919 列，没有下降沿，状态机就停在run_active = 1，这条游程永远不输出。

解决：在x_cnt == H_ACTIVE - 1 && de那一拍无条件闭合。另外在de下降沿也补一个兜底闭合，防止上游时序异常导致的悬空状态。

5.5 综合后时序不过但仿真全对：find 的组合路径太长

现象：功能仿真、门级仿真都过，综合报告里 setup slack 是负的，而且违例路径集中在parent[]的读地址到比较器之间。

原因：find的迭代写成了组合逻辑，parent[parent[cur]]这种嵌套在读延迟为 1 的 BRAM 上会展开成一条很长的路径。仿真器不关心延迟，所以看不出来。

解决：把find改成 2.3 节那个多周期状态机，每次读 BRAM 之间插一拍寄存器。如果还是紧，把parent拆成两块 BRAM 做乒乓，或者把MAX_HOP从 8 降到 4，靠 union 时「小标号优先」来压链长。

6. 进阶：把标号流接进后级统计与软硬协同

跑通标号只是第一步，实际项目里真正要的是区域属性：面积、外接矩形、质心。这些不需要等最终标号合并完，可以在游程流上直接累加。一条游程的面积就是x1 - x0 + 1，外接矩形的xmin/xmax直接取x0/x1的极值，ymin/ymax就是游程所在的行号范围，质心的sum_x用等差数列求和一次算完：(x0 + x1) * (x1 - x0 + 1) / 2。这些量全部用临时标号做索引存进一张属性表，帧末合并等价类的时候顺手把属性也合并掉。

// 游程流上的属性累加：一条游程一拍，不需要帧缓存 always @(posedge clk) begin if (run_valid) begin area[run_lbl] <= area[run_lbl] + (run_end - run_start + 1'b1); sumx[run_lbl] <= sumx[run_lbl] + ((run_start + run_end) * (run_end - run_start + 1'b1)) >> 1; xmin[run_lbl] <= (area[run_lbl] == 0) ? run_start : min(xmin[run_lbl], run_start); xmax[run_lbl] <= (area[run_lbl] == 0) ? run_end : max(xmax[run_lbl], run_end); ymin[run_lbl] <= (area[run_lbl] == 0) ? run_y : min(ymin[run_lbl], run_y); ymax[run_lbl] <= (area[run_lbl] == 0) ? run_y : max(ymax[run_lbl], run_y); end end

属性表深度和parent[]一致就行，位宽按最大面积算，1080p 全图也就 200 万，21bit 够用。乘以(x1-x0+1)那一步会溢出，sumx给到 42bit 比较稳。

再往前一步是软硬协同：片内只做扫描和等价对记录，帧末把等价对表通过 DMA 或者 AXI-Lite 吐给 CPU，合并和属性汇总在软件里做。这样 RTL 的时序压力小很多，换分辨率只要改软件侧的表大小，灵活性高。代价是多一次数据搬运，1920×1080 的图，等价对通常也就几千条，几 KB 的量，PCIe 或者千兆网都吃得下。

验证这块我有个固定习惯：每次改完参数，固定跑一组「全 0、全 1、棋盘格、单像素对角线、贴四边各一条线」五个场景，再跑一百帧随机图做回归，same_partition全过才算完。这套流程救过我一次——改MAX_HOP的时候把 8 写成 4，功能仿真前四个场景全过，只有对角线那个场景露了馅，因为链深刚好是 5。从那以后我每次动MAX_HOP、MAX_RUN、LBLW这三个参数，都强制把五个边界场景走一遍，不再信「仿真跑过了」这句话。希望帮到你。

本文还有配套的精品资源，点击获取