3.4　图像特征点提取

特征点提取算法能帮助计算机获取图像的区域特征信息，并应用于图像识别、图像匹配、三维重建、物体跟踪等领域。在实际工程中，具有很高的应用价值。在图像领域，特征点（feature point）也常常被称为关键点（key point）或兴趣点（interest point）。特征点的提取有多种算法，可以从图像纹理信息来提取，也可以通过图像区域灰度统计信息来提取，或者通过频谱变化、小波变换等变换后的特殊空间进行提取。本节将对最常用的SIFT（scale invariant feature transform，尺度不变特征变换）特征点、SURF（Speeded Up Robust Feature，加速稳健特征）特征点和ORB（Oriented FAST and Rotated BRIEF，快速特征点提取和描述）特征点进行分析与讲解，并对比其性能表现。

SIFT在性能方面非常突出，在业界有很高的名气；SURF是对SIFT的改进，在提取速度方面做了优化；ORB是用于取代SIFT和SURF的简洁提取算法，提取速度比SIFT和SURF快很多。后续视觉SLAM中的ORB_SLAM框架就是基于ORB特征点的，该框架在实时性方面表现非常出色。因此学好本节的内容，将极大地降低后续视觉SLAM章节的学习难度。

本节的重点放在SIFT、SURF和ORB这3种特征点提取的原理讲解中，如果对OpenCV中具体实现程序感兴趣，可以阅读OpenCV3中相应的源代码，源代码的路径如下。

• SIFT源码路径：opencv_contrib/modules/xfeatures2d/src/sift.cpp。
• SURF源码路径：opencv_contrib/modules/xfeatures2d/src/surf.cpp。
• ORB源码路径：opencv/modules/features2d/src/orb.cpp。

3.4.1　SIFT特征点

SIFT［3］是一种对图像的旋转、尺度和亮度特性保持不变，且对仿射变换、噪声等有较好稳定性的图像局部特征。那什么是旋转尺度不变性呢？简单点说就是同一个物体，用相机在不同的角度和距离拍出来的图片，图片中物体的特征应该是一样的，不因图片的大小和旋转而改变。

SIFT特征提取过程，如图3-7所示。由于所有操作都在灰度图上进行，因此输入原始图需要先经过灰度转换。然后构建高斯金字塔（gaussian pyramids），用于表示图像的尺度空间。将高斯金字塔每组（octave）中相邻两图层求差值得到高斯差分金字塔（Difference of Gaussian Pyramids，DoG金字塔），用于尺度空间的极值点检测。接着通过极值点检测、特征点定位和特征点筛选操作，提取出特征点在尺度空间的位置。之后回到高斯金字塔，求取该尺度空间位置上的特征点主方向以及邻域方向。最后利用特征点的方向信息可以生成很多特征的描述子，这些特征组合成向量的形式就是特征点的描述向量，在整个提取过程的最后将输出所有特征点的描述向量。特征点包含尺度、位置和特征描述信息，利用这些信息就可以做图像识别、图像匹配等应用了。

1. 尺度空间

将单张图像利用尺度参数进行处理，得到多尺度空间的图像序列。尺度空间中的图像模糊度逐渐变大，这样能够模拟人眼由近及远观察目标时在视网膜上成像的过程。从多尺度空间的图像序列提取特征，能得到具有尺度不变性的特征。下面依次对图像金字塔、高斯金字塔和高斯差分金字塔的构建过程进行解析。

（1）图像金字塔

正如其名，图像金字塔由一张张逐渐缩小的图片组合而成。金字塔最底层放置的是原始图像，然后上一层图像由下一层图像经过1/2倍降采样得到，其实就是隔点采样，这样图像尺寸会逐渐缩小，如图3-8所示。

金字塔中含有图像的数量n，可用式（3-20）计算得到。其中，rows和cols分别为原始图像的行数和列数，t为金字塔顶层图像期望尺寸的对数值。也就是说已知塔顶图像的尺寸，就可以求得塔包含图像的数量。

（2）高斯金字塔

若将尺度连续性考虑进来，则还需要在图像金字塔的基础上引入高斯滤波，这就是高斯金字塔。在SIFT特征提取过程中，高斯金字塔的构建过程如图3-9所示。

高斯金字塔中的图像有组（octave）和层（Layer）的概念，通过组索引和层索引可以为塔中的每个图像建立索引。SIFT算法的提出者Lowe建议将原始灰度图扩大到2倍大小，即通过2倍升采样和高斯滤波，将扩大后的图作为塔最底层的图开始构建，这样可以保留原图信息，增加特征点数量。同一组内的图层具有相同的大小，后一个图层由前一个图层经过尺度因子为σ(o, s)的高斯滤波处理得到，也就是说同一组内递增的图层将越来越模糊。尺度因子σ(o, s)的计算如式（3-21）所示，o和s分别为组索引和层索引，σ0为初始尺度因子，在程序中为一个常数值，S是组中图层的总数量。

在不同组中，后一组的第1个图层由前一组的倒数第3个图层直接经过1/2倍降采样得到，取倒数第3个图层是为了保持下一步高斯差分金字塔的尺度空间连续性。按照这个步骤，不断构建出新的组，最终就能得到一个完整的高斯金字塔。关于金字塔的组数O、层数S等参数，请参考具体程序，这里的讲解只是举例说明而已。

（3）高斯差分金字塔

通过构建高斯差分金字塔，检测高斯差分金字塔的极值点，能够提取原图像中的角点特征。要搞清楚其中的原理，需要先从拉普拉斯算子开始说起。拉普拉斯算子是n维欧式空间的一个二阶微分算子，拉普拉斯定义为求梯度的散度，如式（3-22）所示。

利用拉普拉斯算子对函数求二阶导数，能求出函数一阶导数的极值点，也就是最大梯度点。这里先以最简单的1维空间为例，展示利用二阶导数求出函数局部最大梯度点的过程，如图3-10所示。

再来讨论2维空间的情况。在图像中，局部像素最大梯度点是变化最明显的点，这样的点可以作为特征点。但是直接的拉普拉斯操作非常容易受图像噪声点的干扰，于是就引入了抗干扰的高斯滤波，先进行高斯滤波，再进行拉普拉斯操作，这就是高斯拉普拉斯运算（Laplace of Gaussian，LoG）。虽然对图像做高斯拉普拉斯运算能实现角点检测，但是运算复杂。理论证明，高斯差分函数与尺度归一化高斯拉普拉斯函数非常近似，因此可以用高斯差分运算替代高斯拉普拉斯运算来做图像角点的检测。关于近似的理论推导，如式（3-23）～式（3-25）所示。

接下来就讲一下如何构建高斯差分金字塔，其实就是将高斯金字塔同组内的相邻图层做差即可，如图3-11所示。

2. 特征点位置提取

特征点位置提取在高斯差分金字塔中完成，分为极值点检测、特征点定位和特征点筛选这些步骤。

（1）极值点检测

在高斯差分金字塔的同一组内，图层上的极值点由该图层像素的8个邻域点与上下相邻图层的9×2=18个邻域点比较大小得到。也就是说要判断一个点是否为极值点，需要将其与周围的26个点比较大小，如图3-12所示。由此可知，要检测全尺度下的极值点，高斯差分金字塔的每个组内要多出2个图层，而高斯差分金字塔是由高斯金字塔做差得到的，那么高斯金字塔的每个组内要多出3个图层，这就是前面讲到的为什么要从倒数第3个图层来生成下一个组的原因，即为了保持高斯差分金字塔中尺度的连续性。

（2）特征点定位

通过上面方法得到的是离散空间的极值点，但是离散空间的极值点并不是真正的极值点。如图3-13所示，曲线的离散采样点A、B、C、D中，A和B分别是极大值点与极小值点，但并不是曲线上真正的极值点。因此，需要利用曲线拟合的方法得到连续空间的曲线，并得到真正的极值点。这个操作在图像中是一个亚像素定位的过程，拟合过程为在极值点附近做泰勒级数展开，找出特征点更精确的位置。

（3）特征点筛选

高斯差分算子容易产生较强的边缘响应，因此特征点还需要经过筛选，去除边缘点的影响。首先获取特征点位置处的Hessian矩阵H，如式（3-26）所示。

矩阵H的特征值a和b表示x与y方向的梯度。边缘点的梯度肯定是一个方向大而另一个方向小。因此可以设置一个阈值T，用于剔除边缘点。假设a>b，则满足a/b>T的点将被判断为边缘点，从而被剔除。

3. 特征点方向提取

特征点方向提取在高斯金字塔中完成，分为特征点主方向、特征点邻域方向和特征描述子这些步骤。

（1）特征点主方向

经过在高斯差分金字塔中的一系列操作，提取出了特征点在尺度空间的位置信息。接下来就可以去高斯金字塔中提取该尺度空间位置处的点方向信息。我们需要先提取特征点的主方向，提取过程如图3-14所示。

找到高斯金字塔中相应尺度空间的图层，在特征点位置的3σ邻域窗口计算像素的梯度，梯度的幅值m和方向θ通过式（3-27）和式（3-28）求得，其中f(x, y)为邻域窗口的像素值。

计算好梯度的幅值和方向后，将方向每10°划分一个范围，对方向进行统计，方向对应的幅度需要经过高斯系数加权后进行累计，也就是说离特征点中心越远的梯度点的幅值累计时需乘以一个越小的加权系数。统计完所有方向后，就得到方向的统计直方图，直方图的横轴是方向角度，一共有36个刻度（10°、20°、…、360°），直方图的纵轴是对应方向幅值加权累计的结果。以直方图峰值的方向作为主方向，并保留大于80%峰值的方向作为辅方向，以增强鲁棒性。

（2）特征点邻域方向

要对特征点做一个好的表示，还需要用到特征点邻域上的方向。在计算邻域上的方向分布前，需要先将邻域图像按主方向进行旋转，这样邻域方向就是统一以主方向为基准来表示，以实现特征的旋转不变性，如图3-15所示。

如图3-16所示，在得到的旋转不变性邻域上，进行4×4的区域划分，得到16个区域。对每个区域求方向的统计直方图，这里的直方图将方向每45°划分一个范围，也就是8个方向。方向对应的幅度同样需要经过高斯系数加权后进行累计，这里的高斯系数是以各自区域中心来计算的。

（3）特征描述子

从上面特征点邻域方向一共得到了4×4×8=128个量，也就是说一个特征点可以用这样的128维向量来描述，即描述向量。为了去除光照变化的影响，需要对描述向量做归一化处理。同时为了消除成像时饱和度变化的影响，需要对归一化后的描述向量进行阈值化处理，即设置一个阈值，将大于阈值的、具有较大幅值的方向去除，再进行一次归一化处理。最后按照特征点的尺度对描述向量进行排序。SIFT特征提取完成后，能得到一系列特征点。每个特征点包含尺度、位置和描述信息，有了这些信息就可以做图像识别、匹配之类的应用了。如图3-17所示为从图片中提取SIFT特征的效果。

3.4.2　SURF特征点

SIFT［4］算法最大的缺点是在一般设备上达不到实时性的要求，而SURF是对SIFT的改进，在提取速度方面做了优化。SURF特征提取过程和SIFT特征提取过程基本一样，只是在一些步骤上做了改进以提高运行实时性。下面针对改进的地方展开讲解。

1. 尺度空间

在SIFT中建立尺度空间的步骤包括创建高斯金字塔和创建高斯差分金字塔两步，而在创建高斯金字塔过程中，要利用不同尺度因子的高斯滤波器对图像进行滤波来得到多尺度空间。高斯滤波运算是很耗时的，所以这一步需要进行优化。

同样考虑到基于高斯拉普拉斯算子检测图像角点的良好特性，所以在SURF特征提取过程中使用了另一种近似高斯拉普拉斯运算的方式（即基于Hessian矩阵的盒式滤波运算），能大幅降低运算的耗时。下面就解析一下整个过程，高斯拉普拉斯运算的第一步是对图像I(x, y)进行高斯滤波，如式（3-29）所示。

然后对高斯滤波后的图像中的每个像素进行拉普拉斯运算，拉普拉斯运算结果用Hessian矩阵表示，如式（3-30）所示。矩阵中的元素分别是对x方向求二阶导数、对x和y方向依次求偏导数、对y和x方向依次求偏导数对y方向求二阶导数这样4个操作。

不难发现，上面Hessian矩阵中4个元素的操作是关键，这4个操作分别对应在x方向求二阶导数、在x和y方向依次求偏导数、在y和x方向依次求偏导数和在y方向求二阶导数高斯滤波窗口。这种滤波窗口有3种形状，分别是x方向二阶导形、y方向二阶导形和x、y混合导形，如图3-18的左半部分所示。窗口中的不同亮度表示不同的加权系数，可以看到这些窗口中的系数还是非常多的，计算起来很耗时。解决办法是利用盒式滤波来近似这些窗口，其实就是将一定区域的不同加权系数统一用某个固定值表示，如图3-18的右半部分所示，通过图像的积分图很容易证明利用盒式滤波来近似的合理性。

利用盒式滤波器求出图像中每个像素的Hessian矩阵后，接着求Hessian矩阵的决定值，如式（3-31）所示。

考虑到利用盒式滤波近似可能带来的误差，这里加一个0.9的补偿系数，如式（3-32）所示。这样图像中每个Hessian矩阵的决定值就可以用于后续的极值点检测了。

与SIFT尺度空间不同的是，在SURF中金字塔的不同组的图层大小是一样的。我们通过以下方式来实现多尺度空间：在不同组上使用盒式滤波器的窗口尺寸逐渐增大；在同一组内的不同图层上使用相同窗口尺寸的盒式滤波器，但是窗口中的尺度因子取值逐渐增大。

2. 特征点位置提取

SIFT特征点位置是在DoG空间进行的，而SURF特征点位置是在Hessian矩阵的决定值中进行的。除了这一点区别外，极值点检测、特征点定位和特征点筛选的方式是一样的，不再赘述。

3. 特征点方向提取

在SIFT中，特征点主方向是通过求特征点邻域上梯度的方向统计直方图，取直方图峰值的方向得到，而SURF是统计特征点邻域上的Haar小波特征得到。统计60°扇形区域内所有x和y方向小波特征，这些特征通过高斯加权系数进行累计，即远离中心的小波特征乘上的加权系数小。然后以15°间隔旋转这个60°扇形区域，将整个圆遍历，统计出最大值的那个扇形方向就是特征点主方向，如图3-19所示。

在SIFT中，先将特征点邻域按主方向旋转后，计算该邻域各个区块的梯度方向直方图来描述特征点，描述向量是4×4×8=128维。在SURF中，不旋转邻域图像，而是按主方向旋转邻域窗口。以旋转之后窗口的x和y方向作为Haar小波特征计算的方向，窗口同样被划分成4×4的区块，每个区块含有5×5个像素，统计每个区块中5×5个像素的x方向小波特征之和、x方向小波特征绝对值之和、y方向小波特征之和、y方向小波特征绝对值之和，如图3-20所示。

把这4个统计值作为该区块的描述，那么描述向量是4×4×4=64维。也就是说，SURF特征描述向量维度只有SIFT特征描述向量维度的一半。图3-21所示为从图片中提取SURF特征的效果。

3.4.3　ORB特征点

学习完SIFT和SURF特征后，最后来学习ORB特征。ORB［5］特征的最大优点是在提取上具有很好的实时性，按业界的说法，ORB提取速度比SURF快10倍，比SIFT快100倍。ORB提取速度能这么快，得益于其所基于的FAST（Features from Accelerated Segments Test）特征和BRIEF（Binary Robust Independent Elementary Features）描述。

ORB特征提取过程如图3-22所示。

由于所有操作都在灰度图上进行，因此输入原始图需要先经过灰度转换。然后构建图像金字塔，用于表示图像的尺度空间。由此可见，ORB的尺度空间构建方法比SIFT和SURF简单多了，因为图像仅进行逐个的降采样就行了，并且构建出来的图像金字塔中各张图直接拼接成一张大图，用这张大图就能直接表示尺度空间，这样做也能大大加快构建速度。后续的特征提取与描述都直接在这张大图上进行，以使特征具有尺度不变性。这里提取的是FAST特征，并且对FAST特征进行了改进，增加了FAST特征点的旋转方向信息提取，改进后称oFAST。最后在特征点邻域内，计算BRIEF描述，并且对BRIEF描述也进行了改进，借助特征点的旋转方向信息来计算BRIEF描述，改进后称rBRIEF。这里对FAST特征和BRIEF描述进行的改进，都是为了使特征点具有旋转不变性。计算完所有的oFAST和rBRIEF，就能得到所有特征点的描述向量，提取过程便完成了。

1. 尺度空间

ORB构建出的图像金字塔中的各种图片拼接在一起成为一张大图，并记录好大图中每个尺度的起始和结束位置，用这张大图就能直接表示尺度空间，如图3-23所示。

2. 特征点提取

先说FAST特征的提取过程，对给定的像素点p，判断p点邻域圆周上的16个像素点中是否有连续N个点的灰度值与p点灰度值之差超过某一阈值，这个阈值一般设为p点灰度值的20%，满足这个判断的点就是FAST特征点。根据N的具体取值，FAST有几种不同的形态，常用的有FAST-12、FAST-11和FAST-9。由于这样提取的过程并没有包含特征点的旋转方向信息，为了使特征点具有旋转不变性，还要计算特征点的方向。只需要计算出邻域的灰度质心m，邻域中心p到灰度质心m的方向就是特征点的方向，这样就得到了oFAST特征。oFAST特征提取过程如图3-24所示。

3. 特征点描述

在BRIEF描述计算过程中，首先对图像金字塔拼接的大图进行高斯滤波处理，以去除一些高频噪声点的干扰；然后在特征点的邻域内随机挑选两个点作为一个点对，如果点对中的第1个点亮度大于第2个点，则为这个点对分配特征值1，反之分配特征值0；按照高斯分布依次挑选256个这样的点对，最终可以得到一个256维的向量，并且向量中的每个元素只能取0或1两个值，比如V=[101001110101010111010...]这样的形式。为了使特征点描述具有旋转不变性，还要将特征点的方向考虑进来。其实很简单，只需要将BRIEF中按照高斯分布依次挑选的256个点对按特征点方向旋转，得到新的256个点对，对新的点对计算分配特征值即可，这样就得到了rBRIEF描述。到这里，ORB特征就提取出来了。图3-25所示为从图片中提取ORB特征的效果。