SIFT算法介绍¶
- 寒假期间我主要阅读了三部分内容：中科大的文章《多视点视频捕获及实时拼接技术研究》，David Lowe对于SIFT算法的阐述Distinctive Image Features from Scale-Invariant Keypoints，以及A.Vedaldi完全根据Lowe的SIFT思想（不是改进的SIFT）用MATLAB/C编写的SIFT演示代码。
- 下面根据LOWE的文章，先对SIFT算法的主要原理、流程做一个简要阐述。由于该算法的核心是“尺度不变”特征点的提取，所以特征点得筛选资源从高斯金字塔产生的差分高斯空间中的局部极值点获得。
- 我认为关于高斯金字塔以及拉普拉斯算子的原理可以作以下直观理解：SIFT算法的尺度不变特征点大多是边缘上的点（更进一步是边缘上的角点（如矩形的四个顶点），关于边缘上非角点得去除会在下文提到），而边缘上的点即是高频（亮度与邻接点相差大）的点，它的亮度变化率取到一个极大值，即亮度变化率的变化率（亮度的二阶导数）等于0，即拉普拉斯算子△I=0。
- 由于当图像与高斯核卷积后，I(x,y)变为G(X,Y,σ),求二阶偏导数可以转化为求关于尺度σ的一阶偏导数（高斯核即二维正态分布是热传导方程的一个解），且求这个偏导数更易实现，所以引入以σ为变量的高斯差分空间。对高斯差分空间可作如下直观理解：当人眼由远及近地观察一个物体，物体的细节会变化，但大体轮廓不会变化，由此可以通过比较站在远处和近处的两个画面来确定轮廓。事实上高斯差分空间中的图像看起来像浮雕，轮廓非常明显，所以求出高斯差分空间邻接图像的极值点即可。】
- 下面进行初步取得的极值点得筛选工作，分两步，筛出特征点。
- 用二次曲面来模拟每个极值点附近的图像亮度函数，求出理论上极值点，设定一个界限，舍去实际点与理论点偏差大于界限的点。
- 去除仅落在边缘上而非角点的点。这类应被舍去的点有一个特征：沿着边缘切线方向的图像函数平缓（曲率小），垂直边缘方向陡峭（曲率大）。由于Hessian矩阵的两个特征值是X,Y方向的曲率，所以求出每个极值点两个特征值的比值，设定一个界限，舍去不合格的点即可。
- 选定特征点后，就对每个特征点进行描述子（模拟人眼视网膜）的制作（因为特征点对图像的变化过于敏感，而描述子不敏感）。
- 由于SIFT对旋转有不变性，所以为每个特征点计算一个方向，这是制作描述子的预备工作。【具体实现是选定一个特征点附近的区域，算出区域中所有点的梯度大小以及方向，然后将这些方向分为36组，按梯度大小和正态分布函数加权，绘制0~360°的直方图，再用二次函数拟合求直方图的最大值点，得到一个特征点的总方向（若有次最大值点接近极大值点，则将这一特征点分为二个在同一坐标的点，但分别使用两个不同方向）。】
- 确定方向后将区域内所有点的梯度方向转过一个上述确定的主方向的角度。然后将区域分为4*4=16个正方形子区域，每个区域中的点按梯度大小和正态分布加权，绘制出8个方向的直方图，所以每个特征点可得到一个128维的描述子向量（因为要使特征点对对比度变化不敏感，还需对向量归一化处理）。这些描述子即可用于匹配，即寻找另一幅图像中与该特征点128维向量几何距离最短的点。LOWE提到的方法是用K-D树搜索，但由于高维情形耗时较长，需加一个近似最优的贪心法剪枝和一个卡时出解的策略求得近似解。至此，SIFT算法完成。
- 除上述对SIFT算法的理论可行性讨论外，在SIFT实现的过程中还有一个重要的方面是一些参数的选择，例如一个OCTAVE几个图，一个描述子几个子区域，以及舍弃极值点时界限阈值（threshold）的选择，这些都关系到识别的精确度和算法的效率。Lowe在文章中给出了推荐数据，但在具体情况下可能可以再作微调（如识别的场景不同）。
- SIFT算法时间复杂度的瓶颈在于描述子的建立和匹配，如何优化对特征点的描述方法是提升SIFT效率的关键，PCA-SIFT等算法在这里做了优化。
- 《多视点视频捕获及实时拼接技术研究》这篇文章阐述的是如何实现一个实时拼接的系统。但这篇文章由于事先约定摄像头相对位置的不变性，所以借用SIFT计算两幅图像的转换矩阵只需进行一次。因此该文强调的实时并非因SIFT效率的提升（检测与匹配）而达到实时性，而是融合的实时性（由于采用线性的加权算法融合，较易达到实时效果）。
- 最后简要讨论一下实现代码。A.Vivaldi的代码是演示用的，所以代码强调可读性而非效率。可以从代码看到，使用MATLAB/C混编，既有MATLAB的优点（可以使用MATLAB中的图像工具包，更方便地返回函数的多个输出值，数据类型处理非常方便），也有C的优点（高效）。所以编写时可以用C写运算量大的部分，用MATLAB写对C语言运算结果的数据进行归并整理的部分（如生成金字塔，根据特征点坐标建立索引图像等）和主程序部分。