【论文阅读】Modeling the world from internet photo collections

Modeling the world from internet photo collections论文阅读

第1节 摘要 综述
第2节 介绍 综述
第3节 先前技术 历史回顾
第4节 重建流程
关键点检测与匹配方法
SFM重构
图像配准

• 5、图像呈现
• 6、页面浏览
• 7、技术术语解析
  • SIFT（关键点检测技术）
  • ANN（近邻搜索优化算法）
  • kd-tree（数据结构优化方案）
  • 单应性矩阵（投影矩阵分析）
  • bundle adjustment（几何优化算法）
  • 8点算法（基础几何计算方法）
  • RANSAC（随机抽样一致性方法）
  • DLT（直接线性变换算法）
  • 极几何理论（几何理论基础框架）

1、摘要

互联网上收藏着丰富的图片素材，在展现人类视觉感知能力方面具有独特价值。
在计算机视觉领域中如何有效利用这些图像素材开展研究？本文将聚焦于三维场景建模与可视化这一主题展开探讨。
文中提出了一种基于关键词搜索结果图像的结构重建与基于图像的三维渲染技术相结合的新算法。
为此我们将其命名为Photo Tourism方法这一创新性命名方案已在许多著名世界遗址及景观中实现了重建工作。
通过这项算法及其应用成果可以看出它在利用良好照片（主要来自互联网）构建世界著名遗址、城市景观及自然风光等三维场景方面取得了重要进展。
最后部分讨论了本研究面临的主要挑战及其潜在意义。

2、介绍

网络图像因缺乏有序性、处于非标定状态且具有易变性以及光照条件不稳定等问题，
难以直接应用于传统计算机视觉领域。
在计算机视觉领域面临的主要困难是：如何使两张图片如何对应三维坐标的问题。

本文的整体架构首先涉及最新的技术和动态。随后阐述了解决方案的具体步骤，并命名为Photo Tourism的前端可视化系统。继而提出了若干开放性研究课题,其中包括基于超大图像数据集创建更为高效的技术以实现快速对应与重建过程。在此基础上进行了拓展与改进,并提供了更多细节信息以供进一步探讨

3、先前技术（历史介绍）

• 特征配准
• SFM
• 基于图象的空间重建
• 基于图象的空间着色
• 实现对图片的空间浏览功能，并对图片进行标注以传递标签信息

4、重建过程

4.1 关键点的检测和匹配

该系统采用自动化的SIFT算法进行特征点检测，在图像处理过程中能够精准提取出每张图片中的关键信息。该算法通过分析图像结构并结合数学模型，在计算过程中为每个识别出的特征点生成对应的128维特征向量。其原理可在SIFT原理部分详述。

图中每个feature都是128维的向量

关键点配准 ：其目的旨在通过配准实现对应关键区域间的权重分配。例如：参考图示，在玩偶的眼睛部位等关键区域之间建立权重关系, 而避免与其他非关键部位产生关联。

为了达到这个效果, 应该评估特征点之间的距离. 基于上一步骤的sift特征提取过程, 每个特征点均被一个128维向量所描述. 因此, 在分析这些特征点之间的关系时,"高维向量"的距离计算就显得尤为重要. kd-tree通过构建一棵二叉树结构,"高维向量"会被系统地划分到树的不同子节点中.

衡量匹配点间的距离

为了确保图像间特征点的配对关系为每一对仅存在一个对应，在完成每个image_i内所有特征点与最近邻的配对之后，在另一幅图中的对应关系也只能维持一对一或者最多允许一对多（即n:1）。如果出现多于一个配对的情况（即n>1），则会移除这些多余的配 correspondence

通过上述步骤的实施与分析, 我们能够推导出图片间的哪些特征点存在一一对应关系. 换句话说, 在二维图像平面中各特征点之间的关联性, 可以被映射到三维空间直角坐标系中同一位置. 如图所示, 点x与x' 即为这样一对对应的特征点, 它们分别是从不同视角拍摄下同一个物体在三维空间中X位置的真实投影

通过上述步骤的实施与分析

计算基础矩阵F的方法是通过8点算法构建包含8个方程的一组线性方程组，并附加det(F)=0的约束条件。这一系统由以下等式组成：
\begin{cases} p_1^T F p_1' = 0 \\ p_2^T F p_2' = 0 \\ \vdots \\ p_8^T F p_8' = 0 \\ det(F) = 0 \end{cases}
通过求解这一系统找到最优解即可确定基础矩阵F的具体值。
为了求解上述系统中的最优解问题，则采用RANSAC结合LM算法进行迭代优化以获得最小误差解。
具体而言：

1. 自动提取两幅图像的关键点集并生成初始匹配对集合；

2. 剔除错误匹配对：

   • 计算当前抽样所确定的基础矩阵F及其一致点集S(F)；
   • 比较当前一致集与之前的一致集大小关系：
     • 若当前一致性更大，则更新当前一致集S(F)及对应的基矩阵F；
     • 否则维持原有的一致集及基矩阵；
   • 根据自适应机制终止抽样过程以获得最大一致性集合；

3. 利用最大一致性集合（即正确匹配对）重新计算基矩阵F。

将图片作为节点，在论文中的示意图中显示为一个网络结构。每个匹配的特征点通过加权边连接起来。

4.2 SFM重构

估计每张图片的参数（平移旋转焦距）
为了防止优化收敛到局部最小，需再估计合适的初始图片集，对应两种情况使用两种方式初始化
方式一：
----当图片不能被单应性模型很好的描述时，从一对儿匹配特征点数量最多的两张图开始
方式二：
----a）用RANSAC计算所有图像的单应性矩阵，并记录下来
这里单应性应理解为：用相机从不同位置拍摄同一物体 的图像之间存在单应性，可以用投影变换 表示
----b）为了防止退化（选取图片过于相似，导致泛化性不够），在剩余图片中选一对单应性最low（匹配程度最小）的图，但最少不得小于100个匹配
----c）对此初始化的两张图，用5点算法建立方程组，RANSAC迭代估计参数，再执行两次bundle adjustment，

初始化完成后，在RANSAC迭代过程中计算内外参数。在每次迭代期间，并非每次都使用五个特征点来估算内参和外参；相反地，在每一步都会加入一个观测最多轨迹的摄像头，并采用DLT技术对相机外参数进行初始估算；最后将得到一个上三角矩阵用于内部参数估算。

将所有观测到的点，在完成内外部参数转换至世界坐标后（或：将所有观测到的点在完成内外部参数转换至世界坐标之后），纳入基于最小化投影误差的优化过程（或：将所有观测到的所有点被纳入基于最小化投影误差优化的过程）

重投影误差的最小化采用bundle adjustment算法，并选择能够使得重投影误差达到最小值的二维观测点

步骤2-4过程图示如下 ：

获得观测数据后，在BA优化模型中逐步纳入这些关键采样位置信息。基于该坐标系下各摄像机成像平面上的观测到的P系列点及其对应的方向向量分别为\mathbf{P_1}, \mathbf{P_2}, \mathbf{P_3}, …；相应的光线方向分别为\mathbf{l_1}, \mathbf{l_2}, \mathbf{l_3}, …。当进行一次优化迭代时，在剩余光线方向中寻找与当前参考光线\mathbf{l_i}夹角最大的那条射线作为候选解；如果该最大角度超过两倍的标准差，则判定能够实现有效的三角化；否则需要将其归类为特殊情形（即平行摄像机系统）

sfm 改进 部分：

1. 去除包含离群点的轨迹数据，并筛选出适合用于优化计算的剩余轨迹点
2. 增加多个摄像机捕获的图片数量，并采用基于匹配度的方法，在图片间匹配度达到 0.75M 的条件下进行处理
3. 计算径向畸变参数

4.3 影像配准

1. 目标：旨在通过sfm生成的三维点云数据与卫星地图及数字高程图实现精准对应。
2. 该过程均建立在相对坐标系的基础上。
3. 方法：
   a）首先确定世界坐标系的垂线方向（由重力加速度矢量确定）。
   b）通过将三维空间中的配准任务转化为二维平面内的匹配操作（便于人工进行精确配准）。

5、图片渲染

应用界面的介绍：省略
图像平滑切换中的渲染 ：两种不同的图像切换方案
1、 从一张完整图片切换到另一张完整图片
2、 从一张完整图片切换到用户手动选定的部分
这里主要论述了在切换过程中视角的方向必须进行合理选择，并采用合理的图像插值算法以保证渲染效果的流畅性与视觉质量。

第三种方法：三角剖分点云与平面近似体 该文采用的方法是第二种插值方式（triangle-based triangulation），因其稳定性表现更为优异 两种方法的原理

4. 有两种无需视觉反馈的情形：第一种是两张图像几乎没有共同的特征点，在这种情况下直接通过渐淡效果展示；第二种情况是当两个平面comonplane(C_j,C_k)与C_j、C_k的方向均值垂直时

6、用户导航

软件使用方法：跳过
自动传递用户标定的注释：
方法：将某注记标记为变量a
1 依次遍历每张图片
2 判断注释a是否覆盖了整个图像或仅在其边缘区域存在
3 若注释a在图j的像素矩阵中有至少一个非零值存在，则定义图j的特征点集合为变量Cj中的元素
4 计算S_ANN与该特征点集合之间的相似度得分，并检查该得分是否落在区间[0.05, 0.8)内
5 当满足上述条件时，则将该注记传递至图j中

7、术语解释

SIFT

• 论文中作用 ：该方法通过提取图像的特征点，并将其表示为向量形式。
• 定义：在不同尺度的空间中搜索关键点，并确定每个关键点的方向。
• 原理：
  1、提取关键点 ：该步骤旨在遍历所有可能的尺度空间中的图像位置。
  • 通过高斯微分函数来定位具有尺度和旋转不变特性的兴趣点。
    2、定义与计算方向 ：i. 通过不同σ值的Difference of Gaussians（DOG）进行滤波处理；ii. DOG类似于对LOG进行离散化处理（即先进行高斯平滑操作后进行梯度计算），从而确定关键点的位置。

ii. 在上图中可见各层均具有多通道特征。
这些特征之间存在以下关系描述：
每个层级都是一个频带划分，
其中每个频带由不同尺度的高斯滤波器生成，
具体而言，
它们由不同尺度的高斯滤波器生成，
其标准差分别为\sigma、k\sigma、k^2\sigma……直到k^n\sigma。

通过计算两个高斯函数在不同尺度参数下的差值，并将其除以(k\sigma - \sigma)得到的结果等于\frac{\partial G}{\partial \sigma}。

在octave之间：上层的第一张是下层倒数第三章降采样生成

iii. 寻找特征点 ，差分后金子塔每一层中：

等价于关键的位置相当于极值的位置
对应的位置相当于圆心坐标
在取得极大/极小值的过程中\sigma参数在此过程中所取的最大/最小数值代表半径大小
从图中可见的大圆圈对应金字塔顶端的关键特征位置
而位于底部的小圆圈对应底端的主要特征位置

根据设定的尺度参数σ，在每个关键点周围构建一个梯度直方图；该梯度直方图基于以特征点为中心区域、半径长度为3.5σ的空间范围内进行统计

梯度直方图的横轴对应八个指向，并将数值最大的那两个指向定义为主向量和辅助向量

对图像进行主方向旋转后，在旋转变换后对像素点进行划分网格结构，并通过分析每个特征点对应的向量特征完成后续处理。

ANN（近似最近邻）

• 论文作用：设有向量a及向量集合B，则旨在寻找B中与a距离近邻的k个向量。
• 定义：Approximate Nearest Neighbor（Ann），对于一个向量X=[x1,x2,x3…xn]而言，则需从海量数据集中筛选出前K个最相似的数据实例。这些数据实例往往具有较高的维度，在线服务中若采用传统方法直接进行精确匹配查询则会面临效率低下且延迟过高的问题；因此研究界普遍采用了将相似度查找问题转化为Ann问题的方式。
• 原理：
  （1）从根节点出发开始查询数据集Q：根据Q与各节点比较的结果向下探索Kd-Tree至叶子节点。
  其中Q与各节点比较是指针对Q在第k维上的值与其父节点存储的关键值进行对比操作；若当前维度上的值小于父节点关键值，则进入左子树；反之则进入右子树。
  达到叶子节点后需计算该实例与其父节点保存的数据之间的距离，并记录最小距离对应的实例及其对应距离值。
  （2）执行回溯操作以寻求可能存在的更近邻实例：即检查未被访问过的分支是否存在比当前最小距离还近的数据实例。
  若发现某未被访问分支所在区域距Q的距离小于当前最小距离，则需进入该子树继续搜索；若找到比当前记录更近的数据实例则更新为新的最近邻实例及其对应距离值；否则维持原有记录不变。
  此过程需自下而上依次检查所有可能存在的分支直至完成整个树结构的所有遍历工作。

kd-tree

• 论文中作用 ：用于界定高维空间中各特征点之间的距离关系

  • 定义：Kd-Tree（即K-维树），是一种基于高维空间的数据索引结构，在大规模的高维数据集中实现最近邻及近似最近邻的高效查找
  • 原理：通过将二叉查找树的概念推广至多维空间，并采用最大方差法评估向量大小、中值法划分区间的方式构建树形数据结构；
    每个非叶节点会将一个向量集合分割为两个子向量集合
    假设某节点将向量集合A划分为A₁和A₂

• 最大方差准则： 按照A中每个向量在第i维上的大小值，在kd树的第i层将空间划分为左右两个子区域，并分别建立相应的子树。

  • 中值法是以分割点的选择为基础，在构建kd树的过程中将所有数据点按照其在某一个特定维度上的特征值进行分类处理。

单应性矩阵

论文中作用 ：用于衡量两张图片的匹配程度

定义：单应性即为图像在两个成像平面间的映射关系，并由一对摄像机像素平面上的变换矩阵所描述

该方法基于以下原理：其中两个像素平面之间的点满足如下关系：
\begin{bmatrix} x' \\ y'\\ 1\\ \end{bmatrix} = \begin{pmatrix} h_{11},h_{12},h_{13}\\ h_{21},h_{22},h_{23}\\ h_{13},h_{32},h_{33}\\ \end{pmatrix}. \begin{bmatrix} x\\ y\\ 1\\ \end{bmatrix}

通过上述方程可以看出：已知一对点可对应于两个关于H矩阵的方程。其中其坐标值为x'=（h₁₁x + h₁₂x + h₁₃）/(h₃₁x + h₃₂x + h₃₃)；同理可得y'=（h₁₁y + h₁₂y + h₁₃）/(h₃₁y + h₃₂y + h₃₃)

4个已知点建立线性方程组为（N=4）

建立线性方程组之后，转为优化问题，再用RANSAC求解

bundle adjustment

• 论文中作用 ：基于RANSAC成功估计内外参数后，在构建世界坐标系中的三维点集合时实现对像机重投影误差的最小化。
• 定义：BA本质上是一个优化模型，核心在于最小化重投影误差。
• 原理：目前尚在研究中。
• 参考1参考2

8点算法

• 论文中作用：用8个点估计基本矩阵F
• 原理：

项目	含义
O1、O2	相机1、相机2
I、I’	相机1成像平面、相机2成像平面
K、K’	相机1内参数矩阵、相机2内参数矩阵
P	世界坐标系下的点
p、p’	P点在相机1、2成像平面上的投影点（成像点）坐标
R、T	O2相对O1的旋转、平移矩阵

基于极几何理论推导得出结论可知，
p和p’之间满足某种关系式：

p^{\prime T} F p = 0

其中F为基线矩阵。
而该方程也可表示为：

\text{EpipolarConstraint}(p, p') = 0

最后构建了一个8维线性方程组，并在满足约束条件det(F)=0的基础上将其转化为一个优化问题；随后通过反复迭代RANSAC算法来计算得到矩阵F。

RANSAC

• 论文中所起的作用：* 在论文中有两个主要作用：

1. 基于LM的结合用于估计基础矩阵F的具体值。
2. 基于BA的结合则用于解决复杂的优化问题。

• 定义为一种拟合方式。
• 原理如下：
  一. RANSAC用于去除错误配准：
  1．系统自动提取两幅图像的所有特征并生成初始配准候选集合。
  2．通过迭代抽样评估配准质量：
  2-1 计算当前抽样结果对应的基元矩阵及其一致性区域。
  2-2 比较新一致性区域与前次的结果。
  2-3 若新一致性区域更大，则更新结果并淘汰旧数据。
  重复直到收敛条件满足。
  3．基于最终的最大一致性区域重新计算基元参数。

二. RANSAC优化模型的具体实现过程如下：
①在以下框架中考虑一个最小抽样集的概念：该抽样集所需的最少样本数量为n（其中n表示初始化模型所需的基本样本数量），以及一个样本集合P（其中P中的样本总数要大于n）。从集合P中随机选取包含n个样本的子集S作为初始估计的基础；
②通过计算子集S上生成的初始估计模型M与剩余子集中其他点之间的拟合误差，并设定一个合适的阈值t后得到的一致点群；
③当满足一致性条件时认为得到正确的模型参数，并利用这些内点（inliers）采用最小二乘法等方法重新计算出更为精确的新版本模型M*；随后重新选取新的初始子集S并重复上述过程；
④经过预定次数的迭代抽样后若仍未能获得一致解，则判定算法失效；否则选择具有最大一致点群的那个结果作为内外点划分的标准，并完成整个优化过程。

DLT

• 研究目的 ：标定相机的内参和外参
  • 定义：基于直接线性变换（DLT）的方法能够有效地建立像点与物点之间坐标的直接线性关系。
  • 特点：
    • 无需预先确定内参和外参
    • 特别适用于无需精确校准相机的情形
    • 适用于中等及以下精度需求的任务
  • 研究内容：待探讨

极几何理论

• 世界坐标系, 相机坐标系, 像素坐標.
• 內部相機參數與外部相機參數.
• 三維重建過程.
• 基本矩陣.
• 基本矩陣.
• 影消點與消失線的位置关系.

极几何学习笔记