一种基于加权采样的图像特征点匹配方法

摘要

本发明公开了一种基于加权采样的图像特征点匹配的方法。给定一个包含有两幅图像间正确匹配点和不正确匹配点的数据集合，首先用SIFT算法找出两幅图像间的匹配点并构成一个数据集，然后为数据集中的每对匹配点设置一个大于0的权值，再按照权值大小对数据集进行多次采样，用采样到的匹配点来计算基础矩阵，然后根据计算得到的基础矩阵来判断正确的匹配点并增加它们的权重，重复上述的采样过程多次，最后选出那些权值大于一个用户给定的阈值的匹配点。使用本方法对图像的匹配点进行处理具有良好的效果，在给定的匹配点集中含有大量的不正确匹配点的时候，该方法能选出大量的正确匹配点。

说明书

技术领域

本发明涉及三维重建等领域，尤其涉及一种基于加权采样的图像特征点匹配方法。

背景技术

近几年，计算机科学在视频的三维重建等方面取得了很大的进展。人们可以用放置在不同位置的多台摄像机对同一场景进行拍摄，通过对拍摄到的场景进行处理，恢复出整个场景或者场景中某个物体的坐标。从视频或者图像中恢复出物体的三维模型这种方法得到了很大的应用，它被广泛的应用在环境仿真、工业测量、电子商务、特技制作等领域。为了提高重建出来的三维模型的质量，高效率和高质量的特征点匹配是非常有用的。

特征点的检测和匹配在计算机视觉中是一个基础问题，在这个问题上，大量的研究者做了大量的工作。David Lowe在2004年提出了一个著名的算法，即SIFT算法(D.Lowe.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60(2)：91-110)，这个算法可以用来在两幅图像间检测和找到特征点。SIFT算法有尺度不变性，给定两幅相同大小或者不同大小的图片，SIFT算法可以在两幅图像中检测到图像中的特征点和匹配点。但是由于图像噪声的存在，SIFT算法找出的图像匹配点集含有很多不正确的匹配点。因此，需要一个算法来处理SIFT算法找出来的匹配点集，使得处理后的匹配点集合中不包含或者包含有比较少的不正确匹配点。

为了从SIFT算法找出的匹配点结中选出正确的匹配点，研究者们提出了使用极线几何和随机采样的方法，这里面包括了随机采样一致性算法(RANSAC)和LMedS算法等。这些算法的一般模式都是从数据集中随机采样一些样本数据，然后用这些样本数据计算出两幅图像间的极线几何性质，再用两幅图像间的极线几何性质去找出正确的匹配点，随机采样的次数一般都很多。

这里所说的极线几何的性质，主要是指两幅图像间的基础矩阵(R.Hartley，A.Zisserman.Multiple View Geometry in Computer Vision[M].CambridgeUniversity Press，London，2000)。基础矩阵描述了两幅图像间的代数关系，所有的两幅图像间的正确的匹配点都应该符合基础矩阵的关系。常用的计算基础矩阵的方法有8点法(R.Hartley，A.Zisserman.Multiple View Geometry in ComputerVision[M].Cambridge University Press，London，2000)等。在极线几何里，用Sampson Distance(R.Hartley，A.Zisserman.Multiple View Geometry in ComputerVision[M].Cambridge University Press，London，2000)来衡量一对匹配点符合基础矩阵的程度，可以把Sampson Distance看成是一对匹配点满足一个基础矩阵的误差，误差大就说明这对匹配点不符合基础矩阵，因此是一对不正确的匹配点。

现有的随机采样一致性算法(RANSAC)，LMedS等算法的运行结果在很大程度上和数据集中的不正确匹配点的比例有关，实验证明，在数据集中不正确匹配点的比例很高的时候，这些算法产生的结果会把很多的不正确匹配点认为是正确的匹配点选出来。

发明内容

本发明的目的是克服现有技术的不足，提供了一种有效的基于加权采样的图像特征点匹配的方法。

基于加权采样的图像特征点匹配的方法包括以下步骤：

1)给定对同一个场景在不同角度拍摄的两幅图像，用SIFT算法找到两幅图像中的匹配点，构成一个数据集，数据集中元素是两幅图像间的一对匹配点；

2)为每对匹配点设定一个大于0的权值；

3)按照匹配点的权重随机采样，每次采样8对点，用8点法计算出两幅图像间的基础矩阵F，计算出每对匹配点在这个基础矩阵下的Sampson Distance并组成误差数组记录下来；

4)对步骤3)重复N次，得到N个误差数组，找出N个误差数组中中值最小的误差数组，根据中值最小的误差数组计算出阈值λ，对中值最小的误差数组中Sampson Distance小于阈值λ的匹配点，权重增加一个预先设定好的数值；

5)对步骤3)和步骤4)重复M次，找出那些权重大于用户给定阈值σ的匹配点作为最后的匹配点。

所述用SIFT算法找到两幅图像中的匹配点，构成一个数据集步骤：给定输入的对同一个场景在不同角度拍摄的两幅图像，运用SIFT算法找出两幅图像中的匹配点，并把找到的两幅图像中的匹配点构成一个数据集，数据集中的每个元素就是两幅图像间的一对匹配点。

所述按照匹配点的权重随机采样步骤：随机从数据集中选出一些匹配点，使得权重大的匹配点被选中的概率大，假设数据集中包含有n对匹配点，其中第i对匹配点的权重为w_i，那么，第i对匹配点被选中的概率p_i的计算公式为：

$p_i=\frac{w_i}{\underset{j=1}{\overset{n}{\Sigma }}{w}_j}---1$

实施的算法为：

输入：权重数组

输出：随机采样出的8对点的序号

步骤1：给定包含了每对匹配点的权重数组w，复制这个数组为w’，构造一个空的输出集合output；

步骤2：求出数组w’中所有元素的和$s=\underset{i=1}{\overset{n}{\Sigma }}{w^{\prime }}_i;$

步骤3：生成一个在[0，s]范围内的随机数k，从数组w’中找出下标为j的元素，使得如下公式满足：

$\underset{i=1}{\overset{j}{\Sigma }}{w^{\prime }}_i\ge k$

$\underset{i=1}{\overset{j-1}{\Sigma }}{w^{\prime }}_i<k$

步骤4：把步骤3找出来的下标j添加到输出集合output，并把w’数组中的第j个元素，即w′_j设为0；

步骤5：对步骤2，步骤3和步骤4重复8次；

步骤6：输出output数组。

所述用8点法计算出两幅图像间的基础矩阵F步骤：假设8对匹配点的图像坐标为(x_i，y_i)和(x′_i，y′_i)，首先构造一个矩阵A：

$A=\left(\begin{array}{ccccccccc}{x}_1{x_1}^{\prime }& y_1{x_1}^{\prime }& {x_1}^{\prime }& x_1{y_1}^{\prime }& y_1{y_1}^{\prime }& {y_1}^{\prime }& x_1& y_1& 1\\ .& .& .& .& .& .& .& .& .\\ .& .& .& .& .& .& .& .& .\\ .& .& .& .& .& .& .& .& .\\ x_8{x_8}^{\prime }& y_8{x_8}^{\prime }& {x_8}^{\prime }& x_8{y_8}^{\prime }& y_8{y_8}^{\prime }& {y_8}^{\prime }& x_8& y_8& 1\end{array}\right)$

然后求出一个矩阵f＝(f₁₁ f₁₂ f₁₃ f₂₁ f₂₂ f₂₃ f₃₁ f₃₂ f₃₃)，使得f满足如下等式：

Af＝0

||f||＝1

具体步骤为：对矩阵A进行SVD分解，使得A＝UDV^T，则矩阵f就是矩阵V的第9列，SVD在matlab中有现成的函数可以调用，上述求解矩阵f的过程用以下的matlab代码来表示：

[U，D，V]＝svd(A)；

f＝V(：，9)′；

求出矩阵f后，按照矩阵f构造一个3×3的矩阵F’，使得矩阵F’满足：

$F^{\prime }=\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)$

接着对矩阵F’进行SVD分解，使得F′＝UDV^T，SVD分解后，矩阵D为3×3的对角矩阵，D＝diag(r，s，t)，求出矩阵F＝U·diag(r，s，0)·V^T，矩阵F为基础矩阵。

所述计算出每对匹配点在这个基础矩阵下的Sampson Distance并组成误差数组记录下来步骤：计算出一个基础矩阵F后，为数据集中的每对匹配点计算在基础矩阵F下的Sampson Distance，并组成一个数组，称为误差数组，数组中的第i个元素是数据集中第i对匹配点在基础矩阵F下的Sampson Distance。计算Sampson Distance的公式为：

$D=\frac{{\left(u^{{\prime }^T}\mathrm{Fu}\right)}^2}{{l_1}^2+{l_2}^2+{{l^{\prime }}_1}^2+{{l^{\prime }}_2}^2}$

其中，u和u′为数据集中的一对匹配点，用齐次坐标来表示，即如果一个点的坐标表示为(x，y)，那么这对点的齐次坐标表示为(x，y，1)^T，公式中u为第1幅图像上的匹配点，u′为第2幅图像上的匹配点，l₁和l₂分别是极线l的齐次坐标表示的第一个和第二个元素，l₁和l′₂分别是极线l′的齐次坐标表示的第一个元素和第二个元素。l和l′的计算公式为：

l＝Fu′

l′＝F^Tu

可以看到，l和l′都是一个3×1的矩阵，因此可以取到这两个矩阵的第一个和第二个元素。

所述找出N个误差数组中中值最小的误差数组步骤：一个误差数组的中值被定义为：

$\mathrm{med}=\left(\begin{array}{cc}{a}_{(n+1)/2}& n\mathrm{mod}2=1\\ (a_{n/2}+a_{n/2+1})/2& n\mathrm{mod}2=0\end{array}\right)$

其中，a是排序好的误差数组，a_i是数组中的第i个元素，n是数组中的元素个数，计算出每个误差数组的中值，找出中值最小的误差数组。

所述根据中值最小的误差数组计算出阈值λ步骤：假设数组W是挑选出来的中值最小的误差数组，阈值λ的计算公式如下：

λ＝2*1.4826*(1+5/(n-8))*median{W}

其中，median{W}是数组W的中值，n是数组W中元素的个数。

使用本发明对图像的匹配点进行处理具有良好的效果，在给定的匹配点集中含有大量的不正确匹配点的时候，该方法能选出大量的正确匹配点。

附图说明

图1是本发明待处理的两幅图片；

图2是用SIFT算法找到的两幅图像间的匹配特征点；

图3是本发明输出的两幅图像间的匹配特征点。

具体实施方式

基于加权采样的图像特征点匹配的方法包括以下步骤：

1)给定对同一个场景在不同角度拍摄的两幅图像，用SIFT算法找到两幅图像中的匹配点，构成一个数据集，数据集中元素是两幅图像间的一对匹配点；把这个数据集称为S，由于图像噪声和SIFT算法本身的因素，数据集S中含有很多不正确的匹配点。

2)为每对匹配点设定一个大于0的权值；

为每对匹配点设定一个大于0的权值，即为这个集合构造一个权重数组w，其中数组中的第i个元素是数据集中第i对匹配点的权值，数组中的每个元素都被设为一个固定的数值a，即每对匹配点的权值被设为a，这里a是一个大于0的数字。

3)按照匹配点的权重随机采样，每次采样8对点，用8点法计算出两幅图像间的基础矩阵F，计算出每对匹配点在这个基础矩阵下的Sampson Distance并组成误差数组记录下来；

即用随机采样的方法从数据集中采样8对点，采样的过程中，数据集中每对点被采样到的概率不同，权重大的匹配点被选中的概率大。

4)对步骤3)重复N次，得到N个误差数组，找出N个误差数组中中值最小的误差数组，根据中值最小的误差数组计算出阈值λ，对中值最小的误差数组中Sampson Distance小于阈值λ的匹配点，权重增加一个预先设定好的数值；

即首先对所有的误差数组分别进行排序，并求出这些误差数组的中值，一个误差数组的中值的计算公式为：

$\mathrm{med}=\left(\begin{array}{cc}{a}_{(n+1)/2}& n\mathrm{mod}2=1\\ (a_{n/2}+a_{n/2+1})/2& n\mathrm{mod}2=0\end{array}\right)$

其中，a是排序好的误差数组，a_i是数组中的第i个元素，n是数组中的元素个数。得到所有误差数组的中值后，我们选出误差中值最小的那个数组，把它记为W，我们用如下公式计算阈值：

λ＝2*1.4826*(1+5/(n-8))*median{W}

其中，median{W}是数组W的中值，n是W中元素的个数，也就是数据集S包含的元素个数。求出阈值λ后，我们从数组W中挑出Sampson Distance小于λ那些匹配点，并增加它们的权重，把它们的权重增加一个固定的数值b，即如果在数组W中，第i对匹配点的Sampson Distance小于λ，那么我们增加它的权重，使得w_i＝w_i+b。

5)对步骤3)和步骤4)重复M次，找出那些权重大于用户给定阈值σ的匹配点作为最后的匹配点。

所述用SIFT算法找到两幅图像中的匹配点，构成一个数据集步骤：给定输入的对同一个场景在不同角度拍摄的两幅图像，运用SIFT算法找出两幅图像中的匹配点，并把找到的两幅图像中的匹配点构成一个数据集，数据集中的每个元素就是两幅图像间的一对匹配点。

所述按照匹配点的权重随机采样步骤：随机从数据集中选出一些匹配点，使得权重大的匹配点被选中的概率大，假设数据集中包含有n对匹配点，其中第i对匹配点的权重为w_i，那么，第i对匹配点被选中的概率p_i的计算公式为：

$p_i=\frac{w_i}{\underset{j=1}{\overset{n}{\Sigma }}{w}_j}---1$

实施的算法为：

输入：权重数组

输出：随机采样出的8对点的序号

步骤1：给定包含了每对匹配点的权重数组w，复制这个数组为w’，构造一个空的输出集合output；

步骤2：求出数组w’中所有元素的和$s=\underset{i=1}{\overset{n}{\Sigma }}{w^{\prime }}_i;$

步骤3：生成一个在[0，s]范围内的随机数k，从数组w’中找出下标为j的元素，使得如下公式满足：

$\underset{i=1}{\overset{j}{\Sigma }}{w^{\prime }}_i\ge k$

$\underset{i=1}{\overset{j-1}{\Sigma }}{w^{\prime }}_i<k$

步骤4：把步骤3找出来的下标j添加到输出集合output，并把w’数组中的第j个元素，即w′_j设为0；

步骤5：对步骤2，步骤3和步骤4重复8次；

步骤6：输出output数组。

所述用8点法计算出两幅图像间的基础矩阵F步骤：假设8对匹配点的图像坐标为(x_i，y_i)和(x′_i，y′_i)，首先构造一个矩阵A：

$A=\left(\begin{array}{ccccccccc}{x}_1{x_1}^{\prime }& y_1{x_1}^{\prime }& {x_1}^{\prime }& x_1{y_1}^{\prime }& y_1{y_1}^{\prime }& {y_1}^{\prime }& x_1& y_1& 1\\ .& .& .& .& .& .& .& .& .\\ .& .& .& .& .& .& .& .& .\\ .& .& .& .& .& .& .& .& .\\ x_8{x_8}^{\prime }& y_8{x_8}^{\prime }& {x_8}^{\prime }& x_8{y_8}^{\prime }& y_8{y_8}^{\prime }& {y_8}^{\prime }& x_8& y_8& 1\end{array}\right)$

然后求出一个矩阵f＝(f₁₁ f₁₂ f₁₃ f₂₁ f₂₂ f₂₃ f₃₁ f₃₂ f₃₃)，使得f满足如下等式：

Af＝0

||f||＝1

具体步骤为：对矩阵A进行SVD分解，使得A＝UDV^T，则矩阵f就是矩阵V的第9列，SVD在matlab中有现成的函数可以调用，上述求解矩阵f的过程用以下的matlab代码来表示：

[U，D，V]＝svd(A)；

f＝V(：，9)′；

求出矩阵f后，按照矩阵f构造一个3×3的矩阵F’，使得矩阵F’满足：

$F^{\prime }=\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)$

接着对矩阵F’进行SVD分解，使得F′＝UDV^T，SVD分解后，矩阵D为3×3的对角矩阵，D＝diag(r，s，t)，求出矩阵F＝U·diag(r，s，0)·V^T，矩阵F为基础矩阵。

所述计算出每对匹配点在这个基础矩阵下的Sampson Distance并组成误差数组记录下来步骤：计算出一个基础矩阵F后，为数据集中的每对匹配点计算在基础矩阵F下的Sampson Distance，并组成一个数组，称为误差数组，数组中的第i个元素是数据集中第i对匹配点在基础矩阵F下的Sampson Distance。计算Sampson Distance的公式为：

$D=\frac{{\left(u^{{\prime }^T}\mathrm{Fu}\right)}^2}{{l_1}^2+{l_2}^2+{{l^{\prime }}_1}^2+{{l^{\prime }}_2}^2}$

其中，u和u′为数据集中的一对匹配点，用齐次坐标来表示，即如果一个点的坐标表示为(x，y)，那么这对点的齐次坐标表示为(x，y，1)^T，公式中u为第1幅图像上的匹配点，u′为第2幅图像上的匹配点，l₁和l₂分别是极线l的齐次坐标表示的第一个和第二个元素，l₁和l′₂分别是极线l′的齐次坐标表示的第一个元素和第二个元素。l和l′的计算公式为：

l＝Fu′

l′＝F^Tu

可以看到，l和l′都是一个3×1的矩阵，因此可以取到这两个矩阵的第一个和第二个元素。

所述找出N个误差数组中中值最小的误差数组步骤：一个误差数组的中值被定义为：

$\mathrm{med}=\left(\begin{array}{cc}{a}_{(n+1)/2}& n\mathrm{mod}2=1\\ (a_{n/2}+a_{n/2+1})/2& n\mathrm{mod}2=0\end{array}\right)$

其中，a是排序好的误差数组，a_i是数组中的第i个元素，n是数组中的元素个数，计算出每个误差数组的中值，找出中值最小的误差数组。

所述根据中值最小的误差数组计算出阈值λ步骤：假设数组W是挑选出来的中值最小的误差数组，阈值λ的计算公式如下：

λ＝2*1.4826*(1+5/(n-8))*median{W}

其中，median{W}是数组W的中值，n是数组W中元素的个数。

实施例

如附图1所示，图中左右两幅图像分别是对同一个场景在两个不同角度进行拍摄得到的两幅图像，其中第二幅图像是相机在拍摄第一幅图像的位置水平转过一个角度拍摄的，因此，这两幅图像上的匹配点应该在一条水平线上。

首先，用SIFT算法找出附图1中两幅图片的匹配点，并把这些匹配点组成集合S，集合中的每个元素是附图1中两幅图片的一对匹配点。在附图1中把集合S每对匹配点用线段连起来，就得到了附图2，也就是说，在附图2中，每条线段所连的两个点是集合S中的一对匹配点，可以看到，在附图2中，有很多线段是不水平的，由于附图1中的两幅图像是相机通过水平转过一个角度拍摄的，因此，两幅图像中的匹配点应该在一条水平线上，因此，附图2中那些不水平的线段连接的匹配点都是不正确的，也就是说，集合S中含有很多不正确的匹配点。

得到了集合S后，我们接着对这个数据集进行如下处理：

1)首先为集合S中的每对匹配点设定权值为a。

2)按照匹配点的权值大小对它们随机采样，每次采样的过程中，权值大的匹配点被采样到的概率也大。每次采样8对点，采样到8对点后，用这8对点求出两幅图像间的基础矩阵F，并求出数据集S里面所有匹配点对在这个基础矩阵下的Sampson Distance并组成误差数组保存下来，因此每次采样的过程，我们能得到1个误差数组。

3)重复步骤2)N次后，我们得到N个误差数组，找出中值最小的那个误差数组，并算出阈值λ，从这个误差数组中找出那些Sampson Distance小于λ的匹配点对，把它们的权值增加b，其中b是一个大于0的数字。

4)重复步骤2)和步骤3)M次，然后从误差数组中选出那些权值大于一个用户给定阈值σ的匹配点作为输出。

实验结果如附图3所示，经过本方法处理后，可以看到附图3中每条线段连接的点对都处于一条水平线上，因此结果比附图2中的结果有很大改进。