ORB特征点检测

date
Oct 21, 2021
Last edited time
Nov 20, 2021 02:15 PM
status
Published
slug
ORB特征点检测
tags
CV
summary
好久没整理笔记了, 把这个ORB特征点检测的笔记整理了一下
type
Post
origin
https://www.notion.so/lazurite/ORB-e88bce0440f74f209d832c770384a4b4
Field
Plat
ORB特征提取、匹配及实现
之前在看SLAM的时候便看到了ORB特征，用它可以快速的提取图像中的特征点并匹配两幅图像。这里就再简单记录一下其原理和C++的实现代码。 ORB特征由关键点和描述子两部分组成。它的关键点称为"Oriented Fast"，是一种改进的FAST角点。描述子称为"BRIEF(Binary Robust Independent Elementary ...
ORB特征提取、匹配及实现
http://zhaoxuhui.top/blog/2018/01/29/ORB%E7%89%B9%E5%BE%81%E6%8F%90%E5%8F%96-%E5%8C%B9%E9%85%8D%E5%8F%8A%E5%AE%9E%E7%8E%B0.html
ORB特征提取、匹配及实现
什么是 ORB怎么实现 ORBFAST 角点检测FAST 角点的检测过程FAST 检测角点的缺点Oriented FAST 角点检测BRIEF描述子怎么加？如何进行匹配?Rotated BRIEFORB 如何优化？rBRIEF

什么是 ORB

ORB（Oriented FAST and Rotated BRIEF）是 Oriented FAST + Rotated BRIEF 的缩写（感觉应该叫 OFRB）。是目前最快速稳定的特征点检测和提取算法，许多图像拼接和目标追踪技术利用 ORB 特征进行实现。
ORB 的优点
  • 尺度不变性
  • 旋转不变性
  • 光变不变性

怎么实现 ORB

要了解 ORB，如果直接去看他们的论文，感觉多半会蒙圈。那是写给学术圈有一定基础的人看的。我等工程狗要了解 ORB 用简单的公式就可以：
ORB = Oriented FAST（特征点） + Rotated BRIEF（特征描述）
其中:
Oriented FAST 是一种改进的 FAST 角点检测方法
Rotate BRIEF 称为特征描述或者描述子

FAST 角点检测

FAST 角点检测方法只比较像素亮度的大小, 如果一个像素与其邻域的像素值差别过大, 则认为这个点可能是角点.

FAST 角点的检测过程

  • Step1: 确定候选角点（Segment Test）
      1. 选择某个像素 ， 其像素值为 。以 为圆心，半径为 3， 确立一个圆，圆上有 16 个像素，分别为
      1. 确定一个阈值 ： (比如 的 )。
      1. 让圆上的像素的像素值分别与 的像素值做差，如果存在连续 个点满足 或 （其中 代表此圆上 个像素中的一个点），那么就把该点作为一个候选点。根据经验，一般令 (即为 FAST-12。其它常用的 取值为 9 和 11， 他们分别被称为 FAST-9，FAST-11).
      由于在检测特征点时是需要对图像中所有的像素点进行检测，然而图像中的绝大多数点都不是特征点，如果对每个像素点都进行上述的检测过程，那显然会浪费许多时间，因此 FAST 采用了一种进行非特征点判别的方法。如上图中，对于每个点都检测第 1、5、9、13 号（即上下左右）像素点，如果这 4 个点中至少有 3 个满足都比 大或者都比 小，则继续对该点进行 16 个邻域像素点都检测的方法，否则则判定该点是非特征点（也不可能是角点，如果是一个角点，那么上述四个像素点中至少有 3 个应该和点相同），直接剔除即可。
  • Step2: 非极大值抑制
      • 经过 Step 1 的海选后，还是会有很多个特征点。好在他们有个缺点：很可能大部分检测出来的点彼此之间相邻，我们要去除一部分这样的点。为了解决这一问题，可以采用非最大值抑制的算法：
    • 假设 P，Q 两个点相邻，分别计算两个点与其周围的 16 个像素点之间的差分和为 V。
    • 去除 V 值较小的点，即把非最大的角点抑制掉。
      • 经过上述两步后 FAST 特征值筛选的结果就结束了。

FAST 检测角点的缺点

  1. FAST 不具有方向信息
  1. FAST 使用的固定的 邻域, 因此不具有尺度不变性

Oriented FAST 角点检测

那么，Oriented FAST 是怎么解决这个问题呢？
  • 尺度不变性：可以用图像金字塔解决；
  • 旋转不变性：可以用灰度质心标定方向解决；
尺度不变性：
  1. 对图像做不同尺度的高斯模糊
  1. 对图像做降采样 (隔点采样)
  1. 对每层金字塔做 FAST 特征点检测
  1. n 幅不同比例的图像提取特征点总和作为这幅图像的 oFAST 特征点。
旋转不变性：
  1. 在一个小的图像块 中，定义图像块的矩。
      2. 写成更通俗易懂的形式如下，也就是说m共有4中情况，这里写出三种情况如下。
  1. 通过矩可以找到图像块的质心
  1. 连接图像块的几何中心 与质心 ，得到一个方向向量 ，特征点方向可以定义为

BRIEF

BRIEF是一种二进制描述子，用来描述两个二进制串之间的距离，其描述向量由很多0、1组成。这里的0、1表示关键点附近两个像素(如p、q)的大小关系，若p比q大，取1,反之取0。如果以一定模式选取选取128对点比较，最后即可得到128维由0、1组成的特征向量。

描述子怎么加？

那下面就看一看它是如何给这些特征点加上描述子的：
  1. 为减少噪声干扰，先对图像进行高斯滤波（方差为 ，高斯窗口为 ）
  1. 以特征点为中心，取 的邻域窗口。在窗口内选取一对（两个）点，比较二者像素的大小，进行如下二进制赋值。
      2. 其中，， 分别是随机点 的像素值。
  1. 在窗口中随机选取 对随机点，重复步骤 2 的二进制赋值，形成一个二进制编码，这个编码就是对特征点的描述，即特征描述子。（一般 N=256）
      2. 这个特征可以由 n 位二进制测试向量表示，BRIEF 描述子：
这里面，最关键的地方其实是随机特征对的选取，论文中就给出了 5 种方法（其中第二种比较好），分别为：
  1. 都呈均匀分布 ；
  1. 都呈高斯分布 ，准则采样服从各向同性的同一高斯分布；
  1. 服从高斯分布 ， 服从高斯分布 , 采样分两步进行：首先在原点处为 进行高斯采样，然后在中心为 处为 进行高斯采样；
  1. 在空间量化极坐标下的离散位置处进行随机采样；
  1. , 在空间量化极坐标下的离散位置处进行随机采样；
这 5 种方法生成的 256 对（OpenCV 中用 32 个字节存储这 256 对）随机点如下（一条线段的两个端点是一对）：
notion image
经过上面三个步骤，我们就可以为每个特征点表示为一个 256bit 的二进制编码。

如何进行匹配?

BRIEF 描述子使用 Hamming 距离来描述两个特征点之间的相似程度.
汉明距离是使用在数据传输差错控制编码里面的，汉明距离是一个概念，它表示两个（相同长度）字对应位不同的数量，我们以 表示两个字 之间的汉明距离。对两个字符串进行异或运算，并统计结果为 1 的个数，那么这个数就是汉明距离。
  1. 两个特征编码对应 bit 位上相同元素的个数小于 的，一定不是配对的。
  1. 一幅图上特征点与另一幅图上特征编码对应 bit 位上相同元素的个数最多的特征点配成一对。
对于 BRIEF 来说，描述子里不包含旋转属性，所以一旦匹配图片有稍微大点的旋转角度，按照 Hamming 算法，匹配度将会大幅下降。

Rotated BRIEF

ORB 如何优化？

  1. ORB 算法进一步增强描述子的抗噪能力，采用积分图像来进行平滑；
  1. 在特征点的 邻域内，产生随机点对，并以随机点为中心，取 的子窗口。
  1. 比较两个随机点的子窗口内 25 个像素的大小进行编码（而不仅仅是两个随机点了）
其次，为 BRIEF 增加旋转不变性（Steered BRIEF）：
ORB 算法采用关键点的主方向来旋转 BEIEF 描述子。
  1. 对于任意特征点，在 邻域内位置为 的 对点集，可以用 的矩阵来表示：
  1. 利用 FAST 求出的特征点的主方向 和对应的旋转矩阵 ，算出旋转的 来代表
  1. 计算旋转描述子（steered BRIEF）：
      2. 其中 为 BRIEF 的描述子。

rBRIEF

最后，rBRIEF - 改进特征点描述子的相关性
使用 steeredBRIEF 方法得到的特征描述子具有旋转不变性，但是却在另外一个性质上不如原始的 BRIEF 算法。是什么性质呢，是描述符的可区分性，或者说是相关性。这个性质对特征匹配的好坏影响非常大。描述子是特征点性质的描述。描述子表达了特征点不同于其他特征点的区别。我们计算的描述子要尽量的表达特征点的独特性。如果不同特征点的描述子的可区分性比较差，匹配时不容易找到对应的匹配点，引起误匹配。ORB 论文中，作者用不同的方法对 100k 个特征点计算二进制描述符，对这些描述符进行统计，如下表所示：
notion image
我们先不看 rBRIEF 的分布。对 BRIEF 和 steeredBRIEF 两种算法的比较可知，BRIEF 算法落在 0 上的特征点数较多，因此 BRIEF 算法计算的描述符的均值在 0.5 左右，每个描述符的方差较大，可区分性较强。而 steeredBRIEF 失去了这个特性。
至于为什么均值在 0.5 左右，方差较大，可区分性较强的原因，这里大概分析一下。这里的描述子是二进制串，里面的数值不是 0 就是 1，如果二进制串的均值在 0.5 左右的话，那么这个串有大约相同数目的 0 和 1，那么方差就较大了。用统计的观点来分析二进制串的区分性，如果两个二进制串的均值都比 0.5 大很多，那么说明这两个二进制串中都有较多的 1 时，在这两个串的相同位置同时出现 1 的概率就会很高。那么这两个特征点的描述子就有很大的相似性。这就增大了描述符之间的相关性，减小之案件的可区分性。
下面我们介绍解决上面这个问题的方法：rBRIEF。
原始的 BRIEF 算法有 5 种取点对的方法，原文作者使用了方法 2。为了解决描述子的可区分性和相关性的问题，ORB 论文中没有使用 5 种方法中的任意一种，而是使用统计学习的方法来重新选择点对集合。
  1. 建立 300k 个特征点测试集。
      2. 备注： 对于测试集中的每个点，预处理参考第一个步骤。考虑其 邻域。这里不同于原始 BRIEF 算法的地方是，这里在对图像进行高斯平滑之后，使用邻域中的某个点的 邻域灰度平均值来代替某个点对的值，进而比较点对的大小。这样特征值更加具备抗噪性。另外可以使用积分图像加快求取 邻域灰度平均值的速度。
  1. 特征点选取
      2. 从上面可知，在 的邻域内共有 个这样的子窗口，那么取点对的方法共有 种，我们就要在这Ｍ种方法中选取 256 种取法，选择的原则是这 256 种取法之间的相关性最小。怎么选取呢？
      • 在 300k 特征点的每个 邻域内按 M 种方法取点对，比较点对大小，形成一个 300k x M 的二进制矩阵 Q。矩阵的每一列代表 300k 个点按某种取法得到的二进制数。
      • 对 Q 矩阵的每一列求取平均值，按照平均值到 0.5 的距离大小从小到大的顺序重新对 Q 矩阵的列向量排序，形成矩阵 T。
      • 将 T 的第一列向量放到 R 中
      • 取 T 的下一列向量和 R 中的所有列向量计算相关性，如果相关系数小于设定的阈值，则将 T 中的该列向量移至 R 中。
      • 按照第四步的方式不断进行操作，直到 R 中的向量数量为 256。
      通过这种方法就选取了这 256 种取点对的方法。这个算法是对均值靠近 0.5 的不相关测试进行贪婪搜索，结果称为 rBRIEF。rBRIEF 在方差和相关性上与旋转 BRIEF 相比有明显进步（如图 4）。PCA 的特征值较高，它们的下降速度要快得多。
至此，ORB 的优化就结束了。我们尝试总结一下：
  • FAST 是用来寻找特征点的。ORB 在 FAST 基础上通过金字塔、质心标定解决了尺度不变和旋转不变。即 oFAST。
  • BRIEF 是用来构造描述子的。ORB 在 BRIEF 基础上通过引入 oFAST 的旋转角度和机器学习解决了旋转特性和特征点难以区分的问题。即 rBRIEF.
现在，有了特征点寻找和描述子，ORB 就成了！
跟以往一样，OpenCV 给我们提供了便捷的接口和使用方法。外部看上跟 SIFT 简直不要太一样。
notion image
notion image

© Lazurite 2021 - 2024