特征点检测

特征检测

局部特征点的要求

可重复性和正确性：平面内几何变换不变，平面外几何变化不变，光照鲁邦。

局部性：特征是局部的，对遮挡物不敏感。

数量：要有足够多的特征点/区域来覆盖整个物体

特异性：区域需包含“感兴趣的”结构

有效性：接近实时

特征响应

在任何方向移动窗口，灰度值有较大的改变。

灰度改变度量/特征响应度量

基于灰度

优点：直接用图像灰度值，计算速度块，对噪声不敏感。

角点：特征点与其邻域内足够多的像素点处于不同区域

FAST

邻域Np：Bresenham圆上的16个像素。

特征响应度量：圆上有n个连续的像素点的灰度值都大于或小于中心点的值。

16个像素的轮询顺序决定检测速度（决策树决定轮询顺序）

ORB

在FAST基础上加速。

邻域Np：只包括上下左右四个像素点，效果与和16个像素比较相同。

特征响应度量：至少有一对连续像素的灰度高于I_p+t或小于I_p-t则将p作为关键点。

搜索时间缩减了四倍。

使用图像金字塔保证尺度不变。

使用执行标定方向保证旋转不变。

基于灰度一阶导数——Harris角点检测器

角点

两条直线的交点，轮廓的高曲率点。

窗口函数w(x,y)

可以是二值（窗口内为1，窗口外为0），也可以是高斯函数。

移动后[u,v]灰度值的变换SSD

梯度近似SSD

使用泰勒展开，变化后的灰度值 近似为 变化前的灰度加上梯度。

   

I_x为x方向梯度，I_y为y方向梯度。

自相关矩阵

 

自相关矩阵特征值与变化率的关系

M的特征向量决定方向，特征值λ的大小决定与特征值λ对应特征向量的模长。

在SSD中，特征向量的模长可以视为变化的快慢，也就是特征值越大，变化越快。

特征向量决定方向，特征值决定变化快慢。

特征值1表示水平方向变化率，特征值2表示竖直方向变化率。

在水平边缘上，特征值2远大于特征值1。在竖直边缘上，特征值1远大于特征值2。

在角点，任意方向的变化率都非常大，故所有的特征值都很大。

Harris角点检测器

Harris角点检测器中，因为计算特征值分解的计算量大，不直接计算特征值。

利用公式，将对特征值的运算，转换为对矩阵元素的运算

利用自相关矩阵

R=ac-b²-α(a+c)²

Harris角点检测器步骤

1.计算图像x方向和y方向的梯度I_x，I_y（梯度）

2.计算每个像素点的梯度的乘积。（梯度乘积）

3.计算每个像素点的梯度的乘积的累积（直接用每个像素点梯度乘积的累积求自相关矩阵M，这里使用高斯核）（累积梯度）

x方向梯度乘积累积，x方向和y方向梯度乘积的累积，y方向的梯度乘积累积。

4.定义每个像素点的矩阵M（自相关矩阵）

5.计算每个像素点的角点响应R

6.对响应R做阈值处理和非极大值抑

基于灰度的二阶导数

Harris角点检测器的问题

Harris具有平移不变性，旋转不变性，但是不具有尺度不变性

自动尺度选择

理想的特征尺度函数是突出剧烈的图像不连续性：图像与突出边缘核进行卷积。高斯核的拉普拉斯算子（LoG）是最优的。

因此在高斯金字塔/拉普拉斯金字塔上计算LoG。

二维高斯核拉普拉斯算子

一阶导

二阶导

高斯核的拉普拉斯算子LoG的导数进行卷积分析（为了简便，以一维为例）

使用高斯拉普拉斯LoG一阶导进行卷积时，边缘点就是响应值最大的点。

使用高斯拉普拉斯LoG二阶导进行卷积时，边缘点就是响应值过0的点。

LoG斑点检测

假设一组一维的像素出现斑点，也就是某段区域灰度突然变大。（这里为了简便）

从上述推论可知，使用高斯核的拉普拉斯算子（二阶导）进行卷积的时候，过0点就是其边缘点。

所以在检测斑点的时候，要检测各个边界，也就是过0点。

但是使用不同σ的LoG，得到的过0点位置不同。

当LoG的尺度与斑点的宽度匹配时，LoG的幅值在斑点的中心取得最大值。

  

因为σ可以调节的，所以LoG算子可以检测不同尺寸图片上的斑点。

二维上的过0点的响应最大值（例如一个圆）

LoG的过0点应该和圆对齐，从而推导出合适的σ参数。

所以有如下结论

边缘：灰度值跃迁，与二阶LoG卷积后的过0点。

斑点：两个阶跃之间的区域，也就是两个过0点之间的区域。

本征尺度：调整σ，过0点逐渐靠近，最终合并成一个最大值，得到的响应最大尺度。

目标：使得两个过0点逐渐接近，逐渐形成最大值，这个最大值就是斑点。

LoG可以通过调整σ，检测到不同尺寸图像的斑点。

斑点检测基本步骤

求二维LoG的梯度

再做归一化（归一化见下一节推导）

找到响应最大的尺度，也就是找到合适的σ

代入归一化的LoG即可求得。

归一化的高斯核拉普拉斯算子

用不同尺度的LoG和信号卷积，寻找幅值的最大值，选择最佳尺度。

但是随着尺度的增大，LoG的曲线由双波谷逐渐融合成单波谷。且最大幅度逐渐减小，响应尺度也不断减少，无法判断尺度是否合适，因此需要进行尺度归一化

归一化方式：对于一阶高斯核的导数的响应值乘以σ，保证σ不变。对于二阶高斯核的导数的响应值乘以σ²，从而对σ不变。

  

尺度归一化后的效果

尺度不变检测器DoG（Difference of Gaussian）

可以将LoG近似为DoG计算效率更高

检测尺度归一化的LoG在尺度空间的极值，近似于检测DoG在尺度空间的极值，且DoG效率更高。

DoG与LoG的关系

k-1是常量，不影响函数极值点

k的选择

k趋近于1时，近似程度越高，但是需要计算更多的DoG

方向归一化

根据图像梯度计算特征主方向θ。然后旋转图像，使得主梯度方向为水平方向。

设高斯图像L的尺度为σ，以(x₀,y₀)为中心，半径为r=3x1.5σ内的点，计算梯度幅值和角度。

梯度幅值：

角度：

方向直方图：梯度幅度值高斯加权

主方向：直方图最大的箱子表示方向

 

对方向进行旋转

 

 

在实际应用中，是以特征点为圆心，半径为：

高斯核的方差为：

 

 

Lowe的SIFT基本步骤

构造尺度空间——高斯金字塔：使用高斯函数和与原图像卷积，然后下采样

尺度空间极值检测：使用DoG检测。

关键点定位：检测到的关键点是离散空间的极值点，但是在连续空间的极值有偏差。

剔除低对比度关键点：利用公式判断哪个点应该保留。

剔除边缘响应：使用DoG算子，建立Hessian矩阵，det(H)和trace(H)的比值要小于一定阈值。

方向归一化

构造高斯金字塔

对图像采用不同尺度σ的高斯函数进行平滑。

平滑操作会减少图像中的高频信息。这样也就没必要再用相同数量的像素表示，可以缩小尺寸。对图像进行下采样，逐渐形成金字塔。

平滑图像

相邻金字塔的尺度因子为2倍。

注：大尺度的高斯平滑可通过连续小尺度σ1，σ2高斯平滑，这样可以加速卷积运算。

L(x,y,σ) = g(σ) * I(x,y) = [ g(σ₁) * g(σ₂) ] * I(x,y)  = g(σ₁) * [ g(σ₂)*I(x,y)  ]，其中σ²=σ₁²+σ₂²

下采样

水平和竖直分辨率变为原来的一半

  

初始

预先模糊输入图像作为第0组第0层图像，相当于丢弃了最高的空域的采样率。

SIFT中Lowe将初始图像的尺度设定为σ_-1=0.5，先将图像的尺度扩大一倍，生成第-1组图像。

构造图像金字塔

尺度空间：八度(o)和八度中的第几层(s)组成尺度空间。

一个八度中图像的长宽都相等，也就是变量八度控制图像尺寸。

一个八度中不同层(s)的图像模糊程度不同，也就会层(s)控制模糊程度。

每个八度（Octave）内有S+3层（Interval）。

相邻八度尺度相差2倍，同一组相邻层尺度相差k倍。

第0个八度的尺度：

σ₀,kσ₀,...,k^sσ₀,k^s+1σ₀,k^s+2σ₀

第1个八度的尺度：

2 σ₀,2 kσ₀,...,2 k^sσ₀,2 k^s+1σ₀,2 k^s+2σ₀

第2个八度的尺度：

4 σ₀,4 kσ₀,...,4 k^sσ₀,4 k^s+1σ₀,4 k^s+2σ₀

_....

第n个八度的尺度：

2ⁿ σ₀,2ⁿ kσ₀,...,2ⁿ k^sσ₀,2ⁿ k^s+1σ₀,2ⁿ k^s+2σ₀

上一个八度的导数第三层 和 下一个八度的第0层相同：

也就是

k^sσ₀=2 σ₀，得到：

构造高斯差分金字塔

在高斯金字塔中，每两个相邻层进行相减，生成了高斯差分金字塔。

第一个八度中高斯差分图像的尺寸为：（系数2都是n/3次方）

第二个八度中高斯差分图像的尺寸为：

 

极值点检测

每个八度的S+3个金字塔图像，得到S+2DoG图像，只能检测S个尺度的极值点。

Lowe建议S=3，也就是检测同尺度的8个相邻点，和上下相邻尺度对应的18个点，一共26个点进行比较。

关键点定位——插值

上述检测到到的极值点都是离散空间的极值点。而连续空间的极值点，也就是曲线的极值点如红色点所示。

因此可以通过拟合一条曲线的方式来将离散的点连续化，这种方式也称为子像素插值。

DoG响应函数在尺度空间的二阶泰勒展开：

对Δx求导，并令其为0，得到精确位置：

去除低对比度的点：

若大于等于0.03，则保留下。

 

 去除边缘效应

DoG算子会产生较强的边缘响应，需要剔除不稳定的边缘响应点。

       类似于Harris角点检测器，使用DoG算子定义Hessian矩阵

  

为了能够剔除边缘点，det(H)和trace(H)的比值要小于一定阈值：

通常r取10。

方向归一化

将特征点附近分为 d x d = 4 x 4 =16个子区域

角度分为8等份，特征维度为4x4x8=128维

SIFT算子劣势

实时性差

有时候特征点少

若目标的边缘光滑，则无法准确提取特征点。

因为描述子由梯度组成，所以对光照不敏感，光照鲁棒性强，可处理较大的亮度变化。

可以处理视角的变化。

改进

SURF比SIFT快6倍

ORB比SIFT快2个数量级

特征描述

目的

提取感兴趣周围的特征向量描述

 

特征描述

图像块

将图片周围的灰度值，转换为1维的灰度向量

模板距离

差值平方和（SSD）

差值绝对值之和

归一化互相关（NCC）  

对灰度值变化敏感。

图像梯度

优点：特征对灰度的绝对值不变

缺点：但对几何变形敏感

灰度/颜色直方图

直方图交

直方图X²距离

优点：对尺度和旋转不变

缺点：对空间布局不敏感

空间直方图

将图片分割为一个个小区域，计算每个区域的直方图

描述子

BRIEF描述子

属于二进制的描述子，所以计算和匹配速度都特别快。

使用汉明距离作为相似度量。

图像平滑时，方差为2，窗口为9x9

领域内随机采样n=256个点对(p_i,q_i)，比较每个点对(p_i,q_i)的灰度值，从而得到第i维特征描述值为：

ORB描述子

采用统计机器学习，从邻域所有M种可能的像素点对中选择最佳的。

BRISK描述子

二值编码

像素点对采样方式：径向对称方式

FREAK描述子

二值编码

像素点采样时，*凹区域更多采样（像视网膜）

像素点选择类似ORB

 

特征检测——边缘/轮廓

从特征点检测中的斑点检测部分可以发现，源图像与LoG一阶导数卷积时，边缘为局部极值。

二维高斯滤波器的微分

X方向

Y方向

边缘信息

边缘强度

梯度的模长

梯度方向

与边缘垂直的方向

Canny边缘检测

1.使用高斯一阶导数进行卷积，得到x，y方向梯度。

2.计算梯度的幅值和方向

3.非最大值抑制

将多个像素宽细化为单个像素宽度

在梯度的方向（垂直与边缘），沿着梯度方向比较，如果有幅值比自己大的，则自己设置为非边缘，如果没有则自己就是边缘。

  

 

4.阈值和连接

尽管经过非最大值抑制，但是仍然有噪声。可以从强边缘开始连接边缘像素。

设置较大的阈值T保留强的边缘，设置较小的阈值t保留和强边缘相连的弱边缘。

特征检测——直线

直线拟合

基本方式

类似于线性回归，给定一系列样本点，找得到合适的参数k和b

挑战

平方误差对噪声敏感。

无关数据：不知道模型是哪些部分，

缺失数据

费用

Hough变换

基本思想

采取投票机制，将参数空间作为多个箱子，对于已存在的特征点，看哪个箱子能能够生成这些特征点最多。

图像和参数空间

处于同一条直线上的点，其在参数空间的直线都是交于一点的。有直角坐标形式和极坐标形式。

Hough变换检测直线（直角坐标）

给定空域中的点（边缘点）的集合，计算出经过这些点的直线。

设置参数网格(k,b)，初始化网格对应的累积计数器A(k,b)=0。

对图像中的每个边缘点的位置(x_i,y_i)，在参数网格中遍历，若累积计数器A(k,b)在线b=y_i-kx_i上，对应位置计数器加一。

寻找参数网格累积器最大的值。

根据找到的局部最大值对应的点重新匹配直线。

缺陷：k和b的空间可能从负无穷到正无穷。

Hough变换检测直线（极坐标）

给定空域中的点（边缘点）的集合，计算出经过这些点的直线。

设置参数网格(r,θ)，初始化网格对应的累积计数器A(r,θ)=0。

对图像中的每个边缘点的位置(x_i,y_i)，对θ=0,...,π中的每个元素，判断r=x_icosθ+y_isinθ，若相等，则累积器加一

寻找参数网格累积器最大的值。

根据找到的局部最大值对应的点重新匹配直线：r=xcosθ+ysinθ

使用局部最大值原因：因为有很多条直线，这些直线上的点在参数空间的直线都交于一个点，因此参数空间每个交点代表一个直线，所以要使用局部最大值，而不是全局最大值，全局最大值的话只会保留一条直线。

优点：θ的范围限制在了0到π

  

圆的Hough变换

圆的半径r已知，在图像空间参数为圆心坐标，在参数空间参数为x，y。

参数空间中的1个圆，对应参数空间中的1个点。如果图像中多个点在一个圆上，则参数空间上是多个对应的圆的交点为圆心位置。

参数缺失情况

若半径未知，参数空间则是3维。

梯度方向θ已知，半径已知，只要对两个点搜索

梯度方向已知，但半径未知，要对两条直线搜索

d个参数对应的网络：k₁ x k₂ x ... x k_d，共k^d个元素

Hough变换优点

简单

能处理遮挡（对遮挡的处理思路可以参考Hough）

能检测多个实例

对噪声鲁棒

Hough变换的缺点

只能处理参数较少的情况

搜索时间随着参数的数目呈现指数增长，计算复杂度高。

不易设置参数。