程式碼中的光束法平差
選讀・DLCV 11・三維重建:從多視角幾何到 NeRF 與 Gaussian Splatting 的補充資料(第 3/7 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。
導覽:本頁與本系列: 導覽:本頁與本系列
這則筆記用 SciPy 建立一個完整的小型光束法平差,說明殘差函數、Jacobian 的稀疏性,以及規範(gauge)自由度。
參數。 每台相機有一個旋轉向量 (軸乘以角度)與一個平移 ;每個點有三個座標。有 台相機與 個點時,共有 個未知數,每個觀測有兩個殘差( 與 的誤差)。
規範(gauge)。 把整個場景一起旋轉、平移或縮放,重投影誤差都不會改變:共有七個方向(旋轉三個、平移三個、尺度一個)讓代價保持不變。如果不固定它們,正規方程式是奇異的。這裡把相機 0 固定為單位矩陣,去掉六個;尺度保持自由,實際上由起始點固定。真實的系統會明確固定它,例如固定兩台相機之間的距離。
稀疏性。 觀測 的殘差只依賴相機 與點 ,所以每一對 Jacobian 的列最多有 個非零元素。把這個模式傳給 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],並使用穩健損失 ,讓少數錯誤配對無法拉偏解(這裡 least_squares(..., loss='huber') 就能做到)。
參考文獻
- R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, 2nd ed., Cambridge University Press, 2004. doi
- J. L. Schönberger and J.-M. Frahm, “Structure-from-motion revisited,” in Proc. IEEE CVPR, 2016. CVF
- 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
- J. L. Schönberger et al., “COLMAP,” official documentation (general-purpose structure-from-motion and multi-view stereo pipeline). link
- 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
- 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
- H. C. Longuet-Higgins, “A computer algorithm for reconstructing a scene from two projections,” Nature, vol. 293, pp. 133–135, 1981. doi
- R. I. Hartley, “In defense of the eight-point algorithm,” IEEE TPAMI, vol. 19, no. 6, pp. 580–593, 1997. doi
- D. Nistér, “An efficient solution to the five-point relative pose problem,” IEEE TPAMI, vol. 26, no. 6, pp. 756–770, 2004. doi
- 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
- D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, vol. 60, no. 2, pp. 91–110, 2004. doi
- 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
- 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
- R. T. Collins, “A space-sweep approach to true multi-image matching,” in Proc. IEEE CVPR, pp. 358–363, 1996. doi
- B. Curless and M. Levoy, “A volumetric method for building complex models from range images,” in Proc. SIGGRAPH, pp. 303–312, 1996. doi
- 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
- N. Max, “Optical models for direct volume rendering,” IEEE Transactions on Visualization and Computer Graphics, vol. 1, no. 2, pp. 99–108, 1995. doi
- 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
- 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
- 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
- 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
- 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
- M. Zwicker, H. Pfister, J. van Baar and M. Gross, “EWA volume splatting,” in Proc. IEEE Visualization, 2001. doi
- W. E. Lorensen and H. E. Cline, “Marching cubes: A high resolution 3D surface construction algorithm,” in Proc. SIGGRAPH, pp. 163–169, 1987. doi
- M. Kazhdan, M. Bolitho and H. Hoppe, “Poisson surface reconstruction,” in Proc. Eurographics Symposium on Geometry Processing, 2006. doi
- M. Kazhdan and H. Hoppe, “Screened Poisson surface reconstruction,” ACM Transactions on Graphics, vol. 32, no. 3, 2013. doi
- 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
- 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
- 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
- V. Leroy, Y. Cabon and J. Revaud, “Grounding image matching in 3D with MASt3R,” in Proc. ECCV, 2024. doi · arXiv
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- C.-H. Lin, W.-C. Ma, A. Torralba and S. Lucey, “BARF: Bundle-adjusting neural radiance fields,” in Proc. IEEE/CVF ICCV, 2021. CVF
- 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
- 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
- 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
- G. Chen and W. Wang, “A survey on 3D Gaussian splatting,” ACM Computing Surveys, vol. 58, no. 12, 2026. doi · arXiv
- scikit-image contributors, “skimage.measure.marching_cubes,” scikit-image documentation (API reference). docs
- 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
- 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
- D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in Proc. ICLR, 2015. arXiv