Question

目标

在这一章中我们将学习 BRIEF 算法的基础知识

理论基础

SIFT^2算法使用 128 维的向量描述符。由于它使用的是浮点数，因此它至少需要 512 字节。相似地，SURF^3 算法也至少需要 256 字节（64 维）。创建这样一个数以千计的特征向量需要大量的内存，这对于一个资源有限的应用，尤其是嵌入式系统上的应用来说是不可接受的。而且所消耗的内存空间越多，匹配花费的时间也越长。

但是实际匹配可能不需要所有这些维度。我们可以使用几个像 PCA^5，LDA^6这样的方法压缩它。甚至还有一些方法像是使用LSH^4进行哈希的方法来将浮点数表示的这些SIFT描述符转换为二进制向量。这些二进制向量可以用 Hamming 距离^7来进行特征匹配。这进一步提升了速度，因为计算 Hamming 距离只是执行异或指令和进行位计数，在有SSE指令集的现代计算机上这是相当快的。但是如果要使用这种方法，我们需要先找到描述符，然后才能使用哈希算法，这代表这种方法并不能解决我们最初的内存问题。

此时 BRIEF 算法就可以发挥作用了。它可以不寻找描述符而直接得到二进制向量。 它接受平滑过的图像集并以一种独特的方式（在论文中有解释）选择几组$n_d$$(x,y)$坐标。 然后进行像素强度比较。 例如，假设第一个位置对是 $p$ 和 $q$。 如果 $I(p)<I(q)$，那么结果是1，否则是 0。对所有的 $n_d$ 坐标进行这样的比较之后，我们就可以得到一个$n_d$维的二进制向量。

这里的 $n_d$ 可以是 128、256 或 512。OpenCV 支持所有这些值，但默认情况下 $n_d$ 是 256（OpenCV 使用字节来计算 $n_d$ 的大小，所以这些值在 OpenCV 中就是 16、32 和 64）。只要你得到了这个结果，你就能使用 Hamming 距离来匹配这些描述符。

重要的一点是 BRIEF 是一个特征描述符，它没有提供任何方法来查找特征。 因此，你需要使用其他特征检测器，如 SIFT，SURF 等。论文推荐使用 CenSurE，这是一种快速特征检测器，而且使用它检测得到的特征点来执行 BRIEF 算法相对于使用SURF检测到的点来说效果会稍好一些。

简而言之，BRIEF 是一种更快的进行特征描述符计算和匹配的方法。 除非有很剧烈的平面内旋转，否则它的识别率也很高。

OpenCV 中的 BRIEF

下面的代码展示了如何使用 CenSurE 检测器获取的特征点来计算BRIEF描述符，在 OpenCV 中 CenSurE 检测器被称作 STAR 检测器。

注意，你需要 OpenCV contrib 来使用这些代码。

import numpy as np
import cv2
from matplotlib import pyplot as plt
img = cv2.imread('simple.jpg',0)
# 初始化Star检测器
star = cv2.xfeatures2d.StarDetector_create()
# 初始化BRIEF提取器
brief = cv2.xfeatures2d.BriefDescriptorExtractor_create()
# 用STAR找到关键点
kp = star.detect(img,None)
# 计算出BRIEF描述符
kp, des = brief.compute(img, kp)
print( brief.descriptorSize() )
print( des.shape )

brief.getDescriptorSize() 获取 $n_d$ 的大小（以字节为单位）。默认值是 32。接下来要做的事就是匹配，我们将会在另外一章中介绍它。