4. 菱形搜索法运动估计

任务目标

在运动估计中，全搜索法虽精度高但计算量巨大。本案例实现菱形搜索法（Diamond Search, DS），使用大菱形（LDSP）与小菱形（SDSP）两种模板，在保证估计质量接近全搜索的前提下，显著减少搜索点数，并分析其收敛速度与精度特性。

核心实现

import numpy as np

def sad(block1, block2):
    """计算两个块之间的SAD（差值和）"""
    return np.sum(np.abs(block1.astype(np.int16) - block2.astype(np.int16)))

def diamond_search(ref_frame, cur_block, block_pos, search_range=7):
    """
    菱形搜索运动估计
    ref_frame: 参考帧（灰度图，numpy 2D数组）
    cur_block: 当前块（2D数组）
    block_pos: 当前块在帧中的位置 (row, col)
    search_range: 搜索范围（菱形扩展的最大半径）
    返回: (mv_row, mv_col, search_points)
    """
    height, width = ref_frame.shape
    block_h, block_w = cur_block.shape
    br, bc = block_pos

    # 大菱形模板（LDSP）：中心+上下左右各2步
    ldsp_offsets = [(0, 0), (0, -2), (0, 2), (-2, 0), (2, 0),
                    (-1, -1), (-1, 1), (1, -1), (1, 1)]
    # 小菱形模板（SDSP）：中心+上下左右各1步
    sdsp_offsets = [(0, 0), (0, -1), (0, 1), (-1, 0), (1, 0)]

    best_mv = (0, 0)
    best_sad = float('inf')
    search_points = 0

    # 初始位置：搜索中心为当前块位置
    center_r, center_c = br, bc

    # 第一阶段：LDSP迭代搜索
    while True:
        min_sad = float('inf')
        min_offset = (0, 0)

        for dr, dc in ldsp_offsets:
            ref_r = center_r + dr
            ref_c = center_c + dc
            # 边界检查
            if (ref_r < 0 or ref_r + block_h > height or
                ref_c < 0 or ref_c + block_w > width):
                continue
            ref_block = ref_frame[ref_r:ref_r+block_h, ref_c:ref_c+block_w]
            cost = sad(cur_block, ref_block)
            search_points += 1
            if cost < min_sad:
                min_sad = cost
                min_offset = (dr, dc)

        # 更新最佳匹配
        if min_sad < best_sad:
            best_sad = min_sad
            best_mv = (center_r - br + min_offset[0], center_c - bc + min_offset[1])

        # 检查是否到达搜索范围边界
        if (abs(center_r - br) >= search_range or
            abs(center_c - bc) >= search_range):
            break

        # 若最小点在中心，则转入SDSP；否则移动中心到最小点
        if min_offset == (0, 0):
            break
        else:
            center_r += min_offset[0]
            center_c += min_offset[1]

    # 第二阶段：SDSP精细搜索
    for dr, dc in sdsp_offsets:
        ref_r = center_r + dr
        ref_c = center_c + dc
        if (ref_r < 0 or ref_r + block_h > height or
            ref_c < 0 or ref_c + block_w > width):
            continue
        ref_block = ref_frame[ref_r:ref_r+block_h, ref_c:ref_c+block_w]
        cost = sad(cur_block, ref_block)
        search_points += 1
        if cost < best_sad:
            best_sad = cost
            best_mv = (center_r - br + dr, center_c - bc + dc)

    return best_mv, search_points

def full_search(ref_frame, cur_block, block_pos, search_range=7):
    """全搜索法（用于对比）"""
    height, width = ref_frame.shape
    block_h, block_w = cur_block.shape
    br, bc = block_pos
    best_mv = (0, 0)
    best_sad = float('inf')
    search_points = 0

    for dr in range(-search_range, search_range + 1):
        for dc in range(-search_range, search_range + 1):
            ref_r = br + dr
            ref_c = bc + dc
            if (ref_r < 0 or ref_r + block_h > height or
                ref_c < 0 or ref_c + block_w > width):
                continue
            ref_block = ref_frame[ref_r:ref_r+block_h, ref_c:ref_c+block_w]
            cost = sad(cur_block, ref_block)
            search_points += 1
            if cost < best_sad:
                best_sad = cost
                best_mv = (dr, dc)

    return best_mv, search_points

运行与验证

# 生成测试数据：模拟一个简单运动场景
frame_size = 64
ref_frame = np.random.randint(0, 256, (frame_size, frame_size), dtype=np.uint8)
# 构造当前帧：将参考帧中某块向右下平移(3,2)
block_size = 8
true_mv = (3, 2)
block_pos = (20, 20)  # 当前块在帧中的位置

# 提取当前块（模拟运动后的块，加入少量噪声）
cur_block = ref_frame[block_pos[0]+true_mv[0]:block_pos[0]+true_mv[0]+block_size,
                      block_pos[1]+true_mv[1]:block_pos[1]+true_mv[1]+block_size].copy()
cur_block = np.clip(cur_block.astype(np.int16) + np.random.normal(0, 3, cur_block.shape), 0, 255).astype(np.uint8)

# 执行菱形搜索
ds_mv, ds_points = diamond_search(ref_frame, cur_block, block_pos, search_range=7)
# 执行全搜索对比
fs_mv, fs_points = full_search(ref_frame, cur_block, block_pos, search_range=7)

print(f"真实运动矢量: {true_mv}")
print(f"菱形搜索: 运动矢量={ds_mv}, 搜索点数={ds_points}")
print(f"全搜索:   运动矢量={fs_mv}, 搜索点数={fs_points}")

# 验证：计算两种方法的SAD误差
def get_block(frame, pos, size):
    r, c = pos
    return frame[r:r+size, c:c+size]

ds_sad = sad(cur_block, get_block(ref_frame, (block_pos[0]+ds_mv[0], block_pos[1]+ds_mv[1]), block_size))
fs_sad = sad(cur_block, get_block(ref_frame, (block_pos[0]+fs_mv[0], block_pos[1]+fs_mv[1]), block_size))
print(f"菱形搜索SAD: {ds_sad}, 全搜索SAD: {fs_sad}")

# 收敛性分析：统计搜索点数的减少比例
reduction = (1 - ds_points / fs_points) * 100
print(f"搜索点数减少: {reduction:.1f}%")

预期输出与判定标准

运行上述代码，预期输出类似：

真实运动矢量: (3, 2)
菱形搜索: 运动矢量=(3, 2), 搜索点数=21
全搜索:   运动矢量=(3, 2), 搜索点数=225
菱形搜索SAD: 略大于全搜索SAD（因噪声影响）
搜索点数减少: 90.7%

通过条件：

菱形搜索的运动矢量与真实运动矢量一致（或误差≤1像素）；
搜索点数显著少于全搜索（通常减少80%以上）；
两种方法的SAD差值在噪声允许范围内（本例噪声σ=3，SAD差值应小于块内像素数×噪声方差的一半，即8×8×3²/2≈288）。

收敛性分析要点

收敛速度：菱形搜索的搜索点数约为全搜索的1/10，且与搜索范围大小呈对数关系而非线性关系；
收敛精度：对于单峰误差曲面，DS能收敛到全局最优；对于多峰曲面（如纹理复杂区域），DS可能陷入局部最优，但SAD代价通常接近全局最优；
模板选择：LDSP负责粗定位（大步长快速接近最优），SDSP负责精调（小步长精确收敛），两步结合保证搜索效率与精度平衡。

说明：上图展示了菱形搜索的收敛路径。搜索从中心点开始，通过多次LDSP迭代快速向最优区域移动（每次移动2像素），当LDSP中心点成为最小SAD点时，切换SDSP进行1像素精度的精细搜索。整个过程仅需约20个搜索点，而全搜索需要225个点（15×15），计算量降低约90%。

📚 课程目录