OpenCV ORB 描述符——它究竟是如何存储在一组字节中的？

Question

我目前正在使用 OpenCV 的 ORB 特征提取器，我确实注意到 ORB 描述符的存储方式很奇怪(至少对我来说是这样)(它基本上是一个 BRIEF-32，带有与我的问题无关的修改) .正如你们中的一些人所知，ORB 使用修改后的 FAST-9(圆半径 = 9 像素；还存储关键点的方向)提取关键点，并使用修改后的 BRIEF-32 描述符来存储关键点代表的特征。

BRIEF(ORB 版本)的工作原理如下:我们获取一个 31x31 像素的补丁(代表一个特征)并创建一堆随机的 5x5 像素测试点。然后我们将这些点成对并评估它们的强度，根据该对中第一个点的强度是否大于或小于第二个点的强度，得出二元决策(0 或 1)。然后我们获取所有这些位并使用基本求和公式构建长度为 n 的二进制字符串(对于 BRIEF-32，我们有 32 字节 * 8 = 256 位长二进制字符串):

SUM(2^(i-1)*bit_pair_test)

其中 bit_pair_test 是我们从一对测试点的测试中计算出的位值。最终结果类似于(对于一组二进制测试 (...,0,1,0,1,1)):

(2⁰*1) + (2¹*1) + (2²*0) + (2 ³*1) + (2⁴*0) + ...

现在 OpenCV 的 ORB 存储这些位串的方式对我来说是个谜。如果我们查看包含整个图像的描述符的矩阵，其中每一行都是单个关键点的单个描述符，我们可以看到每个描述符都有 32 个 8 位数字，这总共导致了 BRIEF-32 使用的 256 位来存储信息。 我不明白为什么我们将这 256 位分成 32 个字节。官方文档 ( http://docs.opencv.org/trunk/doc/py_tutorials/py_feature2d/py_brief/py_brief.html ) 仅说明 OpenCV 以字节为单位存储此类描述符，但并未解释其原因。我考虑了三种可能性，但不排除这些可能性的某种组合可能是答案的可能性:

• 一些我看不到的存储技术
• 为这么长的二进制字符串(在我们的例子中是 256 位)计算汉明距离时出现一些性能问题
• 匹配过程的优化 - 匹配基本上是将一幅图像中关键点的描述符与另一幅图像中关键点的描述符进行比较。因为我们有二进制字符串，汉明距离是这里显而易见的选择。可能是以某种方式将这 32 个子字符串中的每一个与第二个图像中另一个关键点的描述符中的对应部分进行比较(位置 0 处的子字符串(关键点 X，图像 1)和位置 0 处的子字符串(关键点 Y，图像 2)。最后，OpenCV 可能会说:“好的，我们有 80% 的描述符匹配率，因为所有子字符串中大约有 26 个在两个描述符中是相同的)所以我们有一个赢家。”但是我找不到任何证据来证实这一点。

PS:你可以阅读ORB上的论文here和关于 BRIEF 的论文 here .

Answer 1

选择 8 位和 32 位模式是由于存储和效率问题。

• 匹配过程

BRIEF、ORB 和 BRISK 中的位顺序不相关(与 FREAK 不同)。因此，这些描述符的所有比特都是同等重要的，不能只比较比特流的第一部分等。

另一方面，FREAK 在设计时考虑了这样一个匹配过程(在 FREAK 的论文中称为级联)。

• 存储问题

好吧，计算机不会存储单独的位。因此，您不会看到任何人在位数组中存储 BRIEF 等。

可以从内存中读取的最小组件是一个字节(通常对应于 8 位，虽然有些 DSP 无法读取小于 16 位的 block ，但那是另一回事)。因此，您可能看到人们将他们的描述符存储在字节数组中(在 C/C++ 中键入 unsigned char，这是底层 OpenCV 实现语言) .

此外，当变量在 CPU 字边界上对齐时，内存访问通常会更好(更快)。现在大多数 CPU 都有 32 位或 64 位字，32 位字是更好的选择，因为 64 位架构在设计时考虑到了传统的 32 位处理器。

• 效率问题

汉明距离是通过异或运算计算的。碰巧许多处理器都有专用的指令集，可以用 32 位字(64 位 CPU 变得更普遍之前整数的常见大小)有效地计算 XOR。更重要的是，它们还可以支持在多个 32 位字上并行计算多个 XOR 值，这是一种称为 SIMD(单输入多数据)的并行技术。例如，可以利用 SSE 扩展来进一步加速 BRIEF/ORB/... 大小为 32 位倍数的描述符的汉明距离计算。