完整搜尋頁面 →

程式碼中的光束法平差

選讀・DLCV 11・三維重建:從多視角幾何到 NeRF 與 Gaussian Splatting 的補充資料(第 3/7 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。

導覽:本頁與本系列: 導覽:本頁與本系列

本頁內容

補充資料 · 7

  1. 正規化八點演算法
  2. 線性三角測量(DLT)
  3. 程式碼中的光束法平差
  4. 平面誘導的單應性
  5. 多解析度雜湊編碼
  6. 為什麼 NeuS 的權重會在表面上達到峰值
  7. 投影 3D 高斯:局部仿射近似

論文導讀 · 3

  1. NeRF(Mildenhall 等人,2020)
  2. 3D Gaussian Splatting(Kerbl 等人,2023)
  3. 「現代觀點」綜述導讀

電腦視覺深度學習

  1. 02 · 深度影像分類
  2. 03 · 物件偵測:從 R-CNN 到 DETR
  3. 09 · 深度影像復原:低階視覺
查看完整課程樹 →

這則筆記用 SciPy 建立一個完整的小型光束法平差,說明殘差函數、Jacobian 的稀疏性,以及規範(gauge)自由度。

參數。 每台相機有一個旋轉向量 ω∈R3\boldsymbol{\omega} \in \mathbb{R}^3(軸乘以角度)與一個平移 t∈R3\mathbf{t} \in \mathbb{R}^3;每個點有三個座標。有 ncn_c 台相機與 npn_p 個點時,共有 6nc+3np6 n_c + 3 n_p 個未知數,每個觀測有兩個殘差(uu 與 vv 的誤差)。

規範(gauge)。 把整個場景一起旋轉、平移或縮放,重投影誤差都不會改變:共有七個方向(旋轉三個、平移三個、尺度一個)讓代價保持不變。如果不固定它們,正規方程式是奇異的。這裡把相機 0 固定為單位矩陣,去掉六個;尺度保持自由,實際上由起始點固定。真實的系統會明確固定它,例如固定兩台相機之間的距離。

稀疏性。 觀測 (c,k)(c, k) 的殘差只依賴相機 cc 與點 kk,所以每一對 Jacobian 的列最多有 6+36 + 3 個非零元素。把這個模式傳給 least_squares,它就能使用稀疏有限差分與稀疏求解器。

程式碼 · Python · 52 行
import numpy as np
from scipy.optimize import least_squares
from scipy.sparse import lil_matrix
from scipy.spatial.transform import Rotation

rng = np.random.default_rng(0)
f, c = 800.0, np.array([320.0, 240.0])
n_cam, n_pts = 4, 80
X_true = rng.uniform([-3, -2, 4], [3, 2, 8], (n_pts, 3))
rvec_true = np.array([[0, 0, 0], [0, -0.15, 0], [0, -0.3, 0.02], [0.05, -0.45, 0]])  # rotation vectors
tvec_true = np.array([[0, 0, 0], [1.0, 0, 0.1], [2.0, 0.1, 0.3], [3.0, 0, 0.6]])

def project(rvec, tvec, X):
    Xc = Rotation.from_rotvec(rvec).apply(X) + tvec
    return f * Xc[:, :2] / Xc[:, 2:] + c

cam_idx = np.repeat(np.arange(n_cam), n_pts)           # every camera sees every point
pt_idx = np.tile(np.arange(n_pts), n_cam)
obs = np.concatenate([project(rvec_true[i], tvec_true[i], X_true) for i in range(n_cam)])
obs += rng.normal(0, 0.5, obs.shape)                    # 0.5 px measurement noise

def residuals(params):
    """Reprojection errors. Camera 0 is held fixed (it defines the world frame)."""
    cams = np.vstack([np.zeros(6), params[:6 * (n_cam - 1)].reshape(-1, 6)])
    X = params[6 * (n_cam - 1):].reshape(-1, 3)
    pred = np.empty_like(obs)
    for i in range(n_cam):
        m = cam_idx == i
        pred[m] = project(cams[i, :3], cams[i, 3:], X[pt_idx[m]])
    return (pred - obs).ravel()

def sparsity():
    """Each residual depends on one camera (6 numbers) and one point (3 numbers)."""
    S = lil_matrix((2 * len(obs), 6 * (n_cam - 1) + 3 * n_pts), dtype=int)
    for k, (i, j) in enumerate(zip(cam_idx, pt_idx)):
        rows = [2 * k, 2 * k + 1]
        if i > 0:
            S[np.ix_(rows, range(6 * (i - 1), 6 * i))] = 1
        S[np.ix_(rows, range(6 * (n_cam - 1) + 3 * j, 6 * (n_cam - 1) + 3 * j + 3))] = 1
    return S

# A rough start, as incremental SfM would provide: perturbed poses and points
x0 = np.concatenate([np.c_[rvec_true[1:] + rng.normal(0, 0.02, (3, 3)),
                           tvec_true[1:] + rng.normal(0, 0.1, (3, 3))].ravel(),
                     (X_true + rng.normal(0, 0.2, X_true.shape)).ravel()])
rms = lambda p: np.sqrt(np.mean(residuals(p) ** 2))
sol = least_squares(residuals, x0, jac_sparsity=sparsity(), x_scale='jac', method='trf')
print(f"unknowns {x0.size}, residuals {2 * len(obs)}, Jacobian non-zeros {sparsity().nnz} "
      f"({100 * sparsity().nnz / (x0.size * 2 * len(obs)):.1f}%)")
print(f"reprojection RMS: start {rms(x0):.2f} px -> after bundle adjustment {rms(sol.x):.3f} px")
X_hat = sol.x[6 * (n_cam - 1):].reshape(-1, 3)
print(f"median 3D point error after BA: {np.median(np.linalg.norm(X_hat - X_true, axis=1)):.4f} units")

輸出

unknowns 258, residuals 640, Jacobian non-zeros 4800 (2.9%)
reprojection RMS: start 32.31 px -> after bundle adjustment 0.388 px
median 3D point error after BA: 0.0122 units

即使在這個小問題中,Jacobian 也只有 2.9% 非零,而且問題越大比例越小,因為每增加一個點,新增的欄只會碰到它自己的觀測。重投影誤差從 32.31 像素降到 0.388 像素,略低於 0.5 像素的雜訊,與正文的兩視角擬合相同。正式的求解器還會更進一步:用 Schur 補(Schur complement)消去這些點,只對相機參數解一個縮減的系統 [13],並使用穩健損失 ρ\rho,讓少數錯誤配對無法拉偏解(這裡 least_squares(..., loss='huber') 就能做到)。

參考文獻

  1. R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, 2nd ed., Cambridge University Press, 2004. doi
  2. J. L. Schönberger and J.-M. Frahm, “Structure-from-motion revisited,” in Proc. IEEE CVPR, 2016. CVF
  3. J. L. Schönberger, E. Zheng, J.-M. Frahm and M. Pollefeys, “Pixelwise view selection for unstructured multi-view stereo,” in Proc. ECCV, 2016. doi
  4. J. L. Schönberger et al., “COLMAP,” official documentation (general-purpose structure-from-motion and multi-view stereo pipeline). link
  5. B. Mildenhall, P. P. Srinivasan, M. Tancik, J. T. Barron, R. Ramamoorthi and R. Ng, “NeRF: Representing scenes as neural radiance fields for view synthesis,” in Proc. ECCV, 2020; also Communications of the ACM, vol. 65, no. 1, pp. 99–106, 2022. doi · CACM doi · arXiv
  6. B. Kerbl, G. Kopanas, T. Leimkühler and G. Drettakis, “3D Gaussian Splatting for real-time radiance field rendering,” ACM Transactions on Graphics, vol. 42, no. 4, 2023. doi · arXiv
  7. H. C. Longuet-Higgins, “A computer algorithm for reconstructing a scene from two projections,” Nature, vol. 293, pp. 133–135, 1981. doi
  8. R. I. Hartley, “In defense of the eight-point algorithm,” IEEE TPAMI, vol. 19, no. 6, pp. 580–593, 1997. doi
  9. D. Nistér, “An efficient solution to the five-point relative pose problem,” IEEE TPAMI, vol. 26, no. 6, pp. 756–770, 2004. doi
  10. M. A. Fischler and R. C. Bolles, “Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography,” Communications of the ACM, vol. 24, no. 6, pp. 381–395, 1981. doi
  11. D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, vol. 60, no. 2, pp. 91–110, 2004. doi
  12. N. Snavely, S. M. Seitz and R. Szeliski, “Photo tourism: Exploring photo collections in 3D,” ACM Transactions on Graphics, vol. 25, no. 3, pp. 835–846, 2006. doi
  13. B. Triggs, P. F. McLauchlan, R. I. Hartley and A. W. Fitzgibbon, “Bundle adjustment — A modern synthesis,” in Vision Algorithms: Theory and Practice, LNCS 1883, pp. 298–372, Springer, 2000. doi
  14. R. T. Collins, “A space-sweep approach to true multi-image matching,” in Proc. IEEE CVPR, pp. 358–363, 1996. doi
  15. B. Curless and M. Levoy, “A volumetric method for building complex models from range images,” in Proc. SIGGRAPH, pp. 303–312, 1996. doi
  16. Y. Yao, Z. Luo, S. Li, T. Fang and L. Quan, “MVSNet: Depth inference for unstructured multi-view stereo,” in Proc. ECCV, 2018. CVF · doi
  17. N. Max, “Optical models for direct volume rendering,” IEEE Transactions on Visualization and Computer Graphics, vol. 1, no. 2, pp. 99–108, 1995. doi
  18. M. Tancik, P. P. Srinivasan, B. Mildenhall, S. Fridovich-Keil, N. Raghavan, U. Singhal, R. Ramamoorthi, J. T. Barron and R. Ng, “Fourier features let networks learn high frequency functions in low dimensional domains,” in Proc. NeurIPS, 2020. proceedings
  19. T. Müller, A. Evans, C. Schied and A. Keller, “Instant neural graphics primitives with a multiresolution hash encoding,” ACM Transactions on Graphics, vol. 41, no. 4, 2022. doi · arXiv
  20. J. J. Park, P. Florence, J. Straub, R. Newcombe and S. Lovegrove, “DeepSDF: Learning continuous signed distance functions for shape representation,” in Proc. IEEE/CVF CVPR, 2019. CVF
  21. L. Mescheder, M. Oechsle, M. Niemeyer, S. Nowozin and A. Geiger, “Occupancy networks: Learning 3D reconstruction in function space,” in Proc. IEEE/CVF CVPR, 2019. CVF
  22. P. Wang, L. Liu, Y. Liu, C. Theobalt, T. Komura and W. Wang, “NeuS: Learning neural implicit surfaces by volume rendering for multi-view reconstruction,” in Proc. NeurIPS, 2021. proceedings · arXiv
  23. M. Zwicker, H. Pfister, J. van Baar and M. Gross, “EWA volume splatting,” in Proc. IEEE Visualization, 2001. doi
  24. W. E. Lorensen and H. E. Cline, “Marching cubes: A high resolution 3D surface construction algorithm,” in Proc. SIGGRAPH, pp. 163–169, 1987. doi
  25. M. Kazhdan, M. Bolitho and H. Hoppe, “Poisson surface reconstruction,” in Proc. Eurographics Symposium on Geometry Processing, 2006. doi
  26. M. Kazhdan and H. Hoppe, “Screened Poisson surface reconstruction,” ACM Transactions on Graphics, vol. 32, no. 3, 2013. doi
  27. A. Guédon and V. Lepetit, “SuGaR: Surface-aligned Gaussian splatting for efficient 3D mesh reconstruction and high-quality mesh rendering,” in Proc. IEEE/CVF CVPR, 2024. CVF · arXiv
  28. B. Huang, Z. Yu, A. Chen, A. Geiger and S. Gao, “2D Gaussian splatting for geometrically accurate radiance fields,” in Proc. SIGGRAPH (Conference Papers), 2024. doi · arXiv
  29. S. Wang, V. Leroy, Y. Cabon, B. Chidlovskii and J. Revaud, “DUSt3R: Geometric 3D vision made easy,” in Proc. IEEE/CVF CVPR, 2024. CVF · arXiv
  30. V. Leroy, Y. Cabon and J. Revaud, “Grounding image matching in 3D with MASt3R,” in Proc. ECCV, 2024. doi · arXiv
  31. J. Wang, M. Chen, N. Karaev, A. Vedaldi, C. Rupprecht and D. Novotny, “VGGT: Visual geometry grounded transformer,” in Proc. IEEE/CVF CVPR, 2025. CVF · arXiv
  32. A. Pumarola, E. Corona, G. Pons-Moll and F. Moreno-Noguer, “D-NeRF: Neural radiance fields for dynamic scenes,” in Proc. IEEE/CVF CVPR, 2021. CVF
  33. G. Wu, T. Yi, J. Fang, L. Xie, X. Zhang, W. Wei, W. Liu, Q. Tian and X. Wang, “4D Gaussian splatting for real-time dynamic scene rendering,” in Proc. IEEE/CVF CVPR, 2024. CVF · arXiv
  34. 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
  35. R. Zhang, P. Isola, A. A. Efros, E. Shechtman and O. Wang, “The unreasonable effectiveness of deep features as a perceptual metric,” in Proc. IEEE/CVF CVPR, 2018. CVF
  36. H. Fan, H. Su and L. J. Guibas, “A point set generation network for 3D object reconstruction from a single image,” in Proc. IEEE CVPR, 2017. CVF
  37. R. Jensen, A. Dahl, G. Vogiatzis, E. Tola and H. Aanæs, “Large scale multi-view stereopsis evaluation,” in Proc. IEEE CVPR, pp. 406–413, 2014. doi
  38. A. Knapitsch, J. Park, Q.-Y. Zhou and V. Koltun, “Tanks and Temples: Benchmarking large-scale scene reconstruction,” ACM Transactions on Graphics, vol. 36, no. 4, 2017. doi · benchmark
  39. J. T. Barron, B. Mildenhall, D. Verbin, P. P. Srinivasan and P. Hedman, “Mip-NeRF 360: Unbounded anti-aliased neural radiance fields,” in Proc. IEEE/CVF CVPR, 2022. CVF · arXiv
  40. D. Verbin, P. Hedman, B. Mildenhall, T. Zickler, J. T. Barron and P. P. Srinivasan, “Ref-NeRF: Structured view-dependent appearance for neural radiance fields,” in Proc. IEEE/CVF CVPR, 2022. CVF
  41. C.-H. Lin, W.-C. Ma, A. Torralba and S. Lucey, “BARF: Bundle-adjusting neural radiance fields,” in Proc. IEEE/CVF ICCV, 2021. CVF
  42. S. M. Seitz, B. Curless, J. Diebel, D. Scharstein and R. Szeliski, “A comparison and evaluation of multi-view stereo reconstruction algorithms,” in Proc. IEEE CVPR, vol. 1, pp. 519–528, 2006. doi
  43. Y. Furukawa and C. Hernández, “Multi-view stereo: A tutorial,” Foundations and Trends in Computer Graphics and Vision, vol. 9, no. 1–2, pp. 1–148, 2015. doi
  44. A. Tewari, J. Thies, B. Mildenhall, P. Srinivasan, E. Tretschk, W. Yifan, C. Lassner, V. Sitzmann et al., “Advances in neural rendering,” Computer Graphics Forum, vol. 41, no. 2, pp. 703–735, 2022. doi · arXiv
  45. G. Chen and W. Wang, “A survey on 3D Gaussian splatting,” ACM Computing Surveys, vol. 58, no. 12, 2026. doi · arXiv
  46. scikit-image contributors, “skimage.measure.marching_cubes,” scikit-image documentation (API reference). docs
  47. A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai et al., “An image is worth 16x16 words: Transformers for image recognition at scale,” in Proc. ICLR, 2021. arXiv
  48. A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser and I. Polosukhin, “Attention is all you need,” in Proc. NeurIPS, 2017. proceedings
  49. D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in Proc. ICLR, 2015. arXiv