SIFT：

        尺度不变特征转换(Scale-invariant feature transform或SIFT)是一种电脑视觉的算法用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量，此算法由 David Lowe在1999年所发表，2004年完善总结。

        其应用范围包含物体辨识、机器人地图感知与导航、影像缝合、3D模型建立、手势辨识、影像追踪和动作比对。

SIFT的特点：

1、具有较好的稳定性和不变性，能够适应旋转、尺度缩放、亮度的变化，能在一定程度上不受视角变化、仿射变换、噪声的干扰。
2、区分性好，能够在海量特征数据库中进行快速准确的区分信息进行匹配
3、多量性，就算只有单个物体，也能产生大量特征向量
4、高速性，能够快速的进行特征向量匹配
5、可扩展性，能够与其它形式的特征向量进行联合

SIFT算法可以解决的问题：

        目标的自身状态、场景所处的环境和成像器材的成像特性等因素影响图像配准/目标识别跟踪的性能。而SIFT算法在一定程度上可解决：

1. 目标的旋转、缩放、平移（RST）

2. 图像仿射/投影变换（视点viewpoint）

3. 光照影响（illumination）

4. 目标遮挡（occlusion）

5. 杂物场景（clutter）

6. 噪声

        SIFT算法的实质是在不同的尺度空间上查找关键点(特征点)，并计算出关键点的方向。SIFT所查找到的关键点是一些十分突出，不会因光照，仿射变换和噪音等因素而变化的点，如角点、边缘点、暗区的亮点及亮区的暗点等。

SIFT算法分解为如下四步：

1. 尺度空间极值检测：搜索所有尺度上的图像位置。通过高斯微分函数来识别潜在的对于尺度和旋转不变的兴趣点。

2. 关键点定位：在每个候选的位置上，通过一个拟合精细的模型来确定位置和尺度。关键点的选择依据于它们的稳定程度。

3. 方向确定：基于图像局部的梯度方向，分配给每个关键点位置一个或多个方向。所有后面的对图像数据的操作都相对于关键点的方向、尺度和位置进行变换，从而提供对于这些变换的不变性。

4. 关键点描述：在每个关键点周围的邻域内，在选定的尺度上测量图像局部的梯度。这些梯度被变换成一种表示，这种表示允许比较大的局部形状的变形和光照变化。

一.尺度空间极值检测

1.构建高斯差分金字塔：

（1）对图像做高斯平滑；
（2）对图像做降采样。

        图像的金字塔模型是指将原始图像不断降采样，得到一系列大小不一的图像，由大到小，从下到上构成的塔状模型。原图像为金子塔的第一层，每次降采样所得到的新图像为金字塔的一层(每层一张图像)，每个金字塔共n层。为了让尺度体现其连续性，高斯金字塔在简单降采样的基础上加上了高斯滤波。如上图所示，将图像金字塔每层的一张图像使用不同参数做高斯模糊，Octave表示一幅图像可产生的图像组数，Interval表示一组图像包括的图像层数。另外，降采样时，高斯金字塔上一组图像的初始图像(底层图像)是由前一组图像的倒数第三张图像隔点采样得到的。

左边为高斯金字塔，中间是高斯金字塔的内部结构，右边是高斯差分金字塔

1、DOG函数

2、DoG高斯差分金字塔
（1）对应DOG算子，需构建DOG金字塔。
        可以通过高斯差分图像看出图像上的像素值变化情况。（如果没有变化，也就没有特征。特征必须是变化尽可能多的点。）DOG图像描绘的是目标的轮廓。
（2）DOG局部极值检测
        特征点是由DOG空间的局部极值点组成的。为了寻找DoG函数的极值点，每一个像素点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。特征点是由DOG空间的局部极值点组成的。为了寻找DoG函数的极值点，每一个像素点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如下图，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。

二.关键点定位

（1.）去除边缘效应
        在边缘梯度的方向上主曲率比较大，而沿着边缘方向则主曲率较小。候选特征点的DoG函数D(x)的主曲率与2×2Hessian矩阵H的特征值成正比。

其中，Dxx,Dxy,Dyy是候选点邻域对应位置的差分求得的。
H的特征值α和β代表x和y方向的梯度

表示矩阵H对角线元素之和，表示矩阵H的行列式。假设是α较大的特征值，而是β较小的特征值，令α=γβ，则

该值在两特征值相等时达最小。Lowe论文中建议阈值T为1.2，即

时保留关键点，反之剔除。

三.方向确定

1、通过尺度不变性求极值点，需要利用图像的局部特征为给每一个关键点分配一个基准方向，使描述子对图像旋转具有不变性。对于在DOG金字塔中检测出的关键点，采集其所在高斯金字塔图像3σ邻域窗口内像素的梯度和方向分布特征。梯度的模值和方向如下：

2、本算法采用梯度直方图统计法，统计以关键点为原点，一定区域内的图像像素点确定关键点方向。在完成关键点的梯度计算后，使用直方图统计邻域内像素的梯度和方向。梯度直方图将0~360度的方向范围分为36个柱，其中每柱10度。如下图所示，直方图的峰值方向代表了关键点的主方向，方向直方图的峰值则代表了该特征点处邻域梯度的方向，以直方图中最大值作为该关键点的主方向。为了增强匹配的鲁棒性，只保留峰值大于主方向峰值80％的方向作为该关键点的辅方向。

四.关键点描述

        对于每一个关键点，都拥有位置、尺度以及方向三个信息。为每个关键点建立一个描述符，用一组向量将这个关键点描述出来，使其不随各种变化而改变，比如光照变化、视角变化等等。这个描述子不但包括关键点，也包含关键点周围对其有贡献的像素点，并且描述符应该有较高的独特性，以便于提高特征点正确匹配的概率。

PointSIFT：

PointSIFT model

pointsift块是嵌在网络中的一个模块，其输入是n个特征，每个特征d维，其输入与输出保持一致，因此非常容易嵌入任何网络。

OE unit

        方向编码卷积是pointsift块中的基本单元，它可以捕获周围的点，具体步骤如下：

步骤一：以特征点f为中心，将空间分割为八个方向，每个方向中离f最近的点代表该方向，若在半径r内未找到特征点，则用f表示。步骤一结束后，每个特征带有周围八个方向的信息，即从n×d变为n×8×d

步骤二：对每个特征点进行一次x轴的卷积，即每个点的八个特征进行两两结合，结束后每个特征点带有4个维度的特征，即从n×8×d变为n×4×d。公式如下：

步骤三：对每个特征点再进行一次y轴的卷积，即每个点的四个特征两两结合，结束后每个特征点带有2个维度的特征，即从n×4×d变为n×2×d。公式如下：
步骤四：对每个特征点再次进行一次z轴的卷积，即每个点的两个特征结合，结束后每个特征点带有1个维度的特征，即从n×2×d变为n×d。公式如下：


与KNN近邻选择相比：

（1）八邻域搜索的复杂度低，该方法只需搜索一个邻域，而k近邻需要搜索周围所有区域

（2）k近邻选择在某些场景，取点过于片面，八邻域搜索可以捕获所有方向的信息，如上图所示，绿色代表八邻域搜索，红色代表k近邻搜索。

PointSIFT