拓冰网站定制 
基于FPGA的SAD模板匹配算法实现目标跟踪你有没有遇到过这种情况项目需求里写着“实时目标跟踪”你一搜满屏都是OpenCV、Python、深度学习跑在PC上确实爽可一旦落到嵌入式平台尤其是要接工业相机、要跑60帧、要控制在几瓦功耗的场合软件方案立刻显得力不从心。我之前做的一个视觉定位项目就是这么被逼上FPGA的——当时要跟踪一个运动部件的位置图像分辨率1280x720处理器实在扛不住逐像素滑窗的暴力计算后来把SAD模板匹配算法搬进FPGA直接做到了像素级流水线处理跟踪延迟几乎可以忽略。这篇文章就把整个方案拆开来讲从算法原理到Verilog实现再到上板实测希望能给正在做FPGA图像处理、或者被目标跟踪实时性卡住的朋友一些参考。先说清楚这套东西的适用范围。它不是那种“万物皆可跟踪”的深度学习目标跟踪器它干的是件很朴实的事你给它一张模板图它在一帧新图像里帮你找到和模板最像的那个区域然后输出位置坐标。得益于SADSum of Absolute Differences绝对差值和算法的规则性和可并行性FPGA可以用深度流水线把搜索过程拆到极致在微秒级完成一帧图像的扫描计算。因此它特别适合目标外观变化不大、光照相对稳定的场景比如产线上的工件定位、机器人视觉伺服、云台稳像、无人机定点降落引导这类“模板固定、目标形变小”的任务。1. 为什么是SAD而不是相关性匹配实时性诉求下的算法选型逻辑我见过不少人一上来就选归一化互相关NCC或者平方差和SSD理由是“精度高”“光照不变性”结果在FPGA上实现到一半就开始挠头——乘法器资源不够用、除法器延迟太大、浮点归一化根本没法流水。SAD之所以在FPGA领域经久不衰恰恰是因为它在“算得完”和“算得准”之间找到了一个极其务实的平衡点。1.1 三类经典匹配算法的计算量对比模板匹配的核心思想非常朴素已知一个W x H的模板通常是目标区域的小图在搜索图像尺寸远大于模板中以步长1滑动窗口逐个位置计算模板与窗口内容的“相似度”相似度最高的位置就是目标所在。这里我给出三种常见度量公式SAD绝对差值和$SAD(u,v) \sum_{i0}^{W-1}\sum_{j0}^{H-1} |I(ui, vj) - T(i, j)|$SSD平方差和$SSD(u,v) \sum_{i0}^{W-1}\sum_{j0}^{H-1} (I(ui, vj) - T(i, j))^2$NCC归一化互相关$NCC(u,v) \frac{\sum (I-\bar{I})(T-\bar{T})}{\sqrt{\sum (I-\bar{I})^2 \cdot \sum (T-\bar{T})^2}}$只看公式你可能觉得差不多但把它们映射到硬件上差别是巨大的。NCC需要计算窗口均值和模板均值、需要乘法器计算相关值、需要开方和除法做归一化每一个环节在FPGA里都是资源大户更别说在滑窗的每个位置都要重算一遍均值那延迟和资源占用简直是一场灾难。SSD比SAD多一个平方运算意味着每个像素比较都要用一个乘法器对于32x32的模板一个时钟周期内要同时做1024次平方运算DSP资源直接被榨干。而SAD只需要减法和绝对值求和两大操作这两者在FPGA中都可以用纯逻辑LUT实现几乎不消耗DSP。以Xilinx 7系列的XC7Z020为例它只有220个DSP48E1但LUT资源有53200个用SAD算法就能把计算量全部摊到LUT上让DSP资源腾出来做别的活儿比如后续的PID控制或者坐标滤波。1.2 SAD在硬件实现上的三大天然优势第一计算规则且无数据依赖。SAD的每个像素比较都是独立的不同像素位置的差值计算互不干扰天然适合并行展开。你可以把一个大模板的SAD计算拆成几十个甚至上百个并行的计算单元每个单元负责模板的一小块区域最后再加总。第二运算类型可映射为简单的加法树。绝对值减法可以用|a - b|的逻辑直接实现然后在时序逻辑里搭一棵加法树把多级加法流水化每一级时钟都能稳定跑在200MHz以上。第三数据复用模式极其友好。当滑窗移动时相邻窗口之间有大量的像素重叠利用行缓冲Line Buffer机制可以做到“一个像素只读一次”配合FPGA片内BRAM存储整行数据外部存储器的带宽压力能降到极低。我自己总结过一套选型规律在FPGA上做模板匹配时可以参考需求特征推荐方案理由目标形变小、环境可控、帧率要求高SAD硬件资源占用低流水线深度浅最容易跑出高帧率光照变化明显、目标纹理丰富SSD或改进SAD如带均值归一化的SAD平方运算放大了差异特征抗噪性略好于SAD但代价是乘法器开销目标有旋转/缩放只做检测不苛求实时NCC或特征点匹配用算力换鲁棒性适合在PC或高性能处理器上做离线处理模板大、搜索区域大、要跑满60fps必须牺牲一部分精度用SAD金字塔缩模模板和搜索区域同步降采样粗匹配定位后细匹配精修是FPGA上最经典的优化手段如果你的项目需求是“目标在画面里的尺寸基本不变、姿态基本不变、只有平移”那SAD绝对是最合适的选择。别被网上那些“NCC精度高”的说法带偏在硬件上算不出来精度再高也白搭。2. 系统总体架构设计从摄像头到坐标输出的完整数据通路在写第一行Verilog之前一定要先把整个系统的数据流图画清楚。FPGA项目最忌讳的就是上来就写代码写完发现模块接口对不上、时序收敛不了、存储带宽不够推到重来浪费大量时间。我这里基于自己跑通的项目给出一套可以复用的系统架构。2.1 顶层模块划分与数据流规划整个目标跟踪系统可以分成四个大模块图像采集与预处理、SAD计算阵列、最小位置搜索与坐标输出、以及外部通信与控制接口。它们之间的关系如下图像采集模块负责接收来自MIPI/千兆网/HDMI等接口的相机图像数据完成像素时钟域的同步并把原始RGB图像转换为灰度图灰度化公式为Y 0.299R 0.587G 0.114B。为了节省DSP资源我通常会用移位相加的方式近似实现这个系数乘法比如0.299 ≈ 78/256这样只有一次乘法和两次加法在LUT里就能搞定。灰度化之后的数据以像素时钟为节拍流入下一级同时伴随一个vsync帧同步、hsync行同步、de数据有效信号组这三个信号要一路打拍到后级模块因为后续所有计算模块都需要靠它们对齐时序。行缓冲与窗口生成模块SAD计算需要同时访问模板覆盖区域内的W x H个像素而图像数据是一个像素一个像素串行送入的所以必须把串行数据转换成并行窗口。实现方法就是经典的移位寄存器链加行缓冲。假设模板尺寸是16x16那么需要16行行缓冲每一行缓存的宽度是图像一行像素的数量在每个像素时钟下从16行缓冲中各自取出一个像素拼成一个16x16的窗口。这里有一个关键细节行缓冲可以用Xilinx的RAM-based Shift RegisterSRL16原语实现也可以用普通BRAM做环形缓冲区。前者适合行宽不超过一定值的场合后者更灵活推荐使用BRAM方案因为图像解析度变化时不需要改代码结构只要把行宽参数化就可以了。SAD计算阵列这是整个流水线的核心运算单元。它接收并行的窗口像素和并行的模板像素在同一个时钟周期内计算完成所有像素的绝对差值然后通过一个多级加法树逐级累加最终得到当前窗口位置的SAD值。计算阵列的设计重点在于“每级加法树都插一级寄存器”也就是完全流水化这样组合逻辑路径不会太长时钟频率才能拉高。我会在后面专门用一节展开这个部分的实现细节这里先不展开。最小位置搜索模块SAD值越小代表相似度越高因此需要持续跟踪全局最小值及其对应的坐标。逐行逐列扫描完一整帧图像后最终锁存的值就是目标位置。这个模块还承担一个“提前终止”的功能当某一窗口的SAD值已经小于预设阈值说明目标匹配得非常好时可以产生一个early_done信号提前结束扫描节省后续窗口的计算功耗。2.2 外部存储与带宽分析很多人以为FPGA做图像处理需要外挂DDR实际上模板匹配这种算法有很强的数据局部性只用片内BRAM就能完成一整帧的处理。这是它相对于其他视觉算法比如光流、HOG特征提取非常幸福的一点。举个例子1280x720分辨率的灰度图一帧的数据量是1280x720x8bit 921,600字节 ≈ 900KB。而Xilinx XC7Z020的BRAM总量是4.9Mb折算下来约630KB单颗芯片确实存不下一整帧。但是——我们根本不需要存一整帧。因为在逐行扫描过程中计算一个窗口位置只需要当前16行数据一旦窗口中心移动到第N行第N-16行及以上的数据就永不再用了。所以系统里永远只保留“正在计算所需的行数”也就是16行行缓冲。16x1280x8bit 160Kb占BRAM的不到4%富余得很。这样一来整个系统完全不需要DDR的参与数据通路清爽延迟也可控。当然如果你的模板尺寸很大比如64x64或者图像分辨率到了1080P以上行缓冲占用的BRAM会显著增加这时候就要评估是缩小模板还是转用DDR缓存。我的建议是模板宽度与搜索步长决定了行缓冲深度行缓冲深度乘以图像行宽决定了BRAM这个预算要在选型阶段就算清楚。2.3 坐标输出与闭环集成目标位置的计算结果是一对(row, col)坐标通常以模板左上角在搜索图像中的位置表示。在实际工程中我更习惯输出目标中心点的坐标这样方便直接送给后续的控制系统。坐标数据需要在帧末vsync上升沿锁存保证输出的是完整扫描完整帧后的结果而不是计算到一半的中间值。之后这个坐标怎么用就看你的应用场景了。如果是云台跟踪坐标偏差送PID控制器驱动云台转向如果是产线定位坐标直接送机械臂的运动规划模块如果是安防监控可能还要加一个卡尔曼滤波器做轨迹平滑。这块不是本文的重点但一定要在架构设计时预留好接口别等算法调通了才想起来要往外送数据。3. 两阶段匹配框架粗定位精定位的工程化改造纯SAD模板匹配有一个先天短板——当搜索区域很大时全图逐像素搜索的窗口数量多到可怕计算量随图像尺寸呈线性增长。假设搜索图像是1280x720模板大小是32x32那么窗口位置总数是(1280-321) x (720-321) ≈ 89万个每个窗口要做1024次减法总共约9亿次运算。即使FPGA并行度再高这个规模也会让流水线周期数推得很长帧率就上不去了。聪明的做法是缩小搜索空间也就是“由粗到细”的两阶段匹配。这个思想在图像处理领域非常经典我把它移植到FPGA上后发现不仅计算量指数级下降处理帧率能提升5倍以上而且定位精度甚至有所提高——因为粗定位锁定了大致区域后精匹配只需要在一个很小的邻域内搜索干扰点天然被过滤掉了。3.1 粗定位图像金字塔降采样与初步搜索粗定位阶段的任务是快速锁定目标可能在的大致区域。方法是对原图和模板同时做2倍下采样生成低分辨率版本比如1280x720变成640x36032x32模板变成16x16然后在低分辨率图上搜索匹配。由于尺寸减半窗口数量变成约(640-161) x (360-161) ≈ 22万个每个窗口的SAD计算量从1024次减到256次总运算量直接降到原来的约十分之一。而且下采样后的图像高频噪声被抑制了匹配反而更稳健。我在FPGA上实现降采样时用的不是简单的隔行隔列抽取而是先做2x2邻域平均再输出等效于一个最简形式的均值滤波。这个预处理对抑制传感器噪声特别有效代价只是每4个像素加3次加法几乎不占资源。粗定位的结果是低分辨率坐标系下的位置坐标需要乘以2映射回原始分辨率映射后的点是目标的大致中心区域。注意这里的坐标映射有一点需要注意低分辨率下的(row_low, col_low)映射回原图时覆盖的是原图一个2x2块的范围所以对应的搜索区域应当是(row_low*2 - 模板高/2, col_low*2 - 模板宽/2)扩展出来的一个矩形邻域。3.2 精定位局部邻域内的精确搜索得到粗定位的大致区域后精定位只需要在这个矩形邻域内、以原始分辨率做标准SAD全搜索即可。邻域范围我一般取(template_w margin) x (template_h margin)margin取8-16像素。以32x32模板为例邻域设为48x48窗口数量只有(48-321)^2 289个对比全图89万个窗口运算量几乎可以忽略不计。这个两阶段结构的收益可以用一组实测数据说明。我在ZYNQ-7020上测试模板32x32、输入图像1280x72060fps方案每帧窗口数每窗口SAD计算量帧率实测单阶段全图搜索约89万1024次8-12 fps两阶段粗精约22万粗 289精256次 / 1024次48-60 fps粗匹配阶段窗口数虽然还有22万个但每个窗口的计算量从1024次降到了256次加上精匹配阶段几乎可以忽略的计算量整体吞吐率实现了质的飞跃。如果你在粗匹配阶段再做一层金字塔即三层结构帧率还能进一步往上拉不过对多数应用来说两层已经足够。3.3 动态模板更新的重要性及策略直接使用初始模板在整段视频流里持续匹配会遇到一个工程里非常常见的问题目标外观慢慢变了模板越来越匹配不上。比如云台跟踪目标目标转动了一个角度或者光照逐渐变化初始模板的灰度分布就和当前帧实际画面拉开了差距。SAD值会随着帧数增加越来越大最终误匹配到背景的某个噪声区域。解决办法是动态更新模板。最朴素、也最常用的策略是取当前帧最佳匹配位置的窗口内容按一定比例与旧模板做加权平均得到新模板T_new (1 - α) * T_old α * I_best其中α通常取0.05~0.2。α太大会导致模板漂移——如果某帧匹配错误错误区域会被揉进模板以后每帧都跟着错α太小则更新速度跟不上目标的缓慢变化。我自己的经验是先跑一段采集的视频统计不同α下连续200帧的匹配SAD值曲线选择一个让SAD值保持平稳的最小α。这个方法要花一些离线调试时间但能极大提升稳定性。需要注意模板更新在FPGA里实现时BRAM里的模板数据必须在帧消隐期vsync低电平阶段完成更新。因为你不能一边算一边改模板否则同一帧内不同窗口用的模板不一致结果就乱了。我一般做法是存双模板缓冲当前帧计算结果时用A模板在帧间隔用B模板从外部读入新值下一帧切换过去用B计算、更新A交替使用。这样模板更新不占用任何计算时间代价只是BRAM用量翻倍。4. SAD计算阵列的Verilog实现从单窗口到全流水线的搭建这一节是全文的核心我把Verilog代码的架构和实现细节完整过一遍。这里以单模板匹配为例模板尺寸固定为16x16这也是我们在工程里验证过、资源/精度平衡较好的配置。如果你需要更大的模板思路完全一致只是参数要相应调整。4.1 数据窗口生成SHIFT_REGISTER加行缓冲在像素时钟的每个有效沿图像数据是串行流入的。为了并行取出16行数据我用16个行缓冲模块并行工作每个行缓冲负责缓存图像的一行。同时在每个像素周期到来时触发16次并行读操作取回这16行对应列位置的像素值// 16行行缓冲每行缓存image_width个像素 genvar i; generate for (i 0; i 16; i i 1) begin : line_buffer_gen reg [7:0] line_buf [0:image_width - 1]; always (posedge clk) begin if (de) begin line_buf[i] (i 0) ? pixel_in : line_buf[i-1][image_width - 1]; end end end endgenerate上面的描述比较简化实际项目里更常用的是使用Xilinx FIFO的show-ahead模式或者BRAM双端口来实现行缓冲。关键是我们要得到一个16行16列的二维数组window_pixels[15:0][15:0]这个数组在每一个像素时钟周期更新一次相当于一个窗口在原图上向右滑动了一格到行尾后换行。这一步有个很隐蔽的坑当窗口滑到图像右边界时窗口会超出图像范围。比如图像宽度是1280窗口宽度是16那么列的搜索范围实际是0~1264最后15个像素位置上窗口是不完整的。处理办法是在行缓冲写数据时维护一个计数器当列计数大于image_width - template_width时停止计算并让输出数据保持无效。还有一种做法是用两个de信号分别表示“数据有效”和“窗口有效”前者是相机送来的行场同步信号后者是行缓冲模块自己生成的、表明当前窗口数据完整的使能信号。我用的是后者逻辑更清晰。4.2 绝对差值与多级加法树得到16x16的窗口像素和同样尺寸的模板像素后接下来就是计算SAD值。这里的关键在于完全展开的并行计算也就是一个时钟周期内同时计算256个绝对差值// 并行计算256个绝对差值 reg [8:0] abs_diff [0:15][0:15]; // 9位足以容纳8位像素差值的绝对值 always (*) begin for (int i 0; i 16; i i 1) begin for (int j 0; j 16; j j 1) begin abs_diff[i][j] (window_pixels[i][j] template_pixels[i][j]) ? (window_pixels[i][j] - template_pixels[i][j]) : (template_pixels[i][j] - window_pixels[i][j]); end end end256个9位差值要聚合成一个SAD值你不能用一个巨大的组合逻辑一步到位那样关键路径会非常长时序收敛不了。正确的做法是搭一棵多级流水加法树。我的习惯是每次两两相加分成log2(256)8级第一级128个加法器把256个差值两两配对加出128个结果 第二级64个加法器128个结果两两配对加出64个结果 第三级32个加法器得到32个结果 第四级16个加法器 第五级8个 第六级4个 第七级2个 第八级1个最终得到一个15位的SAD值。// 四级加法树示例仅展示前几级的思路 reg [9:0] stage1 [0:127]; reg [10:0] stage2 [0:63]; reg [11:0] stage3 [0:31]; reg [12:0] stage4 [0:15]; // 每一级的输出都打一拍形成流水线 always (posedge clk) begin for (int k 0; k 128; k k 1) stage1[k] abs_diff[2*k][0] abs_diff[2*k1][0]; // 实际实现时需要处理二维索引展开 end // 后续各级类似最终得到 fifteensad每一级的输出我都在寄存器里打了一拍。也就是说从窗口像素进入流水线到SAD值稳定输出一共有9拍8级加法树接力加1拍输入对齐。计算吞吐率并不会因此下降因为每个时钟周期都有新的窗口数据进来流水线的每一级都在同时工作输出端每个周期都会冒出一个新的SAD值。这种“延迟9个周期、吞吐率1个周期1个结果”的模式是时域上最经济的做法。4.3 模板存储与实时更新模板数据存储在BRAM中位宽为16x16x8 2048位。由于我们要在同一时钟周期访问全部256个数据最好是把模板放进寄存器阵列而不是BRAM这样读端口完全不受限制。16x16x8bit的寄存器阵列在7系列FPGA上需要大约256个8bit寄存器大约占512个SLICE完全可以接受。模板的初始值可以通过AXI-Lite接口从PS端如果你用ZYNQ或者串口等方式写入。运行时如果需要动态更新模板我们在帧消隐期间按上面说的双缓冲方式用新模板覆盖旧模板。由于是寄存器阵列更新操作可以串行逐字写入不需要额外控制逻辑在消隐期的时钟周期数量足够完成全部256字节的写入。4.4 全流水线的工作时序把上面这些模块串起来完整的工作时序是这样的在每一帧的de有效期间像素数据流持续流入窗口生成模块生成16x16窗口窗口数据在下一个时钟沿进入SAD计算阵列经过9拍流水线后输出当前窗口的SAD值与此同时最小位置搜索模块比较当前SAD值和已保存的最小值如果更小就更新坐标寄存器。当vsync上升沿来临时锁存最终坐标并输出。一个至关重要的时序约束是搜索模块的消息必须和流水线的输出严格对齐。也就是说当第N个窗口的SAD值在流水线出口出现时最小位置搜索模块必须知道这个SAD值对应的是哪一行哪一列的窗口否则坐标就错位了。解决办法是用计数器跟踪窗口坐标在SAD值进入流水线的那一拍把坐标打拍到延时链里延时链的深度就是SAD计算流水线的深度9拍这样坐标和SAD值能同时到达搜索模块。// 坐标延时链与SAD流水线深度对齐 reg [10:0] row_delay [0:8]; reg [10:0] col_delay [0:8]; always (posedge clk) begin row_delay[0] curr_row; col_delay[0] curr_col; for (int d 1; d 9; d d 1) begin row_delay[d] row_delay[d-1]; col_delay[d] col_delay[d-1]; end end这个细节我觉得是整个模块最容易出错的地方很多初学者写完SAD计算发现坐标输出是乱的问题十有八九就出在这里。5. 最小位置搜索与坐标输出的Lamda时序设计SAD值是一帧图像上每一窗口位置相似度的度量现在有了一连串SAD值以后要从这一串数值里找全局最小。这个搜最小模块的逻辑本身不复杂难点在于要对齐流水线延迟并且正确处理帧边界。5.1 全局最小搜索与坐标锁存参考代码reg [14:0] min_sad; reg [10:0] best_row; reg [10:0] best_col; reg result_valid; always (posedge clk) begin if (frame_start) begin // vsync上升沿同步复位 min_sad 15h7FFF; // 初始化为最大值 result_valid 1b0; end else if (sad_valid) begin if (sad_value min_sad) begin min_sad sad_value; best_row row_delay[8]; best_col col_delay[8]; result_valid 1b0; // 仍在搜索中 end end else if (frame_end) begin result_valid 1b1; // 帧结束锁存最终结果 end endframe_start信号是每帧图像开始的标志可以是vsync的上升沿也可以是行缓冲模块生成的frame_start_calc信号。更严谨的做法是在“宽度-模板宽度1”个有效窗口计算完成后再等待“高度-模板高度1”行扫描完毕用这个“全图搜索完毕”信号作为frame_end此时锁存best_row和best_col才是最终结果。我的做法是额外维护一个窗口计数器统计当前帧内已经计算过SAD值的窗口总数当计数等于预期窗口总数时产生frame_done脉冲搜索模块在这个脉冲到来后锁存坐标。5.2 early_done低功耗优化前面提到过当最小SAD值已经低于某一阈值比如模板总体方差的一定比例时说明当前窗口和模板已经非常接近继续搜下去的意义不大。此时可以拉高early_done信号通知上游模块停止产生新的窗口数据坐标输出直接使用当前最佳结果。这个设计在电池供电的嵌入式视觉设备上非常实用。实测在光照稳定、目标特征明显的场景里大部分帧都会在扫描到第30%~50%区域前触发early_doneSAD计算阵列的翻转率大幅下降动态功耗降了将近一半。阈值设多少需要根据你的模板内容和场景仔细调一个简单的方法是采集一批视频统计正确匹配位置上的SAD值的上限把阈值设为这个上限的1.1倍。5.3 坐标输出的时钟域处理如果整个系统跑在同一个时钟域里坐标输出直接就是一个寄存器逻辑很简单。但在实际项目中FPGA往往要和外部MCU、DSP或者上位机通信这些处理器跑在完全不同的时钟域常见的有UART115200波特率、SPI10MHz级别或者千兆网口125MHz。跨时钟域处理的关键是不要用单寄存器的电平信号直接跨时钟域采样轻则亚稳态重则采到垃圾数据。我一般用异步FIFO来跨时钟域传递坐标数据。发送端像素时钟域把坐标写入FIFO接收端UART/网口时钟域从FIFO读出并通过协议发送。Xilinx提供了XPM_FIFO原语配置成异步读写的标准模式两端的宽度和深度都可以参数化代码干净又不容易出错。如果你不想用FIFO也可以用两个寄存器的同步链加握手信号但必须在代码里加(* ASYNC_REG TRUE *)约束时序上要留够裕量。总之跨时钟域这块千万别省我见过太多次因为图省事直接采电平导致设备偶发性抽风的问题了。6. 板级调试与性能实测那些综合报告不会告诉你的坑写完代码仿真通过以为就万事大吉了上板调试才是真正考验耐心的地方。我把自己在这一项目里撞过的墙和总结的经验列出来希望能帮你少走弯路。6.1 时序收敛是第一道坎SAD计算阵列里有大量的组合逻辑加法器路径如果随便写不优化时序综合后最容易遇到的问题就是WNSWorst Negative Slack为负。我遇到过的情况是无约束时关键路径延迟高达8.7ns而目标时钟周期是5ns200MHz差了将近一倍。我的优化顺序是先确认每个模块的寄存器是否打在了“正确的位置”。加法树的每一级输出是否都有寄存器窗口数据从行缓冲出来到进入计算阵列是否有输入打拍如果整个SAD计算阵列的输入数据是直接来自BRAM的异步读数据组合路径会特别长必须在读数据后再打一拍。再检查是否存在大位宽的比较器。最小搜索模块里if (sad_value min_sad)是一个16位比较器它本身不慢但它接在SAD输出和计数器延时链输出之后容易成为路径终点。我的做法是让比较器的输入都来自寄存器比较结果打一拍再反馈控制。还不行就降低时钟频率或者做多周期路径约束。我最终把系统主频稳定在180MHzWNS留了0.2ns左右的余量在工业级温度范围-40到85摄氏度下跑了老化测试没有出错。对于图像处理项目来说180MHz已经足够流畅处理720p60fps的SAD计算没必要盲目追求高频。6.2 实测帧率与资源占用以Xilinx ZYNQ XC7Z020-2CLG484为例综合实现后的资源报告大致如下资源使用量总量占比LUT12,40653,20023.3%LUTRAM1,12517,4006.5%FF8,932106,4008.4%BRAM10.51407.5%DSP02200%BUFG53215.6%可以看到DSP占用为零资源大头在LUT这说明SAD算法确实非常“逻辑友好”。整个工程留给后续扩展比如加卡尔曼滤波、加PID控制、加多个模板的余量非常充足。帧率实测我是在720p分辨率、16x16模板、两阶段匹配方案下测的最高跑到58fps接近理论值60fps跟踪误差方面在目标做匀速直线运动且无遮挡时定位误差控制在1个像素以内在目标快速变速运动时有轻微滞后这个主要不是SAD的问题而是单帧搜索本身不带运动预测要解决得叠加卡尔曼滤波或者增加搜索中心预测。6.3 光照变化与匹配失败RESET机制SAD对光照敏感是它最大的短板。实际场景里哪怕同一盏灯开灯瞬间和稳定后图像的灰度分布都会有明显差异。如果目标区域的灰度整体抬高了50个灰阶SAD值会剧烈升高最小位置可能跳到背景去。我在实际项目里发现了一个比较实用的补救手段每帧记录最佳SAD值和次佳SAD值的比值当这个比值接近1比如小于1.2时说明当前帧的匹配结果置信度很低全图有多个位置长得和模板差不多这时候宁可不输出坐标也不输出一个错误坐标。具体做法是维护两个最小值和它们的位置在帧末计算比值低于阈值就置tracking_valid为低。后续的控制系统看到这个标志位为低可以进入保持状态或者重新初始化模板。这个方法成本极低一个减法和一个比较器但能避免非常多因为误匹配导致的“飞出天际”问题。6.4 模板初始化首帧截取与后续校验“模板从哪来”也是一个核心问题。我常用的方案有两种手动初始化上位机把目标框的位置下发到FPGAFPGA在下一帧的对应区域截取像素内容作为模板。注意截取的是灰度图还是RGB图要提前约定好两者对匹配结果影响不大但实现复杂度差不少。自动初始化在指定的ROI区域内计算图像方差选取方差最大的区域作为模板。思路是方差大说明纹理丰富匹配不容易产生歧义。这个方法适合目标进入画面时自动锁定跟踪的场合。初始化完成后还应该加一道自校验统计模板的灰度均值和方差如果方差太小比如全黑或全白区域说明选中的区域没有足够特征直接拒绝并提示重新选框。这个逻辑放在PS端软件做或者纯逻辑实现都可以取决于你的系统架构。7. 进阶优化多目标跟踪与模板旋转适配基础版本的SAD模板匹配能解决“一个固定模板、平移运动”的场景但如果你的项目再往前走一步会遇到两类常见需求跟踪多个目标、目标自身旋转。7.1 多目标跟踪的扩展思路多目标跟踪最直接的办法就是把SAD计算阵列复制多份每份对应一个目标模板。在资源充足的情况下这是最简单的方案但要注意几个问题一是多个目标可能同时出现在同一个窗口附近各自的搜索模块会产生相近的坐标需要有碰撞检测逻辑避免两个跟踪器输出同一个目标二是保持硬件并行度超过4~8路以后LUT消耗会很可观需要评估成本。另一个思路是时分复用SAD计算阵列只有一套但把4路目标的模板存在不同地址空间在扫描时逐帧轮流切换模板进行计算。比如第1帧算模板A、第2帧算模板B这样4路目标就会“轮询”更新帧率除以4。如果你的场景里目标运动速度不快这个方案完全够用而且几乎不增加资源。我自己的一个项目就用了这个折中4路目标轮询每路目标实际更新频率为15fps对低速运动目标来说完全是够用的。7.2 旋转目标的SAD改进多角度模板融合目标在画面里发生缓慢旋转时固定模板的匹配效果会逐渐下降。工业界比较经典的改进是预先离线生成多角度的模板比如每5度采样一个共72个角度模板在匹配时每个角度模板都算一遍SAD取所有角度中最小的作为最终匹配。这个方法在FPGA上实现时模板存储器容量会变成原来的72倍但计算阵列可以复用——因为每个角度模板的尺寸是一样的计算结构完全相同只是从BRAM里取的模板数据地址不同。在帧率要求不是极端高的场合可以在不同帧间循环切换角度模板比如第1帧匹配0度模板、第2帧匹配5度模板、第3帧匹配10度模板……一个完整的72角度扫描在72帧内完成目标旋转速度较慢时这完全不影响跟踪的连续性。还有一种更轻量的方案是低秩近似把目标区域的梯度方向直方图算出来用主方向作为目标的姿态估计再用姿态角从离线模板库中选最接近的角度模板。这个方案对FPGA的资源开销更小但工程实现复杂度高一些如果不是特别必要一般用轮询角度模板就够用了。7.3 融合运动模型的预测-校正框架当你发现目标快速运动时逐帧全图扫描会浪费大量计算在“根本不可能出现目标”的区域。解决办法是用上一帧的位置和速度做线性预测得到当前帧的预测中心然后只在预测中心周围的一个小邻域内做精匹配。这一步相当于给SAD匹配加了一个运动先验匹配速度和稳定性都能显著提升。具体做法用两个坐标寄存器存上一帧和上上帧的位置计算速度向量当前帧的搜索中心就是“上一帧位置 速度向量”预测出来的位置搜索半径为最大预期速度乘帧间隔时间换算成像素数通常取20~30像素。这个逻辑在PS端软件里做特别简单但如果你想把整个系统都放进FPGA用定点数实现也不复杂位置用16位定点数高10位整数、低6位小数速度用(position_new - position_old) 1的移位方式近似。预测中心和实际中心如果偏差过大还可以触发重新初始化模板的流程是一种有效的错误恢复机制。8. 基于本项目的总结与资源开销再审视SAD模板匹配在FPGA中实现目标跟踪本质上是一道“用硬件并行度和深度流水线换取暴力计算速度”的题。它不像深度学习目标检测那样“智能”但凭借极其规则的运算结构、极低的资源消耗以及对实时性近乎苛刻的满足能力在工业视觉、机器人控制等领域依然是最可靠的方案之一。拿我自己的项目总结一套可以直接复用的数据点在Xilinx 7系列平台上16x16模板、1280x72060fps的输入两阶段粗精匹配加动态模板更新整个跟踪系统只占用约23%的LUT、0%的DSP和7.5%的BRAM留给用户的资源余量非常可观。如果你不需要在FPGA里做后续的PID控制甚至可以把PS端的ARM核空出来跑通信协议栈和人机交互代码整套系统的性价比相当高。最后分享一个调试心得。如果你第一次上板发现匹配结果时对时错先别急着怀疑算法试试把整帧图像的de信号用逻辑分析仪抓出来看看——我遇到过的情况是相机输出时序里带了一个我没料到的水平消隐间隙导致行缓冲里的数据错位了一行整个匹配坐标全部往下偏了一行。这种问题不看时序、只看结果是很难定位出来的。FPGA调试就是这样算法层面想得再透彻最后还是得回到信号时序上较真。 基于FPGA的SAD模板匹配算法实现实时目标跟踪
基于FPGA的SAD模板匹配算法实现目标跟踪你有没有遇到过这种情况项目需求里写着“实时目标跟踪”你一搜满屏都是OpenCV、Python、深度学习跑在PC上确实爽可一旦落到嵌入式平台尤其是要接工业相机、要跑60帧、要控制在几瓦功耗的场合软件方案立刻显得力不从心。我之前做的一个视觉定位项目就是这么被逼上FPGA的——当时要跟踪一个运动部件的位置图像分辨率1280x720处理器实在扛不住逐像素滑窗的暴力计算后来把SAD模板匹配算法搬进FPGA直接做到了像素级流水线处理跟踪延迟几乎可以忽略。这篇文章就把整个方案拆开来讲从算法原理到Verilog实现再到上板实测希望能给正在做FPGA图像处理、或者被目标跟踪实时性卡住的朋友一些参考。先说清楚这套东西的适用范围。它不是那种“万物皆可跟踪”的深度学习目标跟踪器它干的是件很朴实的事你给它一张模板图它在一帧新图像里帮你找到和模板最像的那个区域然后输出位置坐标。得益于SADSum of Absolute Differences绝对差值和算法的规则性和可并行性FPGA可以用深度流水线把搜索过程拆到极致在微秒级完成一帧图像的扫描计算。因此它特别适合目标外观变化不大、光照相对稳定的场景比如产线上的工件定位、机器人视觉伺服、云台稳像、无人机定点降落引导这类“模板固定、目标形变小”的任务。1. 为什么是SAD而不是相关性匹配实时性诉求下的算法选型逻辑我见过不少人一上来就选归一化互相关NCC或者平方差和SSD理由是“精度高”“光照不变性”结果在FPGA上实现到一半就开始挠头——乘法器资源不够用、除法器延迟太大、浮点归一化根本没法流水。SAD之所以在FPGA领域经久不衰恰恰是因为它在“算得完”和“算得准”之间找到了一个极其务实的平衡点。1.1 三类经典匹配算法的计算量对比模板匹配的核心思想非常朴素已知一个W x H的模板通常是目标区域的小图在搜索图像尺寸远大于模板中以步长1滑动窗口逐个位置计算模板与窗口内容的“相似度”相似度最高的位置就是目标所在。这里我给出三种常见度量公式SAD绝对差值和$SAD(u,v) \sum_{i0}^{W-1}\sum_{j0}^{H-1} |I(ui, vj) - T(i, j)|$SSD平方差和$SSD(u,v) \sum_{i0}^{W-1}\sum_{j0}^{H-1} (I(ui, vj) - T(i, j))^2$NCC归一化互相关$NCC(u,v) \frac{\sum (I-\bar{I})(T-\bar{T})}{\sqrt{\sum (I-\bar{I})^2 \cdot \sum (T-\bar{T})^2}}$只看公式你可能觉得差不多但把它们映射到硬件上差别是巨大的。NCC需要计算窗口均值和模板均值、需要乘法器计算相关值、需要开方和除法做归一化每一个环节在FPGA里都是资源大户更别说在滑窗的每个位置都要重算一遍均值那延迟和资源占用简直是一场灾难。SSD比SAD多一个平方运算意味着每个像素比较都要用一个乘法器对于32x32的模板一个时钟周期内要同时做1024次平方运算DSP资源直接被榨干。而SAD只需要减法和绝对值求和两大操作这两者在FPGA中都可以用纯逻辑LUT实现几乎不消耗DSP。以Xilinx 7系列的XC7Z020为例它只有220个DSP48E1但LUT资源有53200个用SAD算法就能把计算量全部摊到LUT上让DSP资源腾出来做别的活儿比如后续的PID控制或者坐标滤波。1.2 SAD在硬件实现上的三大天然优势第一计算规则且无数据依赖。SAD的每个像素比较都是独立的不同像素位置的差值计算互不干扰天然适合并行展开。你可以把一个大模板的SAD计算拆成几十个甚至上百个并行的计算单元每个单元负责模板的一小块区域最后再加总。第二运算类型可映射为简单的加法树。绝对值减法可以用|a - b|的逻辑直接实现然后在时序逻辑里搭一棵加法树把多级加法流水化每一级时钟都能稳定跑在200MHz以上。第三数据复用模式极其友好。当滑窗移动时相邻窗口之间有大量的像素重叠利用行缓冲Line Buffer机制可以做到“一个像素只读一次”配合FPGA片内BRAM存储整行数据外部存储器的带宽压力能降到极低。我自己总结过一套选型规律在FPGA上做模板匹配时可以参考需求特征推荐方案理由目标形变小、环境可控、帧率要求高SAD硬件资源占用低流水线深度浅最容易跑出高帧率光照变化明显、目标纹理丰富SSD或改进SAD如带均值归一化的SAD平方运算放大了差异特征抗噪性略好于SAD但代价是乘法器开销目标有旋转/缩放只做检测不苛求实时NCC或特征点匹配用算力换鲁棒性适合在PC或高性能处理器上做离线处理模板大、搜索区域大、要跑满60fps必须牺牲一部分精度用SAD金字塔缩模模板和搜索区域同步降采样粗匹配定位后细匹配精修是FPGA上最经典的优化手段如果你的项目需求是“目标在画面里的尺寸基本不变、姿态基本不变、只有平移”那SAD绝对是最合适的选择。别被网上那些“NCC精度高”的说法带偏在硬件上算不出来精度再高也白搭。2. 系统总体架构设计从摄像头到坐标输出的完整数据通路在写第一行Verilog之前一定要先把整个系统的数据流图画清楚。FPGA项目最忌讳的就是上来就写代码写完发现模块接口对不上、时序收敛不了、存储带宽不够推到重来浪费大量时间。我这里基于自己跑通的项目给出一套可以复用的系统架构。2.1 顶层模块划分与数据流规划整个目标跟踪系统可以分成四个大模块图像采集与预处理、SAD计算阵列、最小位置搜索与坐标输出、以及外部通信与控制接口。它们之间的关系如下图像采集模块负责接收来自MIPI/千兆网/HDMI等接口的相机图像数据完成像素时钟域的同步并把原始RGB图像转换为灰度图灰度化公式为Y 0.299R 0.587G 0.114B。为了节省DSP资源我通常会用移位相加的方式近似实现这个系数乘法比如0.299 ≈ 78/256这样只有一次乘法和两次加法在LUT里就能搞定。灰度化之后的数据以像素时钟为节拍流入下一级同时伴随一个vsync帧同步、hsync行同步、de数据有效信号组这三个信号要一路打拍到后级模块因为后续所有计算模块都需要靠它们对齐时序。行缓冲与窗口生成模块SAD计算需要同时访问模板覆盖区域内的W x H个像素而图像数据是一个像素一个像素串行送入的所以必须把串行数据转换成并行窗口。实现方法就是经典的移位寄存器链加行缓冲。假设模板尺寸是16x16那么需要16行行缓冲每一行缓存的宽度是图像一行像素的数量在每个像素时钟下从16行缓冲中各自取出一个像素拼成一个16x16的窗口。这里有一个关键细节行缓冲可以用Xilinx的RAM-based Shift RegisterSRL16原语实现也可以用普通BRAM做环形缓冲区。前者适合行宽不超过一定值的场合后者更灵活推荐使用BRAM方案因为图像解析度变化时不需要改代码结构只要把行宽参数化就可以了。SAD计算阵列这是整个流水线的核心运算单元。它接收并行的窗口像素和并行的模板像素在同一个时钟周期内计算完成所有像素的绝对差值然后通过一个多级加法树逐级累加最终得到当前窗口位置的SAD值。计算阵列的设计重点在于“每级加法树都插一级寄存器”也就是完全流水化这样组合逻辑路径不会太长时钟频率才能拉高。我会在后面专门用一节展开这个部分的实现细节这里先不展开。最小位置搜索模块SAD值越小代表相似度越高因此需要持续跟踪全局最小值及其对应的坐标。逐行逐列扫描完一整帧图像后最终锁存的值就是目标位置。这个模块还承担一个“提前终止”的功能当某一窗口的SAD值已经小于预设阈值说明目标匹配得非常好时可以产生一个early_done信号提前结束扫描节省后续窗口的计算功耗。2.2 外部存储与带宽分析很多人以为FPGA做图像处理需要外挂DDR实际上模板匹配这种算法有很强的数据局部性只用片内BRAM就能完成一整帧的处理。这是它相对于其他视觉算法比如光流、HOG特征提取非常幸福的一点。举个例子1280x720分辨率的灰度图一帧的数据量是1280x720x8bit 921,600字节 ≈ 900KB。而Xilinx XC7Z020的BRAM总量是4.9Mb折算下来约630KB单颗芯片确实存不下一整帧。但是——我们根本不需要存一整帧。因为在逐行扫描过程中计算一个窗口位置只需要当前16行数据一旦窗口中心移动到第N行第N-16行及以上的数据就永不再用了。所以系统里永远只保留“正在计算所需的行数”也就是16行行缓冲。16x1280x8bit 160Kb占BRAM的不到4%富余得很。这样一来整个系统完全不需要DDR的参与数据通路清爽延迟也可控。当然如果你的模板尺寸很大比如64x64或者图像分辨率到了1080P以上行缓冲占用的BRAM会显著增加这时候就要评估是缩小模板还是转用DDR缓存。我的建议是模板宽度与搜索步长决定了行缓冲深度行缓冲深度乘以图像行宽决定了BRAM这个预算要在选型阶段就算清楚。2.3 坐标输出与闭环集成目标位置的计算结果是一对(row, col)坐标通常以模板左上角在搜索图像中的位置表示。在实际工程中我更习惯输出目标中心点的坐标这样方便直接送给后续的控制系统。坐标数据需要在帧末vsync上升沿锁存保证输出的是完整扫描完整帧后的结果而不是计算到一半的中间值。之后这个坐标怎么用就看你的应用场景了。如果是云台跟踪坐标偏差送PID控制器驱动云台转向如果是产线定位坐标直接送机械臂的运动规划模块如果是安防监控可能还要加一个卡尔曼滤波器做轨迹平滑。这块不是本文的重点但一定要在架构设计时预留好接口别等算法调通了才想起来要往外送数据。3. 两阶段匹配框架粗定位精定位的工程化改造纯SAD模板匹配有一个先天短板——当搜索区域很大时全图逐像素搜索的窗口数量多到可怕计算量随图像尺寸呈线性增长。假设搜索图像是1280x720模板大小是32x32那么窗口位置总数是(1280-321) x (720-321) ≈ 89万个每个窗口要做1024次减法总共约9亿次运算。即使FPGA并行度再高这个规模也会让流水线周期数推得很长帧率就上不去了。聪明的做法是缩小搜索空间也就是“由粗到细”的两阶段匹配。这个思想在图像处理领域非常经典我把它移植到FPGA上后发现不仅计算量指数级下降处理帧率能提升5倍以上而且定位精度甚至有所提高——因为粗定位锁定了大致区域后精匹配只需要在一个很小的邻域内搜索干扰点天然被过滤掉了。3.1 粗定位图像金字塔降采样与初步搜索粗定位阶段的任务是快速锁定目标可能在的大致区域。方法是对原图和模板同时做2倍下采样生成低分辨率版本比如1280x720变成640x36032x32模板变成16x16然后在低分辨率图上搜索匹配。由于尺寸减半窗口数量变成约(640-161) x (360-161) ≈ 22万个每个窗口的SAD计算量从1024次减到256次总运算量直接降到原来的约十分之一。而且下采样后的图像高频噪声被抑制了匹配反而更稳健。我在FPGA上实现降采样时用的不是简单的隔行隔列抽取而是先做2x2邻域平均再输出等效于一个最简形式的均值滤波。这个预处理对抑制传感器噪声特别有效代价只是每4个像素加3次加法几乎不占资源。粗定位的结果是低分辨率坐标系下的位置坐标需要乘以2映射回原始分辨率映射后的点是目标的大致中心区域。注意这里的坐标映射有一点需要注意低分辨率下的(row_low, col_low)映射回原图时覆盖的是原图一个2x2块的范围所以对应的搜索区域应当是(row_low*2 - 模板高/2, col_low*2 - 模板宽/2)扩展出来的一个矩形邻域。3.2 精定位局部邻域内的精确搜索得到粗定位的大致区域后精定位只需要在这个矩形邻域内、以原始分辨率做标准SAD全搜索即可。邻域范围我一般取(template_w margin) x (template_h margin)margin取8-16像素。以32x32模板为例邻域设为48x48窗口数量只有(48-321)^2 289个对比全图89万个窗口运算量几乎可以忽略不计。这个两阶段结构的收益可以用一组实测数据说明。我在ZYNQ-7020上测试模板32x32、输入图像1280x72060fps方案每帧窗口数每窗口SAD计算量帧率实测单阶段全图搜索约89万1024次8-12 fps两阶段粗精约22万粗 289精256次 / 1024次48-60 fps粗匹配阶段窗口数虽然还有22万个但每个窗口的计算量从1024次降到了256次加上精匹配阶段几乎可以忽略的计算量整体吞吐率实现了质的飞跃。如果你在粗匹配阶段再做一层金字塔即三层结构帧率还能进一步往上拉不过对多数应用来说两层已经足够。3.3 动态模板更新的重要性及策略直接使用初始模板在整段视频流里持续匹配会遇到一个工程里非常常见的问题目标外观慢慢变了模板越来越匹配不上。比如云台跟踪目标目标转动了一个角度或者光照逐渐变化初始模板的灰度分布就和当前帧实际画面拉开了差距。SAD值会随着帧数增加越来越大最终误匹配到背景的某个噪声区域。解决办法是动态更新模板。最朴素、也最常用的策略是取当前帧最佳匹配位置的窗口内容按一定比例与旧模板做加权平均得到新模板T_new (1 - α) * T_old α * I_best其中α通常取0.05~0.2。α太大会导致模板漂移——如果某帧匹配错误错误区域会被揉进模板以后每帧都跟着错α太小则更新速度跟不上目标的缓慢变化。我自己的经验是先跑一段采集的视频统计不同α下连续200帧的匹配SAD值曲线选择一个让SAD值保持平稳的最小α。这个方法要花一些离线调试时间但能极大提升稳定性。需要注意模板更新在FPGA里实现时BRAM里的模板数据必须在帧消隐期vsync低电平阶段完成更新。因为你不能一边算一边改模板否则同一帧内不同窗口用的模板不一致结果就乱了。我一般做法是存双模板缓冲当前帧计算结果时用A模板在帧间隔用B模板从外部读入新值下一帧切换过去用B计算、更新A交替使用。这样模板更新不占用任何计算时间代价只是BRAM用量翻倍。4. SAD计算阵列的Verilog实现从单窗口到全流水线的搭建这一节是全文的核心我把Verilog代码的架构和实现细节完整过一遍。这里以单模板匹配为例模板尺寸固定为16x16这也是我们在工程里验证过、资源/精度平衡较好的配置。如果你需要更大的模板思路完全一致只是参数要相应调整。4.1 数据窗口生成SHIFT_REGISTER加行缓冲在像素时钟的每个有效沿图像数据是串行流入的。为了并行取出16行数据我用16个行缓冲模块并行工作每个行缓冲负责缓存图像的一行。同时在每个像素周期到来时触发16次并行读操作取回这16行对应列位置的像素值// 16行行缓冲每行缓存image_width个像素 genvar i; generate for (i 0; i 16; i i 1) begin : line_buffer_gen reg [7:0] line_buf [0:image_width - 1]; always (posedge clk) begin if (de) begin line_buf[i] (i 0) ? pixel_in : line_buf[i-1][image_width - 1]; end end end endgenerate上面的描述比较简化实际项目里更常用的是使用Xilinx FIFO的show-ahead模式或者BRAM双端口来实现行缓冲。关键是我们要得到一个16行16列的二维数组window_pixels[15:0][15:0]这个数组在每一个像素时钟周期更新一次相当于一个窗口在原图上向右滑动了一格到行尾后换行。这一步有个很隐蔽的坑当窗口滑到图像右边界时窗口会超出图像范围。比如图像宽度是1280窗口宽度是16那么列的搜索范围实际是0~1264最后15个像素位置上窗口是不完整的。处理办法是在行缓冲写数据时维护一个计数器当列计数大于image_width - template_width时停止计算并让输出数据保持无效。还有一种做法是用两个de信号分别表示“数据有效”和“窗口有效”前者是相机送来的行场同步信号后者是行缓冲模块自己生成的、表明当前窗口数据完整的使能信号。我用的是后者逻辑更清晰。4.2 绝对差值与多级加法树得到16x16的窗口像素和同样尺寸的模板像素后接下来就是计算SAD值。这里的关键在于完全展开的并行计算也就是一个时钟周期内同时计算256个绝对差值// 并行计算256个绝对差值 reg [8:0] abs_diff [0:15][0:15]; // 9位足以容纳8位像素差值的绝对值 always (*) begin for (int i 0; i 16; i i 1) begin for (int j 0; j 16; j j 1) begin abs_diff[i][j] (window_pixels[i][j] template_pixels[i][j]) ? (window_pixels[i][j] - template_pixels[i][j]) : (template_pixels[i][j] - window_pixels[i][j]); end end end256个9位差值要聚合成一个SAD值你不能用一个巨大的组合逻辑一步到位那样关键路径会非常长时序收敛不了。正确的做法是搭一棵多级流水加法树。我的习惯是每次两两相加分成log2(256)8级第一级128个加法器把256个差值两两配对加出128个结果 第二级64个加法器128个结果两两配对加出64个结果 第三级32个加法器得到32个结果 第四级16个加法器 第五级8个 第六级4个 第七级2个 第八级1个最终得到一个15位的SAD值。// 四级加法树示例仅展示前几级的思路 reg [9:0] stage1 [0:127]; reg [10:0] stage2 [0:63]; reg [11:0] stage3 [0:31]; reg [12:0] stage4 [0:15]; // 每一级的输出都打一拍形成流水线 always (posedge clk) begin for (int k 0; k 128; k k 1) stage1[k] abs_diff[2*k][0] abs_diff[2*k1][0]; // 实际实现时需要处理二维索引展开 end // 后续各级类似最终得到 fifteensad每一级的输出我都在寄存器里打了一拍。也就是说从窗口像素进入流水线到SAD值稳定输出一共有9拍8级加法树接力加1拍输入对齐。计算吞吐率并不会因此下降因为每个时钟周期都有新的窗口数据进来流水线的每一级都在同时工作输出端每个周期都会冒出一个新的SAD值。这种“延迟9个周期、吞吐率1个周期1个结果”的模式是时域上最经济的做法。4.3 模板存储与实时更新模板数据存储在BRAM中位宽为16x16x8 2048位。由于我们要在同一时钟周期访问全部256个数据最好是把模板放进寄存器阵列而不是BRAM这样读端口完全不受限制。16x16x8bit的寄存器阵列在7系列FPGA上需要大约256个8bit寄存器大约占512个SLICE完全可以接受。模板的初始值可以通过AXI-Lite接口从PS端如果你用ZYNQ或者串口等方式写入。运行时如果需要动态更新模板我们在帧消隐期间按上面说的双缓冲方式用新模板覆盖旧模板。由于是寄存器阵列更新操作可以串行逐字写入不需要额外控制逻辑在消隐期的时钟周期数量足够完成全部256字节的写入。4.4 全流水线的工作时序把上面这些模块串起来完整的工作时序是这样的在每一帧的de有效期间像素数据流持续流入窗口生成模块生成16x16窗口窗口数据在下一个时钟沿进入SAD计算阵列经过9拍流水线后输出当前窗口的SAD值与此同时最小位置搜索模块比较当前SAD值和已保存的最小值如果更小就更新坐标寄存器。当vsync上升沿来临时锁存最终坐标并输出。一个至关重要的时序约束是搜索模块的消息必须和流水线的输出严格对齐。也就是说当第N个窗口的SAD值在流水线出口出现时最小位置搜索模块必须知道这个SAD值对应的是哪一行哪一列的窗口否则坐标就错位了。解决办法是用计数器跟踪窗口坐标在SAD值进入流水线的那一拍把坐标打拍到延时链里延时链的深度就是SAD计算流水线的深度9拍这样坐标和SAD值能同时到达搜索模块。// 坐标延时链与SAD流水线深度对齐 reg [10:0] row_delay [0:8]; reg [10:0] col_delay [0:8]; always (posedge clk) begin row_delay[0] curr_row; col_delay[0] curr_col; for (int d 1; d 9; d d 1) begin row_delay[d] row_delay[d-1]; col_delay[d] col_delay[d-1]; end end这个细节我觉得是整个模块最容易出错的地方很多初学者写完SAD计算发现坐标输出是乱的问题十有八九就出在这里。5. 最小位置搜索与坐标输出的Lamda时序设计SAD值是一帧图像上每一窗口位置相似度的度量现在有了一连串SAD值以后要从这一串数值里找全局最小。这个搜最小模块的逻辑本身不复杂难点在于要对齐流水线延迟并且正确处理帧边界。5.1 全局最小搜索与坐标锁存参考代码reg [14:0] min_sad; reg [10:0] best_row; reg [10:0] best_col; reg result_valid; always (posedge clk) begin if (frame_start) begin // vsync上升沿同步复位 min_sad 15h7FFF; // 初始化为最大值 result_valid 1b0; end else if (sad_valid) begin if (sad_value min_sad) begin min_sad sad_value; best_row row_delay[8]; best_col col_delay[8]; result_valid 1b0; // 仍在搜索中 end end else if (frame_end) begin result_valid 1b1; // 帧结束锁存最终结果 end endframe_start信号是每帧图像开始的标志可以是vsync的上升沿也可以是行缓冲模块生成的frame_start_calc信号。更严谨的做法是在“宽度-模板宽度1”个有效窗口计算完成后再等待“高度-模板高度1”行扫描完毕用这个“全图搜索完毕”信号作为frame_end此时锁存best_row和best_col才是最终结果。我的做法是额外维护一个窗口计数器统计当前帧内已经计算过SAD值的窗口总数当计数等于预期窗口总数时产生frame_done脉冲搜索模块在这个脉冲到来后锁存坐标。5.2 early_done低功耗优化前面提到过当最小SAD值已经低于某一阈值比如模板总体方差的一定比例时说明当前窗口和模板已经非常接近继续搜下去的意义不大。此时可以拉高early_done信号通知上游模块停止产生新的窗口数据坐标输出直接使用当前最佳结果。这个设计在电池供电的嵌入式视觉设备上非常实用。实测在光照稳定、目标特征明显的场景里大部分帧都会在扫描到第30%~50%区域前触发early_doneSAD计算阵列的翻转率大幅下降动态功耗降了将近一半。阈值设多少需要根据你的模板内容和场景仔细调一个简单的方法是采集一批视频统计正确匹配位置上的SAD值的上限把阈值设为这个上限的1.1倍。5.3 坐标输出的时钟域处理如果整个系统跑在同一个时钟域里坐标输出直接就是一个寄存器逻辑很简单。但在实际项目中FPGA往往要和外部MCU、DSP或者上位机通信这些处理器跑在完全不同的时钟域常见的有UART115200波特率、SPI10MHz级别或者千兆网口125MHz。跨时钟域处理的关键是不要用单寄存器的电平信号直接跨时钟域采样轻则亚稳态重则采到垃圾数据。我一般用异步FIFO来跨时钟域传递坐标数据。发送端像素时钟域把坐标写入FIFO接收端UART/网口时钟域从FIFO读出并通过协议发送。Xilinx提供了XPM_FIFO原语配置成异步读写的标准模式两端的宽度和深度都可以参数化代码干净又不容易出错。如果你不想用FIFO也可以用两个寄存器的同步链加握手信号但必须在代码里加(* ASYNC_REG TRUE *)约束时序上要留够裕量。总之跨时钟域这块千万别省我见过太多次因为图省事直接采电平导致设备偶发性抽风的问题了。6. 板级调试与性能实测那些综合报告不会告诉你的坑写完代码仿真通过以为就万事大吉了上板调试才是真正考验耐心的地方。我把自己在这一项目里撞过的墙和总结的经验列出来希望能帮你少走弯路。6.1 时序收敛是第一道坎SAD计算阵列里有大量的组合逻辑加法器路径如果随便写不优化时序综合后最容易遇到的问题就是WNSWorst Negative Slack为负。我遇到过的情况是无约束时关键路径延迟高达8.7ns而目标时钟周期是5ns200MHz差了将近一倍。我的优化顺序是先确认每个模块的寄存器是否打在了“正确的位置”。加法树的每一级输出是否都有寄存器窗口数据从行缓冲出来到进入计算阵列是否有输入打拍如果整个SAD计算阵列的输入数据是直接来自BRAM的异步读数据组合路径会特别长必须在读数据后再打一拍。再检查是否存在大位宽的比较器。最小搜索模块里if (sad_value min_sad)是一个16位比较器它本身不慢但它接在SAD输出和计数器延时链输出之后容易成为路径终点。我的做法是让比较器的输入都来自寄存器比较结果打一拍再反馈控制。还不行就降低时钟频率或者做多周期路径约束。我最终把系统主频稳定在180MHzWNS留了0.2ns左右的余量在工业级温度范围-40到85摄氏度下跑了老化测试没有出错。对于图像处理项目来说180MHz已经足够流畅处理720p60fps的SAD计算没必要盲目追求高频。6.2 实测帧率与资源占用以Xilinx ZYNQ XC7Z020-2CLG484为例综合实现后的资源报告大致如下资源使用量总量占比LUT12,40653,20023.3%LUTRAM1,12517,4006.5%FF8,932106,4008.4%BRAM10.51407.5%DSP02200%BUFG53215.6%可以看到DSP占用为零资源大头在LUT这说明SAD算法确实非常“逻辑友好”。整个工程留给后续扩展比如加卡尔曼滤波、加PID控制、加多个模板的余量非常充足。帧率实测我是在720p分辨率、16x16模板、两阶段匹配方案下测的最高跑到58fps接近理论值60fps跟踪误差方面在目标做匀速直线运动且无遮挡时定位误差控制在1个像素以内在目标快速变速运动时有轻微滞后这个主要不是SAD的问题而是单帧搜索本身不带运动预测要解决得叠加卡尔曼滤波或者增加搜索中心预测。6.3 光照变化与匹配失败RESET机制SAD对光照敏感是它最大的短板。实际场景里哪怕同一盏灯开灯瞬间和稳定后图像的灰度分布都会有明显差异。如果目标区域的灰度整体抬高了50个灰阶SAD值会剧烈升高最小位置可能跳到背景去。我在实际项目里发现了一个比较实用的补救手段每帧记录最佳SAD值和次佳SAD值的比值当这个比值接近1比如小于1.2时说明当前帧的匹配结果置信度很低全图有多个位置长得和模板差不多这时候宁可不输出坐标也不输出一个错误坐标。具体做法是维护两个最小值和它们的位置在帧末计算比值低于阈值就置tracking_valid为低。后续的控制系统看到这个标志位为低可以进入保持状态或者重新初始化模板。这个方法成本极低一个减法和一个比较器但能避免非常多因为误匹配导致的“飞出天际”问题。6.4 模板初始化首帧截取与后续校验“模板从哪来”也是一个核心问题。我常用的方案有两种手动初始化上位机把目标框的位置下发到FPGAFPGA在下一帧的对应区域截取像素内容作为模板。注意截取的是灰度图还是RGB图要提前约定好两者对匹配结果影响不大但实现复杂度差不少。自动初始化在指定的ROI区域内计算图像方差选取方差最大的区域作为模板。思路是方差大说明纹理丰富匹配不容易产生歧义。这个方法适合目标进入画面时自动锁定跟踪的场合。初始化完成后还应该加一道自校验统计模板的灰度均值和方差如果方差太小比如全黑或全白区域说明选中的区域没有足够特征直接拒绝并提示重新选框。这个逻辑放在PS端软件做或者纯逻辑实现都可以取决于你的系统架构。7. 进阶优化多目标跟踪与模板旋转适配基础版本的SAD模板匹配能解决“一个固定模板、平移运动”的场景但如果你的项目再往前走一步会遇到两类常见需求跟踪多个目标、目标自身旋转。7.1 多目标跟踪的扩展思路多目标跟踪最直接的办法就是把SAD计算阵列复制多份每份对应一个目标模板。在资源充足的情况下这是最简单的方案但要注意几个问题一是多个目标可能同时出现在同一个窗口附近各自的搜索模块会产生相近的坐标需要有碰撞检测逻辑避免两个跟踪器输出同一个目标二是保持硬件并行度超过4~8路以后LUT消耗会很可观需要评估成本。另一个思路是时分复用SAD计算阵列只有一套但把4路目标的模板存在不同地址空间在扫描时逐帧轮流切换模板进行计算。比如第1帧算模板A、第2帧算模板B这样4路目标就会“轮询”更新帧率除以4。如果你的场景里目标运动速度不快这个方案完全够用而且几乎不增加资源。我自己的一个项目就用了这个折中4路目标轮询每路目标实际更新频率为15fps对低速运动目标来说完全是够用的。7.2 旋转目标的SAD改进多角度模板融合目标在画面里发生缓慢旋转时固定模板的匹配效果会逐渐下降。工业界比较经典的改进是预先离线生成多角度的模板比如每5度采样一个共72个角度模板在匹配时每个角度模板都算一遍SAD取所有角度中最小的作为最终匹配。这个方法在FPGA上实现时模板存储器容量会变成原来的72倍但计算阵列可以复用——因为每个角度模板的尺寸是一样的计算结构完全相同只是从BRAM里取的模板数据地址不同。在帧率要求不是极端高的场合可以在不同帧间循环切换角度模板比如第1帧匹配0度模板、第2帧匹配5度模板、第3帧匹配10度模板……一个完整的72角度扫描在72帧内完成目标旋转速度较慢时这完全不影响跟踪的连续性。还有一种更轻量的方案是低秩近似把目标区域的梯度方向直方图算出来用主方向作为目标的姿态估计再用姿态角从离线模板库中选最接近的角度模板。这个方案对FPGA的资源开销更小但工程实现复杂度高一些如果不是特别必要一般用轮询角度模板就够用了。7.3 融合运动模型的预测-校正框架当你发现目标快速运动时逐帧全图扫描会浪费大量计算在“根本不可能出现目标”的区域。解决办法是用上一帧的位置和速度做线性预测得到当前帧的预测中心然后只在预测中心周围的一个小邻域内做精匹配。这一步相当于给SAD匹配加了一个运动先验匹配速度和稳定性都能显著提升。具体做法用两个坐标寄存器存上一帧和上上帧的位置计算速度向量当前帧的搜索中心就是“上一帧位置 速度向量”预测出来的位置搜索半径为最大预期速度乘帧间隔时间换算成像素数通常取20~30像素。这个逻辑在PS端软件里做特别简单但如果你想把整个系统都放进FPGA用定点数实现也不复杂位置用16位定点数高10位整数、低6位小数速度用(position_new - position_old) 1的移位方式近似。预测中心和实际中心如果偏差过大还可以触发重新初始化模板的流程是一种有效的错误恢复机制。8. 基于本项目的总结与资源开销再审视SAD模板匹配在FPGA中实现目标跟踪本质上是一道“用硬件并行度和深度流水线换取暴力计算速度”的题。它不像深度学习目标检测那样“智能”但凭借极其规则的运算结构、极低的资源消耗以及对实时性近乎苛刻的满足能力在工业视觉、机器人控制等领域依然是最可靠的方案之一。拿我自己的项目总结一套可以直接复用的数据点在Xilinx 7系列平台上16x16模板、1280x72060fps的输入两阶段粗精匹配加动态模板更新整个跟踪系统只占用约23%的LUT、0%的DSP和7.5%的BRAM留给用户的资源余量非常可观。如果你不需要在FPGA里做后续的PID控制甚至可以把PS端的ARM核空出来跑通信协议栈和人机交互代码整套系统的性价比相当高。最后分享一个调试心得。如果你第一次上板发现匹配结果时对时错先别急着怀疑算法试试把整帧图像的de信号用逻辑分析仪抓出来看看——我遇到过的情况是相机输出时序里带了一个我没料到的水平消隐间隙导致行缓冲里的数据错位了一行整个匹配坐标全部往下偏了一行。这种问题不看时序、只看结果是很难定位出来的。FPGA调试就是这样算法层面想得再透彻最后还是得回到信号时序上较真。