半全域匹配一步一步來
選讀・DLCV 11A・深度估計與光流 的補充資料(第 2/4 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。
導覽:本頁與本系列: 導覽:本頁與本系列
這則筆記沿著一條掃描線,逐步走過 SGM 的遞迴,也就是正文只用一條式子說完的部分。
遞迴。 在方向為 的路徑上(水平掃描線是 ,由左到右),像素 在視差 的聚合代價為
其中 是匹配代價, 是前一個像素的聚合代價,, 是改變一級的懲罰, 是較大跳變的懲罰 [5], [6]。四個選項分別是:維持前一個視差(免費)、改變一級(代價 ),或從前一個最佳視差跳到任何其他視差(代價 )。減去 不會改變最小值的位置,只是讓 維持有界。
為什麼 。 傾斜的表面視差是逐漸變化的,每隔幾個像素變一級,所以小步長必須便宜。深度邊緣是罕見的大跳變,應該付出更高的代價,但不論大小都要是固定的量,這樣真正的邊緣才不會被平滑成斜坡。例如 MC-CNN 在影像梯度大的地方會降低兩個懲罰,因為深度邊緣常和強度邊緣重合 [6]。
為什麼需要多條路徑。 一條由左到右的路徑只會從左邊傳播資訊;無紋理區域左端的像素得到幫助,右端的像素則沒有。把多個方向的路徑加總,就讓每個像素得到來自四面八方的支援。完整演算法用 8 個方向;OpenCV 預設用 5 個 [7]。
在一條掃描線上的測試。 這段程式碼為 60 個像素建立代價陣列,在第 30 欄有一個從 5 到 9 的視差階梯,並有一段無紋理的區間(第 10–23 欄),其中所有代價幾乎相等,然後比較 WTA 和「由左到右路徑加上由右到左路徑」的加總。
程式碼 · Python · 26 行
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]}")輸出
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/9WTA 讓每個有紋理的像素都對,每個無紋理的像素都錯。兩條 SGM 路徑則用鄰居的視差填滿無紋理的區間,而第 29/30 欄的深度階梯得以保留:跳變只需付一次 ,而如果在階梯之後保留錯誤的視差,之後每個有紋理的像素都要付出很大的匹配代價。
參考文獻
- R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, 2nd ed., Cambridge University Press, 2004. doi
- 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
- 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
- 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
- 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
- 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
- OpenCV contributors, “cv::StereoSGBM class documentation,” OpenCV source,
modules/calib3d/include/opencv2/calib3d.hpp(4.x branch). source - 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
- 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
- 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
- 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
- J.-R. Chang and Y.-S. Chen, “Pyramid stereo matching network,” in Proc. IEEE/CVF CVPR, 2018. CVF
- 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
- G. Xu, X. Wang, X. Ding and X. Yang, “Iterative geometry encoding volume for stereo matching,” in Proc. IEEE/CVF CVPR, 2023. CVF
- 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
- 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
- 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
- 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
- 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
- R. Ranftl, A. Bochkovskiy and V. Koltun, “Vision transformers for dense prediction,” in Proc. IEEE/CVF ICCV, 2021. CVF
- L. Yang, B. Kang, Z. Huang, Z. Zhao, X. Xu, J. Feng and H. Zhao, “Depth Anything V2,” in Proc. NeurIPS, 2024. proceedings · arXiv
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- C. Godard, O. Mac Aodha and G. J. Brostow, “Unsupervised monocular depth estimation with left-right consistency,” in Proc. IEEE CVPR, 2017. CVF
- 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
- 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
- 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
- B. K. P. Horn and B. G. Schunck, “Determining optical flow,” Artificial Intelligence, vol. 17, no. 1–3, pp. 185–203, 1981. doi
- 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
- 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
- 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
- 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
- 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
- A. Ranjan and M. J. Black, “Optical flow estimation using a spatial pyramid network,” in Proc. IEEE CVPR, 2017. CVF
- 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
- 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
- Z. Teed and J. Deng, “RAFT-3D: Scene flow using rigid-motion embeddings,” in Proc. IEEE/CVF CVPR, 2021. CVF · arXiv
- 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
- 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
- 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
- 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
- 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
- M. Menze and A. Geiger, “Object scene flow for autonomous vehicles,” in Proc. IEEE CVPR, pp. 3061–3070, 2015. CVF · doi
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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