完整搜尋頁面 →

正規化八點演算法

選讀・DLCV 11・三維重建:從多視角幾何到 NeRF 與 Gaussian Splatting 的補充資料(第 1/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 · 深度影像復原:低階視覺
查看完整課程樹 →

這則筆記說明如何用八組或更多配對線性地估計基礎矩陣,以及為什麼要先重新縮放像素座標。

線性系統。 把 FF 寫成向量 f=(F11,F12,…,F33)\mathbf{f} = (F_{11}, F_{12}, \dots, F_{33})。一組配對 x1=(u1,v1,1)\mathbf{x}_1 = (u_1, v_1, 1)、x2=(u2,v2,1)\mathbf{x}_2 = (u_2, v_2, 1) 滿足 x2⊤Fx1=0\mathbf{x}_2^\top F \mathbf{x}_1 = 0,這是一個線性方程式 a⊤f=0\mathbf{a}^\top \mathbf{f} = 0,其中 a=x2⊗x1\mathbf{a} = \mathbf{x}_2 \otimes \mathbf{x}_1(全部九個乘積 u2u1,u2v1,u2,v2u1,…,1u_2 u_1, u_2 v_1, u_2, v_2 u_1, \dots, 1)。疊起 n≥8n \ge 8 組配對,得到 Af=0A\mathbf{f} = \mathbf{0},其中 A∈Rn×9A \in \mathbb{R}^{n \times 9}。滿足 ∥f∥=1\lVert \mathbf{f} \rVert = 1 的最小平方解,是 AA 最小奇異值所對應的右奇異向量 [7]、[8]。

秩為 2 的那一步。 真正的基礎矩陣秩為 2(所有對極線都通過同一點,即對極點)。線性解通常秩為 3。用 Frobenius 範數下最接近的秩 2 矩陣取代它:計算 F=U diag(σ1,σ2,σ3)V⊤F = U \,\mathrm{diag}(\sigma_1, \sigma_2, \sigma_3) V^\top,再令 σ3=0\sigma_3 = 0 [8]。對本質矩陣,兩個非零奇異值還必須相等,所以正文的程式碼才使用 diag(1,1,0)\mathrm{diag}(1, 1, 0)。

為什麼要正規化。 在像素座標中,a\mathbf{a} 的元素大小從約 1 到約 10510^5(像素在幾百的範圍時的 u2u1u_2 u_1)。於是矩陣 A⊤AA^\top A 的條件很差(見 ML 01c 的條件數),雜訊在小的奇異向量中被放大。Hartley [8] 證明,一個簡單的修正就能讓線性演算法變得有競爭力:平移每張影像的點,使其重心在原點,並縮放使其到原點的平均距離為 2\sqrt{2},影像 1 用相似轉換 T1T_1,影像 2 用 T2T_2。在正規化座標中解 F^\hat{F},強制秩為 2,再用 F=T2⊤F^ T1F = T_2^\top \hat{F}\, T_1 還原正規化。

測試。 這段程式碼在帶雜訊的配對(1 像素雜訊)上比較兩種版本,並在 1,000 組全新、無雜訊的配對上量測 Sampson 誤差,這是配對到對極約束的幾何距離的一階近似 [1]。

程式碼 · Python · 45 行
import numpy as np

rng = np.random.default_rng(1)
K = np.array([[800.0, 0, 320], [0, 800.0, 240], [0, 0, 1]])
a = np.deg2rad(12)
R = np.array([[np.cos(a), 0, -np.sin(a)], [0, 1, 0], [np.sin(a), 0, np.cos(a)]])  # camera 2 rotation
t = np.array([-1.0, 0.1, 0.1])                                                      # camera 2 translation
X = rng.uniform([-3, -2, 4], [3, 2, 8], (100, 3))
proj = lambda P: (P @ K.T)[:, :2] / (P @ K.T)[:, 2:]
x1 = proj(X) + rng.normal(0, 1.0, (100, 2))           # 1 px noise
x2 = proj(X @ R.T + t) + rng.normal(0, 1.0, (100, 2))

def eight_point(x1, x2, normalize=True):
    """Fundamental matrix from >= 8 matches (pixels); x2h^T F x1h = 0."""
    def T_of(x):                                      # move centroid to 0, mean distance to sqrt(2)
        c = x.mean(0); s = np.sqrt(2) / np.linalg.norm(x - c, axis=1).mean()
        return np.array([[s, 0, -s * c[0]], [0, s, -s * c[1]], [0, 0, 1]])
    T1, T2 = (T_of(x1), T_of(x2)) if normalize else (np.eye(3), np.eye(3))
    a = np.c_[x1, np.ones(len(x1))] @ T1.T
    b = np.c_[x2, np.ones(len(x2))] @ T2.T
    A = np.einsum('ni,nj->nij', b, a).reshape(-1, 9)
    F = np.linalg.svd(A)[2][-1].reshape(3, 3)
    U, S, Vt = np.linalg.svd(F)
    F = U @ np.diag([S[0], S[1], 0.0]) @ Vt           # enforce rank 2
    F = T2.T @ F @ T1                                 # undo the normalization
    return F / np.linalg.norm(F)

def sampson(F, x1, x2):
    """First-order geometric distance of each match to the epipolar constraint (pixels)."""
    a, b = np.c_[x1, np.ones(len(x1))], np.c_[x2, np.ones(len(x2))]
    Fa, Ftb = a @ F.T, b @ F
    num = np.sum(b * Fa, axis=1) ** 2
    return np.sqrt(num / (Fa[:, 0] ** 2 + Fa[:, 1] ** 2 + Ftb[:, 0] ** 2 + Ftb[:, 1] ** 2))

tx = np.array([[0, -t[2], t[1]], [t[2], 0, -t[0]], [-t[1], t[0], 0]])
F_true = np.linalg.inv(K).T @ tx @ R @ np.linalg.inv(K)       # F = K^-T [t]x R K^-1
F_true /= np.linalg.norm(F_true)
X_test = rng.uniform([-3, -2, 4], [3, 2, 8], (1000, 3))       # fresh, noise-free test matches
y1, y2 = proj(X_test), proj(X_test @ R.T + t)
for n in [8, 15, 100]:
    for norm in [False, True]:
        F = eight_point(x1[:n], x2[:n], norm)
        print(f"{n:3d} matches, normalized={str(norm):5s}: mean Sampson error on test matches "
              f"{sampson(F, y1, y2).mean():8.3f} px")
print(f"true F on the same test matches: {sampson(F_true, y1, y2).mean():.2e} px")

輸出

  8 matches, normalized=False: mean Sampson error on test matches    3.186 px
  8 matches, normalized=True : mean Sampson error on test matches    3.016 px
 15 matches, normalized=False: mean Sampson error on test matches    6.091 px
 15 matches, normalized=True : mean Sampson error on test matches    1.083 px
100 matches, normalized=False: mean Sampson error on test matches    0.632 px
100 matches, normalized=True : mean Sampson error on test matches    0.181 px
true F on the same test matches: 2.34e-14 px

在 15 或 100 組配對時,正規化版本在這次實驗中準確了好幾倍;只有最少的 8 組帶雜訊配對時,兩者都很差,這也是 RANSAC 樣本之後要再用所有內點重新擬合的原因之一。陷阱:正規化必須逐張影像計算,秩 2 的那一步必須在還原正規化之前進行,而退化的配置(所有點在同一個平面上,或兩台相機之間沒有平移)無論用什麼演算法,都會讓 FF 無法確定。

參考文獻

  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