4、立体匹配算法原理：从代价计算到视差优化
立体匹配，说白了就是给左右两张图“找亲戚”。左图里的一个像素点，在右图里到底对应谁？找到之后，一算偏移量，深度就出来了。
我刚开始做双目系统时，觉得立体匹配不就是个“找相似”嘛，有啥难的？结果一上手才发现，坑多得很。光照变化、纹理缺失、重复纹理、遮挡区域……每个问题都能让你调到头秃。
今天咱们就把立体匹配的四个核心步骤掰开揉碎，再聊聊局部匹配和全局匹配的区别，最后重点讲SGM——这个在工程里用得最多的算法。
4.1 立体匹配的四个步骤
不管什么匹配算法，基本都逃不过这四步：匹配代价计算 → 代价聚合 → 视差计算 → 视差优化。我习惯把这四步比作“相亲流程”——先看照片打分，再综合各方评价，最后做决定，完了还得修修图。
4.1.1 匹配代价计算
这一步最简单直接：给定左图一个像素点 (x, y)，在右图同一行上，从 d_min 到 d_max 每个候选视差位置，算一个“相似度分数”。
常用的方法有：
- 绝对差之和（SAD）：窗口内像素差的绝对值求和。快，但容易受光照影响。
- 平方差之和（SSD）：类似SAD，但用平方。对噪声更敏感。
- 归一化互相关（NCC）：抗光照变化能力强，但计算量大。
- Census变换：我项目里最常用的。把像素和邻域比较，生成二进制串，再用汉明距离算代价。对光照变化鲁棒性极好。
核心要点：匹配代价计算的结果是一个三维数组——代价体积（Cost Volume），尺寸为 H × W × (d_max - d_min)。这是后续所有步骤的基础。
4.1.2 代价聚合
这一步是很多新手容易忽略的。你想想看，单像素的代价计算受噪声影响很大，一个点算出来的代价可能完全不准。怎么办？把周围邻居的信息也拿过来参考。
代价聚合的本质就是滤波。常见方法：
- 盒式滤波（Box Filter）：简单平均，速度快但会模糊边缘。
- 高斯滤波：加权平均，中心权重高，边缘保留稍好。
- 引导滤波（Guided Filter）：我强烈推荐。以原图作为引导，边缘保留效果极好，而且计算效率高。
- 十字交叉聚合（Cross-based）：自适应形状的聚合窗口，适合硬件实现。
我的经验：在嵌入式平台上，如果算力有限，优先考虑盒式滤波+引导滤波的组合。先用盒式滤波快速粗聚合，再用引导滤波精修边缘。我曾经在一个FPGA项目上这么干过，效果不错。
4.1.3 视差计算
代价聚合之后，每个像素在每个视差下都有一个“聚合后的代价”。视差计算就是从中挑一个最好的。
- 赢家通吃（WTA）：最简单，选代价最小的视差。速度快，但容易出噪声。
- 子像素插值：WTA只能得到整数视差，精度不够。用二次曲线拟合代价曲线，找到亚像素级别的极值点。我一般用抛物线拟合，简单够用。
注意：子像素插值不是万能的。如果代价曲线太平坦，插值结果会很不稳定。我遇到过这种情况，后来加了置信度判断，平坦区域直接标记为无效。
4.1.4 视差优化
算出来的视差图通常有很多“毛刺”——孤立的错误点、遮挡区域的空洞、边缘处的锯齿。这一步就是做“美容”。
常用手段：
- 左右一致性检查（LRC）：从左图算到右图，再从右图算回左图，看视差是否一致。不一致的就是遮挡点或错误点。这是最常用的后处理手段。
- 中值滤波：简单粗暴，去除孤立噪点。
- 加权中值滤波：保留边缘的同时去噪，效果更好。
- 孔洞填充：对遮挡区域，用周围有效视差插值填充。我习惯用最近邻有效点填充，简单且不会引入太多模糊。
4.2 局部匹配 vs 全局匹配
搞清楚了四个步骤，咱们来聊聊两种大的流派。
| 对比项 | 局部匹配 | 全局匹配 |
|---|---|---|
| 核心思想 | 只考虑局部窗口内的信息 | 构建全局能量函数，考虑所有像素 |
| 代价聚合 | 必须做，且是核心 | 通常不做，或做简化 |
| 视差计算 | WTA | 能量函数最小化（图割、动态规划等） |
| 精度 | 中等，边缘容易模糊 | 高，尤其边缘和弱纹理区域 |
| 速度 | 快，适合实时 | 慢，难以实时 |
| 典型算法 | BM（块匹配）、SAD、NCC | GC（图割）、DP（动态规划）、SGM |
说白了，局部匹配是“近视眼”，只看周围一小块；全局匹配是“远视眼”，看全局。但全局匹配计算量太大，在嵌入式平台上基本跑不动。
那有没有折中方案？有，就是SGM。
4.3 SGM（半全局匹配）算法详解
SGM，全称 Semi-Global Matching，是德国人 Hirschmüller 在 2005 年提出的。它既不是纯局部，也不是纯全局，而是“半全局”——在多个一维路径上做动态规划，近似模拟二维全局优化。
我最早接触SGM是在2015年，当时做一个车载双目项目。BM算法在高速场景下视差图全是洞，换了SGM之后，效果立竿见影。从那以后，SGM就成了我的“标配”。
4.3.1 SGM的核心思想
SGM的出发点是：全局匹配的能量函数太难优化了，咱们把它拆成多个一维路径，每个路径上做动态规划，最后把各路径的结果加起来。
能量函数长这样：
E(D) = Σ C(p, Dp) + Σ P1 * T[|Dp - Dq| = 1] + Σ P2 * T[|Dp - Dq| > 1]其中：
- C(p, Dp)：像素 p 在视差 Dp 下的匹配代价
- P1：对相邻像素视差变化为1的惩罚（小变化）
- P2：对相邻像素视差变化大于1的惩罚（大变化，通常是边缘）
- T[·]：条件判断，成立为1，否则为0
这个能量函数的意思很直观：匹配代价要小，同时相邻像素的视差要平滑。P1和P2就是控制平滑力度的两个旋钮。
4.3.2 多路径聚合
SGM不直接优化上面的能量函数，而是从多个方向（通常是8个或16个方向）分别做一维动态规划，然后累加。
每个方向上的递推公式：
Lr(p, d) = C(p, d) + min(
Lr(p-r, d),
Lr(p-r, d-1) + P1,
Lr(p-r, d+1) + P1,
min_k Lr(p-r, k) + P2
) - min_k Lr(p-r, k)最后，所有路径的代价累加：
S(p, d) = Σ Lr(p, d)然后WTA选最优视差。
关键点：为什么要减去 min_k Lr(p-r, k)？这是为了防止数值溢出，同时保证代价不会无限增长。我刚开始看论文时没注意这个细节，自己实现时发现代价越来越大，查了半天才发现少了这一步。
4.3.3 P1和P2的参数调优
这两个参数直接影响视差图质量。我分享一些经验：
- P1：通常设为 8~16（基于Census代价）。太小则视差图噪声大，太大则过度平滑。
- P2：通常设为 32~128。P2应该比P1大，因为视差跳变（边缘）应该比小变化更受惩罚。
- 自适应P2：我常用的技巧。根据像素梯度动态调整P2——梯度大的地方（边缘），P2设小一点，允许视差跳变；梯度小的地方（平坦区域），P2设大一点，强制平滑。
// 自适应P2的伪代码
P2 = P2_base;
if (abs(I(p) - I(p-r)) > gradient_threshold) {
P2 = P2 / 2; // 边缘区域，降低惩罚
}避坑指南：我曾经在一个纹理极少的场景（白墙）上调SGM，P2设得太大，结果整个视差图变成了一块平板。后来把P2调小，同时增加了P1，才得到合理的渐变效果。记住：平坦区域靠P1平滑，边缘靠P2允许跳变。
4.3.4 SGM的工程实现要点
在嵌入式平台上实现SGM，有几个地方要特别注意：
- 内存管理：代价体积 H×W×D 可能很大。以720p图像、128视差为例，如果用uint16存储，需要 1280×720×128×2 ≈ 235MB。嵌入式设备扛不住。我一般用分块计算或行缓存来降低内存。
- 路径顺序：8路径聚合时，注意数据依赖。我习惯先做水平方向（左→右、右→左），再做垂直方向（上→下、下→上），最后做对角线。这样缓存利用率高。
- 定点化：浮点运算在嵌入式上太慢。我把所有代价和惩罚都转成整数，用移位代替乘除。精度损失在可接受范围内。
- 并行化：SGM的每个像素计算是独立的（除了路径依赖），非常适合用SIMD指令或GPU加速。我在ARM NEON上做过优化，速度能提升4~5倍。
4.3.5 SGM的优缺点总结
- 优点：精度高（接近全局匹配）、速度快（可实时）、对弱纹理区域有较好的鲁棒性。
- 缺点：内存消耗大、参数调优需要经验、对倾斜表面（非前向平行）效果一般。
嗯，说到倾斜表面，我补充一句。SGM假设视差在局部是分段常数的，对于倾斜表面（比如路面），它会产生“阶梯效应”。解决办法是用视差平面拟合做后处理，或者改用更高级的算法（如SGBM的改进版）。
4.4 本章小结
立体匹配的四步流程——代价计算、代价聚合、视差计算、视差优化——是理解所有匹配算法的基础。局部匹配快但精度有限，全局匹配精度高但慢，SGM在两者之间找到了一个很好的平衡点。
我个人建议，如果你刚开始做双目系统，先从SGM入手。它足够成熟，资料多，效果稳定。等吃透了SGM，再根据具体场景去调整或替换其中的模块——比如把代价计算换成更鲁棒的Census，或者把聚合方式改成引导滤波。
调参这件事，没有捷径。多试、多看视差图、多对比ground truth，慢慢你就会有感觉。
公众号:蓝海资料掘金营，微信deep3321