ORB特征提取算法（理论篇）
Abstract
ORB 是 Oriented Fast and Rotated Brief 的简称，可以⽤来对图像中的关键点快速创建特征向量，这些特征向量可以⽤来识别图像中的对象。
其中，Fast 和 Brief 分别是特征检测算法和向量创建算法。ORB ⾸先会从图像中查特殊区域，称为关键点。关键点即图像中突出的⼩区域，⽐如⾓点，⽐如它们具有像素值急剧的从浅⾊变为深⾊的特征。然后 ORB 会为每个关键点计算相应的特征向量。ORB 算法创建的特征向量只包含 1 和 0，称为⼆元特征向量。1 和 0 的顺序会根据特定关键点和其周围的像素区域⽽变化。该向量表⽰关键点周围的强度模式，因此多个特征向量可以⽤来识别更⼤的区域，甚⾄图像中的特定对象。
ORB 的特点是速度超快，⽽且在⼀定程度上不受噪点和图像变换的影响，例如旋转和缩放变换等。
FAST 算法
ORB 特征检测的第⼀步是查图像中的关键点，⽽关键点检测算法即使⽤ FAST 算法。
FAST 是 Features from Accelerated Segments Test 的简称，可以快速选择关键点，算法步骤如下：
位字符串是什么给与⼀个像素点 p，FAST ⽐较⽬标 p 圆圈范围中的 16 个像素，每个像素按⾼于 p，⼩于 p，或者与 p 相似，分为三类。
注意这⾥的⽐较是带有阈值 h 的。对于给定的阈值 h，更亮的像素将是亮度超过 Ip+h 的像素，更暗的像素将是亮度低于 Ip-h 的像素，相似像素将是亮度在这两个值之间的像素。在对像素分类后，如果圈圈上有 8 个以上的相连像素，暗于或亮于 p 则将像素 p 选作关键点。
⽽ FAST 如此⾼效的原因是，仅将 p 与圆圈中的 4 个等距像素相⽐。这种⽅法已经证明和⽐较 16 个周围像素的效果相同。如果⾄少有⼀对连续像素的亮度⾼于或低于 p，则将 p 选作关键点。这种优化使得在整个图像中搜索关键点的时间缩短了四倍。
但是，这些关键点可以像我们提供什么样的信息？对⽐邻近像素的亮度有何意义？⾸先观察⼀下 FAST 算法标记关键点的图像。
可以看出关键点位于亮度有变化的区域，此类区域通常确定了某种边缘，例如猫的⽖⼦。边缘定义了猫的界限，以及脸部区域的界限，因此这些关键点使我们能够识别这只猫，⽽不是图像中的任何其他对象或背景。
BRIEF 算法
我们已经知道 ORB 如何使⽤ FAST 确定图像中的关键点，下⾯我们将了解 ORB 如何使⽤ BRIEF 算法，并将这些关键点转换为特征向量。ORB 算法的第⼆步是将第⼀个算法发现的关键点变成特征向量，这些特征向量可以共同表⽰⼀个对象。
要创建特征向量，ORB 会⽤到 BRIEF 算法。BRIEF 是 Binary Robust Independent Elementary Features 的简称，它的作⽤是根据⼀组关键点创建⼆元特征向量。正如在简介视频中看到的，⼆元特征向量⼜称为⼆元描述符，是仅包含 1 和 0 的特征向量。在 BRIEF 中每个关键点由⼀个⼆元特征向量描述，该向量⼀般为 128-512 位的字符串，其中仅包含 1 和 0。
注意，这⾥的“位”是⼆进制位的简称，1 位只能存储⼀个⼆进制值，要么 1 要么是 0。位字符串是⼀组位，这些是位字符串⽰例。
第⼀个是 1 位字符串因此只存储 1 位。第⼆个是 2 位字符串，因此可以存储 2 个⼆进制位。在此⽰例中它存储的是 0 和 1。同样，第三个是 3 位字符串，因此可以存储 3 个位，以此类推。计算机运⾏的是⼆进制或机器代码，因此使⽤⼆元特征向量的⼀⼤优势是可以⾮常⾼效地存储在内存中，并且可以快速计算。速度对实时应⽤来说极为关键，这些特性不仅使 BRIEF 速度⾮常快，⽽且使 BRIEF 能够在计算资源⾮常有限的设备（例如智能⼿机）上运⾏。
BRIEF 如何为每个点创建这些⼆元描述符？BRIEF 算法⾸先利⽤⾼斯核对给定图像进⾏平滑处理，以防
描述符对⾼频噪点过于敏感。然后，对于给定关键点，例如猫⽖上的这个点。
BRIEF 从该关键点周围界定好的邻域内随机选择⼀对像素，关键点周围的邻域称为 Patch，它是⼀个具有特定像素宽度和⾼度的正⽅形。这⾥显⽰的随机对中的第⼀个像素，是⼀个蓝⾊正⽅形，它是从以关键点为中⼼的⾼斯分布中抽取的⼀个像素，标准偏差或分散趋势为σ。
这⾥显⽰为黄⾊正⽅形的像素，是随机对中的第⼆个像素。它是从以该第⼀个像素为中⼼的⾼斯分布中抽取的像素，标准偏差为σ/2，经验表明这种⾼斯选择提⾼了特征匹配率。
BRIEF 然后开始为关键点构建⼆元描述符，⽅法是如下所⽰地⽐较这两个像素的亮度。如果第⼀个像素⽐第⼆个亮，则为描述符中的相应位分配值 1，否则分配值 0。
在这个⽰例中第⼆个像素⽐第⼀个亮，因此我们为特征向量的第⼀个位分配值 0。特征向量的第⼀个位对应的是这个关键点的第⼀个随机点对，然后 BRIEF 会针对同⼀关键点选择新的随机像素对⽐较它们的亮度并为特征向量中的下个位分配 1 或 0。
在上⾯新选取的随机像素中，我们看到现在第⼀个像素⽐第⼆个亮，因此为特征向量中的第⼆个位分配值 1。
对于 256 位向量，BRIEF 会针对同⼀关键点重复这⼀流程 256 次，然后转到下个关键点。接着将 256
个像素亮度⽐较结果放⼊该关键点的
⼆元特征向量中。BRIEF 像这样为图像中的每个关键点创建⼀个向量。
缩放不变性和旋转不变性
ORB 使⽤ FAST 检测图像中的关键点，并且通过额外的⼏个步骤确保⽆论对象的⼤⼩或位置如何都能检测到图像中的对象。
给定⼀个图像 ORB 算法⾸先开始构建图像⾦字塔。
图像⾦字塔是单个图像的多尺度表⽰法，由⼀系列原始图像的不同分辨率版本组成。⾦字塔的每个级别都由上个级别的图像下采样版本组成。下采样是指图像分辨率被降低，⽐如图像按照 1/2 ⽐例下采样。因此⼀开始的 4x4 正⽅形区域现在变成 2x2 正⽅形。图像的下采样包含更少的像素，并且以 1/2 的⽐例降低⼤⼩。
这是⼀个包含 5 个级别的图形⾦字塔⽰例，在每个级别图像都以 1/2 的⽐例下采样。到了第四级别图像的分辨率是原始图像的 1/16。ORB 创建好图像⾦字塔后，它会使⽤ FAST 算法从每个级别不同⼤⼩的图像中快速到关键点。因为⾦字塔的每个级别由原始图像的更⼩版本组成，因此原始图像中的任何对象在⾦字塔的每个级别也会降低⼤⼩。
通过确定每个级别的关键点 ORB 能够有效发现不同尺⼨的对象的关键点，这样的话 ORB 实现了部分缩放不变性。这⼀点很重要，因为对象不太可能在每个图像中的⼤⼩都完全⼀样，尤其是像猫这样的对象某个时刻可能靠近相机，在另⼀个时刻离相机很远。
现在 ORB 获得了与这个图像⾦字塔每个级别相关的关键点。在发现⾦字塔所有级别中的关键点后，ORB 现在为每个关键点分配⼀个⽅向，例如朝左或朝右，取决于该关键点周围的强度是如何变化的。
我们详细了解下背后原理。ORB ⾸先选择⾦字塔Level 0 中的图像，对于该图像 ORB 将计算关键点的⽅向。
⽅法是⾸先计算以该关键点为中⼼的⽅框中的强度形⼼。强度形⼼可以看做给定 patch 中的平均像素强度的位置。计算强度形⼼后，通过画⼀条从关键点到强度形⼼的向量，获得该关键点的⽅向，如上图所⽰。这个关键点的⽅向是向下并朝左，因为这个区域的亮度朝着这个⽅向增强。
为⾦字塔级别 0 的图像中的每个关键点分配⽅向后，ORB 现在为所有其他⾦字塔级别的图像重复相同流程。需要注意的是，在每个图像⾦字塔级别，Patch ⼤⼩并没有缩减，因此相同 Patch 在每个⾦字塔级别覆盖的图像区域将更⼤，导致关键点的⼤⼩各不相同。
可以从此处看出这⼀点。在此图中，圆圈表⽰每个关键点的⼤⼩，更⾼的⾦字塔级别中的关键点⼤⼩更⼤。
到关键点并为其分配⽅向后，ORB 现在使⽤修改后的 BRIEF 版本创建特征向量，这个修改后的 BRIEF 版本称为 rBRIEF，即 Rotation-Aware BRIEF。⽆论对象的⽅向如何，它都可以为关键点创建相同的向量，使得 ORB 算法具有旋转不变性，意味着它可以在朝着任何⾓度旋转的图像中检测到相同的关键点。和 BRIEF ⼀样 rBRIEF ⾸先在给定关键点周围的已界定 patch 中随机选择 256 个像素对，以构建 256位向量。然后根据关键点的⽅向⾓度旋转这些随机像素对，使随机点的⽅向与关键点的⼀致。最后, rBRIEF 对⽐随机像素对的亮度并相应地分配 1 和 0 创建对应的特征向量，为图像中的所有关键点创建的所有特征向量集合称之为 ORB 描述符。
使⽤ ORB 描述符进⾏对象识别
你已经知道 ORB 算法的原理，但可能会疑问到底可以如何使⽤ ORB 描述符进⾏对象识别呢？我们来看⼀个⽰例以了解 ORB 如何检测到具有不同⼤⼩和⽅向的同⼀对象。
假设我想在其他图像中检测到此⼈的⾯孔，例如在这个多⼈合影中，我们将第⼀张图像称为训练图像，第⼆张图像，即要对其进⾏⼈脸检测的图像，称为查询图像。
给定这个训练图像，我想在这个查询图像中查相似的特征，第⼀步是计算训练图像的 ORB 描述符并将其存储到内存中。
ORB 描述符将包含⼆元特征向量，⽤于描述这个训练图像中的关键点。第⼆步是计算并保存查询图像的 ORB 描述符，获得训练和查询图像的描述符后，最后⼀步是使⽤相应的描述符对这两个图像进⾏关键点匹配，通常使⽤匹配函数来完成这⼀步。
匹配函数的⽬的是匹配两个不同图像的关键点，⽅法是⽐较这两个图像的描述符，看看它们是否很相近可以匹配。当匹配函数对⽐两个关键点时，它会根据某种指标得出匹配质量，这种指标表⽰关键点特征向量的相似性。可以将这个指标看作与两个关键点之间的标准欧⼏⾥得距离相似性。某些指标会直接检测特征向量是否包含相似顺序的 1 和 0。需要注意的是，不同的匹配函数使⽤不同的指标来判断匹配质量。对于 ORB 等使⽤的⼆元描述符来说，通常使⽤汉明指标，因为它执⾏起来⾮常快。
汉明指标通过计算⼆元描述符之间的不同位数量判断两个关键点之间的匹配质量。在⽐较训练图像和查询图像的关键点时，差异数最少的关键点对被视为最佳匹配。匹配函数对⽐完训练图像和查询图像中的所有关键点后，返回最匹配的关键点对。
我们的训练图像和查询图像之间的最匹配点显⽰在此处，可以清晰地看出训练图像和查询图像之间最匹配的点主要对应的是训练图像的⾯孔。有⼀两个特征不是太匹配，原因可能是该图像区域的强度模式⽐较相似。因为⼤部分点对应的是训练图像中的脸部，可以看出匹配函数能够在查询图像中正确地识别该⾯孔。
后记
本⽂是 Udacity 计算机视觉纳⽶学位课程笔记，下⼀步将在 OpenCV 中应⽤ ORB 算法，并观察 ORB 算法的鲁棒性。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。