Full search page →

Semi-global matching step by step

Optional · supplementary note 2 of 4 for DLCV 11A · Depth Estimation and Optical Flow. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.

Navigate: this page and this track: Navigate: this page and this track

On this page

Supplementary notes · 4

  1. Robust matching costs: ZNCC and census
  2. Semi-global matching step by step
  3. Sub-pixel disparity and the soft argmin
  4. Monocular depth foundation models: data and the camera

Paper guides · 3

  1. RAFT (Teed and Deng, 2020)
  2. MiDaS (Ranftl et al., 2022)
  3. Guide to the Modern view surveys

Deep Learning for Computer Vision

  1. 02 · Deep Image Classification
View the whole course tree →

This note walks through SGM’s recursion on one scanline, the part that the main text states in one equation.

The recursion. On a path with direction r\mathbf{r} (for a horizontal scanline, r=(1,0)\mathbf{r} = (1, 0), left to right), the aggregated cost at pixel xx and disparity dd is

L(x,d)=C(x,d)+min⁡(L(x−1,d),  L(x−1,d−1)+P1,  L(x−1,d+1)+P1,  mx−1+P2)−mx−1,L(x, d) = C(x, d) + \min\bigl( L(x-1, d),\; L(x-1, d-1) + P_1,\; L(x-1, d+1) + P_1,\; m_{x-1} + P_2 \bigr) - m_{x-1},

where C(x,d)C(x, d) is the matching cost, L(x−1,⋅)L(x-1, \cdot) are the aggregated costs of the previous pixel, mx−1=min⁡kL(x−1,k)m_{x-1} = \min_k L(x-1, k), P1P_1 is the penalty for a change of one level and P2P_2 the penalty for a larger jump [5], [6]. The four options are: keep the previous disparity (free), change by one level (cost P1P_1), or jump from the best previous disparity to any other (cost P2P_2). Subtracting mx−1m_{x-1} does not change the minimizer; it only keeps LL bounded.

Why P1<P2P_1 \lt P_2. A slanted surface changes disparity gradually, one level every few pixels, so small steps must be cheap. A depth edge is a large jump that happens rarely, so it should cost more, but a fixed amount regardless of size, so that real edges are not smoothed into ramps. MC-CNN, for example, lowers both penalties where the image gradient is large, because depth edges often coincide with intensity edges [6].

Why several paths. One left-to-right path only propagates information from the left; a pixel at the left end of a textureless region gets help, one at the right end does not. Summing paths from several directions gives each pixel support from all around. The full algorithm uses 8 directions; OpenCV’s default uses 5 [7].

A test on one scanline. The snippet builds a cost array for 60 pixels with a disparity step from 5 to 9 at column 30 and a textureless stretch (columns 10–23) where all costs are nearly equal, and compares WTA with the sum of a left-to-right and a right-to-left path.

Code · Python · 26 lines
import numpy as np

rng = np.random.default_rng(0)
Wd, D = 60, 16
d_true = np.where(np.arange(Wd) < 30, 5, 9)             # a depth step at column 30
cost = rng.uniform(0.6, 1.0, (Wd, D))                   # matching cost C(x, d) along one scanline
textured = np.ones(Wd, bool); textured[10:24] = False    # columns 10..23 have no texture
cost[textured, d_true[textured]] = 0.1                   # textured pixels: a clear minimum
cost[~textured] = 0.6 + 0.02 * rng.standard_normal((14, D))   # textureless: flat and noisy

def aggregate(C, P1=0.05, P2=0.3):
    """One SGM path from left to right: L(x, d) = C(x, d) + min(...) - min_k L(x-1, k)."""
    L = np.empty_like(C); L[0] = C[0]
    for x in range(1, len(C)):
        prev = L[x - 1]; m = prev.min()
        up = np.r_[prev[1:], np.inf] + P1               # neighbour had disparity d + 1
        down = np.r_[np.inf, prev[:-1]] + P1            # neighbour had disparity d - 1
        L[x] = C[x] + np.minimum.reduce([prev, up, down, np.full(D, m + P2)]) - m
    return L

S = aggregate(cost) + aggregate(cost[::-1])[::-1]       # two paths: left-to-right and right-to-left
for name, c in [("winner-take-all", cost), ("SGM, 2 paths", S)]:
    d_hat = c.argmin(1)
    print(f"{name:16s} correct: textured {np.mean(d_hat[textured] == d_true[textured]):.2f}, "
          f"textureless {np.mean(d_hat[~textured] == d_true[~textured]):.2f}, "
          f"step kept at x=29/30: {d_hat[29]}/{d_hat[30]}")

Output

winner-take-all  correct: textured 1.00, textureless 0.00, step kept at x=29/30: 5/9
SGM, 2 paths     correct: textured 1.00, textureless 1.00, step kept at x=29/30: 5/9

WTA gets every textured pixel right and every textureless one wrong. Two SGM paths fill the textureless stretch with the disparity of its neighbours, and the depth step at columns 29/30 survives: a jump costs P2P_2 only once, while keeping the wrong disparity beyond the step would pay the large matching cost at every following textured pixel.

References

  1. R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, 2nd ed., Cambridge University Press, 2004. doi
  2. D. Scharstein and R. Szeliski, “A taxonomy and evaluation of dense two-frame stereo correspondence algorithms,” International Journal of Computer Vision, vol. 47, no. 1–3, pp. 7–42, 2002. doi
  3. D. Scharstein, R. Szeliski and H. Hirschmüller, “Middlebury Stereo Evaluation — Version 3,” official benchmark page (bad 2.0 metric, non-occluded and all masks). link · stereo home page
  4. R. Zabih and J. Woodfill, “Non-parametric local transforms for computing visual correspondence,” in Computer Vision — ECCV ‘94 (Lecture Notes in Computer Science), pp. 151–158, Springer, 1994. doi
  5. H. Hirschmüller, “Stereo processing by semiglobal matching and mutual information,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 2, pp. 328–341, 2008. doi
  6. J. Žbontar and Y. LeCun, “Stereo matching by training a convolutional neural network to compare image patches,” Journal of Machine Learning Research, vol. 17, no. 65, pp. 1–32, 2016. JMLR · arXiv
  7. OpenCV contributors, “cv::StereoSGBM class documentation,” OpenCV source, modules/calib3d/include/opencv2/calib3d.hpp (4.x branch). source
  8. H. Laga, L. V. Jospin, F. Boussaid and M. Bennamoun, “A survey on deep learning techniques for stereo-based depth estimation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 44, no. 4, pp. 1738–1764, 2022. doi · arXiv
  9. F. Tosi, L. Bartolomei and M. Poggi, “A survey on deep stereo matching in the twenties,” International Journal of Computer Vision, vol. 133, no. 7, pp. 4245–4276, 2025. doi · arXiv
  10. N. Mayer, E. Ilg, P. Häusser, P. Fischer, D. Cremers, A. Dosovitskiy and T. Brox, “A large dataset to train convolutional networks for disparity, optical flow, and scene flow estimation,” in Proc. IEEE CVPR, pp. 4040–4048, 2016. CVF · doi
  11. A. Kendall, H. Martirosyan, S. Dasgupta, P. Henry, R. Kennedy, A. Bachrach and A. Bry, “End-to-end learning of geometry and context for deep stereo regression,” in Proc. IEEE ICCV, 2017. CVF
  12. J.-R. Chang and Y.-S. Chen, “Pyramid stereo matching network,” in Proc. IEEE/CVF CVPR, 2018. CVF
  13. L. Lipson, Z. Teed and J. Deng, “RAFT-Stereo: Multilevel recurrent field transforms for stereo matching,” in Proc. International Conference on 3D Vision (3DV), pp. 218–227, 2021. doi · arXiv
  14. G. Xu, X. Wang, X. Ding and X. Yang, “Iterative geometry encoding volume for stereo matching,” in Proc. IEEE/CVF CVPR, 2023. CVF
  15. M. Poggi, F. Tosi, K. Batsos, P. Mordohai and S. Mattoccia, “On the synergies between machine learning and binocular stereo for depth estimation from images: A survey,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021. doi · arXiv
  16. B. Wen, M. Trepte, J. Aribido, J. Kautz, O. Gallo and S. Birchfield, “FoundationStereo: Zero-shot stereo matching,” in Proc. IEEE/CVF CVPR, 2025. CVF · arXiv
  17. D. Eigen, C. Puhrsch and R. Fergus, “Depth map prediction from a single image using a multi-scale deep network,” in Proc. NeurIPS, 2014. proceedings · arXiv
  18. R. Ranftl, K. Lasinger, D. Hafner, K. Schindler and V. Koltun, “Towards robust monocular depth estimation: Mixing datasets for zero-shot cross-dataset transfer,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 44, no. 3, pp. 1623–1637, 2022. doi · arXiv
  19. L. Yang, B. Kang, Z. Huang, X. Xu, J. Feng and H. Zhao, “Depth Anything: Unleashing the power of large-scale unlabeled data,” in Proc. IEEE/CVF CVPR, 2024. CVF · arXiv
  20. R. Ranftl, A. Bochkovskiy and V. Koltun, “Vision transformers for dense prediction,” in Proc. IEEE/CVF ICCV, 2021. CVF
  21. L. Yang, B. Kang, Z. Huang, Z. Zhao, X. Xu, J. Feng and H. Zhao, “Depth Anything V2,” in Proc. NeurIPS, 2024. proceedings · arXiv
  22. B. Ke, A. Obukhov, S. Huang, N. Metzger, R. C. Daudt and K. Schindler, “Repurposing diffusion-based image generators for monocular depth estimation,” in Proc. IEEE/CVF CVPR, 2024. CVF · arXiv
  23. S. F. Bhat, R. Birkl, D. Wofk, P. Wonka and M. Müller, “ZoeDepth: Zero-shot transfer by combining relative and metric depth,” arXiv:2302.12288, 2023. arXiv
  24. W. Yin, C. Zhang, H. Chen, Z. Cai, G. Yu, K. Wang, X. Chen and C. Shen, “Metric3D: Towards zero-shot metric 3D prediction from a single image,” in Proc. IEEE/CVF ICCV, 2023. CVF · arXiv
  25. M. Hu, W. Yin, C. Zhang, Z. Cai, X. Long, K. Wang, H. Chen, G. Yu, C. Shen and S. Shen, “Metric3D v2: A versatile monocular geometric foundation model for zero-shot metric depth and surface normal estimation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 46, no. 12, pp. 10579–10596, 2024. doi · arXiv
  26. L. Piccinelli, Y.-H. Yang, C. Sakaridis, M. Segu, S. Li, L. Van Gool and F. Yu, “UniDepth: Universal monocular metric depth estimation,” in Proc. IEEE/CVF CVPR, 2024. CVF · arXiv
  27. A. Bochkovskii, A. Delaunoy, H. Germain, M. Santos, Y. Zhou, S. R. Richter and V. Koltun, “Depth Pro: Sharp monocular metric depth in less than a second,” in Proc. ICLR, 2025. OpenReview · arXiv
  28. R. Garg, V. Kumar B.G., G. Carneiro and I. Reid, “Unsupervised CNN for single view depth estimation: Geometry to the rescue,” in Proc. ECCV (Lecture Notes in Computer Science), pp. 740–756, 2016. doi · arXiv
  29. C. Godard, O. Mac Aodha and G. J. Brostow, “Unsupervised monocular depth estimation with left-right consistency,” in Proc. IEEE CVPR, 2017. CVF
  30. T. Zhou, M. Brown, N. Snavely and D. G. Lowe, “Unsupervised learning of depth and ego-motion from video,” in Proc. IEEE CVPR, 2017. CVF
  31. C. Godard, O. Mac Aodha, M. Firman and G. J. Brostow, “Digging into self-supervised monocular depth estimation,” in Proc. IEEE/CVF ICCV, 2019. CVF · arXiv
  32. Z. Wang, A. C. Bovik, H. R. Sheikh and E. P. Simoncelli, “Image quality assessment: From error visibility to structural similarity,” IEEE Transactions on Image Processing, vol. 13, no. 4, pp. 600–612, 2004. doi
  33. B. K. P. Horn and B. G. Schunck, “Determining optical flow,” Artificial Intelligence, vol. 17, no. 1–3, pp. 185–203, 1981. doi
  34. B. D. Lucas and T. Kanade, “An iterative image registration technique with an application to stereo vision,” in Proc. International Joint Conference on Artificial Intelligence (IJCAI), 1981. pdf
  35. G. Farnebäck, “Two-frame motion estimation based on polynomial expansion,” in Image Analysis (Lecture Notes in Computer Science), pp. 363–370, Springer, 2003. doi
  36. J. Hur and S. Roth, “Optical flow estimation in the deep learning age,” in Modelling Human Motion, N. Noceti, A. Sciutti and F. Rea, Eds., pp. 119–140, Springer, 2020. doi · arXiv
  37. A. Dosovitskiy, P. Fischer, E. Ilg, P. Häusser, C. Hazırbaş, V. Golkov, P. van der Smagt, D. Cremers and T. Brox, “FlowNet: Learning optical flow with convolutional networks,” in Proc. IEEE ICCV, 2015. CVF · arXiv
  38. E. Ilg, N. Mayer, T. Saikia, M. Keuper, A. Dosovitskiy and T. Brox, “FlowNet 2.0: Evolution of optical flow estimation with deep networks,” in Proc. IEEE CVPR, 2017. CVF
  39. A. Ranjan and M. J. Black, “Optical flow estimation using a spatial pyramid network,” in Proc. IEEE CVPR, 2017. CVF
  40. D. Sun, X. Yang, M.-Y. Liu and J. Kautz, “PWC-Net: CNNs for optical flow using pyramid, warping, and cost volume,” in Proc. IEEE/CVF CVPR, 2018. CVF
  41. Z. Teed and J. Deng, “RAFT: Recurrent all-pairs field transforms for optical flow,” in Proc. ECCV (Lecture Notes in Computer Science), pp. 402–419, 2020. doi · arXiv
  42. Z. Teed and J. Deng, “RAFT-3D: Scene flow using rigid-motion embeddings,” in Proc. IEEE/CVF CVPR, 2021. CVF · arXiv
  43. H. Xu, J. Zhang, J. Cai, H. Rezatofighi and D. Tao, “GMFlow: Learning optical flow via global matching,” in Proc. IEEE/CVF CVPR, 2022. CVF
  44. H. Xu, J. Zhang, J. Cai, H. Rezatofighi, F. Yu, D. Tao and A. Geiger, “Unifying flow, stereo and depth estimation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 45, no. 11, pp. 13941–13958, 2023. doi · arXiv
  45. Z. Huang, X. Shi, C. Zhang, Q. Wang, K. C. Cheung, H. Qin, J. Dai and H. Li, “FlowFormer: A transformer architecture for optical flow,” in Proc. ECCV (Lecture Notes in Computer Science), pp. 668–685, 2022. doi · arXiv
  46. Y. Wang, L. Lipson and J. Deng, “SEA-RAFT: Simple, efficient, accurate RAFT for optical flow,” in Proc. ECCV (Lecture Notes in Computer Science), pp. 36–54, 2024. doi · arXiv
  47. S. Vedula, S. Baker, P. Rander, R. Collins and T. Kanade, “Three-dimensional scene flow,” in Proc. IEEE ICCV, vol. 2, pp. 722–729, 1999. doi
  48. M. Menze and A. Geiger, “Object scene flow for autonomous vehicles,” in Proc. IEEE CVPR, pp. 3061–3070, 2015. CVF · doi
  49. A. Geiger, P. Lenz, C. Stiller and R. Urtasun, “Scene flow evaluation 2015 (stereo 2015, flow 2015, scene flow 2015),” The KITTI Vision Benchmark Suite, official benchmark page (dataset size, D1, D2, Fl and SF outlier definitions). link
  50. A. Geiger, P. Lenz, C. Stiller and R. Urtasun, “Stereo evaluation 2012,” The KITTI Vision Benchmark Suite, official benchmark page (dataset size, Out-Noc and Out-All at 2–5 px). link
  51. A. Geiger, P. Lenz and R. Urtasun, “Are we ready for autonomous driving? The KITTI vision benchmark suite,” in Proc. IEEE CVPR, pp. 3354–3361, 2012. doi
  52. D. Scharstein, H. Hirschmüller, Y. Kitajima, G. Krathwohl, N. Nešić, X. Wang and P. Westling, “High-resolution stereo datasets with subpixel-accurate ground truth,” in Pattern Recognition (Proc. GCPR) (Lecture Notes in Computer Science), pp. 31–42, Springer, 2014. doi · datasets
  53. T. Schöps, J. L. Schönberger, S. Galliani, T. Sattler, K. Schindler, M. Pollefeys and A. Geiger, “A multi-view stereo benchmark with high-resolution images and multi-camera videos,” in Proc. IEEE CVPR, pp. 2538–2547, 2017. CVF · datasets
  54. D. J. Butler, J. Wulff, G. B. Stanley and M. J. Black, “A naturalistic open source movie for optical flow evaluation,” in Proc. ECCV (Lecture Notes in Computer Science), pp. 611–625, 2012. doi · project page
  55. N. Silberman, D. Hoiem, P. Kohli and R. Fergus, “Indoor segmentation and support inference from RGBD images,” in Proc. ECCV (Lecture Notes in Computer Science), pp. 746–760, 2012. doi · dataset page
  56. U. Rajapaksha, F. Sohel, H. Laga, D. Diepeveen and M. Bennamoun, “Deep learning-based depth estimation methods from monocular image and videos: A comprehensive survey,” ACM Computing Surveys, vol. 56, no. 12, 2024. doi · arXiv