HEVC(十二)：基于块匹配的运动估计算法与算法优化

在视频编码中，帧间预测（Inter Prediction）是消除时间冗余、提升压缩效率的关键所在。作为帧间预测的核心，运动估计（ME, Motion Estimation）通过在已编码的参考帧中寻找与当前块最相似的匹配块，计算出运动向量（MV, Motion Vector）。

HEVC（H.265）引入了灵活的编码树单元（CTU）和预测单元（PU）划分机制，使得运动估计的搜索空间和计算复杂度呈指数级增长。如何在保证压缩效率（率失真性能）的同时，大幅降低运动估计的计算复杂度，是视频编码器工程落地的核心痛点。

一图总结

HEVC 块匹配运动估计的核心原理

灵活的 PU 划分带来的计算灾难

相较于 H.264 固定大小的宏块（16×1616\times1616×16），HEVC 的预测单元（PU）支持从64×6464\times6464×64到4×44\times44×4的多尺度划分，并引入了非对称运动划分（AMP，如24×6424\times6424×64、64×4864\times4864×48等）。这意味着对于一个64×6464\times6464×64的 CTU，编码器需要对数十种可能的 PU 划分组合分别进行运动估计，计算量暴增。

匹配准则：SAD、SATD 与 RD Cost

在块匹配过程中，评价“相似度”的计算准则直接决定了复杂度和画质：

• SAD（绝对误差和）：计算最简单，适合在快速搜索的早期阶段大量使用。

  SAD=∑i∑j∣Pcur(i,j)−Pref(i,j)∣SAD = \sum_{i} \sum_{j} |P_{cur}(i,j) - P_{ref}(i,j)|SAD=i∑​j∑​∣Pcur​(i,j)−Pref​(i,j)∣

• SATD（哈达玛变换绝对误差和）：在 SAD 基础上引入 Hadamard 变换，能更好地模拟频域中的残差能量，对主观画质和实际码率的预测更准，但计算量约为 SAD 的 3 倍。

• RD Cost（率失真代价）：终极评估标准。结合了残差畸变DDD和运动向量编码所需的实际码率RRR：

  J=D+λ⋅RJ = D + \lambda \cdot RJ=D+λ⋅R

  由于计算JJJ需要进行完整的量化和熵编码，复杂度极高，通常仅在确定最优候选 MV 时使用。

亚像素精度运动估计

为了捕捉微小的运动，HEVC 支持 1/4 像素精度（Quarter-Pel）的亮度运动估计。

• 半像素内插：采用 8 抽头 DCT-IF 滤波器。
• 1/4 像素内插：采用 7 抽头 DCT-IF 滤波器。 多抽头滤波意味着在进行亚像素搜索时，内存带宽和计算插值的开销非常巨大。

经典块匹配搜索算法

如果采用全搜索算法（FS, Full Search），在搜索窗内逐像素匹配，虽能找到全局最优解，但芯片或 CPU 根本无法做到实时编码。因此，工程上引入了高效的快速搜索算法：

TZSearch 算法（HEVC 官方 HM 模型默认）

TZSearch 是目前公认在率失真性能和计算复杂度上平衡得最好的算法之一。其核心步骤如下：

1. 预测 MV 作为搜索起点：利用时空相邻块的 MV（如 AMVP 候选集）预测出数个可能的起点，选择 SAD 最小的作为搜索中心。
2. 正方形/菱形网格搜索（Grid Search）：以步长1,2,4,8,…,2N1, 2, 4, 8, \dots, 2^N1,2,4,8,…,2N呈指数增长的形式向外做同心圆（正方形或菱形）搜索。
3. 光栅扫描（Raster Search）：如果在步骤 2 中找到的最优点距离中心太远（说明发生了大运动），则在整个搜索窗内进行大步长的光栅扫描，防止陷入局部最优。
4. 两段式细化搜索（Refinement）：在上述步骤确定的最优点周围，以步长为 1 进行精细的菱形或正方形搜索，直至收敛。

运动估计

在实际工程落地（如开发基于 C++/SIMD 的软编编码器或 FPGA/ASIC 硬件编码器）时，必须对运动估计进行极限榨干。以下是四个层面的核心优化策略：

算法层：基于纹理与时空相关性的提前终止（Early Termination）

绝大多数视频序列在时间和空间上具有极强的连续性。通过提前结束不必要的搜索，可以省去 60% 以上的计算量。

• SAD 边界预测与阈值终止：利用当前块左方、上方已编码块的最小 SAD 值，动态计算出一个“全平滑阈值”THSADTH_{SAD}THSAD​。在搜索过程中，一旦当前候选点的 SAD 小于该阈值，立即判定为“足够优秀的匹配”，直接终止后续搜索。
• 全零块（Zero Block）提前判定：在 Lookahead（预分析）阶段计算当前块的方差。若方差极小且当前 SAD 满足阈值，可预测其残差经量化后必为全零（CBF=0）。此时无需再做多模式 PU 划分，直接跳过该 CU 的其他模式搜索。

软件工程层：SIMD 矢量化指令集改写（x86 AVX2/ARM Neon）

运动估计中 80% 的时间消耗在大量的加减法和绝对值计算（SAD/SATD）上。这是典型的SIMD（单指令多数据）应用场景。

• AVX2 优化实例（以16×1616\times1616×16块的 SAD 计算为例）：

  在 x86 架构下，使用_mm256_sad_epu8（VPSADBW）指令，一条指令可以同时计算 32 个uint8_t像素的绝对差值并求和。通过循环展开（Loop Unrolling），将多行像素读入寄存器，并行并行处理，性能相较于纯 C++ 循环可提升8 ~ 10 倍。

• 内存对齐（Memory Alignment）：确保当前帧和参考帧的图像缓冲区在内存中是 32 字节或 64 字节对齐的。这样可以使用_mm256_load_si256代替非对齐的_mm256_loadu_si256，直接打满内存总线带宽。

硬件与架构层：参考帧缓存与数据流水线优化

在 4K@60fps 甚至 8K 编码场景下，运动估计最大的瓶颈往往不是算力，而是内存带宽（Memory Bandwidth）。

• 数据复用（Data Reuse / Level-C 流水线）：当搜索窗口在参考帧中滑动时，相邻两个搜索块所覆盖的参考帧像素有极大的重叠。工程上通常在片上 SRAM（或 CPU L1/L2 Cache）中开辟一个固定大小的Search Window Buffer。当当前块发生位移时，只从外部 DDR 中补充边缘的新像素（拉入一列/一行），最大程度减少对外部通用内存的重复读取。
• 亚像素搜索解耦（Two-stage ME）：千万不要在全搜索阶段就带入亚像素插值。正确做法是分两步：
  1. 整像素搜索：在原始参考帧像素上用快速算法（如 TZSearch）找到最优整像素点MVintegerMV_{integer}MVinteger​。
  2. 亚像素精细化：仅针对MVintegerMV_{integer}MVinteger​周围的3×33\times33×3（半像素）和接下来的3×33\times33×3（1/4像素）小区域进行局部插值和选优，将插值过滤器的调用次数降低到极点。

率失真层：基于哈达玛变换（SATD）的快速模式过滤

由于 SAD 没有考虑像素间的空间相关性，仅用 SAD 选出来的 MV 往往不是码率最低的。为了避免直接计算昂贵的 RD Cost，可以采用SAD -> SATD -> RD Cost的多级级联过滤机制：

1. 采用纯 SAD 在大范围内筛出前 5 个较优候选 MV。
2. 对这 5 个候选点进行快大小的Hadamard 变换，计算出 SATD。
3. 结合位元估计（Bit Estimation，预测 MV 编码所需比特数），计算近似代价：JSATD=SATD+λ⋅RmvJ_{SATD} = SATD + \lambda \cdot R_{mv}JSATD​=SATD+λ⋅Rmv​。
4. 仅对JSATDJ_{SATD}JSATD​最优的 1~2 个候选模式进行真正的亚像素插值和 RD Cost 最终裁决。

总结

HEVC 的运动估计算法优化，本质上是一场算力、带宽与率失真性能之间的博弈。

在实际生产环境中，算法人员需要根据应用场景灵活定制策略：对于低延时、高并发的流媒体直播或监控场景，应果断阉割 AMP 模式，依靠“纹理预测提前终止 + SIMD 极限加速的 TZSearch”来压榨 CPU；而对于离线转码，则应引入完整的多级 SATD 过滤及动态码率控制，以换取最高的画质压缩比。掌握这些干货，是调优各类开源（如 x265）或自研编码器的核心根基。