19

我目前正在使用 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 0 *1) + (2 1 *1) + (2 2 *0) + (2 3 *1) + (2 4 *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的论文和关于这里的 Brief的论文。

4

1 回答 1

19

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

  • 匹配过程

Brief、ORB 和 BRISK 中的位顺序不相关（与 FREAK 不同）。因此，这些描述符的所有位都具有相同的重要性，您不能只比较位流的第一部分等。

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

  • 存储问题

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

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

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

  • 效率问题

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

于 2014-05-15T11:46:59.113 回答