3. 全搜索算法：流程、复杂度与优缺点

全搜索，也叫穷举搜索。说白了，就是把搜索窗口里每个候选位置都算一遍，找出最匹配的那个块。这是最暴力、最直接的方法，也是衡量其他快速算法的“黄金标准”。

我刚开始做运动估计时，第一个实现的就是全搜索。那时候觉得，这有什么难的？把所有位置都算一遍不就行了？后来才发现，事情没那么简单——计算量是个大问题。

3.1 全搜索的流程

全搜索的流程其实很直观。我给你拆解一下：

1. 确定搜索窗口：在当前帧中，以当前块为中心，划定一个矩形区域。比如 ±16 像素，那就是 33×33 的搜索范围。
2. 逐点遍历：从窗口的左上角开始，按光栅扫描顺序，依次移动到每个候选位置。
3. 计算匹配代价：在每个候选位置，计算当前块与参考块之间的匹配误差。常用的是 SAD（差值和）或 SSD（平方差值和）。
4. 记录最优：如果当前候选位置的代价小于之前记录的最小值，就更新最优运动向量和最小代价。
5. 输出结果：遍历完整个窗口后，输出最优运动向量。

嗯，这里要注意一个细节：搜索步长。通常步长是 1 个像素，但也可以设为 2 或 4 像素来降低计算量。不过，步长越大，精度损失也越大。

3.2 计算复杂度分析

全搜索的计算复杂度，是它最大的痛点。我们来算一笔账。

假设搜索窗口大小为 (2W+1) × (2W+1)，块大小为 N×N。那么：

• 每个候选位置需要计算 N×N 次像素操作（比如 SAD 的减法、值、累加）。
• 候选位置总数为 (2W+1)²。
• 所以，每个块的总计算量是 O(N² × W²)。

举个例子：W=16，N=16，那么每个块需要计算 33×33×16×16 = 278,784 次操作。对于一帧 1080p 的视频，宏块数量大约是 8160 个。一帧的总操作量就是 278,784 × 8160 ≈ 2.27 × 10⁹ 次。这还只是一帧！

参数	数值	说明
搜索窗口半径 W	16	常见设置
块大小 N	16	标准宏块
候选位置数	1089	(2×16+1)²
每块操作数	278,784	1089 × 256
1080p 宏块数	8160	1920×1080 / 16²
每帧总操作数	~2.27 × 10⁹	约 22.7 亿次

3.3 优缺点讨论

全搜索的优点和缺点都很极端。我们一个一个说。

优点

• 全局最优：这是最大的优势。只要搜索窗口足够大，全搜索一定能找到全局最优的运动向量。其他快速算法都只能找到局部最优。
• 实现简单：代码逻辑非常直接，没有复杂的跳转或提前终止条件。我经常用它作为验证其他算法的基准。
• 结果稳定：不会因为初始搜索点的选择而波动。每次运行结果都一样。

缺点

• 计算量巨大：刚才的复杂度分析已经说明了问题。在实时系统中，这基本是死路。
• 不适合大窗口：如果搜索窗口半径 W 增大，计算量呈平方级增长。W 从 16 增加到 32，计算量翻 4 倍。
• 没有利用运动连续性：全搜索不考虑相邻块的运动相关性，每个块都是独立搜索。其实，相邻块的运动向量往往很接近。

3.4 全搜索的改进思路

既然全搜索这么慢，那有没有办法改进？当然有。我总结了几种常见的思路：

• 提前终止：在遍历过程中，如果当前代价已经小于某个阈值，就提前停止搜索。这需要合理设置阈值。
• 降采样搜索：先在低分辨率图像上做全搜索，得到粗略的运动向量，再在高分辨率图像上做小范围精细搜索。
• 硬件加速：用 GPU 或专用 DSP 并行计算所有候选位置的代价。全搜索的并行性非常好，每个候选位置的计算是独立的。

我个人比较推荐降采样搜索。为什么呢？因为它在精度和速度之间取得了很好的平衡。我曾经在一个项目中，先用 1/4 分辨率做全搜索，再在原始分辨率上做 ±2 像素的精细搜索。速度提升了 10 倍以上，精度损失不到 1%。

3.5 全搜索的适用场景

全搜索虽然慢，但并不是一无是处。在以下场景中，它仍然是不可替代的：

• 算法验证：开发新的快速算法时，用全搜索的结果作为 ground truth，验证新算法的精度。
• 离线处理：对实时性没有要求的场景，比如视频后期处理、电影修复等。
• 小窗口搜索：如果搜索窗口很小（比如 ±4 像素），全搜索的计算量完全可以接受。
• 硬件实现：在 FPGA 或 ASIC 中，全搜索的规则数据流非常适合流水线设计。

你想想看，全搜索就像一把“重剑”。它不灵活，但威力巨大。用对了地方，它就是最好的工具。