编码与格式 / 系统课时

用块匹配搜索运动矢量

用块匹配搜索运动矢量

视频中一个物体移动后,当前帧的像素往往能在参考帧的附近找到相似内容。块匹配就是通过搜索参考帧中的候选区域,找到与当前块误差最小的位置,并计算运动矢量。本篇用具体像素数据完成一次搜索,再比较全搜索与快速搜索的计算成本。

学习目标

  • 理解当前块、参考块、搜索窗口和运动矢量的坐标关系。
  • 使用绝对误差和(SAD)计算候选块的匹配代价,完成一次全搜索。
  • 估算不同搜索策略的计算量,理解快速搜索可能遗漏最佳匹配的原因。

块匹配究竟在搜索什么

假设视频中一个白色方块向右移动了 3 个像素。编码器处理当前帧时,不必直接编码整个方块的所有像素,而是可以寻找参考帧中原来那个方块的位置,再编码位置差和预测残差。

块匹配通常包含四个对象:

  • 当前块:当前帧中需要预测的矩形像素区域,例如 16×16 像素。
  • 参考帧:编码器和解码器能够共同使用的已重建参考图像。
  • 搜索窗口:允许从参考帧中寻找候选块的空间范围。
  • 运动矢量:从当前块位置指向选中参考块位置的二维位移。

这里采用常见的坐标约定:图像左上角是原点,向右为正 xx,向下为正 yy。当前块左上角为 (x,y)(x,y),参考块左上角为 (x+dx,y+dy)(x+dx,y+dy),则运动矢量为 (dx,dy)(dx,dy)。

例如,当前块坐标为 (40,20)(40,20),参考块坐标为 (37,20)(37,20),运动矢量就是 (−3,0)(-3,0)。这表示解码器预测当前块时,需要从参考帧当前位置左侧 3 个像素取样;它不等同于物体从上一帧到当前帧的运动方向。

当前块、搜索窗口和运动矢量的空间关系

实际编码器经常使用不同大小的预测块以及亚像素运动精度。为了先把搜索过程算清楚,下面只讨论整数像素位移和单一参考帧,暂不涉及插值与多参考帧选择。

用 SAD 衡量两个块有多相似

块匹配需要一个可计算的评价指标。绝对误差和(Sum of Absolute Differences,SAD)会逐个比较当前块和候选参考块的像素值,将差的绝对值相加。

对于宽 WW、高 HH 的亮度块,计算公式为:

SAD(dx,dy)=∑j=0H−1∑i=0W−1∣C(x+i,y+j)−R(x+dx+i,y+dy+j)∣SAD(dx,dy)=\sum_{j=0}^{H-1}\sum_{i=0}^{W-1}|C(x+i,y+j)-R(x+dx+i,y+dy+j)|

其中 CC 为当前帧亮度值,RR 为参考帧亮度值。SAD 越小,代表像素越相似;SAD 等于 0,说明两个块在当前比较精度下完全相同。

例如当前 2×2 块和某个候选块如下:

像素位置 当前块 候选块 绝对误差
左上 50 48 2
右上 60 64 4
左下 70 69 1
右下 80 77 3

于是 SAD=2+4+1+3=10SAD=2+4+1+3=10。若另一个候选块的 SAD 为 26,在仅比较 SAD 的情况下,优先选择误差为 10 的候选块。

SAD 不考虑视觉结构和运动矢量的码率,因此不能保证选择到最终编码成本最低的候选块。实际编码器常使用包含失真与码率的代价,例如 J=D+λRJ=D+\lambda R,其中 DD 表示预测失真,RR 表示运动信息等编码所需比特数,λ\lambda 控制码率权重。SAD 可以作为运动搜索中的快速匹配指标。

手算一次搜索并找到运动矢量

假设当前块左上角坐标为 (4,4)(4,4),搜索范围为水平与垂直方向各 ±1 个像素。候选位移分别取 −1-1、00、11,一共需要比较 3×3=93×3=9 个候选块。

为了便于手算,当前块设为以下 2×2 灰度数据:

行 第 1 列 第 2 列
第 1 行 50 60
第 2 行 70 80

假设从参考帧取出的 9 个候选块经过逐像素比较,得到以下 SAD:

dy / dx -1 0 1
-1 32 24 38
0 10 45 57
1 28 36 49

最小误差为 10,位置对应 dx=−1dx=-1、dy=0dy=0。因此选中参考块左上角为 (3,4)(3,4),运动矢量为 (−1,0)(-1,0)。

对这组数据,编码器可以使用参考帧 (3,4)(3,4) 位置的块来预测当前块;实际编码时还需要处理预测残差。若多个位置的 SAD 相同,可以规定优先选择运动矢量长度更短的候选,或者进一步比较运动矢量编码成本,使结果具有确定性。

下面使用 Python 3 和 NumPy 复现搜索。先运行 python -m pip install numpy 安装依赖,再保存为 motion_search.py。

python
import numpy as np

# 构造参考帧:在偏左位置放入待匹配的亮度块
reference = np.zeros((8, 8), dtype=np.int16)
reference[4:6, 3:5] = [[50, 60], [70, 80]]
current = np.array([[50, 60], [70, 80]], dtype=np.int16)

x, y, radius = 4, 4, 1
best = (float('inf'), 0, 0)

# 全搜索:逐个枚举搜索窗口中的合法整数像素位移
for dy in range(-radius, radius + 1):
    for dx in range(-radius, radius + 1):
        candidate = reference[y + dy:y + dy + 2,
                              x + dx:x + dx + 2]
        sad = int(np.abs(current - candidate).sum())
        if sad < best[0]:
            best = (sad, dx, dy)

print(f"SAD={best[0]}, MV=({best[1]},{best[2]})")

预期输出:

text
SAD=0, MV=(-1,0)

程序使用人工构造的参考帧,最佳候选恰好完全一致,因此 SAD 为 0;前面的手算表使用另一组候选误差,最小 SAD 为 10。两者共同说明搜索过程,不能把两组不同的像素数据当作同一次实验。

代码使用有符号整数,避免无符号 8 位数组直接相减发生下溢。示例的 8×8 参考帧足以容纳全部候选块;实际项目必须检查图像边界,否则靠近画面边缘时可能截取到不完整的候选块。

全搜索的计算成本有多高

全搜索(Full Search)会在限定窗口内枚举所有整数像素候选位置。若水平和垂直搜索半径均为 pp,且没有边界裁剪,候选数量为:

N=(2p+1)2N=(2p+1)^2

对于每个候选,需要比较 W×HW×H 个像素。忽略循环、缓存和其他开销,直接计算 SAD 的时间复杂度约为 O((2p+1)2WH)O((2p+1)^2WH)。

以 16×16 块为例:

搜索半径 候选位置数 像素绝对差计算次数
±4 81 20,736
±8 289 73,984
±16 1,089 278,784
±32 4,225 1,081,600

搜索半径从 8 增加到 16,候选数从 289 增加到 1,089,约为原来的 3.77 倍。这还只是一个块的搜索量,如果一帧有数千个预测块,再考虑多个参考帧,计算成本会迅速上升。

全搜索的优势是:在给定的整数搜索窗口和指定 SAD 指标下,可以找到全局最小 SAD 的候选。它并不保证全视频的率失真最优,因为分块方式、参考帧选择、亚像素插值和运动矢量码率等因素尚未计入。

快速搜索为什么能减少计算量

快速运动搜索不会把窗口内所有位置都计算一遍,而是先选择少量候选,再围绕较优位置逐步搜索。例如菱形搜索会利用中心及上下左右等位置进行局部比较,再根据结果移动搜索中心。

下面以一个简化的十字形局部搜索为例,说明候选筛选思想,不把它等同于任何标准编码器的完整实现。

  1. 首先计算 (0,0)(0,0) 与上下左右共 5 个位置的 SAD。
  2. 如果中心位置最优,结束当前搜索;否则移动到 SAD 最小的邻居位置。
  3. 在新中心附近评估尚未计算过的上下左右候选,并重复移动。
  4. 当没有邻居的 SAD 严格低于当前中心,或者达到搜索窗口边界时结束。

全搜索与快速局部搜索候选位置对比

假设某次局部搜索只检查了 17 个互不重复的候选,而相同窗口的全搜索需要 289 个候选,那么候选评估数量约减少 1−17/289=94.1%1-17/289=94.1\%。这是特定搜索轨迹的计算量示例,并非固定性能指标;实际加速效果还受内存访问、向量化和实现方式影响。

局部搜索的代价是可能落入局部最小值:例如 SAD 在 (1,0)(1,0) 附近都较大,但远处 (7,−3)(7,-3) 才是真正的最佳匹配,局部策略就可能提前停止。为减少这种情况,实际编码器常结合运动矢量预测、多起点搜索、分层搜索与必要的局部精细搜索。

怎样检查搜索结果是否可靠

验证运动搜索不能只看是否找到了一个矢量。可用以下三个指标检查算法是否真的有用:

  1. 匹配误差:记录最佳候选 SAD,并与零运动矢量 (0,0)(0,0) 的 SAD 比较。若结果没有改善,应检查候选范围、参考帧内容和搜索过程。
  2. 搜索成本:统计实际评估的唯一候选数量与像素比较次数。相同块大小下,候选数更少通常意味着 SAD 计算工作量更小,但不直接等于运行时间同比下降。
  3. 预测效果:用选中参考块生成预测块,逐像素计算当前块减预测块得到的残差,检查残差能量,并进一步评估实际编码码率。

可以将示例中的搜索半径由 1 改成 2,观察候选数量从 9 增加到 25,但由于人工构造的最佳匹配仍在 (−1,0)(-1,0),输出运动矢量保持不变。若把目标块放到距离当前坐标更远的位置,则必须相应增大参考帧尺寸并检查候选边界。

块匹配的可执行判断标准是:在合法搜索范围内找到误差较低的参考块,同时把候选评估量控制在编码预算内。全搜索适合验证匹配质量和建立基准,快速搜索适合需要限制计算开销的编码过程。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用块匹配搜索运动矢量

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通