一种基于三视图几何中三点线性关系的任意点匹配算法

摘要

本发明公开了一种基于三视图几何中三点线性关系的任意点匹配算法。本发明在两视图极线约束的基础上，添加三视图几何信息，利用三视图位置信息和像素信息同时约束匹配点对；并在三视图几何关系实现上通过迭代的方式以克服微小误差对最终结果的影响。

说明书

技术领域：

本发明属于图像处理与模式识别领域中的立体匹配技术领域，具体涉及一种基于三视图几何中三点线性关系的任意点匹配算法。 

背景技术：

在立体匹配领域中，立体图像由在不同位置不同视角的两摄像机对同一场景拍摄得到。通过在两图像中查找的任意点对位置信息得到点对的视差估计，进而可以根据视差获取深度信息。寻找任意点对是立体匹配技术的关键步骤，目前立体匹配技术主要分为全局匹配算法和局部匹配算法。全局匹配算法包括：基于图割理论的匹配算法、置信传播算法、SGBM等，主要通过构建能量函数E(d)，最小化E(d)寻找点坐标。局部匹配算法主要通过各种相容性在点坐标的局部邻域寻找相似性最高的点局部邻域，局部邻域的中心点即为匹配点坐标。相容性主要有：亮度信息、梯度信息、区域互相关信息、区域互信息及多视图中的几何信息等。 

目前立体匹配中的局部匹配算法中主要考虑两视图中的对极几何信息和像素信息来寻找点对（通过在右视图极线上寻找左视图中点P的对应点P'，将二维空间降到一维空间上寻找）；而三视图几何主要用于摄像机标定和三维重构中，虽然三视图几何也有被用于立体匹配的方法，但都非常容易受到噪声的影响而使得误差较大。 

发明内容：

本发明的目的在于克服现有技术的不足，提供一种基于三视图几何中三点线 性关系的任意点匹配算法。 

为了解决背景技术所存在的问题，本发明采用以下技术方案： 

一种基于三视图几何中三点线性关系的任意点匹配算法,它包括如下步骤： 

步骤一：读取图像：读取由不同视角不同位置的相机对同一场景拍摄得到的图像1、2、3；并在图像2中选择需要匹配的点坐标x'； 

步骤二：获取候选点集合：根据两视图几何中的对极几何模型确定点x'在图像1和图像3中的候选搜索路径L1和L3；在路径L1和L3中，以一个像素为步阶，逐步获取每一个像素点坐标，将其分别加入候选点集PV1,PV3中； 

步骤三：三视图三点线性关系匹配：构建矩阵Q，其中选择第一个矩阵的三行、第二个矩阵的前两行和第三个矩阵的前两行；选取点集PV1和PV3中各任一点，加上鼠标选点x'及投影矩阵组成矩阵Q；计算矩阵Q的行列式；理论上，三点对组成的矩阵Q的行列式值应严格等于0，由于实际参与计算的摄像机投影矩阵不可避免的存在误差，使得在实际实现上不会正好等于0；当三点坐标存在1个像素左右的误差时，矩阵Q的行列式的值能够达到10¹⁰左右； 

步骤四：归一化互相关匹配：逐步选取第3步保留下来的点集中的点对，按照归一化互相关系数计算公式，计算每个点坐标邻域内像素与图2点x'邻域内像素间的归一化互相关匹配值，邻域宽度按照经验选为20个像素； 

步骤五：得出最佳匹配点：在步骤四的结果中，若某点对的互相关匹配值和最大，则该点对即为最终匹配的点x和x''。 

进一步的，所述的步骤三中构建矩阵Q需要根据下列公式： 

用一个方程描述空间点X在三幅图像上的投影为： 

$\left(\begin{array}{cccc}A& x& & \\ B& & x^{\prime }& \\ C& & & x^{\prime \prime }\end{array}\right)\left(\begin{array}{c}X\\ -k\\ {-k}^{\prime }\\ {-k}^{\prime \prime }\end{array}\right)=O$

把这个矩阵记为Q，它有9行和7列，根据这个方程组有一个非零解，可以退出它的秩最多为6，因此它的任何7*7的子式为零，这个事实确立了点x,x'和x''的坐标之间存在着三线性关系； 

其中一种组成该7*7的子式为： 

从矩阵A中选三行，而从另外两个矩阵B和C中各选两行，得如下等式： 

$\det \left(\begin{array}{cccc}A& x& & \\ b^j& & x^{\prime j}& \\ b^l& & x^{\prime l}& \\ c^k& & & x^{\prime \prime k}\\ c^m& & & x^{\prime \prime m}\end{array}\right)=0$

进一步的，所述的步骤三中通过迭代的方式寻找行列式值过零点的位置，具体实施步骤如下： 

（1）将投影矩阵和点x作为已知量，x'¹,x'²,x''¹,x''²为未知量，公式二可表示为：f(x'¹,x'²,x''¹,x''²)＝0，将点集PV1和PV2中选择的两点作为迭代的起点 

（2）计算每个未知量的偏导数 

（3）寻找偏导数最大的未知量，以0.1个像素为步阶，计算新的行列式值 

（4）重复第二步和第三步，直到行列式值由正变负，或由负变正。即此时行列式值通过零点 

（5）将过零点状态下的各未知量的值作为实际匹配点对 

（6）计算起点与第5步得到的点坐标的距离d 

（7）若d小于1个像素，则认为该起点为满足三线性关系的点对。即从PV1和PV3中选择的两点与点x'对应着空间中同一点，将这两个点保留下来，作为后续归一化互相关匹配的候选点； 

经过上述7个步骤，将点集PV1和PV3中在位置关系上不可能是同一点对的点删掉，保留下属于同一点对的多组点对。 

本发明对比现有技术有如下的有益效果：本发明在两视图极线约束的基础上，添加三视图几何信息，利用三视图位置信息和像素信息同时约束匹配点对；并在三视图几何关系实现上通过迭代的方式以克服微小误差对最终结果的影响 

附图说明：

图1为本发明方法流程图。 

图2为三视图几何模型 

具体实施方式：

下面结合附图，对本发明作进一步详细描述： 

图1为本发明方法流程图。 

1.读取图像：读取由不同视角不同位置的相机对同一场景拍摄得到的图像1、2、3；并在图像2中选择需要匹配的点坐标x' 

2.获取候选点集合：根据两视图几何中的对极几何模型确定点x'在图像1和图像3中的候选搜索路径L1和L3。在路径L1和L3中，以一个像素为步阶，逐步获取每一个像素点坐标，将其分别加入候选点集PV1,PV3中 

3.三视图三点线性关系匹配：根据“原理说明”部分的第二个公式，构建矩阵Q，其中选择第一个矩阵的三行、第二个矩阵的前两行和第三个矩阵的前两行。选取点集PV1和PV3中各任一点，加上鼠标选点x'及投影矩阵组成矩阵Q；计算矩阵Q的行列式；理论上，三点对组成的矩阵Q的行列式值应严格等于0，由于实际参与计算的摄像机投影矩阵不可避免的存在误差，使得在实际实现上不会正好等于0。在本文的应用中，当三点坐标存在1个像素左右的误差时，矩阵Q的行列式的值能够达到10¹⁰左右。这个非常大的值并不代表参与计算的三点坐标与实际匹配点对坐标的差值非常大。 

在本文中，我们通过迭代的方式寻找行列式值过零点的位置，具体实施如下： 

1)将投影矩阵和点x作为已知量，x'¹,x'²,x''¹,x''²为未知量，公式二可表示为：f(x'¹,x'²,x''¹,x''²)＝0，将点集PV1和PV2中选择的两点作为迭代的起点 

2)计算每个未知量的偏导数 

3)寻找偏导数最大的未知量，以0.1个像素为步阶，计算新的行列式值 

4)重复第二步和第三步，直到行列式值由正变负，或由负变正。即此时行列式值通过零点 

5)将过零点状态下的各未知量的值作为实际匹配点对 

6)计算起点与第5步得到的点坐标的距离d 

7)若d小于1个像素，则认为该起点为满足三线性关系的点对。即从PV1 和PV3中选择的两点与点x'对应着空间中同一点，将这两个点保留下来，作为后续归一化互相关匹配的候选点。 

经过上述7个步骤，将点集PV1和PV3中在位置关系上不可能是同一点对的 

点删掉，保留下属于同一点对的多组点对。 

4.归一化互相关匹配：逐步选取第3步保留下来的点集中的点对，按照归一化互相关系数计算公式，计算每个点坐标邻域内像素与图2点x'邻域内像素间的归一化互相关匹配值，邻域宽度按照经验选为20个像素。 

5.得出最佳匹配点：在第4步结果中，若某点对的互相关匹配值和最大，则该点对即为最终匹配的点x和x''。 

原理说明 

设x,x',x''为一组跨三视图的点对应。令三个摄像机矩阵分别为：A,B,C，且c^j为矩阵C的第j行，三视图几何模型如图2所示。 

我们可以用一个方程描述空间点X在三幅图像上的投影为： 

$\left(\begin{array}{cccc}A& x& & \\ B& & x^{\prime }& \\ C& & & x^{\prime \prime }\end{array}\right)\left(\begin{array}{c}X\\ -k\\ {-k}^{\prime }\\ {-k}^{\prime \prime }\end{array}\right)=O$

把这个矩阵记为Q，它有9行和7列。根据这个方程组有一个非零解，可以退出它的秩最多为6。因此它的任何7*7的子式为零，这个事实确立了点x,x'和x''的坐标之间存在着三线性关系。 

其中一种组成该7*7的子式为： 

从矩阵A中选三行，而从另外两个矩阵B和C中各选两行，得如下等式： 

上式表明： 

$\det \left(\begin{array}{cccc}A& x& & \\ b^j& & x^{\prime j}& \\ b^l& & x^{\prime l}& \\ c^k& & & x^{\prime \prime k}\\ c^m& & & x^{\prime \prime m}\end{array}\right)=0$

对于空间中同一空间点X的三图像点投影x,x',x''，及对应的摄像机矩阵A,B,C，按照上式组建得到矩阵Q。矩阵Q满足det(Q)＝0，即矩阵的行列式值为 0。 

需要理解到的是：以上所述仅是本发明的优选实施方式，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以作出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。