Part III · 第 11 章 多视图几何 · 11.1Part III · Ch. 11 Multi-View Geometry · 11.1

对极几何：本质矩阵与基础矩阵Epipolar Geometry: Essential & Fundamental Matrices

只有两张图、没有任何三维模型时，图 1 里的一个像素能告诉你它在图 2 里的位置吗？能：对应点一定落在一条直线（极线）上。这条约束写成矩阵就是本质矩阵 E 与基础矩阵 F，是视觉里程计、运动恢复结构、双目校正和 SLAM 初始化共同的起点。本节从几何画面推出 x₂ᵀEx₁ = 0，在带噪声的匹配上运行真正的 8 点算法，把 E 分解成四组 (R, t) 并用手性（cheirality）检验选出唯一正确的一组，同时看清为什么单目永远不知道尺度、哪些场景会让算法失效。 With only two images and no 3D model, what does one pixel in image 1 tell you about image 2? Its match must lie on a line, the epipolar line. Written as a matrix, that single constraint is the essential matrix E and the fundamental matrix F, the common starting point of visual odometry, structure from motion, stereo rectification and SLAM initialization. We derive x₂ᵀEx₁ = 0 from the geometry, run the real 8-point algorithm on noisy matches, decompose E into four (R, t) candidates and let the cheirality test pick the one correct answer, and see why a single camera never knows scale and which scenes break the algorithm.

约 40 分钟~40 min 前置：1.6 秩与零空间 · 1.8 叉积 · 1.12 SVD · 5.3 SE(3) · 10.1 针孔相机 · 10.2 齐次坐标 · 10.3 内参外参Prereqs: 1.6 Rank & Null Space · 1.8 Cross Product · 1.12 SVD · 5.3 SE(3) · 10.1 Pinhole · 10.2 Homogeneous Coordinates · 10.3 Intrinsics & Extrinsics 5 个交互5 interactives

    1为什么机器人需要它Why robots need this

    一台只有一个摄像头的机器人在走。第 \(t\) 帧和第 \(t+1\) 帧是两张图，它想知道自己在两帧之间怎样运动了（旋转多少、朝哪个方向平移），可是手里没有环境的三维地图，连场景里的东西多远都不知道。能做什么？

    两张图之间有一件事完全不依赖场景长什么样：图 1 的一个像素，只能对应图 2 里的一条直线（极线），而不是整个平面。这是纯几何事实，只要两个相机的相对位姿和内参确定，它就成立。反过来，如果能找到足够多的对应点，让它们都满足这条直线约束，就能解出相对位姿。这就是对极几何，它支撑了：

    • 视觉里程计与 SLAM 的初始化：单目系统用两帧的匹配估计初始运动，再三角化出第一批地图点（11.3 节）。
    • 运动恢复结构 (SfM)：COLMAP 一类的系统，每对图像先做一次两视图几何验证，再拼成整个场景（11.6 节）。
    • 双目与校正：左右图像的对应点在同一行上，是极线平行时的特例（11.2 节）；搜索匹配点从二维变成一维。
    • 鲁棒匹配：极线约束是剔除错误匹配（外点）的主要依据，RANSAC 用 5 点或 8 点的最小求解器（11.5 节）。

    本节只用两张图的 2D–2D 对应点。已知 3D 点时用 PnP（11.4 节）更直接；两视图对应点先给出 \((R,t)\)，再三角化（11.3 节）和整体优化（束调整，11.6 节）把它精化。

    A robot with a single camera is moving. Frame \(t\) and frame \(t+1\) are two images, and it wants to know how it moved between them (how much it rotated, in which direction it translated), but it has no 3D map and does not even know how far away things are. What can it do?

    One fact between two images does not depend on what the scene looks like at all: a pixel in image 1 can only correspond to a line in image 2 (the epipolar line), not to the whole plane. It is pure geometry and holds whenever the relative pose and intrinsics of the two cameras are fixed. Conversely, if you can find enough correspondences that all satisfy this line constraint, you can solve for the relative pose. That is epipolar geometry, and it underlies:

    • Visual odometry and SLAM initialization: a monocular system estimates its first motion from the matches between two frames and then triangulates the first map points (Lesson 11.3).
    • Structure from motion (SfM): systems such as COLMAP verify every image pair with a two-view geometry step before assembling the whole scene (Lesson 11.6).
    • Stereo and rectification: in a rectified pair, matching points lie on the same row, the special case of parallel epipolar lines (Lesson 11.2); the search for a match drops from 2D to 1D.
    • Robust matching: the epipolar constraint is the main test for rejecting wrong matches (outliers); RANSAC uses 5-point or 8-point minimal solvers (Lesson 11.5).

    This lesson uses only 2D–2D correspondences between two images. When 3D points are known, PnP (Lesson 11.4) is more direct; two-view matches first give \((R,t)\), and triangulation (Lesson 11.3) plus global optimization (bundle adjustment, Lesson 11.6) refine it.

    2直觉：一条光线，在另一张图里是一条线Intuition: a ray in one view is a line in the other

    图 1 里的一个像素 \(\mathbf x_1\)，对应相机 1 光心发出的一条光线：光线上所有的三维点都投影到这个像素（10.1 节）。三维点到底在光线的哪里，一张图说不出来，深度丢了。现在让相机 2 看这条光线：光线上不同深度的点，在图 2 里投影成一条直线，这就是极线。因此 \(\mathbf x_1\) 的匹配点必在这条线上，一维的搜索代替了二维。

    几何上的关键对象有四个，都在 FIG 1 里：基线（两个光心的连线）；对极平面（过两个光心和三维点 \(X\) 的平面）；极线（对极平面和图像平面的交线，每张图一条）；极点 \(\mathbf e_1,\mathbf e_2\)（基线与两个图像平面的交点，也就是另一个相机的光心在这张图里的像）。所有极线都经过极点，因为所有对极平面都含有基线。

    FIG 1 里，左下是相机 1 的图像，右下是相机 2 的图像，上面是三维视图。在图 1 里点击或拖动琥珀色的点：三维里出现经过它的光线、对极平面，图 2 里出现对应的极线。用"深度"滑块沿光线移动 \(X\)，图 2 里的像点 \(\mathbf x_2\) 沿极线滑动，并始终在线上。极线的一端是极点 \(\mathbf e_2\)（深度 0，也就是相机 1 的光心），另一端是方框标出的"深度 ∞"点（光线的无穷远端），匹配点必在这两个端点之间。

    A pixel \(\mathbf x_1\) in image 1 corresponds to a ray from camera 1's centre: every 3D point on the ray projects to that pixel (Lesson 10.1). Where on the ray the point really sits, one image cannot say; depth is lost. Now let camera 2 look at that ray: points at different depths along it project to a straight line in image 2, the epipolar line. So the match of \(\mathbf x_1\) must lie on this line, and a 1D search replaces a 2D one.

    Four geometric objects matter, all in FIG 1: the baseline (the line joining the two camera centres); the epipolar plane (the plane through both centres and the 3D point \(X\)); the epipolar lines (the intersections of the epipolar plane with the image planes, one per image); and the epipoles \(\mathbf e_1,\mathbf e_2\) (where the baseline meets the two image planes, i.e. the image of the other camera's centre). All epipolar lines pass through the epipole because every epipolar plane contains the baseline.

    In FIG 1, the lower left is camera 1's image, the lower right camera 2's image, and the top is the 3D view. Click or drag the amber dot in image 1: the ray through it and the epipolar plane appear in 3D, and the matching epipolar line appears in image 2. Slide X along the ray with the "depth" slider: its image \(\mathbf x_2\) slides along the epipolar line and never leaves it. One end of the line is the epipole \(\mathbf e_2\) (depth 0, which is camera 1's centre), the other end is the square marked "depth ∞" (the far end of the ray); the match must lie between these two ends.

    FIG 1两个视图与一条光线Two views and a ray
    三维视图：拖动旋转3D view: drag to orbit
    预设位姿Preset poses
    相机 1（青）固定，相机 2（紫）的位姿由滑块给出，量取在相机 1 的坐标系里（x 右，y 下，z 前）。琥珀色：像素 \(\mathbf x_1\)、它的光线、点 \(X\) 与极线。青色半透明平行四边形是对极平面；绿色圆环是极点（在相机后方时标签注明"在相机后"，在画面外时画成指向它的箭头，并标出坐标）。图像坐标 \((u,v)\)，\(v\) 向下，画面里用 \(y=-v\) 绘制，左上角的小箭头标出方向。图 1 里的虚线是对极平面与图 1 的交线：它经过 \(\mathbf e_1\) 和 \(\mathbf x_1\)。读数里的距离是 \(\mathbf x_2\) 到 \(\mathbf l_2=F\tilde{\mathbf x}_1\) 的距离，应为 \(10^{-13}\) 量级。 Camera 1 (cyan) is fixed; camera 2 (purple) has its pose set by the sliders, measured in camera 1's frame (x right, y down, z forward). Amber: the pixel \(\mathbf x_1\), its ray, the point \(X\) and the epipolar line. The translucent cyan parallelogram is the epipolar plane; green rings are the epipoles (labelled "behind" when behind the camera, an arrow pointing at it with its coordinates when outside the picture). Image coordinates are \((u,v)\) with \(v\) down, drawn as \(y=-v\); the small arrows in the top-left corner show the directions. The dashed line in image 1 is the intersection of the epipolar plane with image 1: it passes through \(\mathbf e_1\) and \(\mathbf x_1\). The distance in the readout is that of \(\mathbf x_2\) from \(\mathbf l_2=F\tilde{\mathbf x}_1\), which should be about \(10^{-13}\).
    试一试Try this
    • 拖动"深度 Z"滑块，让深度改变 1.5 m 以上。图 2 里的 \(\mathbf x_2\) 沿着极线滑动，端点分别是什么？为什么单张图看不出深度？Drag the "depth Z" slider by more than 1.5 m. Watch \(\mathbf x_2\) slide along the epipolar line: what are its two end points, and why can one image not tell depth?
    • 点"平行并排"预设：基线平行于两个像平面，极点跑到无穷远，所有极线平行（水平线）。这就是校正后双目（11.2 节）的构型：匹配点在同一行上。Press the "Side by side" preset: the baseline is parallel to both image planes, the epipoles go to infinity and all epipolar lines are parallel (horizontal). This is the rectified-stereo configuration (Lesson 11.2): matches lie on the same row.
    • 点"向前走"预设（或令 \(t_z>0.5\) m、\(t_x\) 很小）：极点 \(\mathbf e_1\) 落进图 1 里，极线从它向四周辐射。这是机器人向前行驶时看到的"光流扩张点"（focus of expansion）。Press "Move forward" (or make \(t_z>0.5\) m with a small \(t_x\)): the epipole \(\mathbf e_1\) falls inside image 1 and the epipolar lines radiate from it. This is the "focus of expansion" a forward-driving robot sees.
    • 把三个平移滑块都拖到 0。极线消失了，读数提示 \(E=0\)。没有基线就没有对极几何：纯旋转的相机只改变视线方向，不提供任何深度信息（见后面的退化情形）。Drag all three translation sliders to 0. The epipolar line vanishes and the readout says \(E=0\). No baseline, no epipolar geometry: a purely rotating camera only changes its viewing direction and gives no depth information (see the degenerate cases below).
    约定（本节全部遵守）Convention (used throughout this lesson)

    以相机 1 的坐标系为参考。同一个三维点在两个相机坐标系里的坐标满足 \(\mathbf X_2=R\,\mathbf X_1+\mathbf t\)，也就是 \((R,\mathbf t)\) 是从相机 1 系到相机 2 系的变换 \({}^{2}T_{1}\)（5.3 节，OpenCV 的 recoverPose 同此约定）。相机 2 的光心在相机 1 系里是 \(\mathbf C_2=-R^{\top}\mathbf t\)，相机 2 的位姿是 \({}^{1}T_{2}=(R^{\top},\,-R^{\top}\mathbf t)\)。注意 \(\mathbf t\) 不是相机 2 的位置，而是相机 1 光心在相机 2 坐标系里的坐标。两个相机坐标系都是 OpenCV 光学系（x 右，y 下，z 前）。

    Take camera 1's frame as the reference. The coordinates of one 3D point in the two camera frames satisfy \(\mathbf X_2=R\,\mathbf X_1+\mathbf t\); that is, \((R,\mathbf t)\) is the transform \({}^{2}T_{1}\) from camera 1's frame to camera 2's frame (Lesson 5.3; OpenCV's recoverPose uses the same convention). Camera 2's centre in camera 1's frame is \(\mathbf C_2=-R^{\top}\mathbf t\), and its pose is \({}^{1}T_{2}=(R^{\top},\,-R^{\top}\mathbf t)\). Note that \(\mathbf t\) is not camera 2's position: it is the coordinates of camera 1's centre in camera 2's frame. Both camera frames are OpenCV optical frames (x right, y down, z forward).

    3动手玩：推出本质矩阵 EPlay: deriving the essential matrix E

    极线怎么算？把 FIG 1 里的几何翻译成代数。在相机 2 的坐标系里看（FIG 2）：相机 2 的光心 \(O\) 在原点，相机 1 的光心在 \(\mathbf t\)，三维点 \(X\) 的位置有两种写法。从相机 2 直接看：\(\mathbf X_2=\lambda_2\hat{\mathbf x}_2\)，\(\hat{\mathbf x}_2\) 是像素的归一化坐标（\(\hat{\mathbf x}=K^{-1}\tilde{\mathbf x}=(x,y,1)\)，10.3 节），\(\lambda_2\) 是深度；从相机 1 走过去：先到 \(\mathbf t\)，再沿相机 1 的光线走 \(\lambda_1 R\hat{\mathbf x}_1\)（光线方向 \(\hat{\mathbf x}_1\) 要用 \(R\) 转到相机 2 的坐标轴上）。两种走法到同一点，三个向量形成一个闭合三角形：

    How do we compute the epipolar line? Translate the geometry of FIG 1 into algebra. Work in camera 2's frame (FIG 2): camera 2's centre \(O\) is at the origin, camera 1's centre is at \(\mathbf t\), and the 3D point \(X\) can be reached in two ways. Straight from camera 2: \(\mathbf X_2=\lambda_2\hat{\mathbf x}_2\), where \(\hat{\mathbf x}_2\) is the pixel's normalized coordinate (\(\hat{\mathbf x}=K^{-1}\tilde{\mathbf x}=(x,y,1)\), Lesson 10.3) and \(\lambda_2\) is the depth. Via camera 1: first go to \(\mathbf t\), then along camera 1's ray, \(\lambda_1 R\hat{\mathbf x}_1\) (the ray direction \(\hat{\mathbf x}_1\) must be rotated by \(R\) onto camera 2's axes). Both routes reach the same point, so the three vectors form a closed triangle:

    $$ \hl{ray2}{\lambda_2\hat{\mathbf x}_2}\;=\;\hl{ray1}{\lambda_1 R\hat{\mathbf x}_1}\;+\;\hl{base}{\mathbf t}. $$

    三个向量首尾相接，所以它们在同一个平面里（对极平面）。三个向量共面等价于混合积为零：\(\hat{\mathbf x}_2\cdot(\mathbf t\times R\hat{\mathbf x}_1)=0\)。叉积是线性的，可以写成矩阵（1.8 节）：\(\mathbf t\times\mathbf v=[\mathbf t]_\times\mathbf v\)。于是

    Three vectors laid head to tail lie in one plane, the epipolar plane. Coplanar vectors have a vanishing triple product: \(\hat{\mathbf x}_2\cdot(\mathbf t\times R\hat{\mathbf x}_1)=0\). The cross product is linear and can be written as a matrix (Lesson 1.8): \(\mathbf t\times\mathbf v=[\mathbf t]_\times\mathbf v\). Therefore

    $$ \hat{\mathbf x}_2^{\top}\,\hl{E}{E}\,\hat{\mathbf x}_1=0,\qquad \hl{E}{E}=[\mathbf t]_\times R,\qquad [\mathbf t]_\times=\begin{bmatrix}0&-t_z&t_y\\ t_z&0&-t_x\\ -t_y&t_x&0\end{bmatrix}. $$

    \(E\) 叫本质矩阵 (essential matrix)，只含相对位姿 \((R,\mathbf t)\)，不含内参。把 \(\hat{\mathbf x}=K^{-1}\tilde{\mathbf x}\) 代回去，对像素坐标就是 \(\tilde{\mathbf x}_2^{\top}F\tilde{\mathbf x}_1=0\)，\(F=K_2^{-\top}EK_1^{-1}\)，基础矩阵 (fundamental matrix)。\(F\tilde{\mathbf x}_1\) 就是图 2 里那条极线的系数 \((a,b,c)\)：\(au+bv+c=0\)。FIG 2 把上面五步依次演示出来，数值检验是真实计算：同一个匹配的 \(\hat{\mathbf x}_2^{\top}E\hat{\mathbf x}_1\) 在 \(10^{-16}\) 量级。

    \(E\) is the essential matrix: it contains only the relative pose \((R,\mathbf t)\) and no intrinsics. Substituting \(\hat{\mathbf x}=K^{-1}\tilde{\mathbf x}\) back gives the pixel-space version \(\tilde{\mathbf x}_2^{\top}F\tilde{\mathbf x}_1=0\) with \(F=K_2^{-\top}EK_1^{-1}\), the fundamental matrix. \(F\tilde{\mathbf x}_1\) is exactly the coefficient vector \((a,b,c)\) of the epipolar line \(au+bv+c=0\) in image 2. FIG 2 steps through the five stages; the numerical checks are real computations: \(\hat{\mathbf x}_2^{\top}E\hat{\mathbf x}_1\) for the same match is at the \(10^{-16}\) level.

    FIG 2推导 E：从共面到矩阵Deriving E: from coplanarity to a matrix
    相机 2 坐标系 · 拖动旋转camera-2 frame · drag to orbit
    按钮 1–5 逐步推进。画面是以相机 2 为参考的三维视图（相机 2 的坐标轴在原点，相机 1 的坐标轴在 \(\mathbf t\)，朝向由 \(R\) 的各列给出）。琥珀箭头 \(\mathbf t\)，蓝箭头 \(\lambda_1R\hat{\mathbf x}_1\)，紫箭头 \(\lambda_2\hat{\mathbf x}_2\) 构成闭合三角形；第 3 步起显示对极平面和它的法向 \(\mathbf n=\mathbf t\times R\hat{\mathbf x}_1\)，\(\hat{\mathbf x}_2\perp\mathbf n\) 就是混合积为零。右侧读数全部由当前位姿和匹配点真实算出；E 的奇异值是 \((\|\mathbf t\|,\|\mathbf t\|,0)\)，F 的秩为 2。悬停公式里带底色的向量，对应的箭头加粗。 Buttons 1–5 step through the derivation. The view is 3D in camera 2's frame (camera 2's axes at the origin, camera 1's axes at \(\mathbf t\), oriented by the columns of \(R\)). The amber arrow \(\mathbf t\), blue arrow \(\lambda_1R\hat{\mathbf x}_1\) and purple arrow \(\lambda_2\hat{\mathbf x}_2\) form a closed triangle; from stage 3 on the epipolar plane and its normal \(\mathbf n=\mathbf t\times R\hat{\mathbf x}_1\) are shown, and \(\hat{\mathbf x}_2\perp\mathbf n\) is the vanishing triple product. Every number on the right is computed from the current pose and match; the singular values of E are \((\|\mathbf t\|,\|\mathbf t\|,0)\) and F has rank 2. Hover the highlighted vectors in the formulas to thicken the matching arrows.
    试一试Try this
    • 依次点到第 5 步。换几个匹配点和随机位姿：\(\hat{\mathbf x}_2^{\top}E\hat{\mathbf x}_1\) 每次都是 \(10^{-16}\) 量级，E 的前两个奇异值总是相等，且等于 \(\|\mathbf t\|\)。Step to stage 5. Try other matches and random poses: \(\hat{\mathbf x}_2^{\top}E\hat{\mathbf x}_1\) is always at the \(10^{-16}\) level, E's two largest singular values are always equal, and they equal \(\|\mathbf t\|\).
    核心洞见Key insight

    对每一对匹配，\(\tilde{\mathbf x}_2^{\top}F\tilde{\mathbf x}_1=0\) 是关于 \(F\) 的 9 个元素的一个线性方程。\(F\) 里藏着相对位姿和内参，却不需要知道任何三维点：方程里没有深度 \(\lambda\)。线性意味着可以直接用 SVD 求解（1.12 节），这就是 8 点算法。

    For each match, \(\tilde{\mathbf x}_2^{\top}F\tilde{\mathbf x}_1=0\) is one linear equation in the nine entries of \(F\). \(F\) hides the relative pose and the intrinsics, yet no 3D point is needed: the depths \(\lambda\) have dropped out. Linear means we can solve it directly with the SVD (Lesson 1.12): that is the 8-point algorithm.

    E 与 F 有多少自由度？How many degrees of freedom do E and F have?

    E：5 个。旋转 \(R\) 3 个，平移 \(\mathbf t\) 只剩方向 2 个：对极方程两边乘任何常数仍成立，所以 \(\|\mathbf t\|\) 不可观（尺度模糊，见 FIG 4）。从矩阵角度数：9 个元素减 1（整体尺度），减 1（\(\det E=0\)，秩 2），再减 2（两个非零奇异值相等），\(9-1-1-2=5\)。F：7 个。\(F\) 只有"整体尺度"和"秩 2"两个限制，\(9-1-1=7\)，它不要求奇异值相等，因为内参 \(K_1,K_2\) 把这条性质破坏了。所以 \(E\) 比 \(F\) 少 2 个自由度，等于已知内参带来的信息。

    E: 5. The rotation \(R\) contributes 3 and the translation \(\mathbf t\) only its direction, 2: the epipolar equation stays true if you multiply \(\mathbf t\) by any constant, so \(\|\mathbf t\|\) is unobservable (scale ambiguity, see FIG 4). Counting from the matrix: 9 entries, minus 1 (overall scale), minus 1 (\(\det E=0\), rank 2), minus 2 (the two nonzero singular values are equal): \(9-1-1-2=5\). F: 7. \(F\) only has "overall scale" and "rank 2", \(9-1-1=7\); it does not require equal singular values because the intrinsics \(K_1,K_2\) destroy that property. So \(E\) has 2 fewer degrees of freedom than \(F\), exactly the information bought by knowing the intrinsics.

    4第二、第三视角：估计 F，再恢复运动Second and third views: estimating F, then recovering motion

    从带噪声的匹配估计 F：8 点算法Estimating F from noisy matches: the 8-point algorithm

    真实系统拿到的不是 \(E\) 或 \(F\)，而是一堆带噪声的匹配点（特征检测与匹配，11.5 节）。每对匹配给出一个线性方程 \(\mathbf a_i^{\top}\mathbf f=0\)，其中 \(\mathbf f\) 是 \(F\) 的 9 个元素排成的向量。叠起 \(N\ge8\) 个方程得到 \(A\mathbf f=0\)，要在 \(\|\mathbf f\|=1\) 下最小化 \(\|A\mathbf f\|\)：解是 \(A\) 的最小右奇异向量（1.6 节的零空间，1.12 节的 SVD）。最后还要把 \(F\) 投影到秩 2：令最小奇异值为 0。

    FIG 3 运行的就是这个算法，用的是真实代码，不是动画。场景是固定的（相机 2 向前并稍向右移动），匹配点加上高斯像素噪声。紫线是估计的极线，绿线是真值极线，琥珀圆点是真实的匹配点。度量"估计得好不好"有两种数：用来拟合的点上的 Sampson 误差（小不代表好），以及留出的、没参与拟合的 80 个点上的对极距离（这才是泛化误差）。试着体会：N 很小时拟合误差接近零，留出误差却很大——算法在"背"噪声。

    A real system does not receive \(E\) or \(F\) but a pile of noisy matches (feature detection and matching, Lesson 11.5). Each match gives a linear equation \(\mathbf a_i^{\top}\mathbf f=0\), where \(\mathbf f\) stacks the nine entries of \(F\). Stacking \(N\ge8\) of them gives \(A\mathbf f=0\); minimize \(\|A\mathbf f\|\) under \(\|\mathbf f\|=1\): the solution is the smallest right singular vector of \(A\) (the null space of Lesson 1.6, the SVD of Lesson 1.12). Finally project \(F\) to rank 2 by zeroing its smallest singular value.

    FIG 3 runs exactly this algorithm with real code, not an animation. The scene is fixed (camera 2 moved forward and slightly right) and the matches get Gaussian pixel noise. Purple lines are the estimated epipolar lines, green lines the true ones, amber dots the true matches. There are two ways to score the result: the Sampson error on the points used for fitting (small does not mean good) and the epipolar distance on 80 held-out points that did not take part in the fit (the real generalization error). Watch for it: with few matches the fit error is almost zero while the held-out error is large; the algorithm is memorizing the noise.

    FIG 38 点算法实验室8-point algorithm lab
    左：图 2。青色小点是用于拟合的匹配点（带噪声），8 条绿线与 8 个琥珀点是留出点的真值极线与真匹配，紫线是估计的 F̂ 给出的极线；绿圈是真极点，紫圈是估计的极点。强制秩 2 时，紫线严格共点于紫圈；关掉后它们不再严格共点（匹配少、噪声大时最明显）。右：留出误差随噪声变化，红线不归一化，绿线 Hartley 归一化（各取 10 次噪声重抽的中位数，粗线是当前设置）。读数里的 σ₇ σ₈ σ₉ 是（归一化后）矩阵 A 最小的三个奇异值：一般场景只有 σ₉ 很小，退化场景有三个很小。虚拟相机 1280×960 像素，焦距 1040 px，场景深度 4.5–8 m。 Left: image 2. Small cyan dots are the (noisy) matches used for fitting; 8 green lines and 8 amber dots are the held-out points' true epipolar lines and true matches; purple lines are those from the estimate F̂. The green ring is the true epipole, the purple ring the estimated one. With rank 2 enforced, the purple lines meet exactly at the purple ring; with it off they no longer meet exactly (most visible with few matches and large noise). Right: held-out error against noise, red without normalization and green with Hartley normalization (median of 10 noise draws each; the thick curve is the current setting). σ₇ σ₈ σ₉ in the readout are the smallest three singular values of the (normalized) matrix A: a general scene has only σ₉ small, a degenerate one has three small ones. The virtual camera is 1280×960 px with focal length 1040 px; scene depth is 4.5–8 m.
    试一试Try this
    • 把 N 拉到 8–10，噪声 \(\sigma\ge0.5\) px：拟合误差只和噪声同量级，留出误差却是它的两倍以上。8 个方程恰好解出 8 个自由度，噪声没有被平均掉。再把 N 加到 100，留出误差降下来。Set N to 8–10 with noise \(\sigma\ge0.5\) px: the fit error is only about the noise level, yet the held-out error is more than twice that. Eight equations pin down exactly eight unknowns, so the noise is never averaged out. Raise N to 100 and the held-out error drops.
    • 取 \(\sigma\ge1.5\)、\(N\ge15\)，把"归一化"关掉：误差明显更大，至少是归一化的 1.5 倍，换几次噪声常常是好几倍（读数给出同一份数据归一化后的结果，右图红线远高于绿线）。像素坐标的量级差太大（\(uu'\sim10^6\)，常数项 1），SVD 的最小二乘被大数淹没。Take \(\sigma\ge1.5\), \(N\ge15\) and switch "normalize" off: the error is clearly larger, at least 1.5× the normalized one and often several times it over a few noise draws (the readout gives the normalized result on the same data and the red curve sits far above the green one). Pixel coordinates have wildly different magnitudes (\(uu'\sim10^6\) against a constant 1), so the SVD's least squares is swamped by the big entries.
    • 把"强制秩 2"关掉：紫线不再严格共点（N 小、噪声大时最明显），读数里 \(\hat F\) 的 σ₃/σ₁ 从 \(10^{-17}\) 变成非零。误差数值变化不大，但没有严格的极点，E 的分解（FIG 4）就缺了依据。Switch "enforce rank 2" off: the purple lines no longer meet exactly at one point (most visible with N near 8 and larger noise) and \(\hat F\)'s σ₃/σ₁ in the readout goes from \(10^{-17}\) to nonzero. The error number barely changes, but without an exact epipole the decomposition of E (FIG 4) has nothing to stand on.
    • 切到"平面场景"（取 \(N\ge20\)）：σ₇ σ₈ σ₉ 三个同样小，σ₈/σ₉ 约为 1，F 在一个三维族里随噪声乱跳，留出误差变得很大，极点位置也不稳定。再试"纯旋转"：同样的症状，因为没有基线。Switch to "planar scene" (with \(N\ge20\)): σ₇ σ₈ σ₉ are all equally small, σ₈/σ₉ is about 1, F wanders through a 3-dimensional family with the noise, the held-out error gets large and the epipole is unstable. Then try "pure rotation": the same symptoms, because there is no baseline.

    从 E 恢复运动：四个解与手性检验Recovering motion from E: four solutions and the cheirality test

    有了 \(E\)（已知内参时，用归一化坐标直接估计，或 \(E=K_2^{\top}FK_1\)），就可以拆出 \((R,\mathbf t)\)。对 \(E\) 做 SVD，\(E=U\,\mathrm{diag}(\sigma,\sigma,0)\,V^{\top}\)，\(\mathbf t\) 是 \(E\) 的左零向量 \(\mathbf u_3\)，只确定到正负号和尺度；旋转有两个解 \(UWV^{\top}\) 与 \(UW^{\top}V^{\top}\)（\(W\) 是绕 z 轴转 90° 的矩阵）。符号 × 两个旋转共 4 个候选。其中两个旋转差了一个绕基线的 180° 转动，称为"孪生对"(twisted pair)。

    数据本身不分辨它们：对极方程对 \(\pm\mathbf t\)、对两种旋转都成立。真正区分的是物理常识：被拍到的点必须在两个相机的前面。对每个候选，把匹配三角化得到深度 \((\lambda_1,\lambda_2)\)，只有一个候选让两个深度都为正。这叫手性检验 (cheirality)。FIG 4 里相机 1（灰）在原点，四种颜色是四个候选的相机 2，每个候选各自"重建"了所有匹配点（小点），选定的一对匹配画成大点，边缘绿色表示在两个相机前面，红色表示不在。灰色的淡相机是真值。

    Given \(E\) (estimated directly in normalized coordinates when the intrinsics are known, or \(E=K_2^{\top}FK_1\)), we can pull out \((R,\mathbf t)\). Take the SVD \(E=U\,\mathrm{diag}(\sigma,\sigma,0)\,V^{\top}\); \(\mathbf t\) is the left null vector \(\mathbf u_3\) of \(E\), determined only up to sign and scale; the rotation has two solutions, \(UWV^{\top}\) and \(UW^{\top}V^{\top}\) (\(W\) is the 90° rotation about z). Sign times rotation gives 4 candidates. The two rotations differ by a 180° turn about the baseline, a "twisted pair".

    The data cannot tell them apart: the epipolar equation holds for \(\pm\mathbf t\) and for both rotations. What distinguishes them is common sense: an observed point must lie in front of both cameras. For each candidate triangulate the matches to get depths \((\lambda_1,\lambda_2)\); only one candidate makes both depths positive. This is the cheirality test. In FIG 4 camera 1 (grey) is at the origin and the four colours are camera 2 under each candidate; every candidate "reconstructs" all matches (small dots), and the selected match is the big dot, with a green rim if it is in front of both cameras and a red rim if not. The faint grey camera is the ground truth.

    FIG 4分解 E：四个候选与手性检验Decomposing E: four candidates and the cheirality test
    以 ‖t‖ = 1 为单位 · 拖动旋转units of ‖t‖ = 1 · drag to orbit
    E 由 \(N\) 个带噪声的匹配用 8 点算法估计（归一化坐标，奇异值强制为 \((\sigma,\sigma,0)\)），再用 SVD 分解出四个候选。右侧表格第三列是"同时在两个相机前方的点数 / N"，唯一满 N 的就是正确候选（粗体加 ✓ 是投票选中的）。读数里的百分比是 100 次独立噪声重抽中选对的比例；噪声大、匹配少时它会下降。最后一个滑块把整个世界（场景和基线）一起放大 s 倍：所有像素坐标不变（最大变化约 \(10^{-13}\) px），估计出的 \(\|\hat{\mathbf t}\|\) 永远是 1。 E is estimated from \(N\) noisy matches with the 8-point algorithm (normalized coordinates, singular values forced to \((\sigma,\sigma,0)\)) and decomposed by SVD into four candidates. The third column of the table is "points in front of both cameras / N"; only one candidate reaches N and it is the correct one (bold with ✓ is the one the vote picked). The percentage in the readout is the share of 100 independent noise draws in which the vote picks the right candidate; it drops with heavy noise or few matches. The last slider enlarges the whole world (scene and baseline together) by a factor s: every pixel coordinate stays the same (the maximal change is about \(10^{-13}\) px) and the estimated \(\|\hat{\mathbf t}\|\) is always 1.
    试一试Try this
    • 点"候选 1…4"逐个聚焦（其余变淡），找到那个被投票选中且就是真值的候选：它的大点在两个相机前面，边缘是绿色；另外三个，点要么在相机 1 后面，要么在相机 2 后面。Focus on candidates 1…4 one by one (the others fade) and find the one that the vote picks and that is the ground truth: its big dot is in front of both cameras with a green rim; for the other three the dot is behind camera 1, behind camera 2, or both.
    • 把尺度 s 拉到 3 以上（或 0.33 以下）：真实基线变成 \(s\) 倍，场景大了又大，像素读数一点不变，重建的三维图形也没动。单目只能恢复到相似变换，没有米。Drag the scale s above 3 (or below 0.33): the true baseline becomes \(s\) times as long and the scene balloons, yet the pixel readout does not change and the reconstructed 3D picture does not move. A single camera recovers the world only up to similarity: there are no metres.
    同一个约束的三种说法Three phrasings of one constraint

    几何：\(\mathbf x_1\)、\(\mathbf x_2\) 与两个光心构成的对极平面含基线，等价于两条光线共面。代数：\(\tilde{\mathbf x}_2^{\top}F\tilde{\mathbf x}_1=0\)，对 \(F\) 线性，\(F\tilde{\mathbf x}_1\) 就是极线。射影：\(F=[\mathbf e_2]_\times H_\infty\)，其中 \(H_\infty=K_2RK_1^{-1}\) 把图 1 的点按"深度无穷远"搬到图 2（FIG 1 里的方框）。极线是连接 \(\mathbf e_2\)（深度 0）与 \(H_\infty\tilde{\mathbf x}_1\)（深度 ∞）的直线：\(\mathbf l_2=\mathbf e_2\times H_\infty\tilde{\mathbf x}_1\)。把 \(H_\infty\) 换成由任何一个平面诱导的单应 \(H_\pi\)，公式依然成立（10.5 节）。

    Geometric: \(\mathbf x_1\), \(\mathbf x_2\) and the two centres span an epipolar plane that contains the baseline; equivalently, the two rays are coplanar. Algebraic: \(\tilde{\mathbf x}_2^{\top}F\tilde{\mathbf x}_1=0\), linear in \(F\), and \(F\tilde{\mathbf x}_1\) is the epipolar line. Projective: \(F=[\mathbf e_2]_\times H_\infty\) with \(H_\infty=K_2RK_1^{-1}\), which carries a point of image 1 to image 2 "at infinite depth" (the square in FIG 1). The epipolar line joins \(\mathbf e_2\) (depth 0) and \(H_\infty\tilde{\mathbf x}_1\) (depth ∞): \(\mathbf l_2=\mathbf e_2\times H_\infty\tilde{\mathbf x}_1\). Replace \(H_\infty\) by the homography \(H_\pi\) induced by any plane and the formula still holds (Lesson 10.5).

    5再看数学The math

    提示：把鼠标悬停在公式中带底色的符号上，FIG 1 或 FIG 2 中对应的元素会被高亮。Tip: hover the highlighted symbols in the formulas; the matching element in FIG 1 or FIG 2 lights up.

    对极约束、E 与 FThe epipolar constraint, E and F

    设 \(\mathbf X_2=R\mathbf X_1+\mathbf t\)，像素 \(\tilde{\mathbf x}_i=K_i\hat{\mathbf x}_i\)。把第 3 节（FIG 2）的推导再写一遍，并用 \(\mathbf t\times\mathbf v=[\mathbf t]_\times\mathbf v\)：

    Let \(\mathbf X_2=R\mathbf X_1+\mathbf t\) and pixels \(\tilde{\mathbf x}_i=K_i\hat{\mathbf x}_i\). Repeating the derivation of FIG 2 with \(\mathbf t\times\mathbf v=[\mathbf t]_\times\mathbf v\):

    $$ \begin{aligned}\lambda_2\hat{\mathbf x}_2&=\lambda_1R\hat{\mathbf x}_1+\mathbf t \ \xrightarrow{\ \times\mathbf t\ }\ \lambda_2[\mathbf t]_\times\hat{\mathbf x}_2=\lambda_1[\mathbf t]_\times R\hat{\mathbf x}_1 \\ &\xrightarrow{\ \hat{\mathbf x}_2^{\top}\cdot\ }\ \boxed{\hat{\mathbf x}_2^{\top}\hl{E}{E}\,\hat{\mathbf x}_1=0,\ \ E=[\mathbf t]_\times R}\\[4pt] &\text{pixels: }\ \boxed{\tilde{\mathbf x}_2^{\top}F\tilde{\mathbf x}_1=0,\ \ F=K_2^{-\top}EK_1^{-1}}\end{aligned} $$

    （第二步用了 \(\hat{\mathbf x}_2^{\top}[\mathbf t]_\times\hat{\mathbf x}_2=0\)：向量与自己的叉积垂直于自己。）极线、极点与它们的性质：

    (The second step uses \(\hat{\mathbf x}_2^{\top}[\mathbf t]_\times\hat{\mathbf x}_2=0\): a vector is perpendicular to its cross product with anything.) The epipolar lines, the epipoles and their properties:

    $$ \begin{aligned}\hl{line}{\mathbf l_2}&=F\tilde{\mathbf x}_1,\quad \mathbf l_1=F^{\top}\tilde{\mathbf x}_2\\ \hl{epi}{\mathbf e_2}&=K_2\,\hl{base}{\mathbf t},\quad \mathbf e_1=-K_1R^{\top}\mathbf t=K_1\mathbf C_2\\ F\mathbf e_1&=\mathbf 0,\quad F^{\top}\mathbf e_2=\mathbf 0\end{aligned} $$

    \(F\mathbf e_1=K_2^{-\top}[\mathbf t]_\times R\,K_1^{-1}K_1(-R^{\top}\mathbf t)=-K_2^{-\top}[\mathbf t]_\times\mathbf t=\mathbf 0\)，因此 \(F\) 一定有零空间，秩 ≤ 2，极点就是它的左、右零向量，\(\det F=0\)。线 \(\mathbf l\) 与点 \(\mathbf x\) 的关系是 \(\mathbf l^{\top}\mathbf x=0\)（10.2 节的点线对偶）。下面把 \(E\) 与 \(F\) 并排：

    \(F\mathbf e_1=K_2^{-\top}[\mathbf t]_\times R\,K_1^{-1}K_1(-R^{\top}\mathbf t)=-K_2^{-\top}[\mathbf t]_\times\mathbf t=\mathbf 0\), so \(F\) always has a null space: rank ≤ 2, the epipoles are its left and right null vectors, and \(\det F=0\). A line \(\mathbf l\) and a point \(\mathbf x\) are incident when \(\mathbf l^{\top}\mathbf x=0\) (the point–line duality of Lesson 10.2). Side by side:

    本质矩阵 \(E\)Essential matrix \(E\)基础矩阵 \(F\)Fundamental matrix \(F\)
    作用的坐标Coordinates归一化坐标 \(\hat{\mathbf x}=K^{-1}\tilde{\mathbf x}\)（需要内参）normalized \(\hat{\mathbf x}=K^{-1}\tilde{\mathbf x}\) (needs the intrinsics)像素坐标（不需要内参）pixels (no intrinsics needed)
    自由度DoF57
    约束Constraints秩 2，且两个非零奇异值相等 (Huang–Faugeras)rank 2 and two equal nonzero singular values (Huang–Faugeras)只有秩 2：\(\det F=0\)rank 2 only: \(\det F=0\)
    能给出Yields\((R,\mathbf t/\|\mathbf t\|)\)，4 个候选\((R,\mathbf t/\|\mathbf t\|)\), 4 candidates极线、极点；射影重建，没有度量epipolar lines and epipoles; projective reconstruction, no metric
    最小求解器Minimal solver5 点 (Nistér)，最多 10 个解5-point (Nistér), up to 10 solutions7 点，最多 3 个解；线性 8 点7-point, up to 3 solutions; linear 8-point

    8 点算法The 8-point algorithm

    把 \(\tilde{\mathbf x}_2^{\top}F\tilde{\mathbf x}_1=\sum_{ij}\tilde x_{2,i}F_{ij}\tilde x_{1,j}\) 按行展开成内积，第 \(i\) 对匹配 \((u_i,v_i)\to(u_i',v_i')\) 给出一个方程：

    Expanding \(\tilde{\mathbf x}_2^{\top}F\tilde{\mathbf x}_1=\sum_{ij}\tilde x_{2,i}F_{ij}\tilde x_{1,j}\) row by row as a dot product, the \(i\)-th match \((u_i,v_i)\to(u_i',v_i')\) gives one equation:

    $$ \begin{aligned}\mathbf a_i^{\top}\mathbf f&=0,\quad \mathbf a_i=\tilde{\mathbf x}_{2,i}\otimes\tilde{\mathbf x}_{1,i}=(u'u,\ u'v,\ u',\ v'u,\ v'v,\ v',\ u,\ v,\ 1)\\ \mathbf f&=(F_{11},F_{12},\dots,F_{33}),\\ A&=\begin{bmatrix}\mathbf a_1^{\top}\\ \vdots\\ \mathbf a_N^{\top}\end{bmatrix},\qquad \hat{\mathbf f}=\arg\min_{\|\mathbf f\|=1}\|A\mathbf f\|=\mathbf v_9\end{aligned} $$

    \(\mathbf v_9\) 是 \(A=U\Sigma V^{\top}\) 的最后一列右奇异向量（1.12、1.13 节）。步骤：①Hartley 归一化：对每张图的点做平移和缩放，使质心在原点、到原点的平均距离是 \(\sqrt2\)，即 \(\mathbf x\mapsto T\mathbf x\)；②在归一化点上建 \(A\)，取 \(\mathbf v_9\) 排成 \(\hat F\)；③强制秩 2：\(\hat F=U\,\mathrm{diag}(s_1,s_2,s_3)\,V^{\top}\to U\,\mathrm{diag}(s_1,s_2,0)\,V^{\top}\)（Frobenius 范数下最近的秩 2 矩阵，Eckart–Young）；④去归一化：\(F=T_2^{\top}\hat FT_1\)。第①步看似是小技巧，实则关键：像素坐标下 \(A\) 的列有 \(10^6\)、\(10^3\)、\(1\) 三种量级，条件数极大；归一化后各列同量级。Hartley（1997）的结论是，这样的 8 点算法与迭代算法精度相当，而且简单得多（FIG 3 的红绿线）。若直接估计 \(E\)，把第③步换成"最近的本质矩阵"：奇异值替换为 \((\tfrac{s_1+s_2}2,\tfrac{s_1+s_2}2,0)\)。

    \(\mathbf v_9\) is the last right singular vector of \(A=U\Sigma V^{\top}\) (Lessons 1.12 and 1.13). The steps: (1) Hartley normalization: translate and scale the points of each image so the centroid is at the origin and the mean distance to it is \(\sqrt2\), \(\mathbf x\mapsto T\mathbf x\); (2) build \(A\) from the normalized points and reshape \(\mathbf v_9\) into \(\hat F\); (3) enforce rank 2: \(\hat F=U\,\mathrm{diag}(s_1,s_2,s_3)\,V^{\top}\to U\,\mathrm{diag}(s_1,s_2,0)\,V^{\top}\) (the nearest rank-2 matrix in the Frobenius norm, Eckart–Young); (4) denormalize: \(F=T_2^{\top}\hat FT_1\). Step 1 looks like a trick but is essential: with pixel coordinates the columns of \(A\) have magnitudes \(10^6\), \(10^3\) and \(1\), a huge condition number; after normalization all columns are comparable. Hartley (1997) showed that the normalized 8-point algorithm is about as accurate as iterative methods and much simpler (the red and green curves in FIG 3). To estimate \(E\) directly, replace step 3 by "nearest essential matrix": singular values become \((\tfrac{s_1+s_2}2,\tfrac{s_1+s_2}2,0)\).

    从 E 到 (R, t)，以及手性检验From E to (R, t), and the cheirality test

    令 \(E=U\,\mathrm{diag}(\sigma,\sigma,0)\,V^{\top}\)，必要时把 \(U,V\) 的第三列变号使 \(\det U=\det V=+1\)。取 \(W=\begin{bmatrix}0&-1&0\\1&0&0\\0&0&1\end{bmatrix}\)：

    Let \(E=U\,\mathrm{diag}(\sigma,\sigma,0)\,V^{\top}\), flipping the sign of the third columns of \(U\) and \(V\) if needed so that \(\det U=\det V=+1\). With \(W=\begin{bmatrix}0&-1&0\\1&0&0\\0&0&1\end{bmatrix}\):

    $$ \begin{aligned}R&\in\{\,UWV^{\top},\ UW^{\top}V^{\top}\,\},\qquad \mathbf t=\pm\mathbf u_3\ \ (\|\mathbf t\|=1)\\ \text{cheirality:}&\ \ \lambda_1>0,\ \lambda_2>0,\ \ \text{where }\ \lambda_2\hat{\mathbf x}_2=\lambda_1R\hat{\mathbf x}_1+\mathbf t\end{aligned} $$

    验证：\(\mathbf t\) 必须满足 \(E^{\top}\mathbf t=R^{\top}[\mathbf t]_\times^{\top}\mathbf t=\mathbf 0\)，所以 \(\mathbf t\) 在 \(E\) 的左零空间里，即 \(\mathbf u_3\)。深度 \((\lambda_1,\lambda_2)\) 由上面三维向量方程的最小二乘解得到（FIG 4 用的就是这个；11.3 节会讲更精确的三角化）。有噪声时用投票：数一数有多少匹配点在两个相机前面，取最多的候选。注意：当基线很小、点很远时，孪生对的深度符号差别也很小，投票可能出错，这正是 FIG 5 里小视差时的失败原因之一。

    Check: \(\mathbf t\) must satisfy \(E^{\top}\mathbf t=R^{\top}[\mathbf t]_\times^{\top}\mathbf t=\mathbf 0\), so it lies in the left null space of \(E\), that is \(\mathbf u_3\). The depths \((\lambda_1,\lambda_2)\) come from the least-squares solution of the 3D vector equation above (this is what FIG 4 uses; Lesson 11.3 covers better triangulation). With noise use a vote: count how many matches are in front of both cameras and take the candidate with the most. Note that for a small baseline and distant points the depth signs of the twisted pair differ only slightly and the vote can go wrong, one reason for the failures at small parallax in FIG 5.

    Sampson 误差与"金标准"Sampson error and the gold standard

    \(\tilde{\mathbf x}_2^{\top}F\tilde{\mathbf x}_1\) 本身没有像素单位的意义。点到极线的距离 \(|\mathbf l^{\top}\mathbf x|/\sqrt{l_1^2+l_2^2}\) 只度量一张图。对两张图的一阶（Sampson）近似给出对匹配点在两张图上同时移动最少的像素量：

    The raw value \(\tilde{\mathbf x}_2^{\top}F\tilde{\mathbf x}_1\) has no pixel meaning, and the point-to-line distance \(|\mathbf l^{\top}\mathbf x|/\sqrt{l_1^2+l_2^2}\) accounts for one image only. The first-order (Sampson) approximation gives the pixel distance by which the match must move in both images together to satisfy the constraint:

    $$ d_{\text{Sampson}}^2=\frac{(\tilde{\mathbf x}_2^{\top}F\tilde{\mathbf x}_1)^2}{(F\tilde{\mathbf x}_1)_1^2+(F\tilde{\mathbf x}_1)_2^2+(F^{\top}\tilde{\mathbf x}_2)_1^2+(F^{\top}\tilde{\mathbf x}_2)_2^2}. $$

    它是真正的几何（重投影）误差的一阶近似，常用作 RANSAC 内点判据和非线性精化的目标。线性的 8 点算法最小化的是代数误差 \(\|A\mathbf f\|\)，不是几何误差；最优的"金标准"是把 \((R,\mathbf t)\) 与所有三维点一起，最小化重投影误差：这就是束调整（11.6 节），而 8 点或 5 点的结果是它的初值。

    It is a first-order approximation to the true geometric (reprojection) error and is the usual RANSAC inlier test and the objective for nonlinear refinement. The linear 8-point algorithm minimizes the algebraic error \(\|A\mathbf f\|\), not the geometric one; the optimal "gold standard" minimizes the reprojection error over \((R,\mathbf t)\) and all 3D points jointly. That is bundle adjustment (Lesson 11.6), with the 8-point or 5-point result as its initial guess.

    退化情形Degenerate cases

    • 平面场景：所有点在一个平面上时，匹配之间是单应 \(\tilde{\mathbf x}_2\sim H\tilde{\mathbf x}_1\)，于是对任何向量 \(\mathbf e\)，\([\mathbf e]_\times H\) 都满足约束，\(A\) 的零空间至少三维，\(F\) 不唯一（FIG 3：σ₇ σ₈ σ₉ 同样小）。对策：同时估计单应，让模型选择决定用哪一个（10.5 节）。
    • Planar scenes: when all points lie on one plane the matches are related by a homography \(\tilde{\mathbf x}_2\sim H\tilde{\mathbf x}_1\), so for any vector \(\mathbf e\) the matrix \([\mathbf e]_\times H\) satisfies the constraint, the null space of \(A\) is at least 3-dimensional and \(F\) is not unique (FIG 3: σ₇ σ₈ σ₉ equally small). Remedy: estimate a homography as well and let model selection decide (Lesson 10.5).
    • 纯旋转（基线 0）：\(\mathbf t=\mathbf 0\)，\(E=0\)，匹配由 \(H_\infty=KRK^{-1}\) 联系，与场景深度无关。同样 \(A\) 零空间三维，且根本没有深度信息可恢复。
    • Pure rotation (baseline 0): \(\mathbf t=\mathbf 0\), \(E=0\), the matches are related by \(H_\infty=KRK^{-1}\) regardless of depth. Again \(A\) has a 3-dimensional null space and there is no depth to recover at all.
    • 小基线、远场景：不是严格退化，但接近纯旋转，平移方向的噪声极大（FIG 5）。
    • Small baseline, distant scene: not strictly degenerate but close to pure rotation, and the translation direction becomes extremely noisy (FIG 5).
    • 临界曲面：所有点恰好在一个过两个光心的直纹二次曲面上时，也有多解（Hartley & Zisserman 第 22 章）。实际场景里很少碰到，但"近似平面"很常见。
    • Critical surfaces: if all points happen to lie on a ruled quadric through both camera centres, the solution is again ambiguous (Hartley & Zisserman ch. 22). Rare in practice; "nearly planar" scenes are common.

    最小求解器Minimal solvers

    要估计 5 个自由度的 \(E\)，最少 5 对匹配：Nistér（2004）的 5 点算法，解一个 10 次多项式，最多 10 个实解，已知内参时用它，因为样本少，RANSAC（11.5 节）迭代次数少得多：5 个点全是内点的概率是 \(w^5\)，8 个点是 \(w^8\)，\(w=0.5\) 时相差 8 倍。7 点算法利用 \(\det F=0\) 解三次方程，最多 3 个解。8 点算法是线性的，用于点多且干净的情形，或者作为 RANSAC 的内点上的最终精化。OpenCV 里 findEssentialMat 用 5 点加 RANSAC，findFundamentalMat 提供 7 点和 8 点。

    The 5-degree-of-freedom \(E\) needs at least 5 matches: Nistér's (2004) 5-point algorithm solves a degree-10 polynomial and yields up to 10 real solutions. Use it when the intrinsics are known, because the smaller sample cuts RANSAC's iterations (Lesson 11.5): the chance that 5 sampled points are all inliers is \(w^5\), for 8 points \(w^8\); at \(w=0.5\) that differs by a factor of 8. The 7-point algorithm uses \(\det F=0\) and a cubic with up to 3 solutions. The 8-point algorithm is linear and suits many clean points or the final refinement on a RANSAC inlier set. In OpenCV, findEssentialMat uses the 5-point algorithm inside RANSAC, while findFundamentalMat offers 7-point and 8-point.

    6机器人中的它：单目初始化为什么要等视差In robotics: why monocular initialization waits for parallax

    单目 SLAM / 视觉里程计启动时没有地图。典型做法（ORB-SLAM 等）：取第一帧作参考，等相机移动到足够"远"，再用这对帧估计 \(F\) 或 \(H\)，恢复 \((R,\mathbf t)\) 并三角化初始地图。为什么要等？FIG 5 用蒙特卡洛给出答案：同样的噪声，横向基线与场景深度之比 \(\rho\)（视差）越小，平移方向的误差越大。\(\rho\) 很小时，两张图几乎只差一个旋转，数据里的"平移信号"被噪声淹没，E 接近纯旋转的退化。旋转本身仍估计得不错，所以 VO 在小位移时可以靠别的传感器（IMU）保持姿态，却无法得到好的平移方向。

    FIG 5 中，每个点是 20 次独立噪声重抽后的中位数，每次都完整运行 8 点估计 E、四个候选分解和手性投票。顶部是对应的俯视图：两个相机（楔形是视场）、场景深度带，以及参考点处的视差角 \(\alpha\)（前向运动时，视差角在运动方向上为零，随偏离方向的角度增大）。切换到"向前移动"：前向运动同样的 \(\rho\) 下平移方向通常更准，因为极点落在图内，所有极线在图内辐射。但前向运动有它自己的问题：视差集中在图像边缘，光轴附近几乎没有视差。

    A monocular SLAM or visual-odometry system starts with no map. The typical recipe (ORB-SLAM and others): take the first frame as a reference, wait until the camera has moved far enough, then estimate \(F\) or \(H\) from that pair, recover \((R,\mathbf t)\) and triangulate the initial map. Why wait? FIG 5 answers with a Monte Carlo experiment: with the same noise, the smaller the ratio \(\rho\) of sideways baseline to scene depth (the parallax), the larger the error in the translation direction. At small \(\rho\) the two images differ almost only by a rotation, the "translation signal" drowns in the noise and E approaches the pure-rotation degeneracy. The rotation itself is still estimated well, which is why VO can keep its attitude at small displacements with other sensors (an IMU) but cannot get a good translation direction.

    In FIG 5 each point is the median of 20 independent noise draws, and every draw runs the complete pipeline: 8-point E, four-candidate decomposition and cheirality vote. The top panel is the matching top view: both cameras (wedges are the fields of view), the scene depth band and the parallax angle \(\alpha\) at a reference point (in forward motion it vanishes along the direction of motion and grows with the angle from it). Switch to "forward": for the same \(\rho\) forward motion usually gives a better translation direction because the epipole is inside the image and the lines radiate across it. Forward motion has its own problem, though: parallax concentrates at the image border, and near the optical axis there is almost none.

    FIG 5视差决定能恢复多准Parallax decides how well motion can be recovered
    俯视图（x 右，z 前）top view (x right, z forward)
    右图的两条曲线是平移方向误差（琥珀）与旋转误差（蓝），纵轴为对数；大圆点是当前滑块位置。基线 \(=6\rho\) m，横向时相机 2 稍向内转以注视场景中心。每个点用 N 个匹配、\(\sigma\) 像素噪声的 20 次独立实验。读数里的"投票选对候选"是手性检验选中真值候选的比例；视差角太小时，孪生对的深度符号几乎相同，投票就不再可靠。 The two curves on the right are the translation-direction error (amber) and the rotation error (blue) on a log axis; the large dots mark the current slider position. Baseline \(=6\rho\) m; in the sideways case camera 2 turns inward slightly to fixate on the scene centre. Each point comes from 20 independent trials with N matches and \(\sigma\) pixels of noise. "Vote picks the right candidate" in the readout is the share of trials in which the cheirality vote selects the true candidate; at very small parallax the twisted pair's depth signs are almost the same and the vote is unreliable.
    试一试Try this
    • 保持"横向移动"，把 \(\rho\) 拉到 0.04 以下：平移方向误差超过 20°，而旋转误差仍只有一两度。增大 N 或减小 \(\sigma\) 能把曲线整体压低，但"小基线很难"这条规律不变。Stay on "sideways" and pull \(\rho\) below 0.04: the translation-direction error exceeds 20° while the rotation error stays at a degree or two. A larger N or a smaller \(\sigma\) pushes the curves down but the rule "small baseline is hard" stays.
    真实系统里In real systems

    SLAM 初始化：ORB-SLAM（Mur-Artal 等，2015）并行估计单应 \(H\)（平面或低视差场景）与基础矩阵 \(F\)（一般场景），用一个基于打分的启发式选其一，再恢复运动并三角化；视差不够时拒绝初始化继续等。SfM：COLMAP（Schönberger & Frahm，2016）对每对图像估计 \(E\)、\(F\)、\(H\)，据内点情况把这对图像分类（例如一般、纯旋转/全景、平面），再进入增量式重建与束调整。OpenCV：findEssentialMat（5 点 + RANSAC）、recoverPose（分解 E 并做手性检验）、findFundamentalMat、stereoRectify（11.2 节）。学习式方法：SuperGlue、LoFTR 等学习的匹配器给出更多更可靠的对应点，之后仍然要用对极几何做几何验证（11.5 节）；DUSt3R（Wang 等，2024）一类的方法直接从图像对回归出点图，不需要显式的 \(E\)。其他：极线约束把立体匹配和多视图注意力从二维搜索降为沿线的一维，一些多视图 Transformer 与 NeRF/3DGS 的前馈重建方法就沿极线采样特征（12.4 节指路）。

    SLAM initialization: ORB-SLAM (Mur-Artal et al., 2015) estimates a homography \(H\) (planar or low-parallax scenes) and a fundamental matrix \(F\) (general scenes) in parallel, picks one with a score-based heuristic, recovers motion and triangulates; if parallax is insufficient it refuses to initialize and keeps waiting. SfM: COLMAP (Schönberger & Frahm, 2016) estimates \(E\), \(F\) and \(H\) for each image pair, classifies the pair from the inlier counts (for example general, pure rotation/panoramic, planar), and then proceeds to incremental reconstruction and bundle adjustment. OpenCV: findEssentialMat (5-point + RANSAC), recoverPose (decomposes E and applies the cheirality test), findFundamentalMat, stereoRectify (Lesson 11.2). Learned methods: learned matchers such as SuperGlue and LoFTR provide more and more reliable correspondences, which are still verified geometrically with epipolar geometry (Lesson 11.5); DUSt3R (Wang et al., 2024) and similar methods regress a pointmap straight from an image pair without an explicit \(E\). Elsewhere: the epipolar constraint turns stereo matching and multi-view attention from a 2D search into a 1D search along the line, and some multi-view transformers and feed-forward NeRF/3DGS-style reconstruction methods sample features along epipolar lines (a pointer to Lesson 12.4).

    7常见误区Common pitfalls

    误区 1：以为 \(\|\mathbf t\|=1\) 就是 1 米Pitfall 1: reading \(\|\mathbf t\|=1\) as one metre

    对极方程对 \(\mathbf t\) 的任意缩放不变，所以只能恢复平移的方向，分解给出的单位向量只是约定。在 FIG 4 里放大整个世界，所有像素原封不动。后果在系统层面：单目 VO 的轨迹只有相似变换意义下的形状；把两对相邻帧的结果串起来时，每一对的尺度都是任意的，需要用共同观测的三维点把尺度对齐，而对齐误差会累积成尺度漂移。度量尺度必须从外部引入：双目基线、IMU、轮速计、已知大小的物体（如 AprilTag）、深度传感器。

    The epipolar equation is invariant to any rescaling of \(\mathbf t\), so only the direction of the translation can be recovered, and the unit vector from the decomposition is just a convention. In FIG 4 enlarge the world and every pixel stays put. The consequence at system level: a monocular VO trajectory has its shape only up to similarity; when you chain the results of consecutive pairs, each pair has its own arbitrary scale and has to be aligned through jointly observed 3D points, and the alignment errors accumulate as scale drift. Metric scale has to come from outside: a stereo baseline, an IMU, wheel odometry, an object of known size (such as an AprilTag), or a depth sensor.

    误区 2：平面场景和纯旋转看起来"很好估计"Pitfall 2: planar scenes and pure rotation look "easy to estimate"

    平面墙、地面、桌面上有大量好匹配，残差也很小，可 8 点算法返回的 \(F\) 在一个三维族里随噪声乱跳（FIG 3 的"平面场景"：拟合很好，留出误差很大，极点漂移）。机器人偏偏常常对着地面看（移动机器人、无人机的下视相机）。检查办法：看 \(A\) 的奇异值有没有出现三个同样小的，或者同时估计单应、比较内点数（ORB-SLAM、COLMAP 都这样做）。纯旋转同理，而且根本没有深度可言：全景拼接可以靠 \(H_\infty\)，但三角化不出任何点。

    Walls, floors and tables offer plenty of good matches with tiny residuals, yet the 8-point algorithm returns an \(F\) that wanders through a 3-dimensional family with the noise (FIG 3, "planar scene": a good fit, a large held-out error, a drifting epipole). Robots often look at the floor (mobile robots, a drone's downward camera). To detect it, look at whether \(A\) has three equally small singular values, or estimate a homography as well and compare the inlier counts (ORB-SLAM and COLMAP both do). Pure rotation is the same and there is no depth at all: panorama stitching works with \(H_\infty\) but nothing can be triangulated.

    误区 3：无噪声的单元测试通过了，所以代码是对的Pitfall 3: the noise-free unit test passes, so the code is right

    没有噪声时，带不带归一化、带不带秩 2 约束都能把残差压到 \(10^{-13}\)，测试全绿。真实数据里差别立刻出现：FIG 3 中不归一化的误差通常是归一化的两倍以上。再加上极线约束只是必要条件：落在极线上的任何一点都通过检验，重复纹理会沿线匹配错；一个运动的物体，只要它在对极平面里移动（例如与相机平行行驶的汽车），也满足约束；一个明显错的匹配会把最小二乘拖偏。所以真实流程里总是 RANSAC + 归一化 8 点 / 5 点（11.5 节），再用 Sampson 误差挑内点。

    Without noise, with or without normalization and with or without the rank-2 step, the residual drops to \(10^{-13}\) and every test is green. On real data the difference appears at once: in FIG 3 the un-normalized error is typically twice the normalized one or more. On top of that the epipolar constraint is only necessary: any point on the line passes the test, repeated textures produce matches that slide along the line, a moving object that moves within the epipolar plane (a car driving parallel to the camera's motion) also satisfies it, and one grossly wrong match drags the least squares away. Real pipelines therefore always use RANSAC + normalized 8-point / 5-point (Lesson 11.5) and pick inliers with the Sampson error.

    误区 4：E 与 F 混用，或对 F 加"奇异值相等"Pitfall 4: mixing up E and F, or forcing equal singular values on F

    \(E\) 只对归一化坐标成立，把像素直接放进 8 点算法再去做 SVD 分解，得到的"\(R\)"不是旋转。\(F\) 的奇异值通常相差一个数量级以上（FIG 3 的真值 \(F\)：第二奇异值约为第一个的 0.04 倍），它只要求秩 2，强行把 \(F\) 的前两个奇异值设成相等会毁掉它。\(E=K_2^{\top}FK_1\) 要用正确的 \(K\)：内参不准或没去畸变（10.3 节）时，得到的 \(E\) 的前两个奇异值就不再相等，这本身是检验标定质量的一个指标。

    \(E\) holds for normalized coordinates only: feed pixels to the 8-point algorithm, decompose with an SVD, and the "\(R\)" is not a rotation. \(F\)'s singular values usually differ by an order of magnitude or more (FIG 3's true \(F\): the second is about 0.04 of the first); it only requires rank 2, and forcing the top two singular values of \(F\) to be equal ruins it. \(E=K_2^{\top}FK_1\) needs the correct \(K\): with inaccurate intrinsics or without removing the distortion (Lesson 10.3) the two largest singular values of \(E\) stop being equal, which in itself is a useful check of calibration quality.

    误区 5：位姿方向与符号约定搞反Pitfall 5: getting the direction and sign conventions backwards

    \(\mathbf X_2=R\mathbf X_1+\mathbf t\)：\((R,\mathbf t)\) 把相机 1 系的坐标变到相机 2 系（"外参"方向），\(\mathbf t\) 是相机 1 光心在相机 2 系中的坐标，不是相机 2 的位置，相机 2 在相机 1 系的位置是 \(-R^{\top}\mathbf t\)。把 \(E\) 拿来用之前，要确认第一个点集属于哪张图：交换两张图得到 \(E^{\top}\)，对应的位姿是 \((R^{\top},-R^{\top}\mathbf t)\)。另外 \(\pm\mathbf t\) 的符号只有手性检验能定，千万不要凭"相机应该往前走"硬选。把解算结果串进 SLAM 的位姿图时，要把它换成 \({}^{w}T_{c}\) 的形式，别直接拿去乘。

    \(\mathbf X_2=R\mathbf X_1+\mathbf t\): \((R,\mathbf t)\) maps camera-1 coordinates to camera-2 coordinates (the "extrinsics" direction), \(\mathbf t\) is camera 1's centre expressed in camera 2's frame, not camera 2's position, and camera 2's position in camera 1's frame is \(-R^{\top}\mathbf t\). Before using \(E\), check which image the first point set belongs to: swapping the two images yields \(E^{\top}\) with the pose \((R^{\top},-R^{\top}\mathbf t)\). The sign of \(\pm\mathbf t\) is decided only by the cheirality test; never pick it because "the camera should be moving forward". When feeding the result into a SLAM pose graph, convert it to a \({}^{w}T_{c}\) form rather than multiplying it in directly.

    8小练习Check yourself

    1. 相机 2 相对相机 1 沿 x 方向平移，没有旋转：\(R=I\)，\(\mathbf t=(2,0,0)^{\top}\)。归一化点 \(\hat{\mathbf x}_1=(0.3,\,0.5,\,1)^{\top}\) 在图 2 里的极线是什么？（手算 \(E=[\mathbf t]_\times\) 再算 \(E\hat{\mathbf x}_1\)。）1. Camera 2 is translated along x relative to camera 1 with no rotation: \(R=I\), \(\mathbf t=(2,0,0)^{\top}\). What is the epipolar line in image 2 of the normalized point \(\hat{\mathbf x}_1=(0.3,\,0.5,\,1)^{\top}\)? (Compute \(E=[\mathbf t]_\times\) by hand, then \(E\hat{\mathbf x}_1\).)
    \([\mathbf t]_\times=\begin{bmatrix}0&0&0\\0&0&-2\\0&2&0\end{bmatrix}\)，\(E=[\mathbf t]_\times\)，\(E\hat{\mathbf x}_1=(0,\,-2,\,1)^{\top}\)，即 \(-2y+1=0\)，\(y=0.5\)。左右并排、方向一致的两个相机，极线就是同一行：这是校正后双目的构型，视差只沿 x 方向（11.2 节）。\([\mathbf t]_\times=\begin{bmatrix}0&0&0\\0&0&-2\\0&2&0\end{bmatrix}\), \(E=[\mathbf t]_\times\), \(E\hat{\mathbf x}_1=(0,\,-2,\,1)^{\top}\), that is \(-2y+1=0\), \(y=0.5\). For two cameras side by side with the same orientation the epipolar line is the same image row: the rectified-stereo configuration, with disparity along x only (Lesson 11.2).
    2. 本质矩阵 \(E\) 与基础矩阵 \(F\)（都只确定到整体尺度）各有多少个自由度？2. How many degrees of freedom do the essential matrix \(E\) and the fundamental matrix \(F\) have (both defined up to overall scale)?
    E：旋转 3 + 平移方向 2 = 5（平移的长度不可观）。F：9 − 1（尺度）− 1（\(\det F=0\)）= 7。E 还额外要求两个奇异值相等，这是 F 没有的约束，多出的 2 个约束就是内参带来的信息。E: rotation 3 + translation direction 2 = 5 (the length of the translation is unobservable). F: 9 − 1 (scale) − 1 (\(\det F=0\)) = 7. E carries the extra equal-singular-value constraint that F lacks; those 2 extra constraints are the information the intrinsics supply.
    3. 对一对真实匹配，在 \(E\) 分解出的四个候选下三角化，深度符号 \((\lambda_1,\lambda_2)\) 分别是 \((+,+)\)、\((-,-)\)、\((+,-)\)、\((-,+)\)。哪一个候选是真实运动？3. For one real match, triangulating under the four candidates from \(E\) gives depth signs \((\lambda_1,\lambda_2)\) of \((+,+)\), \((-,-)\), \((+,-)\), \((-,+)\). Which candidate is the true motion?
    四个候选对对极方程同样成立，数据本身分辨不了，只有"点必须在相机前面"这条物理事实能挑出 \((+,+)\)。\((R,-\mathbf t)\) 给出 \((-,-)\)；孪生对（绕基线转 180°的另一个旋转）给出异号的 \((+,-)\) 或 \((-,+)\)。实际中对所有匹配投票（FIG 4）。All four candidates satisfy the epipolar equation equally, so the data cannot discriminate; only the physical fact "the point must be in front of the camera" picks \((+,+)\). \((R,-\mathbf t)\) gives \((-,-)\); the twisted pair (the other rotation, 180° about the baseline) gives the mixed signs \((+,-)\) or \((-,+)\). In practice all matches vote (FIG 4).
    4. 有人把整个世界（场景和相机运动）都放大 2 倍，然后重新拍摄这两张图。下面哪个结论对？4. Someone scales the entire world (scene and camera motion) by a factor of 2 and re-shoots the two images. Which statement is correct?
    针孔投影是 \(\tilde{\mathbf x}\sim K[R|\mathbf t]\tilde{\mathbf X}\)，\(\mathbf X\) 与 \(\mathbf t\) 同乘 2，像素不变；\(E=[\mathbf t]_\times R\) 变成 \(2E\)，而对极方程 \(\hat{\mathbf x}_2^{\top}E\hat{\mathbf x}_1=0\) 对整体比例不敏感。所以单目只能恢复到相似变换，旋转不受影响（FIG 4 的尺度滑块）。Pinhole projection is \(\tilde{\mathbf x}\sim K[R|\mathbf t]\tilde{\mathbf X}\); multiply both \(\mathbf X\) and \(\mathbf t\) by 2 and the pixels do not change. \(E=[\mathbf t]_\times R\) becomes \(2E\), but \(\hat{\mathbf x}_2^{\top}E\hat{\mathbf x}_1=0\) does not care about an overall factor. A single camera therefore recovers the world only up to similarity, and the rotation is unaffected (FIG 4's scale slider).
    5. 手持相机原地转动（\(\mathbf t=\mathbf 0\)，只有 \(R\)），拍两张图，匹配 200 对，运行 8 点算法。会发生什么？5. A handheld camera rotates in place (\(\mathbf t=\mathbf 0\), only \(R\)). You take two images, find 200 matches and run the 8-point algorithm. What happens?
    纯旋转时所有匹配满足 \(\tilde{\mathbf x}_2\sim H\tilde{\mathbf x}_1\)，于是任何 \([\mathbf e]_\times H\) 都满足对极方程，\(E=0\) 不含信息。增加匹配数没有用（FIG 3 的"纯旋转"：σ₇ σ₈ σ₉ 同样小，极点乱跳）。应当估计单应；只有单应解释不了数据时，才继续估计 \(F\)。Under pure rotation all matches satisfy \(\tilde{\mathbf x}_2\sim H\tilde{\mathbf x}_1\), so every \([\mathbf e]_\times H\) satisfies the epipolar equation and \(E=0\) carries no information. More matches do not help (FIG 3, "pure rotation": σ₇ σ₈ σ₉ equally small, the epipole jumping about). Estimate the homography; only if \(H\) is rejected go on to estimate \(F\).

    9延伸阅读Further reading

    • R. Hartley & A. Zisserman, Multiple View Geometry in Computer Vision, 2nd ed. (Cambridge University Press, 2004), Ch. 9–11 — 对极几何与基础矩阵、相机与结构的三维重建、基础矩阵的估计（含 8 点、7 点与归一化）Epipolar geometry and the fundamental matrix, 3D reconstruction of cameras and structure, and computation of F (8-point, 7-point and normalization)
    • H. C. Longuet-Higgins, A computer algorithm for reconstructing a scene from two projections, Nature 293, 133–135, 1981 — 本质矩阵与 8 点算法的出处The origin of the essential matrix and the 8-point algorithm
    • R. Hartley, In defense of the eight-point algorithm, IEEE Trans. PAMI 19(6):580–593, 1997 — 说明坐标归一化让 8 点算法变得可用Shows that coordinate normalization makes the 8-point algorithm competitive
    • D. Nistér, An efficient solution to the five-point relative pose problem, IEEE Trans. PAMI 26(6):756–770, 2004 — 已知内参时 5 点估计 E（最多 10 个解）The 5-point solver for E with known intrinsics (up to 10 solutions)
    • Y. Ma, S. Soatto, J. Košecká & S. S. Sastry, An Invitation to 3-D Vision (Springer, 2004), Ch. 5 — 两个标定视图的重建：本质矩阵、4 个解与手性约束Reconstruction from two calibrated views: the essential matrix, the four solutions and the positive-depth constraint
    • T. S. Huang & O. D. Faugeras, Some properties of the E matrix in two-view motion estimation, IEEE Trans. PAMI 11(12):1310–1312, 1989 — 本质矩阵的充要条件（秩 2 且两个非零奇异值相等）The characterization of essential matrices (rank 2, two equal nonzero singular values)
    • R. Mur-Artal, J. M. M. Montiel & J. D. Tardós, ORB-SLAM: A versatile and accurate monocular SLAM system, IEEE T-RO 31(5):1147–1163, 2015 — 单目初始化中 \(H\) 与 \(F\) 的模型选择Model selection between \(H\) and \(F\) in monocular initialization
    • J. L. Schönberger & J.-M. Frahm, Structure-from-Motion Revisited, CVPR 2016 — COLMAP：两视图几何验证与增量式 SfMCOLMAP: two-view geometric verification and incremental SfM