理解SIFT

理解SIFT

MarkdownHTML

## SIFT步骤### 找尺度空间极值 可以用DoG找 需要讲理论依据和DoG结合进行推导 s值和$\sigma$值的选取问题### 关键点定位 和泰勒展开相关### 方向赋值### 局部图像描述符## SIFT用于目标识别的步骤 目标图像提取SIFT特征；搭建SIFT特征数据库 用快速kNN将目标特征在数据库中查找 用霍夫变换寻找属于同一单目标的簇(cluster) 用least-square(最小二乘法)验证## SIFT算法步骤 多尺度极值检测(用DoG找) 关键点定位 方向赋值 关键点描述符## 尺度空间极值检测尺度空间定义：$L(x,y,\sigma)=G(x,y,\sigma)*I(x,y)$相关论文已证明，真正具有尺度无关性的算子只有一种：归一化的LoG函数：$\sigma^2\nabla^2G$考虑高斯查分函数DoG:$G(x,y,k\sigma)-G(x,y,\sigma)$对应的尺度空间表达式有：$D(x,y,\sigma)=L(x,y,k\sigma)-L(x,y,\sigma) \\=(G(x,y,k\sigma)-G(x,y,\sigma))*I(x,y)$考虑热放射等式，有：$\frac{\partial G}{\partial \sigma}=\sigma\nabla^2G$其证明过程：$G(x,y)=\frac{1}{2\pi \sigma^2}e^{\frac{x^2+y^2}{2\sigma^2}} \\\frac{\partial G}{\partial x}=-\frac{x}{2\pi\sigma^4}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\frac{\partial^2G}{\partial^2x}=-\frac{\sigma^2-x^2}{2\pi\sigma^6}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\nabla^2G=\frac{\partial^2G}{\partial^2x}+\frac{\partial^2G}{\partial^2y} = \frac{x^2+y^2-2\sigma^2}{2\pi\sigma^6}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\frac{\partial G}{\partial \sigma}=\frac{x^2+y^2-2\sigma^2}{2\pi\sigma^5}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\therefore \frac{\partial G}{\partial x}=\sigma \nabla^2 G$$G(x,y)=\frac{1}{2\pi \sigma^2}e^{\frac{x^2+y^2}{2\sigma^2}} \\\frac{\partial G}{\partial x}=-\frac{x}{2\pi\sigma^4}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\frac{\partial^2G}{\partial^2x}=-\frac{\sigma^2-x^2}{2\pi\sigma^6}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\nabla^2G=\frac{\partial^2G}{\partial^2x}+\frac{\partial^2G}{\partial^2y} = \frac{x^2+y^2-2\sigma^2}{2\pi\sigma^6}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\frac{\partial G}{\partial \sigma}=\frac{x^2+y^2-2\sigma^2}{2\pi\sigma^5}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\therefore \frac{\partial G}{\partial x}=\sigma \nabla^2 G$而考虑$\frac{\partial G}{\partial \sigma}$的近似替代公式：$\sigma\nabla^2G=\frac{\partial G}{\partial \sigma} \approx \frac{G(x,y,k\sigma)-G(x,y,\sigma)}{k\sigma-\sigma}$因此有：$G(x,y,k\sigma)-G(x,y,\sigma) \approx (k-1)\sigma^2\nabla^2G$即：用DoG来近似替代LoG算子，得到近似不变的尺度无关特性。相差的倍数是常量没有影响。当k->1，误差几乎为0.### 高斯金字塔的建立**octave**：采样率相同、尺寸相同，模糊度逐渐增强的一组相邻图像**level**：octave中的每张图像，叫做一个level每个octae内是持续高斯模糊得到；每个octave的第一个levle通过降采样得到。每个octave内有s次模糊。$\sigma$的选取和$s$选取，不能太小，否则不准确；太大又会消耗太多计算资源，得不到实时效果。Lowe的论文实验表明，选取$\sigma=1.6$，$s=3$是合适的。不过为了充分利用输入的图像，可以考虑在生成octave前做一次升采样：认为照相机采集的图像本身就是模糊的，其$\sigma=0.5$，利用线性插值得到$\sigma=1.0$的图像，然后用于生成octave**疑问**l升采样后的图像，有没有再次做模糊操作得到octave的第一张？还是说直接作为octave的第一个level？### DoG金字塔每两个高斯金字塔level之间做差值就得到DoG的一个level。为了得到所有极值，因为高斯金字塔的首尾两层不会被带入计算，因此在首尾各添加一层，最上面再加一层**这段还是不够清晰，需要修改**### 局部极值检测在DoG金字塔中，检测空间中每个像素点周边的26个点。如果是极值，那么继续往金字塔高层进行检测。极值检测需要考虑检测的策略：检测到的极值点数量会影响到后续的特征检测数量，特征越少则匹配的结果越少，但是往往是正确率较高的匹配；特征越多则匹配的结果越多，但是正确率往往不高。前者更多地考虑了效率，后者更多地考虑了完整性，需要在效率和完整性之间权衡。因而，要选取合适数量的特征数量，在这之前需要选取合适数量的极值点，这就需要考虑采样频率的问题。（实际上，集中在一起的极值点对于小的扰动非常不稳定）。采样频率的问题，包括尺度上的采样频率、空间域上的采样频率两个方面。Lowe通过实验得到一些测量结果，从结果的图表中得到$s$值和$\sigma$值的经验值。Lowe的实验图像“有32张，包括室外场景、人脸、航拍图片、工业图像（这些图像的来源领域对结果几乎没有影响）”。但是本人认为，仅仅从32张图像就得到相关的经验参数，并不很具有说服力，如果有时间，不妨使用更多的图片进行相关测定。尺度上的采样频率问题，就是考虑图像金字塔中每个octave内的尺度空间数量s。实验中尺度图像由随机的旋转和0.2~0.9之间的随机尺度变换得到，同时也添加了1%的噪声（使用平均分布为每个像素点增加一个随机数）。实验结果为：随着尺度数量s的增加，同一位置的重复匹配率“先增加后减小”，同一极值点对应的特征描述符在数据库中被**正确**搜索到的比率，也是“先增加后减小”。折可以被解释为：随着尺度数量s的增加，尽管极值点数量增加，但是过了一定限度后增加的极值点都是低于平均稳定程度的，因而反倒降低了匹配的重复率和正确率。对应于Lowe的实验结果，选取$s=3$时，正确匹配率最高。而随着尺度数量s的增加，极值点数量也增加，并且正确匹配的极值点的总数也是增加的；而通常目标识别通常更依赖于正确匹配的极值点数量而不是正确匹配率，因此看起来使用更大的尺度空间数s会得到更好的效果。但是，这会增加计算消耗。因而，Lowe的论文中权衡了正确率和计算消耗，选取$s=3$作为每个octave内的尺度数量。也就是说，仅仅检测那些稳定的极值点，同时又能够避免大量的计算消耗，还能够得到很好的正确率。空间域上的采样频率问题，就是高斯模糊的参数$\sigma$，即平滑尺度。考虑到极值可能随机地出现在一起，也需要类似前面一种情况考虑采样频率和检率的问题。实验数据表明，随着$\sigma$的增加，同一特征点在变换后的图像中被重复检测到的百分比、极值点对应的特征描述符在数据库中被查找到的正确率，都呈现增加趋势。但是$\sigma$增加后计算量也增加，权衡考虑算法效率和正确率，使用$\sigma=1.6$。（同样地，这显然也是Lowe的32张图像的测试结果带来的经验数据，个人认为这个数据要根据不同的情况可以适当修改）。同时也可以考虑图像预先平滑操作，这样能**有效地忽略最高空域频率**（这句其实并不理解），其做法是：认为相机拍摄得到的原始图像的模糊度为$\sigma=0.5$，通过双线性差值得到$\sigma=1.0$模糊尺度的图像。这就意味着，在创建尺度空间的第一个octave之前，需要做一次平滑操作（也就是：原图升采样得到$\sigma=1.0$-->做第一次预先处理的平滑得到$\sigma=1.6$的尺度图像作为第一个octave的第一个level）。**这里发现对于“采样”并不很理解，需要找书仔细看下**## 确定关键点的精确位置前面得到的极值，只是离散的图像金字塔中不同尺度下的极值点。真正的尺度空间应当是连续的，而不是离散的，图像金字塔中的极值只是真正极值的近似，还需要进一步的精确检测，得到真正的极值点和极值。使用泰勒公式对DoG函数进行展开，并求导，解出导数为0的点，得到的解就是“前面极值检测中检测到的极值采样点，与真正的尺度空间中的极值点的偏差（这个偏差是向量(x,y,$\sigma$)）”。即：$定义向量\vec{x} = (x, y, \sigma)对D函数，泰勒展开有：D(\vec {x})=D+\frac{\partial D^T}{\partial \vec {x}}\vec {x} + \frac{1}{2}\vec {x}^T\frac{\partial^2 D}{\partial \vec{x}^2}\vec {x}求解得到：\vec {x_0} = - \frac{\partial^2 D^{-1}}{\partial \vec {x}^2}\frac{\partial D}{\partial \vec {x}} $$其中使用到对于向量求导的计算，包括： \\\frac{\partial \vec {x}}{\partial \vec {x}}=单位矩阵E \\\frac{\partial \vec{x}^T \vec{x}}{\vec{x}} = 2 \vec{x}$将$\vec{x_0}$带入$D(\vec{x})$的表达式，得到对应的极值：$D(\vec{x}) = D + \frac{1}{2}\frac{\partial D^T}{\partial \vec{x}}\vec{x}$实验中忽略$D \lt 0.03$的极值点。这样，得到的$\vec{x}$表示采样点的偏离量。此时，keypoint的表示中包括了：位置(x,y),尺度$\sigma$。后面还会包括方向。### 消除边界响应还需要去除边界上的干扰，需要考虑**主曲率**。 通过计算**黑塞矩阵**能得到特征值之间的关系，而主曲率和特征值之间是成倍的关系，因此只需要考虑特征值之间的关系。假设黑塞矩阵算出的特征值中，大的为$\alpha$，小的为$\beta$，而：$ H=\begin{matrix} D_{xx} & D_{xy} \\ D_{xy} & D_{yy}\end{matrix}$$Tr(H)=D_{xx}+D_{yy} = \alpha + \beta \\Det(H)=D_{xx}D_{yy}-(D_{xy})^2 = \alpha \beta$显然，$\frac{Tr(H)}{Det(H)}$是增函数，因此只需要保证：$\frac{Tr(H)^2}{Det(H)}

## SIFT步骤### 找尺度çºé—´æžå€¼    可以用DoG找    需要è²ç†èºä¾æå’ŒDoG结合进行推导    s值和$\sigma$值的选取é—题### 关é”点åšä½    和泰勒展开相关### 方向赋值### 局部图像描述符## SIFT用于ç›æ ‡è¯†åˆ«çš„步骤    ç›æ ‡å›¾åƒæå–SIFT特征；搭建SIFT特征数æåº“    用快速kNN将ç›æ ‡ç‰¹å¾åœ¨æ•°æåº“中查找    用霍夫变换寻找属于同一单ç›æ ‡çš„ç°‡(cluster)    用least-square(最小二乘法)验证## SIFTç—法步骤    多尺度极值检测(用DoG找)    关é”点åšä½    方向赋值    关é”点描述符## 尺度çºé—´æžå€¼æ£€æµ‹å°ºåº¦çºé—´åšä¹‰ï¼š$L(x,y,\sigma)=G(x,y,\sigma)*I(x,y)$相关èºæ–‡å·²è¯æ˜Žï¼ŒçœŸæ­£å…·æœ‰å°ºåº¦æ— å…³æ€§çš„ç—子只有一种：归一化的LoG函数：$\sigma^2\nabla^2G$考虑高斯查分函数DoG:$G(x,y,k\sigma)-G(x,y,\sigma)$对应的尺度çºé—´è¡¨è¾¾å¼æœ‰ï¼š$D(x,y,\sigma)=L(x,y,k\sigma)-L(x,y,\sigma) \\=(G(x,y,k\sigma)-G(x,y,\sigma))*I(x,y)$考虑热放射等式，有：$\frac{\partial G}{\partial \sigma}=\sigma\nabla^2G$其证明过程：$G(x,y)=\frac{1}{2\pi \sigma^2}e^{\frac{x^2+y^2}{2\sigma^2}} \\\frac{\partial G}{\partial x}=-\frac{x}{2\pi\sigma^4}e^{-\frac{x^2+y^2}{2\sigma^2}}  \\\frac{\partial^2G}{\partial^2x}=-\frac{\sigma^2-x^2}{2\pi\sigma^6}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\nabla^2G=\frac{\partial^2G}{\partial^2x}+\frac{\partial^2G}{\partial^2y} = \frac{x^2+y^2-2\sigma^2}{2\pi\sigma^6}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\frac{\partial G}{\partial \sigma}=\frac{x^2+y^2-2\sigma^2}{2\pi\sigma^5}e^{-\frac{x^2+y^2}{2\sigma^2}}  \\\therefore \frac{\partial G}{\partial x}=\sigma \nabla^2 G$$G(x,y)=\frac{1}{2\pi \sigma^2}e^{\frac{x^2+y^2}{2\sigma^2}} \\\frac{\partial G}{\partial x}=-\frac{x}{2\pi\sigma^4}e^{-\frac{x^2+y^2}{2\sigma^2}}  \\\frac{\partial^2G}{\partial^2x}=-\frac{\sigma^2-x^2}{2\pi\sigma^6}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\nabla^2G=\frac{\partial^2G}{\partial^2x}+\frac{\partial^2G}{\partial^2y} = \frac{x^2+y^2-2\sigma^2}{2\pi\sigma^6}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\frac{\partial G}{\partial \sigma}=\frac{x^2+y^2-2\sigma^2}{2\pi\sigma^5}e^{-\frac{x^2+y^2}{2\sigma^2}}  \\\therefore \frac{\partial G}{\partial x}=\sigma \nabla^2 G$而考虑$\frac{\partial G}{\partial \sigma}$的近似替代公式：$\sigma\nabla^2G=\frac{\partial G}{\partial \sigma} \approx \frac{G(x,y,k\sigma)-G(x,y,\sigma)}{k\sigma-\sigma}$因此有：$G(x,y,k\sigma)-G(x,y,\sigma) \approx (k-1)\sigma^2\nabla^2G$即：用DoG来近似替代LoGç—子，得到近似不变的尺度无关特性。相å·çš„倍数是常量没有影响。当k->1，误å·å‡ ä¹Žä¸º0.### 高斯金字塔的建立**octave**：采样率相同、尺寸相同，模糊度逐渐增强的一组相邻图像**level**：octave中的每张图像，叫做一个level每个octae内是持续高斯模糊得到；每个octave的第一个levle通过降采样得到。每个octave内有s次模糊。$\sigma$的选取和$s$选取，不能太小，否则不准ç¡ï¼›å¤ªå¤§åˆä¼šæ¶ˆè€—太多è¡ç—资源，得不到åžæ—¶æ•ˆæžœã€‚Lowe的èºæ–‡åžéªŒè¡¨æ˜Žï¼Œé€‰å–$\sigma=1.6$，$s=3$是合适的。不过为了充分åˆç”¨è¾“入的图像，可以考虑在生成octave前做一次升采样：è¤ä¸ºç…§ç›¸æœºé‡‡é›†çš„图像本身就是模糊的，其$\sigma=0.5$，åˆç”¨çº¿æ€§æ’值得到$\sigma=1.0$的图像，然后用于生成octave**疑é—**l升采样后的图像，有没有再次做模糊操作得到octave的第一张？还是说直接作为octave的第一个level？### DoG金字塔每两个高斯金字塔level之间做å·å€¼å°±å¾—到DoG的一个level。为了得到所有极值，因为高斯金字塔的首尾两层不会被带入è¡ç—，因此在首尾各添加一层，最上面再加一层**这æµè¿˜æ˜¯ä¸å¤Ÿæ¸…晰，需要ä¿æ”¹**### 局部极值检测在DoG金字塔中，检测çºé—´ä¸­æ¯ä¸ªåƒç´ ç‚¹å‘¨è¾¹çš„26个点。如果是极值，那么继续往金字塔高层进行检测。极值检测需要考虑检测的策略：检测到的极值点数量会影响到后续的特征检测数量，特征越少则匹配的结果越少，但是往往是正ç¡çŽ‡è¾ƒé«˜çš„匹配；特征越多则匹配的结果越多，但是正ç¡çŽ‡å¾€å¾€ä¸é«˜ã€‚前者更多地考虑了效率，后者更多地考虑了åŒæ•´æ€§ï¼Œéœ€è¦åœ¨æ•ˆçŽ‡å’ŒåŒæ•´æ€§ä¹‹é—´æƒè¡¡ã€‚因而，要选取合适数量的特征数量，在这之前需要选取合适数量的极值点，这就需要考虑采样频率的é—题。（åžé™…上，集中在一起的极值点对于小的扰动非常不稳åšï¼‰ã€‚采样频率的é—题，包括尺度上的采样频率、çºé—´åŸŸä¸Šçš„采样频率两个方面。Lowe通过åžéªŒå¾—到一些测量结果，从结果的图表中得到$s$值和$\sigma$值的经验值。Lowe的åžéªŒå›¾åƒâ€œæœ‰32张，包括å¤å¤–场景、人脸、航拍图片、工业图像（这些图像的来源领域对结果几乎没有影响）”。但是本人è¤ä¸ºï¼Œä»…仅从32张图像就得到相关的经验参数，并不很具有说服力，如果有时间，不妨使用更多的图片进行相关测åšã€‚尺度上的采样频率é—题，就是考虑图像金字塔中每个octave内的尺度çºé—´æ•°é‡s。åžéªŒä¸­å°ºåº¦å›¾åƒç”±éšæœºçš„旋转和0.2~0.9之间的随机尺度变换得到，同时也添加了1%的噪声（使用平均分布为每个像素点增加一个随机数）。åžéªŒç»“果为：随着尺度数量s的增加，同一位ç½çš„重复匹配率“先增加后减小”，同一极值点对应的特征描述符在数æåº“中被**æ­£ç¡**搜索到的比率，也是“先增加后减小”。折可以被解释为：随着尺度数量s的增加，尽ç¡æžå€¼ç‚¹æ•°é‡å¢žåŠ ï¼Œä½†æ˜¯è¿‡äº†ä¸€åšé™åº¦åŽå¢žåŠ çš„极值点都是低于平均稳åšç¨‹åº¦çš„，因而反倒降低了匹配的重复率和正ç¡çŽ‡ã€‚对应于Lowe的åžéªŒç»“果，选取$s=3$时，正ç¡åŒ¹é…çŽ‡æœ€é«˜ã€‚而随着尺度数量s的增加，极值点数量也增加，并且正ç¡åŒ¹é…çš„极值点的总数也是增加的；而通常ç›æ ‡è¯†åˆ«é€šå¸¸æ›´ä¾èµ–于正ç¡åŒ¹é…çš„极值点数量而不是正ç¡åŒ¹é…çŽ‡ï¼Œå› æ­¤çœ‹èµ·æ¥ä½¿ç”¨æ›´å¤§çš„尺度çºé—´æ•°s会得到更好的效果。但是，这会增加è¡ç—消耗。因而，Lowe的èºæ–‡ä¸­æƒè¡¡äº†æ­£ç¡çŽ‡å’Œè¡ç—消耗，选取$s=3$作为每个octave内的尺度数量。也就是说，仅仅检测那些稳åšçš„极值点，同时又能够避免大量的è¡ç—消耗，还能够得到很好的正ç¡çŽ‡ã€‚çºé—´åŸŸä¸Šçš„采样频率é—题，就是高斯模糊的参数$\sigma$，即平滑尺度。考虑到极值可能随机地出现在一起，也需要类似前面一种情况考虑采样频率和检率的é—题。åžéªŒæ•°æè¡¨æ˜Žï¼Œéšç€$\sigma$的增加，同一特征点在变换后的图像中被重复检测到的百分比、极值点对应的特征描述符在数æåº“中被查找到的正ç¡çŽ‡ï¼Œéƒ½å‘ˆçŽ°å¢žåŠ è¶‹åŠ¿ã€‚但是$\sigma$增加后è¡ç—量也增加，权衡考虑ç—法效率和正ç¡çŽ‡ï¼Œä½¿ç”¨$\sigma=1.6$。（同样地，这显然也是Lowe的32张图像的测试结果带来的经验数æï¼Œä¸ªäººè¤ä¸ºè¿™ä¸ªæ•°æè¦æ ¹æä¸åŒçš„情况可以适当ä¿æ”¹ï¼‰ã€‚同时也可以考虑图像预先平滑操作，这样能**有效地忽略最高çºåŸŸé¢‘率**（这句其åžå¹¶ä¸ç†è§£ï¼‰ï¼Œå…¶åšæ³•æ˜¯ï¼šè¤ä¸ºç›¸æœºæ‹æ‘„得到的原始图像的模糊度为$\sigma=0.5$，通过双线性å·å€¼å¾—到$\sigma=1.0$模糊尺度的图像。这就意味着，在创建尺度çºé—´çš„第一个octave之前，需要做一次平滑操作（也就是：原图升采样得到$\sigma=1.0$-->做第一次预先处理的平滑得到$\sigma=1.6$的尺度图像作为第一个octave的第一个level）。**这里发现对于“采样”并不很理解，需要找书仔细看下**## ç¡åšå…³é”点的精ç¡ä½ç½å‰é¢å¾—到的极值，只是离散的图像金字塔中不同尺度下的极值点。真正的尺度çºé—´åº”当是连续的，而不是离散的，图像金字塔中的极值只是真正极值的近似，还需要进一步的精ç¡æ£€æµ‹ï¼Œå¾—到真正的极值点和极值。使用泰勒公式对DoG函数进行展开，并求导，解出导数为0的点，得到的解就是“前面极值检测中检测到的极值采样点，与真正的尺度çºé—´ä¸­çš„极值点的偏å·ï¼ˆè¿™ä¸ªåå·æ˜¯å‘量(x,y,$\sigma$)）”。即：$åšä¹‰å‘量\vec{x} = (x, y, \sigma)对D函数，泰勒展开有：D(\vec {x})=D+\frac{\partial D^T}{\partial \vec {x}}\vec {x} + \frac{1}{2}\vec {x}^T\frac{\partial^2 D}{\partial \vec{x}^2}\vec {x}求解得到：\vec {x_0} = - \frac{\partial^2 D^{-1}}{\partial \vec {x}^2}\frac{\partial D}{\partial \vec {x}} $$其中使用到对于向量求导的è¡ç—，包括：  \\\frac{\partial \vec {x}}{\partial \vec {x}}=单位çŸé˜µE    \\\frac{\partial \vec{x}^T \vec{x}}{\vec{x}} = 2 \vec{x}$将$\vec{x_0}$带入$D(\vec{x})$的表达式，得到对应的极值：$D(\vec{x}) = D + \frac{1}{2}\frac{\partial D^T}{\partial \vec{x}}\vec{x}$åžéªŒä¸­å¿½ç•¥$D \lt 0.03$的极值点。这样，得到的$\vec{x}$表示采样点的偏离量。此时，keypoint的表示中包括了：位ç½(x,y),尺度$\sigma$。后面还会包括方向。### 消除边界响应还需要去除边界上的干扰，需要考虑**主曲率**。 通过è¡ç—**黑塞çŸé˜µ**能得到特征值之间的关系，而主曲率和特征值之间是成倍的关系，因此只需要考虑特征值之间的关系。假è¾é»‘å¡žçŸé˜µç—出的特征值中，大的为$\alpha$，小的为$\beta$，而：$ H=\begin{matrix}     D_{xx} & D_{xy} \\     D_{xy} & D_{yy}\end{matrix}$$Tr(H)=D_{xx}+D_{yy} = \alpha + \beta  \\Det(H)=D_{xx}D_{yy}-(D_{xy})^2 = \alpha \beta$显然，$\frac{Tr(H)}{Det(H)}$是增函数，因此只需要保证：$\frac{Tr(H)^2}{Det(H)}