苏州网站建设点一点,网站推广公司成功的经典案例,优化网站定制,网上怎么找承包小工程系列文章目录 文章目录 系列文章目录引言一、高斯金字塔二、高斯差分金字塔三、特征点处理四、特征点描述子总结 引言
SIFT算法是为了解决图片的匹配问题#xff0c;想要从图像中提取一种对图像的大小和旋转变化保持鲁棒的特征#xff0c;从而实现匹配。这一算法的灵感也十分…系列文章目录 文章目录 系列文章目录引言一、高斯金字塔二、高斯差分金字塔三、特征点处理四、特征点描述子总结 引言
SIFT算法是为了解决图片的匹配问题想要从图像中提取一种对图像的大小和旋转变化保持鲁棒的特征从而实现匹配。这一算法的灵感也十分的直观人眼观测两张图片是否匹配时会注意到其中的典型区域特征点部分如果我们能够实现这一特征点区域提取过程再对所提取到的区域进行描述就可以实现特征匹配了。于是问题就演变成了以下几个子问题
应该选取什么样的点作为特征点呢人眼对图像中的高频区域更加的敏感由此我们应该选择变化剧烈的边缘或者角点进行检测这里我们选择检测角点。这里的intuition不是很明白但感觉来说可能是我们提取的是特征点进行匹配而边缘往往是由多个点组成。 怎样使得选取的特征点有尺度不变性呢使用高斯金字塔获取不同尺寸下的图像变体由这些变体获得尺度不变特征。 怎样使得选取的特征点有缩放不变性呢使用高斯金字塔获取不同尺寸下的图像变体每个变体里都提取特征点再缩放回原大小以获得图像不同尺寸下的特征点。 怎样使得选取的特征点有旋转不变性呢后续采取将特征点区域旋转到主方向的设定以获得旋转不变性。 如何描述特征点区域呢 使用特征点区域内每个方向的梯度赋值类似HOG算子。
以上几个问题在SIFT算法里都用了很有意思的trick后续会一一介绍。
一、高斯金字塔
引入高斯金字塔的目的在引言中已经介绍过了–解决图片缩放及尺度变化下特征提取的问题高斯金字塔的Intuition有两个1. 人看物体时近大远小可以对图片下采样实现金字塔-组2. 人看物体时近处清晰远处模糊可以对图像高斯平滑实现高斯-层具体的推导可以参见我的另一篇博客 Opencv学习笔记六图像金字塔 在SIFT里高斯金字塔的层数和组数有着如下设定
组数 O [ l o g 2 m i n ( M , N ) ] − 3 O[log_2min(M,N)]-3 O[log2min(M,N)]−3
层数 S n 3 Sn3 Sn3
组数的设定是来自于提出SIFT算法的原始论文给出的经验值理论上来说知要 O ≤ [ l o g 2 m i n ( M , N ) ] O\leq[log_2min(M,N)] O≤[log2min(M,N)]即可层数的设定则是有着理论依据的这里的 n n n是我们想要提取特征点的图片层数由于提取出高斯金字塔后需要计算层间差分以获得高斯差分金字塔(DOG, Difference of Gausssian)高斯金字塔层数需要比DOG层数多1而计算特征值时要求在尺度层面即上下相邻层间计算则DOG层数要比特征层数多2则要求 S n 3 Sn3 Sn3。
附在SIFT中对于高斯金字塔有几个需要补充的知识点。
SIFT算法中的S指的是scale即尺度的概念这一概念有别于传统的图像尺寸而是一种连续变化的参数在高斯金字塔里的 σ \sigma σ就是这样一个尺度空间的参数更特殊的高斯核是唯一可以产生连续多尺度变化的线性核这就是为什么我们用高斯金字塔这一部分内容涉及到尺度空间的概念可以自行了解。 图像金子塔一文中提到了两个基础参数层间尺度变化系数 k k k和初始尺度 σ 0 \sigma_0 σ0在原始算法中规定 k 2 o r n r 0 , 1… , n 2 k2^{o\frac{r}{n}}r{0,1…,n2} k2onrr0,1…,n2由于每组的起始层是由前一组倒数第三层降采样得到实际上保证了每组开始的尺度为 σ 0 , 2 σ 0 , 3 σ 0 . . . \sigma_0,2\sigma_0,3\sigma_0… σ0,2σ0,3σ0…。此外我们提到 σ 0 1.6 \sigma_01.6 σ01.6而实际拍摄图片时相机已经原始景物进行了一次尺度变换此变换的系数原文设定经验值为 σ ′ 0.5 \sigma’0.5 σ′0.5由此我们得到 σ 0 1. 6 2 − σ ′ 2 1.52 \sigma_0\sqrt{1.62-\sigma’2}1.52 σ01.62−σ′2
1.52。这一式子的来历为高斯滤波体现为高斯核与原图进行卷积 f ( x ) ⨂ G ′ ( x ) f(x)\bigotimes G’(x) f(x)⨂G′(x)两次高斯滤波的级联相当于 f ( x ) ⨂ ( G ′ ( x ) ⨂ G ( x ) ) f(x)\bigotimes (G’(x) \bigotimes G(x)) f(x)⨂(G′(x)⨂G(x))而两个高斯卷积的结果仍为高斯卷积且方差满足平方和关系可用时域卷积或者傅里叶变换证明详见参考文献。
二、高斯差分金字塔
通过高斯金字塔我们获取了不同尺度的图片接下来的问题是如何获取高频区域呢一个很简单的思路就是按照边缘检测的算法使用差分滤波器如拉普拉斯滤波器、sobel滤波器在图片上滑动找到灰度值变化剧烈的区域。而经前人研究归一化的高斯拉普拉斯算子的极大值极小值相较于其他特征提取函数可以获得最稳定的图像特征因此我们打算使用归一化的高斯拉普拉斯算子在多尺度图片上提取特征但是使用这种方式提取复杂度会很高又尺度归一化高斯拉普拉斯算子和DOG函数有着如下关系: G ( x , y , k σ ) − G ( x , y , σ ) ≈ ( k − 1 ) σ 2 ∇ 2 G G(x,y,k\sigma)-G(x,y,\sigma)\approx(k-1)\sigma^2 \nabla^2 G G(x,y,kσ)−G(x,y,σ)≈(k−1)σ2∇2G 证明如下 忽略高斯函数系数: G ( x , y , σ ) 1 σ 2 e x p ( − x 2 y 2 2 σ 2 ) ∂ G ∂ x − x σ 4 e x p ( − x 2 y 2 2 σ 2 ) ∂ 2 G ∂ x 2 − σ 2 x 2 σ 6 e x p ( − x 2 y 2 2 σ 2 ) ∇ 2 G ( x , y ) ∂ 2 G ∂ x 2 ∂ 2 G ∂ y 2 − 2 σ 2 x 2 y 2 σ 6 e x p ( − x 2 y 2 2 σ 2 ) ∂ G ∂ σ − 2 σ 2 x 2 y 2 σ 5 e x p ( − x 2 y 2 2 σ 2 ) ⇒ σ ∇ 2 G ∂ G ∂ σ G(x,y,σ)1σ2exp(−x2y22σ2)∂G∂x−xσ4exp(−x2y22σ2)∂2G∂x2−σ2x2σ6exp(−x2y22σ2)∇2G(x,y)∂2G∂x2∂2G∂y2 −2σ2x2y2σ6exp(−x2y22σ2)∂G∂σ−2σ2x2y2σ5exp(−x2y22σ2)⇒σ∇2G∂G∂σ
G(x,y,σ)σ21exp(−2σ2x2y2)∂x∂G−σ4xexp(−2σ2x2y2)∂x2∂2Gσ6−σ2x2exp(−2σ2x2y2)∇2G(x,y)∂x2∂2G∂y2∂2G σ6−2σ2x2y2exp(−2σ2x2y2)∂σ∂Gσ5−2σ2x2y2exp(−2σ2x2y2)⇒σ∇2G∂σ∂G 又对于差分高斯金字塔有 D O G G ( x , y , k σ ) − G ( x , y , σ ) ( k − 1 ) σ ≈ ∂ G ∂ σ D O G ≈ ( k − 1 ) σ 2 ∇ 2 G \begin{aligned} DOG\frac{G(x,y,k\sigma)-G(x,y,\sigma)}{(k-1)\sigma}\approx \frac{\partial G}{\partial \sigma}\ DOG \approx(k-1)\sigma2\nabla2G \end {aligned} DOG(k−1)σG(x,y,kσ)−G(x,y,σ)≈∂σ∂GDOG≈(k−1)σ2∇2G 由此我们不再需要在高斯金子塔上进行卷积操作只需要计算在尺度层面 σ \sigma σ进行层间差分得到高斯差分金字塔(DOG)即完成了特征提取的操作。 在这里插入图片描述
三、特征点处理
得到DOG后我们理论上来说就已经获得了特征值但我们需要对特征值进行一些处理就像我们在cannny边缘检测中使用的非极大值抑制等思路去掉没那么特征的特征值。 1.阈值化
简单的阈值化去除掉变换没有那么剧烈的点这些点就有可能是噪声引起的算是在高斯拉普拉斯之外又加了一层去噪措施。 v a l { v a l a b s ( v a l ) 0.5 T n 0 o t h e r w i s e val {val0abs(val)0.5Tnotherwise
val{val0abs(val)0.5nTotherwise 这里的 T T T为经验值0.04 n n n为之前提过的提取特征点数目。 2.非极大值抑制
非极大值一致的思路就和在其他算法中的一样我们要求选取出的特征值应该是其领域范围内的极值不同之处在于其他算法要求的只是图像这一二维平面内的极值而这里要求还要在尺度 σ \sigma σ这一层面上也是极值这也承接了前文DOG层数要比提取特征所用层数多2的设定。 在这里插入图片描述 3. 二阶泰勒修正
由于我们的图片在 x , y , σ x,y,\sigma x,y,σ方向上都只能取到离散值即使通过前两个步骤取到了一些特征点但这些特征点都不够精确我们需要引入二阶泰勒函数对齐进行修正使得特征点可以出现在亚像素亚尺度位置。 在这里插入图片描述
f ( X ) f ( X 0 ) ∂ f T ∂ X X ^ 1 2 X T ^ ∂ 2 f ∂ X 2 X ^ f(X)f(X_0)\frac{\partial f^T}{\partial X}\hat{X}\frac{1}{2}\hat{XT}\frac{\partial2 f}{\partial X^2}\hat{X} f(X)f(X0)∂X∂fTX21XT∂X2∂2fX^ 上式给出了特征点 X 0 X_0 X0附近函数的近似值 f ( x ) f(x) f(x)其中 X ^ X − X 0 \hat{X}X-X_0 X^X−X0对该式求取一阶导数零点即可得函数实际极值点位置与 X 0 X_0 X0的距离从而对离散特征点修正到亚尺度处。 f ′ ( X ) ∂ f T ∂ X ∂ f 2 ∂ X 2 X ^ f’(X)\frac{\partial f^T}{\partial X}\frac{\partial f^2}{\partial X^2}\hat{X} f′(X)∂X∂fT∂X2∂f2X^
X ^ e x − ∂ 2 f − 1 ∂ X 2 ∂ f ∂ X \hat{X}{ex}-\frac{\partial^2 f^{-1}}{\partial X^2}\frac{\partial f}{\partial X} X^ex−∂X2∂2f−1∂X∂f 带入前式可求取新的特征点的灰度值 f ( X ′ ) f ( X 0 ) 1 2 ∂ f T ∂ X ′ X ^ e x f(X’)f(X_0)\frac{1}{2}\frac{\partial f^T}{\partial X’}\hat{X}{ex} f(X′)f(X0)21∂X′∂fTX^ex 需要注意的是上式是一个不断迭代的过程也即根据当前特征点二阶泰勒求取新的特征点这一过程会不断重复直到满足终止条件如 X ^ \hat{X} X^过小。另需注意当所得解超出离散极值点一定范围时需要舍去因为二阶泰勒拟合只在其附近有效。
附一个挺有意思的点在于这里的迭代目的和梯度下降法里的迭代并不是同一个目的梯度下降里我们求取的是函数在某点的梯度因为我们很难对复杂非线性的神经网络求除其一阶导数零点即使求取到了也可能落入局部极值而这里我们是直接求到了函数的一阶零点迭代的目的是因为函数本身是一种近似泰勒展开只取到了第二项需要不断对原函数进行近似。这两种迭代的目的并不相同。 4.低对比度去除
目的和之间的阈值化类似同样是去除掉没那么剧烈变化的特征点。要求 ∣ f ( x ) ∣ ≥ T n |f(x)|\geq\frac{T}{n} ∣f(x)∣≥nT 5.边缘效应去除
引言中提过我们想要提取的特征点为角点而非边缘而前述一系列措施只能保证取到灰度值变换剧烈的点而边缘点同样符合这一特征因此我们将通过以下方式去除边缘点。
计算黑森矩阵 H ( x , y ) [ D x x ( x , y ) D x y ( x , y ) D y x ( x , y ) D y y ( x , y ) ] H(x,y)
[Dxx(x,y)Dyx(x,y)Dxy(x,y)Dyy(x,y)]H(x,y)[Dxx(x,y)Dyx(x,y)Dxy(x,y)Dyy(x,y)]
若矩阵行列式 D e t ( H ) 0 Det(H)0 Det(H)0舍去该特征点
若矩阵行列式和迹不满足 T r ( H ) D e t ( H ) ( γ 0 1 ) 2 γ 0 \frac{Tr(H)}{Det(H)}\frac{(\gamma_01)^2}{\gamma_0} Det(H)Tr(H)γ0(γ01)2舍去该特征点 γ 0 \gamma_0 γ0为有实际意义的经验值通常设定为10。接下来解释以下这几个步骤的意义角点和边缘点的区别在于边缘在图像中表现为一条线垂直于线的方向频率高沿着线的方向频率比较低而角点则在多大于2个方向方向出现强高频分量。黑森矩阵实际上是函数的二阶偏导构成的矩阵可以反应函数的曲率变化状况。又对于二次型矩阵有如下性质
假定二次型矩阵 H H H两个特征值为 α , β \alpha,\beta α,β则 D e t ( H ) α β Det(H)\alpha\beta Det(H)αβ T r ( H ) α β Tr(H)\alpha\beta Tr(H)αβ;
实二次型矩阵的特征值异号时该矩阵为不定矩阵黑森矩阵为不定矩阵时该临界点为非极值点
黑森矩阵的特征值标定了函数在相应特征向量方向上变化的快慢。由性质12我们可以推导处当 D e t ( H ) 0 Det(H)0 Det(H)0时特征点为非极值点舍去 由性质13我们可以推导出当 T r ( H ) D e t ( H ) ( α β ) 2 α 2 β 2 \frac{Tr(H)}{Det(H)}\frac{(\alpha\beta)2}{\alpha2\beta^2} Det(H)Tr(H)α2β2(αβ)2过小时由两特征特征向量的比值 γ \gamma γ构成的式子 ( γ 1 ) 2 γ \frac{(\gamma1)^2}{\gamma} γ(γ1)2同样较小且对勾函数在 γ 1 \gamma1 γ1时单增我们可以根据 T r ( H ) D e t ( H ) \frac{Tr(H)}{Det(H)} Det(H)Tr(H)大小判断特征向量的相对大小该值过小说明函数在该点不同方向上的变化非常不均匀类似于边缘舍去。
四、特征点描述子
通过前述步骤我们已经获得了不同尺寸层面上的稳定特征点接下来需要对其进行描述。
确定特征点区域方向
引言中提到为了使特征点拥有旋转不变性我们会将特征点区域统一旋转到特定方向这一方向即为特征点区域的主方向因此我们需要先确定主方向。 计算方式为统计在离该特征点尺度 σ ∗ \sigma^* σ∗最近的尺度层 σ o c t 上 \sigma_{oct}上 σoct上以特征点为中心 3 σ ′ 3 ∗ 1.5 σ o c t 3\sigma’31.5\sigma_{oct} 3σ′3∗1.5σoct范围内的像素的梯度幅值及方向对于范围内的梯度幅值用 1.5 σ ∗ 1.5\sigma^ 1.5σ∗高斯核滤波以实现距离加权。得到一系列梯度幅值和方向对 p a i r s { a m p , a n g } pairs{amp,ang} pairs{amp,ang}后将 360 ° 360° 360°方向划分为多个bins将包含相应 a n g ang ang的 p a i r s pairs pairs中的 a m p amp amp值累加到对应的bins上如果 a n g ang ang在两个bins划分间则根据距离分配 a m p amp amp。此处和HOG算法类似可自行查阅。最终可以获得特征点区域内幅值-方向直方图选取其中幅值最大的方向作为主方向。 在这里插入图片描述 附这里的几个参数像是统计区域的半径高斯加权的方差有着不同的设置方式但内在思路是一致的。此外如果在主方向之外出现了幅值达到了主方向幅值80%的其他方向我们会将其作为辅方向后续匹配时会出现两个位置、尺度相同但方向不同的两个特征点区域。 2. 特征点区域描述子
获得了特征点区域的主方向之后我们就可以利用该值计算出有旋转不变性的描述子了。首先还是和前一步类似统计该特征点所在尺度层面一定区域内的梯度幅值和方向实施起来略有不同。
首先在特征点所处尺度层面内划定特征区域半径为
r 3 2 σ o c t ( d 1 ) 2 r\frac{3\sqrt{2}\sigma_{oct}(d1)}{2} r232σoct(d1)其中 d d d为我们在一个维度上划分的子块数目通常为4
将该区域划分为共 d ∗ d d*d d∗d个子块每个子块内包含多个像素点
将划定出来的区域旋转到该区域的主方向前一步已求出
在每个子块内构筑幅值-方向直方图统计8个方向的梯度幅值。由此该区域可用 8 ∗ d ∗ d 8*d*d 8∗d∗d维向量表示由此完成了特征点区域描述子的构建在这里插入图片描述
附需要注意的是以上的计算都是发生在相应的高斯金字塔尺度层面上而非原图或者DOG上此外由于旋转产生的像素值丢失通过插值算法解决可以自行了解。如果想在原图上可视化SIFT特征需要将我们获得的稳定特征点坐标变换回原始的图像尺寸上简单的乘以原下采样倍数即可。总结
至此SIFT算法就讲解完毕了匹配的部分根据提的特征采用其他的聚类算法即可总的来说这个算法还是有一定难度本文也只是针对其他博客没有提到的细节引入了数学推导使得整个思考过程更加连贯更加详细的数学证明如有限差分法还请移步参考。 https://blog.csdn.net/Dr_maker/article/details/121442210
