SGBM算法流程（二）

SGBM 单路径动态规划公式详解

目录

1. 为什么需要代价聚合

1.1 局部匹配的问题

原始代价计算的缺陷:

假设我们只用局部块匹配 (Block Matching) 来计算代价： $$C(x,y,d)=\sum _{(i,j)\in W}|I_L(x+i,y+j)-I_R(x+i-d,y+j)|$$

直接用 WTA (Winner-Takes-All) 选择最小代价： $$D(x,y)=\arg \underset{d}{\min }C(x,y,d)$$

问题示例:

场景: 一面白墙 (弱纹理区域)

左图像: [255, 255, 255, 255, 255, …]
右图像: [255, 255, 255, 255, 255, …]

代价计算:
C(x, y, d=0) = 0
C(x, y, d=1) = 0
C(x, y, d=2) = 0
…
C(x, y, d=50) = 0 ← 所有视差代价相同！

结果: 无法确定正确视差，产生随机噪声

核心矛盾:

• 局部代价只考虑当前像素
• 忽略了空间连续性约束 (相邻像素的深度通常平滑变化)

1.2 全局能量函数

为解决上述问题，引入全局优化目标：

$$E(D)=$$

p∑​C(p,Dp​)​∗数据项: 匹配质量+平滑项: 空间一致性

∑∗p,qV(Dp​,Dq​)​​

物理意义:

• 数据项: 要求视差与图像匹配
• 平滑项: 要求相邻像素视差平滑

优化目标: $$D^{\ast }=\arg \underset{D}{\min }E(D)$$

难点: 这是一个 NP-hard 问题，精确求解需要指数时间复杂度 $O(D^N)$，其中 $N$ 是像素总数。

1.3 Semi-Global 近似

Hirschmüller 的核心贡献：用多条 1D 路径的动态规划近似 2D 全局优化

2D 全局优化 (NP-hard):
┌─────────────┐
│ ● ● ● ● ● ● │
│ ● ● ● ● ● ● │ 需要同时考虑所有像素的相互关系
│ ● ● ● ● ● ● │
└─────────────┘
复杂度: O(D^(W×H))

1D 路径动态规划 (多项式):
────────────→ 路径1 (0°)
↘↘↘↘↘↘↘↘↘↘ 路径2 (45°)
↓↓↓↓↓↓↓↓↓↓ 路径3 (90°)
…
复杂度: O(W×H×D×P) ← 可实时计算

2. 动态规划的核心思想

2.1 什么是路径

路径定义: 从图像边界到当前像素的像素序列

水平路径 (0°) 示例:

图像:
0 1 2 3 4 5 (x坐标)
┌───────────────────────┐
│ A → B → C → D → E → F │ y=10
└───────────────────────┘

路径 r (方向=0°):
起点: A(0, 10)
终点: F(5, 10)
序列: A → B → C → D → E → F

对于像素 D(3, 10)，其前一个像素 $p-r$ 是 C(2, 10)。

2.2 动态规划的本质

核心思想: 当前像素的最优解依赖于前一个像素的最优解

贝尔曼方程 (Bellman Equation): $$L_r(p,d)=C(p,d)+\underset{d^{\prime }}{\min }\left[L_r(p-r,d^{\prime })+V(d,d^{\prime })\right]$$

直观理解:

到达当前像素 p 的最小代价 = 当前匹配代价 + (前一像素最小代价 + 视差变化惩罚)

优势:

• 时间复杂度从 $O(D^N)$ 降低到 $O(N\times D^2)$
• 通过记忆化避免重复计算

3. 公式完整解析

3.1 标准形式