Local Invariant Feature Detectors
Table of Contents
1. 图像局部不变性特征
什么是局部特征?A local feature is an image pattern which differs from its immediate neighborhood.
参考:
图像局部不变性特征与描述,王永明/王贵锦(本文主要摘自该书)
Local Invariant Feature Detectors - A Survey, 2008
1.1. 特征的不变性
特征的不变性有很多,比如旋转不变性(物体旋转后也能检测出来),亮度不变性(物体变暗或变亮都能检测出来),尺度不变性(物体缩放后也能检测出来),仿射不变性(后文将介绍)等等。
1.1.1. 仿射变换
仿射变换(Affine transformation)的定义为:
用于图像处理时,
图 1 (摘自Linear transformations)是乘以一个矩阵(即线性变换)的例子。
Figure 1: 乘以一个矩阵(即线性变换)所对应图像变换的例子
图像处理中,仿射变换还可以写为:
从而,仿射变换可以
Figure 2: 仿射变换的例子
由于仿射变换的
2. 尺度空间理论简介
图像尺度空间(Scale space)分析技术是一种性能突出的多尺度分析(Multiple-scale analysis)技术,它在图像处理中占据非常重要的地位。
参考:
Tony Lindeberg. (1998), "Feature Detection with Automatic Scale Selection" (pdf)
2.1. 尺度空间定义
图像的尺度空间记为
其实,上式就是高斯模糊(Gaussian blur)运算。当参数
Figure 3: 上左(原图),上右(高斯模糊
在不同尺度上,可以检测出不同的特征。大尺度图像上可以检测概貌特征,小尺度图像上可以检测细节特征。
2.2. 尺度空间理论应用
尺度空间理论不是一个具体的图像处理算法,而是一个通用的“图像处理框架”。 比如,可以在这个框架下检测角点(Corner)、斑点(Blob)等等。Harris-Laplace 角点检测、SIFT 斑点检测、SURF 斑点检测等算法都是尺度空间理论的应用。
2.3. 特征检测和定位
图像特征往往在粗糙的尺度上被检测到,此时位置信息未必是最准确的。因此, 通常图像的尺度分析包含两个阶段:首先在粗尺度上进行特征检测,然后再在细尺度上进行精确定位。 如图 4 (摘自:Tony Lindeberg. (1998), "Feature Detection with Automatic Scale Selection")所示。
Figure 4: 尺度分析中角点检测实例。第 1 列为原图像,第 2 列为不同尺度上检测的结果,第 3 列是精确定位后的结果。
3. Corner 检测
角点(Corner)对应于物体的拐角,如道路的十字路口、丁字路口等。
角点检测方法主要分为两类:基于图像“边缘”的方法和基于图像“灰度”的方法。本文介绍的 Harris 角点检测和 SUSAN 角点检测都是后者,即基于图像“灰度”的方法。
3.1. Harris 角点检测
Harris 角点检测的基本思路如下: 考虑一个局部的小区域(或称小窗口),如果在各个方向上移动这个特定的小窗口,窗口内图像的灰度发生了较大的变化,那么,就认为在窗口内遇到了角点,如图 5 左图所示。 如果这个特定的窗口在图像各个方向上移动时,窗口内图像的灰度没有发生变化,那么窗口内就不存在角点,如图 5 中图所示;如果窗口在某一个方向移动时,窗口内图像的灰度发生了较大的变化,而在另一些方向上没有发生变化,那么,窗口内的图像可能就是一条直线的线段,如图 5 右图所示。
Figure 5: 左图(窗口移动与角点);中图(窗口移动与平面);右图(窗口移动与线段)
对于图像
式中,
Figure 6: 左图(常量加权函数),右图(高斯加权函数)
当
3.1.1. 两个例子
考虑图 7 所示例子,我们要检测红色框中心点是否为角点。
Figure 7: 实例 1:检测红色框中心点是否为角点
先考虑两个特例,假设
Figure 8: 设
Figure 9: 设
对图 7 红色框中心点,考虑
Figure 10: 图 7 中当
从图 10 中明显可看到,当
我们再看一个例子。考虑图 11 所示例子,我们要检测红色框中心点是否为角点。
Figure 11: 实例 2:检测红色框中心点是否为角点
考虑
Figure 12: 图 11 中当
从图 12 中明显可看到,当
注:本节介绍的两个例子摘自:https://dsp.stackexchange.com/questions/3336/mathematics-of-harris-corner-point-detection
3.1.2. 数学推导
根据二元函数泰勒展开,对图像
把上式代入自相关函数
其中:
由线性代数(可参考《工程数学线性代数(第五版),同济大学版》5.7 节 正定二次型)中的知识可知:
Figure 13:
Figure 14: 椭圆
前面介绍过,判断点
3.1.3. 矩阵 M(x,y)特征值与图像区域类型的关系
前面介绍了如何通过矩阵
矩阵
(1) 图像中的直线。一个特征值大,另一个特征值小,
(2) 图像中的平面。两个特征值都小,且近似相等; 自相关函数数值在各个方向上都小(即
(3) 图像中的角点。两个特征值都大,且近似相等; 自相关函数值在所有方向上都大(即
Figure 15: 矩阵 M(x,y)特征值与图像区域类型的关系
3.1.3.1. 矩阵 M 的其它名字:"Structure Tensor" or "Second Moment Matrix"
矩阵 M:
它还有其它名字:"Structure Tensor" or "Second Moment Matrix"。
3.1.4. Harris 角点响应(避免直接求特征值)
求解矩阵特征值的费时的操作,Harris 给出了不直接求特征值来判断角点的方法。Harris 指出可以通过计算一个角点响应值
上式中,
Harris 给出了下面结论:
(1) 当
(2) 当
(3) 当
3.1.5. Harris 角点检测算法总结
根据上述讨论,可以将 Harris 图像角点检测算法归纳如下,共分以下五步:
(1) 计算图像
(2) 计算图像两个方向梯度的乘积。
(3) 使用高斯函数对
(4) 计算每个像素的 Harris 响应值
(5) 在 3×3 或 5×5 的邻域内进行“非最大值抑制”,局部最大值点即为图像中的角点。
3.1.6. OpenCV 例子:Harris 角点检测
OpenCV 中实现了 Harris 角点检测,参见函数 cornerHarris ,下面是它的一个例子:
#!/usr/bin/env python # -*- coding: utf-8 -*- import cv2 import numpy as np filename = 'chessboard.jpg' img = cv2.imread(filename) gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY) gray = np.float32(gray) dst = cv2.cornerHarris(gray,2,3,0.04) #result is dilated for marking the corners, not important dst = cv2.dilate(dst,None) # Threshold for an optimal value, it may vary depending on the image. img[dst>0.01*dst.max()]=[0,0,255] cv2.imwrite('output.jpg', img)
这个例子中,假设输入图像 chessboard.jpg 如图 16 所示。
Figure 16: 待检测图像
则检测的输出图像 output.jpg 如图 17 所示。
Figure 17: Harris 角点检测结果(红色标记)
3.1.7. Harris 角点检测算子的扩展
3.1.7.1. Harris-Laplace 角点检测算子
Harris 角点检测算子对亮度变化不敏感,且具有旋转不变性(回忆一下前面讨论,从各个方向移动小窗口
将 Harris 角点检测算子和高斯尺度空间表示相结合,可以使 Harris 角点检测算子具有“尺度不变性”,这种方法也称为“Harris-Laplace 检测方法”。
参考:https://en.wikipedia.org/wiki/Corner_detection#The_multi-scale_Harris_operator
3.1.7.2. Harris-Affine 角点检测算子
Harris-Affine 角点检测算子对原始 Harris 角点检测算子进行扩展,使其具备“仿射不变性”。
参考:K. Mikolajczyk, K. and C. Schmid (2004). "Scale and affine invariant interest point detectors"
3.2. Shi-Tomasi 角点检测(Harris 角点检测的变种)
Jianbo Shi 和 Carlo Tomasi 在其论文 Good Features to Track 中提出的 Shi-Tomasi 算法,开始主要是为了解决跟踪问题,用来衡量两幅图像的相似度,我们可以把它看为 Harris 角点检测算法的变种。
Shi-Tomasi 角点检测和 Harris 角点检测的不同之处仅在于角点响应的计算公式不同。
Harris 角点检测中使用下面公式计算待检测点的响应:
Shi-Tomasi 角点检测中使用下面公式计算待检测点的响应:
Shi-Tomasi 角点检测需要计算矩阵 M 的两个特征值。
3.3. SUSAN 角点检测
SUSAN(Smallest Univalue Segment Assimilatating Nucleus 的缩写),即“最小核值相似区”,是由牛津大学的 Smith 等提出来的。
这里介绍一下 SUSAN 角点检测的基本思想。
SUSAN 检测方法是一种基于窗口模板的检测方法, 在图像每个像素点位置处建立一个圆形窗口,把圆中心像素与圆形模板内其他像素比较,统计出与圆中心像素相似的像素数量,当相似像素数量小于一个阈值,就被认为是要检测的角点。 如图 18 所示。
Figure 18: SUSAN 原理(在 a 圆形窗口中和它中心像素相似的像素数量最少)
SUSAN 角点检测的一个优点就是对局部的噪声不敏感,抗干扰能力强,因为 SUSAN 算子不依赖图像分割的结果,避免了梯度计算。
参考:https://users.fmrib.ox.ac.uk/~steve/susan/susan/node2.html#SECTION00020000000000000000
4. Blob 检测
斑点检测(Blob detection)是计算机视觉的重要内容,是区域检测(Region detection)的一种特例,是许多特征生成、目标识别等方法的重要预处理环节。
斑点通常指与周围有着颜色和灰度区别的区域。如,一棵树是一个斑点,一块草地、一栋房子也可看成一个斑点等等。斑点通常和关键点(key point),兴趣点(intrest point)以及特征点(feature point)表示同一个概念。 由于斑点代表的是一个区域,相比单纯的角点(Corner),它的稳定性要好,抗噪声能力要强。
4.1. 利用 LoG 检测斑点
LoG 是高斯拉普拉斯算子(Laplace of Guassian)的缩写,它的定义是:
我们知道,高斯拉普拉斯算子
图 19 是利用高斯拉普拉斯算子检测一维信号中边缘的例子。
Figure 19: LoG 算子检测一维信号中边缘的例子
下面将介绍如何改造 LoG 算子,让其可以进行斑点检测。
4.1.1. 一维信号斑点检测
一维信号中的斑点可以认为是两个相邻的突跳边缘组成。图 20 是不同大小的一维斑点。
Figure 20: 不同大小的一维斑点
图 21 是高斯函数(
Figure 21: 斑点信号与高斯函数(
“零交叉点”对应原信号边缘。此外,我们发现,对于图 21 的右下子图, 检测 LoG 的“极值点”可以检测出原信号(图 20 右下子图)中的斑点。 检测出的斑点的尺寸(这里为 2)正好是高斯函数方差(
不过,使用检测 LoG 极值的方法只能检测出小斑点,而无法检测大斑点(如图 20 中上排两个子图、左下子图中的斑点就不法检测出来)。就算把
Figure 22: LoG 响应随
实验表明, 使用尺度归一化的 LoG(Scale-normalized Laplacian of Gaussian)可以去除方差增大导致的衰减现象。尺度归一化 LoG 算子(二维情况)的定义为
图 23 是对一维信号的非规范化和尺度归一化 LoG 响应的对比图。
Figure 23: 非规范化(子图 a)和尺度归一化 LoG(子图 b)响应对比图
4.1.2. 尺度归一化 LoG 检测斑点
前面以一维信号为例介绍了尺度归一化 LoG 算子检测斑点的过程。对于图像(二维信号)中斑点的检测过程也类似,基本过程为: 首先求尺度归一化 LoG 算子
求
上式可化简为:
即:
例如,对于图 24 中的二值化圆形斑点,在尺度
Figure 24: 图像中的圆形斑点与其尺度归一化 LoG 响应
图 25 是实际检测斑点的过程示意图。对于二维图像,计算图像在不同尺度下的尺度归一化 LoG 响应值(即求
Figure 25: 在位置和尺度空间中搜索峰值点
4.2. 利用 DoH 检测斑点
另一种斑点检测方法是利用图像点 Hessian 矩阵(二阶微分):
上式中,
计算 Hessian 矩阵的行列式(Determinant of Hessian, DoH):
尺度归一化的 DoH 为:
当
无论是 LoG 还是 DoH,它们对图像中的斑点进行检测,其步骤都可以分为以下两步:
1)使用不同的
2)在图像的位置空间与尺度空间中搜索 LoG 与 DoH 响应的峰值。
参考:
Lindeberg, 2015 "Image matching using generalized scale-space interest points" (pdf)
https://en.wikipedia.org/wiki/Blob_detection#The_determinant_of_the_Hessian
4.2.1. LoG vs. DoH
与 LoG 相比, DoH 响应仅当两个垂直方向上同时有大的变化时才会有较大的响应,所以,DoH 对图像中的细长结构的斑点有较好的抑制作用。 如图 26 (摘自 Lindeberg, 2015 "Image matching using generalized scale-space interest points")所示,通过对比第二排右子图(LoG 检测结果)和第三排右子图(DoH 检测结果)可知,细长斑点在 DoH 检测中被较好地抑制。
Figure 26: 第一排(原图),第二排(LoG 响应及其极值点),第三排(DoH 响应及其极值点)
5. Blob 检测高效算法:SIFT
尺度不变特征转换(Scale-Invariant Feature Transform)是一种机器视觉的算法,用于 检测与描述图像中的局部特征 ,它对旋转、尺度缩放、亮度变化保持不变性,对视角变化、仿射变换、噪声也保持一定程度的稳定性。此算法由 David Lowe 在 1999 年所发表,2004 年完善总结。该算法不仅仅是个特征检测算法, 它将特征点检测和特征失量生成、特征匹配搜索等步骤完整地结合在一起进行优化,达到了接近实时的运算速度。 下面的描述中,不区分特征点、斑点、兴趣点等概念。
SIFT 的四个步骤:
(1) Scale-space extrema detection(在尺度空间上查找特征点);
(2) Keypoint localization(特征点精确定位);
(3) Orientation assignment(为每个特征点指定方向参数);
(4) Keypoint descriptor(生成特征点描述子)
参考:
David G. Lowe. (2004), "Distinctive Image Features from Scale-Invariant Keypoints" (pdf)
5.1. SIFT 算法检测特征点
SIFT 算法的第一步是在尺度空间(Scale-space)上查找特征点。
SIFT 算法中,尺度空间在实现时使用高斯金字塔表示,高斯金字塔的构建分为两部分:
(1) 对图像做不同尺度的高斯模糊,这样得到了一组(Octave)尺度空间;
(2) 对图像做降采样(隔点采样),这样得到了多组尺度空间。
5.1.1. 初步求原始极值点
节 4.1.2 中介绍了使用“尺度归一化 LoG 算子”
其中,
Figure 27: DoG 的计算
在 DoG 中检测特征点的过程和节 4.1.2 中描述的在尺度归一化 LoG 响应中检测斑点过程是相同(即如图 25 所示)。
得到原始极值点的过程可总结为图 28 (摘自http://blog.csdn.net/lhanchao/article/details/52345845 )所示。
Figure 28: SIFT 得到初步极值点过程
注:SIFT 论文中建议采用 4 个 octaves,第个 octave 中采用 5 个高斯模糊层。
5.1.2. 精确定位极值点
在节 2.3 中介绍过,在尺度空间中寻找到的特征点的位置信息往往不够精确。图 29 是一维情况下采样后极值点偏离真正极值点的例子。
Figure 29: 采样后极值点偏离真正极值点
一般,采用“子像元插值(sub pixel interpolation)”的方式来求得更准确的极值点。
首先,我们看一个一维函数插值的例子,如图 30 所示。
Figure 30: 已知离散一维函数值,求取连续一维函数值极值点的例子
在
求
对于 3 维函数
其中:
求
精确定位极值点这个步骤主要进行下面两个处理:
处理一: 如果
处理二: 计算极值点
极值点处的极值
把
5.1.3. 去除不稳定极值点(删除边缘效应)
节 4.2.1 中介绍过通过 LoG 求斑点时,细节结构的斑点(边缘)不会被较好地抑制。边缘是不稳定的,很难定位,应该把它们去掉。SIFT 采用 DoG 来近似 LoG,并没有克服这个缺点,所以我们需要想办法来删除位于边缘部分的极值点。
我们通过极值点邻域的曲率来判断的当前极值点是否在边缘上。在跨越边缘的方向有较大的主曲率,在与边缘相切的方向主曲率较小。
主曲率可以通过下面 2 阶 Hessian 方阵求出:
某点的主曲率和该点的 Hessian 矩阵的特征值是成比例的,因此可以通过 Hessian 矩阵的特征值来确定某点在差分高斯金字塔中的主曲率。
我们可以只关心两个特征值的比例,当比例较小时,说明两个特征值相差不大,从而不同方向的主曲率相关不大。而当两个特征值比例很大时,则说明不同方向的主曲率相关比较大,这样的极值点应该删除。
由于只关心特征值的比例,采用和 Harris 角点检测类似的思路,我们可以避免直接求解 Hessian 矩阵特征值。具体过程如下所述。设 Hessian 矩阵的两个特征值分别为
记
上式左边可通过 Hessian 矩阵求解得到,它仅与两个特征值的比例有关,而与具体特征值无关。当两个特征值相等时,
在 SIFT 论文中,给出的曲率比率阈值
5.1.4. 检测特征点过程演示
图 31 (摘自 SIFT wikipedia )是检测 SIFT 算法检测特征点的过程演示。
Figure 31: 上图为通过 DoG 求得的原始特征点;中图为通过子像元插值,去掉低响应点后的特征点;下图为删除边缘效应后的特征点
5.2. SIFT 特征描述子
在特征点提取之后,如何使用或选择一种合适的特征描述方法来描述特征点附近局部图像模式,便是图像识别过程中又一重要步骤。图像识别过程往往是两幅图像之间进行相似性比较的过程,为了实现相似性度量,使用或选择一种紧凑而完整的特征描述是十分重要的。特征描述子(Descriptor)是一种图像局部结构特征的定量化数据描述,它能够充分反映特征点附近局部图像的形状和纹理结构特性。
5.2.1. 特征点方向分配
为了让特征点具有图像旋转不变性,需要根据检测到的特征点的局部图像结构求得一个方向基准。 我们使用图像梯度的方法求取局部结构的稳定方向。对于已经检测到的特征点,我们知道了该特征点的尺度值
计算以特征点为中心,以
完成特征点邻域的高斯图像的梯度计算后,使用直方图统计邻域内像素的梯度方向和幅值。梯度方向直方图的横轴是梯度方向角,纵轴是梯度方向角对应的梯度幅值累加值。梯度方向直方图将 0-360 度的范围分为 36 个柱(bins),每 10 度为一个柱。 直方图的峰值代表该特征点处邻域内图像梯度的主方向,也即该特征点的主方向。 如图 32 (摘自:http://aishack.in/tutorials/sift-scale-invariant-feature-transform-keypoint-orientation/ )所示。不过,每个累加到梯度方向直方图的采样点的梯度幅值都要进行权重处理,加权采用圆形高斯加权函数,高斯加权函数的
Figure 32: 梯度方向直方图(直方图的峰值代表该特征点的主方向)
如果在梯度方向直方图中存在一个相当于主峰值能量 80%能量的峰值时(如图 32 所示),则将这个方向认为是该特征点的辅方向。一个特征点可能会被指定具有多个方向(一个主方向,一个以上辅方向),这可以增强匹配的鲁棒性,如下图所示。实际编程实现中,就是把该特征点复制成多份特征点,并将方向值分别赋给这些复制后的特征点。通常,离散的梯度方向直方图要进行插值拟合处理,这样可以求得更精确的方向角度值。
在获得了图像特征点主方向
5.2.2. 特征点特征矢量生成
SIFT 描述子是对特征点附近“邻域内高斯图像梯度”统计结果的一种表示,它是一个三维的阵列,但通常在编程将它表示成一个矢量(1维向量),这个矢量是通过对三维阵列按一定规律进行排列得到的。
特征描述子与特征点所在的尺度有关,因此,对梯度的求取应在特征点对应的高斯图像上进行。将特征点附近的邻域划分成
为了保证特征矢量具有旋转不变形,需要以特征点为中心,将特征点附近邻域内图像的梯度的位置和方向旋转一个方向角
Figure 33: 将特征点附近邻域内图像梯度的位置和方向旋转方向角
特征点邻域划分成
Figure 34: SIFT 特征矢量由 128 维矢量组成
特征向量形成后,记为
非线性光照,相机饱和度变化可能造成某些方向的梯度值过大,而对方向的影响微弱。因此设置门限值(向量归一化后,一般取门限值为0.2)截断较大的梯度值,即大于0.2的值只取为0.2。然后,再进行一次归一化处理。