一种改进的SURF快速匹配方法

1.一种改进的SURF快速匹配方法，步骤如下：
1)求取初始图像的积分图像和Hessian矩阵的行列式
对需要进行匹配的初始图像遍历求取初始图像的积分图像，并求取图像上每个点的Hessian矩阵的行列式；
2)建立尺度空间金字塔并进行特征点的定位
为使SURF算法具有尺度不变性，必须建立尺度空间金字塔，保持图像大小不变，通过改变盒式滤波器的模板大小来建立尺度图像金字塔，具体构建方法为：图像尺度空间金字塔分四层，对每一层进行四次滤波，第1层第一次滤波模板大小是给定的，为9*9，第1层中相邻的模板尺寸相差6个像素，即第1层中第一至四次滤波模板大小分别是9*9、15*15、
21*21和27*27；第2层中相邻的滤波模板大小相差12个像素，第3层中相邻的滤波模板大小相差24个像素，第4层中相邻的滤波模板大小相差48个像素，每一层的第一个模板尺寸等于前一层的第二个模板的尺寸，故第2层中第一至四次滤波模板大小分别是15*15、
27*27、39*39、51*51，第3层中第一至四次滤波模板大小分别是27*27、51*51、75*75、
99*99，第4层中第一至四次滤波模板大小分别是51*51、99*99、147*147、195*195，每次滤波对应的近似尺度可由公式 计算，其中σapprox表示尺度；特征点
定位过程：为Hessian矩阵响应值设定一个阈值，所有小于这个阈值的点都被去除，然后通过非极大值抑制将那些比其临近层及本层尺度周围的点的响应值都大或都小的点选为特征点，最后拟合三维二次函数精确确定特征点的位置和尺度；
3)通过Haar小波确定特征点的主方向
在以特征点为圆心，6σ为半径的圆形邻域里，用边长为4σ的Haar小波模板求X和Y两个方向的Haar小波响应，并用标准差为2σ的高斯函数对滤波后的区域加权，而后以特征点为中心，用一个圆心角为π/3的扇形在圆形邻域内扫描一周，计算该扇形所扫描的每个π/3角度内包括的图像点的Haar小波响应总和，取其中最大响应的方向为该特征点的主方向，其中σ为特征点所在的尺度值，X和Y是圆形邻域所处的平面直角坐标系中的两个方向；
4)进行特征点的分类
将检测到的特征点在其相应尺度上按其主方向旋转，将特征点的主方向作为平面直角坐标系xoy中的X轴，然后以特征点为圆心，以其所在尺度σ为半径做一圆，坐标轴将此圆形领域划分为四个区域，分别为平面直角坐标系xoy的四个象限中的像素区域，分别计算各象限中像素区域元素的像素和∑1，∑2，∑3，∑4，然后计算第一象限中的像素和与第三象限中的像素和的差值∑13，第二象限中的像素和与第四象限中的像素和的差值∑24，最后根据差值形成一个两维的特征向量τ1，τ2，如下式所示：
5)形成特征描述向量
将特征点的主方向作为平面直角坐标系xoy中的一个轴，以特征点为原点，选取大小为20σ×20σ的矩形邻域，然后将其平均分成4×4个子区域，即形成大小为5σ×5σ的
16个子区域，用窗口尺寸为2σ的Haar小波对16个子区域进行滤波，Haar小波窗口在子区域内自上而下均匀扫描25次，得到25组x方向和y方向上的响应值dx、dy，再用标准差为3.3σ的高斯函数对dx，dy进行加权，统计子区域内的响应值dx、dy的和∑dx、∑dy以及其绝对值的和∑|dx|，∑|dy|的值，形成子区域内的特征向量，将4×4个子区域内的特征向量组合形成64维的向量，加上步骤4)得到的两维向量τ1，τ2，共同组成新的66维向量v，即 对此66维向量进行归一化处理，得到了特征点
的改进的SURF特征描述子；
6)进行特征匹配
两维向量的特征向量τ1，τ2组合为00,01,10,11四组，用基于BBF搜索方法的最近邻匹配算法来完成对目标的检测和识别，对特征向量进行相似性测量，以两个特征向量的欧氏距离作为特征相似的判别标准，设两幅图像I1和I2的新的SURF特征向量集分别为V1＝{v11,v12,...,v1m}，V2＝{v21,v22,...,v2n}，其中m,n分别是两图像上SURF特征点的个数，计算相似特征向量的方法如下式：
dis(v1i,v2j)表示两个特征集中两个特征向量的欧式距离，其中V2中第j0个向量与V1中第i个向量的欧氏距离最小，用dis(j0)表示；V2中第j1个向量与V1中第i个向量的欧氏距离次小，用dis(j1)表示，R为dis(j0)与dis(j1)之比值，设定阈值R0，当R>R0时，特征向量匹配不成功，反之则两向量为匹配向量对。

一种改进的SURF快速匹配方法\n技术领域\n[0001] 本发明涉及数字图像处理技术领域，具体涉及一种改进的SURF快速匹配方法。\n背景技术\n[0002] 在图像处理与机器视觉中，局部图像特征的描述与侦测可以用来帮助辨识物体，因此对物体的局部特征提取具有重要意义。\n[0003] Herbert Bay等人于2006年在文章“SURF:Speeded Up Robust Features[J].Computer Vision and Image Understanding(CVIU),2008,110(3):346-359.”中提出了SURF算法，SURF算法就是一种局部特征描述算法，具有尺度不变性等优点。但是在基于视觉的目标识别过程中，最关心的问题是识别的准确度和是否能实时处理。由于SURF算法特征匹配比较需要对一幅图像上每一个选定的特征点都要与另一幅图像上所有的特征点一一进行匹配，所以耗时仍然过高，要达到特征之间的实时匹配也显得吃力。并且由于误匹配导致匹配的准确率下降。\n(三)发明内容\n[0004] 本发明的目的就是为了解决经典SURF算法仍然耗时过高准确率降低的问题，提供了一种改进的SURF快速匹配方法,该方法可以较明显提高经典SURF算法的速度与精度。\n[0005] 为了实现上述目的，本发明采用如下技术方案:\n[0006] 一种改进的SURF快速匹配方法，步骤如下：\n[0007] 1)求取初始图像的积分图像和Hessian矩阵的行列式\n[0008] 对需要进行匹配的初始图像遍历求取初始图像的积分图像，并求取图像上每个点的Hessian矩阵的行列式；\n[0009] 2)建立尺度空间金字塔并进行特征点的定位\n[0010] 为使SURF算法具有尺度不变性，必须建立尺度空间金字塔，保持图像大小不变，通过改变盒式滤波器的模板大小来建立尺度图像金字塔，具体构建方法为：图像尺度空间金字塔分四层，对每一层进行四次滤波，第1层第一次滤波模板大小是给定的，为9*9，第\n1层中相邻的模板尺寸相差6个像素，即第1层中第一至四次滤波模板大小分别是9*9、\n15*15、21*21和27*27；第2层中相邻的滤波模板大小相差12个像素，第3层中相邻的滤波模板大小相差24个像素，第4层中相邻的滤波模板大小相差48个像素，每一层的第一个模板尺寸等于前一层的第二个模板的尺寸，故第2层中第一至四次滤波模板大小分别是15*15、27*27、39*39、51*51，第3层中第一至四次滤波模板大小分别是27*27、51*51、\n75*75、99*99，第4层中第一至四次滤波模板大小分别是51*51、99*99、147*147、195*195，每次滤波对应的近似尺度可由公式 计算，其中σapprox表示尺度；\n特征点定位过程：为Hessian矩阵响应值设定一个阈值，所有小于这个阈值的点都被去除，然后通过非极大值抑制将那些比其临近层及本层尺度周围的点的响应值都大或都小的点选为特征点，最后拟合三维二次函数精确确定特征点的位置和尺度；\n[0011] 3)通过Haar小波确定特征点的主方向\n[0012] 在以特征点为圆心，6σ为半径的圆形邻域里，用边长为4σ的Haar小波模板求X和Y两个方向的Haar小波响应，并用标准差为2σ的高斯函数对滤波后的区域加权，而后以特征点为中心，用一个圆心角为π/3的扇形在圆形邻域内扫描一周，计算该扇形所扫描的每个π/3角度内包括的图像点的Haar小波响应总和，取其中最大响应的方向为该特征点的主方向，其中σ为特征点所在的尺度值，X和Y是圆形邻域所处的平面直角坐标系中的两个方向；\n[0013] 4)进行特征点的分类\n[0014] 将检测到的特征点在其相应尺度上按其主方向旋转，将特征点的主方向作为平面直角坐标系xoy中的X轴，然后以特征点为圆心，以其所在尺度σ为半径做一圆，坐标轴将此圆形领域划分为四个区域，分别为平面直角坐标系xoy的四个象限中的像素区域，分别计算各象限中像素区域元素的像素和∑1，∑2，∑3，∑4，然后计算第一象限中的像素和与第三象限中的像素和的差值∑13，第二象限中的像素和与第四象限中的像素和的差值∑24，最后根据差值形成一个两维的特征向量τ1，τ2，如下式所示：\n[0015] \n[0016] 5)形成特征描述向量\n[0017] 将特征点的主方向作为平面直角坐标系xoy中的一个轴，以特征点为原点，选取大小为20σ×20σ的矩形邻域，然后将其平均分成4×4个子区域，即形成大小为5σ×5σ的16个子区域，用窗口尺寸为2σ的Haar小波对16个子区域进行滤波，Haar小波窗口在子区域内自上而下均匀扫描25次，得到25组x方向和y方向上的响应值dx、dy，再用标准差为3.3σ的高斯函数对dx，dy进行加权，统计子区域内的响应值dx、dy的和∑dx、∑dy以及其绝对值的和∑|dx|，∑|dy|的值，形成子区域内的特征向量，将4×4个子区域内的特征向量组合形成64维的向量，加上步骤4)得到的两维向量τ1，τ2，共同组成新的66维向量v，即v＝(τ1,τ2,∑dx,∑|dx|,∑dy,∑|dy|)，对此66维向量进行归一化处理，得到了特征点的改进的SURF特征描述子；\n[0018] 6)进行特征匹配\n[0019] 两维向量的特征向量τ1，τ2组合为00,01,10,11四组，用基于BBF搜索方法的最近邻匹配算法来完成对目标的检测和识别，对特征向量进行相似性测量，以两个特征向量的欧氏距离作为特征相似的判别标准，设两幅图像I1和I2的新的SURF特征向量集分别为V1＝{v11,v12,...,v1m}，V2＝{v21,v22,...,v2n}，其中m,n分别是两图像上SURF特征点的个数，计算相似特征向量的方法如下式：\n[0020] \n[0021] \n[0022] \n[0023] dis(v1i,v2j)表示两个特征集中两个特征向量的欧式距离，其中V2中第j0个向量与V1中第i个向量的欧氏距离最小，用dis(j0)表示；V2中第j1个向量与V1中第i个向量的欧氏距离次小，用dis(j1)表示，R为dis(j0)与dis(j1)之比值，设定阈值R0，当R>R0时，特征向量匹配不成功，反之则两向量为匹配向量对。\n[0024] 本发明方法首先利用图像的Hessian矩阵进行极值点的检测，在确定了极值点之后利用Haar小波对图像进行计算得到特征点主方向和64维特征描述子。最后结合特征点的分类思想，根据特征点主方向邻域内像素和之间的差值形成一个2维的特征向量，与SURF的特征描述子相结合形成66维特征向量，以达到提高匹配速度的目的。在匹配时，首先对特征点按照其特征向量的前两维进行粗匹配，从而将特征点分成4组，然后将四组特征点进行分别组内匹配。\n[0025] 本发明针对SURF算法对一幅图像上每一个选定的特征点都要与另一幅图像上所有的特征点一一进行匹配，耗时仍然过高，并且由于误匹配导致匹配的准确率下降的问题，提出了一种改进的SURF快速匹配方法。在提取出特征后进行匹配前先将特征点进行分组，然后再进行组内匹配，这样节省匹配耗时并提供了准确率。\n[0026] 本发明的主要贡献和特点在于：一定程度上解决了经典SURF算法匹配耗时仍然过高，精度不够的问题，提供了一种匹配前先进行分组的特征匹配的新思路，较明显的提高了局部特征提取的速度和精度。更适用于对实时性要求较高的图像配准，对于像智能服务机器人这类需要对环境做出实时反映的项目实现具有重要意义，本发明为这类项目提供了图像提取和匹配实时性的可能性。\n(四)附图说明\n[0027] 图1为本发明方法的流程框图；其中1)-6)为其各个步骤。\n[0028] 图2是本发明算法与经典SURF算法在Coil-100库的准确率比较图，由图中可以看出本发明方法在匹配准确率上比经典SURF算法有不小的提高。\n[0029] 图3为本发明算法与经典SURF算法在匹配时间上的对比表格。由图中可以看出本发明算法比经典SURF算法在速度上有了很大的提高。\n(五)具体实施方式\n[0030] 下面结合附图与实施例对本发明作进一步说明，但不限于此。\n[0031] 实施例:\n[0032] 本发明实施例1如图1所示,一种改进的SURF快速匹配方法，步骤如下：\n[0033] 1)求取初始图像的积分图像和Hessian矩阵的行列式\n[0034] 对需要进行匹配的初始图像遍历求取初始图像的积分图像，并求取图像上每个点的Hessian矩阵的行列式；\n[0035] 2)建立尺度空间金字塔并进行特征点的定位\n[0036] 为使SURF算法具有尺度不变性，必须建立尺度空间金字塔，保持图像大小不变，通过改变盒式滤波器的模板大小来建立尺度图像金字塔，具体构建方法为：图像尺度空间金字塔分四层，对每一层进行四次滤波，第1层第一次滤波模板大小是给定的，为9*9，第\n1层中相邻的模板尺寸相差6个像素，即第1层中第一至四次滤波模板大小分别是9*9、\n15*15、21*21和27*27；第2层中相邻的滤波模板大小相差12个像素，第3层中相邻的滤波模板大小相差24个像素，第4层中相邻的滤波模板大小相差48个像素，每一层的第一个模板尺寸等于前一层的第二个模板的尺寸，故第2层中第一至四次滤波模板大小分别是15*15、27*27、39*39、51*51，第3层中第一至四次滤波模板大小分别是27*27、51*51、\n75*75、99*99，第4层中第一至四次滤波模板大小分别是51*51、99*99、147*147、195*195，每次滤波对应的近似尺度可由公式 计算，其中σapprox表示尺度；\n特征点定位过程：为Hessian矩阵响应值设定一个阈值，所有小于这个阈值的点都被去除，然后通过非极大值抑制将那些比其临近层及本层尺度周围的点的响应值都大或都小的点选为特征点，最后拟合三维二次函数精确确定特征点的位置和尺度；\n[0037] 3)通过Haar小波确定特征点的主方向\n[0038] 在以特征点为圆心，6σ为半径的圆形邻域里，用边长为4σ的Haar小波模板求X和Y两个方向的Haar小波响应，并用标准差为2σ的高斯函数对滤波后的区域加权，而后以特征点为中心，用一个圆心角为π/3的扇形在圆形邻域内扫描一周，计算该扇形所扫描的每个π/3角度内包括的图像点的Haar小波响应总和，取其中最大响应的方向为该特征点的主方向，其中σ为特征点所在的尺度值，X和Y是圆形邻域所处的平面直角坐标系中的两个方向；\n[0039] 4)进行特征点的分类\n[0040] 将检测到的特征点在其相应尺度上按其主方向旋转，将特征点的主方向作为平面直角坐标系xoy中的X轴，然后以特征点为圆心，以其所在尺度σ为半径做一圆，坐标轴将此圆形领域划分为四个区域，分别为平面直角坐标系xoy的四个象限中的像素区域，分别计算各象限中像素区域元素的像素和∑1，∑2，∑3，∑4，然后计算第一象限中的像素和与第三象限中的像素和的差值∑13，第二象限中的像素和与第四象限中的像素和的差值∑24，最后根据差值形成一个两维的特征向量τ1，τ2，如下式所示：\n[0041] \n[0042] 5)形成特征描述向量\n[0043] 将特征点的主方向作为平面直角坐标系xoy中的一个轴，以特征点为原点，选取大小为20σ×20σ的矩形邻域，然后将其平均分成4×4个子区域，即形成大小为5σ×5σ的16个子区域，用窗口尺寸为2σ的Haar小波对16个子区域进行滤波，Haar小波窗口在子区域内自上而下均匀扫描25次，得到25组x方向和y方向上的响应值dx、dy，再用标准差为3.3σ的高斯函数对dx，dy进行加权，统计子区域内的响应值dx、dy的和∑dx、∑dy以及其绝对值的和∑|dx|，∑|dy|的值，形成子区域内的特征向量，将4×4个子区域内的特征向量组合形成64维的向量，加上步骤4)得到的两维向量τ1，τ2，共同组成新的66维向量v，即v＝(τ1,τ2,∑dx,∑|dx|,∑dy,∑|dy|)，对此66维向量进行归一化处理，得到了特征点的改进的SURF特征描述子；\n[0044] 6)进行特征匹配\n[0045] 两维向量的特征向量τ1，τ2组合为00,01,10,11四组，用基于BBF搜索方法的最近邻匹配算法来完成对目标的检测和识别，对特征向量进行相似性测量，以两个特征向量的欧氏距离作为特征相似的判别标准，设两幅图像I1和I2的新的SURF特征向量集分别为V1＝{v11,v12,...,v1m}，V2＝{v21,v22,...,v2n}，其中m,n分别是两图像上SURF特征点的个数，计算相似特征向量的方法如下式：\n[0046] \n[0047] \n[0048] \n[0049] dis(v1i,v2j)表示两个特征集中两个特征向量的欧式距离，其中V2中第j0个向量与V1中第i个向量的欧氏距离最小，用dis(j0)表示；V2中第j1个向量与V1中第i个向量的欧氏距离次小，用dis(j1)表示，R为dis(j0)与dis(j1)之比值，设定阈值R0，当R>R0时，特征向量匹配不成功，反之则两向量为匹配向量对。