从OpenCV源码学习match()和knnMatch()进行双目匹配

写在前面的话：最近做双目匹配，需要用到OpenCV的特征识别匹配，但是对于低反射率物体即使投影了随机散斑之后出来的效果依旧很差，于是乎看看特征匹配的源码，看看能不能从原理上有所发现（用的knnMatch并且已经极线对准，可是效果在有的图上比较凉凉）。废话不多说，这篇博文讲的是看源码学习OpenCV，仿佛没找到比较好的文章，于是，自己看，写一个。后续有发现的话在后面补充。环境：OpenCV3.2源码，VS2013（为什么不用新的？公司要求啊。。。要求统一环境）

//其实很早就该写了，但是考虑到科研可能要用这个改匹配算法，就先没写，后来改用了别的方案，匹配效果远比这个方法好。这篇博文讲的是这个算法的组织，以及可以根据学习结果改一改匹配函数用来针对性提升效果。所以默认读者是会用的。事实证明只用OCV自己的库只能满足玩一玩的需求，距离应用还有很大距离。

这里用的OpenCV3.3的文档，为什么不用3.2的文档？因为我之前用3.3后来被迫换3.2，于是乎懒得下3.2文档，毕竟基本都一样，发现不对的话再去查，这里懒一下，其实这么做是不对的。（反正是实习，随便玩哈哈哈*2333）看文档有助于看懂源码，尤其是理清类之间的关系。

基类的方法，这里主要要看的是箭头标记的那俩，因为这俩是我要用的。发现这个DescriptorMatcher是个抽象的基类，后面有俩子类，实际上我们在用的时候也是用的后面俩，分别是BFMatch和FlannBasedMatcher。

上面是match()的文档，看不清可以去文档官网一大把doc，各种版本都有哈，我习惯下下来看，比较方便，一样的。

再看看knnMatch()的文档，嗯。好了不解释了，很简单的英文。match()匹配点对，knnMatch()返回每个点的k个匹配点，所以感觉knnMatch给的选择更多一点，而且给出候选点更可能包含真正的匹配点（事实就是这样的，后面说）

在源码里找到match()的实现:

发现match()实际上调用就是knnMatch()把返回k个的匹配包了一层皮，设置返回一个最匹配的点。所以重点就一个knnMatch()就完了。我们转到定义，去看看knnMatch()发现：

看一眼源码发现knnMatch()第一个调用的是第二个重载的knnMatch()（猜也猜得到）然后有调用的DescriptorMatcher: :knnMatchImpl()在两个基类的实现，于是乎vs go to define时候有：BF还是FLANN，也就是说上面说过的两个子类要分别实现父类：DescriptorMatcher的方法了（顺便看一下大佬写C++，学学经验）我goto到了BFMatcher::knnMatchImpl()。这个方法分别在两个子类里面实现了。这个基类是没有实现的。

忽略掉一堆为了安全机制和指令集还有工程上的那堆杂七杂八的成熟的考虑，比如一堆宏和条件编译。看重点，判断两个向量的匹配度还不是要算距离函数，什么欧氏距离、余弦距离、汉明距离…

找到了计算距离函数的地方，这里默认欧氏距离了（看默认参数）。然后去找找文档。文档里没有给匹配函数指定距离函数的参数，其实在构造器构造函数里：

也是默认构造用的欧氏距离，读者有兴趣可以试试别的距离函数，

文档里有对NormTypes的公式定义，很清晰，宏分别对应什么距离函数一清二楚。但是这是有问题的，一会看下面。

在core/stat.cpp里实现的距离计算。（字体突然变了？换成了VS2017,2013版的go to def找不到，17版这些方面还有实时看资源占用是真的方便。。想用17。。。）可以看到源码对于CV_8U还是很友好的，实现了不少，对于CV_32F只实现了三种，说好的那么多NormType。当然这里我们看到的可能不一样，我不记得我是不是改过源码，印象中至少其他部分我改过，改完应该会有我的标记的，毕竟过去接近一年了，坏习惯。红色剪头是crosscheck的实现，一个自我调用，参数取false就完成了，这个操作天秀啊（对于当时我这个没见过世面的菜鸡来说。现在习惯了）。

如果想要修改匹配规则，按照源码的布局，在你的工程里复制大部分BFMatch的源码，照葫芦画瓢改就可以了，对于CV_32F，我尝试了不同的距离函数，也可以自定义距离运算。这里贴出来：

这样就可以自己随心所欲地修改匹配规则了。详细的就不贴了，最后。我放弃了OpenCV的匹配规则（尝试实现了源码没有实现的方法，发现还是NORM_L2稳定可靠，尴尬，因为浮点数乘除太容易出现问题了），而是采用纯数学计算和图像处理的方法。如果文章录的话，我把文章再贴这。不过文章也没有描述的很详细，领导不让写详细，摊手。照葫芦画瓢，Flann也能自己看懂了。不过建议先找文章和文档看，不然直接上手源码还是有压力的，看完文章和文档可能还有不清楚的，这时候源码描述的一清二楚。先写到这里，我写博客真随意。

当图像中同一点周围有多个特征向量时。比如坐标点p(10,10)提取了特征向量，同时坐标点p2(10,11)和点p3(11,10)等附近点同样提取到特征向量。那么原则上另一幅图像的对应正确匹配点和上述点的计算“距离”，应当是相近的。

这里就用到了上面的内容，只有在源码里可以随意修改。看源码可以知道下图的dist存储的实际是排序好的特征向量距离，以NORM_L2为例： 然后最后得到的排序好的相似度排序可以得到： （这里是自己画出来的展示图，是行匹配时候，左图一行在右图对应的查找出来的匹配点。在ImageWatch里面看，VS2017可用的ImageWatch可以在我上传的资源找。下图的一行就是对于某一个点，在右图的候选点的计算结果，举个例子：第一行就是对于左图某一点，在右图候选点的相关度计算结果，每个像素存储的就是一个点的相关度） 再稍微解释下：像素的第一个通道是匹配点所在列（双目匹配，相机经过标定，且经过极线校正。我感觉这部分这里就不说了，网上也挺多的，用OpenCV的stereoCalib相关的那堆）。第二行数据为左图右图匹配点的行偏差。第三行就是真正的dist，计算公式在NormType也可以自己丰富。（其实写这篇博客的目的就是要自己去修改它的匹配规则来优化）可以看到对于某个待匹配点，计算出来的候选点经过匹配计算，也都是相邻的点（图像局部相似性）。 Lowe进行特征匹配筛选采用：最佳匹配点与次佳匹配点比值的形式，ratio 资料很多，上图截取自这个帖子。虽然是有效果的，但是，我认为这其实是在去除个别特殊的离群值。其实本身没有直接原理证明，只是一种概率统计学的规律，当然并没有深究，说的错的话轻喷，评论可以给我科普一下。（Lowe大佬的paper都敢质疑，怕是疯了）可以看到，有的时候最佳匹配（第0列）比次佳匹配（第一列）其实不见得就是正确的匹配。比如第0行，第540列明显比216列更像对的匹配点所在列（当然也不一定是对的）。所以可以在匹配时候保留前n个匹配点，然后根据聚集程度筛选。（我才用的是统计方式，可以用直方图也可以用别的方式，自由发挥） 对比一下用这种匹配出来的结果和原来的结果： 先看原来的结果： 可以看到效果还是不错的。下面是采用统计筛选出来的结果： 可以看到数据的完整性好的多，但是噪声也多了很多。至于去噪，还是有办法的，常见的二维去噪的原理都可以应用。 因为一些扯淡的原因不能公开，所以可以自己脑补去噪算法，其实应用常规二维图像去噪的原理修改一下即可。

（2019年3月19日09:07:42）这里只是讲解了如何看源码，以及OpenCV里面的一些工程结构和算法实现，可以类比这些去学习OpenCV其他部分。不得不说OCV是一个很强的库，从这里面看源码可以学到好多骚操作。冈萨雷斯第三版里面的所有算法这里都有实现，而且还有改进。当然，看源码注释经常能看到XXX来自XXX的文章，然后附上链接。这是对知识的尊重。感动ing… 这里讲了knnMatch的向量相似度计算查找最近似解。实际上，在真正的双目三维重构上，用这种方法做出来的效果是完全不能满足测量要求的，因为点密度不可控、对噪声的鲁棒性也很差、计算复杂度也很高，所以，学习学习就好啦，毕竟这个module不是专门用于3Dreconstruction的。顺便在下面贴出来我们现在已经做到的效果看看叭