📚 课程目录第3章三步搜索法快速运动估计

3. 三步搜索法快速运动估计

任务目标

实现三步搜索法（Three-Step Search, TSS）运动估计，在保证与全搜索（Full Search, FS）精度接近的前提下，将搜索点数从全搜索的 (2W+1)² 减少至 25 个（W 为最大搜索位移）。通过对比两种算法在相同视频帧对上的运动矢量结果与计算量，验证 TSS 的加速效果。

核心原理

三步搜索法以对数递减步长进行粗到细的搜索：初始步长 S = 2^(⌊log2 W⌋)，每次在中心点及周围 8 个邻域点（步长 S）共 9 个候选点中寻找 SAD 最小点，然后将该点作为新中心，步长减半，重复直至 S = 1。总搜索点数为 1 + 8×3 = 25 个（含初始中心点）。

完整实现


import numpy as np

def sad(block1, block2):
    """计算两个等尺寸块的平均误差"""
    return np.sum(np.abs(block1.astype(np.int16) - block2.astype(np.int16)))

def full_search(ref_frame, cur_block, block_pos, block_size, search_range):
    """全搜索：在搜索窗口内遍历所有候选位置，返回最佳运动矢量 (mvx, mvy)"""
    h, w = ref_frame.shape
    bx, by = block_pos  # 当前块左上角坐标
    best_mv = (0, 0)
    best_cost = float('inf')
    for dy in range(-search_range, search_range + 1):
        for dx in range(-search_range, search_range + 1):
            ref_y, ref_x = by + dy, bx + dx
            if ref_y < 0 or ref_x < 0 or ref_y + block_size > h or ref_x + block_size > w:
                continue  # 越界跳过
            ref_block = ref_frame[ref_y:ref_y + block_size, ref_x:ref_x + block_size]
            cost = sad(cur_block, ref_block)
            if cost < best_cost:
                best_cost = cost
                best_mv = (dx, dy)
    return best_mv

def three_step_search(ref_frame, cur_block, block_pos, block_size, search_range):
    """三步搜索法：步长从 S 递减至 1，每步检查 9 个候选点"""
    h, w = ref_frame.shape
    bx, by = block_pos
    # 初始步长：不大于 search_range 的最大 2 的幂
    S = 1
    while S * 2 <= search_range:
        S *= 2
    center_x, center_y = bx, by  # 搜索中心（参考帧坐标）
    best_mv = (0, 0)
    best_cost = float('inf')
    # 先计算初始中心点
    if 0 <= center_y < h - block_size + 1 and 0 <= center_x < w - block_size + 1:
        ref_block = ref_frame[center_y:center_y + block_size, center_x:center_x + block_size]
        best_cost = sad(cur_block, ref_block)
    while S >= 1:
        candidates = [(0, 0), (-S, 0), (S, 0), (0, -S), (0, S),
                      (-S, -S), (-S, S), (S, -S), (S, S)]
        improved = False
        for dx, dy in candidates:
            ref_x, ref_y = center_x + dx, center_y + dy
            if ref_x < 0 or ref_y < 0 or ref_x + block_size > w or ref_y + block_size > h:
                continue
            ref_block = ref_frame[ref_y:ref_y + block_size, ref_x:ref_x + block_size]
            cost = sad(cur_block, ref_block)
            if cost < best_cost:
                best_cost = cost
                best_mv = (dx, dy)
                improved = True
        if improved:
            # 更新中心到最佳候选点
            center_x += best_mv[0]
            center_y += best_mv[1]
        S //= 2
    # 返回相对于原始块位置的最终运动矢量
    return (center_x - bx, center_y - by)

def compare_algorithms(ref_frame, cur_frame, block_size=16, search_range=7):
    """对比全搜索与三步搜索：返回每块的运动矢量及总搜索点数"""
    h, w = cur_frame.shape
    fs_mvs, tss_mvs = [], []
    fs_points, tss_points = 0, 0
    for y in range(0, h - block_size + 1, block_size):
        for x in range(0, w - block_size + 1, block_size):
            cur_block = cur_frame[y:y + block_size, x:x + block_size]
            # 全搜索
            mv_fs = full_search(ref_frame, cur_block, (x, y), block_size, search_range)
            fs_mvs.append(mv_fs)
            fs_points += (2 * search_range + 1) ** 2
            # 三步搜索
            mv_tss = three_step_search(ref_frame, cur_block, (x, y), block_size, search_range)
            tss_mvs.append(mv_tss)
            tss_points += 25  # 固定 25 个搜索点
    return fs_mvs, tss_mvs, fs_points, tss_points

# 最小可复现示例：合成两帧图像（含平移运动）
np.random.seed(42)
frame_size = 64
ref = np.random.randint(0, 256, (frame_size, frame_size), dtype=np.uint8)
cur = np.zeros_like(ref)
# 将参考帧内容向右下平移 (3, 2) 像素生成当前帧
shift_x, shift_y = 3, 2
cur[shift_y:, shift_x:] = ref[:frame_size - shift_y, :frame_size - shift_x]

# 运行对比
fs_mvs, tss_mvs, fs_pts, tss_pts = compare_algorithms(ref, cur)

# 验证：统计运动矢量一致率
match = sum(1 for a, b in zip(fs_mvs, tss_mvs) if a == b)
total_blocks = len(fs_mvs)
print(f"总块数: {total_blocks}")
print(f"全搜索总搜索点数: {fs_pts}, 三步搜索总搜索点数: {tss_pts}")
print(f"搜索点数减少比例: {1 - tss_pts / fs_pts:.2%}")
print(f"运动矢量完全一致块数: {match}/{total_blocks} ({match / total_blocks:.1%})")

运行方式

安装依赖：pip install numpy
将上述代码保存为 tss_demo.py，执行 python tss_demo.py

验证方法与判定标准

代码使用合成图像对（64×64 随机噪声图，整体平移 (3,2) 像素）进行测试。由于图像内容具有唯一匹配性，全搜索能找到真实平移矢量，TSS 在多数块上应得到相同结果。判定通过条件：

程序正常输出 4 行统计信息，无异常报错；
搜索点数减少比例约为 84%（25/225 ≈ 11.1%，即减少 88.9%，实际因边界裁剪略低）；
运动矢量一致率 ≥ 90%（合成图像平移场景下 TSS 通常能准确找到全局最优）。

若一致率偏低，可检查是否因图像块内容重复（如平坦区域）导致多个候选点 SAD 相同，TSS 可能收敛到局部最优——这是该算法的固有特性，在真实视频中可通过增加后续细化搜索缓解。

常见问题

搜索范围不是 2 的幂：代码自动取不大于 search_range 的最大 2 的幂作为初始步长，保证步长序列严格递减至 1。
边界处理：候选点越界时直接跳过，不参与比较，因此实际搜索点数可能略少于 25。
块大小与搜索范围：本实现使用 16×16 宏块和 ±7 搜索范围（视频编码常用配置），修改参数时需保证帧尺寸能被块大小整除。