基于ORB和SLIC超像素分割的特征点匹配方法

Feature Point Matching Method Based on ORB and SLIC Superpixel Segmentation

摘要: 为了增加特征点的提取数量以及提高特征点匹配正确率，本文提出一种基于ORB和SLIC超像素分割的特征点匹配方法。首先利用ORB算法提取出特征点进行匹配，同时加入SLIC超像素分割算法的限制因素进一步提高精度，最后得到优化的特征点匹配结果。本文将SIFT算法，SURF算法和ORB算法相比较，以多次测试求取平均值的方式得出实验数据，得出特征点提取数量的比较情况和特征匹配准确率的比较情况。

Abstract: In order to increase the extracted number of feature points and the matching accuracy of feature points, this paper proposes a feature point matching method based on ORB and SLIC superpixel segmentation. At first, the ORB algorithm was used to extract feature points for matching, and the limiting factors of SLIC superpixel segmentation algorithm were added to further improve the accuracy. Finally, the optimized feature point matching results were obtained. In this paper, SIFT algorithm, SURF algorithm and ORB algorithm were compared. The experimental data were calculated by means of multiple tests to obtain the average value, and the comparison of extraction number of feature points and feature matching accuracy was obtained.

1. 引言

图像特征点的提取和匹配在图像处理领域有着非常重要的作用。例如在图像匹配，图像拼接，3D (三维)建模等技术方面的实现依赖于图像特征点提取和匹配。经过多年对图像特征点的提取和匹配算法的深入研究和应用实践，特征点提取和描述算法得到不断改进和完善。

例如Lowe等人提出的SIFT (尺度不变特征变换) [1] 算法。由于其优越和稳定的性能，已成为这种算法的基准，但时效性差是影响算法应用的主要障碍。鉴于SIFT算法的时效性较差，Bay等人提出的SURF (加速稳健特征) [2] 算法，此算法比SIFT算法更有效。Rublee等人在2011年提出的ORB (对象请求代理)算法的计算及时性 [3] 是SIFT的100倍，是SURF的10倍。Leutenegger等人在2011年提出的BRISK (二进制鲁棒不变可伸缩关键点)算法 [4] 是一个特征提取和二进制描述运算符，它还具有良好的旋转不变性，尺度不变性和鲁棒性。

当然，为了追求算法的及时性，不可避免地会损失算法的准确性。其中BRISK和ORB是典型的快速特征点检测和描述算法，具有很强的时效性。两种算法的优点是强大的鲁棒性，良好的仿射性能和及时性。缺点是它们不具有尺度不变性和较高的错误匹配率，这导致了该算法的一些局限性。

将图像分为超像素有助于进一步处理图像。通过对像素的颜色和距离特性进行聚类，简单线性迭代聚类(SLIC)算法获得了良好的分割效果。在机器视觉和图像处理的研究领域，从具有一定大小的像素块中提取图像特征以进行分析。随机选择或直接给出像素块，将破坏对象的边缘，甚至在同一像素块中对具有不同颜色的像素进行分类。使用超像素，可以将图像分割为语义上有意义的子区域，而不会破坏对象的边界信息。这些子区域中的整个像素共享相似的图像特征，包括颜色，亮度和纹理。超像素不同于图像的基本单位像素。通过使用很少的超像素而不是大像素来表示图像特性。有利于局部特征的提取和结构信息在图像中的表达；它还有助于减小处理对象的大小和后续处理的计算复杂性。作为图像处理的预处理步骤，超像素被广泛应用于图像分割，目标检测和跟踪 [1]。

超像素通常定义为在感知上有意义的原子区域 [5]，不仅可以有效地捕捉图像的功能，而且也大大降低了在随后的图像处理任务中实体的数目，如图像分割，显着性检测，轮廓闭合，草图提取，对象位置，对象跟踪，3D重建等其他图像处理任务。每种超像素分割方法都是一种折衷方法，没有一种方法是完美的。例如，ERS是规律性擅长但粘附弱，而SLIC是擅长粘着但规律性弱 [6] [7] [8]。

我们的工作是改进SLIC超像素分割算法和ORB算法，针对特征点匹配算法在尺度不变性上导致较高的错误匹配率的问题，本文以ORB和SLIC算法为例，研究改进算法的特征点提取和特征点匹配。在基于ORB和SLIC的实验中，利用ORB算法提取出特征点进行匹配，同时加入SLIC超像素分割算法的限制因素，进一步提高精度，最后得到优化的特征点匹配结果。

2. 相关工作

为了从平面图像中提取特征，我们需要一个特征检测器和一个特征描述符。最早的著名特征检测器是Harris corner Harris and Stephens (1988)，它对图像旋转不变。Rosten和Drummond (2006)提出了基于强度比较的FAST检测器，它比以前的检测器快许多倍。对于描述符，SIFT (Lowe 2004)是同行评估中质量最高的方法之一(Mikolajczyk和Schmid 2005)，但是，其计算复杂性和高维性带来了很大的计算负担。SURF (Bay等，2008年)和CARD (Ambai和Yoshida，2011年)他们提出的算法旨在加快SIFT的速度，但对于大规模问题和实时应用而言，它们可能不够快。为平面图像设计的特征匹配算法已应用于展开的经纬度地图(Valgren和Lilienthal 2007)。作为替代SIFT，Calonder等人2010提出描述符计算使用强度比较二进制字符串，实现了算法的速度快于SIFT，但是它对图像旋转和缩放比例非常敏感。为了解决这个问题，开发了结合了FAST拐角检测器和BIR的旋转不变版本的ORB (Rublee等人，2011)描述符。具有尺度不变性和旋转不变性的另外两个相似的二元特征是BRISK (Leutenegger等人，2011)和FREAK (Alahi等人，2012)。众所周知还有一种方法，基于学习的方法，该方法可以找到低维但具有高度判别力的二进制描述符。在我们的工作中，由于效率和简单性，我们将SLIC超像素分割算法和ORB算法相结合，得到一种优化的特征点提取和精度匹配的结果。

将图像分割为超像素有助于进一步处理图像。Vincent和Soille提出的分水岭变换 [9] 是超像素分割算法的先驱。它会自动寻找最小渐变像素作为种子点，并将这些点逐渐扩展到超像素。简单线性迭代聚类(SLIC)将输入图像的像素聚类到k，由于其简单性和高性能，SLIC被广泛使用。LSC和MSLIC是SLIC的最新改进方案。MSLIC将SLIC扩展到内容敏感的超像素，这意味着较小的超像素位于密集区域中，而较大的超像素位于稀疏区域中 [10]。为了生成超像素，Ncut [11] 通过最小化在划分边界 [12] 之间的边缘上定义代价函数，递归划分给定图。均值漂移和Quick-shift是模式寻找算法，它们通过递归移动到像素特征空间 [10] 中每个数据点的内核平滑质心来生成超像素。SEEDS [11] 使用爬山方法通过最小化由颜色分布项和边界项定义的成本函数来提取超像素。

Shijianbo和Jitendra Malik提出的Nrmalized Cuts方法可以通过具有轮廓和纹理特征的图像分割递归生成规则的超像素 [13]。Pedro Felzenszwalb和Daniel Huttenlocher提出了基于图的分割方法。这种方法采用最小生成树的思想来推导相同区域中的相似像素，而不是不同区域中的像素 [14]。由Alastair Moore等人提出的超像素点阵通过在水平或垂直方向上反复搜索最佳路径，基于图像网格 [15] 获得超像素块，从而将图像不断地划分为水平或垂直区域。Veksler等。提出了紧凑型超像素(Graph-cut a)和恒定强度超像素(Graph-cut b)——基于相同全局能量模型的变形。以上两种算法的基本思想是拼接重叠的图像块，以使任何像素都属于一个图像块 [15]。

我们的方法利用SLIC分割超像素的限制因素并结合ORB算法的优势，旨在提高特征点的提取与特征点匹配的效率。

3. 算法概述

3.1. 改进的SLIC算法

众所周知，简单线性迭代聚类(SLIC)方法是一种广泛应用的超像素生成方法，该算法效率高，构造了均匀、紧凑的超像素 [14]。该方法的输入是要形成的超像素(U)的数量。SLIC方法分为初始化和局部聚类两个阶段：在初始化阶段，以特定S等式规则区间随机初始化，其中以U为中心，T表示图像中的像素数量，如公式(1)所示：

$S=\sqrt{\frac{T}{U}}$ (1)

在后期，根据公式(2)计算每个质心到所有邻域像素的距离(D)：

$D\left(i,k\right)=\sqrt{\left(\frac{d_c^2}{m}\right)+\left(\frac{d_s^2}{S}\right)}$ (2)

其中m是对于考虑的超像素(k)和考虑的图像像素(i)的常数，d_c和d_s定义为颜色空间(l, a, b)中的欧氏距离和空间(x, y)距离，如公式(3)和公式(4)所示：

$d_c\left(i,k\right)=\sqrt{{\left(l_i-l_k\right)}^2+{\left(a_i-a_k\right)}^2+{\left(b_i-b_k\right)}^2}$ (3)

$d_s\left(i,k\right)=\sqrt{{\left(x_i-x_k\right)}^2+{\left(y_i-y_k\right)}^2}$ (4)

此外，超像素值不断进行更新，并一直持续到残差低于假设值为止。最后，将所有未分配的像素链接到最近的超像素。超像素是通过基于图的算法和基于梯度的算法生成的。基于图的算法将图像的像素作为节点。两点之间的边缘权重表示两个相邻像素之间在灰色，颜色和纹理方面的非负相似性。分割的最佳原则是最大化类内相似度和类内相似度。在图像中，加权最小等式用于获得最终的超像素块。

基于像素分割算法，我们所做的工作是将分割好的超像素块通过遍历分开获取若干小块，对获取的每一小块进行特征点检测并剔除错误点，最后总和所有小块的特征点数量并与原图像进行特征匹配，检测特征点匹配准确率。

3.2. ORB算法

特征提取是图像处理工作中重要的部分。在这一阶段，我们必须提取有意义的特征元素，以便从庞大的数据库中检索图像。在本文中，我们考虑了ORB特征提取技术。ORB用于从图像中提取较少但最好的特性。与SIFT和SURF相比，计算成本也更低，但计算速度快于SURF。ORB首先应用快速关键点检测器，它检测大量的关键点，然后ORB使用哈里斯角检测器从这些关键点中找到好的特征。提取出好的特征，得到较好的结果，对噪声的敏感性较低。我们可以在ORB中找到图像的质心，如公式(5)所示：

$m_{pq}={\displaystyle \underset{x,y}{\sum }{x}^p{y}^q\left(x,y\right)}$ (5)

利用图像的强度质心，我们可以找到一个角的方向为：

$c\left(\frac{m_{10}}{m_{00}},\frac{m_{01}}{m_{00}}\right)$

从中心到质心的角度为：

$\text{atan}2\left(\frac{m_{10}}{m_{00}},\frac{m_{01}}{m_{00}}\right)=\text{atan}2\left(m_{01},m_{10}\right)$ (6)

ORB使用OFAST作为快速键，侧重于方向；使用RBRIEF作为具有方向(旋转)角的简短描述符，使用方向转换简短描述符中的示例。我们利用SLIC超像素分割限制因素，对于分割提取的每一小块进行特征提取与匹配，结合ORB的优势，最后提高特征点提取与匹配准确性的效率。

4. 实验结果与分析

本文算法利用Visual Studio 2017编写C++代码，在CPU为3.6 GHz Intel Core i7，16 GB内存的计算机上运行。为了补充训练图像集，我们对多组图像进行测试。本文选中一组图像作为展示，如图1所示。本文算法与三种方法进行比较：平面ORB，平面SIFT和平面SURF。为了评估本文算法的性能，我们将本文算法与其他算法进行了比较。首先，我们在实验图像上评估了它们的特征提取数量；然后，我们通过对比特征点的匹配率评估出最优匹配结果。

Figure 1. Presentation diagram

图1. 展示图

4.1. 图像特征提取结果

本文的算法是使用SLIC超像素分割将图像分割为无重叠的若干分区并获取每个分区，然后运用ORB算法对每个分区进行特征提取，实验结果为测试50次后取得的平均值。图2中示出了图2(d)本文算法与图2(a) SIFT算法，图2(b) SURF算法和图2(c) ORB算法等三种算法的比较图。实验要提取特征点的过

Figure 2. Comparison of the algorithm in this paper with other algorithms

图2. 本文算法与其他算法比较

程也可视为是识别物体梯度的过程，梯度意味着边缘，而计算梯度，自然就用到灰度图像了，可以把灰度理解为图像的强度。我们所知道的，图像的颜色易受光照影响，难以提供关键信息，所以这里将图像进行灰度化，同时也可以加快特征提取的速度。

在此实验中，我们使用多组图像进行实验，并与其他几种算法作比较，实验结果数据如下表1所示，表1中显示的特征点提取数量与特征点维度为图1中展示图的实验数据，特征点平均值为多组图像实验数据的平均值。由表1可以看出SIFT特征点维度为SIFT算法最高，但耗时也高。每个特征点利用向量去描述，每个维度上占用4字节，SIFT需要128 × 4 = 512字节内存，SURF则需要256字节，以此类推，内存越大耗时越多。所以从表1中看出本文算法提取出的特征点数量最多，耗时最短。

Table 1. Experimental data of algorithm in this paper with other algorithms

表1. 本文算法与其他算法实验数据

4.2. 图像匹配实验结果

描述符性能是根据精度进行评估的，精度是真实匹配数与所有匹配数之间的比率。

除了比较特征提取数量之外，我们还做了特征点匹配对比。本文所用算法进一步提出最优特征匹配的比较性，在此实验中，我们以图3中展示图为例，图像受到照相机的移动，因此可能包含明显的比例变化。为了进行定量评估，我们对多组图像进行50次测试，每次测试中使用本文算法以及SIFT算法，SURF算法和ORB算法提取关键点，并在匹配后比较匹配率。如图3所示，其中图3(a)为SIFT算法实验图，图3(b)为SURF算法实验图，图3(c)为ORB算法实验图，图3(d)为本文算法实验图。

Figure 3. Matching rate diagram

图3. 匹配率实验图

如下表2中所示，表中为本文算法与SIFT算法，SURF算法和ORB算法的特征匹配数据比较，就比率而言，本文算法平均匹配率最高，SURF算法平均匹配率最低。实验测试是在每组图像利用不同算法进行50次情况下得到的平均值，后续的工作将加大试验次数，以求得更准确的实验结果。

Table 2. Comparison of feature matching rate of experimental data

表2. 匹配率实验数据比较

5. 结束语

在本文中，我们提出了一种基于ORB和SLIC算法的特征点匹配方法，用于提取特征点与匹配特征点。与现有的平面ORB的特征方法不同，我们的方法利用SLIC超像素分割算法的分割限制因素，并通过结合ORB算法得到最优化特征匹配。在多次的实验中可以看出，本文所提出的算法在特征提取方面优于文中其他比较方法。在实际的匹配测试中也有不错的结果。

我们的方法不受室内室外的光线的影响。近期的工作想要研究不同特征点提取方法与SLIC的结合的实验结果情况，例如BRISK (Leutenegger等人，2011)或FREAK (Alahi等人，2012)。此外，可以进一步优化本文算法的实现。

基金项目

广东省教育厅重大项目(2014KZDXM055)；广东省科技厅项目(2016A070708002, 2015A070706001, 2014A070708005)；五邑大学青年基金项目(2014ZK13)；研究生教育创新计划项目(2016SFKC_42, YJS-SFKC-14-05, YJS-PYJD-17-03)资助；教育部“云数融合、科教创新”基金项目(2017B02101)；江门市基础与理论科学研究类科技计划项目(2017JC01021)资助。