建设网站文献,软件工程考研难度大吗,班级主页网页设计模板,大连建站模板厂家学习目标
理解 S I F T / S U R F SIFT/SURF SIFT/SURF算法的原理#xff0c;能够使用 S I F T / S U R F SIFT/SURF SIFT/SURF进行关键点的检测 SIFT/SURF算法
1.1 SIFT原理
前面两节我们介绍了 H a r r i s Harris Harris和 S h i − T o m a s i Shi-Tomasi Shi−Tomasi…学习目标
理解 S I F T / S U R F SIFT/SURF SIFT/SURF算法的原理能够使用 S I F T / S U R F SIFT/SURF SIFT/SURF进行关键点的检测 SIFT/SURF算法
1.1 SIFT原理
前面两节我们介绍了 H a r r i s Harris Harris和 S h i − T o m a s i Shi-Tomasi Shi−Tomasi角点检测算法这两种算法具有旋转不变性但不具有尺度不变性以下图为例在左侧小图中可以检测到角点但是图像被放大后在使用同样的窗口就检测不到角点了。 所以下面我们来介绍一种计算机视觉的算法尺度不变特征转换即 S I F T ( S c a l e − i n v a r i a n t f e a t u r e t r a n s f o r m ) SIFT (Scale-invariant feature transform) SIFT(Scale−invariantfeaturetransform)。它用来侦测与描述影像中的局部性特征它在空间尺度中寻找极值点并提取出其位置、尺度、旋转不变量此算法由 David Lowe在1999年所发表2004年完善总结。应用范围包含物体辨识、机器人地图感知与导航、影像缝合、3D模型建立、手势辨识、影像追踪和动作比对等领域。
SIFT算法的实质是在不同的尺度空间上查找关键点(特征点)并计算出关键点的方向。SIFT所查找到的关键点是一些十分突出不会因光照仿射变换和噪音等因素而变化的点如角点、边缘点、暗区的亮点及亮区的暗点等。
1.1.1 基本流程 L o w e Lowe Lowe将 S I F T SIFT SIFT算法分解为如下四步
尺度空间极值检测搜索所有尺度上的图像位置。通过高斯差分函数来识别潜在的对于尺度和旋转不变的关键点。关键点定位在每个候选的位置上通过一个拟合精细的模型来确定位置和尺度。关键点的选择依据于它们的稳定程度。关键点方向确定基于图像局部的梯度方向分配给每个关键点位置一个或多个方向。所有后面的对图像数据的操作都相对于关键点的方向、尺度和位置进行变换从而保证了对于这些变换的不变性。关键点描述在每个关键点周围的邻域内在选定的尺度上测量图像局部的梯度。这些梯度作为关键点的描述符它允许比较大的局部形状的变形或光照变化。
我们就沿着 L o w e Lowe Lowe的步骤对 S I F T SIFT SIFT算法的实现过程进行介绍
1.1.2 尺度空间极值检测
在不同的尺度空间是不能使用相同的窗口检测极值点对小的关键点使用小的窗口对大的关键点使用大的窗口为了达到上述目的我们使用尺度空间滤波器。 高斯核是唯一可以产生多尺度空间的核函数。-《Scale-space theory: A basic tool for analysing structures at different scales》。 一个图像的尺度空间 L ( x , y , σ ) L(x,y,σ) L(x,y,σ)定义为原始图像 I ( x , y ) I(x,y) I(x,y)与一个可变尺度的 2 2 2维高斯函数 G ( x , y , σ ) G(x,y,σ) G(x,y,σ)卷积运算 即 L ( x , y , σ ) G ( x , y , σ ) ∗ I ( x , y ) L(x,y,σ)G(x,y,σ)∗I(x,y) L(x,y,σ)G(x,y,σ)∗I(x,y)
其中 G ( x , y , σ ) 1 2 π σ 2 e x 2 y 2 2 σ 2 G(x,y,σ) \frac{1}{2πσ^{2}}e^{\frac{x^{2}y^{2}}{2σ^{2}}} G(x,y,σ)2πσ21e2σ2x2y2 σ σ σ是尺度空间因子它决定了图像的模糊的程度。在大尺度下 σ σ σ值大表现的是图像的概貌信息在小尺度下 σ σ σ值小表现的是图像的细节信息。
在计算高斯函数的离散近似时在大概 3 σ 3σ 3σ距离之外的像素都可以看作不起作用这些像素的计算也就可以忽略。所以在实际应用中只计算 ( 6 σ 1 ) ∗ ( 6 σ 1 ) (6σ1)*(6σ1) (6σ1)∗(6σ1)的高斯卷积核就可以保证相关像素影响。
下面我们构建图像的高斯金字塔它采用高斯函数对图像进行模糊以及降采样处理得到的高斯金字塔构建过程中首先将图像扩大一倍在扩大的图像的基础之上构建高斯金字塔然后对该尺寸下图像进行高斯模糊几幅模糊之后的图像集合构成了一个 O c t a v e Octave Octave然后对该 O c t a v e Octave Octave下选择一幅图像进行下采样长和宽分别缩短一倍图像面积变为原来四分之一。这幅图像就是下一个 O c t a v e Octave Octave的初始图像在初始图像的基础上完成属于这个 O c t a v e Octave Octave的高斯模糊处理以此类推完成整个算法所需要的所有八度构建这样这个高斯金字塔就构建出来了整个流程如下图所示 利用 L o G LoG LoG(高斯拉普拉斯方法)即图像的二阶导数可以在不同的尺度下检测图像的关键点信息从而确定图像的特征点。但 L o G LoG LoG的计算量大效率低。所以我们通过两个相邻高斯尺度空间的图像的相减得到 D o G DoG DoG(高斯差分)来近似 L o G LoG LoG。
为了计算 D o G DoG DoG我们构建高斯差分金字塔该金字塔是在上述的高斯金字塔的基础上构建而成的建立过程是在高斯金字塔中每个 O c t a v e Octave Octave中相邻两层相减就构成了高斯差分金字塔。如下图所示
高斯差分金字塔的第 1 1 1组第 1 1 1层是由高斯金字塔的第1组第2层减第1组第1层得到的。以此类推逐组逐层生成每一个差分图像所有差分图像构成差分金字塔。概括为 D O G DOG DOG金字塔的第 o o o组第 l l l层图像是有高斯金字塔的第 o o o组第 l 1 l1 l1层减第 o o o组第 l l l层得到的。后续 S i f t Sift Sift特征点的提取都是在 D O G DOG DOG金字塔上进行的
在 D o G DoG DoG 搞定之后就可以在不同的尺度空间中搜索局部最大值了。对于图像中的一个像素点而言它需要与自己周围的 8 8 8 邻域以及尺度空间中上下两层中的相邻的 18 2 x 9 182x9 182x9个点相比。如果是局部最大值它就可能是一个关键点。基本上来说关键点是图像在相应尺度空间中的最好代表。如下图所示 搜索过程从每组的第二层开始以第二层为当前层对第二层的 D o G DoG DoG图像中的每个点取一个 3 × 3 3×3 3×3的立方体立方体上下层为第一层与第三层。这样搜索得到的极值点既有位置坐标 D o G DoG DoG的图像坐标又有空间尺度坐标层坐标。当第二层搜索完成后再以第三层作为当前层其过程与第二层的搜索类似。当 S 3 S3 S3时每组里面要搜索 3 3 3层所以在 D O G DOG DOG中就有 S 2 S2 S2层在初使构建的金字塔中每组有 S 3 S3 S3层。
1.1.3 关键点定位
由于 D o G DoG DoG对噪声和边缘比较敏感因此在上面高斯差分金字塔中检测到的局部极值点需经过进一步的检验才能精确定位为特征点。
使用尺度空间的泰勒级数展开来获得极值的准确位置 如果极值点的 灰度值小于阈值一般为 0.03 0.03 0.03或 0.04 0.04 0.04就会被忽略掉。 在 OpenCV 中这种阈值被称为 contrastThreshold。 D o G DoG DoG 算法对边界非常敏感 所以我们必须要把边界去除。 H a r r i s Harris Harris 算法除了可以用于角点检测之外还可以用于检测边界。从 H a r r i s Harris Harris 角点检测的算法中当一个特征值远远大于另外一个特征值时检测到的是边界。那在 D o G DoG DoG算法中欠佳的关键点在平行边缘的方向有较大的主曲率而在垂直于边缘的方向有较小的曲率两者的比值如果高于某个阈值在OpenCV中叫做边界阈值就认为该关键点为边界将被忽略一般将该阈值设置为 10 10 10。
将低对比度和边界的关键点去除得到的就是我们感兴趣的关键点。
1.1.4 关键点方向确定
经过上述两个步骤图像的关键点就完全找到了这些关键点具有尺度不变性。为了实现旋转不变性还需要为每个关键点分配一个方向角度也就是根据检测到的关键点所在高斯尺度图像的邻域结构中求得一个方向基准。
对于任一关键点我们采集其所在高斯金字塔图像以r为半径的区域内所有像素的梯度特征幅值和幅角半径 r r r为 r 3 × 1.5 σ r3×1.5σ r3×1.5σ
其中σ是关键点所在 o c t a v e octave octave的图像的尺度可以得到对应的尺度图像。
梯度的幅值和方向的计算公式为 m ( x , y ) ( L ( x 1 , y ) − L ( x − 1 , y ) 2 ( L ( x , y 1 ) − L ( x , y − 1 ) ) 2 m(x,y)\sqrt{(L(x1,y)-L(x-1,y)^{2}(L(x,y1)-L(x,y-1))^{2}} m(x,y)(L(x1,y)−L(x−1,y)2(L(x,y1)−L(x,y−1))2 θ ( x , y ) a r c t a n ( L ( x , y 1 ) − L ( x , y − 1 ) L ( x 1 , y ) − L ( x − 1 , y ) ) θ(x,y)arctan(\frac{L(x,y1)-L(x,y-1)}{L(x1,y)-L(x-1,y)}) θ(x,y)arctan(L(x1,y)−L(x−1,y)L(x,y1)−L(x,y−1))
邻域像素梯度的计算结果如下图所示
完成关键点梯度计算后使用直方图统计关键点邻域内像素的梯度幅值和方向。具体做法是将 360 ° 360° 360°分为 36 36 36柱每 10 ° 10° 10°为一柱然后在以r为半径的区域内将梯度方向在某一个柱内的像素找出来然后将他们的幅值相加在一起作为柱的高度。因为在r为半径的区域内像素的梯度幅值对中心像素的贡献是不同的因此还需要对幅值进行加权处理采用高斯加权方差为 1.5 σ 1.5σ 1.5σ。如下图所示为简化图中只画了 8 8 8个方向的直方图。 每个特征点必须分配一个主方向还需要一个或多个辅方向增加辅方向的目的是为了增强图像匹配的鲁棒性。辅方向的定义是当一个柱体的高度大于主方向柱体高度的80%时则该柱体所代表的的方向就是给特征点的辅方向。
直方图的峰值即最高的柱代表的方向是特征点邻域范围内图像梯度的主方向但该柱体代表的角度是一个范围所以我们还要对离散的直方图进行插值拟合以得到更精确的方向角度值。利用抛物线对离散的直方图进行拟合如下图所示 获得图像关键点主方向后每个关键点有三个信息 ( x , y , σ , θ ) (x,y,σ,θ) (x,y,σ,θ)位置、尺度、方向。由此我们可以确定一个 S I F T SIFT SIFT特征区域。通常使用一个带箭头的圆或直接使用箭头表示 S I F T SIFT SIFT区域的三个值中心表示特征点位置半径表示关键点尺度箭头表示方向。如下图所示
1.1.5 关键点描述
通过以上步骤每个关键点就被分配了位置尺度和方向信息。接下来我们为每个关键点建立一个描述符该描述符既具有可区分性又具有对某些变量的不变性如光照视角等。而且描述符不仅仅包含关键点也包括关键点周围对其有贡献的的像素点。主要思路就是通过将关键点周围图像区域分块计算块内的梯度直方图生成具有特征向量对图像信息进行抽象。
描述符与特征点所在的尺度有关所以我们在关键点所在的高斯尺度图像上生成对应的描述符。以特征点为中心将其附近邻域划分为 d ∗ d d∗d d∗d个子区域一般取 d 4 d4 d4)每个子区域都是一个正方形边长为 3 σ 3σ 3σ考虑到实际计算时需进行三次线性插值所以特征点邻域的为 3 σ ( d 1 ) ∗ 3 σ ( d 1 ) 3σ(d1)∗3σ(d1) 3σ(d1)∗3σ(d1)的范围如下图所示 为了保证特征点的旋转不变性以特征点为中心将坐标轴旋转为关键点的主方向如下图所示 计算子区域内的像素的梯度并按照 σ 0.5 d σ0.5d σ0.5d进行高斯加权然后插值计算得到每个种子点的八个方向的梯度插值方法如下图所示
每个种子点的梯度都是由覆盖其的 4 4 4个子区域插值而得的。如图中的红色点落在第 0 0 0行和第 1 1 1行之间对这两行都有贡献。对第 0 0 0行第 3 3 3列种子点的贡献因子为 d r dr dr对第 1 1 1行第3列的贡献因子为 1 − d r 1-dr 1−dr同理对邻近两列的贡献因子为 d c dc dc和 1 − d c 1-dc 1−dc对邻近两个方向的贡献因子为 d o do do和 1 − d o 1-do 1−do。则最终累加在每个方向上的梯度大小为 w e i g h t w ∗ d r k ( 1 − d r ) 1 − k d c m ( 1 − d c ) 1 − m d o n ( 1 − d o ) 1 − n weightw*dr^{k}(1-dr)^{1-k}dc^{m}(1-dc)^{1-m}do^{n}(1-do)^{1-n} weightw∗drk(1−dr)1−kdcm(1−dc)1−mdon(1−do)1−n
其中 k m n kmn kmn为 0 0 0或为 1 1 1。 如上统计4∗4∗8128个梯度信息即为该关键点的特征向量按照特征点的对每个关键点的特征向量进行排序就得到了SIFT特征描述向量。
1.1.6 总结 S I F T SIFT SIFT在图像的不变特征提取方面拥有无与伦比的优势但并不完美仍然存在实时性不高有时特征点较少对边缘光滑的目标无法准确提取特征点等缺陷自 S I F T SIFT SIFT算法问世以来人们就一直对其进行优化和改进其中最著名的就是 S U R F SURF SURF算法。
1.2 SURF原理
使用 S I F T SIFT SIFT 算法进行关键点检测和描述的执行速度比较慢 需要速度更快的算法。 2006 年 Bay提出了 S U R F SURF SURF 算法是 S I F T SIFT SIFT算法的增强版它的计算量小运算速度快提取的特征与 S I F T SIFT SIFT几乎相同将其与 S I F T SIFT SIFT算法对比如下 1.3 实现
在OpenCV中利用SIFT检测关键点的流程如下所示
1.实例化sift
sift cv.xfeatures2d.SIFT_create()2.利用sift.detectAndCompute()检测关键点并计算
kp,des sift.detectAndCompute(gray,None)参数
gray: 进行关键点检测的图像注意是灰度图像
返回
kp: 关键点信息包括位置尺度方向信息des: 关键点描述符每个关键点对应128个梯度信息的特征向量
3.将关键点检测结果绘制在图像上
cv.drawKeypoints(image, keypoints, outputimage, color, flags)参数
image: 原始图像keypoints关键点信息将其绘制在图像上outputimage输出图片可以是原始图像color颜色设置通过修改b,g,r的值,更改画笔的颜色b蓝色g绿色r红色。flags绘图功能的标识设置 cv2.DRAW_MATCHES_FLAGS_DEFAULT创建输出图像矩阵使用现存的输出图像绘制匹配对和特征点对每一个关键点只绘制中间点cv2.DRAW_MATCHES_FLAGS_DRAW_OVER_OUTIMG不创建输出图像矩阵而是在输出图像上绘制匹配对cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS对每一个特征点绘制带大小和方向的关键点图形cv2.DRAW_MATCHES_FLAGS_NOT_DRAW_SINGLE_POINTS单点的特征点不被绘制 S U R F SURF SURF算法的应用与上述流程是一致这里就不在赘述。
示例
利用 S I F T SIFT SIFT算法在中央电视台的图片上检测关键点并将其绘制出来
import cv2 as cv
import numpy as np
import matplotlib.pyplot as plt
# 1 读取图像
img cv.imread(./image/tv.jpg)
gray cv.cvtColor(img,cv.COLOR_BGR2GRAY)
# 2 sift关键点检测
# 2.1 实例化sift对象
sift cv.xfeatures2d.SIFT_create()# 2.2 关键点检测kp关键点信息包括方向尺度位置信息des是关键点的描述符
kp,dessift.detectAndCompute(gray,None)
# 2.3 在图像上绘制关键点的检测结果
cv.drawKeypoints(img,kp,img,flagscv.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)
# 3 图像显示
plt.figure(figsize(8,6),dpi100)
plt.imshow(img[:,:,::-1]),plt.title(sift检测)
plt.xticks([]), plt.yticks([])
plt.show()结果 总结
SIFT原理 尺度空间极值检测构建高斯金字塔高斯差分金字塔检测极值点。 关键点定位去除对比度较小和边缘对极值点的影响。 关键点方向确定利用梯度直方图确定关键点的方向。 关键点描述对关键点周围图像区域分块计算块内的梯度直方图生成具有特征向量对关键点信息进行描述。
APIcv.xfeatures2d.SIFT_create()
SURF算法
对SIFT算法的改进在尺度空间极值检测关键点方向确定关键点描述方面都有改进提高效率
