·序言

  近期准备开始写一些传统CV算法方面的学习心得，因为我觉得对一名CV学习者而言，了解一些传统的、偏数学的计算机视觉算法还是挺有必要的。虽然神经网络出现之后这些传统算法变得不那么重要，但是缺乏理论的支撑很容易让人在学习新模型的时候产生困惑。因此我希望，用尽可能简明的语言，记录一下我在CV传统算法学习上的所获所得。巧合的是，我的研究生导师也要出一本关于CV的书，于是我提出负责撰写传统CV算法的部分，借这个机会一边写书一边学习~

---------------下面是正文---------------

  传统CV算法的学习笔记共分为三个部分。第一部分是区域特征算法，对于图像比对的理解会挺有帮助的。第二部分是边缘检测算法，对于图像分割的理解会更深刻。第三部分是一些与图像语义理解相关的算法。

  这些天一直在看关于区域特征的算法讲解，搜集了很多个人觉得写得比较好的资料，花十来天整理出了一套学习教材，现分享如下：

  事实上，由于这些资料写得比较详细，学完之后有必要做一个提取和整理，现用简明的语言把我个人的学习笔记和心得分享如下：

【传统CV算法】图像局部特征点检测学习笔记

第一章·概述

  斑点与角点是主要的两类局部特征点。这两个术语看上去有点晦涩，但是翻译者想表达的，我觉得是：斑，即为较为突出的一团色块，在计算机看来，与周围有着颜色与灰度差别的区域就是斑。例如草原上的一棵树或一栋房子，有意思的在于，这与人的认识有些不同：我们不会称草原上的树或房子为“斑”，因为我们不觉得它们具有类似“斑”的突兀感，但是在计算机看来，绿绿的草原上多出的树或房子就是异样的色块，很符合斑的定义。这背后的差异，可以归结于计算机没有图像的语义理解，它不明白草原上树或房子的存在是合乎常理的。因此我觉得这是很有意思的一点，现有的斑点定义是从纯规则化判定出发，但是应该会有更高级一些的斑点的定义，能够结合语义理解去识别人眼所认为的“斑点”。

  同理，角点的定义也是源自计算机视角。角，形成于线条的交叉部分，在计算机看来，灰度发生剧变的区域称为边缘，那么两条边缘的交汇处就是角点。角点非常适合用作图像的定位，从人眼来理解，第一，角点非常好找，因为它是两处灰度突变线的交点，视觉上处于一个显眼的位置；第二，角点辨识度很高，一方面角点依赖于两条边缘，存在重复或相似的角点概率极低，另一方面角点具有旋转不变性，也就是记住一个角点，闭上眼睛旋转图片，再睁开眼依然能唯一定位这个角点。计算机对于角点的理解和人眼差不多，不过在角点检测上显得有些麻烦，似乎不像人类能非常自然――计算机看一个区域，然后上下左右滑动,如果任意方向上都存在较大灰度变化，即存在角点。值得说明的是，任意方向都存在变化很重要，这是因为至少存在两个不同方向的边缘（角点的要求）才能实现任意方向都有变化，否则（边缘数≤1）一定存在一个方向没有灰度变化。我觉得人眼在视觉处理上还是比计算机更高级高效一些，主要体现在角点会在人类视觉中产生一种“刺眼感”,于是帮人省去了局部求导这样的操作，我不明白这种“刺眼感”是如何瞬间产生的，又该如何传递给计算机。姑且认为这得益于人眼计算机制的复杂和先验知识的充沛的结果。

  上述的笔记其实不大像是学习总结，更像是一些随笔和感悟，可能一方面这是我的一个写文风格，另外一方面算法的背后也确实存在一些自然物语，我觉得提取这些物语是学习枯燥的数学算法的乐趣所在。下面开始具体的局部特征检测算法的学习。

第二章·角点检测

1. Harris角点

  Harris的核心思想：

  情况1 如果窗口在图像各个方向上移动时，窗口内图像的灰度没有发生变化，那么窗口内就不存在角点。

  情况2 如果窗口在某一个方向移动时，窗口内图像的灰度发生了较大的变化，而在另一些方向上没有发生变化，那么，窗口内的图像可能就是一条直线的线段。

  情况3 如果在各个方向上移动这个特征的小窗口，窗口内区域的灰度发生了较大的变化，那么就认为在窗口内遇到了角点。

  我们需要找的就是情况3 ，“灰度发生了较大的变化”在数学上我们可以用自相关函数表示：

  这个函数，计算的是待测像素点和周围指定区域的相邻像素点相似性的加权求和。理论上，我们希望，对于任意的ΔX，ΔY，该像素点的自相关函数c都能保持一个比较大的值，直观上解释也就是，该像素点朝着任意方向都有着较大的灰度值变化，那么我们便认为这个待测像素点就是角点。

  之后文章当中用到了一些不错的数学技巧将这一问题进行简化，先是将这一计算式通过泰勒展开简化成了二项式的计算，然后把二项式转化成了几何当中的椭圆问题，最终转化成用椭圆的特征值来实现角点检测：

  >特征值都比较大时，即窗口中含有角点；

  >特征值一个较大，一个较小，窗口中含有边缘；

  >特征值都比较小，窗口处在平坦区域。

  最后我们需要设计一个角点响应式去实现上述的特征值判定，Harris给出的公式如下：

  其中,。

  那上述内容就是简略回顾了Harris算法的核心内容。Harris有着一个比较好的数学定义——朝着任意方向都有着较大的灰度值变化的像素点,这个定义为算法的设定和推导减轻了很多负担。用到的数学技巧也很巧妙，像我这样的小白很难想到。简言之，对于区域特征提取很容易想复杂，找到一个好的数学定义会省事好多。文章当中还搜集了一些Harris的改进算法，对提升Harris的稳定性有些帮助。

2. FAST角点

  正如前篇的笔记当中写到的，“找到一个好的数学定义会省事好多”，FAST算法就是从另一个角度定义了角点：若某像素点与其周围领域内足够多的像素点处于不同的区域，则该像素点可能为角点。这个定义很有意思，不过我感觉定位会不那么精准，因为这样找出的角点会位于拐点处偏内一些，不过对于图像定位其实没太大影响。FAST算法步骤如下：

  1.从图片中选取一个像素P，下面我们将判断它是否是一个特征点。我们首先把它的亮度值设为Ip。

  2.设定一个合适的阈值t。

  3.考虑以该像素点为中心的一个半径等于3像素的离散化的Bresenham圆，这个圆的边界上有16个像素（如下图所示）。

  4.现在，如果在这个大小为16个像素的圆上有n个连续的像素点，它们的像素值要么都比Ip+t大，要么都比Ip−t小，那么它就是一个角点。（如图1中的白色虚线所示）。n的值可以设置为12或者9，实验证明选择9可能会有更好的效果。

  FAST的好处就是在于效率高，但是受噪音的影响比较严重，并且算法的效果很依赖于阈值t。

  FAST-ER主要是通过优化决策树的结构解决形变带来的角点检测不准确问题，具体的实现比较复杂，我不再赘述了（看了两天我还不大理解，也找不到更多的资料了。。SAD，先跳过）下面重点说一下斑点检测中的SIFT和SURF算法吧。

第三章 斑点检测

1. SIFT斑点检测

SIFT算法的关键分为如下四步： 1. 尺度空间极值检测：搜索所有尺度上的图像位置。通过高斯微分函数来识别潜在的对于尺度和旋转不变的兴趣点。 2. 关键点定位：在每个候选的位置上，通过一个拟合精细的模型来确定位置和尺度。关键点的选择依据于它们的稳定程度。 3. 方向确定：基于图像局部的梯度方向，分配给每个关键点位置一个或多个方向。所有后面的对图像数据的操作都相对于关键点的方向、尺度和位置进行变换，从而提供对于这些变换的不变性。 4. 关键点描述：在每个关键点周围的邻域内，在选定的尺度上测量图像局部的梯度。这些梯度被变换成一种表示，这种表示允许比较大的局部形状的变形和光照变化。

SIFT的一整套操作下来，实在是复杂，但是它能解决的问题，是非常高级的，它希望不论图像做什么样的变化，只要特征点依然在图像中，该特征点就能被准确提取出来。我先粗略地提取一下这一套复杂操作的基本思想是什么。首先我们需要找出有可能存在的特征点，并且这些特征点的尺度和方向要不受图像变化的影响，于是我们可以用到高斯差分函数的方法，这个方法简言之就是把图像不同尺度的高斯模糊拼接为一个金字塔，然后这个金字塔相邻上下层两两相减得到高斯差分算子，这个高斯差分算子（DoG）能够替代（LoG）去进行极值检测，这样检测出的点在不同尺度下都属于极值点，于是我们就较快地找到了可能是特征点的且尺度和方向较为稳定的像素点。然而第一步只是粗选特征点，下面我们需要在这些特征点中选择更为稳定的特征点。一个方法是通过泰勒展开提高DoG函数的精度，另外一个是要淘汰掉一些不好的DoG，比如在DoG的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率，这可以用Hessain矩阵去计算。于是第二步我们实现了关键点定位（精选）。定位完成之后我们要对算子赋予一个方向，但是我们希望这个方向尽可能地具有旋转不变性，于是我们能想到的是如果把算子的方向定义为周围像素区域的某计算式，且该计算式不受图像朝向影响便具有旋转不变性。SIFT给出了一个较为简易的计算式：采用直方图统计邻域像素的梯度方向，累计最多的梯度方向当选为该算子的方向。最后，考虑到后期要进行影像匹配，必须要对特征点做出独一无二的描述，这样才能进行一对一的匹配。SIFT提出利用关键的局部梯度特性进行独一性描述，即计算关键点周围像素的梯度值，并分块进行统计，然后计算出相对于主方向的方向，这里非常关键的一点就是计算临近点相对主方向的梯度方向，这样就使得特征具有旋转不变性。