OpenCV-12-关键点和描述子B

4.3.10 FREAK算法

和BRIEF算法一样，FREAK算法只实现了描述符提取部分，不包含关键点检测器。该算法是作为BRIEF、BRISK和ORB算法的改进版本被提出的，另外FREAK描述符是一个受生物启发的描述符。它的计算方式和BRIEF描述符类似，主要的区别是它计算了用于二值比较的面积。第二个细微的区别是FREAK算法并不使用均匀平滑图像周围的像素进行比较，相反用于比较的像素点分别都对应了不同大小的积分区域，离描述符中心越远的点对应的积分区域越大。FREAK算法通过这种方式模拟人的视觉系统特征，也因此得名Fast Retinal Keypoint。

FREAK算法计算关键点描述符的原理示意图如下，其中直线连接的是可能的测试定点对，圆圈表示的是每个顶点关联的接受域(Receptive Field)，接受域的面积随着其关联顶点距离中心距离的增大而增大。

为了理解FREAK描述符的计算过程，回忆一下前文讲到的BRIEF描述符，但是这次重一个稍微不同的角度。BRIEF从关键点附近选择了大量的像素对进行比较，并且为了提高对噪声的抗性，首先会对原图应用高斯模糊滤镜。在FREAK算法中，用于比较的像素其强度值都可以看作是在原图中该点附近像素强度的高斯加权和，这两种方式在数学上是完全等价的。但是在上图中的这种方式引入了待比较像素的接受域概念，并且考虑了视网膜上神经细胞和使其发生响应的感光器集合之间的关系。在标准的结构中，BRIEF算法包含43个接收域。

和ORB描述符一样，FREAK的作者使用了一种学习技术组织这些接受域中可能的测试对，并按照效果递减排序。通过这种方式具有更高辨识度的测试对(通过较大特征训练集得出)相对于更低辨识度的测试对具有更高的优先级。一旦这个顺序被确定，只有当测试对相比于具有更高独立实用性的竞争者具有更强的去相关性(Decorrelation)时才会被保留。在应用中，对于几十个不同大小的接受域和几千个可能的测试对，只有最有用的512个测试对才有保留的价值。

FERAK算法将这512个测试对分为4个集合，每个集合包含128个测试对。根据经验可以观察到每个集合连续包含了更多的里中心更近的面积相对较小的接受域，但是最主要的具有辨识度的测试对都是两个较大面积接受域对应样本之间的比较。因此可以先只处理这些覆盖更大面积接受域的主要测试对，如果足够相似，则继续处理其他的测试对从而优化匹配。每组128个测试对的结果只需要一次异或(XOR)操作(和位求和)即可完成比较，即通过一个16字节的值。这个值很重要，因为很多现代的处理器都可以在一个周期内完成这样的比较，因此FREAK描述符在比较时是十分高效的。

4.3.11 稠密网格法

稠密网格法实际上不是一个关键点检测器，而是一个通过网格化图像生成关键点的算法。同样的该算法不包含描述符计算部分，当你得到生成的关键点后需要使用其他算法计算描述符。一个稠密网格算法生成的关键点示意图如下，为了方便演示相关的参数中网格密度数量设置为3，第一层网格中关键点大小设置为50，不同层网格间关键点大小缩放系数为2。

稠密网格法相关类定义如下，如前文所讲该算法不包含描述符计算部分，因此该类未实现相关接口。

class cv::DenseFeatureDetector : public cv::FeatureDetector {

public:
// 构造函数
// initFeatureScale：初始层网格中关键点的大小
// featureScaleLevels：网格的层数
// featureScaleMul：不同网格层之间关键点的大小缩放系数
//     第一层后的每一层网格中关键点的大小都等于该属性和前一层关键点大小的乘积
// initXyStep：关键点之间的间距
// initImgBound：免于计算关键点的图像边缘框距离
// varyXyStepWithScale：在不同层之间是否根据关键点的大小缩放initXyStep作为关键点之间的间距
// varyImgBoundWithScale：在不同层之间是否根据关键点的大小缩放initImgBound作为免于计算关键点的图像边缘框距离
explicit DenseFeatureDetector(float initFeatureScale = 1.f, int featureScaleLevels = 1,
                              float featureScaleMul = 0.1f, int initXyStep = 6, int initImgBound = 0,
                              bool varyXyStepWithScale = true, bool varyImgBoundWithScale = false);

cv::AlgorithmInfo* info() const;
...
};

算法内部生成特征点的简单示意图如下，算法会为原图构建间距不等的多层网格，其中网格的层数通过参数featureScaleLevels控制。网格的间距为对应层的关键点大小和间距，其中首层的关键点大小通过参数initFeatureScale控制，其默认值为1，通常情况下并不是我们想要的，但是需要注意该值的设置不仅和图像自身的属性相关，还与你想要使用的描述符生成算法相关。首层关键点之间的间距由参数initXyStep控制。参数featureScaleMul控制了关键点大小和其上一层关键点大小的比例，而参数varyXyStepWithScale控制关键点之间的间距是否也需要在不同网格层间随着关键点大小改变而改变。

参数initImgBound和varyImgBoundWithScale用于确定免于计算关键点的图像边缘框距离，在大多是情况下将它设置参数initFeatureScale的值，确保关键点不会覆盖到图像的边界之外。

4.4 关键点过滤

很多时候你都需要精简关键点列表，这样做的原因可能很多，例如关键点太多，或者是想要删除低质量的关键点，或者是想要移除重复的关键点，又或者是需要移除位于指定区域外的所有关键点。OpenCV提供一个关键点过滤器类和一系列类方法来完成这些任务。在前文讲到的很多关键点检测器内部都隐式调用了相关函数，但是有时可能你也需要直接使用它们。该类的部分定义如下。

class cv::KeyPointsFilter {
public:
// 移除图像边缘框内的所有关键点
// keypoints：待处理的关键点
// imageSize：原始图片的大小
// borderSize：图像边框的距离
static void runByImageBorder(
vector<cv::KeyPoint>& keypoints, cv::Size imageSize, int borderSize);

// 移除大小不符合规则的关键点
// minSize：需要保留的关键点最小尺寸
// maxSize：需要保留的关键点最大尺寸
static void runByKeypointSize(vector<cv::KeyPoint>& keypoints, float minSize, float maxSize = FLT_MAX);

// 根据蒙版过滤关键点
// mask：过滤蒙版，非0值对应的关键点才会被保留，矩阵应和原图大小相同
static void runByPixelsMask(vector<cv::KeyPoint>& keypoints, const cv::Mat& mask);

// 移除重复的关键点
static void removeDuplicated(vector<cv::KeyPoint>& keypoints);

// 保留指定数量的更高质量关键点，根据cv::KeyPoint的属性Response排序
// npoints：需要保留的关键点数量
static void retainBest(vector<cv::KeyPoint>& keypoints, int npoints);
}

4.5 关键点匹配

关键点匹配的方法有两个，第一个是暴力匹配(Brute Force Matching)，这种方法比较了两个集合中所有可能的组合。第二种方法被称为FLANN，实际上是一系列定位距离最近关键点的接口集合。

4.5.1 暴力匹配

暴力匹配相关类的部分定义如下。

class cv::BFMatcher : public cv::DescriptorMatcher {

public:
BFMatcher(int normType, bool crossCheck=false);

virtual ~BFMatcher() {}

// 是否支持蒙版矩阵，总返回true
// 蒙版矩阵不是应用于原图像，而是用于确定某些描述符之间是否需要比较
virtual bool isMaskSupported() const { return true; }
virtual Ptr<DescriptorMatcher> clone(bool emptyTrainData=false) const;
...
};

暴力匹配取出查询集中的每个描述符和匹配器本身持有的描述符集合字典，或者是通过参数提供的训练描述符集合中的每个元素进行比较。这种方式你只需要关注匹配时度量距离的标准，在构造本类实例的时候通过参数normType指定，其可取值以及对应的公式如下。

暴力匹配的另一个特性是可以开启交叉检查(Cross-Checking)，通过构建实例时的参数crossCheck控制。当交叉匹配开启后，只有当查询集中第i个元素query[i]在训练集中的最邻近元素为train[j]，同时训练集中第j个元素train[j]在查询集中的最邻近元素是query[i]时，才判定query[i]和train[j]匹配。这对于提高匹配的正确性很有用，但是会消耗额外的计算成本。

4.5.2 快速近似最近相邻项法

OpenCV使用类cv::FlannBasedMatcher实现FLANN(Fast Library for Approximate Nearest Neighbor)的功能，该类实现了多种在更高维度寻找最近相邻项的算法，其定义如下。

class cv::FlannBasedMatcher : public cv::DescriptorMatcher {

public:
// 构造函数
// indexParams：算法内部索引构建策略，下文介绍
// searchParams：类似于终止条件等搜索行为控制参数，下文介绍
FlannBasedMatcher(const cv::Ptr<cv::flann::IndexParams>& indexParams
    = new cv::flann::KDTreeIndexParams(),
    const cv::Ptr<cv::flann::SearchParams>& searchParams = new cv::flann::SearchParams());

virtual void add(const vector<Mat>& descriptors);
virtual void clear();
virtual void train();
virtual bool isMaskSupported() const;

virtual void read(const FileNode&);
virtual void write(FileStorage&) const;

virtual cv::Ptr<DescriptorMatcher> clone(bool emptyTrainData = false) const;
...
}

线性索引构建策略

当参数indexParams指定为cv::FlannBasedMatcher的实例时，表示使用线性索引构建策略，使用该策略时算法内部的实现和暴力匹配法基本相同。它用于基准比较(Benchmark Comparisons)通常很有用，当然也可以用来验证其他算法得到的结果是否是令人满意的。该类的构造函数不包含任何参数，下面的示例代码构建了这样一个使用线性索引构建策略的FLANN匹配器。

// 这里只是示例代码，因此并未考虑内存管理问题
cv::FlannBasedMatcher matcher(new cv::flann::LinearIndexParams(), new cv::flann::SearchParams());

KD树索引构建策略

当参数indexParams指定为结构体cv::flann::KDTreeIndexParams的实例时，表示使用随机KD树匹配描述符。算法内部会构建很多歌随机数并关联描述符的索引，算法在每个树上向下查询到最近相邻项时，候选项不仅会与自生的树上迄今为止已经发现的最近相邻项比较，还会与其他树上的候选项进行比较。该结构题的定义如下。

struct cv::flann::KDTreeIndexParams : public cv::flann::IndexParams {
// 构造方法
// trees：构建的KD树数量，通常设置为16或者更大的值
KDTreeIndexParams(int trees = 4);
};

使用该策略的FLANN匹配器构建示例代码如下。

// 这里只是示例代码，因此并未考虑内存管理问题
cv::FlannBasedMatcher matcher(new cv::flann::KDTreeIndexParams(16), new cv::flann::SearchParams());

分层k均值索引构建策略

另外一种构建索引的策略是分层K均值聚类法(Hierarchical k-means Clustering)，它的优势是能够智能应用数据集中点的密度，该算法在后文机器学习章节还会详细介绍。该算法是一个递归方法，首先数据会被分为很多个聚类，然后每个聚类再分为多个子聚类，然后递归该过程。这种数据结构对高效匹配很有帮助，其相关类定义如下。

struct cv::flann::KMeansIndexParams : public cv::flann::IndexParams {
// 构造函数
// branching：分支因子，即树每一层的聚类数量
// iterations：聚类构建时需要的迭代次数
//     如果设置为-1，则强制聚类算法一直迭代直至收敛
// centers_init：集群中心初始化策略，下文介绍
// cb_index：控制树的搜索逻辑，下文介绍
KMeansIndexParams(int branching = 32, int iterations = 11,
                  cv::flann::flann_centers_init_t centers_init = cv::flann::CENTERS_RANDOM,
                  float cb_index = 0.2);
};

在大多数情况下使用构造函数默认的参数就能够得到很好的效果。其中参数centers_init控制了集群中心初始化的策略，传统上通常使用值cv::flann::CENTERS_RANDOM，但是近年来实践证明在大多数场景下谨慎选择该值能够得到显著更好的结果。该参数的另外两个取值分别时cv::flann::CENTERS_GONXSLES和cv::flann::CENTERS_KMEANSPP，后者逐渐成为了标准选项。参数cb_index是为那些真正的FLANN专家所预留的，算法内部搜索树时会使用到该参数，它可以控制树被搜索到方式。通常情况下最好将其设置为默认值或者0，设置为0时表示当搜索完一个域时，应该直接继续搜索最近的未搜索过的域。

KD树和K均值法联合索引构建策略

该方法简单的结合了KD树和k均值策略，从而尝试找到它们其中某种方法能够实现的最佳匹配。因为这两个方法匹配近似项方法，因此寻找到另外一种方法总有潜在的收益。你可以将这种方法看作是KD树法具有多个随机数的一种逻辑扩展。相关结构体的定义如下。

struct cv::flann::CompositeIndexParams : public cv::flann::IndexParams {
// 构造函数
// trees：构建的KD树数量，通常设置为16或者更大的值
// branching：分支因子，即树每一层的聚类数量
// iterations：聚类构建时需要的迭代次数
//     如果设置为-1，则强制聚类算法一直迭代直至收敛
// cb_index：控制树的搜索逻辑
// centers_init：集群中心初始化策略
CompositeIndexParams(int trees = 4, int branching = 32,
                     int iterations = 11, float cb_index = 0.2,
                     cv::flann::flann_centers_init_t centers_init = cv::flann::CENTERS_RANDOM);
};

局部敏感哈希索引构建策略

另外一种区别很大的索引构建方式是局部敏感哈希(Locality-Sensitive Hash, LSH)索引构建策略，它使用哈希函数将类似的对象映射到同一个桶中。这些哈希函数能够很快生成候选对象列表，并对其进行评估和比较。OpenCV中实现的LSH变体最早由Lv等人提出，在OpenCV中相关结构体的定义如下。

struct cv::flann::LshIndexParams : public cv::flann::IndexParams {
// 构造函数
// table_number：哈希表数量
// key_size：哈希键的位数，取值空间通常为[10, 20]
// multi_probe_level：控制如何搜索相邻存储区
//     建议使用默认值2，如果设置为0，算法会退化成为非多重探测LSH算法
LshIndexParams(unsigned int table_number, unsigned int key_size,
               unsigned int multi_probe_level);
};

需要注意FLANN中的LSH索引构建策略仅适用于二进制类型秒速符，处理其他类型描述符时不应该使用该策略。

自动索引构建策略

自动索引构建策略是让FLANN算法自动寻找最佳的索引策略，显然这需要一定的时间成本。使用该策略时，可以设置目标精度，即返回的最近相邻项中正确的结果所占百分比。当然所需的精度越高，寻找到合适的索引构建策略就会越困难，生成所有的索引消耗的时间就会更长。相关结构体的定义如下。

struct cv::flann::AutotunedIndexParams : public cv::flann::IndexParams {
// 构造函数
// target_precision：目标精度
// build_weight：构造索引的速率权重
//     如果你不关心算法构建索引的速率，可以使用默认值，如果你需要经常构建该索引，可以将该值设置更大
// memory_weight：节约内存的权重
//     如果你不关心算法消耗的内存时，可以使用默认值
// sample_fraction：训练集的比例
//     如果该值过大，则寻找合适索引构建策略的时间越长，如果该值过小，整个数据集合的计算结果可能会比训练集的计算结果糟糕很多
//     对于大的数据集，使用默认值是一个不错的选择
AutotunedIndexParams(float target_precision = 0.9, float build_weight = 0.01,
                     float memory_weight = 0.0, float sample_fraction = 0.1);
};

FLANN搜索参数

搜索参数控制了FLANN算法的一些简单行为，相关的结构体定义如下。

struct cv::flann::SearchParams : public cv::flann::IndexParams {
// 构造函数
// checks：算法内部最近相邻候选项的数量限制，从这些候选项中会确定真正的最近相邻项
// eps：保留属性，暂时未使用
//     用于KD树的变体KDTreeSingleIndex，控制在特定分支向下查询节点时的终止条件，
//     即查找的点已经足够接近以至于几乎找不到更近的节点
// sorted：当查询到多个项时，如满足指定距离内的项是否根据与查询点的距离升序排序
//     对于kNN搜索而言，该参数无效，返回结果一定升序排列
SearchParams(int checks = 32, float eps = 0, bool sorted = true);
};

4.6 结果展示

4.6.1 关键点展示

关键点展示的函数定义如下。当参数color设置为cv::Scalar::all(-1)，表示使用不同的颜色绘制关键点。参数flags定义了关键点的绘制策略，可取值为cv::DrawMatchesFlags::DEFAULT和cv::DrawMatchesFlags::DRAW_RICH_KEYPOINTS。当使用前者时，每个关键点出会绘制一个小圆圈，当使用后者时，如果关键点有大小，则使用该值作为直径绘制圆，如果有方向还会绘制特征方向。

// image：用于绘制关键点的图片
// keypoints：待绘制的关键点
// outImg：绘制完成后的图片
// color：绘制关键点使用的颜色
// flags：关键点绘制策略
void cv::drawKeypoints(const cv::Mat& image,
                       const vector<cv::KeyPoint>& keypoints,
                       cv::Mat& outImg,
                       const Scalar& color = cv::Scalar::all(-1),
                       int flags = cv::DrawMatchesFlags::DEFAULT);

4.6.2 匹配结果展示

给定一组图片，以及它们关联的关键点，和使用匹配器计算的由cv::Dmatch实例组成的匹配项列表，函数cv::drawMatches会组合这两副图像，并可视化关键点以及匹配结果。该函数的一个使用例子如下图。图中使用的关键点和描述符算法未SIFT，计算匹配项使用了算法FLANN，匹配的关键点使用白色直线相连，未找到匹配项的关键点使用黑色圆圈表示。

函数cv::drawMatches有两种变体，包含了两个不同参数，它们的定义如下。

// 包含单个匹配项列表时使用的绘图函数
// img1：拼接图像时的左图
// keypoints1：img1内的关键点
// img2：拼接图像时的右图
// keypoints2：img2内的关键点
// matches1to2：匹配项
// outImg：绘制完成的图像
// matchColor：绘制匹配项时使用的颜色
// singlePointColor：无匹配项的关键点绘制颜色
// matchesMask：匹配项绘制的蒙版向量，只有非0值对应的匹配项才会被绘制
// flags：关键点和匹配项的绘制策略，下文介绍
void cv::drawMatches(const cv::Mat& img1, const vector<cv::KeyPoint>& keypoints1,
                     const cv::Mat& img2, const vector<cv::KeyPoint>& keypoints2,
                     const vector<cv::DMatch>& matches1to2,
                     cv::Mat& outImg,
                     const cv::Scalar& matchColor = cv::Scalar::all(-1),
                     const cv::Scalar& singlePointColor = cv::Scalar::all(-1),
                     const vector<char>& matchesMask = vector<char>(),
                     int flags = cv::DrawMatchesFlags::DEFAULT)

// 包含多个匹配项列表时使用的绘图函数
void cv::drawMatches(const cv::Mat& img1, const vector<cv::KeyPoint>& keypoints1,
                     const cv::Mat& img2, const vector<cv::KeyPoint>& keypoints2,
                     const vector<vector<cv::DMatch>>& matches1to2,
                     cv::Mat& outImg,
                     const cv::Scalar& matchColor = cv::Scalar::all(-1),
                     const cv::Scalar& singlePointColor = cv::Scalar::all(-1),
                     const vector<vector<char>>& matchesMask = vector<vector<char>>(),
                     int flags = cv::DrawMatchesFlags::DEFAULT);

参数flags的可取值有🌟DEFAULT、🌟DRAW_RICH_KEYPOINTS、🌟DRAW_OVER_OUTIMG、和🌟NOT_DRAW_SINGLE_POINTS(🌟 = cv::DrawMatchesFlags::)，其中第一个选项的值为0，你可以使用逻辑与符合组合这些选项。其中DEFAULT和DRAW_RICH_KEYPOINTS的含义与函数drawKeypoints中对应项含义相同。当参数flag含有DRAW_OVER_OUTIMG就不会清除参数outImg的内容，当你需要用不同颜色绘制多组匹配项时，则可以多次调用函数drawMatches，并在第一次调用后都加入该标记。NOT_DRAW_SINGLE_POINTS被添加时，未找到匹配项的关键点将不会被绘制在输出图像中。

5 小结

在本章的开头介绍了次像素坐标和稀疏光流的概念，紧接着又讨论了关键点的基本概念，并介绍了一系列OpenCV中包含的关键点检测和描述符生成算法，以及OpenCV中对应的接口。然后我们讨论了如何高效的匹配关键点和描述符，从而应用于目标识别和追踪应用。在本章结尾介绍了如何在原图中可视化这些关键点和匹配项，更多的关键点检测器和描述副类型在本系列文章的后记中xfeatures2d部分会详细列出。