📚 课程目录第4章快速搜索算法

4. 快速搜索算法：三步搜索法、菱形搜索法、六边形搜索法、自适应搜索模式

全搜索虽然精度高，但计算量太大。在嵌入式平台或者手机芯片上，每一帧就那么几毫秒的处理时间，根本跑不动。所以工业界搞出了一堆快速搜索算法——说白了，就是用更少的搜索点，找到“差不多最好”的运动矢量。

我这些年调过的降噪算法里，快速搜索占了八成以上。今天把这四种主流方法掰开揉碎讲清楚。

三步搜索法是最经典的快速算法之一。思路很简单：先大步粗搜，再小步细搜。

假设搜索窗口是 ±7 像素，步长从 4 开始，每次减半。

  三步搜索流程：
  第一步：步长=4，检查中心点 + 周围8个点（共9个点），找到最小SAD位置
第二步：以第一步最佳点为中心，步长=2，再检查8个邻域点
第三步：步长=1，最后检查8个邻域点，确定最终运动矢量

总共只需要检查 9+8+8=25 个点，比全搜索的 225 个点少了近 90%。

我的经验：三步搜索法适合运动幅度较大的场景。我在做安防监控的降噪时，经常用它做粗搜阶段的初始化。但要注意——如果运动是亚像素级的，三步法容易陷入局部最优。

菱形搜索法是目前应用最广的快速算法之一。它用两种模板：大菱形和小菱形。

模板类型	形状	搜索点数	用途
大菱形（LDSP）	9个点，呈菱形分布	9	粗搜阶段
小菱形（SDSP）	5个点，呈小菱形分布	5	细搜阶段

算法流程是这样的：先用大菱形反复搜索，直到最佳点出现在中心位置，然后切换到小菱形做最后的精确定位。

避坑指南：我曾经在一个低光照降噪项目里直接用菱形搜索，结果运动估计出来的矢量全是零。后来发现——菱形搜索对平坦区域太敏感了。如果图像纹理少，SAD值差异很小，菱形搜索很容易停在原地。建议在平坦区域加一个纹理检测的预处理。

六边形搜索法比菱形搜索更激进。它用六边形模板，覆盖面积更大，收敛速度更快。

六边形模板有7个点，分布在一个正六边形的顶点和中心。相比菱形的9个点，六边形每次少检查2个点，但覆盖范围反而更大。

  六边形搜索的优势：
  每次迭代检查点数少（7个 vs 菱形9个）
覆盖方向更均匀（6个方向 vs 菱形4个方向）
对斜向运动更友好

我做过对比测试：在同样的搜索精度下，六边形搜索比菱形搜索快约15%。但代价是——如果运动矢量刚好落在六边形的“盲区”里，可能会多迭代几次才能收敛。

前面三种都是固定模板。但实际视频内容千变万化——有的场景运动大，有的场景运动小，有的场景纹理丰富，有的场景一片平坦。固定模板很难在所有场景下都最优。

自适应搜索模式的核心思想：根据运动特征动态调整搜索策略。

我的做法：在实际项目中，我通常用运动矢量预测 + 自适应模式切换。先用前一帧的运动矢量预测当前帧的起始点，然后根据预测矢量的模长自动选择搜索模式。这样既保证了精度，又把计算量压到最低。

下面这张表是我在实际项目中整理的对比数据，供你参考：

算法	搜索点数（±7窗口）	收敛速度	精度	适用场景
全搜索	225	慢	最高	离线处理、精度优先
三步搜索	25	快	中等	大运动、实时性要求高
菱形搜索	13~25（动态）	较快	较高	通用场景、平衡型
六边形搜索	11~21（动态）	最快	较高	实时性极高、资源受限
自适应搜索	5~25（动态）	自适应	高	复杂场景、产品级应用

重要提醒：快速搜索算法虽然快，但都有“局部最优”的问题。我在做运动补偿降噪时，一定会加一个“质量回退”机制——如果快速搜索找到的SAD值比预测值大太多，就回退到全搜索或者扩大搜索范围。宁可慢一点，也不能让运动估计出错。

嗯，快速搜索算法就讲到这里。实际项目中，我建议你从菱形搜索入手，然后根据性能瓶颈逐步优化到自适应模式。别一上来就搞太复杂——先把基础跑通，再谈优化。