翻译 CS231A 课程笔记 4：立体系统和运动恢复结构

博主： Saber
发布时间：2025 年 05 月 09 日
17 次浏览
关闭评论
15779字数
分类：

1. 引言

在之前的笔记中，我们介绍了如何通过增加场景的额外视点来显著增强我们对该场景的认知。我们重点讨论了对极几何的设置，以便在不提取任何关于三维场景信息的情况下，将一个像平面上的点与另一个像平面上的点关联起来。在这些课程笔记中，我们将讨论如何从多个二维图像中恢复关于三维场景的信息。

2. 三角测量

多视图几何中最基本的问题之一是三角测量问题，即在给定一个三维点在两个或多个图像中的投影的情况下，确定该三维点位置的过程。

图1：给定两个视图时的三角测量问题设置

在具有两个视图的三角测量问题中，我们有两个相机，其已知的相机内参分别为 $K$ 和 $K^{\prime}$。我们也知道这两个相机之间相对的旋转和平移 $R, T$。假设在三维空间中有一个点 $P$，它在两个相机的图像中分别位于 $p$ 和 $p^{\prime}$。尽管 $P$ 的位置当前未知，但我们可以测量图像中 $p$ 和 $p^{\prime}$ 的精确位置。因为 $K, K^{\prime}, R, T$ 是已知的，我们可以计算出由相机中心 $O_{1}$、$O_{2}$ 和图像位置 $p$、$p^{\prime}$ 定义的两条视线 $l$ 和 $l^{\prime}$。因此，$P$ 可以计算为 $l$ 和 $l^{\prime}$ 的交点。

图2：现实世界场景中的三角测量问题通常涉及最小化重投影误差

尽管这个过程看起来既直接又数学上合理，但在实践中效果并不理想。在现实世界中，由于观测值 $p$ 和 $p^{\prime}$ 存在噪声，并且相机标定参数不精确，寻找 $l$ 和 $l^{\prime}$ 的交点可能会有问题。在大多数情况下，交点可能根本不存在，因为两条线可能永远不会相交。

2.1 三角测量的线性方法

在本节中，我们描述一种简单的线性三角测量方法，该方法解决了光线之间缺少交点的问题。给定图像中相互对应的两个点 $p=MP=(x,y,1)$ 和 $p^{\prime}=M^{\prime}P=(x^{\prime},y^{\prime},1)$。根据叉积的定义，$p \times (MP) = 0$。我们可以明确地使用叉积生成的等式来形成三个约束条件：

$$x(M_{3}P)-(M_{1}P)=0$$
$$y(M_{3}P)-(M_{2}P)=0$$
$$x(M_{2}P)-y(M_{1}P)=0 \quad (2.1)$$

其中 $M_{i}$ 是矩阵 $M$ 的第 $i$ 行。对于 $p^{\prime}$ 和 $M^{\prime}$ 也可以形成类似的约束。利用来自两个图像的约束，我们可以构建一个形如 $AP=0$ 的线性方程，其中

$$A=\begin{bmatrix}xM_{3}-M_{1}\\ yM_{3}-M_{2}\\ x^{\prime}M^{\prime}_{3}-M^{\prime}_{1}\\ y^{\prime}M^{\prime}_{3}-M^{\prime}_{2}\end{bmatrix} \quad (2.2)$$

该方程可以使用SVD求解，以找到点 $P$ 的最佳线性估计。该方法的另一个有趣的方面是它实际上也可以处理从多个视图进行的三角测量。为此，只需向 $A$ 中附加由新视图增加的约束对应的额外行即可。然而，这种方法不适用于投影重建，因为它不是投影不变的。例如，假设我们将相机矩阵 $M, M^{\prime}$ 替换为受投影变换 $MH^{-1}, M^{\prime}H^{-1}$ 影响的矩阵。线性方程组的矩阵 $A$ 则变为 $AH^{-1}$。因此，先前估计 $AP=0$ 的解 $P$ 将对应于变换后问题 $(AH^{-1})(HP)=0$ 的解 $HP$。回想一下，SVD求解的约束是 $||P||=1$，这在投影变换 $H$ 下不是不变的。因此，这种方法虽然简单，但通常不是三角测量问题的最优解。

2.2 三角测量的非线性方法

相反，现实世界场景中的三角测量问题通常在数学上被描述为解决一个最小化问题：

$$\min_{\hat{P}}||M\hat{P}-p||^{2}+||M^{\prime}\hat{P}-p^{\prime}||^{2} \quad (2.3)$$

在上述等式中，我们寻求在三维空间中找到一个 $\hat{P}$，通过在两个图像中找到 $\hat{P}$ 的重投影误差的最佳最小二乘估计来最好地逼近 $P$。三维点在图像中的重投影误差是指该点在图像中的投影与图像中相应观测点之间的距离。在我们图2的例子中，由于 $M$ 是从三维空间到图像1的投影变换，因此 $P$ 在图像1中的投影点是 $MP$。图像1中 $\hat{P}$ 的匹配观测值是 $p$。因此，点 $P$ 在图像1中的重投影误差是距离 $||MP-p||$。等式2.3中找到的总重投影误差是图像中所有点的重投影误差之和。对于超过两个图像的情况，我们只需向目标函数添加更多的距离项：

$$\min_{\hat{P}}\sum_{i}||M\hat{P}_{i}-p_{i}||^{2} \quad (2.4)$$

在实践中，存在各种非常复杂的优化技术，可以很好地逼近该问题。然而，在本课程的范围内，我们将只关注其中一种技术，即用于非线性最小二乘的高斯-牛顿算法。一般的非线性最小二乘问题是找到一个 $x \in \mathbb{R}^{n}$ 来最小化

$$||r(x)||^{2}=\sum_{i=1}^{m}r_{i}(x)^{2} \quad (2.5)$$

其中 $r$ 是任何残差函数 $r:\mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$，使得对于某个函数 $f$ 输入和观测值 $y$，$r(x)=f(x)-y$。当函数 $f$ 是线性时，非线性最小二乘问题简化为常规的线性最小二乘问题。然而，回想一下，一般来说，我们的相机矩阵不是仿射的。由于投影到像平面通常涉及除以齐次坐标，因此投影到图像通常是非线性的。注意，如果我们将 $e_{i}$ 设置为一个 $2 \times 1$ 的向量 $e_{i}=M\hat{P}_{i}-p_{i}$，那么我们可以将我们的优化问题重新表述为：

$$\min_{\hat{P}}\sum_{i}e_{i}(\hat{P})^{2} \quad (2.6)$$

这可以完美地表示为一个非线性最小二乘问题。

在这些笔记中，我们将介绍如何使用流行的高斯-牛顿算法来找到这个非线性最小二乘问题的近似解。首先，让我们假设我们对三维点 $\hat{P}_{i}$ 有一个合理的估计，我们可以通过先前的线性方法计算出来。高斯-牛顿算法的关键思想是通过将其校正到最小化重投影误差的更好估计来更新我们的估计。在每一步，我们都希望通过某个 $\delta_{P}$ 来更新我们的估计 $\hat{P}$：$\hat{P} = \hat{P} + \delta_{P}$。

但是我们如何选择更新参数 $\delta_{P}$ 呢？高斯-牛顿算法的关键思想是在当前估计 $\hat{P}$ 附近线性化残差函数。在我们的问题中，这意味着点 $P$ 的残差误差 $e$ 可以被认为是：

$$e(\hat{P}+\delta_{P})\approx e(\hat{P})+\frac{\partial e}{\partial P}\delta_{P} \quad (2.7)$$

随后，最小化问题转化为

$$\min_{\delta_{P}}||\frac{\partial e}{\partial P}\delta_{P}-(-e(\hat{P}))||^{2} \quad (2.8)$$

当我们这样表述残差时，我们可以看到它采用了标准线性最小二乘问题的格式。对于具有 $N$ 个图像的三角测量问题，线性最小二乘解是

$$\delta_{P}=-(J^{T}J)^{-1}J^{T}e \quad (2.9)$$

其中

$$e=\begin{bmatrix}e_{1}\\ \vdots\\ e_{N}\end{bmatrix}=\begin{bmatrix}p_{1}-M_{1}\hat{P}\\ \vdots\\ p_{N}-M_{N}\hat{P}\end{bmatrix} \quad (2.10)$$

和

$$J=\begin{bmatrix}\frac{\partial e_{1}}{\partial P_{1}}&\frac{\partial e_{1}}{\partial P_{2}}&\frac{\partial e_{1}}{\partial P_{3}}\\ \vdots&\vdots&\vdots\\ \frac{\partial e_{N}}{\partial P_{1}}&\frac{\partial e_{N}}{\partial P_{2}}&\frac{\partial e_{N}}{\partial P_{3}}\end{bmatrix} \quad (2.11)$$

回想一下，特定图像的残差误差向量 $e_{i}$ 是一个 $2 \times 1$ 的向量，因为像平面中有两个维度。因此，在最简单的双相机情况 $(N=2)$ 的三角测量中，这将导致残差向量 $e$ 是一个 $2N \times 1 = 4 \times 1$ 的向量，雅可比矩阵 $J$ 是一个 $2N \times 3 = 4 \times 3$ 的矩阵。请注意这种方法如何无缝地处理多个视图，因为通过向 $e$ 向量和 $J$ 矩阵添加相应的行来考虑其他图像。在计算更新 $\delta_{P}$ 之后，我们可以简单地重复该过程固定的步数或直到其数值收敛。高斯-牛顿算法的一个重要特性是，我们关于残差函数在估计附近是线性的假设并不能保证收敛。因此，在实践中，对估计的更新次数设置上限总是有用的。

3. 运动恢复仿射结构

在上一节的末尾，我们暗示了如何超越场景的两个视图来获取关于三维场景的信息。我们现在将探讨将双摄像头几何结构扩展到多摄像头。通过组合来自多个视图的点观测值，我们将能够同时确定场景的三维结构和相机的参数，这被称为运动恢复结构 (Structure from Motion, SfM)。

图3：一般运动恢复结构问题的设置

在这里，我们正式介绍运动恢复结构问题。假设我们有 $m$ 个相机，其相机变换 $M_{i}$ 编码了相机的内参和外参。设 $X_{j}$ 是场景中 $n$ 个三维点之一。每个三维点可能在多个相机中可见，其位置为 $x_{ij}$，这是使用投影变换 $M_{i}$ 将 $X_{j}$ 投影到相机 $i$ 的图像的结果。运动恢复结构的目的是从所有观测值 $x_{ij}$ 中恢复场景的结构（$n$ 个三维点 $X_{j}$）和相机的运动（$m$ 个投影矩阵 $M_{i}$）。

3.1 运动恢复仿射结构问题

在解决一般的运动恢复结构问题之前，我们将首先从一个更简单的问题开始，该问题假设相机是仿射或弱透视的。最终，透视缩放操作的缺乏使得这个问题的数学推导更容易。

之前，我们推导了透视和弱透视情况的上述方程。请记住，在完整的透视模型中，相机矩阵定义为

$$M=\begin{bmatrix}A&b\\ v&1\end{bmatrix} \quad (3.1)$$

其中 $v$ 是某个非零的 $1 \times 3$ 向量。另一方面，对于弱透视模型，$v=0$。我们发现这个特性使得 $MX$ 的齐次坐标等于1：

$$x=MX=\begin{bmatrix}m_{1}\\ m_{2}\\ 0 \ 0 \ 1\end{bmatrix}\begin{bmatrix}X_{1}\\ X_{2}\\ X_{3}\\ 1\end{bmatrix}=\begin{bmatrix}m_{1}X\\ m_{2}X\\ 1\end{bmatrix} \quad (3.2)$$

因此，当我们从齐次坐标移动到欧几里得坐标时，投影变换的非线性消失了，弱透视变换仅仅充当放大镜的角色。我们可以更紧凑地表示投影为：

$$\begin{bmatrix}m_{1}X\\ m_{2}X\end{bmatrix}=\begin{bmatrix}A&b\end{bmatrix}X=AX+b \quad (3.3)$$

并以 $M_{\text{affine}}=\begin{bmatrix}A&b\end{bmatrix}$ 的格式表示任何相机矩阵。因此，我们现在使用仿射相机模型来表示三维空间中的点 $X_{j}$ 与每个仿射相机中相应观测值（例如，相机 $i$ 中的 $x_{ij}$）之间的关系。

回到运动恢复结构问题，我们需要估计 $m$ 个矩阵 $M_{i}$ 和 $n$ 个世界坐标向量 $X_{j}$，总共有 $8m+3n$ 个未知数，来自于 $mn$ 个观测值。每个观测值每个相机产生2个约束，因此在 $8m+3n$ 个未知数中有 $2mn$ 个方程。我们可以使用这个方程来了解我们需要的每个图像中相应观测值的数量下限。例如，如果我们有 $m=2$ 个相机，那么我们至少需要 $n=16$ 个三维点。然而，一旦我们在每个图像中标记了足够多的对应点，我们如何解决这个问题呢？

3.2 Tomasi 和 Kanade 的分解方法

在这一部分，我们概述了Tomasi和Kanade用于解决运动恢复仿射结构问题的分解方法。该方法包括两个主要步骤：数据中心化步骤和实际分解步骤。

(图4：应用中心化步骤时，我们平移所有图像点，使其质心（表示为左下角的红色十字）位于像平面的原点。类似地，我们放置世界坐标系，使原点位于三维点的质心（表示为右上角的红色十字）。)

让我们从数据中心化步骤开始。在此步骤中，主要思想是将数据中心化到原点。为此，对于每个图像 $i$，我们通过减去它们的质心 $\overline{x}_{i}$ 来为每个图像点 $x_{ij}$ 重新定义新的坐标 $\hat{x}_{ij}$：

$$\hat{x}_{ij}=x_{ij}-\overline{x}_{i}=x_{ij}-\frac{1}{n}\sum_{j=1}^{n}x_{ij} \quad (3.4)$$

回想一下，运动恢复仿射结构问题允许我们定义图像点 $x_{ij}$、相机矩阵变量 $A_{i}$ 和 $b_{i}$ 以及三维点 $X_{j}$ 之间的关系为：

$$x_{ij}=A_{i}X_{j}+b_{i} \quad (3.5)$$

在此中心化步骤之后，我们可以组合等式3.4中中心化图像点 $\hat{x}_{ij}$ 的定义和等式3.5中的仿射表达式：

$$\hat{x}_{ij}=x_{ij}-\frac{1}{n}\sum_{k=1}^{n}x_{ik}$$
$$=A_{i}X_{j}-\frac{1}{n}\sum_{k=1}^{n}A_{i}X_{k}$$
$$=A_{i}(X_{j}-\frac{1}{n}\sum_{k=1}^{n}X_{k})$$
$$=A_{i}(X_{j}-\overline{X})$$
$$=A_{i}\hat{X}_{j} \quad (3.6)$$

从等式3.6可以看出，如果我们将世界参考系的原点平移到质心 $\overline{X}$，那么图像点的中心化坐标 $\hat{x}_{ij}$ 和三维点的中心化坐标 $\hat{X}_{j}$ 仅通过一个 $2 \times 3$ 的矩阵 $A_{i}$ 相关联。最终，分解方法的中心化步骤允许我们创建一个紧凑的矩阵乘积表示，以将三维结构与其在多个图像中的观测点联系起来。

然而，请注意，在矩阵乘积 $\hat{x}_{ij}=A_{i}\hat{X}_{j}$ 中，我们只能访问等式左侧的值。因此，我们必须以某种方式分解出运动矩阵 $A_{i}$ 和结构 $X_{j}$。利用所有相机的所有观测值，我们可以构建一个测量矩阵 $D$，它由 $m$ 个相机中的 $n$ 个观测值组成（请记住，每个 $\hat{x}_{ij}$ 条目都是一个 $2 \times 1$ 的向量）：

$$D=\begin{bmatrix}\hat{x}_{11}&\hat{x}_{12}&...&\hat{x}_{1n}\\ \hat{x}_{21}&\hat{x}_{22}&...&\hat{x}_{2n}\\ &\vdots&\\ \hat{x}_{m1}&\hat{x}_{m2}&...&\hat{x}_{mn}\end{bmatrix} \quad (3.7)$$

现在回想一下，由于我们的仿射假设，$D$ 可以表示为 $2m \times 3$ 运动矩阵 $M$（包含相机矩阵 $A_{1}, \dots, A_{m}$）和 $3 \times n$ 结构矩阵 $S$（包含三维点 $X_{1}, \dots, X_{n}$）的乘积。我们将使用的一个重要事实是 $rank(D)=3$，因为 $D$ 是两个最大维度为3的矩阵的乘积。

为了将 $D$ 分解为 $M$ 和 $S$，我们将使用奇异值分解 $D=U\Sigma V^{T}$。由于我们知道 $rank(D)=3$，因此 $\Sigma$ 中只有3个非零奇异值 $\sigma_{1}, \sigma_{2}$ 和 $\sigma_{3}$。因此，我们可以进一步简化表达式并获得以下分解：

$$D=U\Sigma V^{T}$$
$$= \begin{bmatrix} u_{1} & \dots & u_{m} \end{bmatrix} \begin{bmatrix} \sigma_{1} & 0 & 0 & 0 & \dots & 0 \\ 0 & \sigma_{2} & 0 & 0 & \dots & 0 \\ 0 & 0 & \sigma_{3} & 0 & \dots & 0 \\ 0 & 0 & 0 & 0 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \dots & 0 \end{bmatrix} \begin{bmatrix} v_{1}^{T} \\ v_{2}^{T} \\ v_{3}^{T} \\ \vdots \\ v_{n}^{T} \end{bmatrix}$$
$$= \begin{bmatrix} u_{1} & u_{2} & u_{3} \end{bmatrix} \begin{bmatrix} \sigma_{1} & 0 & 0 \\ 0 & \sigma_{2} & 0 \\ 0 & 0 & \sigma_{3} \end{bmatrix} \begin{bmatrix} v_{1}^{T} \\ v_{2}^{T} \\ v_{3}^{T} \end{bmatrix}$$
$$= U_{3}\Sigma_{3}V_{3}^{T} \quad (3.8)$$

在此分解中，$\Sigma_{3}$ 定义为由非零奇异值形成的对角矩阵，而 $U_{3}$ 和 $V_{3}^{T}$ 分别通过取 $U$ 的相应三列和 $V^{T}$ 的行获得。不幸的是，在实践中，由于测量噪声和仿射相机近似，$rank(D)>3$。然而，回想一下，当 $rank(D)>3$ 时，$U_{3}\Sigma_{3}V_{3}^{T}$ 仍然是 $MS$ 在 Frobenius 范数意义下的最佳秩-3 近似。仔细检查后，我们发现矩阵乘积 $\Sigma_{3}V_{3}^{T}$ 形成一个 $3 \times n$ 矩阵，其大小与结构矩阵 $S$ 完全相同。类似地，$U_{3}$ 是一个 $2m \times 3$ 矩阵，其大小与运动矩阵 $M$ 相同。虽然这种将 SVD 分解的组件与 $M$ 和 $S$ 相关联的方式导致了运动恢复仿射结构问题的物理和几何上合理的解，但这种选择不是唯一的解。例如，我们也可以将运动矩阵设置为 $M=U_{3}\Sigma_{3}$，将结构矩阵设置为 $S=V_{3}^{T}$，因为在任何一种情况下，观测矩阵 $D$ 都是相同的。那么我们选择哪种分解呢？在他的论文中，Tomasi 和 Kanade 得出结论，一种稳健的分解选择是 $M=U_{3}\sqrt{\Sigma_{3}}$ 和 $S=\sqrt{\Sigma_{3}}V_{3}^{T}$。

3.3 重建中的模糊性

然而，我们在任何分解 $D=MS$ 的选择中都发现固有的模糊性，因为任何任意可逆的 $3 \times 3$ 矩阵 $A$ 都可以插入到分解中：

$$D=MAA^{-1}S=(MA)(A^{-1}S) \quad (3.9)$$

这意味着从运动 $M$ 获得的相机矩阵和从结构 $S$ 获得的三维点是在乘以一个共同矩阵 $A$ 的意义上确定的。因此，我们的解是欠定的，需要额外的约束来解决这种仿射模糊性。当重建具有仿射模糊性时，这意味着平行性得以保留，但度量尺度未知。

重建的另一类重要模糊性是相似性模糊，当重建在相似性变换（旋转、平移和缩放）的意义上是正确的时候发生。仅具有相似性模糊的重建称为度量重建。即使相机经过内部校准，这种模糊性也存在。好消息是，对于已校准的相机，相似性模糊是唯一的模糊性¹。

从图像中无法恢复场景的绝对尺度这一事实是相当直观的。除非我们做出进一步的假设（例如，我们知道图中房子的高度）或整合更多数据，否则物体的尺度、绝对位置和规范方向将始终是未知的。这是因为某些属性可能会补偿其他属性。例如，为了获得相同的图像，我们可以简单地将对象向后移动并相应地缩放它。消除相似性模糊的一个这样的例子发生在相机标定过程中，当时我们假设我们知道标定点相对于世界参考系的位置。这使我们能够知道棋盘格方块的大小，从而学习三维结构的度量尺度。

¹有关更多详细信息，请参阅 [Longuet-Higgins ’81]。

4. 运动恢复透视结构

在研究了简化的运动恢复仿射结构问题之后，让我们现在考虑投影相机 $M_i$ 的一般情况。在一般情况下，每个投影相机矩阵 $M_i$ 包含11个自由度，因为它是按比例定义的：

$$M_i = \begin{bmatrix} a11 & a12 & a13 & b1 \\ a21 & a22 & a23 & b2 \\ a31 & a32 & a33 & 1 \end{bmatrix} \quad (4.1)$$

此外，与仿射情况类似（其中解可以在仿射变换的意义上找到），在一般情况下，结构和运动的解可以在投影变换的意义上确定：我们总是可以将一个 $4 \times 4$ 的投影变换 $H$ 任意地应用于运动矩阵，只要我们也通过逆变换 $H^{-1}$ 变换结构矩阵即可。像平面上的最终观测结果将保持不变。与仿射情况类似，我们可以将一般的运动恢复结构问题设置为从 $mn$ 个观测值 $x_{ij}$ 估计 $m$ 个运动矩阵 $M_i$ 和 $n$ 个三维点 $X_j$。由于相机和点只能恢复到一个 $4 \times 4$ 的投影变换（最多15个参数），我们有 $11m + 3n - 15$ 个未知数和 $2mn$ 个方程。根据这些事实，我们可以确定解决未知数所需的视图和观测值的数量。

4.1 代数方法

(图5：在代数方法中，我们考虑顺序的相机对来确定相机矩阵 $M_1$ 和 $M_2$（相差一个透视变换）。然后我们找到一个透视变换 $H$ 使得 $M_1H = [I \ 0]$ 和 $M_2H = [A \ B]$。)

我们现在将介绍代数方法，该方法利用基本矩阵 $F$ 的概念来解决两个相机的运动恢复结构问题。如图5所示，代数方法的主要思想是计算两个相机矩阵 $M_1$ 和 $M_2$，这两个矩阵只能计算到一个透视变换 $H$。由于每个 $M_i$ 只能计算到一个透视变换 $H$，我们可以总是考虑一个 $H$ 使得第一个相机投影矩阵 $M_1H^{-1}$ 是规范的。当然，相同的变换也必须应用于第二个相机，从而得到如下形式：

$$M_1H^{-1} = [I \ 0] \quad M_2H^{-1} = [A \ b] \quad (4.2)$$

为了完成这项任务，我们必须首先使用前述课程笔记中介绍的八点算法计算基本矩阵 $F$。我们现在将使用 $F$ 来估计投影相机矩阵 $M_1$ 和 $M_2$。为了进行此估计，我们将 $P$ 定义为图像中对应观测值 $p$ 和 $p^{\prime}$ 的对应三维点。由于我们已将 $H^{-1}$ 应用于两个相机投影矩阵，因此我们也必须将 $H$ 应用于结构，从而得到 $P_e = HP$。因此，我们可以将像素坐标 $p$ 和 $p^{\prime}$ 与变换后的结构关联如下：

$$p = M_1P = M_1H^{-1}HP = [I | 0]P_e$$
$$p^{\prime} = M_2P = M_2H^{-1}HP = [A | b]P_e \quad (4.3)$$

通过一些创造性的替换，两个图像对应点 $p$ 和 $p^{\prime}$ 之间出现了一个有趣的特性：

$$p^{\prime} = [A|b]P_e$$
$$= A[I|0]P_e + b$$
$$= Ap + b \quad (4.4)$$

使用等式4.4，我们可以将 $p^{\prime}$ 和 $b$ 之间的叉积写为：

$$p^{\prime} \times b = (Ap + b) \times b = Ap \times b \quad (4.5)$$

根据叉积的定义，$p^{\prime} \times b$ 垂直于 $p^{\prime}$。因此，我们可以写成：

$$0 = p^{\prime T}(p^{\prime} \times b)$$
$$= p^{\prime T}(Ap \times b)$$
$$= p^{\prime T} \cdot (b \times Ap)$$
$$= p^{\prime T}[b]_{\times}Ap \quad (4.6)$$

看这个约束，它应该让你想起基本矩阵的一般定义 $p^{\prime T}Fp = 0$。如果我们设置 $F = [b]_{\times}A$，那么提取 $A$ 和 $b$ 就简化为一个分解问题。让我们从确定 $b$ 开始。再次使用叉积的定义，我们可以写成，

$$F^{\top}b = [[b]_{\times}A]^{\top}b = 0 \quad (4.7)$$

由于 $F$ 是奇异的，$b$ 可以作为 $F^{\top}b = 0$ 的最小二乘解来计算，其中 $||b|| = 1$，使用SVD。一旦 $b$ 已知，我们现在可以计算 $A$。如果我们设置 $A = -[b]_{\times}F$，那么我们可以验证这个定义满足 $F = [b]_{\times}A$：

$$[b_{\times}]A = -[b_{\times}][b_{\times}]F$$
$$= (bb^T - |b|^2I)F$$
$$= bb^TF + |b|^2F$$
$$= 0 + 1 \cdot F$$
$$= F \quad (4.8)$$

因此，我们确定了相机矩阵 $M_1H^{-1}$ 和 $M_2H^{-1}$ 的两个表达式：

$$\tilde{M}_{1} = [I \ 0] \quad \tilde{M}_{2} = [-[b_{\times}]F \ b] \quad (4.9)$$

在结束本节之前，我们想给出 $b$ 的几何解释。我们知道 $b$ 满足 $F b = 0$。回想一下我们在前述课程笔记中推导的对极约束，它发现图像中的对极点是当被基本矩阵变换时映射到零的点（即 $Fe_2 = 0$ 和 $F^Te_1 = 0$）。因此，我们可以看到 $b$ 是一个对极点。这为相机投影矩阵提供了一组新的方程（等式4.10）。

$$\tilde{M}_{1} = [I \ 0] \quad \tilde{M}_{2} = [-[e_{\times}]F \ e] \quad (4.10)$$

4.2 从本质矩阵确定运动

改进通过代数方法获得的重建的一种有用方法是使用已校准的相机。通过使用本质矩阵 $E$（它是归一化坐标下基本矩阵的特例），我们可以提取更准确的相机矩阵初始估计。回想一下，通过使用本质矩阵 $E$，我们假设我们已经校准了相机，因此知道相机内参矩阵 $K$。我们可以直接从归一化图像坐标计算本质矩阵 $E$，也可以从其与基本矩阵 $F$ 和内参矩阵 $K$ 的关系计算：

$$E = K^TFK \quad (4.11)$$

因为本质矩阵假设我们有已校准的相机，我们应该记住它只有五个自由度，因为它只编码外参：相机之间的旋转 $R$ 和平移 $t$。幸运的是，这正是我们想要提取以创建运动矩阵的信息。首先，回想一下本质矩阵 $E$ 可以表示为

$$E = [t]_{\times}R \quad (4.12)$$

因此，也许我们可以找到一种策略将 $E$ 分解为其两个分量。首先，我们应该注意到叉积矩阵 $[t]_{\times}$ 是反对称的。我们定义将在分解中使用的两个矩阵：

$$W = \begin{bmatrix} 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} , \quad Z = \begin{bmatrix} 0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} \quad (4.13)$$

稍后我们将使用的一个重要特性是 $Z = \text{diag}(1, 1, 0)W$（相差一个符号）。类似地，我们还将使用 $ZW = ZW^T = \text{diag}(1, 1, 0)$（相差一个符号）这一事实。作为 Jordan 分解的结果，我们可以创建一个已知到尺度的一般反对称矩阵的块分解。因此，我们可以将 $[t]_{\times}$ 写为

$$[t]_{\times} = UZU^T \quad (4.14)$$

其中 $U$ 是某个正交矩阵。因此，我们可以将分解重写为：

$$E = U\text{diag}(1, 1, 0)(W U^TR) \quad (4.15)$$

仔细观察这个表达式，我们发现它与奇异值分解 $E = U\Sigma V^T$ 非常相似，其中 $\Sigma$ 包含两个相等的奇异值。如果我们知道 $E$（相差一个尺度），并且假设它具有形式 $E = U\text{diag}(1, 1, 0)V^T$，那么我们得到 $E$ 的以下分解：

$$[t]_{\times} = UZU^T , \quad R = UW V^T \text{ or } UW^T V^T \quad (4.16)$$

我们可以通过检查来证明给定的分解是有效的。我们也可以证明没有其他分解。$[t]_{\times}$ 的形式由其左零空间必须与 $E$ 的零空间相同这一事实决定。给定酉矩阵 $U$ 和 $V$，任何旋转 $R$ 都可以分解为 $UXV^T$，其中 $X$ 是另一个旋转矩阵。代入这些值后，我们得到 $ZX = \text{diag}(1, 1, 0)$（相差一个尺度）。因此，$X$ 必须等于 $W$ 或 $W^T$。

请注意，对 $E$ 的这种分解仅保证矩阵 $UW V^T$ 或 $UW^T V^T$ 是正交的。为了确保 $R$ 是有效的旋转，我们只需确保 $R$ 的行列式为正：

$$R = (\det UW V^T)UW V^T \text{ or } (\det UW^T V^T)UW^T V^T \quad (4.17)$$

与旋转 $R$ 可以取两个可能值类似，平移向量 $t$ 也可以取多个值。根据叉积的定义，我们知道

$$t \times t = [t]_{\times}t = UZU^Tt = 0 \quad (4.18)$$

知道 $U$ 是酉矩阵，我们可以发现 $||[t]_{\times}||_F = \sqrt{2}$。因此，我们从此分解中对 $t$ 的估计将来自上述方程以及 $E$ 已知到一个尺度这一事实。这意味着

$$t = \pm U \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} = \pm u_3 \quad (4.19)$$

其中 $u_3$ 是 $U$ 的第三列。通过检查，我们还可以验证通过将 $[t]_{\times} = UZU^T$ 重新格式化为已知到一个符号的向量 $t$ 可以得到相同的结果。

(图6：从本质矩阵中提取相对相机旋转 $R$ 和平移 $t$ 有四种可能的解。然而，只有在 (a) 中，重建的点位于两个相机的前方。(图取自Hartley and Zisserman 教材第260页))

如图6所示，由于 $R$ 和 $t$ 都有两个选项，因此存在四个潜在的 $R, t$ 配对。直观地说，这四个配对包括将相机向某个方向旋转或向相反方向旋转，并结合将其向某个方向平移或向相反方向平移的所有可能配对。因此，在理想条件下，我们只需要三角测量一个点即可确定正确的 $R, t$ 对。对于正确的 $R, t$ 对，三角测量的点 $\hat{P}$ 存在于两个相机的前方，这意味着它相对于两个相机参考系都具有正的z坐标。由于测量噪声，我们通常不依赖于仅三角测量一个点，而是将三角测量许多点，并确定正确的 $R, t$ 对，即包含最多这些点位于两个相机前方的那个对。

5. 一个运动恢复结构流程示例

在找到相对运动矩阵 $M_i$ 之后，我们可以用它们来确定点 $X_j$ 的世界坐标。对于代数方法，这些点的估计在透视变换 $H$ 的意义上是正确的。在从本质矩阵提取相机矩阵时，估计可以在尺度意义上已知。在这两种情况下，三维点都可以通过前面描述的三角测量方法从估计的相机矩阵计算出来。

可以通过链接成对的相机来扩展到多视图情况。我们可以使用代数方法或本质矩阵来获得任何一对相机的相机矩阵和三维点的解，前提是有足够的点对应关系。重建的三维点与相机对之间可用的点对应关系相关联。这些成对的解可以组合在一起（优化），采用一种称为光束法平差的方法，我们接下来会看到。

5.1 光束法平差 (Bundle Adjustment)

到目前为止我们讨论的解决运动恢复结构问题的方法存在一些主要局限性。分解方法假设所有点在每个图像中都可见。由于遮挡和在图像数量众多或某些图像拍摄距离较远时查找对应关系的失败，这种情况不太可能发生。最后，代数方法产生可以组合成相机链的成对解，但不能解决使用所有相机和三维点的连贯优化重建问题。

为了解决这些局限性，我们引入了光束法平差，这是一种解决运动恢复结构问题的非线性方法。在优化过程中，我们的目标是最小化重投影误差，即重建点投影到估计相机中的像素距离与其在所有相机和所有点上的对应观测值之间的距离。之前，在讨论三角测量的非线性优化方法时，我们主要关注双相机情况，在这种情况下，我们自然地假设每个相机都看到了两者之间的所有对应关系。然而，由于光束法平差处理多个相机，它仅计算每个相机可以看到的观测值的重投影误差。但最终，这个优化问题与我们讨论三角测量的非线性方法时引入的问题非常相似。

解决光束法平差的非线性优化的两种常用方法包括高斯-牛顿算法和Levenberg-Marquardt算法。您可以参考前面关于高斯-牛顿算法的详细信息部分，并参考Hartley and Zisserman教材以获取有关Levenberg-Marquardt算法的更多详细信息。

总之，与我们调查过的其他方法相比，光束法平差具有一些重要的优点和局限性。它特别有用，因为它可以平滑地处理大量视图，并且还可以处理特定点并非在每个图像中都可观察到的情况。然而，其主要局限性在于它是一个特别大的最小化问题，因为参数随视图数量的增加而增长。此外，由于它依赖于非线性优化技术，因此需要一个良好的初始条件。因此，光束法平差通常用作大多数运动恢复结构实现的最后一步（即在分解或代数方法之后），因为分解或代数方法可以为优化问题提供良好的初始解。

最后修改：2025 年 05 月 09 日

如果觉得我的文章对你有用，请随意赞赏

此处评论已关闭

翻译 CS231A 课程笔记 4：立体系统和运动恢复结构

Saber • 2025 年 05 月 09 日

<h2>1. 引言</h2>在之前的笔记中，我们介绍了如何通过增加场景的额外视点来显著增强我们对该场景的认知。我们重点讨论了对极几何的设置，以便在不提取任何关于三维场景信息的情况下，将一个像平面上的点与另一个像平面上的点关联起来。在这些课程笔记中，我们将讨论如何从多个二维图像中恢复关于三维场景的信息。<h2>2. 三角测量</h2>多视图几何中最基本的问题之一是三角测量问题，即在给定一个三维点在两个或多个图像中的投影的情况下，确定该三维点位置的过程。<img src="https://acsaber.cn/usr/uploads/2025/05/1022539900.png" alt="图1：给定两个视图时的三角测量问题设置" title="图1：给定两个视图时的三角测量问题设置"style="">在具有两个视图的三角测量问题中，我们有两个相机，其已知的相机内参分别为 $K$ 和 $K^{\prime}$。我们也知道这两个相机之间相对的旋转和平移 $R, T$。假设在三维空间中有一个点 $P$，它在两个相机的图像中分别位于 $p$ 和 $p^{\prime}$。尽管 $P$ 的位置当前未知，但我们可以测量图像中 $p$ 和 $p^{\prime}$ 的精确位置。因为 $K, K^{\prime}, R, T$ 是已知的，我们可以计算出由相机中心 $O_{1}$、$O_{2}$ 和图像位置 $p$、$p^{\prime}$ 定义的两条视线 $l$ 和 $l^{\prime}$。因此，$P$ 可以计算为 $l$ 和 $l^{\prime}$ 的交点。<img src="https://acsaber.cn/usr/uploads/2025/05/2909465815.png" alt="图2：现实世界场景中的三角测量问题通常涉及最小化重投影误差" title="图2：现实世界场景中的三角测量问题通常涉及最小化重投影误差"style="">尽管这个过程看起来既直接又数学上合理，但在实践中效果并不理想。在现实世界中，由于观测值 $p$ 和 $p^{\prime}$ 存在噪声，并且相机标定参数不精确，寻找 $l$ 和 $l^{\prime}$ 的交点可能会有问题。在大多数情况下，交点可能根本不存在，因为两条线可能永远不会相交。<h3>2.1 三角测量的线性方法</h3>在本节中，我们描述一种简单的线性三角测量方法，该方法解决了光线之间缺少交点的问题。给定图像中相互对应的两个点 $p=MP=(x,y,1)$ 和 $p^{\prime}=M^{\prime}P=(x^{\prime},y^{\prime},1)$。根据叉积的定义，$p \times (MP) = 0$。我们可以明确地使用叉积生成的等式来形成三个约束条件：$$x(M_{3}P)-(M_{1}P)=0$$ $$y(M_{3}P)-(M_{2}P)=0$$ $$x(M_{2}P)-y(M_{1}P)=0 \quad (2.1)$$其中 $M_{i}$ 是矩阵 $M$ 的第 $i$ 行。对于 $p^{\prime}$ 和 $M^{\prime}$ 也可以形成类似的约束。利用来自两个图像的约束，我们可以构建一个形如 $AP=0$ 的线性方程，其中$$A=\begin{bmatrix}xM_{3}-M_{1}\\ yM_{3}-M_{2}\\ x^{\prime}M^{\prime}_{3}-M^{\prime}_{1}\\ y^{\prime}M^{\prime}_{3}-M^{\prime}_{2}\end{bmatrix} \quad (2.2)$$该方程可以使用SVD求解，以找到点 $P$ 的最佳线性估计。该方法的另一个有趣的方面是它实际上也可以处理从多个视图进行的三角测量。为此，只需向 $A$ 中附加由新视图增加的约束对应的额外行即可。然而，这种方法不适用于投影重建，因为它不是投影不变的。例如，假设我们将相机矩阵 $M, M^{\prime}$ 替换为受投影变换 $MH^{-1}, M^{\prime}H^{-1}$ 影响的矩阵。线性方程组的矩阵 $A$ 则变为 $AH^{-1}$。因此，先前估计 $AP=0$ 的解 $P$ 将对应于变换后问题 $(AH^{-1})(HP)=0$ 的解 $HP$。回想一下，SVD求解的约束是 $||P||=1$，这在投影变换 $H$ 下不是不变的。因此，这种方法虽然简单，但通常不是三角测量问题的最优解。<h3>2.2 三角测量的非线性方法</h3>相反，现实世界场景中的三角测量问题通常在数学上被描述为解决一个最小化问题：$$\min_{\hat{P}}||M\hat{P}-p||^{2}+||M^{\prime}\hat{P}-p^{\prime}||^{2} \quad (2.3)$$在上述等式中，我们寻求在三维空间中找到一个 $\hat{P}$，通过在两个图像中找到 $\hat{P}$ 的重投影误差的最佳最小二乘估计来最好地逼近 $P$。三维点在图像中的重投影误差是指该点在图像中的投影与图像中相应观测点之间的距离。在我们图2的例子中，由于 $M$ 是从三维空间到图像1的投影变换，因此 $P$ 在图像1中的投影点是 $MP$。图像1中 $\hat{P}$ 的匹配观测值是 $p$。因此，点 $P$ 在图像1中的重投影误差是距离 $||MP-p||$。等式2.3中找到的总重投影误差是图像中所有点的重投影误差之和。对于超过两个图像的情况，我们只需向目标函数添加更多的距离项：$$\min_{\hat{P}}\sum_{i}||M\hat{P}_{i}-p_{i}||^{2} \quad (2.4)$$在实践中，存在各种非常复杂的优化技术，可以很好地逼近该问题。然而，在本课程的范围内，我们将只关注其中一种技术，即用于非线性最小二乘的高斯-牛顿算法。一般的非线性最小二乘问题是找到一个 $x \in \mathbb{R}^{n}$ 来最小化$$||r(x)||^{2}=\sum_{i=1}^{m}r_{i}(x)^{2} \quad (2.5)$$其中 $r$ 是任何残差函数 $r:\mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$，使得对于某个函数 $f$ 输入和观测值 $y$，$r(x)=f(x)-y$。当函数 $f$ 是线性时，非线性最小二乘问题简化为常规的线性最小二乘问题。然而，回想一下，一般来说，我们的相机矩阵不是仿射的。由于投影到像平面通常涉及除以齐次坐标，因此投影到图像通常是非线性的。注意，如果我们将 $e_{i}$ 设置为一个 $2 \times 1$ 的向量 $e_{i}=M\hat{P}_{i}-p_{i}$，那么我们可以将我们的优化问题重新表述为：$$\min_{\hat{P}}\sum_{i}e_{i}(\hat{P})^{2} \quad (2.6)$$这可以完美地表示为一个非线性最小二乘问题。在这些笔记中，我们将介绍如何使用流行的高斯-牛顿算法来找到这个非线性最小二乘问题的近似解。首先，让我们假设我们对三维点 $\hat{P}_{i}$ 有一个合理的估计，我们可以通过先前的线性方法计算出来。高斯-牛顿算法的关键思想是通过将其校正到最小化重投影误差的更好估计来更新我们的估计。在每一步，我们都希望通过某个 $\delta_{P}$ 来更新我们的估计 $\hat{P}$：$\hat{P} = \hat{P} + \delta_{P}$。但是我们如何选择更新参数 $\delta_{P}$ 呢？高斯-牛顿算法的关键思想是在当前估计 $\hat{P}$ 附近线性化残差函数。在我们的问题中，这意味着点 $P$ 的残差误差 $e$ 可以被认为是：$$e(\hat{P}+\delta_{P})\approx e(\hat{P})+\frac{\partial e}{\partial P}\delta_{P} \quad (2.7)$$随后，最小化问题转化为$$\min_{\delta_{P}}||\frac{\partial e}{\partial P}\delta_{P}-(-e(\hat{P}))||^{2} \quad (2.8)$$当我们这样表述残差时，我们可以看到它采用了标准线性最小二乘问题的格式。对于具有 $N$ 个图像的三角测量问题，线性最小二乘解是$$\delta_{P}=-(J^{T}J)^{-1}J^{T}e \quad (2.9)$$其中$$e=\begin{bmatrix}e_{1}\\ \vdots\\ e_{N}\end{bmatrix}=\begin{bmatrix}p_{1}-M_{1}\hat{P}\\ \vdots\\ p_{N}-M_{N}\hat{P}\end{bmatrix} \quad (2.10)$$和$$J=\begin{bmatrix}\frac{\partial e_{1}}{\partial P_{1}}&amp;\frac{\partial e_{1}}{\partial P_{2}}&amp;\frac{\partial e_{1}}{\partial P_{3}}\\ \vdots&amp;\vdots&amp;\vdots\\ \frac{\partial e_{N}}{\partial P_{1}}&amp;\frac{\partial e_{N}}{\partial P_{2}}&amp;\frac{\partial e_{N}}{\partial P_{3}}\end{bmatrix} \quad (2.11)$$回想一下，特定图像的残差误差向量 $e_{i}$ 是一个 $2 \times 1$ 的向量，因为像平面中有两个维度。因此，在最简单的双相机情况 $(N=2)$ 的三角测量中，这将导致残差向量 $e$ 是一个 $2N \times 1 = 4 \times 1$ 的向量，雅可比矩阵 $J$ 是一个 $2N \times 3 = 4 \times 3$ 的矩阵。请注意这种方法如何无缝地处理多个视图，因为通过向 $e$ 向量和 $J$ 矩阵添加相应的行来考虑其他图像。在计算更新 $\delta_{P}$ 之后，我们可以简单地重复该过程固定的步数或直到其数值收敛。高斯-牛顿算法的一个重要特性是，我们关于残差函数在估计附近是线性的假设并不能保证收敛。因此，在实践中，对估计的更新次数设置上限总是有用的。<h2>3. 运动恢复仿射结构</h2>在上一节的末尾，我们暗示了如何超越场景的两个视图来获取关于三维场景的信息。我们现在将探讨将双摄像头几何结构扩展到多摄像头。通过组合来自多个视图的点观测值，我们将能够同时确定场景的三维结构和相机的参数，这被称为运动恢复结构 (Structure from Motion, SfM)。<img src="https://acsaber.cn/usr/uploads/2025/05/4057281683.png" alt="图3：一般运动恢复结构问题的设置" title="图3：一般运动恢复结构问题的设置"style="">在这里，我们正式介绍运动恢复结构问题。假设我们有 $m$ 个相机，其相机变换 $M_{i}$ 编码了相机的内参和外参。设 $X_{j}$ 是场景中 $n$ 个三维点之一。每个三维点可能在多个相机中可见，其位置为 $x_{ij}$，这是使用投影变换 $M_{i}$ 将 $X_{j}$ 投影到相机 $i$ 的图像的结果。运动恢复结构的目的是从所有观测值 $x_{ij}$ 中恢复场景的结构（$n$ 个三维点 $X_{j}$）和相机的运动（$m$ 个投影矩阵 $M_{i}$）。<h3>3.1 运动恢复仿射结构问题</h3>在解决一般的运动恢复结构问题之前，我们将首先从一个更简单的问题开始，该问题假设相机是仿射或弱透视的。最终，透视缩放操作的缺乏使得这个问题的数学推导更容易。之前，我们推导了透视和弱透视情况的上述方程。请记住，在完整的透视模型中，相机矩阵定义为$$M=\begin{bmatrix}A&amp;b\\ v&amp;1\end{bmatrix} \quad (3.1)$$其中 $v$ 是某个非零的 $1 \times 3$ 向量。另一方面，对于弱透视模型，$v=0$。我们发现这个特性使得 $MX$ 的齐次坐标等于1：$$x=MX=\begin{bmatrix}m_{1}\\ m_{2}\\ 0 \ 0 \ 1\end{bmatrix}\begin{bmatrix}X_{1}\\ X_{2}\\ X_{3}\\ 1\end{bmatrix}=\begin{bmatrix}m_{1}X\\ m_{2}X\\ 1\end{bmatrix} \quad (3.2)$$因此，当我们从齐次坐标移动到欧几里得坐标时，投影变换的非线性消失了，弱透视变换仅仅充当放大镜的角色。我们可以更紧凑地表示投影为：$$\begin{bmatrix}m_{1}X\\ m_{2}X\end{bmatrix}=\begin{bmatrix}A&amp;b\end{bmatrix}X=AX+b \quad (3.3)$$并以 $M_{\text{affine}}=\begin{bmatrix}A&amp;b\end{bmatrix}$ 的格式表示任何相机矩阵。因此，我们现在使用仿射相机模型来表示三维空间中的点 $X_{j}$ 与每个仿射相机中相应观测值（例如，相机 $i$ 中的 $x_{ij}$）之间的关系。回到运动恢复结构问题，我们需要估计 $m$ 个矩阵 $M_{i}$ 和 $n$ 个世界坐标向量 $X_{j}$，总共有 $8m+3n$ 个未知数，来自于 $mn$ 个观测值。每个观测值每个相机产生2个约束，因此在 $8m+3n$ 个未知数中有 $2mn$ 个方程。我们可以使用这个方程来了解我们需要的每个图像中相应观测值的数量下限。例如，如果我们有 $m=2$ 个相机，那么我们至少需要 $n=16$ 个三维点。然而，一旦我们在每个图像中标记了足够多的对应点，我们如何解决这个问题呢？<h3>3.2 Tomasi 和 Kanade 的分解方法</h3>在这一部分，我们概述了Tomasi和Kanade用于解决运动恢复仿射结构问题的分解方法。该方法包括两个主要步骤：数据中心化步骤和实际分解步骤。(图4：应用中心化步骤时，我们平移所有图像点，使其质心（表示为左下角的红色十字）位于像平面的原点。类似地，我们放置世界坐标系，使原点位于三维点的质心（表示为右上角的红色十字）。)让我们从数据中心化步骤开始。在此步骤中，主要思想是将数据中心化到原点。为此，对于每个图像 $i$，我们通过减去它们的质心 $\overline{x}_{i}$ 来为每个图像点 $x_{ij}$ 重新定义新的坐标 $\hat{x}_{ij}$：$$\hat{x}_{ij}=x_{ij}-\overline{x}_{i}=x_{ij}-\frac{1}{n}\sum_{j=1}^{n}x_{ij} \quad (3.4)$$回想一下，运动恢复仿射结构问题允许我们定义图像点 $x_{ij}$、相机矩阵变量 $A_{i}$ 和 $b_{i}$ 以及三维点 $X_{j}$ 之间的关系为：$$x_{ij}=A_{i}X_{j}+b_{i} \quad (3.5)$$在此中心化步骤之后，我们可以组合等式3.4中中心化图像点 $\hat{x}_{ij}$ 的定义和等式3.5中的仿射表达式：$$\hat{x}_{ij}=x_{ij}-\frac{1}{n}\sum_{k=1}^{n}x_{ik}$$ $$=A_{i}X_{j}-\frac{1}{n}\sum_{k=1}^{n}A_{i}X_{k}$$ $$=A_{i}(X_{j}-\frac{1}{n}\sum_{k=1}^{n}X_{k})$$ $$=A_{i}(X_{j}-\overline{X})$$ $$=A_{i}\hat{X}_{j} \quad (3.6)$$从等式3.6可以看出，如果我们将世界参考系的原点平移到质心 $\overline{X}$，那么图像点的中心化坐标 $\hat{x}_{ij}$ 和三维点的中心化坐标 $\hat{X}_{j}$ 仅通过一个 $2 \times 3$ 的矩阵 $A_{i}$ 相关联。最终，分解方法的中心化步骤允许我们创建一个紧凑的矩阵乘积表示，以将三维结构与其在多个图像中的观测点联系起来。然而，请注意，在矩阵乘积 $\hat{x}_{ij}=A_{i}\hat{X}_{j}$ 中，我们只能访问等式左侧的值。因此，我们必须以某种方式分解出运动矩阵 $A_{i}$ 和结构 $X_{j}$。利用所有相机的所有观测值，我们可以构建一个测量矩阵 $D$，它由 $m$ 个相机中的 $n$ 个观测值组成（请记住，每个 $\hat{x}_{ij}$ 条目都是一个 $2 \times 1$ 的向量）：$$D=\begin{bmatrix}\hat{x}_{11}&amp;\hat{x}_{12}&amp;...&amp;\hat{x}_{1n}\\ \hat{x}_{21}&amp;\hat{x}_{22}&amp;...&amp;\hat{x}_{2n}\\ &amp;\vdots&amp;\\ \hat{x}_{m1}&amp;\hat{x}_{m2}&amp;...&amp;\hat{x}_{mn}\end{bmatrix} \quad (3.7)$$现在回想一下，由于我们的仿射假设，$D$ 可以表示为 $2m \times 3$ 运动矩阵 $M$（包含相机矩阵 $A_{1}, \dots, A_{m}$）和 $3 \times n$ 结构矩阵 $S$（包含三维点 $X_{1}, \dots, X_{n}$）的乘积。我们将使用的一个重要事实是 $rank(D)=3$，因为 $D$ 是两个最大维度为3的矩阵的乘积。为了将 $D$ 分解为 $M$ 和 $S$，我们将使用奇异值分解 $D=U\Sigma V^{T}$。由于我们知道 $rank(D)=3$，因此 $\Sigma$ 中只有3个非零奇异值 $\sigma_{1}, \sigma_{2}$ 和 $\sigma_{3}$。因此，我们可以进一步简化表达式并获得以下分解：$$D=U\Sigma V^{T}$$ $$= \begin{bmatrix} u_{1} &amp; \dots &amp; u_{m} \end{bmatrix} \begin{bmatrix} \sigma_{1} &amp; 0 &amp; 0 &amp; 0 &amp; \dots &amp; 0 \\ 0 &amp; \sigma_{2} &amp; 0 &amp; 0 &amp; \dots &amp; 0 \\ 0 &amp; 0 &amp; \sigma_{3} &amp; 0 &amp; \dots &amp; 0 \\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; \dots &amp; 0 \\ \vdots &amp; \vdots &amp; \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; \dots &amp; 0 \end{bmatrix} \begin{bmatrix} v_{1}^{T} \\ v_{2}^{T} \\ v_{3}^{T} \\ \vdots \\ v_{n}^{T} \end{bmatrix}$$ $$= \begin{bmatrix} u_{1} &amp; u_{2} &amp; u_{3} \end{bmatrix} \begin{bmatrix} \sigma_{1} &amp; 0 &amp; 0 \\ 0 &amp; \sigma_{2} &amp; 0 \\ 0 &amp; 0 &amp; \sigma_{3} \end{bmatrix} \begin{bmatrix} v_{1}^{T} \\ v_{2}^{T} \\ v_{3}^{T} \end{bmatrix}$$ $$= U_{3}\Sigma_{3}V_{3}^{T} \quad (3.8)$$在此分解中，$\Sigma_{3}$ 定义为由非零奇异值形成的对角矩阵，而 $U_{3}$ 和 $V_{3}^{T}$ 分别通过取 $U$ 的相应三列和 $V^{T}$ 的行获得。不幸的是，在实践中，由于测量噪声和仿射相机近似，$rank(D)&gt;3$。然而，回想一下，当 $rank(D)&gt;3$ 时，$U_{3}\Sigma_{3}V_{3}^{T}$ 仍然是 $MS$ 在 Frobenius 范数意义下的最佳秩-3 近似。仔细检查后，我们发现矩阵乘积 $\Sigma_{3}V_{3}^{T}$ 形成一个 $3 \times n$ 矩阵，其大小与结构矩阵 $S$ 完全相同。类似地，$U_{3}$ 是一个 $2m \times 3$ 矩阵，其大小与运动矩阵 $M$ 相同。虽然这种将 SVD 分解的组件与 $M$ 和 $S$ 相关联的方式导致了运动恢复仿射结构问题的物理和几何上合理的解，但这种选择不是唯一的解。例如，我们也可以将运动矩阵设置为 $M=U_{3}\Sigma_{3}$，将结构矩阵设置为 $S=V_{3}^{T}$，因为在任何一种情况下，观测矩阵 $D$ 都是相同的。那么我们选择哪种分解呢？在他的论文中，Tomasi 和 Kanade 得出结论，一种稳健的分解选择是 $M=U_{3}\sqrt{\Sigma_{3}}$ 和 $S=\sqrt{\Sigma_{3}}V_{3}^{T}$。<h3>3.3 重建中的模糊性</h3>然而，我们在任何分解 $D=MS$ 的选择中都发现固有的模糊性，因为任何任意可逆的 $3 \times 3$ 矩阵 $A$ 都可以插入到分解中：$$D=MAA^{-1}S=(MA)(A^{-1}S) \quad (3.9)$$这意味着从运动 $M$ 获得的相机矩阵和从结构 $S$ 获得的三维点是在乘以一个共同矩阵 $A$ 的意义上确定的。因此，我们的解是欠定的，需要额外的约束来解决这种仿射模糊性。当重建具有仿射模糊性时，这意味着平行性得以保留，但度量尺度未知。重建的另一类重要模糊性是相似性模糊，当重建在相似性变换（旋转、平移和缩放）的意义上是正确的时候发生。仅具有相似性模糊的重建称为度量重建。即使相机经过内部校准，这种模糊性也存在。好消息是，对于已校准的相机，相似性模糊是唯一的模糊性¹。从图像中无法恢复场景的绝对尺度这一事实是相当直观的。除非我们做出进一步的假设（例如，我们知道图中房子的高度）或整合更多数据，否则物体的尺度、绝对位置和规范方向将始终是未知的。这是因为某些属性可能会补偿其他属性。例如，为了获得相同的图像，我们可以简单地将对象向后移动并相应地缩放它。消除相似性模糊的一个这样的例子发生在相机标定过程中，当时我们假设我们知道标定点相对于世界参考系的位置。这使我们能够知道棋盘格方块的大小，从而学习三维结构的度量尺度。¹有关更多详细信息，请参阅 [Longuet-Higgins ’81]。<h2>4. 运动恢复透视结构</h2>在研究了简化的运动恢复仿射结构问题之后，让我们现在考虑投影相机 $M_i$ 的一般情况。在一般情况下，每个投影相机矩阵 $M_i$ 包含11个自由度，因为它是按比例定义的：$$M_i = \begin{bmatrix} a11 &amp; a12 &amp; a13 &amp; b1 \\ a21 &amp; a22 &amp; a23 &amp; b2 \\ a31 &amp; a32 &amp; a33 &amp; 1 \end{bmatrix} \quad (4.1)$$此外，与仿射情况类似（其中解可以在仿射变换的意义上找到），在一般情况下，结构和运动的解可以在投影变换的意义上确定：我们总是可以将一个 $4 \times 4$ 的投影变换 $H$ 任意地应用于运动矩阵，只要我们也通过逆变换 $H^{-1}$ 变换结构矩阵即可。像平面上的最终观测结果将保持不变。与仿射情况类似，我们可以将一般的运动恢复结构问题设置为从 $mn$ 个观测值 $x_{ij}$ 估计 $m$ 个运动矩阵 $M_i$ 和 $n$ 个三维点 $X_j$。由于相机和点只能恢复到一个 $4 \times 4$ 的投影变换（最多15个参数），我们有 $11m + 3n - 15$ 个未知数和 $2mn$ 个方程。根据这些事实，我们可以确定解决未知数所需的视图和观测值的数量。<h3>4.1 代数方法</h3>(图5：在代数方法中，我们考虑顺序的相机对来确定相机矩阵 $M_1$ 和 $M_2$（相差一个透视变换）。然后我们找到一个透视变换 $H$ 使得 $M_1H = [I \ 0]$ 和 $M_2H = [A \ B]$。)我们现在将介绍代数方法，该方法利用基本矩阵 $F$ 的概念来解决两个相机的运动恢复结构问题。如图5所示，代数方法的主要思想是计算两个相机矩阵 $M_1$ 和 $M_2$，这两个矩阵只能计算到一个透视变换 $H$。由于每个 $M_i$ 只能计算到一个透视变换 $H$，我们可以总是考虑一个 $H$ 使得第一个相机投影矩阵 $M_1H^{-1}$ 是规范的。当然，相同的变换也必须应用于第二个相机，从而得到如下形式：$$M_1H^{-1} = [I \ 0] \quad M_2H^{-1} = [A \ b] \quad (4.2)$$为了完成这项任务，我们必须首先使用前述课程笔记中介绍的八点算法计算基本矩阵 $F$。我们现在将使用 $F$ 来估计投影相机矩阵 $M_1$ 和 $M_2$。为了进行此估计，我们将 $P$ 定义为图像中对应观测值 $p$ 和 $p^{\prime}$ 的对应三维点。由于我们已将 $H^{-1}$ 应用于两个相机投影矩阵，因此我们也必须将 $H$ 应用于结构，从而得到 $P_e = HP$。因此，我们可以将像素坐标 $p$ 和 $p^{\prime}$ 与变换后的结构关联如下：$$p = M_1P = M_1H^{-1}HP = [I | 0]P_e$$ $$p^{\prime} = M_2P = M_2H^{-1}HP = [A | b]P_e \quad (4.3)$$通过一些创造性的替换，两个图像对应点 $p$ 和 $p^{\prime}$ 之间出现了一个有趣的特性：$$p^{\prime} = [A|b]P_e$$ $$= A[I|0]P_e + b$$ $$= Ap + b \quad (4.4)$$使用等式4.4，我们可以将 $p^{\prime}$ 和 $b$ 之间的叉积写为：$$p^{\prime} \times b = (Ap + b) \times b = Ap \times b \quad (4.5)$$根据叉积的定义，$p^{\prime} \times b$ 垂直于 $p^{\prime}$。因此，我们可以写成：$$0 = p^{\prime T}(p^{\prime} \times b)$$ $$= p^{\prime T}(Ap \times b)$$ $$= p^{\prime T} \cdot (b \times Ap)$$ $$= p^{\prime T}[b]_{\times}Ap \quad (4.6)$$看这个约束，它应该让你想起基本矩阵的一般定义 $p^{\prime T}Fp = 0$。如果我们设置 $F = [b]_{\times}A$，那么提取 $A$ 和 $b$ 就简化为一个分解问题。让我们从确定 $b$ 开始。再次使用叉积的定义，我们可以写成，$$F^{\top}b = [[b]_{\times}A]^{\top}b = 0 \quad (4.7)$$由于 $F$ 是奇异的，$b$ 可以作为 $F^{\top}b = 0$ 的最小二乘解来计算，其中 $||b|| = 1$，使用SVD。一旦 $b$ 已知，我们现在可以计算 $A$。如果我们设置 $A = -[b]_{\times}F$，那么我们可以验证这个定义满足 $F = [b]_{\times}A$：$$[b_{\times}]A = -[b_{\times}][b_{\times}]F$$ $$= (bb^T - |b|^2I)F$$ $$= bb^TF + |b|^2F$$ $$= 0 + 1 \cdot F$$ $$= F \quad (4.8)$$因此，我们确定了相机矩阵 $M_1H^{-1}$ 和 $M_2H^{-1}$ 的两个表达式：$$\tilde{M}_{1} = [I \ 0] \quad \tilde{M}_{2} = [-[b_{\times}]F \ b] \quad (4.9)$$在结束本节之前，我们想给出 $b$ 的几何解释。我们知道 $b$ 满足 $F b = 0$。回想一下我们在前述课程笔记中推导的对极约束，它发现图像中的对极点是当被基本矩阵变换时映射到零的点（即 $Fe_2 = 0$ 和 $F^Te_1 = 0$）。因此，我们可以看到 $b$ 是一个对极点。这为相机投影矩阵提供了一组新的方程（等式4.10）。$$\tilde{M}_{1} = [I \ 0] \quad \tilde{M}_{2} = [-[e_{\times}]F \ e] \quad (4.10)$$<h3>4.2 从本质矩阵确定运动</h3>改进通过代数方法获得的重建的一种有用方法是使用已校准的相机。通过使用本质矩阵 $E$（它是归一化坐标下基本矩阵的特例），我们可以提取更准确的相机矩阵初始估计。回想一下，通过使用本质矩阵 $E$，我们假设我们已经校准了相机，因此知道相机内参矩阵 $K$。我们可以直接从归一化图像坐标计算本质矩阵 $E$，也可以从其与基本矩阵 $F$ 和内参矩阵 $K$ 的关系计算：$$E = K^TFK \quad (4.11)$$因为本质矩阵假设我们有已校准的相机，我们应该记住它只有五个自由度，因为它只编码外参：相机之间的旋转 $R$ 和平移 $t$。幸运的是，这正是我们想要提取以创建运动矩阵的信息。首先，回想一下本质矩阵 $E$ 可以表示为$$E = [t]_{\times}R \quad (4.12)$$因此，也许我们可以找到一种策略将 $E$ 分解为其两个分量。首先，我们应该注意到叉积矩阵 $[t]_{\times}$ 是反对称的。我们定义将在分解中使用的两个矩阵：$$W = \begin{bmatrix} 0 &amp; -1 &amp; 0 \\ 1 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; 1 \end{bmatrix} , \quad Z = \begin{bmatrix} 0 &amp; 1 &amp; 0 \\ -1 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; 0 \end{bmatrix} \quad (4.13)$$稍后我们将使用的一个重要特性是 $Z = \text{diag}(1, 1, 0)W$（相差一个符号）。类似地，我们还将使用 $ZW = ZW^T = \text{diag}(1, 1, 0)$（相差一个符号）这一事实。作为 Jordan 分解的结果，我们可以创建一个已知到尺度的一般反对称矩阵的块分解。因此，我们可以将 $[t]_{\times}$ 写为$$[t]_{\times} = UZU^T \quad (4.14)$$其中 $U$ 是某个正交矩阵。因此，我们可以将分解重写为：$$E = U\text{diag}(1, 1, 0)(W U^TR) \quad (4.15)$$仔细观察这个表达式，我们发现它与奇异值分解 $E = U\Sigma V^T$ 非常相似，其中 $\Sigma$ 包含两个相等的奇异值。如果我们知道 $E$（相差一个尺度），并且假设它具有形式 $E = U\text{diag}(1, 1, 0)V^T$，那么我们得到 $E$ 的以下分解：$$[t]_{\times} = UZU^T , \quad R = UW V^T \text{ or } UW^T V^T \quad (4.16)$$我们可以通过检查来证明给定的分解是有效的。我们也可以证明没有其他分解。$[t]_{\times}$ 的形式由其左零空间必须与 $E$ 的零空间相同这一事实决定。给定酉矩阵 $U$ 和 $V$，任何旋转 $R$ 都可以分解为 $UXV^T$，其中 $X$ 是另一个旋转矩阵。代入这些值后，我们得到 $ZX = \text{diag}(1, 1, 0)$（相差一个尺度）。因此，$X$ 必须等于 $W$ 或 $W^T$。请注意，对 $E$ 的这种分解仅保证矩阵 $UW V^T$ 或 $UW^T V^T$ 是正交的。为了确保 $R$ 是有效的旋转，我们只需确保 $R$ 的行列式为正：$$R = (\det UW V^T)UW V^T \text{ or } (\det UW^T V^T)UW^T V^T \quad (4.17)$$与旋转 $R$ 可以取两个可能值类似，平移向量 $t$ 也可以取多个值。根据叉积的定义，我们知道$$t \times t = [t]_{\times}t = UZU^Tt = 0 \quad (4.18)$$知道 $U$ 是酉矩阵，我们可以发现 $||[t]_{\times}||_F = \sqrt{2}$。因此，我们从此分解中对 $t$ 的估计将来自上述方程以及 $E$ 已知到一个尺度这一事实。这意味着$$t = \pm U \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} = \pm u_3 \quad (4.19)$$其中 $u_3$ 是 $U$ 的第三列。通过检查，我们还可以验证通过将 $[t]_{\times} = UZU^T$ 重新格式化为已知到一个符号的向量 $t$ 可以得到相同的结果。(图6：从本质矩阵中提取相对相机旋转 $R$ 和平移 $t$ 有四种可能的解。然而，只有在 (a) 中，重建的点位于两个相机的前方。(图取自Hartley and Zisserman 教材第260页))如图6所示，由于 $R$ 和 $t$ 都有两个选项，因此存在四个潜在的 $R, t$ 配对。直观地说，这四个配对包括将相机向某个方向旋转或向相反方向旋转，并结合将其向某个方向平移或向相反方向平移的所有可能配对。因此，在理想条件下，我们只需要三角测量一个点即可确定正确的 $R, t$ 对。对于正确的 $R, t$ 对，三角测量的点 $\hat{P}$ 存在于两个相机的前方，这意味着它相对于两个相机参考系都具有正的z坐标。由于测量噪声，我们通常不依赖于仅三角测量一个点，而是将三角测量许多点，并确定正确的 $R, t$ 对，即包含最多这些点位于两个相机前方的那个对。<h2>5. 一个运动恢复结构流程示例</h2>在找到相对运动矩阵 $M_i$ 之后，我们可以用它们来确定点 $X_j$ 的世界坐标。对于代数方法，这些点的估计在透视变换 $H$ 的意义上是正确的。在从本质矩阵提取相机矩阵时，估计可以在尺度意义上已知。在这两种情况下，三维点都可以通过前面描述的三角测量方法从估计的相机矩阵计算出来。可以通过链接成对的相机来扩展到多视图情况。我们可以使用代数方法或本质矩阵来获得任何一对相机的相机矩阵和三维点的解，前提是有足够的点对应关系。重建的三维点与相机对之间可用的点对应关系相关联。这些成对的解可以组合在一起（优化），采用一种称为光束法平差的方法，我们接下来会看到。<h3>5.1 光束法平差 (Bundle Adjustment)</h3>到目前为止我们讨论的解决运动恢复结构问题的方法存在一些主要局限性。分解方法假设所有点在每个图像中都可见。由于遮挡和在图像数量众多或某些图像拍摄距离较远时查找对应关系的失败，这种情况不太可能发生。最后，代数方法产生可以组合成相机链的成对解，但不能解决使用所有相机和三维点的连贯优化重建问题。为了解决这些局限性，我们引入了光束法平差，这是一种解决运动恢复结构问题的非线性方法。在优化过程中，我们的目标是最小化重投影误差，即重建点投影到估计相机中的像素距离与其在所有相机和所有点上的对应观测值之间的距离。之前，在讨论三角测量的非线性优化方法时，我们主要关注双相机情况，在这种情况下，我们自然地假设每个相机都看到了两者之间的所有对应关系。然而，由于光束法平差处理多个相机，它仅计算每个相机可以看到的观测值的重投影误差。但最终，这个优化问题与我们讨论三角测量的非线性方法时引入的问题非常相似。解决光束法平差的非线性优化的两种常用方法包括高斯-牛顿算法和Levenberg-Marquardt算法。您可以参考前面关于高斯-牛顿算法的详细信息部分，并参考Hartley and Zisserman教材以获取有关Levenberg-Marquardt算法的更多详细信息。总之，与我们调查过的其他方法相比，光束法平差具有一些重要的优点和局限性。它特别有用，因为它可以平滑地处理大量视图，并且还可以处理特定点并非在每个图像中都可观察到的情况。然而，其主要局限性在于它是一个特别大的最小化问题，因为参数随视图数量的增加而增长。此外，由于它依赖于非线性优化技术，因此需要一个良好的初始条件。因此，光束法平差通常用作大多数运动恢复结构实现的最后一步（即在分解或代数方法之后），因为分解或代数方法可以为优化问题提供良好的初始解。