060｜ORB：让二进制特征既快又有区分力

总览 · 目录 · 上一篇：CHOMP · 下一篇：STOMP

论文：Ethan Rublee、Vincent Rabaud、Kurt Konolige、Gary Bradski，ORB: An Efficient Alternative to SIFT or SURF，ICCV 2011，2564–2571。出版记录；IPOL 保存的作者原稿全文。以下依据八页原稿全文；不是对 ORB-SLAM 的解读。另用 OpenCV 的 FAST 文档区分检测器术语与论文表达，当前库实现不视为 2011 年实验的逐行复现。

先接住前作的问题

SIFT提供稳健局部描述，但实时机器人还会受计算和存储约束。ORB把方向补偿与统计筛选接入二进制测试。

五个前置概念

五个前置概念：关键点检测寻找可重复的局部位置；描述子编码局部外观以便比较；方向归一化在局部坐标里补偿旋转；比特方差与相关性衡量测试是否有区分力及是否重复；汉明距离统计两个比特串的不同位置数。

一、问题设定：方向补偿后的二进制描述怎样保持区分力

机器人要认出两幅图像中同一块纹理，通常先找关键点，再给每个点生成一个便于比较的描述。SIFT 很有效，但当时的 CPU 和手机对计算量十分敏感。BRIEF 用许多简单的亮度大小比较生成比特串，非常快，却害怕图像旋转。

背景与任务定义

输入是图像，输出是关键点位置、尺度层级、方向和描述子。匹配器再根据距离寻找候选对应，几何模块决定这些对应是否能解释单应、相对位姿或物体姿态。状态、奖励和动作不是这篇的设定。

检测器回答“在哪里看”，描述子回答“这一小块像什么”。FAST 找角点，BRIEF 编码图块；二者不是同一件事。ORB 的完整组合还涉及图像金字塔、Harris 排序和方向估计，因此比较完整特征系统的时间不能仅比较最后几次比特运算。

本文含离线统计选择：从 PASCAL 2006 图像提取约 30 万关键点，用于挑选测试对。这里的“学习”不是深度网络或强化学习，也不是在线每帧重新训练。选出的模式固定后，运行阶段只计算方向和比特值。

二、给FAST估方向，再筛选高方差低相关测试

oFAST：位置、排序与方向

在多个金字塔层检测 FAST 候选，以 Harris 角点响应排序保留目标数量。FAST-9 中的 9 与连续圆周亮暗测试有关，不应把原稿第 3.1 节的括号描述直接实现成半径九像素的新检测器；具体圆周布局需按 FAST 定义或对应实现核对。

方向来自图块灰度质心。以关键点为原点定义矩

$$m_{pq}=\sum_{x,y}x^py^qI(x,y),\qquad \theta=\operatorname{atan2}(m_{01},m_{10}).$$

向较亮一侧偏移的质心给出一个方向。圆形取样区域减少旋转改变支持区的问题；当质心接近中心时，方向会对噪声敏感。它给一个主方向，不像 SIFT 可以为某些关键点分配多个方向。

从 BRIEF 到 steered BRIEF

一个二进制测试比较两个平滑子区域：

$$b_i=\mathbf1[I(x_i)<I(y_i)].$$

本文使用 256 个测试。每个测试是 31×31 图块中的两块 5×5 子窗口比较，用平滑减少像素噪声影响。256 比特等于 32 字节，这是描述子本体大小，不包括关键点结构或索引开销。

根据 $\theta$ 同时旋转每个测试点的位置：

$$b_i(\theta)=\mathbf1[I(R_\theta x_i)<I(R_\theta y_i)].$$

如果物体图块转了一个角度，估计方向也随之转动，采样就大致回到相同局部结构。原实现把角度离散为 30 档，每档 12°，预计算旋转模式以降低运行成本。它是近似旋转补偿，不是对任意插值、模糊和视角变化精确不变。

为什么“旋转一下”还不够

对一个比特，若取 1 的概率是 $p$，方差为 $p(1-p)$，在 $p=0.5$ 时最大。若某测试对几乎所有关键点都返回 1，它很稳定，却不能区分不同图块。

方向对齐会让角点外观更一致，从而使一些测试偏向同一个结果。多个测试还可能高度相关：看似 256 位，实际上重复问了很多遍相同问题。

第 4.3 节从大量候选中先优先考虑均值接近 0.5 的测试，再贪心检查它与已选测试的绝对相关性；超过阈值就跳过，直到保留 256 个。如果数量不够，再放宽相关阈值。其目标不是让每个比特完全独立，也不是求得一个全局最优组合。

这一步与 PCA 不同：PCA 生成测试响应的线性组合，可能需要计算很多基础测试；这里直接挑选原始比较，保留便宜的运行方式。

最终的几何检验属于应用流程，ORB 本身没有为任意匹配提供几何正确性保证。

二进制编码还改变了索引成本

两串描述的汉明距离为 $d_H(a,b)=\operatorname{popcount}(a\oplus b)$，即异或后数不同位。第 5 节用 multi-probe LSH 搜索大数据库，选部分比特作为桶键。

如果测试高度相关，大量描述会拥挤在少数桶里，查询仍须做许多比较。降低相关性不只影响匹配准确率，也让索引桶更均匀。描述子的统计设计和检索系统因此相互影响。

一个二进制测试的方差，只是信息量的第一道门槛

二进制测试 $b\in\{0,1\}$ 若取1概率为 $p$，方差为 $p(1-p)$。教学比较：$p=0.5$时方差0.25；$p=0.99$时仅0.0099，几乎每块图都输出1，很难区分纹理。即便每位均为0.5，若256位都是同一个比较结果的复制，也只有两种描述子，不能提供256份独立证据。

原文第4节表明“先转正再做BRIEF”会改变测试均值与相关性，因此rBRIEF还要从候选测试中选高方差、低相关组合。方向补偿和统计筛选不是可任意删去的同一件事。原稿第4节

SIFT是描述机制和计算代价上的平行参照；后作DBoW2与ORB-SLAM把ORB特征用于地点检索和几何跟踪。原文人工旋转噪声图像的方向恢复实验只隔离局部组件，不能单独证明实际SLAM回环正确或对大视角变化不变。

方向化测试不再自动保有原BRIEF的比特统计。下面把方差和相关性筛选接进实现，再比较固定长度描述子的速度与匹配信息。

三、构造rBRIEF并匹配，检查有效比特信息

离线选择测试模式：
    从训练图像提取方向化图块
    枚举候选子窗口比较，记录每个图块上的二进制响应
    按响应均值接近 0.5 的程度排序
    贪心加入与已选测试相关性足够低的候选
    直到得到 256 个；必要时调整相关阈值

在线提取：
    建立图像金字塔，每层检测 FAST 候选
    用 Harris 响应排序筛选关键点
    用灰度矩计算每个关键点方向
    按方向选择旋转后的固定测试模式
    执行 256 次比较，打包比特串
匹配：
    用汉明距离进行暴力或索引搜索，得到候选对应
    由任务几何模型验证候选；输出内点与估计结果

一个关于“256 位不等于 256 份信息”的例子

以下为教学构造。假设八个测试全部比较同一条明暗边界，任意图块的结果只能是 00000000 或 11111111。编码长度八位，实际只回答了一个二选一问题。

换成四种相对独立结构各问两遍，响应可能更丰富；再挑出稳定且尽量不重复的八个测试，区分不同图块的能力才可能增加。这里“独立”是教学理想化，rBRIEF 只按有限训练样本的相关性近似筛选。

再看两串 10110000 与 10010100，异或为 00100100，汉明距离为 2。它只表示两次测试不同，不直接对应两像素位移、两度旋转或任何公制几何误差。

四、读速度与匹配实验，固定实现和图像条件

读图：横轴旋转角、纵轴匹配内点比例，比较各描述子在同一旋转试验中的曲线。某些角度的峰谷暴露方向处理的影响；这不能替代不同真实场景上的泛化评估。

实验设置与证据范围

有监督类别识别、描述子模式学习、近邻数据库建立、图像匹配评估是不同环节。大库测试对已有数据库图像做变换，很适合检验检索能力，却不能视为“从未见过的物体类别泛化”。

五组结果怎样读

图 2：质心方向在所测噪声下较稳。 比较角度误差的标准差，支持廉价方向估计可用。不能据此声称低纹理、对称图块或强透视下方向也同样可靠。

读图：蓝色质心法曲线在所测噪声范围内明显低于另两种方向方法；横轴只是这里测试的高斯强度噪声，不包含所有成像变化。

图 3–图 6：消融解释了 rBRIEF 的必要性。 简单旋转 BRIEF 后，均值分布与 PCA 谱暴露方差损失、冗余增加；选择测试后改善，内外点距离分布也更易区分。PCA 图是诊断工具，不是在线描述子的计算步骤。

尚未内嵌：图 6、图 9。方向估计、去相关与匹配性能的定量证据已展示；剩余为学习所得测试对图案和摄影匹配拼图。前者依赖具体训练结果，后者是另一个视觉例证；当前不继续扩展到近完整的学习图案与示例影像集，也不以随机模式冒充学得结果。

读图：简单旋转后的红柱分布扩展，说明测试位的均值性质发生变化；该分布是选择低偏置测试对的依据之一。

读图：前三组谱的下降形态用于诊断测试位之间的相关性；PCA在这里是分析手段，不是在线计算描述子的步骤。

读图：实线和虚线分别对应匹配与非匹配距离，分布分离程度决定阈值辨识的难易；不能只凭曲线峰值判断所有场景的匹配率。

图 7–9：没有每个场景都第一。 高斯噪声 10 的人工旋转试验中，ORB 内点比例超过 70%；真实 Magazines 比较中 ORB 为 36.180%，SURF 为 38.305%，SIFT 为 34.010%。Boat 中 ORB 45.8%、SURF 28.6%、SIFT 30.2%。以 Boat 对 SIFT 为例，绝对差 15.6 个百分点，相对提升约 51.7%，两者不能混写。

读图：不同噪声水平形成多条曲线，各方法相对表现随角度和噪声变化；这组人工旋转试验不能代替真实透视变化评测。

图6的测试对分布和图9的实景匹配拼图暂未转载，以控制同源图像的累计摘引范围；对应原文链接保留。

图 10、11：速度与检索准确率是联合曲线。 rBRIEF 的桶更均匀，LSH 查询在相应设置下有优势。但 SIFT 库约 160 万条、rBRIEF 约 180 万条，索引结构和参数也不同；图说明系统组合的权衡，而不是隔离所有其他变量后唯一归因于描述子。

读图：横轴为桶大小、纵轴为桶数量，三种描述子的分布不同；该差异与候选检索负担有关，但还受索引设置影响。

读图：每点对应一组系统设置，横轴成功比例与纵轴对数时间共同构成权衡；比较时仍需注意数据库规模和参数并不完全相同。

第 6 节：大幅加速必须带实现与工作负载。 24 张 640×480 图像上的平均每帧时间为 ORB 15.3 ms、SURF 217.3 ms、SIFT 5228.7 ms，约为 14.2 倍和 341.7 倍速度比。它们是当时实现的特征检测与描述计时，不是现代任意实现或整个 SLAM 的恒定倍数。物体应用检出约 61%，要求匹配后还能估计位姿；不能改称所有类别分类准确率。

手机部分正文约报 7 Hz，分项均值 66.6、72.8、20.9 ms 相加为 160.3 ms，直接倒数约 6.24 Hz。它们不构成精确一致的逐帧预算，适合保留为近似报告而非自行调数字使其吻合。单应拟合的平面跟踪也不是完整三维建图。

五、限制方向不稳、尺度处理和强视角变化

方向补偿主要处理平面旋转，金字塔处理部分尺度变化。第 7 节承认尺度不变性尚未充分研究。大视角变化、光照的空间非均匀变化、遮挡和运动模糊都可能超出局部比较的稳定范围。

离线低相关只在训练分布上成立，不表示真实世界所有纹理都独立。二进制编码压缩了信息，低纹理或重复纹理仍难区分；快匹配也会很快地产生大量错误候选，所以几何验证不能省略。

对机器人系统而言，特征提取只是部分时间。若后端优化、回环检索或数据传输成为瓶颈，ORB 的局部加速不会按同一倍数传递到整体。与后来 ORB-SLAM 的关系是提供重要视觉组件，而不是已经实现后者的关键帧管理与地图优化。

六、追问：256位描述子有很多重复测试时，增加长度为什么未必增加区分力？

256位描述子有很多重复测试时，增加长度为什么未必增加区分力？

参考答案：重复或高度相关的比特会反复表达相近信息，几乎恒定的比特也难区分窗口。正文因此在方向补偿后检查方差与相关性。应固定长度比较测试集合的统计与匹配表现，而不能把位数直接当独立信息量。

教学参照：ORB (Oriented FAST and Rotated BRIEF)。这里借用其分开方向补偿与描述统计的讲法。

七、把二进制特征交给检索与SLAM

• 模块组合：DBoW：怎样从相似图片中找出真正的重访地点。将二进制局部特征量化成视觉词并检索地点。
• 模块组合：ORB-SLAM：从持续跟踪走向能够重访和恢复的单目地图。把特征用于跟踪、建图与回环，位姿仍需几何优化。

八、自测与参考答案

1．一个比特在所有图像里都稳定为 1，为什么反而不好？

答： 它对噪声可能稳定，却不区分不同图块。匹配既需要同一物体跨视图保持一致，也需要不同物体产生差别。均值接近 0.5 提供较高方差，但还要避免与其他比特重复，因此只看稳定性或只看方差都不够。

2．为什么不能直接对 BRIEF 做 PCA，得到 256 维就结束？

答： PCA 的新维度通常是很多原始测试的线性组合，运行时仍需计算这些测试再做组合，会破坏二进制比较的简单性。rBRIEF 直接选择 256 个原测试，牺牲全局最优去相关的可能性，换取运行时的低成本。

3．ORB 匹配距离很小，为什么还要单应或位姿验证？

答： 重复纹理、量化和视角变化都可能让错误对应获得小汉明距离。几何验证检查多个对应能否共同解释同一空间变换，这是单个局部外观距离没有表达的信息。描述子距离不是几何误差，更不能单凭它确认回环或控制机器人。