原理

基础矩阵

$$X_1^{T}F{X}_2=0\text{\hspace{1em}(1)}$$
$X1$与$X2$是两幅图像的一对匹配点，$F$为基础矩阵，基础矩阵为一幅图像上像$p_1$点到另一幅图像上对极线$L_2$的一种映射。所以有如下公式：
$$L_2=F\ast p_1\text{\hspace{1em}(2)}$$
此公式为后面$ransac$算法需要用到。
基础矩阵F是一个3×3的矩阵，总共有9个未知元素。然而，上面的公式中使用的齐次坐标，齐次坐标在相差一个常数因子下是相等，$F$也就只有8个未知元素，也就是说，只需要8对匹配的点对就可以求解出两视图的基础矩阵$F$。下面介绍下8点法 $Eight-Point-Algorithm$计算基础矩阵的过程。假设在两幅图像对应匹配点的坐标分别为：$X_1=(x_1,y_1,1{)}^T$，$X_2=(x_2,y_2,1{)}^T$,那么由基础矩阵公式得：
$$\left[\begin{array}{ccc}{x}_1& y_1& 1\end{array}\right]\left[\begin{array}{ccc}{f}_{11}& f_{12}& f_{13}\\ f_{21}& f_{22}& f_{23}\\ f_{31}& f_{32}& f_{33}\end{array}\right]\left[\begin{array}{c}{x}_2\\ y_2\\ 1\end{array}\right]=0\text{\hspace{1em}(3)}$$
也即：
$$x_2{x}_1{f}_{11}+x_2{y}_1{f}_{12}+x_2{f}_{13}+y_2{x}_1{f}_{21}+y_2{y}_1{f}_{22}+y_2{f}_{23}+x_1{f}_{31}+y_2{f}_{32}+f_{33}=0\text{\hspace{1em}(4)}$$
将上述公式中的F看成列向量：
$$F=\left[\begin{array}{ccccccc}{f}_{11}& f_{12}& f_{13}{f}_{21}& f_{22}& f_{23}{f}_{31}& f_{32}& f_{33}\end{array}\right]\text{\hspace{1em}(5)}$$
那么可将上述公式改写为：
$$\left[\begin{array}{ccccccccc}{x}_2{x}_1& x_2{y}_1& x_2& y_2{x}_1& y_2{y}_1& y_2& x_1& y_2& 1\end{array}\right]F=0\text{\hspace{1em}(6)}$$
给定8组点的集合，我们有如下方程：

$$\left[\begin{array}{ccccccccc}{x}_2^1{x}_1^1& x_2^1{y}_1^1& x_2^1& y_2^1{x}_1^1& y_2^1{y}_1^1& y_2^1& x_1^1& y_2^1& 1\\ x_2^2{x}_1^2& x_2^2{y}_1^2& x_2^2& y_2^2{x}_1^2& y_2^2{y}_1^2& y_2^2& x_1^2& y_2^2& 1\\ x_2^3{x}_1^3& x_2^3{y}_1^3& x_2^3& y_2^3{x}_1^3& y_2^3{y}_1^3& y_2^3& x_1^3& y_2^3& 1\\ x_2^4{x}_1^4& x_2^4{y}_1^4& x_2^4& y_2^4{x}_1^4& y_2^4{y}_1^4& y_2^4& x_1^4& y_2^4& 1\\ x_2^5{x}_1^5& x_2^5{y}_1^5& x_2^5& y_2^5{x}_1^5& y_2^5{y}_1^5& y_2^5& x_1^5& y_2^5& 1\\ x_2^6{x}_1^6& x_2^6{y}_1^6& x_2^6& y_2^6{x}_1^6& y_2^6{y}_1^6& y_2^6& x_1^6& y_2^6& 1\\ x_2^7{x}_1^7& x_2^7{y}_1^7& x_2^7& y_2^7{x}_1^7& y_2^7{y}_1^7& y_2^7& x_1^7& y_2^7& 1\\ x_2^8{x}_1^8& x_2^8{y}_1^8& x_2^8& y_2^8{x}_1^8& y_2^8{y}_1^8& y_2^8& x_1^8& y_2^8& 1\end{array}\right]\left[\begin{array}{c}{f}_{11}\\ f_{12}\\ f_{13}\\ f_{21}\\ f_{22}\\ f_{23}\\ f_{31}\\ f_{32}\\ f_{33}\end{array}\right]=0\text{\hspace{1em}(7)}$$
求解上述方程的就可以解矩阵F的各个系数，这里选择用$SVD$算法求解，但是由于噪声、错误匹配点等因素影响，可能导致$(7)$公式求解得到的基础矩阵不稳定，所以基于此选择$ransac$算法对其进行改进得到最优的F矩阵。

RANSAC算法

RANSAC算法的基本假设是样本中包含正确数据(inliers，可以被模型描述的数据)，也包含异常数据(outliers，偏离正常范围很远、无法适应数学模型的数据)，即数据集中含有噪声。这些异常数据可能是由于错误的测量、错误的假设、错误的计算等产生的。同时RANSAC也假设，给定一组正确的数据，存在可以计算出符合这些数据的模型参数的方法。

算法的基本假设是：

• 数据由“局内点”组成，例如：数据的分布可以用一些模型参数来解释；
• “局外点”是不能适应该模型的数据；
• 除此之外的数据属于噪声。
• 局外点产生的原因有：噪声的极值；错误的测量方法；对数据的错误假设。

RANSAC基本思想描述如下：

• 考虑一个最小抽样集的势为n的模型(n为初始化模型参数所需的最小样本数)和一个样本集P，集合P的样本数#§>n，从P中随机抽取包含n个样本的P的子集S初始化模型M；
• 余集$SC=\frac{P}{S}$中与模型M的误差小于某一设定阈值t的样本集以及S构成S*。S*认为是内点集，它们构成S的一致集(Consensus Set)；
• 若#(S*)≥N，认为得到正确的模型参数，并利用集S*(内点inliers)采用最小二乘等方法重新计算新的模型M*；重新随机抽取新的S，重复以上过程。
• 在完成一定的抽样次数后，若未找到一致集则算法失败，否则选取抽样后得到的最大一致集判断内外点，算法结束。

RANSAC的优点

• 能鲁棒的估计模型参数。例如，它能从包含大量局外点的数据集中估计出高精度的参数。

RANSAC的缺点：

• 计算参数的迭代次数没有上限；如果设置迭代次数的上限，得到的结果可能不是最优的结果，甚至可能得到错误的结果。RANSAC只有一定的概率得到可信的模型，概率与迭代次数成正比。
• 要求设置跟问题相关的阀值。而且RANSAC只能从特定的数据集中估计出一个模型，如果存在两个（或多个）模型，RANSAC不能找到别的模型。

RANSAC用于剔除错误匹配的算法流程：

• 从匹配的点对中选择8个点，使用归一化8点法估算出基础矩阵$F$
• 计算其余的点对到其对应对极线的距离$d_p$，如果$d_p\le d$则该点为内点，否则为外点。记下符合该条件的内点的个数为$num$
• 迭代k次，或者某次得到内点的数目$num$占有的比例大于等于95%，则停止。选择$num$最大的基础矩阵作为最终的结果。

代码现实

此函数为八点法实现， $x1、x2$为匹配点集合，8点法传入的x1,x2分别为对应的8对匹配点，此处为实现公式7的过程，求解线性方程组的解使用的$SVD$(奇异值分解)算法，$SVD$算法为机器学习的一种算法，具体原理可以网上搜索资料。U,S,V分别为计算得到的左奇异值、奇异值、右奇异值。

def compute_fundamental(x1, x2):
   n = x1.shape[1]
   if x2.shape[1] != n:
       raise ValueError("Number of points don't match.")
   A = np.zeros((n, 9))
   for i in range(n):
       A[i] = [x1[0, i] * x2[0, i], x1[0, i] * x2[1, i], x1[0, i] * x2[2, i],
               x1[1, i] * x2[0, i], x1[1, i] * x2[1, i], x1[1, i] * x2[2, i],
               x1[2, i] * x2[0, i], x1[2, i] * x2[1, i], x1[2, i] * x2[2, i]]
   U, S, V = np.linalg.svd(A)
   F = V[-1].reshape(3, 3)
   U, S, V = np.linalg.svd(F)
   S[2] = 0
   F = np.dot(U, np.dot(np.diag(S), V))

   return F / F[2, 2]

此处为将匹配点进行归一化处理。

 def compute_fundamental_normalized(x1, x2):
    n = x1.shape[1]
    if x2.shape[1] != n:
        raise ValueError("Number of points don't match.")
    # normalize image coordinates
    x1 = x1 / x1[2]
    mean_1 = np.mean(x1[:2], axis=1)
    S1 = np.sqrt(2) / np.std(x1[:2])
    T1 = np.array([[S1, 0, -S1 * mean_1[0]], [0, S1, -S1 * mean_1[1]], [0, 0, 1]])
    x1 = np.dot(T1, x1)
    x2 = x2 / x2[2]
    mean_2 = np.mean(x2[:2], axis=1)
    S2 = np.sqrt(2) / np.std(x2[:2])
    T2 = np.array([[S2, 0, -S2 * mean_2[0]], [0, S2, -S2 * mean_2[1]], [0, 0, 1]])
    x2 = np.dot(T2, x2)
   
    # compute F with the normalized coordinates
    F = compute_fundamental(x1, x2)
    # print (F)
    # reverse normalization
    F = np.dot(T1.T, np.dot(F, T2))

    return F / F[2, 2]

随机选择8对匹配点，用于计算基础矩阵。

def randSeed(good, num = 8):
 '''
 :param good: 初始的匹配点对
 :param num: 选择随机选取的点对数量
 :return: 8个点对list
 '''
 eight_point = random.sample(good, num)
 return eight_point

计算匹配点对的坐标，注意返回坐标为$(x,y)$形式，所以此处增加了一个维度使得返回的为$(x,y,1)$的形式，与前述公式对应。

def PointCoordinates(eight_points, keypoints1, keypoints2):
    '''
    :param eight_points: 随机八点
    :param keypoints1: 点坐标
    :param keypoints2: 点坐标
    :return:8个点
    '''
    x1 = []
    x2 = []
    tuple_dim = (1.,)
    for i in eight_points:
        tuple_x1 = keypoints1[i[0].queryIdx].pt + tuple_dim
        tuple_x2 = keypoints2[i[0].trainIdx].pt + tuple_dim
        x1.append(tuple_x1)
        x2.append(tuple_x2)
    return np.array(x1, dtype=float), np.array(x2, dtype=float)

此处为ransac算法计算匹配点与对极线的距离，由公式$(2)$以及8点法计算得到的F可以计算出对极线的表达式，其中$L=[a,b,c]$对极线的方向向量为[-b,a]，所以此处计算距离利用的是点到向量的距离计算公式$d=\frac{|a\times b|}{a}$，具体公式原理自行百度。

def inlier(F,good, keypoints1,keypoints2,confidence):
    num = 0
    ransac_good = []
    x1, x2 = PointCoordinates(good, keypoints1, keypoints2)
    for i in range(len(x2)):
        line = F.dot(x1[i].T)
        #在对极几何中极线表达式为[A B C],Ax+By+C=0,  方向向量可以表示为[-B,A]
        line_v = np.array([-line[1], line[0]])
        err = h = np.linalg.norm(np.cross(x2[i,:2], line_v)/np.linalg.norm(line_v))
        # err = computeReprojError(x1[i], x2[i], F)
        if abs(err) < confidence:
            ransac_good.append(good[i])
            num += 1
    return num, ransac_good

此函数为ransac算法实现， 从匹配的点对中选择8个点，使用归一化8点法估算出基础矩阵$F$
计算其余的点对到其对应对极线的距离$d_p$，如果$d_p\le d$则该点为内点，否则为外点。记下符合该条件的内点的个数为$num$迭代k次，或者某次得到内点的数目$num$占有的比例大于等于95%，则停止。选择$num$最大的基础矩阵作为最终的结果。保存最优的结果。

 def ransac(good, keypoints1, keypoints2, confidence,iter_num):
  Max_num = 0
  good_F = np.zeros([3,3])
  inlier_points = []
  for i in range(iter_num):
      eight_points = randSeed(good)
      x1,x2 = PointCoordinates(eight_points, keypoints1, keypoints2)
      F = compute_fundamental_normalized(x1.T, x2.T)
      num, ransac_good = inlier(F, good, keypoints1, keypoints2, confidence)
      if num > Max_num:
          Max_num = num
          good_F = F
          inlier_points = ransac_good
  print(Max_num, good_F)
  return Max_num, good_F, inlier_points

测试

sift特征提取匹配点，可以发现有很多错误的匹配点。

利用ransac算法剔除错误匹配点。

$Github$

完整代码见我的$Github$地址：sunrise666。

最后

以上就是魁梧康乃馨为你收集整理的计算机视觉：RANSAC剔除基础矩阵F错误匹配(Python实现)原理代码现实的全部内容，希望文章能够帮你解决计算机视觉：RANSAC剔除基础矩阵F错误匹配(Python实现)原理代码现实所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。