[科普中国]-兴趣点算子

兴趣点

点特征又被称作为兴趣点，指的是图像中具有特殊性质的像素点，是图像的重要特征。它具有旋转不变性和不随光照条件变化的优点。一些图像处理中利用点特征进行处理既可以减少计算量又不会损失重要的灰度信息。经过对它们执行局部分析，如果能够检测到足够多的这种点，同时它们区分度很高，并且可以精确定位稳定的特征。这类点被大量用于解决物体识别，图像匹配，视觉跟踪，三维重建等问题。

点特征主要指图像中的明显点，如建筑物角点、边缘两端、折点等，在图像匹配和遥感影像定位中很有用。常用的提取方法有边缘提取法、角点检测法、兴趣算子法等，方法虽然不同，但基本原则都是选择局部灰度变化最大点作为特征点，这样可以保持特征点邻域内的纹理细节，减少后续的误匹配率。用于点特征提取的算子称为有利算子或兴趣算子。针对点特征的提取的算子也有很多，自20世纪70年代以来出现一系列各不相同、各有特色的兴趣算子，知名的有Moravec算子、Hannah算子与Foistner等。

检测Harris角点角点角点原理来源于人对角点的感性判断，即图像在各个方向灰度有明显变化。算法的核心是利用局部窗口在图像上进行移动判断灰度发生较大的变化，所以此窗口用于计算图像的灰度变化为：

[-1,0,1;-1,0,1;-1,0,1]、[-1,-1,-1;0,0,0;1,1,1]

人各个方向上移动这个特征的小窗口，如图1中窗口内区域的灰度发生了较大的变化，那么就认为在窗口内遇到了角点。如图1中，窗口内图像的灰度没有发生变化，那么窗口内就不存在角点；如果窗口在某一个方向移动时，窗口内图像的灰度发生了较大的变化，而在另一些方向上没有发生变化，那么，窗口内的图像可能就是一条直线的线段。1

数学模型根据算法思想，构建数学模型，计算移动窗口的的灰度差值。

将图像窗口平移 产生灰度变化

其中， 为窗口函数，常选用下图的窗口：

为了减小计算量，利用泰勒级数进行简化公式：

其中，

定义自相关矩阵A=

在上式中，w表示窗口函数。对于矩阵A可以进行对称矩阵的变化，假设利用两个特征值进行替代，其几何含义类似下图中的表达。在几何模型中通过判断两个特征值的大小，来判定像素的属性。

在实际应用中为了能够应用更好的编程，定义了角点响应函数R，通过判定R大小来判断像素是否为角点。

R取决于A的特征值，对于角点|R|很大，平坦的区域|R|很小，边缘的R为负值。

算法流程1）利用水平，竖直差分算子对图像的每个像素进行滤波以求得Ix、Iy，进而求得M中的四个元素的值。

2）对M的四个元素进行高斯平滑滤波，为的是消除一些不必要的孤立点和凸起，得到新的矩阵M。

3）接下来利用M计算对应每个像素的角点响应函数R

4）局部极大值抑制，同时选取其极大值

5）在矩阵R中，同时满足R(i,j)大于一定阈值threshold和R(i,j)是某领域内的局部极大值，则被认为是角点。

检测FAST特征Harris算子是基于两个正交方向上的强度变化率提出了角点。

而FAST特征算法对角点的定义有所不同，它定义基于假定特征点周围的图像强度，通过检查候选像素周围一圈像素来决定是否接受一个特征点。与中心差异较大的像素如果组成连续的圆弧，并且弧长大于圆周长度的3/4，那么我们认为找到一个特征点。和Harris特征相同的是可以在找到的角点上执行非极大值抑制，因此需要指定角点强度的测量方法。该算法可以获得非常快速的特征点检测，在需要考虑运行速度时可以选用，如高帧率的视频序列中进行视觉跟踪。

FAST算法的步骤

FAST的提出者Rosten等将FAST角点定义为：

若某像素与其周围邻域内足够多的像素点相差较大，则该像素可能是角点**。**

**1）**上图所示，一个以像素p为中心，半径为3的圆上，有16个像素点（p1、p2、...、p16）。

**2）**定义一个阈值。计算p1、p9与中心p的像素差，若它们绝对值都小于阈值，则p点不可能是特征点，直接pass掉；否则，当做候选点，有待进一步考察；

**3）**若p是候选点，则计算p1、p9、p5、p13与中心p的像素差，若它们的绝对值有至少3个超过阈值，则当做候选点，再进行下一步考察；否则，直接pass掉；

**4）**若p是候选点，则计算p1到p16这16个点与中心p的像素差，若它们有至少9个超过阈值，则是特征点；否则，直接pass掉。

**5）**对图像进行非极大值抑制：计算特征点出的FAST得分值（即score值，也即s值），判断以特征点p为中心的一个邻域（如3x3或5x5）内，计算若有多个特征点，则判断每个特征点的s值（16个点与中心差值的绝对值总和），若p是邻域所有特征点中响应值最大的，则保留；否则，抑制。若邻域内只有一个特征点（角点），则保留。2

SURF特征基本原理SURF(Speeded Up Robust Features)，是SIFT角点检测算法的改进版，主要体现在速度上，SURF是SIFT速度的3倍。SIFT在尺度和旋转变换的情况下匹配效果比SURF好，而SURF在亮度变化下匹配效果比较好。

与SIFT的区别在于：

尺度空间的建立：SIFT建立一幅图像的金字塔，在每一层上进行高斯滤波并求取DoG进行特征点的提取，而SURF用的是Hessian矩阵。

SIFT特征建立图像金字塔处理尺度不变特性，而SURF特性将高斯核近似为方形滤波。3

算法流程1）构建Hessian矩阵，计算H矩阵判别式，判断是大于0还是小于0；

2）构造尺度空间：不同尺度的box filters与原图片卷积，使原始图像保持不变而只改变滤波器的大小。

3）精确定义特征点：先利用Hessian矩阵确定候选点，然后进行非极大抑制。

4）特征点描述子的生成：在圆形区域内，计算各个扇形范围内x、y方向的haar小波响应，找模最大的扇形方向；20*20s的区域划分为4*4的子区域，每个子区域找5*5个采样点，计算采样点的haar小波响应，记录∑dx,∑dy,∑|dx|,∑|dy|，一共4*4*4=64维。