科研
我的工作

一时苦难

# 复杂区域的三维模型快速重建

# 一、完成的内容

本系统旨在研究基于特征点提取和匹配的三维重建方法，利用多张图像中的特征点信息，恢复物体或场景的三维几何结构。本系统主要完成了以下内容：

• 调研了国内外相关领域的研究现状和发展趋势，分析了三维重建的基本原理和关键技术，总结了三维重建的常用方法和评价指标。

• 设计并实现了一个基于特征点提取和匹配的三维重建系统，包括特征检测、描述、匹配、去噪、相机标定、姿态计算、三维重建、优化、稠密重建和纹理重建等模块。

• 在公开数据集上对所提出的系统进行了测试和评估，与其他三维重建方法进行了对比分析，验证了所提出方法的有效性和优越性。

# 二、所采用的方法以及取得的成果

SfM 是将 3D 结构从其投影重建为一系列从不同视点拍摄的图像的过程。增量 SfM（在本文中表示为 SfM）是一种具有迭代重建组件的顺序处理流水线。它通常从特征提取和匹配开始，然后是几何验证。生成的场景图作为重建阶段的基础，在逐步注册新图像、三角测量场景点、过滤异常值并使用束调整 (BA) 改进重建之前，该阶段使用精心选择的双视图重建为模型播种。以下介绍我们系统所采用的的方法，以及取得的成果。

相机标定

相机标定的过程是指通过一些已知的几何信息，来求解相机的内部参数，从而建立三维空间点和二维图像点之间的对应关系。

一般来说，相机标定的步骤如下：

准备一个标定物，通常是一个带有黑白棋盘格的平面，其角点的世界坐标系和图像坐标系是已知的。
用相机从不同的角度和位置拍摄标定物的照片，至少需要三张以上。
从照片中提取棋盘格的角点，得到每个角点在像素坐标系下的坐标。
根据相机成像模型，建立三维空间点和二维图像点之间的投影关系，利用单应矩阵、透视投影、畸变校正等方法，求解相机的内部参数。
利用最小二乘法或其他优化方法，对求解出的参数进行优化和误差分析。

对于相机内部参数，我们系统中提供优化相机内参的算法，即使不通过相机标定的步骤获得相机内部参数，我们系统也可以通过算法来估计得到相对准确的相机内部参数，若追求更好的更准确的三维模型，一般是手动进行相机标定，将相机内部参数作为固定值。

图像采集

SFM过程中的图像采集过程是指从多个角度拍摄同一场景的图片，并按序号进行保存，以便后续进行特征提取，匹配，重建等步骤。

图像的质量要高，清晰度要好，避免模糊，曝光过度或不足等问题。
图像的数量要适中，不要太少或太多，太少会导致重建不完整或不准确，太多会增加计算量和内存消耗。
图像的视角要有一定的重叠度，一般建议在60%~80%之间，以便提高特征匹配的成功率和稳定性。
图像的视角要有一定的视差，即相机之间的相对位姿要有足够的变化，以便恢复出三维结构。如果图像之间的视差太小，可能会导致奇异性或退化情况。
图像的拍摄环境要尽量保持一致，避免光照，阴影，反射等因素的干扰。同时，场景中的物体要尽量是静止的，避免动态物体的影响。

特征提取

SFM过程中的图像特征提取过程是指从图像中提取具有尺度和旋转不变性的特征点和描述子，以便后续进行特征匹配，计算基础矩阵，恢复相机位姿和三维结构等步骤。

以下红色点为我们提取的特征点

特征点的数量要适中，不要太少或太多，太少会导致匹配不稳定或失败，太多会增加计算量和内存消耗。
特征点的分布要均匀，不要集中在某些区域，以便提高匹配的鲁棒性和准确性。
特征点的描述子要具有较强的区分度，不要与其他特征点混淆，以便降低误匹配的概率。
特征点的类型要适合场景的特点，例如对于纹理丰富的场景，可以使用SIFT，SURF等特征点，对于纹理较少的场景，可以使用Harris，FAST等角点。

以下详细介绍我们采用的FAST角点。

构建高斯尺度空间，产生不同尺度的高斯模糊图像。

进行降采样，得到一系列尺寸不断缩小的图像，计算高斯差分函数。

G (x_{i}, y_{i}, σ) = \frac{1}{2 π σ^{2}} e x p (- (\frac{(x - x_{i})^{2} - (y - y_{i})^{2}}{2 σ^{2}}))

L (x, y, σ) = G (x, y, σ) * I (x, y)

DoG 空间极值检测：寻找 DoG 函数的极值点，每一个像素点和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。

确定特征向量主方向:通过每个极值点的梯度来为极值点赋予方向，梯度幅值等于上下两点像素值差的平方加上左右两点像素值差的平方，梯度方向则为上下两点像素值差与左右两点像素值差的商。

梯度幅值

m (x, y) = \sqrt{(L (x + 1, y) - L (x - 1, y))^{2} + (L (x, y + 1) - L (x, y - 1))^{2}}

梯度方向

θ (x, y) = t a n^{- 1} (\frac{L (x, y + 1) - L (x, y - 1)}{L (x + 1, y) - L (x - 1, y)})

计算特征向量

求取每个像素的梯度幅值与梯度方向，箭头方向代表该像素的梯度方向，长度代表梯度幅值，然后利用高斯窗口对其进行加权运算。在每个小块上绘制 8 个方向的梯度直方图，计算每个梯度方向的累加值。

最终每个小块获得4 ∗ 4 ∗ 8 = 128 维的特征向量

特征匹配

SFM过程中的图像特征匹配过程是指从两两相邻的图像中找出具有相同或相似特征的点对，以便后续进行基础矩阵，本质矩阵，单应矩阵的计算，恢复相机位姿和三维结构等步骤。

特征匹配的方法要适合特征点的类型和数量，可以使用暴力匹配，KD树，FLANN等方法。
特征匹配的结果要满足一一对应的原则，即一个特征点只能匹配到另一个图像中的一个特征点，不能出现多对一或一对多的情况。
特征匹配的结果要满足几何一致性的约束，即匹配点对之间要符合对极几何关系，可以使用基础矩阵或本质矩阵来检验和筛选。
特征匹配的结果要满足运动一致性的约束，即匹配点对之间要符合相机运动模型，可以使用单应矩阵来检验和筛选。

匹配结果如下

我们系统中提供多种图像匹配方式，顺序匹配，词汇树匹配，暴力匹配，GPS空间匹配。

顺序匹配

对于顺序采集的图像，可以采用这一种方式进行图像间的匹配。这一种的匹配过程为，将所有图像进行编号后，对于每一张图像，我们取它先前的10张图像进行一一匹配，与这10张图像分别建立图像匹配关系，以便后续步骤用。除此之外，我们增加一个回环检测策略，每隔一定图像数量后，对图像进行一次回环检测，也就说，这一次匹配的目标图像不仅是先前的10张，而是先前随机的N张，用这种策略与更久远的图像建立匹配关系，从而达到检测回环的功能。对于顺序匹配，可以很快速的完成所有图像的匹配，并且有一定的检测回环能力，对于追求快速，采集的图像是顺序序列，则可以采用这种方式进行图像匹配。

词汇树匹配

对于词汇树匹配，需要我们在进行三维重建之前，构建一个词汇树，该词汇树，指导系统进行匹配。简单来说，需要训练一个模型，该模型覆盖了本次进行三维重建的所有场景，以至于我们拍摄的图像，可以明确推理出该图像是属于哪一部分场景，进而将属于某一场景的所有图像进行互相匹配。这种方式的匹配过程较为精确，而且高效，因为仅仅是属于某一场景的图像才进行相互匹配，并不会把两张毫无相干的图像进行互相匹配来浪费时间。这种匹配方式的精度取决于词汇树的构建，词汇树模型构建的精确，则匹配精确。

暴力匹配

对于暴力匹配，最简单的方式为，两两图像进行匹配，但是这种方式性能很差，可以稍微改进一下。我们将其改为，分块匹配。将所有图像进行分块，对块和块之间的图像进行匹配。这种方式性能较差，若没有图像的额外信息，才会使用该方式进行图像匹配。

GPS空间匹配

对于GPS空间匹配，与词汇树匹配类似，利用GPS信息，确定图像某个具体范围位置，对存在于该范围的图像，我们进行两两匹配，对于无人机采集的图像，我们一般采用这种方式进行图像匹配。

构建场景图

使用一种图论的方法来表示和优化图像之间的匹配关系，从而提高重建的效率和质量。

构建场景图的目的是为了找出最优的图像对来进行三角化和位姿估计，避免使用冗余或错误的匹配信息。
构建场景图的方法是将所有图像看作一个无向图的节点，将两个图像之间的匹配点数或者重叠度看作边的权重，然后使用最小生成树算法（如Prim或Kruskal）来找出最大权重的边，形成一个连通且无环的子图。
构建场景图的过程可以分为两个阶段：第一个阶段是根据所有图像对之间的匹配点数或者重叠度来构建一个初始的最大生成树；第二个阶段是根据每个图像对之间的几何一致性（如基础矩阵或单应矩阵）来对初始的最大生成树进行修剪和优化，去除错误或不稳定的边。
构建场景图的结果是一个包含所有图像节点和部分匹配边的最大生成树，这个树可以用来指导后续的重建步骤，例如选择初始图像对，添加新的图像，进行局部或全局优化等。

由于增量式SfM（Structure from Motion，运动结构恢复）需要在每次添加图像后都进行一次局部或全局的捆绑调整（Bundle Adjustment），这会导致效率较低，而且由于误差累积，容易出现漂移问题。因此，我需要使用图论的方式来表示和优化图像之间的匹配关系，从而提高重建的效率和质量。具体来说，我可以将所有图像看作一个无向图的节点，将两个图像之间的匹配点数或者重叠度看作边的权重，然后使用最小生成树算法（如Prim或Kruskal）来找出最大权重的边，形成一个连通且无环的子图。这样，我就可以根据这个子图来指导后续的重建步骤，例如选择初始图像对，添加新的图像，进行局部或全局优化等。

我们的目标是使用图像的方式来重建三维模型，但是由于增量式的SfM算法效率较低，容易出现误差累积和漂移问题，所以你需要对图像之间的匹配关系进行优化。我们的思路是使用图论的方法，将图像间的匹配关系表示为一个无向图，其中每个顶点代表一张图像，每条边代表两张图像之间存在共同的可见区域。然后你将使用最大生成树算法，从这个无向图中找出一棵包含所有顶点且边权值之和最大的树。边权值可以根据两张图像之间的匹配点数目、基线长度、三角量测角度等因素来确定。最大生成树可以保证你选取的图像对具有较好的视角和匹配质量，从而提高重建效果。接下来，你将使用图割算法，将最大生成树划分为多个子图。图割算法可以根据子图中顶点和边的个数、边权值之和等条件来确定划分方案。划分后的子图可以看作是相对独立的小型场景，对每个子图单独进行增量式SfM重建，得到相机参数和三维点坐标。最后，你将使用捆绑调整算法，对所有子图进行全局优化，消除误差累积和漂移，并将所有子图合并为最终模型。

增量SfM重建

在增量式sfm中，选择下一幅图像的目的是为了扩展重建模型，增加场景覆盖范围和减少误差累积。选择下一幅图像的原则是要保证与已经重建的图像有足够多的匹配点，且具有较好的视差角度，以便于进行三角化和PnP。一种常用的方法是根据图像之间的匹配点数目、基线长度、三角量测角度等因素来确定边权值，然后从子图中找出一棵最大生成树，按照树的深度优先顺序遍历图像。这里我们采用一种下一个最佳视图策略来找到当前最适合重建的图像。

下一个最佳视图规划已经在计算机视觉、摄影测量和机器人技术领域进行了研究。在稳健的 SfM 中选择下一个最佳视图旨在最小化重建误差。在这里，我们提出了一种有效的下一个最佳视图策略，遵循一种最大化重建鲁棒性的不确定性驱动方法。选择下一个最佳视图至关重要，因为每个决定都会影响剩余的重建。一个错误的决定可能会导致一连串的相机错误注册和错误的三角测量。此外，选择下一个最佳视图会极大地影响姿势估计的质量以及三角测量的完整性和准确性。准确的姿态估计对于稳健的 SfM 至关重要，因为如果姿态不准确，点三角测量可能会失败。

下一个最佳视图的候选者不是至少看到 Nt > 0 个三角点的尚未注册的图像。使用特征轨迹图可以有效地跟踪此统计信息。对于 Internet 数据集，此图可能非常密集，因为许多图像可能会看到相同的结构。因此，在重建的每一步都有许多候选视图可供选择。 Haner 等人提出的详尽协方差传播。是不可行的，因为需要在每个步骤中为每个候选者计算和分析协方差。我们提出的方法使用高效的多分辨率分析来近似他们的不确定性驱动方法。我们必须同时跟踪每个候选图像中可见点的数量及其分布。更多的可见点和这些点的更均匀分布应该导致更高的分数 S，这样具有更好条件的可见点配置的图像首先被注册。为了实现这个目标，我们将图像离散化为一个固定大小的网格，在两个维度上都有 Kl bins。每个单元格有两种不同的状态:空和满。每当空单元格中的一个点在重建过程中变得可见时，单元格的状态就会变为完整，并且图像的分数 Si 会增加一个权重 wl。通过这个方案，我们量化了可见点的数量。由于细胞只对总分有贡献一次，因此我们更倾向于在点聚集在图像的一部分中的情况下更均匀地分布(即只有少数细胞包含所有可见点)。但是，如果可见点的数量为 Nt < K2 l ，则此方案可能无法很好地捕获点的分布，因为每个点都可能落入单独的单元格中。因此，我们通过在每个连续级别使用更高分辨率 Kl = 2l 对图像进行分区，将先前描述的方法扩展到具有 l = 1...L 级别的多分辨率金字塔。得分在所有级别上累积，权重 wl = K2 l 与分辨率相关。该数据结构及其分数可以有效地在线更新。

为了处理任意级别的异常值外点值,我们使用 RANSAC 制定了多视图三角剖分问题。我们考虑特征轨迹 T = {Tn | n =1...NT } 作为一组具有先验未知内点比率 ε 的测量值。测量 Tn 由归一化图像观察 ̄ xn∈ R2 和相应的相机位姿 Pn ∈ SE(3) 组成,定义从世界到相机帧的投影 P = [RT −RT t] 其中 R ∈ SO(3) 和 t ∈ R3。我们的目标是最大限度地支持符合条件良好的双视图三角剖分

X_{a b} \sim τ (x_{a}, x_{b}, P_{a}, P_{b}) w i t h a \neq b

其中 τ 是任何选择的三角剖分方法(在我们的例如 DLT 方法 [26]),Xab 是三角点。请注意,我们不会从全景图像对(第 4.1 节)进行三角测量,以避免由于姿势估计不准确而导致错误的三角测量角度。条件良好的模型满足两个约束。首先,足够的三角剖分角

\cos α = \frac{t_{a} - X_{a b}}{| | t_{a} - X_{a b} | |_{2}} \cdot \frac{t_{a} - X_{a b}}{| | t_{b} - X_{a b} | |_{2}}

其次,正深度 da 和 db w.r.t.视图 Pa 和 Pb(手性约束),深度定义为

d = [p_{31} p_{32} p_{33} p_{34}] [X_{a b}^{T} 1]^{T}

其中 pmn 表示 P 的第 m 行和第 n 列中的元素。如果 Tn 具有正深度 dn 且其重投影误差

e_{n} = | | x_{n} - [\begin{matrix} x / z \\ y / z \end{matrix}] | |_{2} w i t h [\begin{matrix} x \\ y \\ z \end{matrix}] = P_{n} [\begin{matrix} X_{a b} \\ 1 \end{matrix}]

小于某个阈值 t。 RANSAC 将 K 最大化作为一种迭代方法,并且通常它会随机均匀地对大小为 2 的最小集合进行采样。但是,由于对于小 NT 可能会多次采样相同的最小集,因此我们将随机采样器定义为仅生成唯一样本。为确保至少对一个无离群值的最小集进行采样,有置信度η,RANSAC 必须至少运行 K 次迭代。由于先验内点比率未知,我们将其设置为较小的初始值 ǫ0 并在我们找到更大的共识集(自适应停止标准)时调整 K。因为特征轨迹可能包含多个独立点,所以我们通过从剩余测量中删除共识集来递归地运行此过程。如果最新共识集的大小小于三,则递归停止。为了减少累积误差，我们在图像配准和三角测量后执行 BA。通常，不需要在每个步骤之后执行全局 BA，因为增量 SfM 只会影响局部模型。因此，我们在每次图像配准后对连接最多的图像集执行局部 BA。类似于 VisualSFM，我们仅在将模型增长一定百分比后才执行全局 BA，从而导致 SfM 的摊销线性运行时间。参数化。为了考虑潜在的异常值，我们使用 Cauchy 函数作为局部 BA 中的稳健损失函数 ρj。对于几百个摄像头的问题，我们使用稀疏直接求解器，对于更大的问题，我们依赖 PCG。我们使用 Ceres Solver 并提供在任意图像组合之间共享任意复杂度相机模型的选项。对于无序的互联网照片，我们依赖于具有一个径向畸变参数的简单相机模型，因为估计依赖于纯粹的自校准。过滤。BA之后，一些观察结果与模型不符。在全局 BA 之后，我们还检查退化相机，例如由全景图或人工增强图像引起的。通常，这些相机只有离群值观测值，或者它们的内在函数会收敛到一个虚假的最小值。因此，我们不将焦距和失真参数限制在先验固定范围内，而是让它们在 BA 中自由优化。由于主点校准是一个不适定的问题，我们将其固定在未校准相机的图像中心。具有异常视野或大失真系数幅度的相机被认为是错误估计并在全局 BA 之后被过滤。

PnP（Perspective-n-Point）是指已知n个3D空间点以及它们在图像上的投影位置时，估算相机所在的位姿的问题。PnP对该图像进行配准的过程是利用已经重建的3D点和新图像中的匹配点，求解相机的旋转矩阵和平移向量。由于匹配点中可能存在异常值，因此通常使用RANSAC等鲁棒估计方法来剔除异常值，并使用最小化重投影误差的方法来优化相机位姿。

PnP问题可以用数学语言描述如下：

x_{i} = K (R X_{i} + t), i = 1, \dots, n

其中，xi是第i个3D点Xi在图像上的投影坐标，K是相机的内参矩阵，R和t是相机的旋转矩阵和平移向量，即相机的位姿。求解PnP问题就是求解R和t。

PnP问题有多种算法，我们使用以下三种常见的算法：

直接线性变换法（Direct Linear Transform，DLT）：这种方法假设相机已经校准过了，即已知K。对于每组3D-2D匹配点，可以得到两个线性方程，一共有12个未知数（R和t的元素）。至少需要6组匹配点才能求解线性方程组。设有n组匹配点，则可以写成矩阵形式：
$A F = 0$
其中，A是一个2n×12的矩阵，F是一个12×1的向量，包含了R和t的元素。当n=6时，可以直接求解线性方程组。当n>6时，可以使用奇异值分解（SVD）等方法求解最小二乘解。然后，将F恢复为R和t。

这种方法的优点是简单快速，缺点是只考虑了线性意义下的最优解，没有考虑几何约束（例如旋转矩阵的正交性）。
P3P：这种方法是已知三个3D目标点与其2D投影之间的对应关系，来确定标定相机的位姿问题。这种方法利用了三角约束，给出三角约束意义下的最优解。具体来说，可以使用相似三角形、四元数等方法来减少未知参数的个数，把P3P方程组转化为四次方程或者六次方程。然后，使用牛顿迭代法等方法求解方程的实根。

这种方法的优点是考虑了几何约束，缺点是可能存在多解或者缺解的情况。为了得到唯一的解，至少还应引入一个点，构建两个三角形，进行求解。另一种方法是使用RANSAC等鲁棒估计方法，将点集划分为三个点子集，检查这些子集的一致性。
RPnP：这种方法是一种鲁棒的O(n)复杂度的PnP算法，可以处理任意数量的3D-2D匹配点。这种方法的思想是先建立一个新的正交坐标系，然后求解正交坐标系到相机坐标系之间的旋转和平移矩阵。具体来说，可以使用主成分分析（PCA）等方法确定旋转轴，然后使用最小二乘法等方法求解旋转角和平移矢量的方程。

这种方法的优点是鲁棒、高效、通用，缺点是需要进行非线性优化，可能陷入局部最优解。

对于以上三种方法，我们分别进行求解，由于构建的求解方式不一致，我们对三种方式求解的结果进行精度分析，选取目前认为最优的结果作为PnP的结果。

BA是指捆绑调整（Bundle Adjustment）的缩写，它是一种非线性最小二乘优化方法，用于从多个视角下的匹配点，同时恢复出相机的内外参数和3D空间点的坐标。BA的目标是最小化重投影误差，即将3D点投影到各个相机上得到的2D坐标与实际观测到的2D坐标之间的距离平方和。

BA的数学模型可以表示为：

min_{C, X} = \sum n_{j} = \sum m ρ (∥ π (C_{j}, X_{i}) - x_{i j} ∥ 2)

其中，Cj是第j个相机的参数（包括内参和外参），Xi是第i个3D点的坐标，π(Cj,Xi)是将3D点Xi投影到第j个相机上得到的2D坐标，xij是第j个相机上观测到的第i个3D点对应的2D坐标，ρ是一个鲁棒损失函数，用于降低异常值的影响。

为了求解这个优化问题，需要计算目标函数关于相机参数和3D点坐标的偏导数，即雅可比矩阵。然后可以使用高斯-牛顿法或者列文伯格-马夸尔特法等方法来迭代地更新相机参数和3D点坐标，直到收敛或者达到最大迭代次数。

BA 是 SfM 中的主要性能瓶颈。我们提出了一种方法，该方法利用增量 SfM 和密集照片集合的固有特性，通过将冗余相机聚类到高场景重叠组中来更有效地参数化 BA。由于兴趣点的受欢迎程度不同，照片集通常具有高度不均匀的可见性模式。此外，无序集合通常聚集成在许多图像中共同可见的点片段。许多以前的工作利用这一事实来提高 BA 的效率，将摄像机和点划分为子图，子图通过分隔符变量连接，将划分作为连接摄像机和点参数图上的图切割问题。然后 BA 在固定相机和点和改进分隔符变量之间交替，反之亦然。将具有低秩的多个点折叠为单个因素，对相机施加高秩约束，从而在相机共享许多点时提供计算优势。我们提出的方法是受这些先前工作的启发。我们将问题划分为内部参数被分解的子图。SfM根据图像和点的参数是否受到最新增量模型扩展的影响，将图像和点分为两组。对于大问题，大部分场景不受影响，因为模型通常在局部扩展。BA 自然会针对新扩展的部分进行更多优化，而其他部分只会在漂移的情况下进行改进。此外，照片集通常相机分布不均匀，有许多冗余视点。受这些观察的启发，我们将未受影响的场景部分划分为组 G = {Gr | r = 1...NG} 的高度重叠图像并将每个组 Gr 参数化为单个相机。受最新扩展影响的图像被独立分组，以允许对其参数进行最佳细化。这会导致标准 BA 参数化。对于未受影响的图像，我们创建基数NGr组。如果图像是在最新的模型扩展期间添加的，或者如果超过 εr的观测值比具有大于 r 像素的重投影误差（以改进重新三角化相机），我们认为图像受到影响。一组内的图像应尽可能冗余，图像之间的共同可见点的数量是描述它们相互影响程度的度量。对于具有 NX 个点的场景，每个图像都可以用二进制可见性向量 vi ∈ {0, 1}NX 来描述，其中如果点 Xn 在图像 i 中可见，则 vi 中的第 n 个条目为 1，否则为 0。图像 a 和 b 之间的交互程度是使用对它们的向量 vi 的按位运算计算的

V_{a b} = \frac{| | v_{a} \land v_{b} | |}{| | v_{a} \lor v_{b} | |}

为了构建组，我们将图像排序为 I= {Ii | ‖vi‖≥‖vi 1‖}。我们通过从 ̄ I 中删除第一个图像 Ia 并找到使 Vab 最大化的图像 Ib 来初始化一个组 Gr。

f Vab > V 和 |Gr| < S，图像 Ib 从 ̄ I 中移除并添加到组 Gr。否则，将初始化一个新组。为了减少寻找 Ib 的时间，我们采用启发式方法将搜索限制在 Kr 空间最近邻，其共同观察方向在 ±β 度范围内，其动机是这些图像很可能共享许多点.然后对组中的每个图像进行参数化 w.r.t.一个共同的组局部坐标系。分组图像的 BA 成本函数是

E_{g} = \sum_{j} ρ (| | π_{g} (G_{r}, P_{c}, X_{k}) - x_{j} | |_{2}^{2})

使用外部组参数 Gr ∈ SE(3) 和固定的 Pc。然后将组 r 中图像的投影矩阵定义为组和图像姿态 Pcr = PcGr 的串联。总成本 E 是分组和未分组成本贡献的总和。为了有效连接 Gr 和 Pi 的旋转分量，我们依赖四元数。由于计算 πg 相对于 π 的相对开销较小，因此较大的组大小会带来更大的性能优势。请注意，即使对于两个组的情况，我们也观察到了计算优势。此外，性能优势取决于问题的大小，因为摄像机数量的减少对直接方法的立方计算复杂度的影响大于间接方法的线性复杂度。

三角化测量

三角化是指根据两个或多个视角下的匹配点，恢复出它们对应的3D空间点的过程。三角化是sfm中重要的一步，它可以扩展重建模型，增加场景覆盖范围和减少误差累积。

三角化的基本原理是利用射影几何中的交叉比不变性，即两条直线上的四个点的交叉比在不同视角下保持不变。因此，如果已知两个视角下的匹配点以及相机的位姿，就可以通过求解线性方程组或者最小化重投影误差等方法，得到3D空间点的坐标。

三角化有多种算法，这里简单介绍三种常见的算法：

线性三角化：这种方法假设相机已经校准过了，即已知相机的内参矩阵。对于每组2D-2D匹配点，可以得到一个线性方程，一共有4个未知数（3D点的齐次坐标）。至少需要两组匹配点才能求解线性方程组。设有n组匹配点，则可以写成矩阵形式：
$A X = 0$
其中，A是一个2n×4的矩阵，X是一个4×1的向量，包含了3D点的齐次坐标。当n=2时，可以直接求解线性方程组。当n>2时，可以使用奇异值分解（SVD）等方法求解最小二乘解。然后，将X转换为非齐次坐标。

这种方法的优点是简单快速，缺点是只考虑了线性意义下的最优解，没有考虑几何约束（例如相机位姿和3D点之间的一致性）。
非线性三角化：这种方法是在线性三角化的基础上，使用非线性优化方法来进一步提高精度和鲁棒性。具体来说，可以使用高斯-牛顿法或者列文伯格-马夸尔特法等方法来最小化重投影误差：
$min_{X} \sum_{i = 1}^{n} ∥ π (P i, X) - x i ∥^{2}$
其中，π(Pi,X)是将3D点X投影到第i个相机上得到的2D坐标，xi是第i个相机上观测到的2D坐标，Pi是第i个相机的投影矩阵。这种方法需要给定一个初始值，通常可以使用线性三角化得到的结果作为初始值。

这种方法的优点是考虑了几何约束，缺点是需要进行迭代优化，可能陷入局部最优解或者收敛速度慢。
鲁棒三角化：这种方法是在非线性三角化的基础上，使用鲁棒损失函数来降低异常值的影响。具体来说，可以使用Huber损失函数或者Tukey损失函数等方法来替代平方损失函数，使得重投影误差对于异常值不敏感：
$min_{X} \sum_{i = 1}^{n} ρ (∥ π (P i, X) - x i ∥ 2)$
其中，ρ是一个鲁棒损失函数，例如：
$ρ (x) = {\begin{cases} x & x < c \\ c + \frac{c^{2}}{2 x} - \frac{c}{2} & x \geq c \end{cases}$
这种方法的优点是鲁棒性高，缺点是需要选择合适的鲁棒损失函数和参数，以及进行迭代优化。

重新三角测量。类似于 VisualSfM，我们执行重新三角测量 (RT) 以在全局 BA（预 BA RT）之前考虑漂移效应。然而，BA 通常会显着改善相机和点参数。因此，我们建议通过额外的 BA 后 RT 步骤来扩展非常有效的 BA 前 RT。此步骤的目的是通过继续跟踪以前未能三角化的点（例如，由于姿势不准确等）来提高重建的完整性。我们不增加三角化阈值，而是继续跟踪具有误差低于过滤阈值的观测值。此外，我们尝试合并轨道，从而为下一个 BA 步骤提供更多的冗余。迭代优化。 Bundler 和 VisualSfM 执行 BA 和过滤的单个实例。由于漂移或 BA 前 RT，通常 BA 中的大部分观察结果是异常值，随后被过滤掉。由于 BA 受到异常值的严重影响，因此 BA 的第二步可以显着改善结果。因此，我们建议在迭代优化中执行 BA、RT 和过滤，直到过滤的观察值和 BA 后 RT 点的数量减少。在大多数情况下，第二次迭代后结果会显着改善并且优化会收敛。

合并最终模型

上述方法，我们已经得到了各个子图的SfM结果，我们最后一步是将各个子模型合并。

求解各个子图的图像集。你可以根据子图之间的拓扑关系，将相邻或相交的子图分为一组，形成一个图像集。例如，如果你有四个子图A，B，C，D，其中A和B有重叠部分，B和C有重叠部分，C和D有重叠部分，那么你可以将A，B，C分为一组，形成一个图像集ABC；将B，C，D分为一组，形成一个图像集BCD。
找出各个子图中重叠的部分。你可以在每个图像集中进行特征点匹配，找出不同子图之间共享的特征点。例如，在图像集ABC中，你可以找出A和B之间共享的特征点AB；在图像集BCD中，你可以找出B和C之间共享的特征点BC；在两个图像集之间，你可以找出B和C之间共享的特征点BC’。
利用重叠的部分，求解两个子图的相似变换。你可以根据共享特征点之间的对应关系，求解两个子图之间的相似变换矩阵（Similarity Matrix），使得两个子图能够对齐。例如，在图像集ABC中，你可以根据AB之间的对应关系，求解A到B的相似变换矩阵SAB；在图像集BCD中，你可以根据BC之间的对应关系，求解B到C的相似变换矩阵SBC；在两个图像集之间，你可以根据BC’之间的对应关系，求解B到C’的相似变换矩阵SBC’。
将各个子图的模型进行融合。你可以根据相似变换矩阵，将各个子图的模型变换到同一个坐标系下，然后进行模型融合。例如，在图像集ABC中，你可以将A的模型变换为SABA；在图像集BCD中，你可以将D的模型变换为SBCD；在两个图像集之间，你可以将C的模型变换为SBC’*C；然后将所有的模型进行融合，得到最终的三维重建结果。

具体过程如下：

输入两个要对齐的模型，输出他们之间的相似变换矩阵alignment设置RANSAC的一些参数，最大误差，和内点率找到两个模型之间的公共图片 $I$ 再提取出两份，reconstruction1 中的 $I$ 表示为src_images，和reconstruction2中的 $I$ 表示为ref_images使用RANSAC估算两个images集的相似变换

两点云中的所有相机中心的坐标

X = (x_{1}, \dots, x_{n})

Y = (y_{1}, \dots, y_{n})

我们将其转为矩阵形式

M = [\begin{matrix} a_{1} & a_{2} & \dots & a_{n} \\ b_{1} & b_{2} & \dots & b_{n} \\ c_{1} & c_{2} & \dots & c_{n} \end{matrix}]

去中心化

\overset{―}{M} = [\begin{matrix} a_{1} - \overset{―}{a} & a_{2} - \overset{―}{a} & \dots & a_{n} - \overset{―}{a} \\ b_{1} - \overset{―}{b} & b_{2} - \overset{―}{b} & \dots & b_{n} - \overset{―}{b} \\ c_{1} - \overset{―}{c} & c_{2} - \overset{―}{c} & \dots & c_{n} - \overset{―}{c} \end{matrix}]

分别计算奇异值，与协方差矩阵

σ^{2} = \frac{1}{n} \sum_{i = 1}^{n} (x_{i} - \overset{―}{x})^{2}

\sum_{x y} = \frac{1}{n} \sum_{i = 1}^{n} (y_{i} - \overset{―}{y}) (x_{i} - \overset{―}{x})

最后进行奇异值分解

\sum_{x y} = U D V^{T}

其中

R = U S V

C = \frac{1}{σ^{2}} t r (D S)

t = \overset{―}{y} - c R \overset{―}{x}

先初始化一个RANSAC，得到最大迭代次数max_num_trials。

$N = \infty$ ，sample_count=0
while $N$ $>$ sample_count
- 选择一组样本，并记录它的内点数
- 计算外点率e = 1- number_of_inliers/total_number_of_points
  - 随机采样当前最优模型中的内点，估计新的模型（迭代10次），如果优于当前模型，则更新最优模型
- 计算最大迭代次数
  $N = \frac{\log (1 - p)}{\log (1 - (1 - e)^{s})}$
- sample_count += 1

开始迭代

从俩堆点云中随机采样需要的最少点数X_rand, Y_rand
从当前的采样中，估算model Estimate(X_rand, Y_rand)
局部优化

计算残差

对于每张图像，确定从一个图像正确投影到另一个图像以及从另一个图像正确投影回来的3D点的比率，考虑给定的对齐方式。残差定义为1减去这个比率，即误差阈值为0.3意味着该图像的70％点必须在给定的最大重投影误差阈值内重新投影。

遍历所有公共图像
遍历该图像中所有的特征点，并且该特征点在图像1和图像2都存在对应的3D点，num_common_points+1
计算双向误差，如果小于最大重投影误差，则num_inliers+1
计算外点率negative_inlier_ratio = 1- num_inliers/num_common_points
如果统计外点率negative_inlier_ratio < max_residual，则support.num_inliers+1
对比内点数，如果内点数相同，则比较外点率，更新当前最优模型
随机采样当前最优模型中的内点，估计新的模型
再对比新的模型是不是比上一步的最优模型的内点数更多
更新最大迭代次数
结束迭代，取出最优模型

融合

对比传入的reconstruction，生成common_image_ids 和 missing_image_ids，将missing_image_ids中的图像注册到当前的reconstruction中，注册很简单，将它本身的位姿乘以俩reconstruction的相似变换

P^{'} = s \cdot (\begin{matrix} R & t \\ 0 & 1 \end{matrix}) \cdot T^{- 1}

使用以下两种规则进行点云合并

复制非冲突的点云到当前重建中，即那些在当前重建中没有被三角化观测到的点。
合并无歧义的tracks，即只将两个重建中的点合并，如果它们有一个一对一的映射。

遍历传入的点云中的所有3D点
- 遍历这个3D点的track
  - 如果当前这个track在common_imgaes中，加入到old_track中
  - 如果当前这个track在missing_images中，加入到new_track中
将3D点添加到当前的reconstruction中
如果当前的reconstruction中已经存在这个新添加的3D点，那么将它们合并

过滤误差较大的三维点

计算重投影误差

P_{c} = R \cdot P + t

(\begin{matrix} u \\ v \\ 1 \end{matrix}) = \frac{1}{z} \cdot K \cdot P_{c}

e^{2} = {‖ (\begin{matrix} u \\ v \end{matrix}) - (\begin{matrix} p_{x} \\ p_{y} \end{matrix}) ‖}^{2}

如果大于一定重投影误差值，则将该3D点删除

得到最终结果

在稠密重建MVS方面，我们采用了多视几何的方法，使用SfM处理得到的相机姿态和三角测量得到的稀疏点云，运用光束法进行三角剖分，以得到高质量的三维重建结果。在这个过程中，我们采用了多种算法和方法，如多视几何恢复三维结构、MVSNet等深度学习方法等，通过大量的实验，我们发现这些方法在稠密重建方面都表现出了较好的效果。经过稠密点云计算、成像约束等操作后，我们得出的重建模型与实际场景相符合度高，重建结果细节丰富，具有一定的可视化效果。

我们采用了PatchMatch一种计算机视觉算法，用于求解图像匹配的问题。它由Barnes、Shechtman和Finkelstein在2009年发表，是一种快速而且高效的方法，用于在两幅图像中寻找匹配的图像块。

在PatchMatch算法中，每个像素点的匹配过程被看作一个寻找最优匹配的过程，而最优匹配点的目标是找到使两个匹配图像块误差最小的位置，从而确定每个像素点在另一幅图像中的对应位置。为了达到这个目标，PatchMatch算法采用了多尺度的策略，并利用相似图像块的局部性质来缩小匹配搜索区域的范围。为了进一步提高匹配速度，快速近似最近邻搜索技术被引入，大大缩短了算法的运行时间。

PatchMatch匹配算法步骤

初始化：初始化就是给每个patch的最近邻赋初值，也就是给图中的每个块随机赋予一个初始的匹配块

迭代：从左上角至右下角依次遍历每个patch，每个patch进行匹配传递和随机搜索两个步骤

匹配传递：匹配传递的思想是一个patch会试图借用邻居的匹配关系，来查询是否能得到更好的匹配，如果能得到更好的匹配，就更新自己的最近邻。这样一个patch如果拥有好的匹配成绩，它与另一张图中patch的匹配关系会被周围的邻居patch学习。最终每个patch会计算一个偏移值，用来表示所匹配块在另一张图中的位置

随机搜索：每次匹配过后，对于得到的还会继续对其施加一个随机搜索的策略，试图通过扰动看看能不能让其跳出局部最优

每次随机搜索会在上一步匹配传递的基础上，在不断指数衰减的半径区域里随机匹配若干次，直到半径缩到1个像素以下。

该算法的核心思想是基于简化的假设，即在两幅图像中所寻找的匹配图像块的位置和相应误差值应该是较为接近的，因此可以通过随机的方式得到初始的近似匹配，通过不断迭代，逐步优化误差值，并不断缩小匹配图像块的搜索区域，最终找到最优的匹配位置。

PatchMatch算法虽然简单，但是在实践中具有较高的鲁棒性和准确性，能够在短时间内处理大量的匹配任务，尤其对于处理图像缺陷修复、图像填充、图像修补、图像合成和场景重建等任务具有独特的优势。因此，在计算机视觉领域，PatchMatch算法越来越得到广泛的应用，并成为图像匹配领域的一个重要研究方向之一。

在不断优化误差值时，PatchMatch算法通过引入了多尺度的策略，可以使得算法更快地收敛至最优解。PatchMath算法在处理大型图像时还可以通过快速近似最近邻搜索来加快算法速度，PathchMatch结果如下图所示。

最近邻字段可以通过为字段分配随机值或使用先验信息来初始化。当使用随机偏移进行初始化时，我们在图像 B 的整个范围内使用独立的均匀样本。在第 4 节中描述的应用程序中，我们使用从粗到细的逐渐调整大小的过程，因此我们可以选择使用一个初始猜测从金字塔中的上一层升级。然而，如果我们只使用这个初始猜测，算法有时会陷入次优的局部最小值。为了保持这个先验的质量但仍然保留一些逃离这种最小值的能力，我们使用随机初始化执行算法的一些早期迭代，然后仅在 D 较小的补丁处与上采样初始化合并，然后执行剩余的迭代。

初始化后，我们执行改进 NNF 的迭代过程。算法的每次迭代按如下方式进行：按扫描顺序（从左到右，从上到下）检查偏移量，并且每个偏移量都经过传播，然后进行随机搜索。这些操作在补丁级别交错：如果 Pj 和 Sj 分别表示补丁 j 的传播和随机搜索，那么我们按以下顺序进行：P1，S1，P2，S2，...。 . . , Pn, 锡。传播。我们尝试使用 f (x − 1, y) 和 f (x, y − 1) 的已知偏移量来改进 f (x, y)，假设补丁偏移量可能相同。例如，如果在 (x − 1, y) 处有一个很好的映射，我们会尝试将该映射向右平移一个像素，用于我们在 (x, y) 处的映射。令 D(v) 表示 A 中 (x, y) 处的补丁与 B 中的补丁 (x, y) + v 之间的补丁距离（误差）。我们将 f (x, y) 的新值设为{D( f (x, y)), D( f (x − 1, y)), D( f (x, y − 1))} 的 arg min。结果是，如果 (x, y) 具有正确的映射并且位于相干区域 R 中，则 (x, y) 下方和右侧的所有 R 都将被正确的映射填充。此外，在偶数次迭代中，我们通过以反向扫描顺序检查偏移量来向上和向左传播信息，使用 f (x + 1, y) 和 f (x, y + 1) 作为我们的候选偏移量。随机搜索。令 v0 = f(x, y)。我们尝试通过在距 v0 呈指数递减的距离处测试一系列候选偏移来改进 f (x, y)：

u_{i} = v_{0} + w a^{i} R_{i}

其中 Ri 是 [−1, 1] × [−1, 1] 中的均匀随机数，w 是较大的最大搜索“半径”，α 是搜索窗口大小之间的固定比率。我们检查 i = 0, 1, 2, ... 的补丁，直到当前搜索半径 wαi 低于 1 个像素。在我们的应用程序中，w 是最大图像维度，α = 1/2，除非另有说明。请注意，搜索窗口必须限制在 B 的范围内。停止条件。虽然根据应用程序可能会使用不同的停止标准，但在实践中我们发现它可以很好地迭代固定次数。此处显示的所有结果都是通过总共 4-5 次迭代计算得出的，之后 NNF 几乎总是收敛。收敛如图 3 和随附的视频所示。效率。可以通过几种方式提高这种朴素方法的效率。在传播和随机搜索阶段，当尝试使用候选偏移量 u 改进偏移量 f (v) 时，如果 D(u) 的部分和超过当前已知距离 D( f (v))，则可以提前终止.此外，在传播阶段，当使用边长为 p 和 Lq 范数的方形补丁时，距离的变化可以在 O(p) 而不是 O(p2) 时间内递增计算，方法是注意求和中的冗余项重叠区域。但是，这会产生额外的内存开销来存储当前最佳距离 D( f (x, y))。 GPU 实现。第 4 节中描述的编辑系统依赖于 NNF 估计算法的 CPU 实现，但我们还在 GPU 上制作了一个完全并行化变体的原型。为此，我们在随机搜索和传播的迭代之间交替，其中每个阶段并行处理整个偏移量字段。虽然传播本质上是一个串行操作，但我们采用了 Rong 和 Tan 的跳洪方案来执行多次迭代的传播。尽管我们的 CPU 版本能够在整个扫描线上传播信息，但我们发现实际上不需要长距离传播，最大跳跃距离为 8 就足够了。我们还在每个跳跃距离仅使用 4 个邻居，而不是 Rong 和 Tan 提出的 8 个邻居。

我们的迭代算法在极限内收敛到精确的 NNF。在这里，我们为这种收敛提供了一个理论分析，表明它在前几次迭代中以高概率收敛得最快。此外，我们表明，在只需要近似补丁匹配的常见情况下，该算法收敛得更快。因此，通过将计算限制为少量迭代，我们的算法最适合用作近似算法。我们首先分析收敛到精确的最近邻域，然后将此分析扩展到更有用的收敛到近似解的情况。假设 A 和 B 具有相同的大小（M 个像素）并且使用随机初始化。尽管在这个初始猜测中任何一个位置被分配最佳偏移的几率微乎其微 (1/M)，但至少一个偏移被正确分配的几率非常好 (1 − (1 − 1/M)M ) ) 或对于大 M 大约为 1 − 1/e。由于随机搜索在小的局部区域中非常密集，我们还可以将“正确”分配视为正确偏移量周围大小为 C 像素的小邻域内的任何分配。这样的偏移量将在随机搜索的大约一次迭代中得到纠正。在这样的邻域中至少分配一个偏移量的可能性非常大：(1 − (1 −C/M)M ) 或对于大 M，1 − exp(−C)。

现在我们为我们的算法考虑一个具有挑战性的综合测试用例：一个大小为 m 像素的独特区域 R 位于一对其他方面均一的图像 A 和 B 中的两个不同位置（插图所示）。这个图像是一个困难的案例，因为背景没有提供关于在哪里可以找到独特区域的偏移量的信息。均匀背景中的补丁可以匹配大量其他相同的补丁，这些补丁在一次迭代中以非常高的概率通过随机猜测找到，因此我们只考虑不同区域 R 的收敛。如果不同区域 R 中的任何一个偏移量是在正确偏移量的邻域 C 内，然后我们假设在少量迭代之后，由于小局部区域中随机搜索的密度（前面提到的），所有 R 都将通过传播是正确的（对于符号简单假设这是瞬时的）。现在假设 R 还没有收敛。考虑我们的算法在最大尺度 w 下执行的随机搜索。规模为 w 的随机搜索迭代独立地对图像 B 进行采样，并且这些样本中的任何一个落在正确偏移量的邻域 C 内的概率 p 为

P = 1 - (1 - \frac{C}{M})^{m}

在进行任何迭代之前，收敛的概率为 p。我们没有在迭代 0, 1, ...,t − 1 上收敛并在迭代 t 上收敛的概率是 p(1 − p)t 。概率因此形成几何分布，预期收敛时间为t = 1/p − 1。为了简化，让相对特征尺寸为γ = m/M，然后随着分辨率M变大取极限：

< t >= [1 - (1 - \frac{C}{M})^{γ M}]^{- 1} - 1

lim_{M ⟶ \infty} < t >= [1 - \exp (- C γ)]^{- 1} - 1

通过对小 γ 的泰勒展开，t = (Cγ)−1 − 1 2 = M/(Cm) − 1 2 。也就是说，对于大图像分辨率和相对于图像分辨率 M 的小特征尺寸 m，我们预期的收敛迭代次数保持不变。我们对从 0.1 到 2 兆像素的分辨率 M 的图像进行了模拟，证实了这个模型。例如，我们发现对于 m = 202 的区域，算法在对 M = 20002 的图像进行 5 次迭代后以非常高的概率收敛。上面的测试用例很难，但不是精确匹配的最差测试用例。精确匹配的最坏情况是当图像 B 包含高度重复的纹理和许多与 A 中的不同特征相似的干扰物时。偏移可能会被其中一个干扰物“困住”，有效邻域区域大小 C 可能是减少到 1（即，只有完全匹配才能在随机搜索期间将解决方案从干扰项中拉出）。然而在实践中，对于许多图像分析和合成应用程序，例如我们在本文中展示的应用程序，找到近似匹配（根据补丁相似性）不会导致任何明显的差异。

在纹理重建方面，我们使用了多视觉立体投影的方法，将特定区域内的多张图像投影到三维重建模型上，从而得到了真实的纹理信息。我们的纹理重建方法采用了多标定照相机和多时刻捕获信息等技术，确保了纹理映射的准确性和一致性。通过采用贴图和参数空间纹理映射等算法，我们成功地为三维重建模型添加了逼真的纹理信息。经过反复验证和调整，我们的纹理重建结果非常出色，可以有效地提高三维模型的逼真度和真实感。

# 三、创新点

本系统在基于特征点提取和匹配的三维重建方法上有以下创新点：

我们结合了增量SfM和全局SfM的优化方法，构建场景图，并将大场景划分为多个小场景，并行对多个小场景进行增量重建，最后通过融合的方式将多个小场景合并为大场景。同时在一些优化过程中，我们提出了多种优化策略，从而可以得到较高精度的三维模型。

我们结合传统计算机视觉技术和深度学习技术，在不同阶段使用不同类型的特征表示来提高三维重建效果。在特征检测阶段使用SIFT特征，在稠密重建阶段使用MVSNet深度预测。

我们提出了一种基于光束法的稠密重建方法，在保证精度和鲁棒性的同时降低了计算复杂度。我们利用SfM得到的相机姿态信息来约束光束法搜索空间，并利用深度学习预测深度信息来加速光束法求解过程。

我们提出了一种基于多视觉立体投影的纹理重建方法，在保证纹理质量和一致性的同时增加了纹理多样性。我们利用多标定照相机捕获不同角度、不同光照条件下的图像，并利用参数空间纹理映射算法将它们融合到三维模型上。

← Keyframe3 一些期刊→