虽然出现了越来越多快速的检测器/描述符组合，但是基于定向直方图(HOG)描述符之一的尺度不变特征转换(SIFT)依然被广泛运用。HOG的基本思想是通过物体在局部邻域中的强度梯度分布来描述物体的结构。为此，将图像划分为多个单元，在这些单元中计算梯度并将其收集到直方图中。然后，将所有单元格的直方图集用作相似性度量，以唯一地标识图像块或对象。SIFT/SURF使用HOG作为描述符，既包括关键点检测器，也包括描述符，功能很强大，但是被专利保护。SURF是在SIFT的基础上改进，不仅提高了计算速度，而且更加安全鲁棒性，两者的实现原理很相似。在此我先仅介绍SIFT。SIFT方法遵循五步过程，下面将对此进行简要概述。首先，使用称为“拉普拉斯高斯（LoG）”的方法来检测图像中的关键点，该方法基于二阶强度导数。LoG应用于图像的各种比例级别，并且倾向于检测斑点而不是拐角。除了使用唯一的比例级别外，还根据关键点周围局部邻域中的强度梯度为关键点分配方向。其次，对于每个关键点，其周围区域都会通过消除方向而改变，从而确保规范的方向。此外，该区域的大小将调整为16 x 16像素，从而提供了标准化的图像补丁。第三，基于强度梯度_Ix_和_Iy_计算归一化图像补丁内每个像素的方向和大小。第四，将归一化的贴片划分为4 x 4单元的网格。在每个单元内，超出幅度阈值的像素的方向收集在由8个bin组成的直方图中。最后，将所有16个单元格的8柱状直方图连接到一个128维向量（描述符）中，该向量用于唯一表示关键点。SIFT检测器/描述符即使在杂波中和部分遮挡下也能够可靠地识别物体。尺度，旋转，亮度和对比度的均匀变化是不变的，仿射失真甚至是不变的。 SIFT的缺点是速度低，这使其无法在智能手机等实时应用中使用。HOG系列的其他成员（例如SURF和GLOH）已针对速度进行了优化。但是，它们仍然在计算上过于昂贵，因此不应在实时应用中使用。此外，SIFT和SURF拥有大量专利，因此不能在商业环境中自由使用。为了在OpenCV中使用SIFT，必须使用#include <opencv2/xfeatures2d/nonfree.hpp>，并且需要安装OPENCV_contribute包，注意一定要在Cmake选项中开启 OPENCV_ENABLE_NONFREE。二进制Binary描述符基于HOG的描述符的问题在于它们基于计算强度梯度，这是非常昂贵的操作。即使已进行了一些改进（例如SURF），使用了积分图像，速度提高了，但这些方法仍然不适合处理能力有限的设备（例如智能手机）上的实时应用程序。二进制描述符家族是基于HOG的方法的一种更快（免费）的替代方案，但准确性和性能稍差。二进制描述符的核心思想是仅仅依赖强度信息(即图像本身) ，并将关键点周围的信息编码为一串二进制数字，当搜索相应关键点时，这些数字可以在匹配步骤中非常有效地进行比较。也就是说二进制描述符将兴趣点的信息编码成一系列数字，并作为一种数字“指纹” ，可用于区分一个特征和另一个特征。目前，最流行的二进制描述符是 BRIEF、 BRISK、 ORB、 FREAK 和 KAZE (所有这些都可以在 OpenCV 库中找到)。二进制描述符从高层次的角度来看，二进制描述符由三个主要部分组成： 1、一种描述样本点位于关键点附近的位置的采样模式( sampling pattern )。2、一种消除了图像补丁围绕关键点位置旋转影响的方向补偿方法( orientation compensation)。3、一种样本对选择的方法(ample-pair selection)，它产生成对的样本点，这些样本点根据它们的强度值相互比较。如果第一个值大于第二个值，我们就在二进制字符串中写一个“1” ，否则就写一个“0”。在对采样模式中的所有点对执行此操作之后，将创建一个长的二进制链(或“ string”)(因此得到描述符类的族名)。BRISK“二进制鲁棒不变可伸缩关键点”关键点检测器 / 描述符是二进制描述符的代表。在此我先仅介绍BRISIK。2011年Stefan Leutenegger 提出的BRISK 是一个基于 FAST 的检测器和一个Binary描述符的组合，这个描述符由通过对每个关键点邻域进行专门采样而获得的强度比较创建。BRISK的采样模式由多个采样点（蓝色）组成，其中每个采样点周围的同心环（红色）表示应用高斯平滑的区域。与某些其他二进制描述符（例如ORB或Brief）相反，BRISK采样模式是固定的。平滑对于避免混叠非常重要（这种效应会导致不同信号在采样时变得难以区分-或彼此混叠）。在样本对选择期间，BRISK算法会区分长距离对和短距离对。长距离对（即在样本图案上彼此之间具有最小距离的样本点）用于根据强度梯度估算图像补丁的方向，而短距离对用于对已组装的描述符字符串进行强度比较。在数学上，这些对表示如下：首先，我们定义所有可能的采样点对的集合A。然后，我们从A提取子集L，子集L的欧氏距离大于上阈值。L是用于方向估计的长距离对。最后，我们从A提取欧氏距离低于下阈值的那些对。该集合S包含用于组装二进制描述符串的短距离对。下图显示了短对（左）和长对（右）的采样模式上的两种距离对。从长对中，关键点方向向量G 计算如下：首先，根据归一化的单位矢量计算两个采样点之间的梯度强度，归一化的单位矢量给出两个点之间的方向，乘以两个点在各自比例下的强度差。然后在(2)中，关键点方向向量 g 从所有梯度强度的总和中计算出。基于 g ，我们可以使用采样模式的方向重新排列短距离配对，从而确保旋转不变性。基于旋转不变的短距离配对，可以如下构建最终的二进制描述符：从 g 计算出关键点的方位后，我们使用它使短距离配对旋转不变。然后，所有对之间的强度 S 被比较并用于组装可用于匹配的二进制描述符。
OPENCV Detector/Descriptor implementation
目前存在各种各样的特征点检测器/描述符，如 HARRIS, SHI-TOMASI, FAST, BRISK, ORB, AKAZE, SIFT, FREAK, BRIEF。每一种都值得单独用一篇博客去描述，但是本文的目的是为了给大家一份综述，因此不详细的从原理上分析这些检测器/描述符。网上有大量描述这些检测器/描述符的文章，但是我还是建议大家先看OPENCV库的Tutorial: How to Detect and Track Object With OpenCV.以下我会介绍各个特征点检测器/描述符的代码实现以及参数详解, 文章结尾会基于实际结果对这些组合进行评价。有些OPENCV函数可以同时用于检测器/描述符，但是有的组合会出现问题。SIFT Detector/Descriptor SIFT detector and ORB descriptor do not work together
HARRIS Detector
SHI-TOMASI Detector
BRISIK Detector/Descriptor
FREAK Detector/Descriptor
FAST Detector/Descriptor
ORB Detector/Descriptor SIFT detector and ORB descriptor do not work together
AKAZE Detector/Descriptor KAZE/AKAZE descriptors will only work with KAZE/AKAZE detectors.
BINARY descriptors :BRISK, BRIEF, ORB, FREAK, and AKAZE- Hamming distance
HOG descriptors : SIFT (and SURF and GLOH, all patented)- L2-norm
寻找匹配对
让我们假设在一个图像中有N个关键点及其关联的描述符，在另一幅图像中有M个关键点。
蛮力匹配(Brute Force Matching)
寻找对应对的最明显方法是将所有特征相互比较，即执行N x M比较。对于第一张图像中给定的关键点，它将获取第二张图像中的每个关键点并计算距离。距离最小的关键点将被视为一对。这种方法称为“蛮力匹配(Brute Force Matching)”或“最近邻居匹配(Nearest Neighbor Matching)”。OPENCV中蛮力匹配的输出是一个关键点对的列表，这些关键点对按其在所选距离函数下的描述符的距离进行排序。
快速最近邻(FLANN)
2014年，David Lowe和Marius Muja发布了"快速最近邻(fast library for approximate nearest neighbors(FLANN)")。FLANN训练了一种索引结构，用于遍历使用机器学习概念创建的潜在匹配候选对象。该库构建了非常有效的数据结构（KD树）来搜索匹配对，并避免了穷举法的穷举搜索。因此，速度更快，结果也非常好，但是仍然需要调试匹配参数。BFMatching和FLANN都接受描述符距离阈值T，该距离阈值T用于将匹配项的数量限制为“好”，并在匹配不对应的情况下丢弃匹配项。相应的“好”对称为“正阳性（TP）”，而错对称为“假阳性（FP）”。为T选择合适的值的任务是允许尽可能多的TP匹配，而应尽可能避免FP匹配。根据图像内容和相应的检测器/描述符组合，必须找到TP和FP之间的权衡点，以合理地平衡TP和FP之间的比率。下图显示了SSD上TP和FP的两种分布，以说明阈值选择。第一阈值T1被设置为两个特征之间的最大允许的SSD，其方式是选择了一些正确的正匹配，而几乎完全避免了错误的正匹配。但是，使用此设置也将丢弃大多数TP匹配项。通过将匹配阈值增加到T2，可以选择更多的TP匹配，但是FP匹配的数量也将显着增加。在实践中，几乎没有找到TP和FP的清晰明了的分离，因此，设置匹配阈值始终是平衡“好”与“坏”匹配之间的折衷。尽管在大多数情况下都无法避免FP，但目标始终是尽可能降低FP次数。在下文中，提出了实现这一目标的两种策略。
Nearest neighbor distance ratio (NN)/K-nearest-neighbor(KNN)
减少误报数量的另一种非常有效的方法是为每个关键点计算最近邻距离比(nearest neighbor distance ratio)。KNN与NN的区别在与 NN 每个特征点只保留一个最好的匹配 (keeping only the best match)，而KNN 每个特征点保留k个最佳匹配(keeping the best k matches per keypoint). k一般为2.主要思想是不要将阈值直接应用于SSD。相反，对于源图像中的每个关键点，两个(k=2)最佳匹配位于参考图像中，并计算描述符距离之间的比率。然后，将阈值应用于比率，以筛选出模糊匹配。下图说明了原理。在该示例中，将具有关联描述符da的图像补丁与其他两个具有描述符的图像补丁d_ b1 和 d_b2进行比较 。可以看出，图像补丁看起来非常相似，并且会导致模棱两可，因此不可靠。通过计算最佳匹配与次佳匹配之间的SSD比值，可以过滤掉这些较弱的候选对象。在实践中，已证明阈值0.8可以在TP和FP之间提供良好的平衡。在原始SIFT中检查的图像序列中，使用此设置可以消除90％的错误匹配，而丢失少于5％的正确匹配。注意，只有KNN能设置阈值0.8。NN只会提供一个最佳匹配。以下是匹配的执行代码：
内容反馈