2. 基于块匹配的全搜索运动估计

任务目标

实现全搜索块匹配（Full Search Block Matching）运动估计算法，输入两帧灰度图像，输出全局平移运动矢量（dx, dy），并对比不同块大小（8×8、16×16、32×32）对估计精度的影响。

核心原理

全搜索块匹配将当前帧划分为固定大小的块，在参考帧的搜索窗口内遍历所有候选位置，以最小SAD（差之和）作为匹配准则，得到每个块的运动矢量。由于本案例针对全局平移运动，取所有块运动矢量的众数作为全局运动估计结果。

实现代码

import numpy as np
from collections import Counter

def generate_translated_image(img, dx, dy):
    """生成平移后的图像（用于构造测试输入）"""
    h, w = img.shape
    out = np.zeros_like(img)
    # 计算有效源区域
    src_y0 = max(0, -dy)
    src_y1 = min(h, h - dy)
    src_x0 = max(0, -dx)
    src_x1 = min(w, w - dx)
    dst_y0 = max(0, dy)
    dst_y1 = min(h, h + dy)
    dst_x0 = max(0, dx)
    dst_x1 = min(w, w + dx)
    out[dst_y0:dst_y1, dst_x0:dst_x1] = img[src_y0:src_y1, src_x0:src_x1]
    return out

def full_search_block_matching(cur, ref, block_size, search_range=16):
    """
    全搜索块匹配
    参数:
        cur: 当前帧 (H, W) 灰度图
        ref: 参考帧 (H, W) 灰度图
        block_size: 块大小（正方形边长）
        search_range: 搜索半径（像素）
    返回:
        (global_dx, global_dy): 全局平移矢量
    """
    h, w = cur.shape
    mv_list = []
    
    # 遍历所有块（步长=block_size，不重叠）
    for y in range(0, h - block_size + 1, block_size):
        for x in range(0, w - block_size + 1, block_size):
            block = cur[y:y+block_size, x:x+block_size]
            best_sad = float('inf')
            best_mv = (0, 0)
            
            # 在搜索窗口内全搜索
            for dy in range(-search_range, search_range + 1):
                for dx in range(-search_range, search_range + 1):
                    ref_y = y + dy
                    ref_x = x + dx
                    # 边界检查
                    if (ref_y < 0 or ref_y + block_size > h or
                        ref_x < 0 or ref_x + block_size > w):
                        continue
                    ref_block = ref[ref_y:ref_y+block_size, ref_x:ref_x+block_size]
                    sad = np.sum(np.abs(block.astype(np.int16) - ref_block.astype(np.int16)))
                    if sad < best_sad:
                        best_sad = sad
                        best_mv = (dx, dy)
            mv_list.append(best_mv)
    
    # 取众数作为全局运动估计
    if not mv_list:
        return (0, 0)
    counter = Counter(mv_list)
    global_mv = counter.most_common(1)[0][0]
    return global_mv

def evaluate_block_sizes(img, true_dx, true_dy, block_sizes=(8, 16, 32)):
    """评估不同块大小的估计精度"""
    ref = generate_translated_image(img, true_dx, true_dy)
    results = {}
    for bs in block_sizes:
        est_dx, est_dy = full_search_block_matching(img, ref, bs)
        error = abs(est_dx - true_dx) + abs(est_dy - true_dy)
        results[bs] = {'estimated': (est_dx, est_dy), 'error': error}
    return results

# ========== 最小验证入口 ==========
if __name__ == "__main__":
    # 构造测试图像：随机噪声图（含足够纹理）
    np.random.seed(42)
    H, W = 128, 128
    img = np.random.randint(0, 256, (H, W), dtype=np.uint8)
    
    # 真实平移量
    true_dx, true_dy = 5, -3
    
    # 评估不同块大小
    results = evaluate_block_sizes(img, true_dx, true_dy)
    
    for bs, r in results.items():
        print(f"块大小 {bs}×{bs}: 估计运动=({r['estimated'][0]}, {r['estimated'][1]}), "
              f"误差(曼哈顿距离)={r['error']}")

运行方式

python full_search_motion_estimation.py

验证方法与判定标准

程序使用128×128随机噪声图作为测试输入，真实平移量为(5, -3)。运行后观察输出：

• 通过条件：三种块大小估计的误差均为0，即全部正确估计出(5, -3)。
• 精度对比：若图像纹理不足或存在重复模式，小块的估计可能因噪声敏感产生误差，而大块更鲁棒但运动分辨率较低。本测试使用随机噪声图，理论上三种块大小均能正确估计。

若需测试真实图像序列，可将img替换为实际灰度帧，并设置已知的平移量进行验证。

关键说明

• 搜索范围固定为±16像素，覆盖本测试的平移量(5,-3)。若真实运动超出此范围，需增大search_range。
• 块匹配采用不重叠分块，步长等于块大小；全局运动取所有块运动矢量的众数，对局部运动区域具有鲁棒性。
• SAD计算使用int16防止uint8溢出。