section{SIFT}

????

subsection{SIFT简介cite{2}}

????
???? textbf{尺度不变特征转换(Scale-invariant feature transform或SIFT)}，由David Lowe于1999年首次提出，作用是将一幅图像映射为一个局部特征向量集；特征向量具有平移、缩放、旋转不变性，同时对光照变化、仿射及投影变换也有一定的不变性。
????
????
???? SIFT算法的特点有：~
???? 1.SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性；
???? 2.独特性（Distinctiveness）好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配；
???? 3.多量性，即使少数的几个物体也可以产生大量的特征向量；
???? 4.高速性，经优化的匹配算法甚至可以达到实时的要求；
???? 5.可扩展性，可以很方便的与其他形式的特征向量进行联合。
???
????
????
???? SIFT算法的基本步骤为：~
???? 1.高斯差分（DoG）滤波；
???? 2.尺度空间的极值检测和关键点位置确定；
???? 3.关键点方向确定；
???? 4.构建关键点特征描述符；
????
????
????
????

subsection{高斯滤波、LoG和DoGcite[p102]{1}}

????
???? textbf{高斯滤波}
????
???? 2D高斯平滑算子（高斯滤波器）由下式给出：
???? $$ G(x,y) = e^{ - frac{x^2+y^2}{2sigma^2}} $$
???? 其中x,y是图像坐标；$ sigma $是关联的概率分布的标准差。有时用带有规范因子的公式来表达：
???? $$ G(x,y) = frac{1}{2pisigma^2}e^{ - frac{x^2+y^2}{2sigma^2}}? $$
???? 或
???? $$ G(x,y) = frac{1}{sqrt{2pi} sigma^2} e^{ - frac{x^2+y^2}{2sigma^2}}? $$
????
???? 标准差$ sigma $是高斯滤波器的唯一参数，它与滤波器操作的邻域大小成正比。离算子中心越远的像素影响越小，离中心超过3$ sigma $的像素的影响可以忽略不记。所以高斯模板只需要计算$ (6sigma+1)times (6sigma+1)$的大小即可。
???? ~
????
???? 高斯滤波器的特性cite{2}：
????
??
???????? 1.圆对称性
???????? 2.线性可分。在计算卷积的时候，可以利用一行和一列的两个矩阵和图像进行卷积。高斯算子$G_{(2N+1times 2N+1)} $可以分解为两个一维向量$ h_{1_{(2N+1) times1}},h_{2_{1times(2N+1)}} $的乘积，原卷积可以改写为
???????? begin{align*}
???????? g(x,y)&= sum_{m = -N}^Nsum_{n =-N}^N G(m,n)f(x+m,x+n)
???????? & =? sum_{m = -N}^Nh_1(m)sum_{n =-N}^N h_2(n)f(x+m,x+n)
???????? end{align*}
???????? 3.对于同一张图片进行连续多次高斯模糊与只用一次大的高斯模糊，可以达到一样的效果。只需要两种方式的标准差满足方和根的关系即可。
???????? 4.高斯卷积核被证明是尺度变换唯一的变换核，也是唯一的线性核。
????
????
???? textbf{LoG(Laplacian of Gaussian)}
????
???? 使用Laplace算子
???? $$ nabla^2g(x,y) = frac{partial^2g(x,y)}{partial x^2} +frac{partial^2g(x,y)}{partial y^2} $$
???? 可以给出图像的二阶导数，用于边缘检测。
???? %噪声是什么？比如说一个信号，可以认为低频的是实际信号，特别高频的是噪声。二维中，高频的是噪声 ？——梯度大的是噪声？
???? 由于Laplace算符在检测边缘的时候也会检测到噪声（例如独立的噪点），因此需要先用高斯核对图像进行卷积操作，使图像平滑。使用LoG算子对图像f(x,y)进行处理，表示为
???? $$ nabla^2[G(x,y,sigma)*f(x,y)] $$
???? 由于卷积的性质，上式等价于
???? $$ [nabla^2G(x,sigma)]*f(x,y) $$
????
???? $ nabla^2G(x,sigma) $与图像无关，可以先计算出来。
???? ~
????
???? 由$ G(x,y) = e^{ - frac{x^2+y^2}{2sigma^2}} $，得到
???? $$ frac{partial^2G}{partial x^2} = frac{1}{sigma^2}(frac{x^2}{sigma^2} - 1)e^{ - frac{x^2+y^2}{2sigma^2}},quad??? frac{partial^2G}{partial y^2} = frac{1}{sigma^2}(frac{y^2}{sigma^2} - 1)e^{ - frac{x^2+y^2}{2sigma^2}} $$
????
???? 由此，
???? $$ nabla^2G(x,sigma)? = frac{1}{sigma^2}(frac{x^2+y^2}{sigma^2} - 2)e^{ - frac{x^2+y^2}{2sigma^2}} $$
????
???? 注：当使用带有规范化因子的高斯滤波器$ G(x,y) = frac{1}{2pisigma^2}e^{ - frac{x^2+y^2}{2sigma^2}}? $时，得到
???? $$ nabla^2G(x,sigma)? =(frac{x^2+y^2 - 2sigma^2 }{2pisigma^6})e^{ - frac{x^2+y^2}{2sigma^2}} $$
????
???? 函数形状为
???? begin{center} {includegraphics[scale = 0.5]{log.jpg}图1}end{center}
????
???? 一个常用的LoG算子如下：
???? $$ begin{bmatrix}
???? 0 & 0&-1 &0 &0
???? 0&-1&-2&-1&0
???? -1&-2&16&-2 &-1
???? 0&-1 &-2 &-1 &0
???? 0&0&-1&0&0
???? end{bmatrix} $$
???? ~

??? textbf{DoG(Difference of Gaussian)}
????
???? 可以使用DoG算子来对LoG算子进行近似。原理如下：
????
???? 对带有规范因子的高斯函数求偏导，得到
???? $$ frac{partial G}{partial sigma}? = sigma nabla^2 G$$
???? 而G对$ sigma $的偏导数有近似
???? $$? frac{partial G}{partial sigma} approx frac{G(x,ksigma) - G(x,sigma)}{ksigma- sigma} $$
????
???? 于是
???? $$G(x,sigma) approx (k-1)sigma^2 nabla^2 G $$
????
???? 注：在构建高斯金字塔时，同组的任意相邻两层之间，尺度都相差k倍，于是直接相减得到的结果相比$ sigma^2 nabla^2 G $都含有一个系数(k-1)，对探查局部的极值点无影响。
???

subsection{高斯金字塔的构建}

???? 整个高斯金字塔的结构如下图所示。
????

???? 整个金字塔的结构由组(Octave)和层(Interval)构成。每“组”图片是由大小相同的“层”构成的，而组与组之间图片的大小则不相等。高斯金字塔的构建过程为：先对原图像进行不同尺度的高斯滤波，得到第一组的各层。再对这组图片中的特定某张进行降采样，得到第二组图片的第一层。重复上述操作，即可得到高斯金字塔。
????

subsubsection{对图像做不同尺度的高斯模糊}

???? 我们使用一个三维坐标(o,s,$ sigma $)来标注图像在高斯金字塔中的位置。三个坐标的意思分别是组序号、层序号和尺度空间索引。另外，引入三个参数S,O和k。每组照片有S+3层（S人为定义），整个高斯金字塔有O组（O由顶端和底部图像的大小共同确定），$ k = 2^{frac{1}{S}} $。（后面会提到这三个参数的来源）
????
???? 首先，将原图作尺度为$ sqrt{sigma^2 - sigma_0^2 } $的高斯滤波,作为金字塔的第0组第0层
???? footnote{ 在Lowe的论文中将$ sigma $定为1.6，图片的初始尺度$ sigma_0 $定为0.5。由于在检测极值点前对原始图像的高斯平滑以致图像丢失高频信息，所以 Lowe 建议在建立尺度空间前首先对原始图像长宽扩展一倍，以保留原始图像信息，增加关键点数量。}，它的尺度为$ sigma $。
????
???? 对第0层作尺度为$ sqrt{(ksigma)^2 - sigma^2 } $的高斯滤波，得到尺度为$ ksigma $ 的第0组第1层图片footnote{利用高斯滤波的方和根关系}。
????
???? 对第1层作尺度为$ sqrt{(k^2sigma)^2 - (ksigma)^2 } $的高斯滤波，得到尺度为$ k^2sigma $ 的第0组第2层图片。
????
???? 第3层的尺度为$ k^3sigma $,第4层的尺度为$ k^4sigma $......重复上面过程，得到underline{第0组的 S+3 张图片，它们 的尺度坐标为：$ sigma,ksigma,k^2sigma ... k^{S+1}sigma,k^{S+2}sigma? $}
????

subsubsection{对图像做降采样}

???? 对第0组的倒数第三层（尺度为$ k^S sigma $）进行降采样，得到第1组的第0层，尺度为2$ sigma $。{scriptsize (人为将尺度定为$ 2sigma $的理由是什么？)}另外，由此可推出参数之间的关系$ k = 2^{frac{1}{S}} $。
????
???? 对第1组重复进行第0组的平滑过程，得到第1组的S+3张图片，它们的尺度坐标为：$ 2sigma,2ksigma,2k^2sigma ... 2k^{S+1}sigma,2k^{S+2}sigma$
????
???? 如此续行，得到O组图片，构成高斯金字塔。其中第o组第s层的图像，它的尺度为$ 2^o k^s sigma = 2^{o + frac{s}{S}} sigma $ 。
????

????
???

subsubsection{补充}

????
???? 1.为什么每组S+3张照片：在构建高斯差分金字塔时，要求每组图片可以在中间的S层上找到关键点。于是高斯差分金字塔中，每组有S+2层，高斯金字塔中就要求有S+3层。
????
???? 2.为什么用倒数第三张图片进行降采样，得到下一组图片的第0层：为了保证高斯差分金字塔的连续性。以S=3为例（最常用），高斯金字塔的尺度为：
????
???? 第0组：$ sigma to 2^{1/3}sigmato 2^{2/3}sigmato 2^{3/3}sigmato 2^{4/3}sigmato 2^{5/3}sigma $
????
???? 第1组：$ 2sigmato 2*2^{1/3}sigmato 2*2^{2/3}sigmato 2*2^{3/3}sigmato 2*2^{4/3}sigmato 2*2^{5/3}sigma $
????
???? 对应高斯差分金字塔的尺度为：
????
???? 第0组：$ sigmato 2^{1/3}sigmato 2^{2/3}sigmato 2^{3/3}sigmato 2^{4/3}sigma $
????
???? 第1组：$ 2sigmato 2*2^{1/3}sigmato 2*2^{2/3}sigmato 2*2^{3/3}sigmato 2*2^{4/3}sigma $
????
???? 掐头去尾，能够探查到关键点的层数为：
????
???? 第0组：$ 2^{1/3}sigmato 2^{2/3}sigmato 2^{3/3}sigma $
????
???? 第1组：$2*2^{1/3}sigmato 2*2^{2/3}sigmato 2*2^{3/3}sigma$
????
???? 它们的尺度正好是连续的。这一效果的好处是，在尺度空间的极值点确定过程中，不会漏掉任何一个尺度上的极值点。cite{5}
????
???

subsection{高斯差分金字塔的构建}

???? 使用高斯金字塔的上下两层相减，得到高斯差分金字塔。
???? begin{center} {includegraphics[scale = 0.6]{sift_2.jpg}}end{center}
???? 根据近似关系
???? $$G(x,sigma) approx (k-1)sigma^2 nabla^2 G $$
???? 可以得到高斯差分金字塔中每层图像的尺度坐标。
???? begin{center} {includegraphics[scale = 0.6]{sift3.jpg}}end{center}
????
???

subsection{尺度空间的极值检测}

???? 每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。 一个点如果在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个关键点。cite{7}
????
???? 每组图片的第一层和最后一层由于只与一张图片相邻，无法产生关键点。于是高斯差分金字塔中每组的S+2层图片可以在其中的S层上检测到极值点。
????
??

????
????
???

subsection{关键点位置确定}

???? 由于上述极值点的搜索是在离散空间中进行的，检测道德极值点并不是真正意义上的极值点。下图显示了一维信号离散空间得到的极值点与连续空间的极值点之间的差别。我们可以利用已知的离散空间点插值得到连续空间极值点，这一过程叫做子像元插值/亚像素插值。
?

????
???? 可以使用三维二次函数在关键点附近对图像-尺度函数$ D(x,sigma) $进行拟合，以精确得到关键点的坐标。
????
???? 假设我们在位置$ (x,sigma) $处检测到了一个离散空间中的局部极值点。那么真正的极值点有很大可能就在它的附近，假设它相对$ (x,sigma) $偏离了$ (Delta x,Delta y,Delta sigma) $。
????
???? 将$ D(x,sigma) $泰勒展开到2次：
???? $$ D(Delta x,Delta sigma) = D(x,sigma)+begin{bmatrix}? frac{partial D}{x} & frac{partial D}{y} & frac{partial D}{sigma}
???? end{bmatrix}begin{bmatrix}
???? Delta x Delta y Delta sigma
???? end{bmatrix}+frac{1}{2}begin{bmatrix}
???? Delta x &Delta y? & Delta sigma
???? end{bmatrix}begin{bmatrix}
???? frac{partial ^2D}{partial x^2} & frac{partial ^2D}{partial xpartial y} &frac{partial ^2D}{partial xpartial sigma} frac{partial ^2D}{partial ypartial x}& frac{partial ^2D}{partial y^2} & frac{partial ^2D}{partial ypartial sigma}???? frac{partial ^2D}{partial sigmapartial x}&frac{partial ^2D}{partial sigmapartial y}? & frac{partial ^2D}{partial sigma^2}
???? end{bmatrix}begin{bmatrix}
???? Delta x???? Delta y Delta sigma
???? end{bmatrix} $$
???? 式中偏导数使用离散的形式近似。
????
???? 上式可以写成矢量形式：
???? $$ D(textbf{x}) = D+frac{partial D^T}{partial textbf{x}}Delta textbf{x}+frac{1}{2}Delta textbf{x}^Tfrac{partial ^2D^T}{partial textbf{x}^2}Delta textbf{x} $$
????
???? 令$ D(textbf{x}) $的一阶导数为0，得到
???? $$ Delta textbf{x} = -frac{partial^2D^{-1}}{partial textbf{x}^2}frac{partial D(textbf{x})}{partial textbf{x}} $$
????
???? 进行多次迭代（Lowe算法中最多迭代5次，超过5次则认为这个关键点不是真正的极值点，应舍弃），得到最终点的精确位置$ hat{x} $。如果$ hat{x} $相对textbf{x}在任意维度上的偏离值大于0.5,也应舍弃该点。将其带入$ D(hat{x})$,只保留前两项，得到
???? $$ D(hat{x}) = D +frac{1}{2} frac{partial D^T}{textbf{x}} hat{x} $$
???? 求其绝对值$ |D(hat{x})| $，如果小于阈值（在Lowe的论文中，假设像素值在[0,1]，将阈值设定为0.03），则认为是不稳定的，可能受到噪声的干扰，应舍弃。
????
???? cite{5}（下一部分是直接复制的的,与Lowe的论文完全一致）
????
???? 除了删除DoG响应值低的点，还应消除边缘效应的影响。在DoG图像中，边缘有比较强的响应值。而一旦特征点落在图像的边缘上，这些点就是不稳定的点。一方面图像边缘上的点是很难定位的，具有定位歧义性；另一方面这样的点很容易受到噪声的干扰而变得不稳定。
????
???? 一个平坦的DoG响应峰值往往在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。而主曲率可以通过2×2的Hessian矩阵H求出：
???? $$ H(x,y) = begin{bmatrix}D_{xx}(x,y) & D_{xy}(x,y) D_{xy}(x,y) &D_{yy}(x,y) end{bmatrix} $$
????
???? 上式中，D值可以通过求取邻近点像素的差分得到。H的特征值与D的主曲率成正比例。我们可以避免求取具体的特征值，因为我们只关心特征值的比例。令$ alpha = lambda_{max} $为最大的特征值，$ beta = lambda_{min} $为最小的特征值，那么，我们通过H矩阵直迹计算它们的和，通过H矩阵的行列式计算它们的乘积：
???? $$ Tr(H) = D_{xx}+D_{yy} = alpha +beta $$
???? $$ Det(H) = D_{xx}D_{yy}-(D_{xy})^2=alpha beta $$
???? 如果$ gamma $为最大特征值与最小特征值之间的比例，即$ alpha = gamma beta $，这样便有
???? $$ frac{Tr(H)^2}{Det(H)} = frac{(alpha+beta)^2}{alphabeta} = frac{(gamma+1)^2}{gamma} $$
???? 上式的结果只与两个特征值的比例有关，而与具体特征值无关。当两个特征值相等($ gamma = 1 $)时，$ frac{(gamma+1)^2}{gamma}? $的值最小，随着$ gamma $的增加，$ frac{(gamma+1)^2}{gamma}? $的值也增加。所以要想检查主曲率的比例小于某一阈值$ gamma $，只要检查下式是否成立：
???? $$ frac{Tr(H)^2}{Det(H)} < frac{(gamma+1)^2}{gamma} $$
???? Lowe在论文中给出的$ gamma = 10 $。也就是说对于主曲率比值大于10的特征点将被删除。
????
????

subsection{关键点方向确定}

???? 为了使特征描述符具有旋转不变性，需要为每一个关键点分配一个基准方向。使用图像梯度的方法求取局部结构的方向（在实验中被证明是最稳定的方法）。
????
???? 目前的关键点是经亚像素插值得到的，三维坐标是实数。于是在分配基准方向时，以高斯金字塔中最近的点来代替这个关键点进行计算。
????
???? 对于与高斯金字塔中任意一个点，它的梯度的模值和方向由下式给出：
???? $$ m(x,y) = sqrt{(L(x+1,y)-L(x-1,y))^2 + (L(x,y+1)-L(x,y-1)^2} $$
???? $$ theta = tan^{-1} ( (L(x,y-1) ) ,textbf{/} ,(L(x+1,y))$$
????
???? 接下来在对关键点邻域内的梯度进行统计，得到梯度直方图。梯度直方图将0~{}$ 360 ^circ $的范围分为36个柱。注意：在向直方图加入一个点时，这个点的方向$ theta(x,y) $要以梯度的模m(x,y)和尺度为$ 1.5sigma $的高斯函数加权。(意味着只考虑大小为$ 3sigma? $ 的窗口内的点即可)
????
???? begin{center} {includegraphics[scale = 0.8]{sift_6.jpg}}end{center}
????
???? 方向直方图的峰值则代表了该特征点处邻域梯度的方向，以直方图中最大值作为该关键点的主方向。为了增强匹配的鲁棒性，只保留峰值大于主方向峰值80％的方向作为该关键点的辅方向。因此，在相同位置和尺度可能会有多个方向不同的关键点被创建，即同一点生成多个特征描述符。cite{8}(Lowe论文原话)
????
???? 对梯度直方图峰值(主方向/副方向)附近的三个柱进行二次插值，可以得到更精确的方向角度值。
????
???? 至此，检测出的含有位置、尺度和方向的关键点即是该图像的SIFT特征点。
????
??

? subsection{构建关键点特征描述符}%没改完啊啊啊啊啊啊啊

???? 下面为每一个关键点建立一个描述符，这个描述符要求具有在旋转、光照、尺度等变换有一定的不变性。
????
???? Lowe建议使用在关键点尺度空间内4*4的窗口中计算的8个方向的梯度信息，共4*4*8=128维向量来表征特征点。
????
???? 描述子的生成步骤为：
????
???? textbf{1.将坐标轴旋转为关键点的方向，以确保旋转不变性。}
???? begin{center} {includegraphics[scale = 0.8]{sift_9.jpg}}end{center}
????
???? 坐标关系
???? $$ begin{bmatrix}
???? x‘y‘
???? end{bmatrix} = begin{bmatrix}
???? costheta & -sinthetasin theta &costheta
???? end{bmatrix} begin{bmatrix}
???? xy
???? end{bmatrix} $$
????
???? textbf{2.对一个关键点产生128维SIFT特征向量。}
????
???? 将关键点附近的邻域划分为4*4个子区域，每个子区域作为一个种子点，每个种子点有8个方向。
???? 计算每个种子点周围的$ 3sigma $窗口中每一个像素的梯度，使用高斯函数（$ 1.5sigma $）和梯度的模进行加权，统计到8个方向中。
???? begin{center} {includegraphics[scale = 0.5]{sift_8.jpg}}end{center}
????
???? textbf{3.将特征向量的长度归一化，可以进一步取出光照变化的影响。}
????
????
???? %在光照充足的情况下，m(x,y)也会变大——》关键点的方向的大小会变大
????
????
????

section{补充}

????
???? 1.为什么使用尺度空间cite{6}：尺度空间(scale space)思想最早是由Iijima于1962年提出的，后经witkin和Koenderink等人的推广逐渐得到关注，在计算机视觉邻域使用广泛。
????
???? 尺度空间理论的基本思想是：在图像信息处理模型中引入一个被视为尺度的参数，通过连续变化尺度参数获得多尺度下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。
????
???? 尺度空间方法将传统的单尺度图像信息处理技术纳入尺度不断变化的动态分析框架中，更容易获取图像的本质特征。尺度空间中各尺度图像的模糊程度逐渐变大，能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。
????
???? “Decting locations that are invariant to scale change of the image can be accomplished by serching for stable features across al possible scales,using a continus function of scale known as scale space.”cite{3}
????
???? 2.为什么把高斯差分空间的极值点作为关键点：“In detailed experimental comparisons,Mikolajczyk (2002) found that the maxima and minima of $ sigma^2 nabla^2 G $ produce the most stable image features compared to a range of other possible image functions,such as the gradient,Hessian,or Harris corner function. ”cite{3}
???? 而使用DoG来近似LoG可以减少计算量。

??? pagebreak
???? begin{thebibliography}{99}??? %引用
???????? bibitem{1} Milan Sonka,Vaclav Hlavac,Roger Boyle. 图像处理、分析与机器视觉[M].
???????? bibitem{2} url{https://blog.csdn.net/hit2015spring/article/details/52895367}
???????? bibitem{3} Lowe D G. Distinctive Image Features from Scale-Invariant Keypoints[J]. International Journal of Computer Vision,2004,60(2):91-110.
???????? bibitem{4} url{http://fourier.eng.hmc.edu/e161/lectures/gradient/node8.html}
???????? bibitem{5} url{https://www.cnblogs.com/ronny/p/4028776.html}
???????? bibitem{6} url{https://blog.csdn.net/zddblog/article/details/7521424}
???????? bibitem{7} url{https://blog.csdn.net/abcjennifer/article/details/7639681}
???????? bibitem{8} url{https://blog.csdn.net/u010440456/article/details/81483145}
???? end{thebibliography}

end{document}