英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

VF-SIFT：非常快速的SIFT特征匹配

Faraj Alhwarin,DanijelaRistić-Durrant,and Axel Grauml;ser

Institute of Automation，University of Bremen,Otto-Hahn-Alle NW1,

D-28359 Bremen,Germany

{alhwarin,ristic,ag}@iat.uni-bremen.de

摘要。 基于特征的图像匹配是计算机视觉任务中最根本的问题之一。 随着功能数量的增加，匹配过程很快成为瓶颈。 本文提出了一种加速SIFT特征匹配的新方法。 主要思想是通过几个成对的独立角度来扩展SIFT特征，这对于旋转，缩放和照明变化是不变的。 在特征提取过程中，SIFT特征根据引入的角度分类到不同的簇中并存储在多维表中。 因此，在特征匹配中，只比较属于群集的SIFT特征，其中可能期望正确匹配。 通过与人工神经网络搜索的两种状态算法，分层k均值和随机kd树的性能比较，对两组图像，真实立体图像和标准数据集图像测试了所提出方法的性能。 实验结果表明，该方法的性能优于其他两种算法。 实验结果表明，相对于穷举搜索，特征匹配可以加速约1250倍，而不会丢失显着量的正确匹配。

关键词：快速SIFT，VF-SIFT，快速特征匹配，快速图像匹配。

简介

基于特征的图像匹配是许多计算机视觉应用中的关键任务，如对象识别，图像拼接，运动结构和3D立体重建。这些应用程序通常需要实时性能。

SIFT算法在文献[1]中提出，目前在计算机视觉应用中应用最为广泛，这是因为SIFT特征具有高度的独特性，并且在缩放，旋转和照明变化方面不变。 然而，SIFT的主要缺点是算法的计算复杂度随着关键点的数量而迅速增加，尤其是在匹配步骤中，由于SIFT特征描述符的高维度。 为了克服这个缺点，已经提出了SIFT算法的各种修改。Ke和Sukthankar [2]将主成分分析（PCA）应用于SIFT描述子。 PCA-SIFT将SIFT特征描述符维度从128降低到36，使得PCA-SIFT是SIFT特征描述符长度的大小，与原始SIFT方法相比，其加快了特征匹配3倍。

最近，有几篇论文[5,6]发表了，讨论了使用现代图形硬件（GPU）加速SIFT算法的某些部分，重点在于特征检测和描述步骤。 在[7]中，GPU被用来加速特征匹配。 这些GPU-SIFT方法提供了10到20倍的处理速度。 其他论文如[8]讨论了在现场可编程门阵列（FPGA）上实现SIFT的情况，实现了大约10倍的处理速度。

匹配步骤可以通过搜索近似最近邻（ANN）而不是确切的最近邻（ANN）来加速。 神经网络搜索最广泛使用的算法是kd-tree [9]，该算法在低维搜索空间中成功工作，但在特征维数增加时表现不佳。 在[1]中，Lowe使用了最佳Bin-First（BBF）方法，该方法通过修改搜索排序从kd树扩展，使得特征空间中的二进制按照距查询特征最近距离的顺序进行搜索，在检查了前200个最近邻居之后停止搜索。 BBF提供的加速因子比彻底搜索快2倍，而丢失大约5％的正确匹配。 在[10]中，Muja和Lowe比较了许多不同的算法用于在具有广泛维度的数据集上进行近似最近邻搜索，他们发现两种算法获得最佳性能，这取决于数据集和期望的精度。 这些算法使用分层k均值树或随机kd树。

在[11]中引入了一种新的策略，用于通过将SIFT特征扩展两个新属性（特征类型和特征角度）来加速SIFT特征匹配。 当将这些属性与SIFT描述符一起用于匹配目的以便仅比较具有相同或非常相似属性的特征时，可以将SIFT特征匹配的执行相对于穷举搜索加速18倍而没有明显的失去准确性。

在本文中，SIFT特征扩展了4个新的成对独立角度。 这些角度是从SIFT描述符计算出来的。 在SIFT特征提取阶段，特征存储在4维表格中，无需额外的计算成本。 然后，在匹配阶段只比较属于可能预期正确匹配的单元的SIFT特征。 通过利用这个想法，SIFT特征匹配的执行相对于穷举搜索可以加快1250倍，而不会显着降低准确性。

原始SIFT方法

尺度不变特征变换（SIFT）方法拍摄图像并将其转换为通过以下三个阶段提取的一组局部特征，这里简要解释。更多细节可以在[1]中找到：

1.特征检测和定位：通过选择DoG尺度空间的极值来确定图像中潜在兴趣点的位置。 为了搜索尺度空间极值，DoG图像中的每个像素与3times;3尺度空间区域中的26个相邻像素进行比较。 如果像素比其所有相邻的更低/更大，则将其标记为候选关键点。 通过拟合使用围绕关键点的二阶泰勒展开计算的三维二次函数来准确定位每个关键点。 然后通过丢弃低对比度点和属于边缘的点来过滤关键点。

(a)

mag（i）

(b)

T

最大

ori（i）

- 180q

T

最大

0q

180q

图1.（a）围绕关键点的梯度图像补丁。 （b）由渐变图像补丁构建的36个分箱。

2.特征方向分配：根据局部图像渐变数据为每个关键点分配一个方向。对于关键点周围某个图像区域中的每个像素，计算一阶梯度（梯度幅度和方向）。梯度数据通过依赖于比例的高斯窗口（如图1a中的圆形窗口所示）进行加权，然后用于构建一个覆盖方位范围[-180°，180°]的36格方向直方图（OH），如图1b。方向

SIFT功能theta;max被定义为对应于最大箱的方向，如图1所示。

3.特征描述符：关键点周围的梯度图像补丁由高斯窗口加权，Gau等于描述符窗口宽度的一半（图2a中的圆形窗口示出）并且通过theta;max旋转以使特征方向与水平方向对齐以提供旋转不变性（参见图2a）。 旋转之后，关键点周围的区域被细分为4x4的方形子区域。 如图2b所示，从每个子区域构建8 bin子定向直方图（SOH）。为了避免边界影响，使用三线性插值将每个梯度样本的值分配到相邻的直方图区域中。 最后，16个结果SOH被转换成128-D向量。该向量被归一化。

(a)

(b)

i

j

图2.（a）带有4x4矩形网格的旋转梯度图像片。 （b）16个用于建立SIFT描述符的8个单元SOH。

以单位长度来实现对光照变化的不变性。 这个矢量被称为SIFT描述符（SIFT-D），用于两个SIFT特征之间的相似性测量。

非常快速的SIFT功能

通常情况下，如果一个场景是由两个摄像头或一个摄像头捕捉的，但是来自两个不同的视点，则两个结果图像中的对应点将具有不同的图像坐标，不同的比例和不同的方向。 尽管如此，它们必须具有几乎相似的描述符，用于使用相似性度量来匹配图像[1]。 描述符的高维使特征匹配非常耗时。

为了加速特征匹配，假定可以为每个特征分配4个成对独立的角度。 这些角度对于观察几何和照明变化是不变的。 当这些角度与SIFT-D一起用于特征匹配时，我们可以避免比较大部分无法以任何方式匹配的特征。 这将导致匹配步骤的显着加速，如下所示。

SIFT特征角度

在[11]中，SIFT特征匹配与穷举搜索相比增加了18倍，这是通过将SIFT特征扩展为具有从OH计算的一个均匀分布角度并通过将特征分裂为最大值和最小值SIFT特征来实现的。 在本文中，试图通过从SIFT-D计算的几个角度来扩展SIFT特征。 如第2节所述，为了计算SIFT-D，关键点周围的感兴趣区域在矩形网格中的子区域中被细分。 从每个子区域建立SOH。 理论上，可以将SIFT特征扩展多个等于SOH数量的角度，因为这些角度将从SOH中计算出来。 在4times;4网格的情况下，角度的数量是16.然而，为了达到SIFT匹配的非常高的速度，这些角度应该是多变量随机变量的分量，其均匀分布在16维空间[-180° ，180°]¹⁶。 为了满足这个要求，必须验证以下两个条件[15]：

• • • 每个角度必须在[-180°，180°]（均等条件）下均匀分布。
    • 角度必须是成对独立的（成对独立条件）。

在本节中，我们的目标是找到几何角度，这些角度几何和光度变换不变，并符合上述条件。 首先，将与每个SOH的所有区间的矢量和与水平方向相对应的方向之间的角度建议为SIFT特征角。 图3b几何地表示SOH的矢量和。 在数学上，

建议的角度{theta;ij；i,j=1,...,4}计算如下：

(1)

mag_ij（k）和ori_ij（k）是k^thbin的大小和方向ij^thSOH。由于角度theta;_ij是从SOH计算出来的，从中可以看出SIFT-D是成立的，它们几何和光度转换不变。 然而，必须检查这些角度，不管它们是否满足同样可能的和成对的独立条件。

(a)

(b)

边界角度

(c)

 ij

中心角

图3.（a）SOHs， （b）：SOH单元的矢量和， （c）从SOH计算的角度

同样可能的条件：检查角度theta;ij是否相等可能的条件，他们被认为是随机变量。概率密度通过从700个测试图像（500个标准数据集图像和来自真实世界机器人应用的200个立体图像）中提取的10个⁶SIFT特征来估计每个角度的函数（PDF）。 图6给出了使用的测试图像的一些示例。

。

ş12ş22ş32

ș42

ş13ş23ş33

ș43

16%

16%

(b)

10%

10%

-180 -144 -108

-72 -36

36 72 108 144 180