基于尺度空间的快速特征检测算法

Fast Feature Detector Based on Scale Space

摘要: 本文采用三次样条函数近似高斯核函数对图像构建离散尺度空间，其模糊比和初始平滑度设为2和0.627，在图像尺度空间内，依次利用边缘检测和FAST角点检测方法提取图像特征点。

Abstract: In this paper, the cubic spline function is used to approximate the Gaussian kernel function to construct the discrete scale space of the image, and its fuzzy ratio and initial smoothness are set to 2 and 0.627. In the image scale space, the edge detection and fast corner detection methods are used to extract the image feature points.

1. 引言

特征检测是在图像上提取满足某种显著性指标的特征点的过程。特征点可以是斑点、角点甚至边 [1] [2]。特征检测在现实世界中有很多应用，如视觉定位和三维重建。一个好的特征检测器必须提供可靠的兴趣点/关键点，这些兴趣点/关键点具有尺度不变性、高度可分辨性、对噪声和失真的鲁棒性、高重复率的有效性、良好的局部性、易于实现和计算快速。近三十年来，大量的图像局部特征检测器被提出，其中尺度不变特征变换(SIFT) [3] 可能是最著名的技术之一，它实际上为图像处理和计算机视觉开辟了一个新纪元。

在文献中，特征检测器可以分为基于灰度的、基于多尺度的和基于学习的三类。基于灰度的检测器直接应用于图像的灰度值，这些探测器通常速度很快。Harris角点检测器及其变体 [4]、加速片段测试的特征(FAST) [5]、最大稳定极值区域(MSER) [6]、基于灰度的区域(IBR) [7] 和最小值段同化核(SUSAN) [8] 是这一类中最具代表性的方法。

第二类特征检测器采用尺度空间分析。首先将输入图像变换成一个尺度空间金字塔，然后检测关键点。在文献中，这种方法通常被称为多尺度特征检测器。一些代表性的多尺度特征检测器包括SIFT [3]、加速鲁棒特征(SURF) [9]、Harris仿射和Hessian仿射 [10]、仿射SIFT (ASIFT) [11]、称为KAZE的非线性尺度空间方法 [12]、具有容错能力的尺度不变特征检测器(SIFER) [13]，移位滤波器响应(COSFIRE) [14] 和多尺度Harris角点检测器(HarrisZ) [15] 的组合。多尺度方法检测的关键点通常具有较高的精度、重复性、鲁棒性和尺度不变性。与基于灰度的方法相比，它们表现出更好的性能，但通常需要更多的计算时间。与前两类方法相比，第三类方法不提取和分析图像的特定特征来识别关键点，而是自动学习和评估关键点的位置或描述方式，尽管这种基于学习的方法最有潜力，训练数据限制了它们在实际中的适用性。

近年来，已经开发了几种基于深度学习的特征检测器 [16] [17] [18]。它们在图像上进行训练，通常会提供抗失真的关键点。尽管基于学习的特征检测器由于具有数据增强的预训练而具有一定的尺度不变性，但它们对尺度变化不具有内在的不变性，在尺度发生显著变化的情况下，匹配往往失败。事实上，数据增强通常能很好地捕捉到真实世界中的局部变化，但它们对大规模数据集的有效性通常难以预测。

大多数传统的探测器不能提供可靠的关键点，它们通常会陷入叠加极值，同时需要相当长的计算时间。Ghahremani (2020)提出了一种多尺度特征检测算法 [19]，在检测离散图像中的关键点时不会产生叠加的极值响应。本文提出了一种新的多尺度特征检测算法，采用了Ghahremani提出的黄金模糊比构建卷积核，利用结构良好的小波和样条函数对所提出的核进行离散化，形成多尺度空间域。该方法的尺度空间不需要上采样或下采样操作，从而为检测到的关键点提供了良好的定位。该算法针对大容量图片有较好的效果，运算速度快。

本文的其余部分组织如下。第2节详细介绍了所提出的基于尺度空间的快速特征检测算法。第3节报告并讨论了快速特征检测器的实验结果，第4节给出了结论和未来的工作。

2. 基于尺度空间的快速特征检测算法

多尺度关键点检测器一般包括两个步骤：尺度空间构造和关键点检测。

本文提出的检测器是一种用于在图像中寻找可靠角点的多尺度特征检测器。我们首先需要设计一个合适的核构建尺度空间。由于高斯核函数是唯一可能的线性尺度空间核函数，故我们选择高斯核函数来构建线性尺度空间，并选用Ghahremani (2020)证明的尺度空间参数的黄金值 [19]，即模糊比和平滑度分别设置为2和0.627，可以在一定程度上解决叠加极值问题，并在此基础上构建尺度空间。由于图像数据是离散的，故我们主要讨论离散情况下的尺度空间，我们选用三次样条函数来构建尺度空间，通过对初始滤波器用零进行插值，得到其他尺度上的滤波器。

2.1. 核的构造

几项研究表明 [20] [21]，自然图像具有在一定尺度范围内存在的特定性质，而可能的尺度空间核是高斯函数。在实际的图像处理中，一种强大的变换是能够对图像的结构信息进行表达的变换。显然，鲁棒的多尺度算法可以为结构信息提供稳定的表示。

为了设计适用于图像离散性质的尺度空间，我们需要对核进行离散化。因此，我们寻求一种可以提供多尺度对象表示的变换，其核函数类似于离散域中的高斯函数，并具有平移不变性、良好的定位以及对噪声和失真的鲁棒性。

考虑到上述所有因素，我们选择三次样条函数作为特征检测器的核心。

由于在图像处理中设计适当的理论分析和综合滤波器组是一项具有挑战性的任务，并且仍有待讨论，Starck等人 [22] 选择了对称FIR B₃滤波器组。一维(1D)三次样条函数 $\varphi$ [图1]定义为：

$\varphi \left(v\right)=\frac{1}{12}\left({\left|v-2\right|}^3-4{\left|v-1\right|}^3+6{\left|v\right|}^3-4{\left|v+1\right|}^3+{\left|v+2\right|}^3\right)$

Figure 1. 1-dimensional cubic spline function

图1. 1维三次样条函数

尺度函数的相关滤波器为 $h^{\left(1\right)}=\left[1,4,6,4,1\right]/16$，其二维核是可分离的，分别在x和y方向卷积两个一维三次样条核得到。可分离性允许快速计算，尤其是对于大型图像。其他放大的滤波器 $h^{\left(j\right)},j\in \left\{2,\cdots ,J\right\}$，通过在 $h^{\left(1\right)}$ 中的每对相邻元素之间插入“ $2^{j-1}-1$ ”个零，可得三次样条核集 $\left\{h^{\left(1\right)},h^{\left(2\right)},\cdots ,h^{\left(N+2\right)}\right\}$，其中，J表示滤波器的个数、N表示有效尺度空间的层数。三次样条函数 $\varphi \left(v\right)$ 的两个连续分辨率之差产生小波函数 $\psi \left(\frac{v}{2}\right)$ [图2]，如下所示：

$\frac{1}{2}\psi \left(\frac{v}{2}\right)=\varphi \left(v\right)-\frac{1}{2}\varphi (\; v\; 2\; )$

Figure 2. 1D wavelet function

图2. 1维小波函数

从图中我们可以看到，三次样条函数近似高斯函数，而产生的小波函数则近似高斯拉普拉斯算子。

我们将用三次样条核集去模糊图像，产生一系列不同尺度的图像，这个过程类似于高斯金字塔的形成。图像的卷积核应近似于高斯核函数。接下来，我们将寻找与三次样条核卷积效果类似的高斯核。以 $h^{\left(1\right)}$ 为例，由于 $h^{\left(1\right)}$ 有5个元素，则假设高斯核的直径为5，根据计算直径d的公式 $d=2\times 3\times \sigma +1$，我们知道尺度 $\sigma$ 值在 $\frac{2}{3}$ 附近。接下来，我们计算精确尺度值，先计算三次样条核与高斯核对应点之间的欧氏距离，当各点欧氏距离最小时，此时的 $\sigma$ 值就是三次样条核对应的尺度值。尺度值精确到2位小数，通过计算可知，欧氏距离最小为0.009736，此时 $h^{\left(1\right)}$ 对应高斯核函数的尺度值为1.07。

$h^{\left(1\right)}$ 与元素个数为5且 $\sigma$ 值为1.07的高斯核的图像，如图3所示。

Figure 3. Curve of $h^{\left(1\right)}$ and Gaussian kernel function

图3. $h^{\left(1\right)}$ 与高斯核函数曲线图

我们构建的尺度空间是基于前一层图像使用三次样条核进行卷积得到的，而DoG金字塔是用不同尺度的高斯核对原图进行卷积。若考虑都是对原图进行卷积，则每层图像的卷积核 $\left\{{\text{H}}_1,{\text{H}}_2,\cdots ,{\text{H}}_{N+2}\right\}$ 可看作是由三次样条核集中的核的卷积得到的，即 ${\text{H}}_1=h^{\left(1\right)},{\text{H}}_2=h^{\left(2\right)}\ast h^{\left(1\right)},\cdots ,{\text{H}}_{N+2}=h^{\left(N+2\right)}\ast \cdots \ast h^{\left(2\right)}\ast h^{\left(1\right)}$，其中 $\ast$ 表示卷积。

我们同样使用最小欧氏距离(Minimum Euclidean Distance)的方法求卷积核 $\left\{{\text{H}}_1,{\text{H}}_2,\cdots ,{\text{H}}_{N+2}\right\}$ 的尺度值，如图所示，我们列举了前5个卷积核 $\left\{{\text{H}}_1,{\text{H}}_2,{\text{H}}_3,{\text{H}}_4,{\text{H}}_5\right\}$，如表1所示。

Table 1. Scale values and errors of convolution kernels

表1. 各卷积核的尺度值及误差

2.2. Canny边缘检测

本文主要检测的是印章图像，考虑到图像的结构特征，我们采用Canny边缘检测算法对图像进行边缘提取，可加快后续的特征点检测速度，减少噪声干扰。

Canny边缘检测方法 [23] 是Canny于1986年提出的一种被公认为效果较好的边缘检测方法。具体实现步骤如下：

(1) 图像平滑；

(2) 梯度幅度值和方向的计算；

(3) 非极大值抑制；

(4) 滞后阈值化；

(5) 算法通过将8连接的弱像素合并到强像素集中，实现边缘链接。

2.3. 尺度空间表示

在构建尺度空间之前，我们要考虑合适的参数值，即模糊比和平滑度。因为在尺度空间参数没有很好定义的情况下，会发生重叠现象，即图像中两个或多个相邻边缘之间的相互作用/干扰，其核响应不能提供有关这些边缘位置的清晰信息。故我们将平滑度和模糊比分别设置为0.627和2，以此构建多尺度空间。

为了降低噪声和其他伪影，需要对输入的原图像做一个初步平滑，我们选择标准差为“ ${\sigma }_0$ ”的高斯核函数，其中 ${\sigma }_0=0.5$ 是防止明显混叠的最小值，我们依据黄金参数值，选择 ${\sigma }_0=0.627$ 的高斯核函数，其相应的平滑滤波器是

$h^{\left(0\right)}=\left[0.00392512,0.17820586,0.63573803,0.17820586,0.00392512\right]$。

我们主要是使用三次样条核来构建尺度空间，其中模糊比为2。这样卷积变换可以将图像映射到不同的尺度级别，具体过程如下：

每个尺度层由三次样条核卷积前一层图像得到，如第j个尺度层，它是通过前一个尺度层“ $j-1$ ”与 $h^{\left(j\right)}$ 卷积得到图像 $C_j$，

$C_j=C_{j-1}\ast h^{\left(j\right)},j=1,2,\cdots ,J$

其中 $h^{\left(j\right)}$ 表示尺度层j的核， $C_0$ 表示初步平滑后的输入图像。我们通过上述操作来构造“尺度空间”。

所提出的多尺度方法框架如图4所示。

尺度空间中相邻两层图像的模糊比接近2，例如“N = 3”时，尺度空间中每一层的尺度值 $\left\{{\sigma }_0,{\sigma }_1,{\sigma }_2,{\sigma }_3,{\sigma }_4,{\sigma }_5\right\}$ 分别为：

$\left\{0.627,1.07,2.33,4.75,9.54,19.10\right\}$，

则

$\mu =\left\{\frac{{\sigma }_1}{{\sigma }_0},\frac{{\sigma }_2}{{\sigma }_1},\frac{{\sigma }_3}{{\sigma }_2},\frac{{\sigma }_4}{{\sigma }_3},\frac{{\sigma }_5}{{\sigma }_4}\right\}=\left\{1.7065,2.1775,2.0386,2.0084,2.0020\right\}$。

不同于传统特征检测器构建的尺度空间金字塔，包含多个组，每个组里有几个尺度层，我们的特征检测器中尺度空间只包含“N + 3”个尺度层，没有组的概念。事实上，我们用零插值对核进行放大来代替对图像进行降采样。这个方法有助于我们检测到的关键点定位良好。

Figure 4. Scale space structure

图4. 尺度空间结构图

2.4. 特征点检测

FAST方法被证明是一种快速有效的特征点(角点)检测方法，故尺度空间创建以后，我们利用性能良好的FAST角点检测算法在每一层精细尺度空间检测特征点。对尺度空间的每一层所使用的FAST的阈值t都相同。

FAST角点检测方法是由Rosten和Drummond于2006年提出，并于2009年进行了完善 [10]。该方法最突出的优点是它的计算效率，它运行速度快，事实上它比其他著名的特征点提取方法(如SIFT、SURF、Harris)都要快，而且如果应用于机器学习方法，该方法能够取得更佳的效果。

FAST角点检测方法的基本原理是使用圆周长为16个像素点的圆(半径为3的Bresenham圆)来判定其圆心像素P是否为角点。在圆周上按顺时针方向从1到16的顺序对圆周像素点进行连续编号。如果在圆周上有N个连续的像素的亮度都比圆心像素的亮度IP加上阈值t还要亮，或者比圆心像素的亮度减去阈值还要暗，则圆心像素被确定为角点。因此要想成为角点，必须满足下列两个条件之一：

条件1：集合S由圆周上N个连续的像素x组成，该集合的任意像素x都满足 $I_x>I_p+t$。

条件2：集合S由圆周上N个连续的像素x组成，该集合的任意像素x都满足 $I_x<I_p-t$。

N一般选择为12，正好为圆周的四分之三。如果N一定，就把使P仍然是角点的最大阈值t定义为P的角点响应值。

基于尺度空间的快速特征检测算法流程图如图5所示。

Figure 5. Flow chart of fast feature detection algorithm based on scale space

图5. 基于尺度空间的快速特征检测算法流程图

3. 数值实验

我们采用印章图像进行实验，参数值N为3，尺度空间由6幅卷积图像构成，去除首尾两层，我们在中间层检测特征点，因为首层采用了低通滤波器以避免发生严重的重叠现象，起到了一个预处理的作用，尾层由于尺度很大一般难提取特征点，为节约计算时间不对该层进行检测。

经过实验我们发现特征点主要集中于 $C_1$ 和 $C_2$ 层之间，检测结果如图6所示。

Figure 6. Detection diagram of C₁ and C₂

图6. C₁和C₂的检测图

我们将图像的每层特征信息存储在文件中，然后输出图像的最终检测结果，如图7所示。

Figure 7. Test results

图7. 检测结果图

4. 结论

本文提出了一种基于尺度空间的快速特征检测算法，其基本思想是：基于黄金模糊比( $\mu =2,\sigma =0.625$ )设计核函数，采用Canny算法检测图像边缘，基于边缘图像利用卷积核构建多尺度体系结构，在尺度空间中利用FAST方法检测特征点。

针对未来工作，我们考虑优化特征点的定位，使其在亚像素区域检测到更精确的坐标，并构建特征描述符，完成图像匹配，使其可以在更多场合应用。

NOTES

^*通讯作者。