论文部分内容阅读
摘要：本文采用SIFT算法进行特征点检测，运用Kd-tree构造数据索引空间，采用最近邻检测算法在其中进行数据的查询，实现待匹配图像特征点和参考图像特征点的匹配。由于SIFT算法描述的特征点具有旋转不变性、尺度不变性等优良特性，借助这些特征点对，能够实现测量系统中的立体匹配。本文对获取的同一场景的两幅图像进行处理，用上述方法进行立体匹配，实现了较好的匹配效果，达到了接近实时性的匹配速度。
关键词：SIFT算法；Kd-tree；最近邻检测；立体匹配
中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）15-0199-03
图像匹配是双目视觉测量系统中的关键技术。基于图像特征的匹配方法是最常用的匹配方法，该方法首先提取图像的局部特征（区域、线、点），然后计算两幅图像特征的相关性来确定它们之间的最佳匹配，再通过反映两幅图像关系的变换矩阵，将待匹配图像投影到参考图像中，实现两幅图像之间的匹配。基于图像特征的匹配方法研究要从Moravec[1]利用角点检测实现立体匹配开始。Harris角点检测在有效地运动跟踪方面具有重要的研究价值。Schmid[2]和Mohr研究表明不变尺度特征匹配能够扩展应用到一般的图像识别问题。由于Harris角点描述符对图像的尺度比较敏感，用于不同尺度的图像之间匹配，效果不是很理想。1999年David G.Lowe总结了已有的基于不变量技术的特征检测方法，提出了一种基于图像局部特征的描述算子，SIFT特征描述算子[3]。该算子具有多种良好的不变特性，对图像的旋转、缩放、尺度空间变换和仿射变换等均保持不变性，此外，该算法将特征检测、特征矢量生成、特征匹配搜索等步骤完整的结合，并进行进一步优化处理，达到了接近实时的运算速度，实现了良好的匹配效果。
本文利用SIFT算法对图像中的特征点进行检测，并利用基于Kd-tree的最近邻算法进行特征点的匹配，最后依赖于已有的特征点匹配对，实现双目视觉立体匹配。
1.2 SIFT特征描述子及特征矢量
SIFT描述子是一种用于特征检测的特征描述子，通过量化描述图像局部特征，客观地反映特征点附近局部区域内图像的分布情况。为了实现图像的旋转不变性，我们通过图像的梯度参数，求取特征点附近局部结构的稳定方向。对于已经检测到的特征点，特征点尺度值是确定的，我们可以得到最接近该值的高斯图像：
1.3 图像特征点匹配
对捕获的同一场景两幅图像，如果两个特征点描述矢量之间相距较近，就认为这两个特征点对应于三维场景中的同一位置；反之，则处于不同的位置。特征点匹配技术就是从对应同一场景的两幅图像特征点集合中，找到两两距离最近的特征点，实现特征点一对一匹配。
特征匹配常采用线性扫描法，就是将特征点和查询点逐一进行距离比较，选择距离最小的点，但是该检索方法搜索效率比较低。本文采用Kd-tree[5]的数据结构，将整个数据空间划分成小空间，逐级展开搜索，搜寻最近邻点。Kd-tree本质上就是二叉树，每个节点表述一个空间范围。构建流程如下：
（1）分析数据点数据，展开kd-tree；
（2）找到分割超面，确定其垂直方向轴序号，计算对应维度上的数据方差；
（4）分割数据。维数小于阈值的，其对应的特征点放在右子树空间；否则放在左子树空间；
（5）分别展开左子树、右子树，重复上述步骤（2）、（3）、（4），将空间和数据集进一步细化，直至空间中只包含一个特征数据点。
在kd-tree中进行数据的查询是为了检索kd-tree数据集中与查询点距离最近的数据点。按照二叉树结构展开搜索，沿着搜索路径，找到最近邻的近似点，也就是包含查询点的叶子节点。但是这样找到的叶子节点不一定就是最近邻点，最近邻点肯定距离查询点更近，也就是说，最近邻点一定在以查询点为圆心，通过叶子节点为半径的圆域内。这就需要我们沿搜索路径回溯操作，看是否存在某一数据点，距离查询点更近。若存在，就用新查到的数据点代替叶子节点，反之若不存在，则认为已经找到的叶子节点就是最近邻点，从而完成特征点的匹配。
2 立体匹配
立体匹配[6]是指对参考图像中的任意像素，在待匹配图像中找到与之相对应的像素点的过程，即找到空间中任一场景点在两幅图像中对应的像素点。这些像素点有可能是已经检测出的特征点，也有可能只是普通的像素点。由于使用SIFT算法检测到的特征点具有多种不变特性，在图像中处于相对稳定的区域，我们可以建立待匹配像素点和周围特征点的关系，来实现像素点之间的匹配。
本文在特征匹配的基础上，研究了普通像素点和特征点之间的关系，实现了图像的立体匹配。算法具体流程如下：
（1）在参考图像中，从上往下，从左至右对图像特征点依次排序，并求取各特征点到参考像素点之间的欧氏距离；
（2）比较求得的欧氏距离，选择其中距离最小的特征点为最近特征点，如存在距离相同的特征点，选择序号最小的特征点为最近特征点；同理，选择距离次小的特征点为次近特征点；
（3）从匹配好的特征点对中，找到最近特征点和次近特征点，并从已经存在的匹配对集合中，找到待匹配图像中与之对应的最近特征点和次近特征点。
（4）在参考图像中，建立两个特征点与参考像素点之间的函数关系。运用该函数关系求出待匹配图像中对应的像素点。
对于立体匹配，除了借助特征点匹配对，立体匹配本身还具有一些约束条件：1）唯一性约束。每个参考像素点存在且只存在唯一的待匹配像素点与之相匹配；2）顺序一致性约束。同一扫描线上的两个像素点在参考图像和待匹配图像上具有相同位置次序；3）一致性约束。两幅图像中，对于未遮挡的相同场景，对应的像素点具有相同的视差。运用立体匹配条件，可以进一步优化我们已经得到的立体匹配点对，实现更好的匹配效果。
关键词：SIFT算法；Kd-tree；最近邻检测；立体匹配
中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）15-0199-03
图像匹配是双目视觉测量系统中的关键技术。基于图像特征的匹配方法是最常用的匹配方法，该方法首先提取图像的局部特征（区域、线、点），然后计算两幅图像特征的相关性来确定它们之间的最佳匹配，再通过反映两幅图像关系的变换矩阵，将待匹配图像投影到参考图像中，实现两幅图像之间的匹配。基于图像特征的匹配方法研究要从Moravec[1]利用角点检测实现立体匹配开始。Harris角点检测在有效地运动跟踪方面具有重要的研究价值。Schmid[2]和Mohr研究表明不变尺度特征匹配能够扩展应用到一般的图像识别问题。由于Harris角点描述符对图像的尺度比较敏感，用于不同尺度的图像之间匹配，效果不是很理想。1999年David G.Lowe总结了已有的基于不变量技术的特征检测方法，提出了一种基于图像局部特征的描述算子，SIFT特征描述算子[3]。该算子具有多种良好的不变特性，对图像的旋转、缩放、尺度空间变换和仿射变换等均保持不变性，此外，该算法将特征检测、特征矢量生成、特征匹配搜索等步骤完整的结合，并进行进一步优化处理，达到了接近实时的运算速度，实现了良好的匹配效果。
本文利用SIFT算法对图像中的特征点进行检测，并利用基于Kd-tree的最近邻算法进行特征点的匹配，最后依赖于已有的特征点匹配对，实现双目视觉立体匹配。
1.2 SIFT特征描述子及特征矢量
SIFT描述子是一种用于特征检测的特征描述子，通过量化描述图像局部特征，客观地反映特征点附近局部区域内图像的分布情况。为了实现图像的旋转不变性，我们通过图像的梯度参数，求取特征点附近局部结构的稳定方向。对于已经检测到的特征点，特征点尺度值是确定的，我们可以得到最接近该值的高斯图像：
1.3 图像特征点匹配
对捕获的同一场景两幅图像，如果两个特征点描述矢量之间相距较近，就认为这两个特征点对应于三维场景中的同一位置；反之，则处于不同的位置。特征点匹配技术就是从对应同一场景的两幅图像特征点集合中，找到两两距离最近的特征点，实现特征点一对一匹配。
特征匹配常采用线性扫描法，就是将特征点和查询点逐一进行距离比较，选择距离最小的点，但是该检索方法搜索效率比较低。本文采用Kd-tree[5]的数据结构，将整个数据空间划分成小空间，逐级展开搜索，搜寻最近邻点。Kd-tree本质上就是二叉树，每个节点表述一个空间范围。构建流程如下：
（1）分析数据点数据，展开kd-tree；
（2）找到分割超面，确定其垂直方向轴序号，计算对应维度上的数据方差；
（4）分割数据。维数小于阈值的，其对应的特征点放在右子树空间；否则放在左子树空间；
（5）分别展开左子树、右子树，重复上述步骤（2）、（3）、（4），将空间和数据集进一步细化，直至空间中只包含一个特征数据点。
在kd-tree中进行数据的查询是为了检索kd-tree数据集中与查询点距离最近的数据点。按照二叉树结构展开搜索，沿着搜索路径，找到最近邻的近似点，也就是包含查询点的叶子节点。但是这样找到的叶子节点不一定就是最近邻点，最近邻点肯定距离查询点更近，也就是说，最近邻点一定在以查询点为圆心，通过叶子节点为半径的圆域内。这就需要我们沿搜索路径回溯操作，看是否存在某一数据点，距离查询点更近。若存在，就用新查到的数据点代替叶子节点，反之若不存在，则认为已经找到的叶子节点就是最近邻点，从而完成特征点的匹配。
2 立体匹配
立体匹配[6]是指对参考图像中的任意像素，在待匹配图像中找到与之相对应的像素点的过程，即找到空间中任一场景点在两幅图像中对应的像素点。这些像素点有可能是已经检测出的特征点，也有可能只是普通的像素点。由于使用SIFT算法检测到的特征点具有多种不变特性，在图像中处于相对稳定的区域，我们可以建立待匹配像素点和周围特征点的关系，来实现像素点之间的匹配。
本文在特征匹配的基础上，研究了普通像素点和特征点之间的关系，实现了图像的立体匹配。算法具体流程如下：
（1）在参考图像中，从上往下，从左至右对图像特征点依次排序，并求取各特征点到参考像素点之间的欧氏距离；
（2）比较求得的欧氏距离，选择其中距离最小的特征点为最近特征点，如存在距离相同的特征点，选择序号最小的特征点为最近特征点；同理，选择距离次小的特征点为次近特征点；
（3）从匹配好的特征点对中，找到最近特征点和次近特征点，并从已经存在的匹配对集合中，找到待匹配图像中与之对应的最近特征点和次近特征点。
（4）在参考图像中，建立两个特征点与参考像素点之间的函数关系。运用该函数关系求出待匹配图像中对应的像素点。
对于立体匹配，除了借助特征点匹配对，立体匹配本身还具有一些约束条件：1）唯一性约束。每个参考像素点存在且只存在唯一的待匹配像素点与之相匹配；2）顺序一致性约束。同一扫描线上的两个像素点在参考图像和待匹配图像上具有相同位置次序；3）一致性约束。两幅图像中，对于未遮挡的相同场景，对应的像素点具有相同的视差。运用立体匹配条件，可以进一步优化我们已经得到的立体匹配点对，实现更好的匹配效果。