正規化八點演算法
選讀・DLCV 11・三維重建:從多視角幾何到 NeRF 與 Gaussian Splatting 的補充資料(第 1/7 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。
導覽:本頁與本系列: 導覽:本頁與本系列
這則筆記說明如何用八組或更多配對線性地估計基礎矩陣,以及為什麼要先重新縮放像素座標。
線性系統。 把 寫成向量 。一組配對 、 滿足 ,這是一個線性方程式 ,其中 (全部九個乘積 )。疊起 組配對,得到 ,其中 。滿足 的最小平方解,是 最小奇異值所對應的右奇異向量 [7]、[8]。
秩為 2 的那一步。 真正的基礎矩陣秩為 2(所有對極線都通過同一點,即對極點)。線性解通常秩為 3。用 Frobenius 範數下最接近的秩 2 矩陣取代它:計算 ,再令 [8]。對本質矩陣,兩個非零奇異值還必須相等,所以正文的程式碼才使用 。
為什麼要正規化。 在像素座標中, 的元素大小從約 1 到約 (像素在幾百的範圍時的 )。於是矩陣 的條件很差(見 ML 01c 的條件數),雜訊在小的奇異向量中被放大。Hartley [8] 證明,一個簡單的修正就能讓線性演算法變得有競爭力:平移每張影像的點,使其重心在原點,並縮放使其到原點的平均距離為 ,影像 1 用相似轉換 ,影像 2 用 。在正規化座標中解 ,強制秩為 2,再用 還原正規化。
測試。 這段程式碼在帶雜訊的配對(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 的那一步必須在還原正規化之前進行,而退化的配置(所有點在同一個平面上,或兩台相機之間沒有平移)無論用什麼演算法,都會讓 無法確定。
參考文獻
- 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