不管是我在之前的博文中提到的SIFT、ORB等算法，其实真正匹配的结果都不会特别好，一旦视角上的变化比较大或者出现之前图像中没有出现的区域，就很容易产生误匹配。但是在实际应用中这些误匹配的点并没有对最终的匹配结果造成很大的影响，这是因为一般在进行匹配以后，都进行了去除误匹配点对的操作，这篇博文主要介绍的就是一种比较有名的RANSAC算法。
那么，首先来看一下这个算法。

一、RANSAC算法介绍

RANSAC（Random Sample Consensus）算法是一种简单且有效的去除噪声影响，估计模型的一种方法。与普通的去噪算法不同，RANSAC算法是使用尽可能少的点来估计模型参数，然后尽可能的扩大得到的模型参数的影响范围。
RANSAC算法的具体描述是：给定 N <script type="math/tex" id="MathJax-Element-7589">N</script>个数据点组成的集合P<script type="math/tex" id="MathJax-Element-7590">P</script>，假设集合中大多数的点都是可以通过一个模型来产生的，且最少通过 n <script type="math/tex" id="MathJax-Element-7591">n</script>个点（n<N<script type="math/tex" id="MathJax-Element-7592">n 对下面的操作执行 k <script type="math/tex" id="MathJax-Element-7593">k</script>次：
（1）从P<script type="math/tex" id="MathJax-Element-7594">P</script>中随机选择 n <script type="math/tex" id="MathJax-Element-7595">n</script>个数据点；
（2）用这n<script type="math/tex" id="MathJax-Element-7596">n</script>个数据点拟合出一个模型 M <script type="math/tex" id="MathJax-Element-7597">M</script>；
（3）对P<script type="math/tex" id="MathJax-Element-7598">P</script>中剩余的数据点，计算每个点与模型 M <script type="math/tex" id="MathJax-Element-7599">M</script>的距离，距离超过阈值的则认定为局外点，不超过阈值的认定为局内点，并记录该模型M<script type="math/tex" id="MathJax-Element-7600">M</script>所对应的局内点的值 m <script type="math/tex" id="MathJax-Element-7601">m</script>；
迭代k<script type="math/tex" id="MathJax-Element-7602">k</script>次以后，选择 m <script type="math/tex" id="MathJax-Element-7603">m</script>最大的模型M<script type="math/tex" id="MathJax-Element-7604">M</script>作为拟合的结果。
因为在实际应用中 N <script type="math/tex" id="MathJax-Element-7605">N</script>的值通常会很大，那么从其中任选n<script type="math/tex" id="MathJax-Element-7606">n</script>个数据点的组合就会很大，如果对所有组合都进行上面的操作运算量就会很大，因此对于 k <script type="math/tex" id="MathJax-Element-7607">k</script>的选择就很重要。通常情况下，只要保证模型估计需要的n<script type="math/tex" id="MathJax-Element-7608">n</script>个点都是点的概率足够高即可。因此设 w <script type="math/tex" id="MathJax-Element-7609">w</script>为N<script type="math/tex" id="MathJax-Element-7610">N</script>个数据中局内点的比例， z <script type="math/tex" id="MathJax-Element-7611">z</script>为进行k<script type="math/tex" id="MathJax-Element-7612">k</script>次选取后，至少有一次选取的 n <script type="math/tex" id="MathJax-Element-7613">n</script>个点都是局内点的概率。则有

<script type="math/tex; mode=display" id="MathJax-Element-7614">z = 1-(1-w^n)^k</script>其中 1−wn <script type="math/tex" id="MathJax-Element-7615">1-w^n</script>表示一次选取不都是局内点的概率， (1−wn)k <script type="math/tex" id="MathJax-Element-7616">(1-w^n)^k</script>表示k次选取中没有一次都是局内点的概率。
则有

<script type="math/tex; mode=display" id="MathJax-Element-7617">k = \frac{log(1-z)}{log(1-w^n)}</script>
这里 z <script type="math/tex" id="MathJax-Element-7618">z</script>一般要求满足大于95%即可。

二、单应性矩阵介绍

通过上面我们了解到了RANSAC算法，那么如何应用RANSAC算法去除误配点呢。首先，我们来介绍一下单应性矩阵。
单应性矩阵描述的是针对同一事物，在不同的视角下拍摄的两幅图像之间的关系。假设这两幅图像之间是透视变换，则单应性矩阵也就是透视变换矩阵H<script type="math/tex" id="MathJax-Element-8198">H</script>定义如下：

<script type="math/tex; mode=display" id="MathJax-Element-8199">H = \left[ \begin{matrix} h_{11}&h_{12}&h_{13}\\h_{21}&h_{22}&h_{23}\\h_{31}&h_{32}&1 \end{matrix} \right]</script>
则有 <script type="math/tex; mode=display" id="MathJax-Element-8200">\left[ \begin{matrix} x'\\y'\\1 \end{matrix} \right] = \left[ \begin{matrix} h_{11}&h_{12}&h_{13}\\h_{21}&h_{22}&h_{23}\\h_{31}&h_{32}&1 \end{matrix} \right] \left[ \begin{matrix} x\\y\\1 \end{matrix}\right]</script>
因此要恢复出 H <script type="math/tex" id="MathJax-Element-8201">H</script>中的8个参数，至少需要4对匹配点，过程如下：

那么就可以每次从所有的匹配点中选出4对，计算单应性矩阵H<script type="math/tex" id="MathJax-Element-8202">H</script>，然后选出内点个数最多的作为最终的结果。计算距离方法如下：

三、基础矩阵介绍

对于基础矩阵的介绍在我之前的博文里已经介绍过 三维重建（一）外极几何，基础矩阵及求解，使用RANSAC方法也与上面单应性矩阵的方法相同。
这里需要注意的是，使用单应性矩阵的方法去除误匹配点对更加严格，也就是说得到的结果更加精确，但是相对于基础矩阵的方法来讲，最后得到的匹配点数目也更少。