全局视觉定位系统研究的意义

全局视觉定位

1 引言

自主机器人是机器人研究的重点方向，定位和导航是自主机器人研究的核心问题。机器人在执行任务过程中需要确定自身当前位置，根据目标位置和当前位置之间的关系计算如何到达目的地完成任务，其中前者要解决的是自定位问题，后者是导航问题，本文主要研究前者。基于视觉的定位技术还能帮助盲人、视弱以至普通人确定自身位置。 环境模型是定位的基础。基于模型的定位方法包括基于环境三维模型和基于拓扑地图的定位方法。环境三维模型的建模过程非常复杂，特别是在室外的场景中建模可能遇到极大的困难。拓扑定位用图的形式来表示环境模型，其中图中的节点表示环境中的地点，连接节点的边表示地点之间的联系，拓扑定位目的是确定机器人当前的位置与地图中的哪个节点最近，也就是机器人处于哪个地点。

在无人驾驶中，感知、定位、规划决策、控制是四个基本的系统模块。由于当前算法还无法实现绝对的智能，因此依然需要大量的先验知识来提高模块性能、鲁棒性，以实现安全的自动驾驶。其中，高精地图是对道路及周边环境先验知识的集成。而建立在地图之上的准确定位，是判断行车状况的重要依据，为后续的感知、规划决策提供有力支撑。

用于定位的主要数据源目前主要有 GPS、激光雷达、视觉、毫米波雷达。对于视觉而言，虽然目前还没有一套产业内公认的足够可靠的定位方案，但是在这方面探索从未停止过，主要原因如下:

安全性是无人驾驶系统最重要的指标，因此大部分功能的实现，都是多源数据、不同算法结果的耦合。没有哪种传感器方案是完美的，比如 GPS RTK 作为广泛使用的方案，容易受卫星状况、天气状况、 数据链传输状况影响，在隧道内、室内和高楼密集区无法使用。再者，激光雷达虽然具有运算量小，提供深度信息，不受光照影响等优点，但信息稀疏，造价目前还十分昂贵，还不具备大批量车辆装配能力。相比较而言，摄像头提供的视觉信息，虽然会受到光照、天气影响，但是成本低，内容丰富，是目前辅助驾驶方案主要数据源，在地图定位方面也具有很大潜力。

由于主流基于视觉定位算法的核心思想一脉相承，所以本文仅从一系列重要算法框架组件角度，介绍了目前实践中最常用的、基于特征点的全局定位算法，即在地图坐标系下进行定位。本文省略了其中涉及到的优化、几何约束公式推导，旨在给同学们一个定位算法的宏观介绍，具体细节可以参考相关文献和书籍。

2 基于特征点的全局定位算法视觉全局定位，指的是根据当前图像，求出相机在地图坐标系中的 6 个自由度 (Degree of freedom, DoF) 位姿 (Pose) , 即 (x, y, z) 坐标，以及环绕三个坐标轴的角度偏转 (yaw, pitch, roll) 。目前主要可以分类为基于 3D 结构的方法、基于 2D 图像的方法、基于序列图像的方法、基于深度学习的方法。其中，基于深度学习的方法属于端到端 (End-to-end) 的方法，而其它多阶段 (Multi-stage) 非端到端方法虽然流程有所差别，但算法思路大都如 Fig 1 所示:

Figure 1: 根据查询图像，计算 2D-3D 转换矩阵，求解相机位姿

基于已建的地图，匹配历史中最相似的地图子集（图像/点云/特征点），根据匹配到的地图子集所提供的历史位姿真值、特征点坐标真值，计算点对间的变换矩阵，求解当前相机位姿。

所以，其核心包含图像描述、建图查询、特征匹配，位姿计算四个方面。这里仅仅是技术层面的宏观分类，实际算法框架不一定按照此顺序执行，而学者在研究中主要针对这些技术进行改进。整体而言，基于特征点的图像描述基本成熟，发展较少。而位姿计算由于是基于几何约束的优化问题，所以方法也较为固定。相对地，建图查询和特征匹配中改进技术较多。根据数据源不同，建图查询、匹配可以是2D-2D，2D-3D，3D-3D。2D 图像由相机得到，3D 点云可以由提供深度的双目相机、RGB-D 相机产生。

21 特征点提取

2D 图像本身是一个由亮度、色彩组成的矩阵，对视角、光照、色调变化等很敏感，直接使用十分困难。所以，一般会使用具有代表性的点进行相关计算。人们希望这样的点具有旋转、平移、尺度、光照不变性等优点。这些点称为图像的特征 (Feature) 点，包含关键点(Key-points) 和描述子 (Descriptor) 两部分。关键点表达了特征点的位置，而描述子则是对于特征点视觉特性的描述，大多为向量形式。一般而言，描述子主要是以某种模式，统计关键点周围的灰度/色彩梯度变化。一种鲁棒的描述子，在不同图像 的不同情况下，同一特征点的描述子的距离 (Distance) 应当较小。

描述子一般是人为手工设计的 (Hand-crafted features) 。经典的描述如 HOG(Histogram of oriented gradients)[1]，SIFT(Scale-invariant feature transform)[2]，SURF(Speeded up robust features)[3]，AKAZE(Accelerated KAZE)[4] 等。

为了实时性的要求，一些计算速度更快的二值模式描述子被设计出来，如 LBP(Local binary patterns)[5]，BRIEF(Binary robust independent elementary features)，ORB(Oriented FAST and rotated BRIEF)[6]，BRISK(Binary robust invariant scalable key-point)[7]，FREAK(Fast retina key-point)[8] 等。

在深度学习流行之前，这些手工特征一直引领着整个计算视觉产业，直到今天，这些特征在那些缺少标注数据、约束较多的场景下，依然被广泛应用。下面简单介绍两类常用的描述子。

211 SIFTSIFT 描述子可以算是 CV 界最具影响力的技术之一。从关键点检测层面，主要使用高斯差分 (Difference of Gaussian, DoG) 方法检测多尺度空间上的极值点，作为关键点。而 Babaud 等人 [9] 证明了高斯平滑是唯一的能用多尺度空间平滑滤波核，为相关方法提供了充足的理论支持。

那么为什么这样的方法可以找到特征关键点呢

由于高斯核可以通过模糊的方式把图像缩放到不同尺度空间，而梯度变化较小的平滑区域在不同尺度空间的值差距较小。相反，边缘、点、角、纹理等区域则差距较大。这样通过对相邻尺度的图像做差分，最终可以算得多尺度空间的极值点。但是，不同的图像细节本身就处于不同的尺度中。比如一副人物画像中，人脸可能经过较小的模糊就会被平滑为一片，而画框的角则可能需要更大尺度的平滑才会体现出局部“极值”。

因此，如 Fig 2 所示，首先利用图像金字塔将图像先分组 (Octave) ，每组中再使用不同尺度的高斯核，形成一系列的层。这种方式比单纯地使用更多尺度的高斯核效果更好，可以检测到更多的特征点。需要注意的是，虽然 SIFT 使用了 DoG 进行关键点检测，但是其它检测方法也是可行的，并不影响 SIFT 描述子的建立。

Figure 2: 高斯差分方法

SIFT 特征点的描述子，可以理解为一种简单统计版的 HOG。如 Fig 3所示，以检测到的关键点为中心，选取周围 16 × 16 的区域，将区域再组织为 4 个 4 × 4 的块(Patch)。对每一个块，使用 8-bins 的直方图对梯度进行统计，梯度方向决定落入哪个 bin，而梯度的模决定值的大小。为了保证尺度一致性，梯度大小需要进行归一化。为了保证旋转不变性，会根据 16 × 16 的区域内的所有梯度计算出一个主方向， 所有梯度按照主方向进行旋转。最终形成 4 × 4 × 8 的 128 维向量。

Figure 3: 基于梯度分块统计的 SIFT 描述子

212 二值描述子虽然在 SIFT 提出后，又产生了一些改进算法如 SURF、AKAZE 等，但是即使放在 2019 年的今天， 依然难以保证一些场景对算法实时性的要求。例如，手持设备一般算力有限。而无人驾驶中，CPU、GPU资源需要被多个计算密集型模块同时调度。因此，效率是考察算法实用性的重要指标。

为了提高效率，一些二值描述子被学者们提出。一般地，这些方法都是在特征关键点周围进行点采 样。然后比较一对点的灰度大小，结果以 0/1 表示，形成 N 维的二进制描述向量，构成特征点的二值模式。而不同二值描述子最大的差别，主要在于特征采样模式不同、点对选取方法不同。

Figure 4: LBP 描述子采样模式

如 Fig 4所示，LBP 描述子采用对关键点周围，进行环形采样，并与中心关键点的灰度进行比较的方案。圆环上展示了灰度比较结果，黑色的点是 0，白色的点是 1。LBP 是二值描述子最简单的形式，而 ORB 改进了 BRIEF 特征，是目前比较常用的二值描述子。如 Fig 5所示，在点对选取上，与单纯使用中心点不同，ORB 采用了随机的方式，更全面地描述局部细节。但点对的相关性会比较大，从而降低描述子的判别性(Discriminative)。ORB 直接采用了贪婪法、穷举法解决这一问题，寻找相关性低的随机点对。

Figure 5: ORB 描述子点对选取模式

以上二值描述子的采样方式和点对选取方式符合人们一般直觉，而 BRISK、FREAK 等描述子则提供了更加规则化、自带尺度信息的二值模式构建方法。例如，FREAK 描述子模仿了人眼的视觉采样模式。如 Fig 6所示，每个采样点的值是红色圆圈范围内的灰度均值，蓝线则表示点对选取方案。

Figure 6: FREAK 描述子采样、点对选取摸式

二值描述子的高效率，主要体现在三个方面。

(1)二值描述子使用二进制向量作为特征描述，只需要 比较点对大小而不需要计算具体梯度。(2)两个描述子之间比较可以使用计算更快，更容易优化的汉明距离 (Hamming distance)。(3)由于每个二进制向量都对应一个十进制数，所以其本身也代了表一种模 式，而不需要像 SIFT 一样使用直方图进行表示。

二值描述子一般判别性不如 SIFT 家族描述子，但在特定场景下，配合并行化编程，可以在保证相似判别能力的同时，效率高出几十甚至百倍。

22 数据库建立与查询数据库可以理解为于地图 + 索引的集成。地图可以是由单纯的 2D 图像组成，也可以是由 3D 点云地图组成，也可以是 2D 图像和 3D 点云的结合。3D 点云地图生成主要使用三维重建的方法 SfM(Structure from motion)，从时间序列的 2D 图像中推算 3D 信息。如果有双目、RGB-D 相机提供深度，可以获得 更准确的 3D 点信息。其中也包含了一些诸如关键帧(Key-frame)的选取策略，具体方法超出了本文的讨论范围，有兴趣的同学可以自行查阅相关资料。数据库的作用在于:

对于一张输入的观测图像，通过数据库，查询建图历史（图像/点云/特征点），得到当前图像最可能观测到的地图子集（图像/点云/特征点），将地图与观测信息进行匹配，计算变换矩阵，得到观测相机的位姿。

索引则是加速这一过程的关键。数据库本身往往是巨大的。以美团的小袋机器人在北京朝阳大悦城二层试运营为例，安装有 3 个深度相机，即使经过筛选，也使用了将近 8 万张 900 × 600 的。考虑到定位所需要的实时性，查询时不可能每次都和 8 万张一一对比，所以要使用索引技术加速整个算法。这方面技术与 SLAM 中的回环测试，视觉中的图像检索、位置识别等高度重合，以下仅介绍一般方法。

一张图像内有若干特征点，需要先对特征点进行编码，如 VLAD(Vector of locally aggregated descriptors) 编码，用局部描述子形成图像的全局描述。再使用索引，如 kd-tree，进行图像级查询。当然，编码和索引也可以同时进行，如层次化词袋模型(Bag-of-words，BoW)+ 正向索引 + 逆向索引的方法。

221 VLAD 编码VLAD(Vector of locally aggregated descriptors)[10]，如 Fig 7所示，是一种通过聚合局部描述子形成码本 (Codebook) ，通过累加计算描述子与码词 (Word) 的距离，进行全局编码的简单方法。一个 d 维描述子 x 通过 k 个码词的码本进行编码，可以形成一个 dk 维的描述向量，向量中的值是描述子与第

k个码词在第 d 维的差。之后进行 L2 归一化，形成最后的 VLAD 向量。

Figure 7: VLAD 通过描述子与码词的距离进行编码

这里要特别提介绍一下 DenseVLAD[11] 和 NetVLAD[12] 。Torii 等人证明，DenseSIFT 在查询、匹配上都优于标准 SIFT。DenseVLAD 在四个尺度，以 2 个像素间隔的网格状采样模式，提取 SIFT 点。在全局随机采样 25M 个描述子，用 k-means 算法生成 128 个码词的码本。VLAD 向量在归一化后使用 PCA(Principal component analysis) 降维，形成最后 4096 维的 DenseVLAD 向量。如 Fig 8所示，使用DenseSIFT 匹配后的内点（绿）数量更多。

Figure 8: DenseSIFT 和标准 SIFT 特征点，匹配后内点(绿)对比

而 NetVLAD，将 VLAD 中加入了监督信息，加强 VLAD 编码的判别性。如 Fig 9所示，假设红、绿两个描述子来源于不应匹配到一起的两张。由于它们都离 VLAD 中心(×)半径较大且距离相似，经过 L2 归一化，它们编码后值也会很相似。而加入了红、绿描述子所对应不匹配的监督信息后，NetVLAD 生成的中心点(★)则可以更好地区分两个描述子，增加他们编码后的距离（半径）差。

Figure 9: NetVLAD 聚类中心(×)与 VLAD 聚类中心(★)对比。

222 BoW 编码 + 索引基于词袋模型 BoW[13, 14] 的特征编码及其设计思想在计算机视觉发展中具有举足轻重的地位，这里不再展开介绍。本文以 2D 查询图像匹配 2D 图像数据库为例，介绍一种常见的 BoW 编码、索引一体化的模型。如 Fig 10所示，词典 (Vocabulary) 生成采用层次化方法，对于数据集中的所有描述子，按树状结构进行空间划分，每一层都是由 k-means 聚类计算。最终叶子节点就相当于码词(Fig 10中有 9个码词)。

Figure 10: 带正向索引、逆向索引的层次化 BoW 模型

树的构造过程，实际上就是将原始图像编码的过程。但是编码本身并不能加快搜索过程，与 VLAD 相似，还是需要与数据库中的图像逐一比较。因此，这里设计了一种逆向索引(Inverse index) ，不需要比较编码后的向量。其原理如 Fig 11所示，对于一张查询图像 (Query image) ，将提取的描述子输入到 BoW 中，最终会落入码词叶子结点 (Visual word) k 中。而每个码词对应一个索引，记录码词 k

对于数据库中第 i

张图的权重

(Fig10)。这里权重使用 TF-IDF(Term frequency–inverse document frequency) 计算。即如果一个词 k

在某个图像 i

中出现频率高，在其它图像出现频率低，则这个词对于图像判别性较好，权重值

较高。最终通过投票 (Voting) 机制，选出匹配图像。同样需要注意的是，逆向索引不一定建立在树形结构的 BoW 上，它仅仅是提供一种快速查询的方法。

Figure 11: 通过逆向索引 + 投票机制，直接查询图像

而正向索引 (Direct Index) 的作用主要是记录构造 BoW 时，数据库的特征点都落入了哪些结点中，这样当查询到图像后，不需要计算特征点，可以直接通过索引提取特征点。

223 3D 点云查询2D 图像查询中，是先从语意层面查询图像，因此可以通过图像对特征点的空间范围进行约束。3D 点云查询没有这样的约束，所以具诸多难点。如需要考虑空间连续性，查询到的点是否都在可观测范围内等。这里仅介绍 Sattler 在 TPAMI 2016 上发表的方法 [15]，经过多年的打磨，这套方法框架相对简洁、完善。由于其中的词典编码搜索步骤与上节内容有所重叠，这里仅介绍 Active Search 和 Visbility Filtering 两种机制。

Active Search 主要是为了使得匹配到的 3D 点尽可能空间中临近、有几何意义。如 Fig 12所示，红 色的点通过一系列编码、精化过程(红线)，匹配到了点云中一个点。根据所提出优先排序(Prioritization) 框架，从点云中找到一个概率最大的 3D 点，并反向(蓝线)匹配查询图像中的一个对应的 2D 点。

Figure 12: Active Search

Figure 13: Visbility Filtering

Visbility Filtering 主要是为了让匹配到的点尽可能可以被相机观测到（定位是无监督的，并不能知道所匹配到的点是否正确）。这里采用的方法是在使用 SfM 建立 3D 点云地图时，同时建立一个双向可见图 (Bipartite visibility graph) 。如 Fig 13（左）所示，当一个点可以同时被两个相机观测时，则建立拓扑关系。Fig 13（中）里，蓝色的点为匹配到的点，它们从观测视角上存在冲突。通过在已有拓扑上进 行图聚类，将相机两两分组，如 Fig 13（右）。这样就可以生成新的图拓扑关系。之后通过判断每个子图(Sub-graph)间的重合情况，过滤掉那些那大概率不可见的点。

需要说明的是，虽然双目相机和 RGB-D 相机可以获取深度，查询 2D 图像也可以获得限定范围内的 3D 特征点坐标，但是由于目前技术限制，在室内材质复杂，室外大尺度场景下，深度并不可靠。所以 2D图像点和 3D 点云地图的匹配依然是一种重要的方法。

23 特征点匹配特征点匹配过程可以是在数据库查询中自适应完成的，这多见于基于 3D 结构的查询。匹配也可以是在查询后单独进行，多见于基于 2D 图像查询。特征匹配的目的是，为后续的变换矩阵计算提供匹配的点对集，实现位姿的解算。

231 经典 RANSAC随机抽样一致算法 (Random sample consensus，RANSAC)[16] 是一种经典的数据过滤、参数拟合算法。它假设数据（内点，Inliers）分布符合一定的数学模型，通过迭代计算，去除外点 (Outliers) 、噪声点， 同时获取概率上最佳的模型参数。在全局定位中，内点指正确的匹配，外点指错误的匹配，参数模型指匹配点对的空间变换矩阵。如 Fig 14所示，经过 RANSAC 算法优化后，匹配更加合理。RANSAC 所期望找到的匹配子集需要满足两个指标：内点重投影误差尽可能小；内点数量尽可能多。所以基本流程如下：

· ①采样初始子集。

· ②计算变换矩阵。

· ③ 根据变换矩阵计算匹配点的重投影误差。

· ④ 去除误差较大的点

· ⑤ 循环①-④，保留最满足指标的匹配方案。

Figure 14: （上）原始特征匹配；（下）经过 RANSAC 算法优化后的匹配

其中，初始候选匹配是根据描述子之间的距离产生的，但重投影误差则只和关键点的空间位置有关， 与描述子本身无关。具体投影矩阵方法请参考“24 位姿计算”。需要指出的是，RANSAC 算法受到原始匹 配误差和参数选择的影响，只能保证算法有足够高的概率合理，不一定得到最优的结果。算法参数主要包括阈值和迭代次数。RANSAC 得到可信模型的概率与迭代次数成正比，所得到的匹配数量和阈值成反比。因此实际使用时，可能需要反复尝试不同的参数设置才能得到较优的结果。

学者们对经典 RANSAC 算法进行了很多改进，如 Fig 15所示，提出了全局 RANSAC(Universal- RANSAC)[17] 的结构图，形成了具有普适性的 RANSAC 架构，涵盖了几乎所有的 RANSAC 的改进方 面，如预滤波、最小子集采样、由最小子集生成可靠模型、参数校验、模型精化。

Figure 15: Universal-RANSAC 通用算法框架

233 可微分 RANSAC由于手工描述子在定位领域依然表现出较高的性能，所以一些学者开始探索使用深度学习代替算法框架中的某些部分，而不是直接使用端到端的位姿估计模型完全代替传统方法。可微分 RANSAC(Differentiable RANSAC，DSAC)[18] 旨在用概率假说选择代替确定性假说选择，使得 RANSAC 过程可以被求导，流程如 Fig 16所示，其中“Scoring”步骤依然采用重投影误差作为指标，所不同的是，误差是基于整张图像而不是特征点，而原先筛选特征点匹配的过程被换为了直接以概率筛选相机位姿假设 h 的过程。虽然目 前方法局限性比较大，但 DSAC 为如何在当前无监督为主的定位算法框架中加入先验知识，提供了一种可行的思路。

Figure 16: 差分 RANSAC 算法框架

P3P 法可以看作是 PnP 法的特殊解法，如 Fig 17所示，利用三角形相似性质增加更多约束，只需要 3 对点就可以求解。其它解法还有直接线性变换法 (Direct linear transformation，DLT)，EPnP(Efficient PnP) 法，和 UPnP(Uncalibrated PnP)等。相对于以上线性优化方法，非线性优化方法如Bundle Adjustment(BA) 也有着广泛的应用。BA 方法在视觉 SLAM 中是一种“万金油”的存在，可以同时优化多个变量，这样可以一定程度缓解局部误差带来的系统不鲁棒，感兴趣的同学可以翻阅相关资料更深入地进行了解。

Figure 17: 2D-3D 变换矩阵计算中的 P3P 方法

3 总结与展望

本文从图像描述、建图查询、特征匹配，位姿计算四个方面介绍了基于特征点的位姿估计算法。虽然传统视觉全局定位方法目前依然是实际应用中的首选，但是，传统方法是建立在特征点被正确定义、正确提取、正确匹配、正确观测的前提下进行的，这一前提对于视觉本身而言就是巨大的挑战。其次，由于传统方法是 multi-stage 框架，而非 end-to-end，所以中间每个环节，环节之间的交互，都需要众多参数调整，每个环节的技术都可以作为一个单独的研究方向。实际应用时，也需要加入对应具体场景的大量tricks，工程上比较复杂。

而人们对 end-to-end 方法的期望催生出了如 PoseNet，VLocNet，HourglassNet 等网络，在 benchmark上取得了不错的成绩。笔者认为目前 end-to-end 的方法还存在很多问题，主要有 loss function 缺少几何 约束，建图时位姿的 6 自由度空间并不连续，与输入空间难以形成良好映射，而且缺少相应的位姿回归、 精化机制等。不能否认，作为非线性空间最有力的建模工具，深度学习在未来会更多地出现在定位领域中。

回归到视觉定位本身，由于视觉最重要的优势就是成本低、语意丰富、使用场景限制少。因此，以视觉为主，其它低成本传感器为辅的定位融合方案在未来也将会是一个重要的课题。

参考资料

[1] Dalal, N, and B Triggs ”Histograms of oriented gradients for human detection” CVPR, 2005

[2] Lowe, David G ”Distinctive Image Features from Scale-Invariant Keypoints” IJCV, 2004

[3] Bay, Herbert, T Tuytelaars, and L V Gool ”SURF: Speeded Up Robust Features” ECCV, 2006[4] PFAlcantarilla,JNuevo,andABartoliFast explicit diffusion for accelerated features in nonlinear scale spaces BMVC, 2013

[5] Ojala, Timo ”Gray Scale and Rotation Invariant Texture Classification with Local Binary Patterns” ECCV, 2000

[6] Rublee, Ethan , et al ”ORB: An efficient alternative to SIFT or SURF” ICCV, 2011

[7] Leutenegger, Stefan , M Chli , and R Y Siegwart ”BRISK: Binary Robust invariant scalable keypoints” ICCV, 2011

[8] Alahi, Alexandre , R Ortiz , and P Vandergheynst ”FREAK: Fast retina keypoint” CVPR, 2012

[9] Witkin, A P, M Baudin, and R O Duda ”Uniqueness of the Gaussian Kernel for Scale-Space Filtering” TPAMI, 1986

[10] Jegou, Herve , et al ”Aggregating local descriptors into a compact image representation” CVPR, 2010

[11] Torii, Akihiko , et al ”24/7 place recognition by view synthesis” CVPR, 2015

[12] Arandjelovic, Relja, et al ”NetVLAD: CNN architecture for weakly supervised place recognition” TPAMI, 2017

[13] Li, Fei Fei ”A Bayesian Hierarchical Model for Learning Natural Scene Categories CVPR, 2005

[14] Galvez-Lopez, D , and J D Tardos ”Bags of Binary Words for Fast Place Recognition in Image Sequences” TRO, 2012

[15] Sattler, Torsten , B Leibe , and L Kobbelt ”Efficient & Effective Prioritized Matching for Large- Scale Image-Based Localization” TPAMI, 2016

[16] Fischler, Martin A, and R C Bolles ”Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography” Communications of the ACM, 1981

[17] Raguram, Rahul , et al ”USAC: A Universal Framework for Random Sample Consensus” TPAMI, 2013

[18] Brachmann, Eric, et al ”DSAC —Differentiable RANSAC for Camera Localization” CVPR, 2017

// 导入OpenCV模块

var cv = require("opencv");

// 读取图像

var img1 = cvimread("/sdcard/img1jpg");

var img2 = cvimread("/sdcard/img2jpg");

// 创建SIFT检测器对象

var sift = new cvFeatureDetector("SIFT");

// 检测图像中的关键点和描述符

var keypoints1 = siftdetect(img1);

var keypoints2 = siftdetect(img2);

var descriptors1 = siftcompute(img1, keypoints1);

var descriptors2 = siftcompute(img2, keypoints2);

// 创建FLANN匹配器对象

var matcher = new cvMatcher("FlannBased");

// 对两幅图像中的关键点进行匹配

var matches = matchermatch(descriptors1, descriptors2);

// 筛选出最优的匹配结果

var bestMatches = matcherfilterMatches(matches, 075);

// 在两幅图像中绘制匹配结果

var output = new cvMat();

cvdrawMatches(img1, keypoints1, img2, keypoints2, bestMatches, output);

// 保存匹配结果图像

cvimwrite("/sdcard/matchesjpg", output);

以上代码中，我们使用了AutoJS的require()函数导入OpenCV模块，并使用cvimread()函数读取了两幅图像。然后，我们创建了一个SIFT检测器对象，并使用它检测了两幅图像中的关键点和描述符。接着，我们创建了一个FLANN匹配器对象，并使用它对两幅图像中的关键点进行了匹配。最后，我们筛选出了最优的匹配结果，并使用cvdrawMatches()函数在两幅图像中绘制了匹配结果，并将结果保存到了本地。

SIFT具有尺度不变性和旋转不变性。具体分为：

尺度规范化的Laplacian of Gaussian(LoG)算子具有尺度不变性。在具体实现中，可用Difference of Gaussian(DoG)算子近似LoG算子，在构建的尺度空间中检测稳定的特征点。

因此尺度空间的构架包含：

sigma越大丢失的高频越多

每个像素要和周围的26个像素比较，确定它是当前尺度下，相邻频率信息的一个峰值。

为什么要精确定位，因为我们这个不论是x、y、sigma方向上都是离散的，要在连续的变化上求得极值点。

DoG函数D(X)=D(x,y,σ)在尺度空间的的Taylor展开式为：

令D(X)导数为0，得到极值点的偏移量：

若X^=(x,y,σ)T在任意一个维度大于05，说明极值点精确位置距离另一个点更近，应该改变当前关键点的位置，定位到新点后执行相同 *** 作，若迭代5次仍不收敛，则认为该检测点不为关键点。精确关键点处函数值为：

|D(X^)|过小易受噪声点的干扰而变得不稳定，若其小于某个阈值(例如003或者004/S)，则将该极值点删除。

为了得到稳定的特征点，只是删除DoG响应值低的点是不够的。由于DoG对图像中的边缘有比较强的响应值，而一旦特征点落在图像的边缘上，这些点就是不稳定的点。一方面图像边缘上的点是很难定位的，具有定位歧义性；另一方面这样的点很容易受到噪声的干扰而变得不稳定。

一个平坦的DoG响应峰值往往在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。而主曲率可以通过2×2的Hessian矩阵H求出

D 的主曲率和H的特征值成正比，令α为较大特征值，β为较小特征值，且α/β=r，则

(r+1)2/r在两个特征值相等时最小，随着r的增大而增大，r值越大，说明两个特征值的比值越大，正好对应边缘的情况。因此，设定一个阈值rt，若满足

则认为该关键点不是边缘，否则予以剔除。

好了，到这一步，我们已经完成了特征点的筛选，并且通过高斯金字塔的设计实现了尺度不变性。接下来，就该去搞定旋转不变性了。

这里的旋转不变性跟咱们角点自带的旋转不变性有一些不同。Harris的角点不变性靠的是旋转后，该是角点的地方还是角点，所以对于整张图对应的所有角点这个尺度看，它是具备旋转不变性的。但是SIFT中，我们希望给每个特征点赋值一个方向，这样，对于单个特征点来说，不管是如何缩放、旋转，这个方向作为它的一个属性都不会变。

为了使特征描述子具有旋转不变性，需要利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数。对于在DoG金字塔中检测出的关键点，在其所在高斯金字塔图像的3σ邻域窗口内计算每个像素的梯度幅值和方向，公式如下：

L为关键点所在尺度空间的灰度值，m(x,y)为梯度幅值，θ(x,y)为梯度方向。对窗口内的像素的模值m(x,y)按σ=15σoct、邻域窗口为3σ=3×15σoct的高斯分布加权。

在完成关键点的梯度计算后，使用直方图统计邻域内像素的梯度和方向，梯度直方图将梯度方向(0,360∘)分为36柱(bins)，如下图所示，直方图的峰值所在的方向代表了该关键点的主方向。

梯度方向直方图的峰值代表了该特征点处邻域梯度的主方向，为了增强鲁棒性，保留峰值大于主方向峰值80%的方向作为该关键点的辅方向，因此，在相同位置和尺度，将会有多个关键点被创建但方向不同，可以提高特征点匹配的稳定性。

至此，将检测出的含有位置、尺度和方向的关键点即是该图像的SIFT特征点。

是用128维向量对每个关键点进行描述。

通过上面的步骤，对于每一个关键点，拥有三个信息：位置、尺度以及方向。接下来就是为每个关键点建立一个描述符，用一组向量将这个关键点描述出来，使其不随各种变化而改变，比如光照变化、视角变化等等。这个描述子不但包括关键点，也包含关键点周围对其有贡献的像素点，并且描述符应该有较高的独特性，以便于提高特征点正确匹配的概率。

SIFT描述子是关键点邻域高斯图像梯度统计结果的一种表示。通过对关键点周围图像区域分块，计算块内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。

特征描述子与特征点所在的尺度有关，因此，对梯度的求取应在特征点对应的高斯图像上进行。将关键点附近的邻域划分为dd(Lowe建议d=4)个子区域，每个子区域做为一个种子点，每个种子点有8个方向。每个子区域的大小与关键点方向分配时相同。

每一个小格都代表了特征点邻域所在的尺度空间的一个像素 ，箭头方向代表了像素梯度方向，箭头长度代表该像素的幅值。然后在4×4的窗口内计算8个方向的梯度方向直方图。绘制每个梯度方向的累加可形成一个种子点。

这样两幅图的特征坐标系都是以关键点的方向为准了，旋转不变性。

如上统计的4 4 8=128个梯度信息即为该关键点的特征向量。特征向量形成后，为了去除光照变化的影响，需要对它们进行归一化处理，对于图像灰度值整体漂移，图像各点的梯度是邻域像素相减得到，所以也能去除。

描述子向量门限。非线性光照，相机饱和度变化对造成某些方向的梯度值过大，而对方向的影响微弱。因此设置门限值(向量归一化后，一般取02)截断较大的梯度值。然后，再进行一次归一化处理，提高特征的鉴别性。

按特征点的尺度对特征描述向量进行排序

对两幅图像中检测到的特征点，可采用特征向量的欧式距离作为特征点相似性的度量，取图像1中某个关键点，并在图像2中找到与其距离最近的两个关键点，若最近距离与次近距离的比值小于某个阈值，则认为距离最近的这一对关键点为匹配点。降低比例阈值，SIFT匹配点数量会减少，但相对而言会更加稳定。阈值ratio的取值范围一般为04~06。

SIFT是一种检测、描述、匹配图像局部特征点的算法，通过在尺度空间中检测极值点，提取位置、尺度、旋转不变量，并抽象成特征向量加以描述，最后用于图像特征点的匹配。SIFT特征对灰度、对比度变换、旋转、尺度缩放等保持不变性，对视角变化、仿射变化、噪声也具有一定的鲁棒性。但其实时性不高，对边缘光滑的目标无法准确提取特征点

旋转不变性是计算关键点方向并旋转得到的；尺度不变性是图像下采样获得高斯金字塔得到的。

滤波一般指就是一个二维矩阵（卷积核），卷积就是用这个矩阵与原图像进行卷积运算得到一个新的图像。

尺度是一个视觉问题，不是数学问题，简单的来讲就是你在不同距离上观察一个物体，产生的视觉感受是不同的。比如你站在不同距离观察一片雪花，离的越远你感受的形状越接近于a->b->c->d的顺序，就是越远，你看到的越是一个大概的轮廓。

一幅图像的SIFT特征提取，分为4个步骤：

SIFT特征点其实就是尺度空间中稳定的点/极值点，那么，为了得到这些稳定点

对于一幅输入图像，为了进行sift特征检测、实现scale-invariant（任何尺度下都能够有对应的特征点），需要对该图像的尺度空间进行分析，即建立高斯金字塔图像、得到不同scale的图像，这里的高斯金字塔与最原始的高斯金字塔稍微有点区别，因为它在构造尺度空间时，将这些不同尺度图像分为了多个Octave、每个Octave又分为了多层。下图给出了Sift中的高斯金字塔的结构图；

构造完尺度空间（差分高斯金字塔）后，接下来的任务就是“在尺度中间中检测出图像中的稳定特征点”：

对于DoG中每一个采样点（每一个Octave中每一层），将其与它邻域内所有像素点（8+18=26）进行比较，判断其是否为局部极值点（极大或者极小），更加具体地：如下图所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。 一个点如果在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点。但要注意：这种相邻层之间的极值点的寻找是在同一Octave中的相邻尺度之间进行寻找的，而不要跨组！

通过拟和“三维二次函数”可以精确确定关键点的位置和尺度（达到亚像素精度），具体方法还未知，可以得到一系列的SIFT候选特征点集合，但由于这些关键点中有些具有较低的对比对，有些输属于不稳定的边缘响应点(因为DoG算子会产生较强的边缘响应)，所以，为了增强匹配稳定性、提高抗噪声能力，应该将这2类关键点去除，实现对候选SIFT特征点集合的进一步净化：

上面只是得到了每个关键点的方向，接下来，需要确定每个关键点的特征向量，具体方式如下：

现有A、B两幅图像，分别利用上面的方法从各幅图像中提取到了k1个sift特征点和k2个特征点及其对应的特征描述子，即k1 128维和k2 128维的特征，现在需要将两图中各个scale（所有scale）的描述子进行匹配。

接下来采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。

[1] SIFT特征提取及匹配

[2] 图像处理之特征提取

以上就是关于全局视觉定位系统研究的意义全部的内容，包括:全局视觉定位系统研究的意义、求在autojs中使用opencv的SIFT特征匹配例子、图像特征之SIFT特征匹配等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！