如果你对双目立体匹配有一定了解，大概率会碰到一个名字——动态规划，也就是 DP。这个词本身不稀奇，很多程序员面试都在背，但它在立体匹配里的用法，不是为了求最长子序列，而是为了在一条扫描线上，找出每个像素最合理的视差序列。我见过不少人一上来就冲进 SGM（半全局匹配）的源码，被一堆方向路径绕晕，其实 SGM 的底子，就是从扫描线 DP 一脉相承下来的。这篇文章我就把立体匹配里的 DP 动态规划算法完整拆开：它解决什么问题、能量函数怎么来的、递推怎么推、代码怎么写、有哪些坑、以及它是怎么演变成 SGM 的。
这个内容适合两类人：一类是刚接触双目视觉、想在代码里真正跑通一个基础匹配算法的学生或工程师；另一类是已经在用现成库调参、但总搞不懂代价体、惩罚参数和横条纹现象根源的人。读完你会明白 DP 为什么被叫做“半全局优化的起点”，也会知道它到底便宜在哪、又弱在哪儿。
1. 立体匹配的三段式流程：DP被夹在哪一步
1.1 从像素对应到深度恢复：立体匹配到底在解什么
先扯远一点。双目相机拍同一场景，左右两张图里同一个物理点会落在不同的像素坐标上，这个偏移量叫视差。离相机近的物体视差大，远的视差小，所以只要把左右图的像素对应关系找出来，就能通过三角关系换算出深度。立体匹配的所有工作，本质上就是“找同名点”。
听起来简单，做起来麻烦。因为一张图里动辄几十万个像素，每个像素可能跟另一张图里很多像素看起来都相似，尤其是纹理稀疏的区域，匹配非常容易认错。而且实际场景里有光照变化、遮挡、反光、重复纹理，这让“同名点”的判断变得模棱两可。传统立体匹配算法踩的坑，基本都是围绕这几个麻烦来的。
一个完整的立体匹配流程，业内通常分成四步：匹配代价计算、代价聚合、视差计算与优化、视差细化。第一步是给每个像素在候选视差范围打分，分数越低说明越像；第二步是在局部窗口里把这些分做平滑；第三步是从累计代价里挑出最优视差；第四步是做亚像素插值、滤波、左右一致性检查之类的后处理。
DP 动态规划算法，准确说是用在“视差计算与优化”这一步，而不是代价计算。它跟前后的步骤是解耦的，也就是说你可以用任何代价计算方式，只要最后把代价体交给 DP 去优化，它就能帮你选出一串“整体最合理”的视差。
1.2 匹配代价、局部聚合与全局优化：DP属于哪一类
如果只看单个像素，代价最小就是最终答案，这种叫“局部方法”。它的优点是快，一个窗口滑过去完事；缺点也很明显，某个像素相似度高不代表周围都一致，结果会噪声很大，而且遇到遮挡区域，局部窗口统计会被污染的像素带偏。
另一条路线是“把整张图的视差求出来，同时要求相邻像素的视差尽量平滑”。这种思路不再单独看像素，而是把全图视差当成一个能量函数的最小化问题。数据项保证每个像素的代价尽量小，平滑项惩罚相邻像素视差突变的区域。两者打架的时候，要有一个平衡。这类方法统称全局优化，Graph Cut 图割、置信传播 BP、动态规划 DP 都在这条线上。
DP 在全局优化里的独特位置是：它把问题限制在“一条扫描线”上，用递归方式在整行像素里寻找一个最优视差序列。行内像素之间的关系全部被考虑进去，但行与行之间互不交流。所以它比局部方法考虑的上下文更广，比全图优化快得多，代价是丢了竖直方向的约束，于是产生我们后面会说的横条纹现象。
1.3 为什么说DP是立体匹配里绕不开的“老古董”
说实话，DP 做立体匹配的巅峰期已经过去二十多年了，现在你想找一个能在通用数据集上打赢深度学习的 DP 实现，基本不可能。但各种半全局算法、多路径聚合、以及很多深度学习视差细化模块，底子都建立在 DP 的递推思想上。SGM 官方论文里，所谓“多路径扫描线优化”本质就是沿多个方向各做一遍 DP，最后把结果加起来。
所以我给你的建议是：别因为 DP“老”就跳过它的原理。恰恰相反，它是理解现代立体匹配的一把钥匙。你只有先把一条线上的 DP 搞明白，SGM 的 16 个方向路径、路径惩罚参数、动态规划回溯，这些概念才能串成一条线。否则面对一堆公式和代码，很难真正消化。
2. 极线约束如何把匹配问题压缩到一条扫描线上
2.1 极线约束：把二维搜索降成一行搜索
立体匹配里有一个很关键的预处理动作——极线校正。左右相机拍摄时，同一个物理点在左右图中的位置是有几何约束的，它一定落在一条“极线”上。如果两幅图经过校正，极线就变成了水平线，也就是说左图某个像素的同名点，只会出现在右图同一行上，不会跑到其他行去。
这一步的意义非常大。本来做匹配要在一个二维区域里搜索，现在只要沿着一行从左往右或从右往左滑动即可，搜索空间一下子从区域变成一维。虽然匹配还是可能在同一条线上的多个位置都看起来很相似，但至少不会出现“我的同名点在左上行，你却在右下行”这种离谱错误。
极线校正通常靠双目标定得到的内外参和畸变系数完成。如果校正做不好，扫描线假设就不成立，DP 和 SGM 的性能会一起跟着雪崩。这是我开始做立体匹配时踩过最疼的坑，一度以为是算法调参问题，最后发现是相机的两个摄像头装配偏了，重做校正之后问题消失。所以遇到匹配结果整体鬼影严重，先别急着调 P1/P2，回去看极线是否严格水平。
2.2 行内独立为什么是合理简化：视差平滑性假设
给定一条扫描线，上面的每个像素都要分配一个视差值。如果没有约束，每个像素选代价最低的视差就行，但结果会锯齿状跳动，因为单个像素的匹配代价不可靠。我们需要一个假设：真实场景中，相邻像素的视差通常是连续变化的。物体表面是平滑的，视差图也应当大体平滑，只在物体边缘、遮挡边界才会出现陡变。
这个假设在大部分场景下是成立的。就算是一个凹凸不平的物体，视差从一个像素到下一个像素的变化也不会特别剧烈，除非刚好跨过物体的轮廓边界。基于这个假设，DP 就在一条扫描线上寻找一个整体代价最小的视差序列：序列中相邻像素视差变化小，就奖励；变化大，就惩罚；但如果有证据表明这里确实是边缘，也能接受一次跳跃。
这个“既能保持平滑、又允许边缘跳变”的平衡，正是 DP 递推里惩罚参数在干的事。它不像简单滤波那样把所有跳变都抹平，而是让算法在“数据证据”和“平滑先验”之间自己权衡。
2.3 每行独立优化的本质：把图像还原成序列标注问题
一旦把整幅图的匹配拆成一行一行分别处理，每一行就是一个独立的一维序列标注问题。给定 N 个像素，每个像素有 D 个视差候选，我们要在这 D^N 种可能性里挑一个最优序列。直接穷举是不可能的，但 DP 利用递推关系，把这个指数级搜索压成了多项式时间。
这正是 DP 在立体匹配里的核心价值。它把“在整行里做全局最优决策”变成“先解决前一个像素的最优，再一步步扩展”。因为平滑项只跟相邻像素有关，所以整个问题满足无后效性：当前像素的最佳选择，只依赖于前一个像素的状态，不需要回头考虑更早之前的选择细节。
这里要体会一个重点：DP 找出来的不是每个像素各自最优，而是整条扫描线上的联合最优。单独看某个像素，它可能选了次优视差，但换来的是左右邻居都更合理、整行更平滑。全局最优就是这样一个互相妥协的结果。
3. DP的数学本质：从能量函数到扫描线递推
3.1 一行内的能量函数：数据项加平滑项的代价
假设一条扫描线有 N 个像素，每个像素 x 分配一个视差 d(x)，候选视差范围是 Dmin 到 Dmax。定义整行的能量为：
E = Σ_x C(x, d(x)) + Σ_x L(d(x), d(x+1))
第一项是数据项，表示像素 x 取视差 d(x) 的代价值，通常直接从代价体里读；第二项是平滑项，表示相邻像素视差变化带来的惩罚。DP 的目标就是找到一组视差序列，让总能量 E 最小。
平滑项 L 常见的设计是分段的。比如经典做法是：两个相邻像素视差相等时惩罚为 0；相差 1 时给一个较小的 P1；相差大于 1 时给一个较大的 P2。为什么分成两档？因为真实场景中，倾斜表面会产生一个像素的微小视差梯度，而物体边缘才会造成视差大幅跳变。如果用同一个惩罚系数，要么边缘直接被抹平，要么微小梯度被频繁触发惩罚，整体视差图会过度细腻或过度破碎。
3.2 递推公式：从序列决策到逐像素最优
现在要设计递推关系。定义 Dp[x][d] 表示“处理到第 x 个像素，并且第 x 个像素的视差定为 d 时，前 x 个像素的最小累计代价”。注意这个定义里，当前像素的视差是固定下来的，但我们不关心它之前到底走了什么路径，只需要知道之前的最优累计代价是多少。
于是递推可以写成：
Dp[x][d] = C(x, d) + min_{k} { Dp[x-1][k] + L(k, d) }
也就是说，当前像素选视差 d 的代价，等于它自己的数据代价 C(x,d)，加上前一个像素选某个视差 k 时的最优累计代价，再加从 k 换到 d 的平滑惩罚。对所有可能的 k 求最小，就是当前状态下所能达到的最小累计代价。
如果不做任何优化，对每个 x 和每个 d 都要遍历所有 k，复杂度是 O(N × D²)。D 一般可能有三五十到几百，N 是图像宽度，乘起来已经不小。后面我会讲前缀/后缀最小值优化，能直接降到 O(N × D)，这就是扫描线 DP 能在嵌入式上跑起来的关键。
3.3 回溯：拿到一整套最优视差序列
递推做完之后，Dp[N-1][d] 里的最小值，就是整行最小能量的结果，但我们要的不是一个数字，而是每个像素具体选哪个视差。这时候需要回溯。
在递推过程中，每算出一个 Dp[x][d]，就顺手记录它当且仅当是从哪一个 k 转移过来的，存进 trace[x][d]。回溯的时候，从最后一列找最小 Dp[N-1][d] 对应的视差作为最后一个像素的视差，然后根据 trace 一步步倒推回 x=0，把每个像素的视差依次填好。这一步看起来不起眼，但实际代码里最容易写错，因为 trace 数组存储的是“来源视差”，稍不留神会跟“前进视差”绕晕，我见过不少实现回溯之后整行视差反着跳的现象，根源都是索引方向没理清。
3.4 前缀最小值：为什么DP能跑得飞快
回到复杂度问题。当 L(k,d) 是分段函数时，min_{k} { Dp[x-1][k] + L(k,d) } 可以拆成三段来求：
- k 等于 d：直接取 Dp[x-1][d]；
- k 等于 d-1 或 d+1：加上 P1 再比较；
- 其他 k（即 |k-d| ≥ 2）：加上统一惩罚 P2。
关键在第三段，它不关心具体是哪个 k，只要求 k 与 d 的距离至少为 2。因此可以预处理一个前缀最小值数组 pref[t] = min_{k≤t} Dp[x-1][k]，再预处理一个后缀最小值数组 suff[t] = min_{k≥t} Dp[x-1][k]，那么第三段的最小值，就是 min(pref[d-2] + P2, suff[d+2] + P2)。这两个数组都能用线性时间算出来，于是每个 x 仍只需要遍历一遍 D 个候选视差，整体复杂度降成 O(N × D)。
这个优化是扫描线 DP 能实用的关键。不加前缀优化的话，同样一条 640 像素宽的扫描线，视差范围 64，复杂度会乘以 64，即便在现代 PC 上也会明显卡顿，更别说嵌入式设备了。
4. 从0到1实现扫描线DP：参考实现与运行细节
4.1 代价体怎么构建：像素差、BT代价与Census变换
DP 递推需要输入“代价体”。最简单的代价计算是绝对灰度差 SAD，也就是 C(x,d) = |左图(x) - 右图(x-d)|。这种方式快，但受光照影响明显，左右相机如果存在亮度差异，代价里会埋进系统性偏差。
我实际用下来，有两种更稳健的代价值得优先考虑。一种是 Birchfield-Tomasi 代价，它在左右像素各自相邻像素上做插值，能够容忍很小的光照偏差，经典程度高。另一种是 Census 变换，它比较的是局部窗口内像素与中心像素的大小关系，得到一个二进制编码，然后用汉明距离作为代价。Census 对光照和噪声非常鲁棒，近些年很多算法都爱拿它做特征，你完全可以直接用 Census 代价喂给 DP 做实验。
不管用哪种，最后都需要整理成一个三维数组 cost[x][y][d]，表示第 y 行第 x 个像素取视差 d 的代价。DP 对每一行会单独拎出来处理 y，所以实际代码里往往按行循环，每行用一个二维 cost[x][d] 数组。
4.2 递推和回溯的参考代码
下面的代码只演示一条扫描线的处理，假设代价数组是 C，形状为 (W, D)。这里我尽量用可读性优先的写法，真实工程里可以再压到原地更新。
def scanline_dp(C, P1, P2): W, D = C.shape dp_prev = C[0].copy() # x=0 时只有数据代价 trace = [[-1] * D for _ in range(W)] # trace[x][d] 记录上一步来源视差 for x in range(1, W): # 预处理前缀最小值和后缀最小值，用于 |k-d| >= 2 的跳变惩罚 pref_val = [0] * D pref_idx = [0] * D pref_val[0] = dp_prev[0] pref_idx[0] = 0 for d in range(1, D): if dp_prev[d] < pref_val[d-1]: pref_val[d] = dp_prev[d] pref_idx[d] = d else: pref_val[d] = pref_val[d-1] pref_idx[d] = pref_idx[d-1] suff_val = [0] * D suff_idx = [0] * D suff_val[D-1] = dp_prev[D-1] suff_idx[D-1] = D-1 for d in range(D-2, -1, -1): if dp_prev[d] < suff_val[d+1]: suff_val[d] = dp_prev[d] suff_idx[d] = d else: suff_val[d] = suff_val[d+1] suff_idx[d] = suff_idx[d+1] dp_cur = [0] * D for d in range(D): best = dp_prev[d] best_k = d if d > 0: cand = dp_prev[d-1] + P1 if cand < best: best = cand best_k = d-1 if d < D-1: cand = dp_prev[d+1] + P1 if cand < best: best = cand best_k = d+1 if d >= 2: cand = pref_val[d-2] + P2 if cand < best: best = cand best_k = pref_idx[d-2] if d <= D-3: cand = suff_val[d+2] + P2 if cand < best: best = cand best_k = suff_idx[d+2] dp_cur[d] = C[x][d] + best trace[x][d] = best_k dp_prev = dp_cur # 回溯：从最后一列最优视差开始往前推 disp = [0] * W d = int(np.argmin(dp_prev)) # 这里假设最后一行最优视差为起点 for x in range(W-1, -1, -1): disp[x] = d if x > 0: d = trace[x][d] return disp写这段代码有四个容易出错的地方，提一下。第一，x=0 那一行 trace 没有意义，回溯时不要访问 trace[0][d]。第二，前缀和后缀数组的索引要跟 d 的边界严格对齐，否则 |k-d| ≥ 2 的条件会被破坏。第三，P1 与 P2 若是整数，代价体最好也统一成同数量级，否则惩罚项会被数据项淹没。第四，C 的行数 W 要跟图像宽度一致，而 d 的编码顺序必须跟视差范围一一对应，常见做法是从最小视差开始递增。
4.3 左右路径的选择与整图处理
上面代码处理的是从左到右的方向。实际匹配中，物体遮挡会导致从左到右和从右到左的信息不一样。一个经典做法是：把扫描线从右往左再做一遍 DP，两遍结果取最小能量或者加权融合，能一定程度减少遮挡区域只用一侧信息带来的偏差。
整图处理非常简单，按行循环调用 scanline_dp 即可。对每一行，从代价三维数组里取出 C[y]，得到这一行的视差序列，存进整幅视差图。由于每一行彼此独立，这个循环完全可以并行化，多个线程各处理几行数据，速度很不错。
4.4 左右一致性检查：给视差图擦屁股
DP 的整行优化能明显压掉噪声，但遮挡区域和重复纹理区域还是会出错误视差。最常用的后处理是左右一致性检查：分别从左图匹配右图、从右图匹配左图，得到左右两张视差图，然后对左图像素 (x,y)，拿它的视差 d 算出在右图的对应点 (x-d,y)，再看右图上这个点的视差是不是也指向左图当前位置，允许 1 个像素的容差。若不一致，这个点通常被标记为无效视差，后续用邻域填充或中值滤波补救。
这种检查对 DP 尤其重要，因为它能区分“整体平滑但确实错了”的像素。我处理公开测试图像时，做完左右一致性检查后，错误像素能减少一半以上，代价是计算量翻倍，但考虑到这是离线处理或者后处理阶段，完全可以接受。
5. 横条纹、低纹理与遮挡：DP三个绕不过去的坎
5.1 横条纹扫描线不一致：视觉上最扎眼的瑕疵
DP 每行独立优化，相邻行之间没有共享任何信息。即使数据项完全一致，两行各自求出的最优序列也可能出现细微差异，反映到视差图上就像一道道水平条纹，业内叫“streaking”。这是扫描线 DP 最著名的缺陷。
条纹有多严重，取决于场景和惩罚参数。纹理丰富的区域，代价能提供足够的约束，条纹不明显；大块低纹理区域，比如白墙、天空、地面，代价在很大范围的视差上都差不多，DP 就可能对相邻行给出非常不同的“全局最优”，条纹就出来了。
应对办法有两种路线。一种是在 DP 结果上做后处理，例如对横条纹方向做中值滤波、双边滤波，视觉上糊一些，但能接受。另一种是直接升级到 SGM 这类多路径方法，把多个方向的 DP 结果累加，行间的孤立性被打破，条纹自然消失。这也是 SGM 成为主流的重要原因之一。
5.2 低纹理区域：惩罚参数的天堂与地狱
低纹理区域是所有全局优化方法的试金石。DP 在低纹理区能表现如何，很大程度上由 P1 和 P2 决定。P1 惩罚相邻像素 1 个单位的视差变化，P2 惩罚较大的跳变。当低纹理区域里数据项几乎无法区分谁优谁劣时，平滑项就主导了一切，两个惩罚系数直接决定这块区域是变成平滑平面还是噪声场。
如果 P1、P2 设得太小，低纹理区域会被数据项的噪声带着走，视差图像一张花纹墙纸。设得过大，区域会被过度平滑成一块大平板，而真正的边缘——比如桌子腿边界——也因为跳变代价太高被强行抹平。这里我给出实际调试时好用的方向：P1 一般设 4 到 12（针对 0-255 灰度级的代价），P2 通常取 P1 的 4 到 8 倍，如果图像噪声大或低纹理面积大，需要再往上加。但每个数据集的最佳值都不同，调参时最好分场景验证，不要迷信网上抄来的参数。
5.3 遮挡区与唯一性假设的矛盾
遮挡区域有一个更本质的麻烦：左图的某些像素，在右图里根本没有对应点，因为被前景物体挡住了。任何匹配算法都找不到这些像素的“真同名点”。DP 的平滑项会硬生生给它们编一个看起来合理的视差，让结果不至于空一大块，但这个视差基本是错的。
所以实际系统里，遮挡通常不指望匹配算法自己去发现，而是靠左右一致性检查来标记。标记为无效的区域，在做三维重建时可以选择丢弃，或者用周围有效视差插值补上去。这个“识别并标记无效”的步骤，往往比把无效区域强行填满更重要。
6. 从DP到SGM：把一维寻优升级成多路径聚合
6.1 SGM为什么能打败行级DP的条纹问题
SGM 的改进思路非常朴素：既然单独一条扫描线会丢竖直方向约束，那我从多个方向各做一遍扫描线 DP，再把所有方向的结果加起来，行间的信息不就进来了吗。
具体来说，SGM 对每个方向 r，沿该方向做一维 DP，得到代价聚合体积 L_r(p,d)。所有方向的结果加起来，得到一个更强的聚合代价 S(p,d) = Σ_r L_r(p,d)，最后取每个像素 S 值最小的视差。因为每个方向的 DP 都能把该方向的平滑信息传递给当前像素，多方向求和之后，等价于把二维图像上的邻域信息都吸收进来了，横条纹自然被摊掉。
从算法实现角度看，SGM 的路径方向就是八个方位再拆成两条射线，一共 8 到 16 个方向，每个方向的递推公式跟扫描线 DP 几乎一模一样，只是坐标沿着射线移动。所以说 DP 是 SGM 的心脏，一点不过分。
6.2 哪些场景值得保留原始DP而不是上SGM
SGM 也不是没有代价。它对每一条路径都要存一个三维聚合代价，内存占用通常是原始扫描线 DP 的几倍到十几倍，速度也慢不少。如果你的设备算力和内存都吃紧，或者你只需要一个粗糙的视差图，原始扫描线 DP 仍然有它的位置。
我知道一些低功耗嵌入式视觉方案，就喜欢用扫描线 DP 外加下采样，先把低分辨率视差图跑出来，再结合图上采样和边缘修复。精度谈不上惊艳，但能在功耗和帧率上换来很大优势。反之，如果你有 GPU 或者稍微强一点的 CPU，直接上 SGM 通常是更稳妥的选择，毕竟条纹问题的修复成本很高。
6.3 我的调试顺序建议：先用DP摸清代价体再做SGM
我自己调试双目匹配时，有一种顺序挺推荐：先写一个最简单的扫描线 DP，把代价体、P1/P2、视差范围调顺，再升级到 SGM。为什么这样？因为扫描线 DP 结构简单，出问题容易定位。如果连 DP 都跑出很多噪声，先别怀疑算法，去检查代价体本身是否失真、极线校正是否准确。代价体和惩罚项理顺之后，再切到 SGM，整个调试过程会顺畅很多。
另外有一点让我印象很深：哪怕同一个代价体，DP 和 SGM 对 P1/P2 的最优值也并不是一致的。SGM 因为有多个方向平均，惩罚可以相对小一些，而单方向 DP 有时候需要更大的 P2 来压住噪声。所以参数必须跟着算法走，不能复用经验不加以验证。
6.4 几句实在的收尾经验
跑了很多轮之后，我对 DP 的体会可以浓缩成几条。第一，代码里最值得花时间打磨的是回溯和边界条件，这两处一旦出错，Bug 很难一眼看出来，因为视差图整体形状可能还对，只是局部出现莫名其妙的反转。第二，代价体的质量决定了 DP 的上限，惩罚参数只是在下限以下努力修复，因此不要指望 DP 能拯救一个坏的代价体。第三，用 DP 调试时可以刻意把 P2 拉大，看看视差图是否被过度平滑，这能帮你快速判断数据项和平滑项的权重是否失衡。
如果你手里正好有一套双目图像对，我的建议是从扫描线 DP 开始做第一个基线版本。哪怕最终产品需要的是高精度视差图，这个最朴素的基线也能让你绕开一堆调参玄学。等你能解释清楚哪条条纹是哪个参数导致的，再向 SGM 甚至深度学习方法切换，你会发现自己对立体匹配的理解已经不一样了。
