块匹配运动估计原理与实现：从视频编码到稳像的工程实践

1. 运动估计到底在解决什么问题

1.1 从一段真实需求说起

前阵子帮一个做视频剪辑的朋友处理一批手持拍摄的素材，画面抖得厉害，他想要一种"把抖动抹平"的效果。我第一反应不是去开防抖插件，而是先想清楚一件事：要抹平抖动，就得先知道每一帧相对上一帧到底动了多少。这个"动了多少"的量化过程，就是运动估计。

运动估计这四个字听起来很学术，但它的本质非常朴素——给定两帧图像，找出它们之间的位移关系。这个位移关系可以是一个全局的平移量，也可以是每个像素各自的移动向量。前者叫全局运动估计，后者叫稠密光流。介于两者之间的，是把画面切成一个个小块，每块单独估计一个运动向量，这就是块匹配运动估计，也是视频编码领域用得最多的一种。

我在实验八里主要折腾的就是块匹配这条路线。原因很简单：它足够直观，代码量可控，而且能直接对应到视频压缩里的运动补偿逻辑。你如果只是想理解运动估计的核心思想，块匹配是最好的切入点；如果你要做视频稳像，全局运动估计更合适；如果你要做目标跟踪或者自动驾驶里的场景流，那稠密光流才是正路。三条路各有各的适用场景，选错了方向，后面调参调到怀疑人生也没用。

1.2 为什么这个实验值得认真做一遍

很多人学数字图像处理，学到运动估计这一章就开始犯迷糊，因为前面的滤波、边缘检测、形态学都是"对单张图做处理"，到了运动估计突然变成"对两张图之间的关系做处理"，思维上要转个弯。但这个弯转过来之后，你会发现很多实际问题都能用同一套框架去拆解。

比如视频压缩，为什么同样一段视频，H.264能比MJPEG小那么多？核心就在于它不存每一帧的完整画面，而是存"这一帧相对上一帧动了多少，残差是多少"。这个"动了多少"就是运动估计的输出。再比如视频稳像，为什么手机拍出来的画面那么稳？因为它实时估计了相机的全局运动，然后把反向的补偿量施加回去。还有慢动作插帧，两帧之间补出来的中间帧，位置就是靠运动估计插出来的。

所以这个实验表面上是在做一道题，实际上是在给你一把钥匙，后面视频编码、稳像、插帧、目标跟踪这些方向，用的都是同一套底层逻辑。我建议你在做这个实验的时候，不要只满足于跑出一个结果图，而是把每一步的中间产物都可视化出来，看看运动向量场长什么样，残差图长什么样，匹配代价的分布长什么样。这些中间产物才是真正帮你建立直觉的东西。

1.3 这个实验适合谁来参考

如果你正在上数字图像处理这门课，实验八大概率是绕不过去的，那这篇内容可以直接当你的操作手册用。如果你已经工作了，但一直对视频处理这块似懂非懂，想找个切入点补一补，块匹配运动估计是最容易上手的一个。如果你是想做视频稳像或者插帧的开发者，前面几节的原理部分可以帮你把概念理清楚，后面的实操部分可以帮你把参数调明白。

需要提前说明的是，这个实验对编程基础有一定要求，至少得会写循环、会操作数组、会读写图像。语言上Python和MATLAB都行，我个人更推荐Python，因为后面如果要接视频处理的库会更顺。但如果你学校要求用MATLAB，也没问题，核心逻辑是一样的，只是语法不同。

2. 块匹配运动估计的核心原理拆解

2.1 为什么要把画面切成块

块匹配的思路，说白了就是"化整为零"。整帧图像的运动太复杂了，前景在动、背景在动、相机也在动，你没法用一个统一的公式描述。但如果我把画面切成16x16的小块，然后假设每个小块内部的运动是一致的，那问题就简化成"这一小块在上一帧的哪个位置"。

这个假设当然不完美。如果块正好切在物体边缘上，块内一半是前景一半是背景，那这个块的运动就没法用单一向量描述，这就是所谓的"块效应"。但工程上我们接受这个不完美，因为它的计算量可控，而且块切得越小，块效应越弱，但计算量越大，这是一个需要权衡的参数。

我在实验里用的块大小是16x16，搜索范围是±16像素。这个组合是比较经典的，视频编码标准里也常用。如果你要做更精细的估计，可以把块缩小到8x8，但搜索范围也要相应调整，不然大运动就搜不到了。

2.2 匹配准则怎么选

块匹配的核心是"怎么判断两个块像不像"。常用的准则有三个：SAD（绝对差之和）、SSD（平方差之和）、NCC（归一化互相关）。

SAD是最简单的，就是把两个块对应位置的像素值相减取绝对值，然后全部加起来。值越小说明越像。它的优点是计算快，没有乘法，全是加法和绝对值，硬件实现特别友好。视频编码里基本都用SAD。

SSD是把差值平方再求和。它对大差值更敏感，所以匹配结果在数值上更"平滑"，但计算量比SAD大，因为多了乘法。如果你对匹配精度要求高，可以用SSD。

NCC是归一化互相关，它对亮度变化不敏感，适合两帧之间曝光有变化的场景。但计算量最大，而且对纹理少的块容易出问题。

我在实验里主要用SAD，因为它是块匹配的"标准答案"，而且后面如果要扩展到视频编码，SAD是绕不开的。但我也建议你把SSD和NCC都实现一遍，对比一下结果，你会对"匹配准则"这个概念有更具体的感受。

2.3 搜索策略的取舍

最笨的搜索方法是全搜索，就是把搜索范围内每一个可能的位置都试一遍，取SAD最小的那个。这个方法一定能找到全局最优，但计算量巨大。如果搜索范围是±16，那每个块要试33x33=1089个位置，每个位置要算256次减法，一个块就是27万次运算。一帧如果有几千个块，那运算量就上亿了。

所以工程上会用快速搜索算法，比如三步搜索、菱形搜索、六边形搜索。这些算法的思路都是"先大步跳，再小步精调"，用少量候选点逼近全局最优。它们不一定能找到真正的最优，但通常能找到接近最优的解，而且速度快很多。

我在实验里两种都实现了。全搜索用来做基准，验证快速搜索的结果对不对。快速搜索用来感受"用精度换速度"这件事到底划不划算。实测下来，菱形搜索在大多数情况下能找到和全搜索一样的结果，但候选点数量只有全搜索的十分之一左右。这个性价比是非常高的。

2.4 运动向量场怎么理解

运动估计的输出是一堆运动向量，每个块一个。把这些向量画在图上，就是运动向量场。箭头方向表示运动方向，箭头长度表示运动幅度。

看运动向量场有几个要点。第一，背景区域的向量通常是一致的，因为相机运动是全局的，背景跟着一起动。第二，前景物体的向量和背景不一样，差异越大说明物体相对背景运动越剧烈。第三，如果某个区域的向量杂乱无章，那大概率是纹理太少，匹配不可靠，出现了误匹配。

我在实验里特意找了一段有平移相机的视频，还有一段有行人走过的视频，分别看它们的运动向量场。平移相机的向量场是整齐的，行人区域的向量场是突变的。这个对比非常直观，建议你也找两段不同特点的素材对比着看。

3. 实操过程与核心环节实现

3.1 实验环境与素材准备

我用的环境是Python 3.9，主要依赖numpy做矩阵运算，opencv做图像读写和可视化，matplotlib做绘图。如果你用MATLAB，对应的函数是imread、imshow、quiver这些，逻辑一样。

素材方面，我准备了三组。第一组是合成的平移图像，就是把一张图整体向右下各移5个像素，这样我知道真实运动是多少，可以用来验证算法对不对。第二组是真实的手持拍摄视频，取相邻两帧，用来感受真实场景的运动。第三组是包含独立运动物体的视频，用来观察前景背景运动不一致的情况。

提示：合成数据非常重要。很多人一上来就拿真实视频调，结果算法对不对都不知道。先用合成数据把流程跑通，确认能恢复出已知的运动量，再去处理真实数据，这样排查问题的时候才有参照。

3.2 块匹配的完整实现步骤

第一步是读取两帧图像，转成灰度图。运动估计通常在灰度图上做，因为彩色三个通道分别估计再合并，计算量翻三倍，而且结果不一定更好。灰度化用标准的加权公式就行。

第二步是确定块的大小和搜索范围。我用的块大小是16，搜索范围是16。这意味着我把当前帧切成16x16的块，然后在参考帧的对应位置周围±16像素的范围内找最像的块。

第三步是遍历每个块，对搜索范围内的每个候选位置计算SAD。这里有个细节要注意：块在图像边缘的时候，搜索范围可能会超出图像边界。我的处理方式是把超出边界的部分裁掉，只计算有效区域。另一种方式是给图像补零或者镜像填充，但那样会引入虚假边缘，影响匹配结果。我倾向于裁掉，虽然会损失一点信息，但不会引入错误。

第四步是记录每个块的最佳匹配位置和对应的运动向量。运动向量就是最佳匹配位置相对于块原位置的偏移量。

第五步是把所有运动向量画出来，同时把残差图也画出来。残差就是当前块减去最佳匹配块之后的差值，残差越小说明匹配越好。

3.3 关键参数的计算与选择

块大小怎么定？我试了8、16、32三档。8x8的块运动向量场更精细，但向量数量多，而且纹理少的块容易误匹配。32x32的块向量场很平滑，但块效应明显，物体边缘的运动会被平均掉。16x16是比较平衡的选择，也是视频编码里的常用值。

搜索范围怎么定？这个取决于你的素材里运动有多快。如果相机移动很慢，±8就够了。如果运动快，可能要±32甚至更大。但搜索范围每扩大一倍，计算量大概翻四倍。我的建议是先估计一下最大运动量，然后搜索范围取最大运动量的1.5倍左右，留一点余量。

匹配准则用SAD还是SSD？我实测下来，在光照稳定的情况下，SAD和SSD的结果差异很小，但SAD快不少。如果两帧之间亮度有变化，SSD会稍微好一点，但也好不了太多。真正对亮度变化鲁棒的是NCC，但计算量太大。所以我的默认选择是SAD，特殊情况再换。

3.4 快速搜索算法的实现要点

菱形搜索是我最推荐的快速算法。它的流程是这样的：先在大菱形上取9个点（中心加周围8个），找到SAD最小的点。如果最小点在中心，说明已经收敛，搜索结束。如果最小点在菱形边上，就以那个点为中心，再取一个小菱形，继续搜。直到最小点落在中心为止。

这个算法的巧妙之处在于，它假设匹配代价的分布是单峰的，而且越靠近最优值代价越小。大多数情况下这个假设成立，所以菱形搜索能很快收敛。但如果代价分布有多个局部极小值，菱形搜索可能会陷进去。这时候可以先用三步搜索做粗定位，再用菱形搜索精调。

我在实验里对比了全搜索、三步搜索、菱形搜索三种方法。在合成数据上，三种方法都能找到正确结果。在真实视频上，菱形搜索偶尔会比全搜索差一两个像素，但速度是十倍以上。这个取舍在工程上是完全可以接受的。

3.5 运动向量场的可视化技巧

直接画箭头图有时候会太密，看不清。我的做法是每隔几个块画一个箭头，或者把箭头长度按比例缩放。另外可以用颜色表示运动方向，用亮度表示运动幅度，这样一张图就能同时表达两个维度的信息。

还有一个技巧是把运动向量场叠加在原图上，这样能直观看到哪个物体的运动向量是什么样的。我通常会把背景的向量画成一种颜色，前景的向量画成另一种颜色，对比非常明显。

残差图也值得一看。如果残差图整体很暗，说明匹配得好。如果某个区域残差很亮，说明那个区域匹配得不好，可能是纹理太少，也可能是运动太复杂超出了搜索范围。残差图是排查问题的好帮手。

4. 常见问题与排查技巧实录

4.1 匹配结果全是零向量怎么办

这是最常见的问题，尤其是新手。现象是运动向量场里所有箭头都是零，看起来好像没有运动。原因通常是搜索范围设成了0，或者循环写错了，根本没遍历候选位置。

排查方法很简单：打印一下搜索范围的循环变量，看看是不是真的在遍历。另外检查一下SAD的计算，如果两个块完全一样，SAD是0，那零向量确实是最优的。但如果所有块都是零向量，那大概率是代码逻辑有问题，不是数据的问题。

还有一种可能是图像读取的时候出了问题，两帧读成了同一帧。检查一下两帧的像素值是不是完全一样，如果是，那说明读取逻辑有问题。

4.2 运动向量场杂乱无章怎么调

如果向量场看起来像一团乱麻，没有明显的规律，通常是以下几个原因。

第一是块太小，纹理太少。16x16的块如果落在纯色区域，匹配结果就是随机的。解决办法是增大块大小，或者对纹理少的块做特殊处理，比如直接继承周围块的运动向量。

第二是搜索范围太小，真实运动超出了搜索范围，算法只能在边界上找一个次优解。解决办法是增大搜索范围，或者先用全局运动估计粗估一下运动量，再设定搜索范围。

第三是匹配准则不合适。如果两帧之间亮度变化大，SAD会失效。这时候换成NCC试试。

第四是图像噪声太大。噪声会干扰匹配，尤其是SAD对噪声很敏感。可以先做一次高斯滤波再估计。

4.3 边缘块的匹配为什么总是不准

边缘块的问题在于，它的搜索范围会超出图像边界。如果处理不当，就会引入虚假的匹配结果。我的处理方式是裁掉超出边界的部分，只计算有效区域。但这样会导致边缘块的SAD计算用的像素数比中间块少，数值上不可比。

一个改进方法是把SAD除以有效像素数，得到平均绝对差，这样不同块之间就可比了。另一个方法是给图像做边界填充，但填充方式要选好，镜像填充比补零好，因为补零会引入强边缘。

我在实验里对比了裁掉和镜像填充两种方式，发现镜像填充在边缘块上的结果更稳定，但计算量稍大。如果你对边缘块的结果要求高，建议用镜像填充。

4.4 快速搜索陷入局部最优怎么破

菱形搜索和三步搜索都有可能陷入局部最优，尤其是当匹配代价的分布不是单峰的时候。判断方法是把全搜索的结果和快速搜索的结果对比，如果差异很大，说明快速搜索陷进去了。

解决办法有几个。一是增大搜索步长，让算法先跳到更远的地方看看。二是用多种快速搜索算法，取它们结果中SAD最小的那个。三是先用全局运动估计得到一个粗略的运动量，然后以这个运动量为中心做小范围搜索，这样能大大降低陷入局部最优的概率。

我在实验里用的是第三种方法，效果最好。全局运动估计可以用相位相关法，速度快，而且对全局平移估计得很准。有了这个粗估值，后面的块匹配就只需要在粗估值附近微调，既快又准。

4.5 常见问题速查表

4.6 几个我踩过的坑

第一个坑是图像数据类型。numpy里图像默认是uint8，做减法的时候如果出现负数会回绕成很大的正数，导致SAD计算完全错误。解决办法是先把图像转成int16或者float32再做运算。这个坑我踩过不止一次，每次都是查半天才发现是数据类型的问题。

第二个坑是运动向量的坐标系。图像坐标是行在前列在后，但画箭头的时候x轴是列，y轴是行，如果不注意就会画反。我建议在代码里明确注释清楚，哪个是行哪个是列，画图的时候再转换。

第三个坑是搜索范围的奇偶性。如果搜索范围是偶数，那候选位置的数量是奇数，中心点正好在正中间。如果搜索范围是奇数，候选位置数量是偶数，中心点就不在正中间了。这个细节在实现快速搜索的时候会影响步长的计算，建议统一用偶数搜索范围。

第四个坑是残差图的显示。残差有正有负，直接显示会很难看。我通常取绝对值再显示，或者把残差归一化到0-255。另外残差图通常整体偏暗，可以做一个伽马变换增强对比度，这样更容易看出问题区域。

5. 从实验到工程的延伸思考

5.1 运动估计在视频编码里的角色

视频编码里的运动估计和实验里做的块匹配，核心逻辑是一样的，但工程上做了大量优化。比如块的大小不是固定的，而是分层的，先估大块再估小块。搜索策略也不是单一的，而是多种算法组合。匹配准则除了SAD还有SATD，就是先做哈达玛变换再算绝对差，对频域特性更敏感。

如果你对这个方向感兴趣，可以去看一下H.264或者H.265的参考软件里运动估计是怎么实现的。代码量很大，但核心思想还是实验里这些。把实验做扎实了，再看工程代码就不会觉得无从下手。

5.2 全局运动估计与视频稳像

视频稳像的核心是估计相机的全局运动，然后施加反向补偿。全局运动估计不需要像块匹配那样逐块估计，而是用整帧图像估计一个统一的运动模型，比如平移、旋转、缩放或者仿射变换。

常用的方法是特征点匹配加模型拟合。先在两帧里找特征点，然后匹配特征点，再用RANSAC拟合运动模型。这个方法比块匹配更鲁棒，因为它不依赖块内运动一致的假设。但它的计算量也更大，而且对特征点少的场景效果不好。

我在实验里用块匹配的运动向量做了一个简单的全局运动估计，就是把所有块的运动向量做平均。这个方法很粗糙，但在相机平移的场景下效果还行。如果要处理旋转和缩放，就得用更复杂的模型。

5.3 光流法与块匹配的区别

光流法估计的是每个像素的运动，比块匹配精细得多。但光流法有两个经典假设：亮度恒定和小运动。亮度恒定假设两帧之间同一个物体的亮度不变，小运动假设相邻帧之间运动很小。这两个假设在实际场景中经常不成立，所以光流法需要配合金字塔分层来扩大运动估计范围。

块匹配不需要亮度恒定假设，因为它比较的是块的相似度，不是像素的亮度。但块匹配的输出是稀疏的，每个块一个向量，不是每个像素一个向量。如果你需要稠密的运动场，光流法更合适。如果你只需要知道每个块动了多少，块匹配更简单直接。

5.4 深度学习时代的运动估计

这几年深度学习在运动估计上用得很多，比如FlowNet、PWC-Net这些网络，直接输入两帧图像，输出稠密光流。它们的精度比传统方法高很多，尤其是处理大运动和遮挡的时候。但它们的计算量也大，而且需要GPU，不适合嵌入式场景。

传统方法并没有被完全取代。在视频编码这种对速度要求极高的场景里，块匹配依然是主流。在手机稳像这种对功耗敏感的场景里，轻量级的传统方法也还在用。我的看法是，传统方法帮你建立直觉，深度学习方法帮你提升精度，两者不是替代关系，而是互补关系。

6. 一些实操心得与建议

做这个实验最大的收获，不是学会了某个具体的算法，而是建立了一种"从运动的角度看图像"的思维方式。以前看视频就是看视频，现在看视频会下意识地想，这一帧相对上一帧，哪些区域动了，动了多少，是全局运动还是局部运动。这种思维方式一旦建立起来，后面学视频编码、稳像、跟踪都会顺很多。

如果你时间有限，我建议把重点放在块匹配的完整实现上，把全搜索和菱形搜索都跑通，把运动向量场和残差图都画出来。快速搜索的细节可以后面再补，但块匹配的核心流程一定要亲手写一遍。看别人的代码和自己写一遍，理解深度完全不一样。

参数调优这块，我的经验是不要一上来就追求完美。先用一组保守的参数把流程跑通，然后每次只调一个参数，观察结果的变化。比如先把块大小固定成16，只调搜索范围，看看搜索范围对结果的影响。然后再固定搜索范围，只调块大小。这样你才能清楚地知道每个参数在起什么作用。

最后分享一个小技巧：如果你觉得运动向量场太密看不清，可以把向量场降采样，每隔4个块画一个箭头。或者用颜色编码运动方向，用饱和度编码运动幅度，这样一张图就能表达四维信息（位置x、位置y、方向、幅度）。这个可视化方法在论文里很常见，自己做实验的时候用起来也很方便。