尺度不变特征转换（尺度不变特征转换）-趣爱秀

介绍

尺度不变特征转换(Scale-invariant feature transform或SIFT)是一种机器视觉的算法用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变数，此算法由David Lowe在1999年所发表，2004年完善总结。^{[1]后续的论文中也有许多基于 SIFT 改进的论文，例如SURF将 SIFT 的许多过程近似，达到加速的效果；PCA-SIFT利用主成分分析降低描述子的维度，减少内存的使用并加快配对速度。}

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

此算法有其专利，专利拥有者为英属哥伦比亚大学。

特征

局部影像特征的描述与侦测可以帮助辨识物体，SIFT 特征是基于物体上的一些局部外观的兴趣点而与影像的大小和旋转无关。对于光线、噪声、些微视角改变的容忍度也相当高。基于这些特性，它们是高度显著而且相对容易撷取，在母数庞大的特征数据库中，很容易辨识物体而且鲜有误认。

使用 SIFT 特征描述对于部分物体遮蔽的侦测率也相当高，甚至只需要3个以上的 SIFT 物体特征就足以计算出位置与方位。

在现今的电脑硬件速度下和小型的特征数据库条件下，辨识速度可接近即时运算。

SIFT 特征的信息量大，适合在大量数据库中快速准确匹配。

算法

尺度空间的极值侦测

尺度不变特征转换

在这个阶段，主要是侦测兴趣点，也就是SIFT架构中的关键点。影像在不同的尺度下用高斯滤波器(Gaussian filters)进行卷积(convolved)，然后利用连续高斯模糊化影像差异来找出关键点。关键点是根据不同尺度下的高斯差(Difference of Gaussians,DoG)的最大最小值。也就是说，DoG影像的是由:^{[2]尺度不变特征转换
尺度不变特征转换
尺度不变特征转换
尺度不变特征转换
尺度不变特征转换
尺度不变特征转换
是在尺度的条件下，由原始影像与高斯模糊进行卷积，例如: 。
尺度不变特征转换
尺度不变特征转换
是尺度可变高斯函数。
尺度不变特征转换
尺度不变特征转换
由上式可知DoG影像是原始影像与不同尺度倍率的高斯模糊后之差值。 SIFT算法为了求得在不同尺度倍率之下DoG影像的极大值，先将原始影像与不同尺度倍率的高斯模糊进行卷积，这些经高斯模糊处理后的影像依其尺度倍率以2倍为一单位分组，并且通常为一个选定后的定值，因此在每一组内经高斯模糊处理后的影像数量相同，此时将同一组相邻的经高斯模糊处理后的影像两两相减可得其DoG影像。
一旦得到DoG影像后，可找出DoG影像中的极大、极小值作为关键点。为了决定关键点，DoG影像中的每个像素会跟以自己为中心周围的八个像素，以及在同一组DoG影像中相邻尺度倍率相同位置的九个像素作，一共二十六个点作比较，若此像素为这二十六个像素中的最大、最小值，则此称此像素为关键点。
SIFT算法中关键点的侦测是一种斑点检测(Blob detection)的一种变形，也就是使用拉普拉斯算子来求出各个倍率及空间中的最大值。高斯差可近似为拉普拉斯算子运算后的结果，因建立高斯金字塔的过程是一种尺寸正规化拉普拉斯运算的近似。
关键点定位
在不同尺寸空间下可能找出过多的关键点，有些关键点可能相对不易辨识或易受噪声干扰。SIFT算法的下一步将会借由关键点附近像素的资讯、关键点的尺寸、关键点的主曲率来定位各个关键点，借此消除位于边上或是易受噪声干扰的关键点。
方位定向
在方位定向中，关键点以相邻像素的梯度方向分布作为指定方向参数，使关键点描述子能以根据此方向来表示并具备旋转不变性。
尺度不变特征转换
尺度不变特征转换
尺度不变特征转换
经高斯模糊处理后的影像，在尺寸下的梯度量与方向可由相邻之像素值计算:
尺度不变特征转换
尺度不变特征转换
计算每个关键点与其相邻像素之梯度的量值与方向后，为其建立一个以10度为单位36条的直方图。每个相邻像素依据其量值大小与方向加入关键点的直方图中，最后直方图中最大值的方向即为此关键点的方向。若最大值与局部极大值的差在20%以内，则此判断此关键点含有多个方向，因此将会再额外建立一个位置、尺寸相同方向不同的关键点。
针对最后算出的方向还有许多优化步骤，为了符合人体的视觉感官，在加入梯度量值到直方图时会乘以距离权重(高斯函数)，以减低离关键点较远的影响程度。为了增加角度的分辨率，不同角度在加入值方图时也需考量线性的权重，依照其角度偏移各区间平均值的量，照比例分配于两个区间内。最后可将值方图以差补的方式求得某个特定的角度值，而非一固定的区间。
关键点描述子
找到关键点的位置、尺寸并赋予关键点方向后，将可确保其移动、缩放、旋转的不变性。此外还需要为关键点建立一个描述子向量，使其在不同光线与视角下皆能保持其不变性，并且能够轻易与其他关键点作区分。
首先每个4*4的子区域内建立一个8方向的直方图，在关键点周围16*16的区域中一共16个子区域，计算每个像素的梯度量值大小与方向后加入此子区域的直方图中，共可产生一个128维的资料。为了使描述子在不同光线下保有不变性，需将描述子正规化为一128维的单位向量。此外为了减少非线性亮度的影响，把大于0.2的向量值设为0.2，最后将正规化后的向量乘上256以8位元无号数储存，可有效减少储存空间。
应用
利用SIFT特征进行物体辨识
SIFT能够找出独特的关键点，此关键点不会受移动、转动、缩放、仿射变换、亮度等外在因素的影响而改变其特性。因此能够有效应用在物体辨识上，其步骤包含：
• 输入侦测物，并执行SIFT算法找出输入影像中不变的特征。
• 这些特征会与SIFT特征数据库作描述子配对，配对将透过最近邻居法来完成。为了增加可信度，将会移除最近距离与第二近距离大于0.8的配对，这将能够有效移除背景造成的错误配对。此外为了提升最近邻居法的计算速度，应用best-bin-first算法能够有够高机率找出最近的距离并加快搜寻速度。
• 去除错误的配对后，仍有不同物体的成功配对，因此需将成功的配对加以分类，将相同物体的分类分在一起并移除不同物体的分类，因此应用了霍夫变换。如此一来便能够辨认拥有相同角度的特征点，这些特征点有很高机率是同一个物件的，因此能够分出各个特征群。
• 对于每个被挑选出来的特征群，使用最小平方法求得输入影像与训练资料间最佳的仿射变换参数。运用此参数对各个特征点作比对，调整参数直到特征点皆能正确仿射没有错误发生为止。
全景图缝合
SIFT的特征匹配可以用于图像缝合，用于对非全景图的全自动全景重建。从输入图像中提取出来的SIFT特征能够通过每一个图像的特征匹配K个最近相邻图像。随后，这种对应关系可以用于对每一个图像寻找m个候选匹配图像。匹配图像间的单应性（Homographies）可以通过使用随机抽样一致（RANSAC）来得出。由于对于输入图像没有限制，图像的搜索应用于匹配图像对的连接部分。因此每一个连接部分都将会对全景图的构建产生影响。最后，对于所有的连接部分，可以使用光束法平差（Bundle adjustment）来连结照相参数，于是全景图就可以通过多频段混合来描绘出来。由于SIFT启发了全景图拼接的目标识别方法，拼接结果的系统将会对于顺序，方向，尺度和图像亮度不敏感。在这里，输入图像可以包含多个全景和噪声图像，全景序列将会作为结果被识别和描绘。
参考资料
[1] Lowe, David G. Object recognition from local scale[引用日期2019-04-30]
[2] 云得. 机器视觉[M]. 科学出版社, 2000.[引用日期2019-04-30]}