Ransac算法

1. Ransac算法

RANSAC(随机抽样一致)算法：一种经典的数据过滤和参数拟合算法。它假设数据（内点，Inliers）分布符合一定的数学模型，通过迭代计算，去除外点 (Outliers) 和噪声点， 同时获取概率上最佳的模型参数。在全局定位中，内点指正确的匹配，外点指错误的匹配，参数模型指匹配点对的空间变换矩阵。RANSAC所期望找到的匹配子集需要满足两个指标：内点重投影误差尽可能小；内点数量尽可能多。基本流程如下：

• 采样初始子集
• 计算变换矩阵
• 根据变换矩阵计算匹配点的重投影误差
• 去除误差较大的点
• 循环1-5，保留最满足指标的匹配方案

 原始特征匹配：  

经过RANSAC算法优化后的匹配：  

其中，初始候选匹配是根据描述子之间的距离产生的，但重投影误差则只和关键点的空间位置有关， 与描述子本身无关。

RANSAC算法受到原始匹配误差和参数选择的影响，只能保证算法有足够高的概率合理，不一定得到最优的结果。算法参数主要包括阈值和迭代次数。RANSAC得到可信模型的概率与迭代次数成正比，所得到的匹配数量和阈值成反比。因此实际使用时需要反复尝试不同的参数设置才能得到较好结果。依据经典RANSAC算法，学术界提出了全局RANSAC(Universal- RANSAC)流程，形成普适性RANSAC架构，将预滤波、最小子集采样、由最小子集生成可靠模型、参数校验、模型精化等模块包括了进来。

2. SIFT特征点匹配和错误剔除

SIFT算法可以得到图像中的特征点以及对应的特征描述，图像间中的特征点匹配一般可采用K近邻（KNN）算法。K近邻算法求取在空间中距离最近的K个数据点，并将这些数据点归为一类。在进行特征点匹配时，一般使用KNN算法找到最近邻的两个数据点，如果最接近和次接近的比值大于设定阈值，则保留这个最接近的值，认为它和其匹配的点为good match。

通过SIFT特征提取步骤可以得到两张图中的匹配点，不同视角的图像上的点具有如下关系：

其中[x1 y1 1]和[x2 y2 1]分别表示对应像素的齐次坐标。单应性矩阵为：

H矩阵有八个参数，求解需要八个方程，由于每一个对应的像素点可以产生2个方程(x和y)，则总共需要四个像素点来求解单应性矩阵。Ransac算法在opencv中调用方式：

H, mask = cv2.findHomography(ptsA,ptsB,cv2.RANSAC,ransacReprojThreshold)

 得到众多匹配点后，使用RANSAC算法每次从中筛选四个随机的点，然后求得H矩阵，依据RANSAC步骤不断迭代，直到求得最优的H矩阵。其中，最大投影误差的计算公式：

示例代码：

import numpy as np
import cv2
from matplotlib import pyplot as plt

def good_match(des1, des2):
    bf = cv2.BFMatcher()
    matches = bf.knnMatch(des1, des2, k=2)
    good = []
    for m, n in matches:
        if m.distance < 0.75 * n.distance:
            good.append(m)
    return good

def sift_kp(image):
    gray_image = cv2.cvtColor(image,cv2.COLOR_BGR2GRAY)
    sift = cv2.xfeatures2d_SIFT.create()
    kp,des = sift.detectAndCompute(image,None)
    kp_image = cv2.drawKeypoints(gray_image,kp,None)
    return kp_image,kp,des

def siftImageAlignment(img1,img2):
   _, kp1, des1 = sift_kp(img1)
   _, kp2, des2 = sift_kp(img2)
   goodMatch = good_match(des1, des2)
   if len(goodMatch) > 4:
       ptsA= np.float32([kp1[m.queryIdx].pt for m in goodMatch]).reshape(-1, 1, 2)
       ptsB = np.float32([kp2[m.trainIdx].pt for m in goodMatch]).reshape(-1, 1, 2)
       ransacReprojThreshold = 4
       H, mask =cv2.findHomography(ptsA,ptsB,cv2.RANSAC,ransacReprojThreshold)
       matchesMask = mask.ravel().tolist()
       img_out = cv2.warpPerspective(img2, H, (img1.shape[1], img1.shape[0]), flags=cv2.INTER_LINEAR + cv2.WARP_INVERSE_MAP)
       draw_params = dict(matchColor=(0, 255, 0),  # draw matches in green color
                          singlePointColor=None,
                          matchesMask=matchesMask,  # draw only inliers
                          flags=2)
       img3 = cv2.drawMatches(img1, kp1, img2, kp2, goodMatch, None, **draw_params)
       plt.imshow(img3, 'gray'), plt.show()
   return img_out, H, mask


if __name__ == "__main__":
    img1 = cv2.imread('D:/test/1.jpg')
    img2 = cv2.imread('D:/test/2.jpg')

    result, _, _ = siftImageAlignment(img1, img2)
    cv2.namedWindow('Result', cv2.WINDOW_NORMAL)
    cv2.imshow('Result', result)
    cv2.waitKey(0)