CV（一）

角点定义

角点（corner point）通常被定义为两条边的交点，更严格的说，角点的局部邻域应该具有两个不同区域的不同方向的边界。而在实际应用中，大多数所谓的角点检测方法检测的是拥有特定特征的图像点，而不仅仅是“角点”。这些特征点在图像中有具体的坐标，并具有某些数学特征，如局部最大或最小灰度、梯度特征等。

现有的角点检测算法并不都十分的鲁棒。很多方法要求有大量的训练集和冗余数据来防止或减少错误特征的出现。角点检测方法的一个很重要的评价标准是对多幅图像中相同或者相似特征的检测能力，并且能够应对光照变化、图像旋转等图像变化。

在我们解决问题时，往往希望找到特征点，“特征”顾名思义，指能描述物体本质的东西，还有一种解释就是这个特征微小的变化都会对物体的某一属性产生重大的影响。而角点就是这样的特征。

一般我们认为，角点=兴趣点=关键特征点

关于角点的具体描述可以有以下几种：

• 一阶导数（即灰度的梯度）的局部最大所对应的像素；
• 两条及两条以上边缘的交点
• 图像中梯度值和梯度方向的变化速率都很高的点
• 角点处的一阶导数最大，二阶导数为0，指示物体边缘变化不连续的方向。

角点检测算法

基本思想

算法基本思想是使用一个固定窗口在图像上进行任意方向上的滑动，比较滑动前和滑动后两种情况，窗口中的像素灰度变化程度，如果存在任意方向上的滑动， 都有着较大灰度变化，那么我们就可以认为该窗口中存在角点。

目前的角点检测算法可归纳为3类：

• 基于灰度图的角点检测
• 基于二值图像的角点检测
• 基于轮廓曲线的角点检测

数学方法刻画角点特征：

$$E(u,v)=\sum_{x,y}w(x,y)[I(x+u,y+v)-I(x,y)]^{2}$$

公式解释：

• [u,v]是窗口的偏移量
• （x，y）是窗口内所对应的像素坐标位置，窗口有多大就有多少个位置
• w(x,y)是窗口函数，最简单情形就是窗口内的所有像素所对应的w权重系数均为1.但有时候，我们会将w(x,y)函数设定为窗口中心为原点的二元正态分布。如果窗口中心点是角点时，移动前与移动后，该点的灰度变化应该最为剧烈，所以该点的权重系数可以设定大些，表示窗口移动时，该点在灰度变化贡献较大；而离窗口中心（角点）较远的点，这些点的灰度变化几近平缓，这些点的权重系数，可以设定小点，以示该点对灰度变化贡献较小，那么我们自然想到使用二元高斯函数来表示窗口函数。

角点检测算法

Moravec角点检测算法（参考文献[1]）

这是一种最早的角点检测算法。尽管这种算法实用性差，但它是许多算法的基础。该算法将角点定义为具有低“自相关性”的。算法检测图像的每一个像素，将图像周边的一个邻域作为一个窗口，并检测这个窗口和周围其他窗口的相关性。这种相关性通过两个窗口间的平方差之和（SSD）来衡量，SSD值越小则相似性越高。

上图为可能遇到的三种情况。如果像素位于平滑图像区域内，周围的窗口都会非常相似.如果像素在边缘上，则周围的窗口在与边缘正交的方向上会有很大的差异，在与边缘平行的方向上则较为相似。而如果像素是各个方向上都有变化的特征点，则周围所有的窗口都不会很相似。

基本公式为：$E(u,v)=\sum_{x,y}w(x,y)[I(x+u,y+v)-I(x,y)]^{2}$

Moravec的原理如果有一句话就是：通过滑动二值矩阵窗口寻找灰度变化的局部最大值。
简单理解就是，首先，计算每个像素点的兴趣值，即以该像素为中心，取一个w*w的方形窗口，计算0度、45度、90度、135度四个方向（有些会考虑8个方向）灰度差的平方和，取其中的最小值作为该像素的兴趣点。实际一些算法用水平或对角线上的一个方向灰度差的平方和来近似替代。

具体主要包括四个过程：
1.滑动窗口计算灰度变化

上图中，红色框为原始框，而蓝色框表示右上的滑动框。白色框表示前景255，黑色框表示背景0.那么原始框和滑动框的灰度变化通过对应位置差的平方和来表示，即$V=\sum_{i=1}^{9}(A_{i}-B_{i})^2$
同样根据上式计算另外几个方向的滑动框的灰度变化。
2.构造角点映射图

在构造角点映射图前我们先分析一下，通过上式我们凭什么可以检测到角点，看下图

上面四张图中的四个红色框表示我们正在处理的框，第一幅图中的窗表示在目标内部或者背景上，该区域灰度分布均匀。第二幅图中的窗跨在图像的边缘处，当垂直于边缘方向滑动时会导致灰度很大的变化，而沿着边缘滑动窗时，灰度变化较小。第三幅图中的窗在角点处，不管往哪个方向滑动窗口都会导致灰度的很大变化。而第四幅图框内是一个离散点，滑动窗向任何方向滑动也会导致灰度的很大变化。

因此通过上面的描述和分析，我们知道，Moravec算子可以作为一种角点性的度量，这种度量通过求各个方向的滑窗的最小值来表示。

$$C(x,y)=min(V_{u,v}(x,y))$$

我们通过下图来描述角点映射图（the cornerness map）的构造：

上图中的通过Moravec算子计算得到的，其中1表示$1×255^2$,2表示$2×255^2$，通过上图可知：

• 角点位于局部最大值处，我们可以应用非极大值抑制找到局部最大值（找到真正的角点，因为该点周围可能也有超过阈值的点。）。
• 离散点（噪声点）与角点有相同的角点性，因此Moravec算子对噪声敏感，但通过增大滑窗的大小可以对噪声起到一定的抑制作用，然而同时增加了计算量。另一方面，可以通过设定一个阈值对cornerness map进行二值化，小于阈值的T的cornerness map设置为0，从而对离散点的局部最大值进行抑制。
• Moaravec 算子不能应用于图像边界的一定区域（标记为X的区域），对于这部分的区域，一般直接忽略，在cornerness map中这些区域对应的值置为0.

下面对Moravec算子的基本步骤进行简单总结，主要包括：

Moravec算法的缺陷：

• 1.不具备旋转不变性
• 2.对边缘点的反应比较强烈

  非极大值抑制(Non-Maximum Suppression,NMS)

  顾名思义，就是抑制不是极大值的元素，可以理解为局部最大搜索。这个局部代表的是一个邻域，邻域有两个参数可变，一个是是维数一个是大小。

论文《Efficient Non-Maximum Suppression》

Harris角点检测

前面提到，当一个窗口在图像上移动，在平滑区域内，窗口在各个方向上都没有变化。当一个窗口在边缘处，沿着边缘互动时它是没有变化的，而垂直于边缘滑动时是有很大变化的。当窗口在角点处，向各个方向滑动都是有很大的变化的。通过窗口在各个方向上的变化程度，我们可以判断是不是为角点

根据前面介绍的角点的数学特征（窗口平移[u,v]产生灰度变化E(u,v)）：

$$E(u,v)=\sum_{x,y}w(x,y)[I(x+u,y+v)-I(x,y)]^{2}$$

由：$I(x+u,y+v)=I(x,y)+I_xu+I_yv+O(u^2,v^2)$得到
$E(u,v)=[u,v]\begin{bmatrix}I_{x}^2&I_xI_y\\I_{x}I_{y}&I_{y}^2\ \end{bmatrix}\begin{bmatrix}u\\v\ \end{bmatrix}$
对于局部微小的移动量[u,v]，近似表达为

$$E(u,v)=\sum_{x,y}w(x,y)[I_xu+I_yv]^2$$ $$E(u,v)≈[u,v]M\begin{bmatrix}u\\v\\ \end{bmatrix}$$

其中M是2×2的矩阵。可由图像的导数求得：

$$M=\sum_{x,y}w(x,y)\begin{bmatrix}I_{x}^2&I_xI_y\\I_{x}I_{y}&I_{y}^2\\ \end{bmatrix}$$

事实上，我们并不需要求上述E(u,v)来判断角点。而是通过矩阵M来分析。
通过对窗口内每个像素的x方向上的梯度与y方向上的梯度进行统计分析。这里以$I_x和I_y$为坐标轴，因此每个像素的梯度坐标可以表示成($I_x,I_y$)。针对平坦区域，边缘区域以及角点区域三种情形进行分析：

下图对这三种情况窗口中的对应像素的梯度分布进行绘制：

如果使用椭圆进行数据集表示，则绘制图示如下：

由此我们可以利用M矩阵的特征值对角点进行判定：

由此我们得到：

• 特征值都比较大时，即窗口内还有角点
• 特征值一个比较大，一个比较小，窗口内还有边缘
• 特征值都比较小，窗口处于平坦处
  为了能定量化，提出了角点响应函数的概念。

定义角点响应函数R为：

$$R=\lambda_1\lambda_2-k(\lambda_1+\lambda_2)^2$$

Harris角点检测算法就是对角点响应函数R进行阈值处理：R＞threshold,即提取R的局部最大值

Harris角点检测的特点：

• Harris具有灰度变化的不变性：即对亮度和对比度的仿射变换并不改变Harris响应的极值点出现的位置，但是，由于阈值的选择，可能会影响角点检测的数量。如下图
  
• Harris具有旋转不变性
• Harris不具有尺度不变性，即当图缩小和放大窗口内包含图像内容是完全不同的。如下图：
  

Shi-Tomasi 算法

事实上该算法是Harris算法的改进。Harris算法是对矩阵M的行列式值与M的迹相减，再将差值与事先给定的阈值进行比较。本算法提出的改进是，若两个特征值中较小的一个大于最小阈值，则会得到强角点。

原来Harris的打分公式为：

$$R=\lambda_1\lambda_2-k(\lambda_1+\lambda_2)^2$$

Shi-Tomasi的打分函数为：

$$R=min(\lambda_1,\lambda_2)$$

如果打分超过阈值，我们就认为它是一个角点。我们可以把它绘制到$\lambda_1-\lambda_2$,就会得到下图：

从这幅图中，我们可以看出来只有当$\lambda_1和\lambda_2$都大于最小值时，才被认为是角点（绿色区域）。

FAST角点检测算法

FAST的提出者将FAST角点定义为：若某像素与其周围邻域内足够多的像素点相差较大，则该像素可能是角点。

邻域可以是下面这样的：

FAST算法步骤

• 1.上图，一个以像素p为中心，半径为3的圆上，有16个像素点$（P_1,P_2,…,P_{16}）$
• 2.定义一个阈值。计算$P_1、P_9、P_5、P_{13}$与中心p的像素差，若他们的绝对值有至少3个超过阈值，则当作候选角点，再及逆行下一步考察，否则不可能是角点；
• 3.若p是候选角点，则计算$P_1到P_{16}$这16个点与中心p的像素差，若他们至少连续9个（有的是9有的是12）超过阈值则是角点，否则不是角点。
• 4.对图像进行非极大值抑制：计算特征点出的FAST得分值，判断以特征点p为中心的一个领域（如3×3或者5×5）内，计算若有多个特征点，则计算每个特征点的FAST得分值（16个点与中心差值的绝对值总和），若p是邻域所有特征点中响应最大的，则保留；否则，抑制。若邻域内只有一个特征点（角点）则保留。
  得分计算公式如下(其中t为阈值)： $$V=max \begin{cases} \sum(pixel\ \ values-p) \ \ \ \ \ \ \ \ if(value-p)>t \\ \sum(p-pixel\ \ values) \ \ \ \ \ \ \ \ if(p-value)>t \\ \end{cases}$$

FAST算法特点

1.速度快
2.受图像噪声以及阈值影响较大
3.

SIFT

SIFT也是一种特征点（角点）检测算法，他的一大特点是SIFT特征对旋转、尺度缩放、亮度变化等保持不变性，是一种稳定的局部特征

SIFT特征检测方法：

• 1.创建尺度空间：尺度空间的目的是为了模拟图像数据的多尺度特征 $$L(x,y,\sigma)=G(x,y,\sigma) * I(x,y)$$ 其中G(x,y,\sigma)是尺度可变的高斯函数，$G(x,y,\sigma)=\frac{1}{2\pi\sigma^{2}}e^{-(x^2+y^2)/2\sigma^2}$
  (x,y)是空间坐标，也是尺度坐标。$\sigma$大小决定图像的平滑程度。大尺度对应图像的概貌特征，小尺度对应图像的细节特征.大的\sigma值对应粗糙尺度（低分辨率），反之，对应精细尺度（高分辨率特征）。

为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（DOG scale-space）.利用不同尺度的高斯差分核与图像卷积生成。：

$$\begin{align} 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) \end{align}$$

关于尺度空间的理解说明图中的2是必须的，尺度空间是连续的。在Lowe的论文中，将第0层的初始尺度为1.6，图片的初始尺度定为0.5.在检测极值点前对原始图像的高斯平滑以致图像丢失高频信息，所以Lowe建议在建立尺度空间前首先对原始图像长宽扩展一倍，以保留原始图像信息，增加特征点数量。尺度越大图像越模糊。

• 2.检测尺度空间中的极值点：为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如下图，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9*2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。如果一个点在DOG尺度空间本层以及上下两层的26个域中是最大或者最小的，就认为该点是图像在尺度下的一个特征点。
  
  同一组中的相邻尺度：
  
  在极值比较的过程中，每一组图像的首末两层是无法进行极值比较的，为了满足尺度变化的连续性，我们在每一组图像的顶层继续用高斯模糊生成三幅图像，高斯金字塔有每组S+3层图像。DOG金字塔每组有S+2层图像。上上上张图的左侧是高斯金字塔，右侧是DOG金字塔。
• 3.精确定位极值点
  通过拟合三维二次函数以精确确定关键点的位置和尺度（达到亚像素精度），同时去除低对比度的关键点和不稳定的边缘响应点（因为 DOG算子会产生较强的边缘响应），以增强匹配稳定性、提高抗噪声能力。

I.空间尺度函数：$D(x,y\sigma)=D(x,y,\sigma)+\frac{\partial D^T}{\partial x}x+\frac{1}{2}x^T\frac{\partial^2D}{\partial x^2}x$
求导，并令其为0，得到精确的$位置\hat{x}$,

$$\hat{x}=-\frac{\partial^2D^{-1}}{\partial x^2}x+\frac{1}{2}x^T\frac{\partial^2D}{\partial x^2}x$$

II.在已经检测到的特征点中，要去掉低对比度的特征点和不稳定的边缘相应点，去除低对比度的点：计算下式

$$D(\hat{x})=D(x,y,\sigma)+\frac{1}{2}\frac{\partial D^T}{\partial x}\hat{x}$$

若$|D(\hat{x})|≥0.03$则保留该点，否则丢弃
$这里\hat{X}=(x,y,\sigma)^T$
III.边缘响应的去除,一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘方向有较小的主曲率。主曲率通过一个2×2的Hessian矩阵H求出

$$H= \begin{bmatrix}D_{xx}&D_{xy}\\D_{xy}&D_{yy}\\ \end{bmatrix}$$

导数由采样点相邻差估计得到。

D的主曲率和H的特征值成正比，令α为最大特征值，β为最小特征值，则

$$Tr(H)=D_{xx}+D_{yy}=α+β$$ $$Det(H)=D_{xx}D_{yy}-(D_{xy})^2=αβ$$

令α=γβ，则

$$\frac{Tr(H)^2}{Det(H)}=\frac{(α+β)^2}{αβ}=\frac{(γβ+β)^2}{γβ^2}=\frac{(γ+1)^2}{γ}$$

如果$r>\frac{(γ+1)^2}{γ}$则丢弃它（一般这里r=10）

• 4.为每个关键点指定方向参数
  利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。 $$m(x,y)\sqrt{(L(x+1,y)-L(x-1,y))^2+(L(x,y+1)-L(x,y-1))^2}$$ $$\theta(x,y)=atan2((L(x,y+1)-L(x,y-1))/(L(x+1,y)-L(x-1,y)))$$ 式中(x,y)处梯度的模值和方向公式。其中L所用的尺度为每个关键点各自所在的尺度

至此，图像的关键点已检测完毕，每个关键点有三个信息：位置、所处尺度、方向。由此可以确定一个SIFT的特征区域

直方图的峰值就是主方向，其他的达到最大值80%的方向作为辅助方向

利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围为0~360度，其中每10度一个柱，总共36个柱。随着距中心点越来越远的邻域其对直方图的贡献也响应减少。

• 关键点描述子的生成
  首先将坐标轴旋转为关键点的方向，以确保旋转不变性。以特征点为中心取88的邻域为采样窗口，将采样点与特征点的相对方向通过高斯加权后归入包含8个方向直方图，最后获得22*8的32维特征描述子，示意图如下：
  
  每一个小格都代表了特征点邻域所在的尺度空间的一个像素，箭头方向代表了像素梯度方向，箭头长度代表该像素的幅值。然后在4×4的窗口内计算8个方向的梯度方向直方图，绘制每个梯度方向的累加可形成一个种子点。
  
  每个直方图有8个方向的梯度方向，每一个描述符包含一个位于关键点附近的四个直方图数组。这就导致了SIFt的特征向量有128维（先是一个4×4来计算出一个直方图，每个直方图8个方向.所以4×4×8=128维）将这个向量归一化之后，就进一步去除了光照的影响

• 5.128维关键点描述子生成步骤
  I.确定计算描述子所需的图像区域
  描述子梯度方向直方图由关键点所在尺度的模糊图像计算产生。图像区域的半径通过下式计算：

  $$radius=\frac{3\sigma_{oct}×\sqrt{2}×(d+1)+1}{2}$$

  $\sigma_{oct}$使关键点所在组（octave）的组内尺度，d=4

II.将坐标移至关键点主方向

那么旋转角度后新坐标为

$$\begin{pmatrix} \hat{x} \\ \hat{y} \\ \end{pmatrix}= \begin{pmatrix} cos\theta \ \ \ \ -sin\theta\\ sin\theta \ \ \ \ \ cos\theta\\ \end{pmatrix} × \begin{pmatrix} x \\ y \\ \end{pmatrix}$$

III.图像半径区域内对每个像素点求其梯度幅值和方向，然后对每个梯度赋值乘以高斯权重参数，生成方向直方图

IV.在窗口宽度为2×2的区域内计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点。然后再在下一个2×2的区域内进行直方图统计，形成下一个种子点，共生成16个种子点。
V. 描述子向量元素门限化即门限化后的描述子向量规范化。

描述子向量元素门限化：

方向直方图每个方向上梯度幅值限制在一定门限值以下（门限一般取0.2）.

描述子向量元素规范化：

$$W=(w_1,w_2,....,w_{128}) \ \ \ \ \ \ \ \ \ \ \ \ \ \ 为得到的128描述子向量，$$ $$L=(l_1,l_2,...,l_{128}) \ \ \ \ \ \ \ \ \ \ \ \ \ 为规范化后的向量$$ $$l_j=W_j/\sqrt{\sum_{i=1}^{128}w_i} \ \ \ \ \ \ \ \ \ \ j=1,2,3,...,128$$

补充概念

什么使局部特征？

• 局部特征从总体上说是图像或者在视觉领域中一些有别于其周围的地方
• 局部特征通常是描述一块区域，使其能具有高可区分度
• 局部特征的好坏直接会决定后面的分类、识别是否会得到一个好的结果

  局部特征需要具备的特性

• 重复性
• 可区分性
• 准确性
• 数量以及效率
• 不变性

  尺度空间理论

• 目的使模拟图像数据的多尺度特征
• 其基本思想是在视觉信息图像处理模型中引入一个被视为尺度的参数，通过连续变化尺度参数获得不同尺度下的视觉处理信息，然后综合这些信息以深入地挖掘图像的本质