尺度不变特征转换

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

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

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

特征

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

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

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

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

演算法

尺度空间的极值侦测

在这个阶段，主要是侦测兴趣点，也就是SIFT架构中的关键点。 影像在不同的尺度下用高斯滤波器(Gaussian filters)进行卷积(convolved)，然后利用连续高斯模糊化影像差异来找出关键点。关键点是根据不同尺度下的高斯差(Difference of Gaussians,DoG)的最大最小值。 也就是说，DoG影像的$D\left(x,y,\sigma \right)$ 是由:

$D\left(x,y,\sigma \right)=L\left(x,y,k_{i}\sigma \right)-L\left(x,y,k_{j}\sigma \right)$

$L\left(x,y,k\sigma \right)$ 是在尺度 $k\sigma$的条件下，由原始影像$I\left(x,y\right)$与高斯模糊$G\left(x,y,k\sigma \right)$进行卷积，例如 :$L\left(x,y,k\sigma \right)=G\left(x,y,k\sigma \right)*I\left(x,y\right)$

$G\left(x,y,k\sigma \right)$ 是尺度可变高斯函数 $G\left(x,y,\sigma \right)={\frac {1}{2\pi \sigma ^{2}}}e^{-(x^{2}+y^{2})/2\sigma ^{2}}$

由上式可知DoG影像是原始影像与不同尺度倍率$k_{i}\sigma$、$k_{j}\sigma$的高斯模糊后之差值。 SIFT演算法为了求得在不同尺度倍率之下DoG影像的极大值，先将原始影像与不同尺度倍率的高斯模糊进行卷积，这些经高斯模糊处理后的影像依其尺度倍率以2倍为一单位分组，并且$k_{i}\sigma$通常为一个选定后的定值，因此在每一组内经高斯模糊处理后的影像数量相同，此时将同一组相邻的经高斯模糊处理后的影像两两相减可得其DoG影像。

一旦得到DoG影像后，可找出DoG影像中的极大、极小值作为关键点。为了决定关键点，DoG影像中的每个像素会跟以自己为中心周围的八个像素，以及在同一组DoG影像中相邻尺度倍率相同位置的九个像素作，一共二十六个点作比较，若此像素为这二十六个像素中的最大、最小值，则此称此像素为关键点。

SIFT演算法中关键点的侦测是一种斑点检测(Blob detection)的一种变形，也就是使用拉普拉斯运算元来求出各个倍率及空间中的最大值。高斯差可近似为拉普拉斯运算元运算后的结果，因建立高斯金字塔的过程是一种尺寸正规化拉普拉斯运算的近似。

关键点定位

在不同尺寸空间下可能找出过多的关键点，有些关键点可能相对不易辨识或易受杂讯干扰。SIFT演算法的下一步将会借由关键点附近像素的资讯、关键点的尺寸、关键点的主曲率来定位各个关键点，借此消除位于边上或是易受杂讯干扰的关键点

邻近资料插补

对于各个可能的关键点，插补邻近资料可决定其位置。最一开始的方法为纪录各个关键点在图片中的位置与尺度。

而新开发出来的方法指出，计算极值得差补位置更能够提供配对的准确度及可靠性，此方法使用DoG影像$D\left(x,y,\sigma \right)$的二次泰勒级数，并以关键点作为原点，其展开式可写成:

$D({\textbf {x}})=D+{\frac {\partial D^{T}}{\partial {\textbf {x}}}}{\textbf {x}}+{\frac {1}{2}}{\textbf {x}}^{T}{\frac {\partial ^{2}D}{\partial {\textbf {x}}^{2}}}{\textbf {x}}$

其中D与其偏微分的值由关键点的位置决定，变数${\textbf {x}}=\left(x,y,\sigma \right)$则是到此关键点的偏移量。

将上式对${\textbf {x}}$ 微分后设为零，便可求出极值${\hat {\textbf {x}}}$的位置。若${\hat {\textbf {x}}}$的任一项参数大于0.5，代表此时有另一关键点更接近极值，将舍弃此关键点并对新的点作插补。反之若所有参数皆小于0.5，此时将偏移量加回关键点中找出极值的位置。

舍弃不明显关键点

此步骤将计算上述二次泰勒级数$D({\textbf {x}})$在${\hat {\textbf {x}}}$的值。若此值小于0.03，则舍弃此关键点。反之保留此关键点，并记录其位置为${\textbf {y}}+{\hat {\textbf {x}}}$，其中${\textbf {y}}$是一开始关键点的位置。

消除边缘响应

DoG函数对于侦测边缘上的点相当敏感，即使其找出位于边缘的关键点易受杂讯干扰也会被侦测为关键点。 因此为了增加关键点的可靠性，需要消除有高度边缘响应但其位置不佳不符合需求的关键点。

为了找出边缘上的点，可分别计算关键点的主曲率，对于在边上的关键点而言，因为穿过边缘方向的主曲率会远大于沿著边缘方向上的主曲率，因此其主曲率比值远大于位于角落的比值。

为了算出关键点的主曲率，可解其二次海森矩阵矩阵的特征值:

${\textbf {H}}={\begin{bmatrix}D_{xx}&D_{xy}\\D_{xy}&D_{yy}\end{bmatrix}}$

其特征值的比例与特征点主曲率的比例相同，因此假设解出的特征值为$\alpha$、$\beta$，其中$\alpha >\beta$。在上述矩阵中:

$\operatorname {Tr} ({\textbf {H}})=D_{xx}+D_{yy}=\alpha +\beta$

$\operatorname {Det} ({\textbf {H}})=D_{xx}D_{yy}-D_{xy}^{2}=\alpha \beta$

因此

${\text{R}}=\operatorname {Tr} ({\textbf {H}})^{2}/\operatorname {Det} ({\textbf {H}})=(r+1)^{2}/r$

其中$r=\alpha /\beta$。由此可知当R越大，$\alpha$、$\beta$的比例越大，此时设定一阈值$r_{\text{th}}$，若R大于$(r_{\text{th}}+1)^{2}/r_{\text{th}}$表示此关键点位置不合需求因此可以去除。

一般来说，设定阈值$r_{\text{th}}=10$

方位定向

在方位定向中，关键点以相邻像素的梯度方向分布作为指定方向参数，使关键点描述子能以根据此方向来表示并具备旋转不变性。

经高斯模糊处理后的影像$L\left(x,y,\sigma \right)$，在$\sigma$尺寸下的梯度量$m\left(x,y\right)$与方向$\theta \left(x,y\right)$可由相邻之像素值计算:

$m\left(x,y\right)={\sqrt {\left((L\left(x+1,y\right)-L\left(x-1,y\right)\right)^{2}+\left((L\left(x,y+1\right)-L\left(x,y-1\right)\right)^{2}}}$

$\theta \left(x,y\right)=arctan((L(x,y-1)-L(x,y+1))/(L(x-1,y)-L(x+1,y)))$

计算每个关键点与其相邻像素之梯度的量值与方向后，为其建立一个以10度为单位36条的直方图。每个相邻像素依据其量值大小与方向加入关键点的直方图中，最后直方图中最大值的方向即为此关键点的方向。若最大值与局部极大值的差在20%以内，则此判断此关键点含有多个方向，因此将会再额外建立一个位置、尺寸相同方向不同的关键点。

针对最后算出的方向还有许多优化步骤，为了符合人体的视觉感官，在加入梯度量值到直方图时会乘以距离权重(高斯函数)，以减低离关键点较远的影响程度。为了增加角度的解析度，不同角度在加入值方图时也需考量线性的权重，依照其角度偏移各区间平均值的量，照比例分配于两个区间内。最后可将值方图以差补的方式求得某个特定的角度值，而非一固定的区间。

关键点描述子

找到关键点的位置、尺寸并赋予关键点方向后，将可确保其移动、缩放、旋转的不变性。此外还需要为关键点建立一个描述子向量，使其在不同光线与视角下皆能保持其不变性，并且能够轻易与其他关键点作区分。

为了使描述子在不同光线下保有不变性，需将描述子正规化为一128维的单位向量。 首先每个4*4的子区域内建立一个八方向的直方图，且在关键点周围16*16的区域中——共4*4个子区域，计算每个像素的梯度量值大小与方向后加入此子区域的直方图中，共可产生一个128维的资料——16个子区域*8个方向。此外为了减少非线性亮度的影响，把大于0.2的向量值设为0.2，最后将正规化后的向量乘上256，且以8位元无号数储存，可有效减少储存空间。

应用

利用SIFT特征进行物体辨识

SIFT能够找出独特的关键点，此关键点不会受移动、转动、缩放、仿射变换、亮度等外在因素的影响而改变其特性。因此能够有效应用在物体辨识上，其步骤包含：

• 输入侦测物，并执行SIFT演算法找出输入影像中不变的特征。

• 这些特征会与SIFT特征资料库作描述子配对，配对将透过最近邻居法来完成。为了增加可信度，将会移除最近距离与第二近距离大于0.8的配对，这将能够有效移除背景造成的错误配对。此外为了提升最近邻居法的计算速度，应用best-bin-first演算法能够有够高机率找出最近的距离并加快搜寻速度。

• 去除错误的配对后，仍有不同物体的成功配对，因此需将成功的配对加以分类，将相同物体的分类分在一起并移除不同物体的分类，因此应用了霍夫变换。如此一来便能够辨认拥有相同角度的特征点，这些特征点有很高机率是同一个物件的，因此能够分出各个特征群。

• 对于每个被挑选出来的特征群，使用最小平方法求得输入影像与训练资料间最佳的仿射变换参数。运用此参数对各个特征点作比对，调整参数直到特征点皆能正确仿射没有错误发生为止。

全景图缝合

SIFT的特征匹配可以用于图像缝合，用于对非全景图的全自动全景重建。从输入图像中提取出来的SIFT特征能够通过每一个图像的特征匹配K个最近相邻图像。随后，这种对应关系可以用于对每一个图像寻找m个候选匹配图像。匹配图像间的单应性（Homographies）可以通过使用随机抽样一致（RANSAC）来得出。由于对于输入图像没有限制，图像的搜索应用于匹配图像对的连接部分。因此每一个连接部分都将会对全景图的构建产生影响。最后，对于所有的连接部分，可以使用光束法平差（Bundle adjustment）来连结照相参数，于是全景图就可以通过多频段混合来描绘出来。由于SIFT启发了全景图拼接的目标识别方法，拼接结果的系统将会对于顺序，方向，尺度和图像亮度不敏感。在这里，输入图像可以包含多个全景和噪声图像，全景序列将会作为结果被识别和描绘。

外部链接

• Sebastian Nowozin (C#)
• Andrea Vedaldi (Matlab/C)
• Andrea Vedaldi (C++)
• David Lowe (C/Matlab) （页面存档备份，存于互联网档案馆）
• Rob Hess (C)
• Dr Krystian Mikolajczyk (C) （页面存档备份，存于互联网档案馆）
• Stephan Saalfeld (Java)
• Adam Chapman / ChangChang Wu (Matlab-GPU implementation) （页面存档备份，存于互联网档案馆）
• Integrating Vision Toolkit (C++) （页面存档备份，存于互联网档案馆） (folder IVT/src/Features/SIFTFeatures, by Pedram Azad and Lars Pätzold)
• libsiftfast (Matlab/C++) （页面存档备份，存于互联网档案馆） 针对x86 SSE 指令集最佳化并使用OpenMP进行多核心运算. (提供Linux, Windows, 和 Mac 版本). LGPL （页面存档备份，存于互联网档案馆）授权
• lip-vireo （页面存档备份，存于互联网档案馆） (Linux 和Windows 版本)
• SIXT Scale Invariant Something Transform