计算机视觉之一：特征检测

主要内容：

1、一个例子解释为什么要进行特征检测

2、图像特征

3、点特征检测：Harris角点、MOPS、SIFT

4、边缘检测：一阶微分算子、二阶微分算子、Canny算子

一、为什么要检测特征？

举一个例子：全景图像拼接，给定两张图像，如何拼接成一张大图？

步骤一：检测特征点

步骤二：匹配特征点

步骤三：图像适配

二、图像的特征有哪些？

计算机视觉中常用的图像特征包括：点、边缘、直线、曲线等

三、点特征检测

1、点特征的优势：

点特征属于局部特征，对遮挡有一定鲁棒性；

通常图像中可以检测到成百上千的点特征，以量取胜；

点特征有较好的辨识性，不同物体上的点容易区分；

点特征提取通常速度很快；

2、什么是好的点特征？

考虑图像上的一个小窗口，当窗口位置发生微小变化时，窗口图像如何变化？

很明显，从下图可以看出，角点是一个好的点特征，因为它沿任意方向移动，窗口的灰度变化明显，所以它可以作为一个特征来进行区分和辨别。

3、点特征的数学表达

假设窗口W发生位置偏移(u,v);
比较偏移前后窗口中每一个像素点的灰度变化值；
使用误差平方和定义误差函数E(u,v)

不同位置点计算得到的E(u,v)如下图所示，E(u,v)值随着u、v变化的效果图，可以看出，平坦区域（如天空）的灰度变化不大（下图3），边缘区域沿着边缘方向的灰度变化.

也很小（下图2），只有角点处的灰度变化稍微剧烈一点（下图1）

　　误差函数E(u,v)：

将I(u,v)进行Taylor展开：

进一步展开，写成：

H称为自相关矩阵，和是H的2个特征值，E(u,v)的变化如下图所示：

根据H的2个特征值大小对图像点进行分类：

角点应该满足的基本性质：最小特征值尽量大

角点响应：

比更有效的角点响应函数：

四、点特征检测：Harris角点

算法步骤：

将原图像I使用w(x,y)进行卷积，并计算图像梯度I_x与I_y；
计算每个图像点的自相关矩阵H；
计算角点响应；
选择R大于阈值且为局部极大值的点作为角点。

Harris角点改进：

Harris检测子获得的角点可能在图像上分布不均匀（对比度高的区域角点多）

改进方法：Adaptive non-maximal suppression（ANMS），只保留半径r内角点响应比其他点大10%的点作为角点。（Brown，Szeliski and Winder，2005）

Harris角点的性质：

1. 旋转不变：

椭圆转过一定角度但是其形状保持不变（特征值保持不变）

2. 光照变化不变：

只使用了图像导数，对于光照线性变化不变

3. 对比度变化部分不变：

4. 对于图像尺度变化不具有不变性：

五、点特征检测：MOPS

MOPS：Multi-scale oriented patches

尺度不变：在多层图像金字塔上检测角点，在同一层进行匹配

MOPS局限：待匹配的图像需要尺度近似

六、点特征检测：SIFT

Scale Invariant Feature Transform （SIFT）（Lowe，2004）

主要内容：

1.SIFT算法特点

2.SIFT算法流程

3.SIFT算法的具体步骤

4.SIFT点的特点

1、SIFT算法的特点：

不变性：

——对图像的旋转和尺度变化具有不变性；

——对三维视角变化和光照变化具有很强的适应性；

——局部特征，在遮挡和场景杂乱时仍保持不变性；

辨别力强：

——特征之间相互区分的能力强，有利于匹配；

数量较多：

——一般500*500的图像能提取约2000个特征点。

2、SIFT算法的流程：

在高斯差分（Difference of Gaussian，DOG）尺度空间中提取极值点并进行优化，从而获取特征点。

3、SIFT算法点检测的具体步骤：

——构建尺度空间；

——构造高斯差分尺度空间；

——DoG尺度空间极值点检测；

——特征点精确定位；

——去除不稳定点；

构建尺度空间：模拟图像数据的多尺度特征

其中是尺度可变高斯函数

尺度参数决定图像的平滑程度，大尺度对应图像的概貌特征，小尺度对应图像的细节特征

构造高斯差分尺度空间（Difference of Gaussian，DOG）

为了在尺度空间中检测稳定的关键点，构造高斯差分尺度空间

使用DOG的几个理由：

1. 计算效率高：高斯卷积，减法；

2. 高斯差分是对尺度归一化LoG的一个很好的近似，而尺度归一化的LoG空间具有真正的尺度不变性（Lindegerg 1994）；

3. 实验比较表明，从尺度归一化LoG空间中提取的图像特征的尺度稳定性最好，优于梯度、Hessian或Harris角点函数。

DoG尺度空间：

DoG尺度空间极值点检测：

一个点和它同尺度的8个相邻点以及上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。
一个点如果在DOG尺度空间的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点。
一个特征点是在三维尺度空间的局部极值点。

特征点精确定位：

一个特征点是在三维尺度空间的局部极值点。但(x,y)为整数像素，为离散尺度，需要对DoG空间拟合进行特征点精确定位。

将的特征点处二阶Taylor展开：

对上式求导，并令其为0，得到精确的位置（偏移量）：

若中的三个变量任意一个偏移量大于0.5，说明精确极值点更接近于另一个特征点，则更换特征点重复上述精确定位流程。

去除不稳定特征点：

——去除对比度低的点：

计算极值点取值，若，则保留该特征点，否则丢弃。

——去除边缘点：

DoG算子会产生较强的边缘响应，利用Harris检测子判断。

若，则保留该特征点，否则丢弃。

4、SIFT点的特点：

视角和旋转变化不变性：

光照不变性：

尺度不变性：

七、点特征检测：小结

根据自相关矩阵特征值检测角点(Harris)； Harris角点具有旋转、光照不变性，但不具有尺度不变性。
高斯差分尺度空间中检测尺度不变特征点(SIFT)； SIFT具有尺度不变性。
Harris与SIFT的机理不同，因此可以联合使用，互为补充。

八、边缘检测

主要内容：

1.图像梯度

2.一阶微分算子

3.二阶微分算子

4.Canny算子

1、为什么要检测边缘？

一个例子：基于边缘的图像编辑

2、图像边缘的产生

物体的边界、表面方向的改变、不同的颜色、光照明暗的变化

3、边缘检测——图像梯度

图像梯度的定义：

水平梯度：

垂直梯度：

图像梯度指向灰度变化最快的方向：

梯度幅值表示边缘的强弱：

边缘是一阶倒数的极大值点：

4、边缘检测——一阶微分算子

使用差分近似一阶微分算子：

直接对图像使用差分容易受到噪声影响：

解决方法：先平滑，再微分

由，可将平滑和微分合为一个算子

二维高斯微分：

实际应用中：对二维高斯微分进行数值近似：Prewitt算子、Sobel算子

Prewitt算子：去噪+ 增强边缘

Sobel算子：去噪+ 增强边缘（给四邻域更大的权重）

使用一阶微分算子提取边缘流程：
1. 使用Prewitt或Sobel算子对图像进行卷积；
2. 将梯度幅值大于阈值的点标记为边缘；
3. (optional)将边缘细化为一个像素宽度。

5、边缘检测——二阶微分算子

如果不使用细化，如何获得单像素宽度边缘？

边缘是一阶倒数的极大值点

边缘是二阶倒数的过零点
注意：仅仅等于0不够，常数函数也为0，必须存在符号改变

对平滑图像做二阶微分：

二维高斯微分：

Laplacian of Gaussian (LoG)算子：首先用Gauss函数对图像进行平滑，抑制噪声，然后对经过平滑的图像使用Laplacian算子
LoG算子等效于：Gaussian平滑+ Laplacian二阶微分

LoG因其形状，也称为Mexican hat

LoG算子与一阶微分算子的比较：

LoG算子的特点：
• 正确检测到的边缘：单像素宽度，定位准确；
• 形成许多封闭的轮廓，这是一个主要问题；
• 需要更加复杂的算法检测过零点。

6、边缘检测——Canny算子

Canny算子是最常用的边缘检测算子

Canny算子是一阶微分算子，但是一个优化的方案
-单像素宽度
-噪声抑制
-边缘增强
-边缘定位
J.Canny, “A Computational Approach to Edge Detection”, IEEE Trans. on PAMI, 8(6),1986.
18482 cites

Canny算子基本流程

（1）高斯平滑滤波器卷积

（2）使用一阶有限差分计算偏导数的两个阵列

相当于与模板进行卷积运算：

当然也可以使用高斯微分算子(Prewitt或Sobel)直接与卷积计算和

（3）边缘幅值和边缘方位角

M代表梯度幅值的大小，在存在边缘的图像位置处，
M的值变大，图像的边缘特征被“增强”。

（4）梯度非极大值抑制

局部极值周围存在相近数值的点：

非极大值抑制（NMS：Non-Maxima Suppression）
主要思想：

由梯度幅值图像，仅保留极大值（严格地说，保留梯度方向上的极大值点）。

具体过程：

1.初始化；

2.对于每个点，在梯度方向和反梯度方向各找n个像素点。若不是这些点中的最大点，则将置零，否则保持不变。

在梯度方向的沿线上检测该点是否为局部极大值；

简化的情形，只使用4个方向：【0,45,90,135】；

得到的结果包含边缘的宽度为1个像素；

（5）对NMS结果进行阈值二值化—双阈值检测

使用大的阈值，得到：
-少量的边缘点
-许多空隙

使用小的阈值，得到：
-大量的边缘点
-大量的错误检测

两个阈值T1，T2：T2 >> T1

由T1得到，低阈值边缘图：更大的误检测率
由T2得到，高阈值边缘图：更加可靠

（6）边缘连接
1. 将中相连的边缘点输出为一幅边缘图像；
2. 对于中每条边，从端点出发在中寻找其延长的部分，直至与中另外一条边的端点相连，否则认为中没有它延长的部分；
3. 将作为结果输出。

Canny算子流程效果图：

• Canny算子的优点
-参数较少
-计算效率
-得到的边缘连续完整
• 参数的选择
-Gauss滤波的尺度
-双阈值的选择(LOW=HIGH*0.4)

Canny算子的处理效果：

九、总结

• 根据自相关矩阵特征值检测角点(Harris)；
• 高斯差分尺度空间中检测尺度不变特征点(SIFT)；
• 一阶高斯微分算子(Prewitt、Sobel)极值检测边缘；
• 二阶高斯微分算子(LoG)过零点检测边缘；
• 非极大值抑制+双阈值检测边缘(Canny)。

十、特征检测参考文献

• Harris, C. and Stephens, M. J. A combined corner and edge detector. In Alvey Vision Conference, 1988.
• Lowe, D. G. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2):91–110, 2004.
• Canny, J. A computational approach to edge detection. IEEE Transactions onPAMI, 8(6):679–698, 1986.
• Tuytelaars, T. and Mikolajczyk, K. Local Invariant Feature Detectors: A Survey. Foundations and Trends in Computer Graphics and Vision, 3(3): 177–280, 2007.