SGM算法原理详解(上)

在立体匹配技术领域，半全局匹配（Semi-Global Matching，SGM）算法因其兼顾精度与效率的显著优势，成为工业级双目测距系统中的核心技术。由 Hirschmüller 于 2005 年提出的 SGM 算法，通过融合局部匹配的快速性与全局匹配的鲁棒性，解决了传统方法在遮挡区域、弱纹理区域的匹配难题。立体匹配的本质是在左右视图中为每个像素寻找对应匹配点，其性能直接决定视差图质量。传统局部匹配算法（如块匹配）通过计算像素邻域的相似度确定匹配点，虽速度快但易受噪声和纹理缺失影响；全局匹配算法（如 Graph-Cut）通过能量函数优化求解全局最优解，虽精度高但计算复杂度呈指数级增长，难以满足实时性要求。SGM 算法提出 “半全局” 策略：通过在多个方向上进行一维代价聚合，近似实现二维全局优化。其核心思想可概括为 “以线代面”—— 在 8 个（或 16 个）不同方向上计算路径代价，将各方向的聚合代价累加作为最终匹配代价。这种设计既规避了全局算法的高复杂度，又通过多方向信息融合提升了匹配鲁棒性，使算法能在普通 GPU 上实现实时运行（帧率≥30fps）。

代价计算是 SGM 的第一步，目的是量化左右视图中像素的匹配程度，生成初始代价体积（Cost Volume）。初始代价需能有效区分匹配与非匹配像素，常用方法包括基于像素值的度量和基于变换特征的度量。基于像素值的度量中，SAD（Sum of Absolute Differences）计算左右像素块对应位置的灰度差绝对值之和，公式为 SAD (u,v,d) = Σ|Iₗ(u+i,v+j) - Iᵣ(u+i-d,v+j)|，其中 (u,v) 为像素坐标，d 为视差假设，Iₗ、Iᵣ分别为左右视图灰度值，SAD 计算简单但对光照变化敏感；SSD（Sum of Squared Differences）通过平方差放大像素差异，对噪声更敏感但能增强匹配峰度。基于特征变换的度量中，Census 变换将像素灰度值转换为二进制特征向量，通过比较邻域像素与中心像素的大小关系（大于为 1，小于为 0）生成抗光照变化的特征，Census 代价通过计算二进制向量的汉明距离获得，对光照鲁棒性强，是 SGM 的常用选择。初始代价体积的维度为 H×W×D（高度 × 宽度 × 最大视差），每个元素代表像素在某视差假设下的匹配代价，值越小表示匹配度越高。

代价聚合是 SGM 的核心创新，通过在多个方向上传播匹配代价，实现对局部噪声的抑制和遮挡区域的鲁棒处理。传统局部匹配仅在固定窗口内聚合代价，易受窗口尺寸影响；而 SGM 通过动态规划在一维路径上聚合代价，再融合多方向结果，近似全局优化效果。对每个像素 (u,v) 和视差 d，沿某一方向（如水平、垂直、45°、135° 等）的聚合代价 L 可通过递归计算：L (u,v,d) = C (u,v,d) + min [L (u',v',d), L (u',v',d-1)+P1, L (u',v',d+1)+P1, minₖL (u',v',k)+P2] - minₖL (u',v',d)，其中 C (u,v,d) 为初始代价，(u',v') 为路径上的前一个像素，P1 为小惩罚项（用于惩罚视差连续变化 1 的情况），P2 为大惩罚项（用于惩罚视差跳变超过 1 的情况），最后一项 minₖL (...) 用于归一化，避免代价累积溢出。该公式通过动态规划实现：在路径上传播时，既考虑当前像素的初始代价，也参考前序像素在不同视差下的最优代价，通过惩罚视差突变实现平滑约束。SGM 通常选择 8 个方向（0°、45°、90°、135°、180°、225°、270°、315°）进行路径聚合，每个方向生成独立的聚合代价图，最终聚合代价通过累加所有方向的聚合代价获得：S (u,v,d) = ΣLᵢ(u,v,d)（i=1..8）。多方向融合的意义在于：不同方向的路径能捕捉场景中不同结构的连续性（如水平路径适合处理地平线，垂直路径适合处理柱状物体），通过互补信息抑制局部歧义，尤其对遮挡区域（某一方向路径被遮挡时，其他方向仍能提供有效信息）具有显著优化效果。