特征提取与匹配---SURF；SIFT；ORB；FAST；Harris角点
匹配方法
匹配函数
1. OpenCV提供了两种Matching方式：
• Brute-force matcher (cv::BFMatcher) //暴力方法找到点集1中每个descriptor在点集2中距离最近的descriptor；找寻到的距离最小就认为匹配//浮点描述子-欧氏距离；二进制描述符-汉明距离。//详细描述：在第一幅图像中选取一个关键点然后依次与第二幅图像的每个关键点进行（描述符）距离测试，最后返回距离最近的关键点 • Flann-based matcher (cv::FlannBasedMatcher) //快速最近邻搜索算法寻找（用快速的第三方库近似最近邻搜索算法）//是一个对大数据集和高维特征进行最近邻搜索的算法的集合，在面对大数据集时它的效果要好于BFMatcher。 //使用FLANN匹配需要传入两个字典参数：一个参数是IndexParams，对于SIFT和SURF，可以传入参数index_params=dict(algorithm=FLANN_INDEX_KDTREE, trees=5)。 对于ORB，可以传入参数index_params=dict(algorithm=FLANN_INDEX_LSH, table_number=6, key_size=12, multi_probe_level=1)。 第二个参数是SearchParams，可以传入参数search_params=dict(checks=100)，它来指定递归遍历的次数，值越高结果越准确，但是消耗的时间也越多。
cv::BFMatcher(int normType=NORM_L2, bool crossCheck=false)，如下所示：1. normType：它是用来指定要使用的距离测试类型,默认值为cv2.Norm_L2,这很适合SIFT和SURF等（c2.NORM_L1也可）。对于使用二进制描述符的ORB、BRIEF和BRISK算法等，要使用cv2.NORM_HAMMING， 这样就会返回两个测试对象之间的汉明距离。如果ORB算法的参数设置为WTA_K==3或4，normType就应该设置成cv2.NORM_HAMMING2。2. crossCheck：默认值为False。如果设置为True，匹配条件就会更加严格，只有到A中的第i个特征点与B中的第j个特征点距离最近，并且B中的第j个特征点到A中的第i个特征点也是最近时才会返回最佳匹配(i,j)， 即这两个特征点要互相匹配才行。BFMatcher对象有两个方法BFMatcher.match()和BFMatcher.knnMatch()。第一个方法会返回最佳匹配。第二个方法为每个关键点返回k个最佳匹配，其中k是由用户设定的。 cv2.drawMatches()来绘制匹配的点，它会将两幅图像先水平排列，然后在最佳匹配的点之间绘制直线。 如果前面使用的是BFMatcher.knnMatch()，现在可以使用函数cv2.drawMatchsKnn为每个关键点和它的个最佳匹配点绘制匹配线，如果要选择性绘制就要给函数传入一个掩模。
一般，点集1称为 train set （训练集）的对应模板图像，点集2称为 query set（查询集）的对应查找模板图的目标图像。
为了提高检测速度，你可以调用matching函数前，先训练一个matcher。训练过程可以首先使用cv::FlannBasedMatcher来优化，为descriptor建立索引树，这种操作将在匹配大量数据时发挥巨大作用。
而Brute-force matcher在这个过程并不进行操作，它只是将train descriptors保存在内存中。
2. matching过程---使用cv::DescriptorMatcher的如下功能来进行匹配：
- 简单查找最优匹配：
void match( const Mat& queryDescriptors, std::vector<DMatch>& matches, const std::vector<Mat>& masks = std::vector<Mat>() );
- 为每个descriptor查找K-nearest-matches：
void knnMatch( const Mat& queryDescriptors, std::vector<std::vector<DMatch> >& matches, int k, const std::vector<Mat>& masks = std::vector<Mat>(), bool compactResult = false );
- 查找那些descriptors间距离小于特定距离的匹配：
void radiusMatch( const Mat& queryDescriptors, std::vector<std::vector<DMatch> >& matches, float maxDistance, const std::vector<Mat>& masks = std::vector<Mat>(), bool compactResult = false );
3. matching结果包含许多错误匹配，错误的匹配分为两种：
- False-positive matches: 将非对应特征点检测为匹配（我们可以对他做文章，尽量消除它）
- False-negative matches: 未将匹配的特征点检测出来（无法处理，因为matching算法拒绝）
- Cross-match filter：在OpenCV中 cv::BFMatcher class已经支持交叉验证，建立 cv::BFMatcher将第二参数声明为true---cv::BFMatcher(cv::NORM_HAMMING,true)
- Ratio test：使用KNN-matching算法，令K=2。则每个match得到两个最接近的descriptor，然后计算最接近距离和次接近距离之间的比值，当比值大于既定值时，才作为最终match。
- RANSAC：随机样本一致性方法，因为我们是使用一幅图像（一个平面物体），可以将它定义为刚性的，在pattern image和query image的特征点之间使用cv::findHomography找到单应性变换（homography transformation），再使用RANSAC找到最佳匹配，从而找到最佳单应性矩阵。（由于cv::findHomography这个函数使用的特征点同时包含正确和错误匹配点，因此计算的单应性矩阵依赖于二次投影的准确性，下面有详细解释）
代码说明---OpenCV3中特征点的提取和匹配
OpenCV中封装了常用的特征点算法（如SIFT,SURF，ORB等），提供了统一的接口，便于调用。 下面代码是OpenCV中使用其feature 2D 模块的示例代码
Mat img1 = imread("F:\\image\\1.png");Mat img2 = imread("F:\\image\\2.png");// 1. 初始化vector<KeyPoint> keypoints1, keypoints2;Mat descriptors1, descriptors2;Ptr<ORB> orb = ORB::create();// 2. 提取特征点orb->detect(img1, keypoints1);orb->detect(img2, keypoints2);// 3. 计算特征描述符orb->compute(img1, keypoints1, descriptors1);orb->compute(img2, keypoints2, descriptors2);// 4. 对两幅图像的BRIEF描述符进行匹配，使用BFMatch，Hamming距离作为参考vector<DMatch> matches;BFMatcher bfMatcher(NORM_HAMMING);bfMatcher.match(descriptors1, descriptors2, matches);
- 获取检测器的实例
在OpenCV3中重新的封装了特征提取的接口，可统一的使用Ptr<FeatureDetector> detector = FeatureDetector::create()来得到特征提取器的一个实例，所有的参数都提供了默认值，也可以根据具体的需要传入相应的参数。 - 在得到特征检测器的实例后，可调用的
detect方法检测图像中的特征点的具体位置，检测的结果保存在vector<KeyPoint>向量中。 - 有了特征点的位置后，调用
compute方法来计算特征点的描述子，描述子通常是一个向量，保存在Mat中。 - 得到了描述子后，可调用匹配算法进行特征点的匹配。上面代码中，使用了opencv中封装后的暴力匹配算法
BFMatcher，该算法在向量空间中，将特征点的描述子一一比较，选择距离（上面代码中使用的是Hamming距离）较小的一对作为匹配点。
上面代码匹配后的结果如下：
特征点的匹配后的优化
特征的匹配是针对特征描述子进行的，上面提到特征描述子通常是一个向量，两个特征描述子的之间的距离可以反应出其相似的程度，也就是这两个特征点是不是同一个。
根据描述子的不同，可以选择不同的距离度量。如果是浮点类型的描述子，可以使用其欧式距离；对于二进制的描述子（BRIEF）可以使用其汉明距离（两个不同二进制之间的汉明距离指的是两个二进制串不同位的个数）。
有了计算描述子相似度的方法，那么在特征点的集合中如何寻找和其最相似的特征点，这就是特征点的匹配了。最简单直观的方法就是上面使用的：暴力匹配方法(Brute-Froce Matcher)，计算某一个特征点描述子与其他所有特征点描述子之间的距离，然后将得到的距离进行排序，取距离最近的一个作为匹配点。这种方法简单粗暴，其结果也是显而易见的，通过上面的匹配结果，也可以看出有大量的错误匹配，这就需要使用一些机制来过滤掉错误的匹配。
汉明距离小于最小距离的两倍
选择已经匹配的点对的汉明距离不大于最小距离的两倍作为判断依据，如果不大于该值则认为是一个正确的匹配，过滤掉；大于该值则认为是一个错误的匹配。其实现代码也很简单，如下：// 匹配对筛选 double min_dist = 1000, max_dist = 0; // 找出所有匹配之间的最大值和最小值 for (int i = 0; i < descriptors1.rows; i++) {double dist = matches[i].distance;if (dist < min_dist) min_dist = dist;if (dist > max_dist) max_dist = dist; } // 当描述子之间的匹配不大于2倍的最小距离时，即认为该匹配是一个错误的匹配。 // 但有时描述子之间的最小距离非常小，可以设置一个经验值作为下限 vector<DMatch> good_matches; for (int i = 0; i < descriptors1.rows; i++) {if (matches[i].distance <= max(2 * min_dist, 30.0))good_matches.push_back(matches[i]); }
结果如下：
对比只是用暴力匹配的方法，进行过滤后的匹配效果好了很多。
交叉匹配
针对暴力匹配，可以使用交叉匹配的方法来过滤错误的匹配。交叉过滤的思想很简单，再进行一次匹配，反过来使用被匹配到的点进行匹配，如果匹配到的仍然是第一次匹配的点的话，就认为这是一个正确的匹配。举例来说就是，假如第一次特征点A使用暴力匹配的方法，匹配到的特征点是特征点B；反过来，使用特征点B进行匹配，如果匹配到的仍然是特征点A，则就认为这是一个正确的匹配，否则就是一个错误的匹配。OpenCV中BFMatcher已经封装了该方法，创建BFMatcher的实例时，第二个参数传入true即可，BFMatcher bfMatcher(NORM_HAMMING,true)。KNN匹配
K近邻匹配，在匹配的时候选择K个和特征点最相似的点，如果这K个点之间的区别足够大，则选择最相似的那个点作为匹配点，通常选择K = 2，也就是最近邻匹配。对每个匹配返回两个最近邻的匹配，如果第一匹配和第二匹配距离比率足够大（向量距离足够远），则认为这是一个正确的匹配，比率的阈值通常在2左右。
OpenCV中的匹配器中封装了该方法，上面的代码可以调用bfMatcher->knnMatch(descriptors1, descriptors2, knnMatches, 2);具体实现的代码如下：const float minRatio = 1.f / 1.5f; const int k = 2;vector<vector<DMatch>> knnMatches; matcher->knnMatch(leftPattern->descriptors, rightPattern->descriptors, knnMatches, k);for (size_t i = 0; i < knnMatches.size(); i++) {const DMatch& bestMatch = knnMatches[i][0];const DMatch& betterMatch = knnMatches[i][1];float distanceRatio = bestMatch.distance / betterMatch.distance;if (distanceRatio < minRatio)matches.push_back(bestMatch); }
将不满足的最近邻的匹配之间距离比率大于设定的阈值（1/1.5）匹配剔除。
- RANSAC
随机采样一致性（RANSAC）可过滤掉错误的匹配，该方法利用匹配点计算两个图像之间单应矩阵，并分解得到位姿R，t，通过三角测量来得到两个关联特征对应的3D点，将3D点按照当前估计的位姿进行投影，也就是重投影，然后利用重投影误差（观测到得投影位置（像素坐标）与3D点进行重投影的位置之差）来判定某一个匹配是不是正确的匹配。
OpenCV中封装了求解单应矩阵的方法findHomography,可以为该方法设定一个重投影误差的阈值，可以得到一个向量mask来指定那些是符合该重投影误差的匹配点对（Inliers），以此来剔除错误的匹配，代码如下：
const int minNumbermatchesAllowed = 8; if (matches.size() < minNumbermatchesAllowed)return;//Prepare data for findHomography vector<Point2f> srcPoints(matches.size()); vector<Point2f> dstPoints(matches.size());for (size_t i = 0; i < matches.size(); i++) {srcPoints[i] = rightPattern->keypoints[matches[i].trainIdx].pt;dstPoints[i] = leftPattern->keypoints[matches[i].queryIdx].pt; }//find homography matrix and get inliers mask vector<uchar> inliersMask(srcPoints.size()); homography = findHomography(srcPoints, dstPoints, CV_FM_RANSAC, reprojectionThreshold, inliersMask);vector<DMatch> inliers; for (size_t i = 0; i < inliersMask.size(); i++){if (inliersMask[i])inliers.push_back(matches[i]); } matches.swap(inliers);
备注：OpenCV的特征点匹配及一些剔除错误匹配的文章，OpenCV2:特征匹配及其优化，使用的是OpenCV2，在OpenCV3中更新了特征点检测和匹配的接口，不过大体还是差不多的。
主要包括以下几个内容：
- DescriptorMatcher
DescriptorMatcher是匹配特征向量的抽象类，在OpenCV2中的特征匹配方法都继承自该类（例如：BFmatcher，FlannBasedMatcher）。
该类主要包含了两组匹配方法：图像对之间的匹配以及图像和一个图像集之间的匹配。
用于图像对之间匹配的方法的声明
// Find one best match for each query descriptor (if mask is empty). CV_WRAP void match( const Mat& queryDescriptors, const Mat& trainDescriptors, CV_OUT vector<DMatch>& matches, const Mat& mask=Mat() ) const; // Find k best matches for each query descriptor (in increasing order of distances). // compactResult is used when mask is not empty. If compactResult is false matches vector will have the same size as queryDescriptors rows. // If compactResult is true matches vector will not contain matches for fully masked out query descriptors. CV_WRAP void knnMatch( const Mat& queryDescriptors, const Mat& trainDescriptors, CV_OUT vector<vector<DMatch> >& matches, int k, const Mat& mask=Mat(), bool compactResult=false ) const; // Find best matches for each query descriptor which have distance less than maxDistance (in increasing order of distances). void radiusMatch( const Mat& queryDescriptors, const Mat& trainDescriptors, vector<vector<DMatch> >& matches, float maxDistance, const Mat& mask=Mat(), bool compactResult=false ) const;方法重载，用于图像和图像集匹配的方法声明
CV_WRAP void match( const Mat& queryDescriptors, CV_OUT vector<DMatch>& matches,const vector<Mat>& masks=vector<Mat>() ); CV_WRAP void knnMatch( const Mat& queryDescriptors, CV_OUT vector<vector<DMatch> >& matches, int k, const vector<Mat>& masks=vector<Mat>(), bool compactResult=false ); void radiusMatch( const Mat& queryDescriptors, vector<vector<DMatch> >& matches, float maxDistance, const vector<Mat>& masks=vector<Mat>(), bool compactResult=false );- DMatcher
DMatcher 是用来保存匹配结果的，主要有以下几个属性
CV_PROP_RW int queryIdx; // query descriptor indexCV_PROP_RW int trainIdx; // train descriptor index CV_PROP_RW int imgIdx; // train image index CV_PROP_RW float distance;在图像匹配时有两种图像的集合，查找集（Query Set）和训练集（Train Set），对于每个Query descriptor，DMatch中保存了和其最好匹配的Train descriptor。另外，每个train image会生成多个train descriptor。
如果是图像对之间的匹配的话，由于所有的train descriptor都是由一个train image生成的，所以在匹配结果DMatch中所有的imgIdx是一样的，都为0.
- KNN匹配
- 计算两视图的基础矩阵F，并细化匹配结果
- 计算两视图的单应矩阵H，并细化匹配结果
