FPGA实现SAD模板匹配：从算法到Verilog的实时目标跟踪实战

1. 从图像数据流到目标坐标：SAD算法的硬件友好性拆解

做FPGA图像处理这几年，我最大的体会是：很多在软件里随手就能写的算法，搬到硬件上完全是另一回事。SAD模板匹配恰好是少有的"天生适合FPGA"的算法之一，这也是为什么很多实时目标跟踪项目的第一版原型都会选它。

SAD（Sum of Absolute Differences，绝对差值和）的原理简单到一句话就能说清：拿一个已知的目标模板，在视频帧的搜索区域内逐个位置滑动，计算模板与对应图像块的像素差值绝对值之和，和最小的位置就是目标最可能出现的地方。听起来就是一个双重循环加累加器的事，在CPU上写起来确实也就十几行代码。但放到实时视频处理场景里，事情就没那么轻松了。

以1080p@60fps的输入为例，一帧图像大约有200万个像素，留给每帧的处理时间只有16.7毫秒。如果搜索区域是100×100像素，模板是32×32像素，暴力遍历需要计算的候选位置接近一万个，每个位置要做1024次减法、取绝对值和累加。这个计算量在通用处理器上做软件优化能跑到实时，但CPU占用率基本就满了。而在FPGA上，SAD的计算结构可以被完全并行化和流水线化，同样的工作量占用资源很少，还能把整条图像处理链路的时间压到微秒级。

不过这里要提醒一句：SAD在FPGA上"好实现"不等于"随便写写就能跑"。实际工程里最麻烦的往往不是算法本身，而是数据怎么喂进来、结果怎么送出去、时序怎么收敛。所以这篇文章我会从算法公式出发，一路讲到具体的Verilog代码结构、乒乓缓存设计、时序约束技巧，最后聊一聊实测性能和踩过的坑。

先看SAD的数学表达。假设模板T的大小是M×N，搜索图像I中的候选块与模板的SAD值为：

SAD(x, y) = Σ(i=0 to M-1) Σ(j=0 to N-1) |I(x+i, y+j) - T(i, j)|

其中(x, y)是候选块左上角在搜索区域中的坐标。遍历整个搜索区域后，取SAD值最小的位置作为跟踪结果。这个公式没有任何复杂的非线性运算，只有减法、绝对值、加法三种操作，映射到FPGA上就是减法器、绝对值逻辑和加法树。整个计算链路的延迟只有几个时钟周期，吞吐量极高。

1.1 为什么模板匹配在target跟踪场景仍不过时

现在深度学习目标检测很火，动不动就是YOLO、Transformer，似乎传统方法已经被淘汰了。但实际做工程项目你会发现，很多场景根本用不上那么重的方案。

第一，FPGA上跑神经网络推理，尤其是视频流实时处理，资源开销非常大。一个稍微像样点的卷积网络，即使做了量化，也要消耗大量的DSP和BRAM资源，逻辑资源和功耗也跟着上去。而SAD模板匹配只用到加法器和比较器，几乎不碰DSP资源，逻辑资源消耗也很小，在入门级芯片上就能跑得很轻松。

第二，当目标是预先知道的小尺寸刚体（比如零件、标记点、特定纹理区域），模板匹配的精度和稳定性完全够用。目标跟踪不等于一定要做语义级别的理解，很多工业场景只需要知道"目标在画面里的像素坐标"就够了。

第三，模板匹配算法是确定性的，行为完全可预测，这对通过安全认证或功能验证非常有帮助。而深度学习模型的行为很难做到逐帧可解释。

我做过一个高速运动目标跟踪的Demo，目标是一个快速移动的小球，背景相对干净。用SAD模板匹配，在100MHz时钟下处理720p视频，单帧匹配耗时不到1毫秒，跟踪稳定，没有任何卡顿感。这要是用软件跑，单帧耗时至少翻十倍，还得面临操作系统调度带来的延迟抖动。

2. 硬件架构设计：从顶层框图到数据通路

FPGA工程和软件工程最大的区别在于，你得先把数据的"流动路径"想清楚，再谈计算逻辑。SAD模板匹配的整体架构我习惯这样划分：图像缓存与数据流控制模块、SAD计算阵列（并行比较器阵列）、最小值和坐标提取模块、以及输出与显示控制接口。每个模块各司其职，组合成一条完整的流水线。

顶层数据通路的逻辑是这样的：视频输入（可以是摄像头接口，也可以是测试用的测试图案发生器）先把像素数据写入行缓存，行缓存将数据组织成模板大小的图像块，然后送入SAD计算单元。计算单元对搜索区域内的所有候选位置并行计算SAD值（或者按行流水计算），得到一个SAD值序列，送入最小SAD追踪模块。该模块不断比较当前SAD值和历史最小值，最终输出最小SAD值对应的坐标。

2.1 搜索窗口的行缓存设计：别小看这块Buffer

SAD计算需要同时访问模板和图像中的邻域像素。如果直接从外部存储器读取每个候选块的像素，访问次数会爆炸。以32×32模板、100×100搜索区域为例，暴力读取的像素数大约是32×32×100×100 ≈ 1000万次，这在实时系统里是不可接受的。

正确的做法是用行缓存（Line Buffer）在FPGA内部构建一个滑动窗口。经典方案是：利用FPGA内部的BRAM实现N行缓存（N等于模板高度，比如32行），每来一个新像素，窗口整体右移一格，当窗口到达行尾时换到下一行。这样任意时刻窗口内都保存了当前位置周围32×32的图像块，数据复用率接近100%。

行缓存的实现有一些细节值得注意：

• 用移位寄存器还是用BRAM？模板小的话（比如8×8），可以用移位寄存器实现，延迟小、逻辑简单；模板大的话（16×16以上），建议用BRAM实现多行循环缓存，节省寄存器资源。
• 建议用两级缓存：第一级缓存原始图像的行数据，第二级缓存窗口内的数据块。这样可以把图像输入速率和计算速率解耦。
• 行缓存深度要留余量。如果图像宽度是1920，缓存深度至少是1920，但实际工程中我习惯留到2048，因为有些视频源会有行消隐和同步信号，控制逻辑更省心。

实际代码里，行缓存的经典写法是用一个二维数组 + 写指针循环覆盖。以16行缓存、每行1280像素、8bit灰度为例：

reg [7:0] line_buffer [15:0][1279:0]; reg [9:0] write_addr; reg [3:0] write_line; always @(posedge clk) begin if (data_valid) begin line_buffer[write_line][write_addr] <= pixel_in; if (write_addr == 1279) begin write_addr <= 0; write_line <= write_line + 1'b1; end else begin write_addr <= write_addr + 1'b1; end end end

这段代码维护了16行、每行1280像素的滑动窗口。窗口的读地址根据当前像素坐标动态生成，取出的16×16数据块直接对接后续的SAD计算阵列。

2.2 SAD计算阵列：并行度与资源的天平

SAD计算阵列是整个设计的核心。一次完整的SAD计算要对模板和图像块的每一个像素做减法、取绝对值、累加。在FPGA上，这个操作可以按像素级并行展开。

以16×16模板为例，理想情况下，我可以生成256个减法器和256个绝对值电路，然后通过一个加法树把256个结果累加起来。这样只用一个时钟周期就能完成一个候选位置的SAD计算。但256路并行意味着大约256个DSP48E1或大量的LUT，对资源紧张的芯片不现实。

实际工程中需要在并行度和资源占用之间取平衡。我常用的设计是把一行的16个像素做并行计算，然后按行累加：

• 16个像素并行做减法、绝对值、部分和，消耗16个减法器和16个加法器；
• 每一行的部分和在一个时钟周期内完成；
• 16行的部分和再串行累加，得到完整的SAD值。

这样只需要大约16路的并行计算资源，代价是单个候选位置需要16个时钟周期才能出结果。不过这个速度对大多数跟踪场景已经够用了。

下面给出16×16模板、行并行实现的核心Verilog框架：

// 假设win_data和template_data是16 bit位宽的16个像素 // 实际使用中应展开为16路减法器 wire [8:0] diff [0:15]; wire [9:0] abs_diff [0:15]; genvar i; generate for (i = 0; i < 16; i = i + 1) begin: sad_cell assign diff[i] = {1'b0, win_data[i]} - {1'b0, template_data[i]}; assign abs_diff[i] = diff[i][8] ? (~diff[i] + 1'b1) : diff[i]; end endgenerate wire [13:0] row_partial_sum; assign row_partial_sum = abs_diff[0] + abs_diff[1] + ... + abs_diff[15];

每一行得到一个14bit的部分和，之后在16行的尺度上做累加。这个加法树可以做成pipeline结构，每级插一拍寄存器，避免组合逻辑过长导致时序不收敛。

我实测过一个8×8模板、64路像素级并行加法树的设计，在Artix-7系列上跑到200MHz没有任何问题。如果做16×16模板全并行（256路），频率会降到150MHz左右，但对720p视频来说仍然绰绰有余。

2.3 最小SAD追踪：比大小也有讲究

SAD计算阵列不断产生候选位置的SAD值，目标跟踪需要从中选出最小的那个以及对应的坐标。这个模块看似简单，其实有一个容易忽略的性能瓶颈。

如果你在每个时钟周期都做一个"当前SAD < 历史最小SAD"的比较，那整个比较链会变得很长。比较器是有延迟的，尤其是当历史最小值需要反馈到下一拍时，组合逻辑回路很可能成为时序瓶颈。

更好的做法是流水线化比较过程：把SAD值和坐标写进一个FIFO，由专门的最小值搜索状态机来处理。状态机每次从FIFO取一个SAD值，和当前最小值比较，同时记录坐标。FIFO可以平滑计算阵列的输出节奏，让最小值搜索不阻塞SAD计算。

另一个工程细节是：不要只记最小SAD值，还得把对应的搜索位置坐标存下来。坐标需要跟着SAD值一起进FIFO，或者通过一个与SAD计算阵列同步的计数器来生成。我习惯用后者：搜索位置由行列计数器直接编码，当SAD值被判定为新的最小值时，把当前计数器值锁存到输出寄存器。

下面是这个核心比较逻辑的示意：

always @(posedge clk or negedge rst_n) begin if (!rst_n) begin min_sad <= 16'hFFFF; best_x <= 0; best_y <= 0; end else if (sad_valid) begin if (sad_value < min_sad) begin min_sad <= sad_value; best_x <= curr_x; best_y <= curr_y; end end end

注意一个坑：如果搜索区域里有多个候选位置SAD值相同，到底取哪一个？这在模板匹配里是个真实存在的问题，尤其当背景有大片平坦区域时。我的做法是"取先出现的"，即只在严格小于时更新，这样实现最简单，行为也确定。如果你需要"取中心位置"之类的策略，就得再加一个计数器记录候选位置与搜索区域中心的距离，并在SAD值相等时做二次比较。

3. 模板更新机制与多目标扩展：从Demo到工程化的距离

能跑通单目标跟踪只是第一步。真正落地的目标跟踪系统，几乎都会遇到两个问题：目标外观变化了怎么办？画面里有多个目标怎么办？

先说模板更新。固定模板在目标发生尺度变化、旋转、光照变化时，匹配效果会迅速恶化。比如跟踪一辆正在转弯的车，模板还是直着时的正面照，转过30度角之后SAD值就会暴涨，跟踪框很容易飘走。

最朴素也最有效的方案是"每N帧用当前跟踪结果区域的图像更新模板"。这样做的好处是能持续跟随目标外观变化，坏处是跟踪错误一旦发生，错误会被累积放大，也就是所谓的"模板漂移"。为了解决漂移问题，工程上常用的折中方案是：

• 保留初始模板（第一帧手工框选或检测得到的目标）；
• 每次匹配时同时计算当前模板和初始模板的SAD；
• 当当前模板的SAD迅速变差时，回退到初始模板重新匹配。

这在FPGA上的实现成本很低：只需要双端口RAM存两份模板，比较逻辑稍作修改即可。而它带来的稳定性提升非常明显，尤其适合目标被短暂遮挡或姿态突变的场景。

如果你用的是Zynq这类SoC FPGA，更聪明的做法是把模板更新放到ARM核上做，比如每50帧用当前跟踪框的图像重新计算一次模板，做一些简单的滤波（比如新旧模板加权平均），然后通过AXI-Lite接口把新模板写入FPGA侧的模板RAM。FPGA只管高速匹配，ARM管决策和更新，分工非常合理。

再说多目标扩展。SAD算法天然支持多目标扩展，思路有两种：

• 时分复用：一个SAD计算阵列，轮流加载多个目标的模板，输出多个最小SAD值和坐标。缺点是当目标数量增多时，整体帧率会线性下降。
• 空间并行：复制多份SAD计算阵列，每份配一个模板，同时计算多个目标的位置。缺点是资源占用会成倍增加。如果做4个目标的跟踪，4套16×16模板的SAD阵列，中等规模的FPGA芯片能扛住。

我实际做过的项目里，用空间并行方案在一块中等规模的Kintex-7上同时跟踪4个目标，处理1080p@60fps输入，资源占用大约在45%左右，时序收敛良好（约180MHz）。如果目标数量再多，建议还是考虑用DSP+软件方案来卸载部分计算。毕竟FPGA也不是万能的，关键还是选对计算引擎。

4. 系统集成与实时性分析：当SAD匹配撞上视频流

算法模块单独验证没问题，不代表放到整个视频链路里也能跑。SAD模板匹配的目标跟踪一般嵌在"视频采集 → 预处理 → 目标匹配 → 结果叠加 → 显示输出"的完整系统中。这里每个环节都会影响SAD模块的输入数据质量，以及整个系统的实时性。

4.1 输入预处理：灰度转换与降噪

SAD算法本身是基于灰度图像的，所以彩色视频进来必须先做RGB转灰度。如果摄像头输出的是RAW Bayer格式，那还得先做去马赛克，再转灰度。这些预处理在FPGA上做很快，但要注意：预处理延迟要计算进整个流水线——如果你的预处理要缓存好几行才能出结果，那SAD模块收到第一帧完整数据的时间会往后拖。

降噪方面，如果画面噪声较大，SAD匹配的稳定性会很差。我的经验是加一个简单的3×3中值滤波或者高斯滤波作为预处理。中值滤波在FPGA上的经典实现是"行缓存 + 排序网络"，3×3窗口的9个像素排序需要3个比较器级联，资源开销不大，效果立竿见影。但注意：滤波会使边缘略微模糊，如果目标本身是很精细的纹理结构，模板匹配精度可能会轻微下降，这一点要在实际项目中权衡。

4.2 帧存调度：DDR3/DDR4带宽与时序

跟踪是在视频帧上撒搜索窗口，可能涉及对整帧图像的随机访问。如果要把搜索区域扩展到全图，或者需要大范围的搜索（比如目标快速运动），就需要把整帧图像存入外部DDR内存。这时DDR读写带宽就成为主要瓶颈。

以1080p、8bit灰度、60fps为例，写入帧存带宽约124MB/s，读取搜索窗口数据的带宽取决于搜索策略。如果搜索区域覆盖整个画面，每个候选位置都要从DDR读一个模板大小的图像块，带宽需求会爆炸，根本跑不动。所以全图搜索的SAD跟踪在实际工程中很少见，大多数情况是基于上一帧目标位置的小范围搜索——比如只搜上一帧位置周围64×64的区域。这样DDR读取带宽可以控制在一个可接受的范围。

我做过一个测试：上一帧位置周围64×64搜索、16×16模板，720p@60fps输入，DDR3-1600单片（16bit），DDR带宽占用大约25%，余量充足。如果把搜索范围扩大到128×128，带宽占用直接飙到80%以上，系统的其他部分（比如显示叠加）就会开始卡顿。

4.3 流水线设计的时序约束要点

FPGA设计跑到系统集成阶段，最让人头疼的就是时序收敛。SAD计算阵列动辄几百级的组合逻辑，如果不加流水线寄存器，时序必然出问题。我的做法是：

• 在每个SAD计算级之间插入一级寄存器，形成3~5级流水线；
• 减法和绝对值合并在同一级流水内完成，减少组合逻辑深度；
• 加法树每级加法插一拍寄存器，用"乒乓寄存器+加法器"结构实现。

时序约束文件（XDC）里，建议给SAD计算阵列单独定义时钟组，并对跨时钟域信号做异步FIFO隔离。视频输入时钟和系统时钟不一致是很常见的情况，比如摄像头给一个24MHz像素时钟，系统主频跑100MHz，中间必须通过异步FIFO转换。我实测过一个设计因为忽略了跨时钟域约束，导致跟踪坐标偶尔跳变，排查了半天才发现是亚稳态问题。

下面给出一段简化版的XDC约束示例：

create_clock -period 10.000 -name sys_clk [get_ports clk] create_clock -period 41.667 -name pix_clk [get_ports pix_clk] set_clock_groups -asynchronous -group [get_clocks sys_clk] -group [get_clocks pix_clk]

5. 实测调优：SAD阈值、搜索策略与性能数据

设计做完之后，真正决定能不能用的，是调优阶段。SAD模板匹配有非常多的"旋钮"可以调，不同场景下的最优参数差异很大。分享几个我实际调过的经验。

5.1 SAD阈值与遮挡判定的配合

SAD最小值本身不能直接说明匹配有多可靠。如果目标跑出画面外，或者被完全遮挡，SAD计算还是会给你一个"最小的"数值，但那个数值通常比正常跟踪时高不少。所以工程上必须设置一个SAD阈值：当最小SAD值超过阈值时，判定为跟踪丢失或目标被遮挡，此时可以切换到等待模式，或者启动搜索模式（扩大搜索区域重新寻找）。

阈值的标定方法，我建议这样：先让系统对着目标正常跟踪50~100帧，记录SAD值的统计分布（最大值、均值、标准差），然后设定阈值为均值加3~4倍标准差。在FPGA上做这个统计不方便，一般是在仿真阶段用软件算好，再固化到寄存器里。如果想做自适应阈值，可以把统计逻辑放在Zynq的ARM端，每N帧回调一次更新阈值寄存器。

5.2 多尺度搜索：大目标变小目标怎么办

SAD模板匹配对尺度变化非常敏感。目标在画面里变大变小，SAD值都会迅速增大。解决这个问题的一个实用方案是多尺度模板池：预先生成目标在不同尺度下的多个模板（比如1.0倍、0.85倍、0.7倍），每一帧对每个尺度都做一次SAD匹配，取所有尺度中最小的SAD值及其坐标作为输出。

这个方案在FPGA上的实现开销是乘法器资源+BRAM容量。如果模板数量不多（3~5个尺度），资源成本还能接受。我的实测感受是：多尺度匹配对跟踪稳定性的提升是肉眼可见的，尤其是在俯视相机（比如无人机视角）场景中，目标大小随高度变化非常明显。

不过要注意多尺度匹配的计算时间会成倍增加。对于实时系统，建议优先做时间维度的并行优化，也就是把不同尺度的匹配任务分配到不同的计算阵列上，而不是串行执行。

5.3 实测性能数据参考

最后给出一组典型的实测数据，硬件平台是Xilinx Artix-7 XC7A200T，工作时钟150MHz，图像分辨率1280×720，灰度8bit：

232微秒的匹配耗时意味着，即使搜索区域进一步扩大，依然有充足的性能余量。如果你用更高端的芯片，比如Kintex-7或Zynq UltraScale+，跑更大的模板和更大的搜索区域也毫无压力。所以SAD模板匹配在FPGA上做目标跟踪，最大的优势不是"能不能做"，而是"做了之后还剩多少资源给其他功能"。这在实际产品设计中，往往比单纯的算法效果更具决策价值。

6. 踩坑实录：跨时钟域、资源竞争与坐标抖动

调试阶段总是会遇到一些让人抓狂的问题。分享几个我踩过的坑，希望能帮你少走弯路。

6.1 异步FIFO没处理好，坐标偶尔跳变

的症状是跟踪基本正常，但每隔几秒钟目标坐标会突然跳出去几十个像素，然后下一帧又跳回来。一开始怀疑是算法问题，查了半天逻辑仿真完全正常。后来用ILA抓实时信号，发现是像素时钟域和系统时钟域之间的异步FIFO读数据时出现了亚稳态，导致偶尔读到错误的像素值，SAD计算结果当然就错了。

解决办法是给异步FIFO加上摆同步（gray code指针同步），并且预留两级寄存器同步后再判断FIFO空满状态。这个坑提醒我：FPGA里最贵的时序成本往往不是算法本身，而是接口转换。

6.2 模板RAM和图像缓存的BRAM资源打架

之前在一个设计中，模板最多支持64个（预留给多目标），每个模板32×32×8bit = 8KB，总共512KB，直接吃了半片Artix-7的BRAM。结果SAD计算阵列里头行缓存已经用了不少BRAM，布局布线时资源告警，甚至出现时序违例。

解决方案有两个方向：

• 把模板存储在DDR里，运行时通过AXI DMA按需读取到FPGA的BRAM缓存中。这样BRAM只需要保存当前用的几个模板即可；
• 压缩模板位宽。灰度8bit降到6bit或者5bit，SAD精度略降但对跟踪稳定性影响不大。曾做过一次测试，5bit量化模板下SAD值整体偏小，但最小坐标基本不变。

6.3 目标高速运动时跟踪框滞后

目标移动速度太快，搜索窗口跟不上，目标直接跑出搜索范围。症状是：跟踪框一开始还行，目标加速后就丢掉，然后到处乱跑。这不是算法算得慢，而是搜索策略的问题。

解决思路是引入运动预测。最简单的预测方法是：记录前两帧目标坐标，用差分近似速度，预测当前帧的搜索中心。公式上就是：

predict_x = last_x + (last_x - prev_x)

predict_y = last_y + (last_y - prev_y)

然后把搜索窗口中心放在predict坐标上，而不是上一帧坐标。这个改动在FPGA上几乎没有成本：两个减法器加两个加法器。但效果非常显著，目标以高速直线运动时，跟踪成功率几乎达到100%。如果还想更精细一些，可以上卡尔曼滤波，不过卡尔曼在FPGA上实现涉及矩阵运算，资源消耗大不少。我的建议是先用差分预测，效果不够再考虑卡尔曼。很多场景下，差分预测已经足够。

另外有一个容易忽略的细节：预测坐标不要直接作为跟踪输出，而是作为搜索中心。最终输出仍然用SAD匹配到的坐标。这样即使预测偏了，只要目标还在搜索窗口内，依然能正确捕获。

7. 用FPGA做SAD跟踪的几点经验总结

如果让我用一个词概括FPGA上的SAD模板匹配目标跟踪，我会选"划算"。算法逻辑简单、资源消耗可控、实时性极强，是FPGA图像处理入门到进阶之间非常优质的一个练习项目。它可以锻炼行缓存设计、流水线架构、并行计算阵列、跨时钟域处理这些基本功，而这些能力在更复杂的FPGA视频处理项目里都是通用的。

再说几个个人体会最深刻的点。

其一，不要一上来就追求全并行。SAD的并行度可以根据芯片资源灵活调整，先用行并行、串行累加的方式跑通整个链路，再去优化并行度是更稳妥的路径。全并行方案在资源利用率上并不一定更优，反而会引入更复杂的布线拥塞和时序收敛问题，调试成本陡增。

其二，数据流的组织比计算本身更重要。很多FPGA初学者把精力都花在SAD计算逻辑上，却忽略了行缓存、FIFO、坐标计数器这些"数据管道"。实际上，视频处理系统的性能瓶颈十有八九出在数据搬运上，而不是计算上。行缓存设计是否合理、跨时钟域FIFO是否可靠，直接决定了整个系统的稳定性。

其三，善用Zynq这种SoC平台做任务分工。单纯的FPGA实现适合追求极致实时性和确定性要求的场景，但一旦涉及复杂的模板更新策略、多目标管理、甚至和上层控制系统交互，ARM核的加入会让系统架构清爽很多。SAD计算在PL侧做，管理和决策在PS侧做，这是Zynq平台上目标跟踪项目最经典的架构之一。

最后留一个可以继续深入的优化方向：当前做的是灰度图像的SAD匹配，如果把RGB三通道的SAD分别计算再加权合并，可以在彩色特征明显的场景下大幅提升匹配精度。实现上只需把单通道SAD阵列复制三份，或者做时分复用，资源增加约2倍，但对特定目标的跟踪效果提升明显。以后有空我会把这个扩展的实现细节单独整理出来，这次就先聊到这里。