一个4K视频帧包含超过800万个像素，而相邻两帧之间可能只有5%的像素发生了显著变化。如果不利用这种时间冗余，每秒60帧的4K视频需要大约12Gbps的原始带宽——这是任何网络都无法承受的。运动估计（Motion Estimation, ME）就是解决这个问题的核心技术，它通过在参考帧中寻找当前块的最佳匹配位置，将视频压缩效率提升一个数量级。

代价是计算复杂度。在典型的H.264/HEVC编码器中，运动估计占据了50-80%的编码时间。这意味着一个两小时的电影，软件编码可能需要数小时甚至数天，其中大部分时间都在执行同一种操作：在搜索窗口中比较像素块。

块匹配：时间冗余的数学建模

运动估计的基本假设是：视频序列中相邻帧的内容具有高度相关性。一个物体在t帧位于位置(x, y)，在t+1帧移动到位置(x+dx, y+dy)，位移向量(dx, dy)就是运动向量（Motion Vector, MV）。

flowchart TB
    subgraph 当前帧
        A[当前块<br/>大小 N×N]
    end
    
    subgraph 参考帧
        B[搜索窗口<br/>大小 (N+2R)×(N+2R)]
        C[最佳匹配块]
    end
    
    A -->|计算匹配代价| B
    B -->|遍历所有候选位置| C
    C -->|输出| D[运动向量 MV]
    
    style A fill:#e1f5fe
    style C fill:#c8e6c9
    style D fill:#fff9c4

块匹配算法将当前帧划分为固定大小的块（H.264中最小为4×4，HEVC中最小为4×4或8×8），然后在参考帧的搜索窗口内寻找最佳匹配块。搜索窗口的大小取决于运动幅度——对于快速运动的场景，可能需要64×64甚至更大的窗口。

匹配程度的度量标准决定了搜索的精度和速度。最常用的三种匹配准则是：

SAD（Sum of Absolute Differences，绝对差值和）

$$SAD = \sum_{i=0}^{N-1}\sum_{j=0}^{N-1}|C(i,j) - R(i+dx, j+dy)|$$

SAD计算简单，只需减法和取绝对值，非常适合硬件实现。但它对亮度变化敏感，且没有考虑像素间的空间相关性。

SATD（Sum of Absolute Transformed Differences，变换后绝对差值和）

$$SATD = \sum_{i,j}|H(C - R)|_{i,j}$$

其中H是Hadamard变换。SATD通过2×2或4×4的Hadamard变换将残差转换到频率域，更能反映图像的结构相似性。相比SAD，SATD的率失真预测更准确，但计算量增加约4倍。

SSD（Sum of Squared Differences，平方差和）

$$SSD = \sum_{i=0}^{N-1}\sum_{j=0}^{N-1}(C(i,j) - R(i+dx, j+dy))^2$$

SSD对大误差更敏感（因为平方放大），在理论上与均方误差（MSE）等价。但平方运算在硬件中代价较高，实际编码器中较少使用。

x264编码器实测数据 4×4块 16×16块
SAD计算周期 ~10 cycles ~160 cycles
SATD计算周期 ~40 cycles ~640 cycles
SSD计算周期 ~25 cycles ~400 cycles

实践中，大多数编码器采用分层策略：粗搜索阶段使用SAD快速定位候选区域，精细搜索阶段使用SATD进行最终决策。

搜索算法：精度与速度的博弈

如果搜索窗口大小为W×W，全搜索（Full Search）需要检查W²个候选位置。对于64×64的搜索窗口，每个块需要执行4096次匹配计算。当视频分辨率为4K（3840×2160），帧率为60fps时，每秒需要处理的块数量约为1200万，全搜索的计算量令人望而却步。

三步搜索（Three-Step Search, TSS）

1981年，Koga等人提出的三步搜索是早期快速算法的代表。算法从搜索中心开始，以步长4检查9个点（中心+8个方向），选择匹配最好的点作为新的搜索中心，步长减半。重复直到步长为1。

graph TB
    subgraph 第一步-步长4
        A1["● ● ●<br/>● ★ ●<br/>● ● ●"]
    end
    
    subgraph 第二步-步长2
        A2["  ●  <br/>● ★ ●<br/>  ●  "]
    end
    
    subgraph 第三步-步长1
        A3[" ● <br/>●★●<br/> ● "]
    end
    
    A1 -->|选择最佳点| A2
    A2 -->|选择最佳点| A3
    
    style A1 fill:#e3f2fd
    style A2 fill:#bbdefb
    style A3 fill:#90caf9

三步搜索的复杂度为O(log₂W)，对于64×64窗口只需检查25个点，比全搜索快约160倍。但它有一个致命缺陷：步长固定，容易陷入局部最优。对于大运动物体，初始步长4可能太小，导致搜索方向错误后无法纠正。

钻石搜索（Diamond Search, DS）

2000年，Zhu和Ma提出的钻石搜索成为H.264时代的主流选择。算法使用两种搜索模式：

  • 大钻石模式（LDSP）：9个点，中心+8个对角点，覆盖距离2
  • 小钻石模式（SDSP）：5个点，中心+4个正交点，覆盖距离1
graph LR
    subgraph 大钻石模式LDSP
        L1["    ●    <br/>  ●   ●  <br/>●   ★   ●<br/>  ●   ●  <br/>    ●    "]
    end
    
    subgraph 小钻石模式SDSP
        L2["    ●    <br/>  ● ★ ●  <br/>    ●    "]
    end
    
    L1 -->|最佳点在中心| L2
    L1 -->|最佳点不在中心| L1

算法流程：

  1. 以搜索中心为起点，执行LDSP
  2. 如果最佳点在中心，切换到SDSP，结束
  3. 如果最佳点在边缘，以该点为新中心，重复步骤1

钻石搜索的收敛速度极快。实验数据显示，平均只需3-5次LDSP迭代就能找到最优解，计算量比全搜索减少30-56%。更重要的是，钻石形状比正方形更符合物体运动的各向异性——真实运动在水平/垂直方向更常见。

HEVC标准中，六边形搜索（HM参考软件的默认算法）进一步优化了搜索效率。六边形模式包含7个点，覆盖半径2的范围，但只需检查比钻石更少的点数。

x264编码器的实现采用了UMH（Uneven Multi-Hexagon）搜索，结合了多种策略：

  • 对小运动使用钻石搜索
  • 对中等运动使用六边形搜索
  • 对大运动使用扩展六边形搜索
  • 根据相邻块的运动向量预测搜索起点

搜索算法性能对比

算法 搜索点数（64×64窗口） PSNR损失 适用场景
全搜索 4096 0 dB（最优） 离线编码、质量优先
三步搜索 25 0.3-0.5 dB 早期硬件
钻石搜索 18-35 0.1-0.2 dB H.264实时编码
六边形搜索 15-30 0.1-0.15 dB HEVC编码
UMH搜索 20-50 0.05-0.1 dB x264默认

亚像素运动估计：从整像素到1/4像素精度

整像素搜索的精度有限——物体移动可能不是整数像素。对于25fps的视频，一个物体在两帧之间移动2.5像素是完全可能的。如果只搜索整数位置，匹配误差会显著增加。

H.264引入了1/4像素精度的运动估计，HEVC甚至支持1/8像素（虽然实际编码器很少使用）。实现方式是对参考帧进行插值，在整数像素之间生成亚像素点。

graph TB
    subgraph 整像素网格
        A["●   ●   ●<br/><br/>●   ●   ●<br/><br/>●   ●   ●"]
    end
    
    subgraph 1/2像素插值
        B["● ■ ● ■ ●<br/>□ ◆ □ ◆ □<br/>● ■ ● ■ ●<br/>□ ◆ □ ◆ □<br/>● ■ ● ■ ●"]
    end
    
    subgraph 1/4像素插值
        C["密集网格<br/>16×密度"]
    end
    
    A -->|半像素滤波| B
    B -->|四分之一像素滤波| C
    
    style A fill:#e8f5e9
    style B fill:#c8e6c9
    style C fill:#a5d6a7

H.264的插值过程：

  1. 1/2像素：使用6抽头滤波器 [1, -5, 20, 20, -5, 1]/32
  2. 1/4像素：对相邻像素取平均

HEVC使用更复杂的DCT-IF（DCT-based Interpolation Filter）：

  • 1/2像素：8抽头滤波器
  • 1/4和3/4像素：7抽头滤波器，每个分数位置使用不同的滤波器系数

插值的代价是计算量和存储带宽。对于每个整像素位置，需要访问周围8个像素来计算一个亚像素值。在硬件实现中，这通常需要行缓存来存储参考像素。

亚像素估计带来的增益是显著的。实验表明，从整像素到1/2像素精度，PSNR可提升0.3-0.5 dB；从1/2像素到1/4像素精度，再提升0.2-0.3 dB。考虑到编码复杂度的增加，1/4像素精度是性价比最优的选择。

B帧与双向预测：时间冗余的极致利用

I帧（帧内编码）、P帧（前向预测）、B帧（双向预测）构成了视频编码的基本时间结构。B帧同时使用前向和后向参考帧，能够获得更高的压缩效率。

flowchart LR
    subgraph GOP结构
        I[I帧] --> P1[P帧]
        P1 --> P2[P帧]
        P2 --> P3[P帧]
        
        I -.->|前向参考| B1[B帧]
        P1 -.->|后向参考| B1
        
        P1 -.->|前向参考| B2[B帧]
        P2 -.->|后向参考| B2
    end
    
    style I fill:#ffcdd2
    style P1 fill:#c8e6c9
    style P2 fill:#c8e6c9
    style P3 fill:#c8e6c9
    style B1 fill:#bbdefb
    style B2 fill:#bbdefb

B帧的编码过程：

  1. 在前向参考帧中搜索最佳匹配块，得到MV₀
  2. 在后向参考帧中搜索最佳匹配块，得到MV₁
  3. 根据匹配程度决定预测模式：
    • LIST_0：仅使用前向预测
    • LIST_1：仅使用后向预测
    • BI-PRED：使用两个预测的加权平均

双向预测的增益来自两个因素。首先，对于被遮挡或新出现的区域，可能只有一个方向的参考有效。其次，即使两个方向都有有效参考，加权平均可以进一步降低预测残差。

HEVC进一步引入了**广义B帧（Generalized B-frame）**概念。传统B帧必须严格位于两个参考帧之间，而HEVC的B帧可以使用任意时序的参考帧组合。这允许编码器选择最优的参考帧，而不受时序限制。

运动向量预测：压缩MV本身

运动向量本身也需要编码传输。一个典型的4K视频，如果每个4×4块都传输独立的MV，仅MV数据就会占用可观的码率。解决方案是利用相邻块运动向量之间的空间相关性——相邻块往往属于同一物体，运动相似。

空间预测（MVP）

H.264定义了三种空间预测模式，从相邻已编码块中选择预测向量：

    A   B
    ┌───┐
  C │当前│
    └───┘
  • 中值预测：MV_pred = median(MV_A, MV_B, MV_C)
  • 左向预测：MV_pred = MV_A
  • 上向预测：MV_pred = MV_B

预测残差（MVD = MV - MV_pred）通常比原始MV小得多，编码效率更高。

AMVP（Advanced Motion Vector Prediction）

HEVC的AMVP机制更加灵活。编码器从两个候选预测器中选择最优的一个：

  1. 空间候选：从左侧、上方、右上方、左下方、左上方五个位置选取
  2. 时间候选：从参考帧的同位块获取

编码器通过率失真优化选择最佳预测器，并通过索引标识选择结果。这比H.264的中值预测更适应复杂运动场景。

Merge模式

HEVC引入的Merge模式更进一步：直接复用相邻块的运动信息，包括MV、参考帧索引和预测方向。编码器只需传输Merge索引，无需任何运动参数残差。

flowchart TB
    A[当前块] --> B{检查相邻块运动信息}
    B --> C[构建候选列表<br/>最多5个候选]
    C --> D{是否有相同运动信息?}
    D -->|是| E[Merge模式<br/>仅传输索引]
    D -->|否| F[AMVP模式<br/>传输MVD]
    
    style E fill:#c8e6c9
    style F fill:#fff9c4

Merge模式的优势在于零残差编码。对于平坦区域或均匀运动物体，Merge模式的码率开销几乎为零。HEVC实测数据显示，Merge模式约占所有帧间编码块的50-70%。

率失真优化：质量与码率的数学平衡

运动估计的目标不是找到"最匹配"的块，而是找到"编码效率最高"的块。一个完美匹配的块可能位于搜索窗口边缘，需要用大量比特来编码其运动向量；一个稍差的匹配可能就在预测位置附近，运动向量残差几乎为零。

率失真优化（Rate-Distortion Optimization, RDO）正是解决这个问题的数学框架。目标函数是拉格朗日代价：

$$J = D + \lambda \cdot R$$

其中D是失真（通常用SSE或SAD），R是编码比特数，λ是拉格朗日乘子。λ控制质量与码率的权衡：

  • λ大：偏向低码率，接受更多失真
  • λ小：偏向高质量，接受更高码率
graph LR
    subgraph 率失真曲线
        A((低码率<br/>高失真))
        B((中等码率<br/>中等失真))
        C((高码率<br/>低失真))
    end
    
    A --> B --> C
    
    D[拉格朗日乘子λ] -->|控制选择| A
    D --> B
    D --> C
    
    style A fill:#ffcdd2
    style B fill:#fff9c4
    style C fill:#c8e6c9

λ的选择与量化参数（QP）密切相关。经验公式：

$$\lambda_{mode} = 0.85 \cdot 2^{(QP-12)/3}$$$$\lambda_{motion} = \sqrt{\lambda_{mode}}$$

这意味着运动估计和模式选择使用不同的λ值，运动估计的λ更小（更重视匹配质量）。

实际编码器中的RDO决策：

  1. 对每个候选MV，计算J_mv = SAD + λ_motion × Rate_mv
  2. 选择J_mv最小的MV作为运动估计结果
  3. 对每个编码模式（Intra/Inter/Merge等），计算J_mode = SSE + λ_mode × Rate_total
  4. 选择J_mode最小的模式作为最终编码模式

这种两阶段优化虽然不是全局最优，但计算复杂度可控，是实际编码器的标准做法。

HEVC的CTU结构：从宏块到编码树单元

H.264的宏块固定为16×16像素，在高清时代显得粒度过粗。HEVC引入编码树单元（Coding Tree Unit, CTU），最大可达64×64，并支持递归划分。

graph TB
    subgraph CTU 64×64
        A["64×64"]
        A --> B["32×32"]
        A --> C["32×32"]
        A --> D["32×32"]
        A --> E["32×32"]
        
        B --> B1["16×16"]
        B --> B2["16×16"]
        B --> B3["16×16"]
        B --> B4["16×16"]
    end
    
    style A fill:#e3f2fd
    style B fill:#bbdefb
    style C fill:#bbdefb
    style D fill:#bbdefb
    style E fill:#bbdefb
    style B1 fill:#90caf9

CTU的优势在于：

  1. 大块处理：对于平坦区域或大运动物体，64×64块效率更高
  2. 灵活划分：复杂区域可以递归划分到4×4或8×8
  3. 并行友好：CTU之间相对独立，适合硬件并行处理

但CTU也带来了运动估计的复杂度增长。一个64×64 CTU可能划分为多达85个编码单元（CU），每个CU都需要独立的运动估计。HEVC编码器的运动估计复杂度约为H.264的2-4倍。

CTU大小与编码效率的关系：

CTU大小 编码效率（BD-BR） 编码时间
16×16 基准 1×
32×32 -5% 1.5×
64×64 -8% 2×

64×64 CTU在1080p及以上分辨率视频中效果显著，但对于低分辨率视频，可能反而降低效率。

VVC的仿射运动预测：突破平移模型限制

传统的块匹配假设块内所有像素具有相同的运动——即平移运动模型。这个假设在旋转、缩放、透视变换等场景下完全失效。例如，摄像机旋转时，画面边缘的运动幅度和方向都不同于中心。

VVC（H.266）引入的仿射运动预测（Affine Motion Prediction）使用2个或3个控制点的运动向量，描述更复杂的运动模型。

4参数仿射模型（2个控制点）：

$$\begin{pmatrix} x' \\ y' \end{pmatrix} = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} + \begin{pmatrix} e \\ f \end{pmatrix}$$

6参数仿射模型（3个控制点）：

$$\begin{pmatrix} x' \\ y' \end{pmatrix} = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} + \begin{pmatrix} e + fx \\ f + gx \end{pmatrix}$$
graph LR
    subgraph 平移模型
        A["MV<br/>→"]
        B["块内所有像素<br/>相同运动"]
    end
    
    subgraph 仿射模型
        C["MV0 →<br/>MV1 ↘<br/>MV2 ↓"]
        D["每个像素<br/>不同运动"]
    end
    
    A --> B
    C --> D
    
    style A fill:#ffcdd2
    style B fill:#ffcdd2
    style C fill:#c8e6c9
    style D fill:#c8e6c9

仿射预测的编码流程：

  1. 选择控制点位置（通常为块的顶点）
  2. 对每个控制点执行常规运动估计
  3. 根据控制点MV计算仿射参数
  4. 对块内每个像素计算各自的预测位置
  5. 执行插值获取预测值

计算量是显著的。对于N×N的块，需要计算N²个像素各自的运动向量，然后执行N²次插值。VVC通过以下优化降低复杂度：

  • 子块级处理：将大块划分为4×4子块，每个子块使用相同的子块中心MV
  • 简化插值：使用双线性插值代替高阶滤波器

实验数据显示，仿射预测为VVC带来15-25%的BD-BR增益，尤其在高分辨率、大运动场景下效果显著。

硬件加速：从CPU到专用电路

运动估计是视频编码中最适合硬件加速的部分。其计算特征非常规整：

  • 大量并行度：不同块、不同搜索位置可独立处理
  • 固定计算模式：重复的SAD/SATD运算
  • 规则的数据访问：搜索窗口内的像素访问

SIMD优化

x264等软件编码器广泛使用SIMD指令优化运动估计。SAD计算在SSE/AVX指令集中有专门的指令：

; 16×16 SAD using SSE2
movdqa xmm0, [current_block]
movdqa xmm1, [ref_block]
psadbw xmm0, xmm1  ; 计算绝对差值和

一条PSADBW指令完成16个像素的SAD计算，相比标量代码快约8-16倍。现代CPU的AVX-512甚至可以一次处理64个像素。

GPU加速

GPU的大规模并行性非常适合运动估计。将搜索窗口内的所有候选位置分配给不同的线程，可以实现数百倍的加速。但GPU的挑战在于：

  • 数据传输开销：参考帧需要从CPU传输到GPU
  • 分支发散：不同块的搜索收敛速度不同
  • 内存带宽：大量像素访问对显存带宽要求高

实际应用中，GPU加速主要面向实时编码场景，如视频会议、游戏直播等。离线编码器仍然倾向于使用CPU，因为CPU可以更灵活地实现复杂的率失真优化。

专用硬件

智能手机和相机中的视频编码芯片通常包含专用的运动估计电路。典型的架构是：

  1. 参考帧缓存：存储一个或多个参考帧，容量约几MB
  2. 搜索引擎：并行执行多个搜索点的SAD计算
  3. 决策逻辑：选择最佳匹配，执行亚像素细化

专用电路的能效比CPU/GPU高1-2个数量级。例如，iPhone A系列芯片的视频编码功耗仅为同等软件编码的1/10。

估算硬件资源

对于4K@60fps实时编码，硬件运动估计需要：

参数 数值
每秒处理块数 ~12M（假设64×64 CTU）
每块搜索点数 ~50（快速算法）
每秒SAD计算 ~600M
处理带宽 ~50 Gpixel/s（包括重叠访问）

这意味着需要16-32个并行的SAD计算单元，配合多端口SRAM来存储参考帧。

结语：算法演进的驱动力

运动估计四十年的技术演进，核心驱动力是两个矛盾：

  1. 精度与速度：更高精度的搜索需要更多计算，但实时编码有时间限制
  2. 通用性与专用性：通用算法难以适应所有场景，专用优化又增加复杂度

全搜索到快速算法的演进解决了速度问题，亚像素估计解决了精度问题，RDO解决了编码效率问题，仿射预测突破了平移模型的限制。每一代标准都在这些问题上寻找新的平衡点。

对于编码器开发者而言，理解这些算法背后的权衡至关重要。没有"最优"的运动估计算法，只有"最适合当前场景"的算法。低延迟直播、离线电影编码、机器视觉存储——这些场景对运动估计的需求截然不同，算法选择也必须因地制宜。

参考资料

  1. Richardson, I. E. (2004). H.264 and MPEG-4 Video Compression: Video Coding for Next-generation Multimedia. John Wiley & Sons.
  2. Sullivan, G. J., et al. (2012). Overview of the High Efficiency Video Coding (HEVC) Standard. IEEE Transactions on Circuits and Systems for Video Technology, 22(12), 1649-1668.
  3. Koga, T., et al. (1981). Motion-compensated interframe coding for video conferencing. Proc. NTC, 81, C9.6.
  4. Zhu, S., & Ma, K. K. (2000). A new diamond search algorithm for fast block-matching motion estimation. IEEE Transactions on Image Processing, 9(2), 287-290.
  5. Tourapis, A. M. (2002). Enhanced Predictive Zonal Search for Single and Multiple Frame Motion Estimation. Visual Communications and Image Processing, 4671, 1069-1079.
  6. Sze, V., Budagavi, M., & Sullivan, G. J. (2014). High Efficiency Video Coding (HEVC): Algorithms and Architectures. Springer.
  7. Bossen, F., et al. (2012). HEVC complexity and implementation analysis. IEEE Transactions on Circuits and Systems for Video Technology, 22(12), 1685-1696.
  8. Chen, K., et al. (2018). Algorithm description for Versatile Video Coding and Test Model 4 (VTM 4). JVET-J1002.
  9. Li, B., et al. (2019). An Overview of Rate-Distortion Optimized Quantization in Video Coding. IEEE Transactions on Circuits and Systems for Video Technology.
  10. x264 source code. Motion estimation implementation. https://code.videolan.org/videolan/x264
  11. Fraunhofer HHI. VVC Software VTM. https://vcgit.hhi.fraunhofer.de/jvet/VVCSoftware_VTM
  12. Wikipedia. Block-matching algorithm. https://en.wikipedia.org/wiki/Block-matching_algorithm
  13. Sullivan, G. J., & Wiegand, T. (1998). Rate-distortion optimization for video compression. IEEE Signal Processing Magazine, 15(6), 74-90.
  14. Wiegand, T., et al. (2003). Rate-constrained coder control and comparison of video coding standards. IEEE Transactions on Circuits and Systems for Video Technology, 13(7), 688-703.