基于LATCH描述子和GMS算法的特征匹配研究

张力力，尚俊云，林洪怡

摘 要：在图像匹配过程中，采用特征点进行初步匹配已经被广泛应用，但是无论采用何种匹配算法，都会存在误匹配点情况，消除掉错误的匹配点是图像匹配的前提。文章提出了一种基于LATCH描述子和GMS的特征匹配的提纯算法，对误匹配点进行筛选和剔除。首先，对两幅图像进行ORB特征检测和LATCH描述子提取，在暴力匹配的基础上通过GMS算法对正确匹配点和错误匹配点进行筛选，采用RANSAC算法对误匹配点进行剔除，结果显示在保证匹配正确率的基础上，可以保留更多的匹配点。

关键词：图像匹配;特征点匹配;描述子;误匹配

贾迪等[1]认为图像匹配是图像处理中的一个重要步骤，在摄像机标定、模式识别、三维重建、目标跟踪、图像拼接等领域得到了广泛的应用。一般完整的基于特征匹配的方法主要包括特征提取、特征匹配和去除误匹配几个步骤。目前主流的特征提取方法主要有LOWE[2]介绍的尺度不变特征变换（Scale-Invariant Feature Transform，SIFT）、BAY H等[3]介紹的加速稳健特征（Speeded Up Robust Features，SURF）和RUBLEE等[4]介绍的定向快速旋转简捷（Oriented FAST and Rotated BRIEF，ORB）等算法，为了保证后续匹配的精度，研究者都考虑到了图像之间的尺度变化、灰度变化和旋转变化。在暴力匹配后，图像中仍然存在一些错误的匹配，因此去除误匹配对图像匹配精度来说是一个很重要的步骤。常用的误匹配点检测技术是TRAN等[5]采用的基于统计模型方法的随机抽样一致性（Random Sample Consesus，RANSAC）算法，通过计算得出两幅图像之间的最优变换模型，筛选出满足模型的内点并剔除外点。

秦晓飞等[6]、赵明富等[7]通过提高RANSAC优化模型的输出参数，并在考虑了点对之间满足对极几何约束条件的前提下，采用8个点对的数据可以大幅度降低RANSAC的迭代次数，但是对极几何约束存在没有可行解的情况。BIAN等[8]提出基于网格运动统计（Grid Motion Statistics，GMS）的匹配算法完成对初匹配点对中正确匹配和错误匹配的区分，从而得到包含大量正确匹配点对的数据。因此本文提出一种改进的特征匹配提纯算法，在基于ORB特征检测的前提下对其提取3种补丁码的学习安排（Learned Arrangements of Three Patch Codes，LATCH）描述子并进行暴力匹配，使得到的特征点正确率较高，然后使用GMS算法进行网格快速划分，使得RANSAC算法可以在更少的迭代次数下得到最优模型。

1 LATCH描述子

ORB采用改进的二元鲁棒独立初等特征（Binary Robust Independent Elementary Features，BRIEF）描述，其是一种二进制编码的描述子，摈弃了利用区域灰度直方图描述特征点的传统方法，大大加快了特征描述符建立的速度，同时也极大降低了特征匹配的时间。ORB可以利用关键点的方向信息计算旋转之后的rBRIEF（rotation-aware BRIEF）描述子，使其具有较好的旋转不变性。

本文算法是相比于BRIEF二值化特征描述方法的一个优化变种，一般的二值化特征描述主要通过计算特征点窗口内n个点对的比较值形成一个bit串，作为该特征点的特征描述子，这样的bit串特征描述子在图像匹配计算时可以通过计算汉明码，大大提高计算速度，但是点对的比较会有一个明显的缺点，就是受噪声影响较大，虽然后续的一些算法通过高斯模糊进行滤波，但是滤波后图像信息会有一定减少。因此，笔者在此基础上提出了一种通过计算窗口内像素块的比较值形成bit串，同时也提出了如何定位像素块的方法。

假设特征点窗口内有3个块P1，P2，P3，每个块包含m×m个像元，每个块可以用一个m×m矩阵表示，块之间的比较为两块中各个像素对应位置处像素差的平方和，设：

（1）

因此该特征点处该像素块对应的特征可以表示为：

（2）

像素块位置的确定是通过监督学习方法进行的，在LLIDD数据集的基础上创建了一个50 k的数据样本对，每对数据样本包括两个图像块，同时有一个标签表示两个图像块是否相同，最终数据集包括一半匹配一半不匹配的图像块。使用过程中会随机产生56 k个3像素块，即：

（3）

再用每个3像素块去对每个数据对进行匹配，若匹配结果与标签结果相同则赋予一个值为1的bit，若不相同则赋予一个值为0的bit，对数据集中所有数据对匹配后将产生一个长度为50 k的bit串，将bit串中每位值相加即为该像素块的匹配能力。对所有像素块都进行该运算后再对匹配能力进行排序，同时删除与前面3像素块相关度大于0.2的3像素块。

2 GMS算法

针对特征匹配问题，GMS算法是一个简单的、基于统计的解决误匹配的方法，可以快速区分出正确的匹配和错误的匹配，提高了匹配的稳定性。核心思想就是运动的平滑性导致了匹配的特征点邻域有较多匹配的点，可以通过计数邻域的匹配点个数来判断一个匹配正确与否。

假设一：运动的平滑性使得匹配周围出现一个相似区域的出现，真匹配中两幅图上的区域位置移动平滑，假匹配则运动不平滑。

图像对{Ia，Ib}分别有{N，M}个特征，X={x1，x2，…，xi，…， xN}是所有匹配的特征的区域的集合。图像的对应区域{Ia，Ib}表示为{a，b}，每一个都有{n，m}个特征。xi∈X是对应的匹配xi区域内的匹配，用Si表示区域内支持真匹配的计量，统计模型是Si=|xi|-1，-1表示减去了原始的匹配。

假设二：令fa表示区域a内n个支撑特征中的一个，给定fa匹配成功的概率为t，若fa是一个错误的匹配，则它的匹配可能出现在全图的任一位置。匹配错但还是匹配到区域b中的概率可以表示为：

p（ fab|faf ）=βm/M（4）

其中，f ab表示fa匹配到区域b事件，f af表示fa匹配错误事件，m表示区域b中的特征数，β是一个权值因子。

设pt，pf分别表示事件f ab匹配正确、错误的概率，T ab，表示区域a和区域b匹配正确、错误的概率。则：

（5）

同理有：

（6）

由于每个特征匹配相互独立，所以Si的二项分布如下：

（7）

假设三：如运动在一个较大的区域平滑，真匹配周围的多个小区域都相似，也就是分数高，会得到一个更加一般的分数计算方式，即：

（8）

其中，K表示不相交区域的个数，{ak，bk}是预测得到的区域对，是落在{ak，bk}上匹配子集，则分布形式为：

（9）

算法定义其真假匹配的区分能力P，是用均值m的差除以标准差s的和表示，真匹配和假匹配区别的大小即两个分布的距离。

（10）

为了提高匹配点划分区域的效率，采用网格进行划分。对于每个单元对{i，j}，分数Sij为：

（11）

其中，|xikjk|是单元格{ik， jk}之间的匹配。

从真假匹配的分布来看，τ=mf+αsf，实际上是一个经验值，mf非常小而α非常较大，使得算法拒绝更多的假匹配，近似地，，从而有：

（12）

3 实验结果与分析

本文测试算法实验平台为Linux系统（Ubuntu 16.04 LTS版本 64位），处理器为4核AMD A8-4500M APU with Radeon（tm） HD Graphics，内存为7×2 Gib，运行环境为KDevelop和opencv-3.4.0，采用C++进行编程，使用标准图像集Mikolajczyk图像库，包括6组不同条件下包括旋转变换、尺度变换、亮度变换、JPEG压缩等的图像，每组图像包括6幅图像。

结果使用匹配正确率和运行时间来对评价图像匹配算法进行评价和分析。因此，正确率的值越大，检测出来的正确点对所占比例越大，匹配效果越好。

不同算法在不同图像变换下的匹配正确率如图1—6所示，其中，横坐标中的1-2表示的是图1和图2之间进行匹配，以此类推，可以看出，本文算法的匹配正确率在一定程度上超过其他3种算法的匹配正确率。

为了验证算法的实际效果，将4种算法应用于相机拍摄的两张实际场景图片，测试结果如表1所示。

由表1可以看到LGR不管在匹配点数还是在匹配正确率上都优于BR和BGR，但运行时间较长;相比较于LR，在匹配点数和匹配正确率相当的情况下，运行时间很短。

4 结语

本文针对如何消除掉错误的匹配点问题，提出了基于LATCH描述子和GMS算法的特征匹配算法。该算法利用LATCH描述子更确切地对特征点进行描述，然后对初匹配结果进行网格划分统计邻域特征点以区分正确匹配点与错误匹配点，并根据图像正确匹配点间满足一定的变换关系原则进行特征点的筛选，实现了匹配正确率的大幅度提高。在一些讲究实时性的SLAM算法中，使用LGR可能使得运行时间远远大于BR和BGR的运行时间，因此后续需要进一步优化LGR算法的框架，减少运行时间。

作者简介：张力力（1995— ），男，陕西西安人，硕士研究生;研究方向：视觉SLAM。

[参考文献]

[1]贾迪，朱宁丹，杨宁华，等.图像匹配方法研究综述[J].中国图像图形学报，2019（5）：677-699.

[2]LOWE D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004（2）：91-110.

[3]BAY H，ESS A，TUYTELAARS T，et al.Speeded-up robust features[J].Computer Vision&Image Understanding，2008（3）：346-359.

[4]RUBLEE E，RABAUD V，KONOLIGE K，et al.ORB：an efficient alternative to SIFT or SURF[C].Washington：Proceedings of the 13th IEEE International Conference on Computer Vision，2011.

[5]TRAN Q H，CHIN T J，CARNEIRO G，et al.In defence of RANSAC for outlier rejection in deformable registration[C].Washington：Proceedings of the 2012 European Conference on Computer Vision，2012.

[6]秦曉飞，皮军强，李峰.基于极线约束的ORB特征匹配算法[J].计算机应用研究，2018（9）：2865-2868.

[7]赵明富，陈海军，宋涛，等.改进RANSAC-SIFT算法在图像匹配中的研究[J].激光杂志，2018（1）：114-118.

[8]BIAN J W，LIN W Y，MATSUSHITA Y，et al.GMS：grid-based motion statistics for fast，ultra-robust feature correspondence[C].Washington：IEEE Conference on Computer Vision and Pattern Recognition，2017.

Feature matching based on LATCH descriptor and GMS algorithm

Zhang Lili， Shang Junyun， Lin Hongyi

（Xian Institute of Aerospace Precision Mechatronics， Xian 710100， China）

Abstract：In the image matching process， the use of feature points for preliminary matching has been widely used， but no matter which matching algorithm is used， there will be mismatched points. So how to eliminate the wrong matching point is the premise of image matching. Therefore， this paper proposes a feature matching purification algorithm based on LATCH descriptor and GMS to filter and eliminate mismatched points， the ORB feature detection and LATCH descriptor extraction are performed on the two images. Based on the violent matching， the correct matching points and the incorrect matching points are filtered by the GMS algorithm. Finally， the RANSAC algorithm is used to eliminate the mismatched points. The results show that more matching points can be retained on the basis of ensuring the correct matching rate.

Key words：image matching; feature point matching; descriptor; mismatch