3. 特征点描述子构造(Orientation assignment and Keypoint descriptor)
3.1 分配主方向
3.2 构造SIFT描述子
3.3 归一化处理
4. 特征点的匹配(Match)
参考文献
附录《SCALE-SPACE FILTERING:A New Approach To Multi-Scale Description》论文部分翻译
摘要:
1. Introduction
2. The Scale-Space Image
3. 不同尺度下的追踪
6. Summary
SIFT(Scale-invariant feature transform)尺度不变特征变换,是计算机视觉中非常经典的特征点提取与描述算法, 该方法于1999年由David Lowe 首先发表于计算机视觉国际会议(International Conference on Computer Vision,ICCV),2004年再次经David Lowe整理完善后发表于International journal of computer vision(IJCV)。
SIFT与Harris这种纯角点检测算法不同,它由
角点检测和
特征点描述子构造两部分组成。也就是他不光能检测到特征点,还可以给他一个描述子向量,有了这个向量,
特征点就可以被计算机所理解。
为了实现尺度不变的特征检测和定位,作者的思路是在所有可能的尺度上搜寻稳定的特征点。
1. 尺度空间极值检测(Scale-space extrema detection)
1.1 尺度空间和极值
尺度空间(scale-space)的概念在1983年Andrew P. Witkin的论文《SCALE-SPACE FILTERING:A New Approach To Multi-Scale Description》中被提出。这篇论文中提到:我们一般用极值和导数来描述信号的特征,然而尺度对这种有描述的影响,所以他们提出了尺度空间(scale-space)作为多尺度描述。论文部分翻译如下:
依赖于尺度的描述可以通过多种方式进行计算。作为一种原始的尺度参数化方法,高斯卷积具有许多好的特性,高斯是对称的,并且严格地减少均值,因此赋予信号值的权值会随着距离的增加而平滑地减少。高斯卷积在尺度参数
σ
\sigma
σ的极限处表现得很好,在较小的
σ
\sigma
σ处趋近非光滑信号,在较大的
σ
\sigma
σ处趋近信号的平均值。高斯函数也很容易被微分和积分。高斯函数并不是唯一满足这些条件的卷积核。然而,我们选择的一个更具体的动机是高斯卷积的零交点(及其导数的交点)的一个性质:当一个值减小时,可能会出现额外的零,但现有的零一般不会消失;此外,在满足“良好行为”准则的卷积核中(大致如上所述),高斯函数是唯一保证满足条件[1]的。这个属性的用途将在下面的部分中解释。 信号f(x)的高斯卷积既依赖于信号的自变量x,也依赖于高斯标准差
σ
\sigma
σ。卷积是由
F
(
x
,
σ
)
=
f
(
x
)
∗
g
(
x
,
σ
)
=
∫
−
∞
∞
f
(
μ
)
1
σ
2
π
e
−
(
x
−
μ
)
2
2
σ
2
d
μ
F(x, \sigma) = f(x)*g(x,\sigma) = \int_{-\infty }^{\infty}f(\mu ) \frac{1}{\sigma\sqrt{2\pi}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}d\mu
F(x,σ)=f(x)∗g(x,σ)=∫−∞∞f(μ)σ2π1e−2σ2(x−μ)2dμ 其中
∗
*
∗表示对
x
x
x的卷积。这个函数在
(
x
,
σ
)
(x,\sigma)
(x,σ)平面上定义了一个曲面,其中常数
σ
\sigma
σ的每个轮廓是
f
(
x
)
f(x)
f(x)的高斯平滑版本,平滑的量随着
σ
\sigma
σ的增加而增加。我们称
(
x
,
σ
)
(x, \sigma)
(x,σ)-平面尺度空间,上面定义的函数
F
F
F称为图像
f
f
f的尺度空间。 然而,仅仅在多尺度上计算这种描述并不解决问题,我们需要找到一些方法来组织或简化这些描述(description).我们的解决方法是尺度空间滤波(scale-space filtering)。通过不断改变尺度参数,扫出一个被叫做"尺度空间图像"的表面(因为原文的实验是基于1维信号的,所以多尺度形成一个二维表面。)通过这种表示,在极值随着尺度参数的变化不断移动时我们可以追踪它,并找出出现新极值的奇点。
所以我们现在清楚了尺度空间其实就是一个和连续的以尺度参数为自变量的函数。那么为了实现尺度不变的特征检测和定位,David Lowe的思路是在所有可能的尺度上搜寻稳定的特征点。为了检测尺度空间中稳定的关键点,Lowe又提出了在高斯差分函数和原图像卷积形成的尺度空间中检测极值作为关键点,这个方法的具体思路在Lowe 1999年的论文中。这个高斯差分尺度空间(Difference of Gaussian, DoG)记为
D
(
x
,
y
,
σ
)
D(x,y,\sigma)
D(x,y,σ),它通过相邻尺度做差得到,这两个相邻尺度的尺度参数差了一个常数
k
k
k:
D
(
x
,
y
,
σ
)
=
(
G
(
x
,
y
,
k
σ
)
−
G
(
x
,
y
,
σ
)
)
∗
I
(
x
,
y
)
=
L
(
x
,
y
,
k
σ
)
−
L
(
x
,
y
,
σ
)
D(x,y,\sigma) = (G(x,y,k\sigma)-G(x,y,\sigma))*I(x,y)\\ = L(x,y,k\sigma) - L(x,y,\sigma)
D(x,y,σ)=(G(x,y,kσ)−G(x,y,σ))∗I(x,y)=L(x,y,kσ)−L(x,y,σ)
L
(
x
,
y
,
σ
)
=
G
(
x
,
y
,
σ
)
∗
I
(
x
,
y
)
L(x,y,\sigma) = G(x,y,\sigma)*I(x,y)
L(x,y,σ)=G(x,y,σ)∗I(x,y)
G
(
x
,
y
,
σ
)
=
1
2
π
σ
2
e
−
(
x
2
+
y
2
)
/
2
σ
2
G(x,y,\sigma) = \frac{1}{2\pi \sigma^2}e^{-(x^2+y^2)/2\sigma^2}
G(x,y,σ)=2πσ21e−(x2+y2)/2σ2 选择
D
(
x
,
y
,
σ
)
D(x,y,\sigma)
D(x,y,σ)这个尺度空间函数的原因有很多,其一是它计算高效,且对图像做了一个平滑滤波;其二,它是对尺度归一化的LoG空间(
σ
2
∇
2
G
\sigma^2 \nabla^2 G
σ2∇2G)的一个很好近似,而从尺度归一化的LoG空间中提取的特征具有真正的尺度不变性。
1.2 DoG和LoG的关系
D
(
x
,
y
,
σ
)
D(x,y,\sigma)
D(x,y,σ)与
σ
2
∇
2
G
\sigma^2 \nabla^2 G
σ2∇2G的关系可以通过heat diffusion方程理解,此时参数是
σ
\sigma
σ而不是常见的
σ
2
\sigma^2
σ2:
∂
G
∂
σ
=
σ
∇
2
G
\frac{\partial G}{\partial \sigma} = \sigma\nabla^2G
∂σ∂G=σ∇2G 从上式可以看出。使用相邻尺度
k
σ
k\sigma
kσ和
σ
\sigma
σ的差值,通过计算有限差分近似
∂
G
∂
σ
\frac{\partial G}{\partial \sigma}
∂σ∂G,可以得到
∇
2
G
\nabla^2G
∇2G
σ
∇
2
G
=
∂
G
∂
σ
≈
G
(
x
,
y
,
k
σ
)
−
G
(
x
,
y
,
σ
)
k
σ
−
σ
\sigma\nabla^2G = \frac{\partial G}{\partial \sigma} \approx \frac{G(x,y,k\sigma)- G(x,y,\sigma)}{k\sigma-\sigma}
σ∇2G=∂σ∂G≈kσ−σG(x,y,kσ)−G(x,y,σ) 因此:
G
(
x
,
y
,
k
σ
)
−
G
(
x
,
y
,
σ
)
≈
k
σ
−
σ
∇
2
G
G(x,y,k\sigma)- G(x,y,\sigma) \approx k\sigma-\sigma\nabla^2G
G(x,y,kσ)−G(x,y,σ)≈kσ−σ∇2G 这表明,当高斯差函数的尺度相差一个常数因子时,它已经包含了尺度不变拉普拉斯函数所需的
σ
2
\sigma^2
σ2尺度归一化。方程中的因子
(
k
−
1
)
(k−1)
(k−1)在所有尺度上都是常数,因此不影响极值位置。当k趋近于1时,近似误差趋近于0.但在实践中作者发现,即使是尺度上的显著差异,如
k
=
2
k = \sqrt{2}
k=2,近似对极值检测或定位的稳定性几乎没有影响。
初始图像被递增的高斯函数重复进行卷积,以生成在尺度空间中尺度以常数因子
k
k
k分隔的图像,如左列所示。把左侧相邻尺度的图像做差得到右侧的高斯尺度差分图像。检测是在右侧的DoG空间中进行的。
David Lowe选择将尺度空间的每个octave(即
σ
\sigma
σ的倍增)划分为一个整数
s
s
s的区间,所以
k
=
2
k=\sqrt{2}
k=2。 这一段不太懂他为啥所以…,附上原文。
We choose to divide each octave of scale space (i.e., doubling of
σ
\sigma
σ) into an integer number, s, of intervals, so k =
2
\sqrt{2}
2. We must produce
s
+
3
s +3
s+3 images in the stack of blurred images for each octave, so that final extrema detection covers a complete octave.
我理解这里的
s
s
s应该是DoG中每个octave里检测极值点的尺度的个数,由于接下来检测局部极值的时候(接下来2.1节就会提到),是考虑尺度空间邻域,即需要和上下相邻的尺度作比较,所以对于上面图片中
s
=
2
s=2
s=2的情况来说,右列中这4个尺度中中间两个尺度用于检测。所以检测
2
2
2个尺度,那么DoG中就需要
s
+
2
=
4
s+2=4
s+2=4张图片。那么左侧的高斯模糊图像就需要
s
+
3
=
5
s+3=5
s+3=5张。
Once a complete octave has been processed, we resample the Gaussian image that has twice the initial value of σ (it will be 2 images from the top of the stack) by taking every second pixel in each row and column. The accuracy of sampling relative to σ is no different than for the start of the previous octave, while computation is greatly reduced
作者通过一组真实图像的实验确定了尺度采样频率和空间采样频率,实验表明
s
=
3
,
σ
0
=
1.6
s=3, \sigma_0 = 1.6
s=3,σ0=1.6时检测到的极值点能够被正确匹配的比最高,因此,本文采用这个值作为默认参数。 其中
s
s
s代表Number of scales sampled per octave: 也就是每个octave中提取特征点的层数,
σ
0
\sigma_0
σ0代表Prior smoothing for each octave. 论文中的超参数的实验结果:
我们认为在尺度空间中
D
(
x
)
D(x)
D(x)的值极值点可能是特征点,所以在高斯差分尺度空间中,搜索每个点的26邻域
(
8
+
9
+
9
)
(8+9+9)
(8+9+9),若是该点为局部极值点,则保存为候选关键点。
2.2 空间点精确定位
由于图片是对连续信号的离散采样,所以我们上一步得到的像素级的极值点可能是不准确的,要进一步计算,确定关键点的精确位置。 对每个极值点,把DoG函数做二阶泰勒展开:
D
(
x
)
=
D
+
∂
D
T
∂
X
X
+
1
2
X
T
∂
2
D
∂
X
2
X
D(x) = D + \frac{\partial D^T}{\partial X}X +\frac{1}{2}X^T \frac{\partial^2D}{\partial X^2}X
D(x)=D+∂X∂DTX+21XT∂X2∂2DX 对方程求导,令导数为0,得到的解即为极值点的偏移量:
X
^
=
−
∂
2
D
−
1
∂
X
2
∂
D
∂
X
\hat{X} = - \frac{\partial^2 D^{-1}}{\partial X^2}\frac{\partial D}{\partial X}
X^=−∂X2∂2D−1∂X∂D 其中
X
=
(
x
,
y
,
σ
)
X = (x,y,\sigma)
X=(x,y,σ),如果它在任一维度上偏移量大于0.5,那就说明极值点已经偏到另一个像素上去了,此时就要改变关键点的初始位置
x
x
x,然后重新计算偏移量,重复进行。最终得到的值可能就不是整数了,是亚像素精度。
2.3 去除不稳定的特征点
由于对比度低的点易受噪声影响,DoG对图像中的边缘有较强的响应,而一旦特征点落在图像边缘上,这些点就变得不稳定,所以我们要把它们去除。 2.3.1 去除对比度低的点 我们认为如果这个点的DoG值不够大的话就把他去掉。
D
(
x
^
)
=
D
+
1
2
∂
D
T
∂
X
X
D(\hat{x})=D+\frac{1}{2}\frac{\partial D^T}{\partial X}X
D(x^)=D+21∂X∂DTX 根据经验,取
∣
D
(
x
^
)
∣
<
0.03
|D(\hat{x})|<0.03
∣D(x^)∣<0.03 2.3.2 去除边缘点 利用Hession矩阵
H
H
H判断关键点是否位于边缘。如果在边缘上,两个特征值的比值会比较大,因此设置个阈值来判断。H的两个特征值对应两个方向上的主曲率大小。 设两个特征值之间的比值为
r
r
r:
λ
1
=
r
λ
2
\lambda_1 = r\lambda_2
λ1=rλ2
T
r
2
(
H
)
D
e
t
(
H
)
=
(
λ
1
+
λ
2
)
2
λ
1
λ
2
=
(
r
λ
2
+
λ
2
)
2
r
λ
2
λ
2
=
(
r
+
1
)
2
r
>
(
10
+
1
)
2
10
\frac{Tr^2(H)}{Det(H)} = \frac{(\lambda_1+\lambda_2)^2}{\lambda_1\lambda_2} = \frac{(r\lambda_2+\lambda_2)^2} {r\lambda_2\lambda_2}\\=\frac{(r+1)^2}{r} > \frac{(10+1)^2}{10}
Det(H)Tr2(H)=λ1λ2(λ1+λ2)2=rλ2λ2(rλ2+λ2)2=r(r+1)2>10(10+1)2
r
r
r的设定是经验值,Lowe论文中
r
r
r取了10 通过计算矩阵的行列式和矩阵,避免了直接计算特征值。 至此,其实就完成了特征点检测部分,接下来就是为每个特征点分配一个描述子。
3. 特征点描述子构造(Orientation assignment and Keypoint descriptor)
以特征点为中心,
3
×
1.5
σ
3\times1.5\sigma
3×1.5σ为半径区域,找一个圆形邻域,计算邻域内图像的梯度幅角和幅值,把它分成36份,以角度区间为横坐标,梯度幅值为纵坐标,统计每个区间内梯度幅值的累加,绘制灰度直方图,这表示了这个邻域内图像灰度的统计规律,得到直方图的峰值就是特征点的主方向。 梯度幅角和幅值的计算:
m
(
x
,
y
)
=
(
L
(
x
+
1
,
y
)
−
L
(
x
−
1
,
y
)
)
2
+
(
L
(
x
,
y
+
1
)
−
L
(
x
,
y
−
1
)
)
2
m(x,y) = \sqrt{(L(x+1, y)-L(x-1, y))^2 + (L(x,y+1)-L(x,y-1))^2} \\
m(x,y)=(L(x+1,y)−L(x−1,y))2+(L(x,y+1)−L(x,y−1))2
θ
(
x
,
y
)
=
t
a
n
−
1
(
(
L
(
x
,
y
+
1
)
−
L
(
x
,
y
−
1
)
)
/
(
L
(
x
+
1
,
y
)
−
L
(
x
−
1
,
y
)
)
\theta(x,y) = tan^{-1}((L(x,y+1)-L(x,y-1))/(L(x+1, y)-L(x-1, y))
θ(x,y)=tan−1((L(x,y+1)−L(x,y−1))/(L(x+1,y)−L(x−1,y)) 值得一提的是,在梯度直方图中,一个特征点可能产生多个坐标、尺度相同,但是方向不同的特征点,15%的特征点有多方向,而且这些点对匹配的稳定性很关键。在梯度直方图中,当存在一个相当于主峰值梯度幅值80%的区间时,可以认为这个方向是这个特征点的辅助方向。为了得到更精确的方向,关键点的方向可以由和主峰值最近的三个柱值通过抛物线插值得到。
[1] David G. Lowe. Distinctive Image Features from Scale-Invariant Keypoints[J]. International Journal of Computer Vision, 2004, 60(2) : 91-110. [2] Witkin, A.P . 1983. Scale-space filtering. In International Joint Conference on Artificial Intelligence, Karlsruhe, Germany, pp. 1019–1022.
附录《SCALE-SPACE FILTERING:A New Approach To Multi-Scale Description》论文部分翻译
依赖于尺度的描述可以通过多种方式进行计算。作为一种原始的尺度参数化方法,高斯卷积具有许多具有“良好行为”(well-behavedness )的特性,即高斯是对称的,并且严格地减少均值,因此赋予信号值的权值会随着距离的增加而平滑地减少。高斯卷积在尺度参数
σ
\sigma
σ的极限处表现得很好,在较小的
σ
\sigma
σ处趋近非光滑信号,在较大的
σ
\sigma
σ处趋近信号的平均值。高斯函数也很容易被微分和积分。 高斯函数并不是唯一满足这些条件的卷积核。然而,我们选择的一个更具体的动机是高斯卷积的零交点(及其导数的交点)的一个性质:当一个值减小时,可能会出现额外的零,但现有的零一般不会消失;此外,在满足“良好行为”准则的卷积核中(大致如上所述),高斯函数是唯一保证满足条件[1]的。这个属性的用途将在下面的部分中解释。 信号f(x)的高斯卷积既依赖于信号的自变量x,也依赖于高斯标准差
σ
\sigma
σ。卷积是由
F
(
x
,
σ
)
=
f
(
x
)
∗
g
(
x
,
σ
)
=
∫
−
∞
∞
f
(
μ
)
1
σ
2
π
e
−
(
x
−
μ
)
2
2
σ
2
d
μ
F(x, \sigma) = f(x)*g(x,\sigma) = \int_{-\infty }^{\infty}f(\mu ) \frac{1}{\sigma\sqrt{2\pi}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}d\mu
F(x,σ)=f(x)∗g(x,σ)=∫−∞∞f(μ)σ2π1e−2σ2(x−μ)2dμ 其中
∗
*
∗表示对
x
x
x的卷积。这个函数在
(
x
,
σ
)
(x,\sigma)
(x,σ)平面上定义了一个曲面,其中常数
σ
\sigma
σ的每个轮廓是
f
(
x
)
f(x)
f(x)的高斯平滑版本,平滑的量随着
σ
\sigma
σ的增加而增加。我们称
(
x
,
σ
)
(x, \sigma)
(x,σ)-平面尺度空间,上面定义的函数
F
F
F称为图像
f
f
f的尺度空间。图1所示的是一个随
σ
\sigma
σ的增加而增加的高斯平滑序列。这些是来自于尺度空间图像的常数剖面图。 在
σ
\sigma
σ的任意值处,平滑信号的n阶导数的极值由(n + 1)阶导数的零点给出,使用下面的式子计算
∂
n
F
∂
x
n
=
f
∗
∂
n
g
∂
x
n
\frac{\partial^n F}{\partial x^n} = f* \frac{\partial^n g}{\partial x^n}
∂xn∂nF=f∗∂xn∂ng 其中高斯函数的导数很容易得到。虽然这里提出的方法适用于任何导数的零点,我们将限制我们的注意力在那些在第二。这些是斜率的极值,即拐点。对于尺度空间图像,
σ
\sigma
σ的所有值处的拐点都满足:
F
x
x
=
0
,
F
x
x
x
≠
0
F_{xx} = 0, F_{xxx} \ne 0
Fxx=0,Fxxx=0 用下标符号表示偏微分。
3. 不同尺度下的追踪
F
x
x
=
0
F_{xx}=0
Fxx=0的等值线标记了平滑信号中拐点的出现和运动,为拐点在所有尺度上的定性描述提供了原料。接下来,我们将对这些等值线应用两个简化假设: (1)确定性假设,极值点可以在不同的尺度被观察到,但是它躺在公共的零等值线在的尺度空间中,这来自于一个潜在的事件 (2)位置假设,产生零等值线的点的真实位置是当
σ
=
0
\sigma=0
σ=0时等值线上
x
x
x的位置。