本项目SIFT代码实现参考了视频讲解及其开源实现，仅使用了两个基本Python库，分别用于矩阵等数值计算和结果绘图展示。特征点匹配算法基于自行实现的最近邻算法，避免引入sklearn库造成打包文件过大。
基本配置
运行环境
Python 3.7.1
numpy 1.21.5
matplotlib 3.5.1
打包工具
pyinstaller 5.0 (项目要求提交exe可执行文件)
软件说明
关于SIFT的流程和原理讲解网上有很多博客提及，但具体的算法实现有需要考虑诸多细节，因此独立实现全部代码还是一定困难。我在完全理解参考代码之后，重新实现了全部代码，并加上了详细的注释。本节中未提及的细节可在源代码中找到函数功能、参数、代码块等的进一步解释说明。
辅助函数
计算图像高斯差分所依赖的基础函数（numpy未提供二维卷积）：
- gaussianKernel 高斯滤波核函数
- convolve2D 图像二维卷积函数
- downSample 图像下采样
matplotlib 未提供图像上绘制点和直线的函数，自行实现两函数，用于结果展示：
- addLine 在图像上添加两点之间的直线
- addKeyPoints 在图像上添加点
基于描述子的特征点匹配：
- kNN 返回两组向量的最近邻
SIFT流程
graph TD; getDoG --> getKeyPoints --> adjustLocalExtrema --> getMainDirection --> getDescriptorSIFT算法分解为如下四步：
-
尺度空间极值检测：搜索所有尺度上的图像位置。通过高斯微分函数来识别潜在的对于尺度和旋转不变的兴趣点。该步骤由getDoG和getKeyPoints完成，getKeyPoints内部调用adjustLocalExtrema，getMainDirection返回最终的关键点。
-
关键点定位：在每个候选的位置上，通过一个拟合精细的模型来确定位置和尺度。
- 对应adjustLocalExtrema函数，用到了图像在极值点处的泰勒展开迭代更新精确极值点
- 偏导数用差分近似代替
- 基于Hessian矩阵去除边缘上的点
- 注意：求导时像素值需要归一化（除以255）
-
方向确定：基于图像局部的梯度方向，分配给每个关键点位置一个或多个方向。所有后面的对图像数据的操作都相对于关键点的方向、尺度和位置进行变换，从而提供对于这些变换的不变性。
-
统计梯度方向直方图
-
抛物线插值确定精确方向：经推导，极值点\(x_2\)更新公式为：
\(x_2' = x_2 + \frac 1 2 (x_1-x_3)/(x_1+x_3-2x_2)\)
-
注意：1. 计算角度/梯度的参考系与图像坐标不同
2. 插值时边界处理
-
-
关键点描述：在每个关键点周围的邻域内，在选定的尺度上测量图像局部的梯度。
- 三线性插值，本质是将直方图上的连续点
hist[r][c][d]的幅值表示在三个维度上立方体八个角点（离散）上的线性组合，根据系数将该点幅值按权重重新分配到八个角点上。参考知乎推导系数。 - 归一化处理去除光照的影响
- 三线性插值，本质是将直方图上的连续点
实验结果
使用cv2库的SIFT
自行实现SIFT
左图在6231个极值点中定位出100个特征点，右图在5386个极值点中定位出104个特征点。结果如下：
SIFT特征匹配结果
由上图可见，从上至下，左上角背景墙壁、头顶发梢、眉毛、左右脸、鼻子、嘴角、头发、裙子、左下角背景墙壁均正确匹配。中间手与腰看似错误匹配，定位检查该特征点，发现该条直线为距离最近的前三组关键点。
打印三组关键点原始信息，可知这三组为大尺度（第一二维为像素坐标，第三维为octave组数，分别位于第3,2,2层）特征，大致对应了身体的整体尺度。
由以上分析结果可见，前14个特征匹配结果均准确无误。
其他匹配结果展示
使用两张不同size的图片，匹配结果存在至少3处错误。
选择前30个匹配特征点展示，可以明显看到存在错误匹配，但大多数相同特征点都完全对应上。
总结
通过编程实践，对SIFT掌握有了更深刻的理解。SIFT能很好提取图像中的局部性特征，通过在空间尺度中寻找极值点，提取出位置、尺度、旋转不变量，并构造描述子用于后续的特征匹配。SIFT能应对图像的旋转、缩放、平移，对亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性。本人代码基于Python实现，实际运行需要较长时间，算法的实时性不高，未来有待改进。
标签：匹配,尺度,极值,SIFT,图像,特征提取,CV,关键点 From： https://www.cnblogs.com/izcat/p/16640706.html