OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

【自取】最近整理的,有需要可以领取学习:

如果需要处理的原图及代码,请移步小编的GitHub地址

传送门:请点击我

如果点击有误:https://github.com/LeBron-Jian/ComputerVisionPractice

前言

特征点检测在目标匹配、目标跟踪、三维重建等领域有着广泛的应用。在目标建模中,从图像中提取目标特征,如颜色、角点、特征点、轮廓、纹理等。现在学习常用的特征点检测方法。[en]Feature point detection is widely used in target matching, target tracking, 3D reconstruction and other applications. In target modeling, target features are extracted from the image, such as color, corner, feature point, outline, texture and so on. And now learn the commonly used feature point detection.

总结提取特征点的功能:[en]Summarize the function of extracting feature points:

  • 1,运动目标跟踪
  • 2,物体识别
  • 3,图像配准
  • 4,全景图像拼接
  • 5,三维重建

一个重要的点特征是角点。本文研究了基于角点检测的算法:Harris角点检测SIFT特征。[en]An important point feature is * corner * . This paper studies the algorithms based on corner detection: * Harris corner detection * and * SIFT feature * .

1,Sift之前的江湖

(这段的地址:https://blog.csdn.net/dcrmg/article/details/52577555)

在Sift横空出世之前,特征点检测与匹配江湖上占据霸主地位的是角点检测家族。先探究一下角点家族不为人知的恩怨情仇。

角点家族的族长是Moravec在1977年提出的Moravec角点检测算子。它是一种基于灰度方差的角点检测方法。该运算符计算图像中像素在水平和垂直方向上的灰度差,以确定角点位置。Moravec是第一个角点检测算法,也是角点族的创始人。[en]The patriarch of the corner family is the Moravec corner detection operator proposed by Moravec in 1977. It is a corner detection method based on gray variance. This operator calculates the gray difference of a pixel in the image along the horizontal and vertical direction to determine the corner position. Moravec is the first corner detection algorithm and the founder of the corner family.

角点的九袋老人是Chris Harris和Mike Stephens在1988年提出的Harris角点检测算子。Harris不仅检测水平和垂直方向的灰度差异,而且还检测所有方向的灰度差异,并且对部分仿射变换具有旋转不变性和稳定性。哈里斯是整个街角测试家庭的代言人。[en]The nine-bag elder of corner point is the harris corner detection operator proposed by Chris Harris & Mike Stephens in 1988. Harris not only examines the gray differences in horizontal and vertical directions, but also examines the gray differences in all directions, and has rotation invariance and stability to partial affine transformations. Harris is the face of the entire corner testing family.

角点家族的伟大保护者是J.shi和C.Tomasi在1994年提出的Shio-Tomasi角点检测算子,它是对Harris角点检测算子的改进,并且有一个直接叫出Harris算子的名字–好特征跟踪,在OpenCV中的实现函数是Good FeauresToTrack。它通过检测自相关矩阵M的两个特征值中较小的一个来确定角点,在大多数情况下,它具有比Harris更好的检测效果。[en]The great protector of the corner family is the Shi-Tomasi corner detection operator proposed by J.shi and C.Tomasi in 1994, it is an improvement of the Harris corner detection operator, and there is a direct “shouting” the name of the Harris operator-“Good Feaures to Track”, and the implementation function in opencv is goodfeaturesToTrack. It determines the corner point by examining the smaller of the two eigenvalues of the autocorrelation matrix M. in most cases, it has a better detection effect than Harris.

角落家族的主要大堂是E.Rosten和T.Drummond在2006年提出的FAST(来自加速分段测试的特征)操作符。通过检测像素点与周围区域16个像素点的差异来确定特征点(角点),并通过分割测试算法大大提高了检测效率。它信奉的真理是“武林天下,唯有快而不破”,在快车道上砥砺前行,基本能满足实时检测系统的要求,在计算机视觉领域赢得了足够的重视。[en]The main lobby of the corner family is the FAST (Feature from Accelerated Segment Test) operator proposed by E.Rosten and T.Drummond in 2006. It determines the feature points (corners) by examining the differences between the pixels and the 16 pixels in the surrounding field, and greatly improves the detection efficiency through the segmentation testing algorithm. It believes in the truth of “martial arts in the world, only fast and unbroken”, forges ahead on the fast road, can basically meet the requirements of the real-time detection system, and has earned enough attention in the field of computer vision.

角点家族这种群雄逐鹿的局面一直持续了很多年,大家你追我赶,在群主 Moravec 的带领下家族基业日渐殷实。直到20年后 1999年的某天,有一个叫Sift的后生出现了。

1999年,大不列颠哥伦比亚大学的David G.Lowe 教授在现有基于不变量技术的特征检测方法基础上,提出了一种基于尺度空间的,对图形缩放,旋转,甚至仿射变换保持不变性的图像局部特征描述算子——sift(尺度不变特征变换),全称是Scale invariant Feature Transform,并且在2004年,又对Sift算法做了更为系统的完善。

2,角点的定义

角点可以被认为是图像亮度急剧变化的点,或者是图像边缘曲线上的最大曲率。[en]The corner can be thought of as the point where the brightness of the image changes sharply or the maximum curvature on the edge curve of the image.

角是极点,在这里属性在某个方面特别突出。[en]The corner is the extreme point, where the attribute is particularly prominent in a certain aspect.

拐角可以是两条直线的交点,也可以是两个主方向不同的相邻物体上的点。[en]A corner can be the intersection of two lines, or it can be a point on two adjacent things with different main directions.

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

从图中可以看出:[en]As can be seen from the picture:

角点:最直观的印象就是在水平,垂直两个方向上变换均较大的点,例如上面E和F是角点,可以迅速定位到。

边缘:仅在水平或者垂直方向有较大的变化,例如上面C和D是边界,可以大致找到位置。

平坦地区:在水平,垂直方向的变换量均较小,例如上面A和B是平坦地区,在图像中有很多存在

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

让我们来看看角落的类型:[en]Let’s take a look at the types of corners:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

3,角点检测

角点检测是一种获取图像特征的方法,广泛应用于跑步检测、图像匹配、视觉跟踪、三维建模和目标识别等领域。也称为特征点检测。[en]Corner detection is a method to obtain image features, which is widely used in the fields of running detection, image matching, visual tracking, 3D modeling and target recognition. Also known as feature point detection.

角点检测算法可以分为三类:[en]Corner detection algorithms can be classified into three categories:

  • 基于灰度图像的角点检测[en]* Corner detection based on grayscale image
  • 基于二值图像的角点检测[en]* Corner detection based on binary image
  • 基于轮廓曲线的角点检测[en]* Corner detection based on contour curve

其中,基于灰度图像的角点检测方法可以分为基于梯度、基于模板和基于模板梯度三种方法。其中,基于模板的方法主要考虑像素点的灰度变化,即图像亮度的变化,将与邻接点有足够对比度的点定义为角点。[en]Among them, corner detection based on grayscale image can be divided into three kinds of methods: gradient-based, template-based and template-gradient-based. Among them, the template-based method mainly considers the gray change of the pixel point, that is, the change of image brightness, and defines the point with sufficient contrast with the adjacent point as the corner point.

基于图像灰度的角点检测方法通过计算点的曲率和梯度来检测角点。常用的基于模板的角点检测算法有:[en]The method based on image grayscale detects corners by calculating the curvature and gradient of points. Commonly used corner detection algorithms based on templates are:

  • Kitchen-Rosenfeld 角点检测
  • Moravec算子
  • Forstner算子
  • Harris角点检测
  • KLT角点检测
  • SUSAN角点检测

4,特征不变性

在特征点检测中,常提出恒定尺度、恒定旋转、抗噪声等指标,作为判断特征点是否稳定的指标。那么它们的特点是什么呢?什么是局部不变特征?让我们一个接一个地学习。[en]In feature point detection, constant scale, constant rotation and anti-noise are often proposed, which are the indicators to judge whether the feature points are stable or not. So what are the characteristics? What is the local invariant feature? Let’s learn one by one.

什么是特征?

每一个物体,我们总是可以用一些词或部分来描述它,比如脸部的特征:两只眼睛,一只鼻子和一张嘴。对于图像,我们需要计算机来理解图像,而要描述图像,我们需要计算机来获取图像的特征。对图像更全面的描述是二维矩阵,矩阵中的每个值代表图像的亮度。有时,我们需要使计算机更加简化,以描述一幅图像,并捕捉一些具有一些良好性质的显著特征,如局部不变性。局部不变性一般包括两个方面:尺度不变性和旋转不变性。[en]Every object, we can always use some words or parts to describe it, such as the characteristics of the face: two eyes, a nose and a mouth. For the image, we need the computer to understand the image, and to describe the image, we need the computer to obtain the characteristics of the image. A more comprehensive description of the image is a two-dimensional matrix, and each value in the matrix represents the brightness of the image. Sometimes we need to make the computer more simplified to describe an image and capture some salient features that have some good properties, such as local invariance. Local invariance generally includes two aspects: scale invariance and rotation invariance.

尺度不变性:人类在识别一个物体时,不管这个物体或远或近,都能对它进行正确的辨识,这就是所谓的尺度不变性。尺度空间理论经常与生物视觉关联,有人也称图像局部不变性特征为基于生物视觉的不变性方法。

旋转不变性:当这个物体发生旋转时,我们照样可以正确地辨认它,这就算所谓的旋转不变性。

局部不变特征

全局特征:从整个图像中抽取的特征。较多的运用在图像检索领域,如图像颜色直方图。

局部特征:从图像的局部区域中抽取的特征(这个局部区域往往是图像中的一个像素及它周围的邻域)

一个好的地方特色应该具有以下特点:[en]A good local feature should have the following characteristics:

  1. 可重复性:同一个物体在不同时间,不同角度拍到图像中,检测到的特征对应的越多越好。
  2. 独特性:特征在该物体上表现为独特性,能与场景下其他物体区分。
  3. 局部性:特征往往是物体某个局部的特点,这样才可以避免遮挡时不能匹配的问题。
  4. 数量性:检测到的特征数目一定要多,密集度最好能在一定程度上反映图像的内容。
  5. 准确性:得到的特征应该能被精确定位,能够精确到像素。
  6. 高效性:特征检测算法运算要快。

那么什么是好的角点检测算法

  • 1,检测出图像中”真实”的角点
  • 2,准确的定位性能
  • 3,很高的重复检测率
  • 4,噪声的鲁棒性
  • 5,较高的计算效率

让我们分别学习Harris角点检测和SIFT算法。[en]Let’s learn Harris corner detection and SIFT algorithm respectively.

1,Harris 角点检测

1.1,Harris角点算法概述

Harris角点是特征点检测的基础,提出了应用邻域像素点灰度差值概念,从而进行判断是否为角点,边缘,平滑区域。Harris角点检测原理是利用移动的窗口在图像中计算灰度变化值,其中关键流程包括转化为灰度图像,计算差分图像,高斯平滑,计算局部极值,确认角点。

1.1.1 Harris角点算法思想

角点原理来源于人对角点的感性判断,即图像在各个方向灰度有明显变化。算法的核心是利用局部窗口在图像上进行移动判断灰度发生较大的变化,所以此窗口用于计算图像的灰度变化为:[-1, 0, 1;-1, 0, 1;-1, 0, 1] [-1, -1, -1; 0, 0, 0;1, 1, 1]。人各个方向上移动这个特征的小窗口,如下图3中窗口内区域的灰度发生了较大的变化,那么就认为在窗口内遇到了角点。如下图1中,窗口内图像的灰度没有发生变化,那么窗口内就不存在角点;如果窗口在某一个方向移动时,窗口内图像的灰度发生了较大的变化,而在另一些方向上没有发生变化,那么,窗口内的图像可能就是一条直线的线段。

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

1.2,Harris角点检测数学推导

根据该算法的思想,Harris算法利用图像在窗口中灰度的自相关性,设计一个窗口在图像中移动,构建数学模型,计算移动窗口的灰度差(即窗口移动前后图像所在区域的自相关系数)。[en]According to the idea of the algorithm, the Harris algorithm uses the autocorrelation of the grayscale of the image in the window, designs a window to move in the image, constructs a mathematical model, and calculates the gray difference of the moving window (that is, the autocorrelation coefficient of the image in the area where the window is located before and after moving).

Harris算法是利用的窗口内图像灰度的自相关性进行的,设定一个窗口,并在图像中移动,计算移动前与移动后窗口所在区域图像的自相关系数。

自相关函数计算如下,(x,y)是窗口的中心位置,w(u,v)是权重(通常取高斯函数),L表示窗口,以及(u,v)表示窗口中的图像位置。[en]The autocorrelation function is calculated as follows, (x, y) is the center position of the window, w (u, v) is the weight (usually take the Gaussian function), L represents the window, and (u, v) represents the image position in the window.

对于图像i(x,y),在点(x,y)处平移(Δx,Δy)后的自相似性:[en]For image I (x, y), the self-similarity after translating (Δ x, Δ y) at the point (x, y):

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

为了减少计算量,采用基于泰勒展开的简化公式来逼近平移后的图像l(x,y)(Δx,Δy)。[en]In order to reduce the amount of calculation, a simplified formula based on Taylor expansion is used to approximate the image l (x, y) after translation (Δ x, Δ y).

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

式中,ix和iy是i(x,y)的偏导数。[en]Where Ix and Iy are partial derivatives of I (x, y).

将近似值替换为自相关函数,包括:[en]Replace the approximate value into the autocorrelation function, including:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

方项以矩阵形式显示和书写,包括:[en]The square term is displayed and written in matrix form, including:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

返回到自相关表达式:[en]Go back to the autocorrelation expression:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

大致可以得到以下表达式:[en]Approximately, the following expressions can be obtained:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

其中M是2到2的矩阵(M矩阵是偏导数矩阵),它可以从图像的导数获得:[en]Where M is a matrix of 2 to 2 (M matrix is a partial derivative matrix), which can be obtained from the derivative of the image:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

可以实现以下简化:[en]Simplification can be obtained:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

经过上述数学推导,得到了自相关函数的表达式。由此可见,这也是椭圆(非标准椭圆)的矩阵表示形式,因此其系数矩阵M的特征值与椭圆的半轴长度有关。[en]After the above mathematical derivation, the expression of the autocorrelation function has been obtained. It can be seen that this is also the matrix expression form of an ellipse (non-standard ellipse), so the eigenvalue of its coefficient matrix M is related to the half-axis length of the ellipse.

1.2.1 椭圆的矩阵方差表示

二次函数本质上是椭圆函数,椭圆如下:[en]The quadratic function is essentially an elliptic function, the ellipse is as follows:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

椭圆型方程如下:[en]The elliptic equation is as follows:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

如果上述差异以矩阵的形式写成如下:[en]If the above variance is written in the form of a matrix as follows:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

1.2.2 椭圆半轴与系数矩阵的关系

N的矩阵的特征值是可以求解的。通过求解上述系数矩阵(包括a,b),我们可以得到本征值与椭圆半轴(a,b)之间的关系。让我们来看看椭圆半轴和本征值之间的关系。如果求出上述方程的本征值,就可以得到该本征值与椭圆半轴之间的关系。[en]The eigenvalue of a matrix of n can be solved. By solving the above coefficient matrix (including a, b), we can get the relationship between the eigenvalue and the elliptic half-axis (a, b). Let’s take a look at the relationship between the elliptical half-axis and the eigenvalue. If we find the eigenvalue of the above equation, we can get the relationship between the eigenvalue and the elliptic half-axis.

用M表示参数:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

所以椭圆型方程是:[en]So the elliptic equation is:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

如果本征值为λ1和λ2,则本征值与半轴之间的关系为:[en]If the eigenvalues are λ 1 and λ 2, the relationship between the eigenvalues and the half axis is:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

我们可以在下面的椭圆中看到它:[en]We can see it in the ellipse below:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

结论是:本征值大,半轴短。[en]The conclusion is: * the eigenvalue is large, the half axis is short *.

边界:一个本征值大,一个本征值小,λ1>>λ2或λ2>>λ1。自相关函数一个方向大,另一个方向小。[en]Boundary: one eigenvalue is large and the other is small, λ 1 > > λ 2 or λ 2 > > λ 1. The value of autocorrelation function is large in one direction and small in other directions.

平面:两个本征值都很小且近似相等;自相关函数值在所有方向上都很小[en]Plane: both eigenvalues are small and approximately equal; autocorrelation function values are small in all directions

角点:两个本征值都很大且大致相等,并且自相关函数在所有方向上都会增加。[en]Corners: both eigenvalues are large and approximately equal, and the autocorrelation function increases in all directions.

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

经过上述数学推导,得到了自相关函数的表达式。由此可见,这也是椭圆(非标准椭圆)的矩阵表达式,因此其系数矩阵M的特征值与椭圆的半轴长度有关,这与上述初步知识中的结论相同。[en]After the above mathematical derivation, the expression of the autocorrelation function has been obtained. It can be seen that this is also the matrix expression of an ellipse (non-standard ellipse), so the eigenvalue of its coefficient matrix M is related to the half-axis length of the ellipse, which is the same as the conclusion in the above preliminary knowledge.

假设M的特征值为λ1λ2,则将其分为以下三种情况:[en]Assuming that the eigenvalue of M is λ 1 λ 2, it is divided into the following three cases:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

通过上述情况,在计算特征值后,我们可以判断它是否是角点。[en]Through the above situation, after calculating the eigenvalue, we can tell whether it is a corner point or not.

1.2.3 角点响应R值

M为梯度的协方差矩阵,在实际应用中为了能够应用更好的编程,定义了角点响应函数R,通过判断R大小来判断像素是否为角点。

R取决于M的特征值,对于角点 |R| 很大,平坦的区域 |R| 很小,边缘的 R 为负值。

当然,计算量非常大,因为图像中几乎每个点都需要计算特征值。以下是拐角响应函数R的经验公式:[en]Of course, the amount of calculation is very large, because almost every point in the image needs to calculate the eigenvalues. Here is an empirical formula of the corner response function R:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

detM 表示M的行列式,traceM表示M的迹,R表示角点响应值,alpha表示经验常数,一般在0.04~0.06之间取值。

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

判断标准:当R超过设定的阈值时,可视为角点,否则为非角点。[en]Judgment criterion: when R exceeds a set threshold, it can be regarded as a corner, otherwise, it is not.

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

1.3,Harris 角点检测算法流程

步骤1:利用水平,竖直差分算子对图像 I(x, y)的每个像素进行滤波以求得 X 和 Y方向的梯度 Ix和Iy,进而求得M中的四个元素的值。

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

在代码中,如果数组是{-1,0,1,-1,0,1,-1,0,1,1},则在X方向上求解,如果在Y方向上是{-1,-1,-1,0,1,1,1,1},则IX和IY的解结束。[en]In the code, if array is {- 1, 0, 1,-1, 0, 1,-1, 0, 1, 1}, it is solved in X direction, and if it is {- 1,-1,-1, 0, 0, 1, 1, 1} in Y direction, the solution of Ix and Iy ends.

求解ix2 iy2 ixy相对简单,可以乘以像素。[en]It is relatively simple to solve the IX2 IY2 IXY, which can be multiplied by pixels.

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

对M的四个元素进行高斯平滑滤波,为的是消除一些不必要的孤立点和凸起,得到新的矩阵M。求M的话,我们使用高斯核对IX2 IY2 IXY进行加权,计算矩阵 M 的元素,A,B,C,然后得到M矩阵。

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

步骤2:接下来使用M计算对应每个像素的角点响应函数R

其中,拐角响应函数R为:[en]Where the corner response function R is:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

改进的拐角响应函数R为:[en]The improved corner response function R is:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

没有随机给定的参数k,该值应该比第一个值更令人满意。[en]There is no randomly given parameter k, and the value should be more satisfactory than the first one.

步骤3:局部最大值抑制,同时选取其最大值

步骤4:在矩阵R中,同时满足 R(i, j)大于一定阈值 threshold 和 R(i, j) 是某邻域内的局部极大值,则被认为是角点。当角点量小于阈值值,则不是候选角点。

1.4,Harris角点性质

1.4.1 阈值决定检测点数量

增加角点响应值R,会降低角点检测的灵性,减少检测到的角点个数;减小Alpha值,会增加角点响应值R,提高角点检测的灵敏度,增加检测到的角点个数。[en]Increasing the value of alpha will reduce the corner response value R, reduce the spirituality of corner detection, reduce the number of detected corners; reduce the alpha value, will increase the corner response value R, increase the sensitivity of corner detection, increase the number of detected corners.

1.4.2 Harris角点检测算子对亮度和对比度的变化不敏感

这是因为在Harris角点检测中,使用了微分算子来对图像进行微分,但微分运算对图像密度的增加或收缩以及亮度的增加或减少不敏感。换言之,亮度和对比度的仿射变换不会改变哈里斯响应极值点的位置,但角点检测的数量可能会受到阈值选择的影响。[en]This is because in the Harris corner detection, the differential operator is used to differentiate the image, but the differential operation is not sensitive to the increase or contraction of image density and the increase or decrease of brightness. In other words, the affine transformation of brightness and contrast does not change the position of the extreme point of the Harris response, but the number of corner detection may be affected by the choice of threshold.

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

1.4.3 Harris角点检测算子具有旋转不变性

Harris角点检测算子使用的是角点附加的区域灰度二阶矩矩阵。而二阶矩矩阵可以表示成一个椭圆,椭圆的长短轴正是二阶矩矩阵特征值平方根的倒数。当特征椭圆转动时,特征值并不发生变换,所以判断角点响应值也不发生变换,由此说明 Harris角点检测算子具有旋转不变性。

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

1.4.4 Harris角点检测算子不具有尺度不变性

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

如下图所示,当缩小右侧图像时,在检测窗口大小不变的前提下,窗口中包含的图像内容完全不同。左侧的图像可以被检测为边缘或曲线,而右侧的图像可以被检测为角。[en]As shown in the following figure, when the right image is reduced, the content of the image contained in the window is completely different on the premise that the size of the detection window remains the same. The image on the left may be detected as an edge or curve, while the image on the right may be detected as a corner.

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

1.5,Harris角点检测实战

1.5.1 Harris的opencv源码

首先,我们来看看哈里斯的OpenCV源代码:[en]First, let’s take a look at the opencv source code of Harris:

csharp;gutter:true; def cornerHarris(src, blockSize, ksize, k, dst=None, borderType=None): # real signature unknown; restored from <strong>doc</strong> """ cornerHarris(src, blockSize, ksize, k[, dst[, borderType]]) -> dst . @brief Harris corner detector.</p> <pre><code>. . The function runs the Harris corner detector on the image. Similarly to cornerMinEigenVal and . cornerEigenValsAndVecs , for each pixel \f$(x, y)\f$ it calculates a \f$2\times2\f$ gradient covariance . matrix \f$M^{(x,y)}\f$ over a \f$\texttt{blockSize} \times \texttt{blockSize}\f$ neighborhood. Then, it . computes the following characteristic: . . \f[\texttt{dst} (x,y) = \mathrm{det} M^{(x,y)} - k \cdot \left ( \mathrm{tr} M^{(x,y)} \right )^2\f] . . Corners in the image can be found as the local maxima of this response map. . . @param src Input single-channel 8-bit or floating-point image. . @param dst Image to store the Harris detector responses. It has the type CV_32FC1 and the same . size as src . . @param blockSize Neighborhood size (see the details on #cornerEigenValsAndVecs ). . @param ksize Aperture parameter for the Sobel operator. . @param k Harris detector free parameter. See the formula above. . @param borderType Pixel extrapolation method. See #BorderTypes. </code></pre> <p>""" pass</p> <pre><code> 参数含义:[en]<u>Parameter meaning:</u> * src:数据类型为 float32 的输入图像 * blockSize:角点检测中指定区域的大小 * ksize:Sobel求导中使用的窗口大小 * k:取值参数为 [0.04, 0.06] #### 1.5.2 Harris角点检测opencv实战 以一张图片为例:[en]<u>Take a picture as an example:</u> ;gutter:true;
import cv2
import numpy as np

img = cv2.imread(‘test_1.jpg’)
print(‘imgshape’, img.shape)
# imgshape (800, 1200, 3)
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
# gray = np.float32(gray)
dst = cv2.cornerHarris(gray, 2, 3, 0.04)
print(‘dst.shape’, dst.shape)
# dst.shape (800, 1200)

img[dst>0.01*dst.max()] = [0, 0, 255]
cv2.imshow(‘dst’, img)
cv2.waitKey(0)
cv2.destroyAllWindows()

比 max 的 0.01 大,则表示为角点,我们拿到其角点。

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

棋盘有更多的角,但它是彩色的。如果你想看到角落的真实效果,你可以使用黑白棋盘。[en]The chessboard has more corners, but it is colored. If you want to see the real effect on the corners, you can use a black-and-white chessboard.

如果你看另一张图片,效果如下:[en]If you look at another picture, the effect is as follows:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

2,SIFT特征

2.1 SIFT特征概述

SIFT 的全称是 Scale Invariant Feature Transform,尺度不变特征变换,由加拿大教授David G.Lowe提出的。SIFT特征对旋转,尺度缩放,亮度变化等保持不变性,是一种非常稳定的局部特征。

SIFT提取图像的局部特征,在尺度空间寻找极值点,并提取出其位置,尺度,方向信息。SIFT的应用范围包括物体辨识,机器人地图感知与导航,影像拼接,3D模型建立,手势识别,影像追踪等。

2.1.1 SIFT算法具有的特征

图像的局部特征对旋转、比例缩放和亮度变化保持不变,对视角变化、仿射变换和噪声保持一定的稳定性。[en]The local features of the image remain unchanged for rotation, scale scaling and brightness change, and maintain a certain degree of stability for visual angle change, affine transformation and noise.

  • 1,对旋转,尺度缩放,亮度变化保持不变性,对视角变化,噪声等也存在一定程度的稳定性
  • 2,独特性,信息量丰富,适用于在海量特征数据中进行快速,准确的匹配
  • 3,多量性,即使少数几个物体也可以产生大量的SIFT特征向量
  • 4,可扩展性,可以很方便的与其他形式的特征向量进行联合

SIFT算法的实质是在不同的尺度空间上寻找关键点(特征点),计算关键点的大小,方向,尺度信息,利用这些信息组成关键点对特征点进行描述的问题。SIFT所查找的关键点都是一些十分突出,不会因光照,仿射变换和噪声等因素而变换的”稳定”特征点,如角点,边缘点,暗区的亮点以及亮区的暗点等。匹配的过程就是对比这些特征点的过程,这个流程可以用下图表述:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

2.2 SIFT特征提取和匹配的具体步骤

首先,我们编写了SIFT特征提取和匹配的步骤如下:[en]First of all, we write the steps of SIFT feature extraction and matching, as follows:

  • 1,生成高斯差分金字塔(DOG金字塔),尺度空间构建
  • 2,尺度空间的极值检测(关键点的初步查探)
  • 3,稳定关键点的精确定位(特征点定位)
  • 4,稳定关键点方向信息分配(特征方向赋值)
  • 5,关键点描述(特征点描述)
  • 6,特征点匹配

关于高斯金字塔的具体原理,你可以参考以下博客:[en]For the specific principles of the Gauss Pyramid, you can refer to the following blog:

OpenCV计算机视觉学习(7)——图像金字塔(高斯金字塔,拉普拉斯金字塔,图像缩放resize()函数)

2.2.1 生成高斯差分金字塔(DOG金字塔),尺度空间创建

尺度空间建立在狗金字塔的基础上,而狗金字塔则由高斯金字塔变换而成。有关高斯金字塔的博客,请参阅:[en]The scale space is built on the basis of the DOG pyramid, while the DOG pyramid is transformed by the Gaussian pyramid. For a blog about the Gaussian pyramid, please refer to:

OpenCV计算机视觉学习(7)——图像金字塔(高斯金字塔,拉普拉斯金字塔,图像缩放resize()函数)

在一定范围内,人眼可以分辨物体的大小,但计算机很难具有相同的能力,因此需要让机器对不同尺度上的物体有统一的认识。有必要考虑不同尺度上图像的特征。[en]In a certain range, the human eye can distinguish whether the object is large or small, but it is difficult for the computer to have the same ability, so it is necessary to make the machine have a unified understanding of the object at different scales. it is necessary to consider the characteristics of images on different scales.

尺度空间的获取通常通过高斯滤波来实现:[en]The acquisition of scale space is usually realized by Gaussian filtering:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

其中G是高斯函数,并且高斯函数公式如下:[en]Where G is a Gaussian function, and the Gaussian function formula is as follows:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

尺度空间的获取就是给图像的不同点赋予不同的权重。以5‘5的高斯核为例,我们可以看到不同点的权重与下图不同。[en]The acquisition of scale space is to assign different weights to different points of an image. Taking the Gaussian kernel of 5’5 as an example, we can see that the weights of different points are different from the figure below.

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

当不同Sigma的高斯函数确定图像的平滑度时,Sigma值越大,图像越模糊:[en]When the Gaussian function of different Sigma determines the smoothness of the image, the larger the Sigma value, the more blurred the image:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

创建高斯差金字塔(DOG)的方法如下:[en]The Gaussian difference pyramid (DOG) is created as follows:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

每一组在层数上,DOG金字塔比高斯金字塔少一层。后续Sift特征点的提取都是在DOG金字塔上进行的。

DOG定义公式:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

其主要实现是通过对原始图像进行尺度变换,得到多尺度下图像的尺度空间表示序列,并对这些序列的主轮廓进行图像区域划分,以主轮廓作为特征向量实现边缘。角点检测、不同分辨率下关键点的提取等。[en]The main realization is that through the scale transformation of the original image, the scale space representation sequence of the image under multi-scale is obtained, the image area of the main contour of these sequences is carried out, and the main contour is used as a feature vector to realize the edge. corner detection, extraction of key points in different resolutions, etc.

2.2.2 DOG 空间极值点检测(关键点的初步查探)

搜索尺度空间中的所有图像,并使用高斯微分函数来识别尺度上的潜在兴趣点和选择不变的兴趣点。[en]Search all the images in the scale space, and use the Gaussian differential function to identify the potential points of interest to the scale and the selection of invariant points of interest.

为了找到尺度空间(DOG函数)的极值点,需要将每个像素与其图像域(相同尺度空间)和尺度域(相邻尺度空间)中的所有邻近点进行比较。当它大于(或小于)所有邻接点时,该点为极值点。如下图所示:[en]In order to find the extreme point of the scale space (DOG function), each pixel should be compared with all the adjacent points in its image domain (the same scale space) and its scale domain (adjacent scale space). When it is greater than (or less than) all the adjacent points, the point is the extreme point. As shown in the following figure:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

在二维图像中,将中间检测点与其所在图像的邻域中的8个像素进行比较,并将其与图像上层和下层(在同一组尺度空间中)的场中的18个像素进行比较。总共比较了26个像素。这样,无论是在尺度空间还是在二维图像空间,都能保证检测到的关键点是局部极值点。[en]In a two-dimensional image, the middle detection point is compared with 8 pixels in the neighborhood of the image in which it is located, and 18 pixels in the field of the upper and lower layers of the image (in the same group of scale space). A total of 26 pixels were compared. In this way, it can ensure that the detected key points are local extreme points in both scale space and two-dimensional image space.

2.2.3 稳定关键点的精确定位

DOG 值对噪声和边缘比较敏感,所以在第2步的尺度空间中检测到的局部极值点还要经过进一步的筛选,去除不稳定和错误检测出的极值点,另一点就是在构建高斯金字塔过程中采用了下采样的图像,在下采样图像中提取的极值点对应在原始图像中的确切位置,也是要在本步骤中解决的问题。

在每个候选位置,通过对精细模型的拟合来确定位置尺度,并根据其稳定性选择关键点。这些候选关键点是狗空间中的局部极值点,这些极值点是离散点。一种精确定位极点的方法是在尺度空间中对DOG函数的曲线进行拟合并计算其极点,从而实现关键点的精确定位。[en]In each candidate position, the location scale is determined by fitting the fine model, and the key points are selected according to their stability. These candidate key points are the local extreme points in DOG space, and these extreme points are discrete points. One method to accurately locate the extreme points is to fit the curve of the DOG function in the scale space and calculate its extreme points, so as to achieve the accurate location of the key points.

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

您可以使用泰勒级数展开:[en]You can use Taylor series to expand:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

消除边界响应

Hessian矩阵:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

令 α = λmax 为最大的特征值,β = λmin最小的特征值

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

Lower 在论文中给出 γ = 10,也就是说对于主曲率比值大于10的特征点将被删除。

2.2.4 稳定关键点方向信息分配(特征点的主方向)

在不同尺度空间中提取稳定的极值点,保证了关键点的尺度不变性。将方向信息分配给关键点的问题是使关键点不变形为图像的角度和旋转。通过求每个极值点的梯度来实现方向分配。[en]The stable extreme points are extracted in different scale spaces, which ensures the scale invariance of the key points. The problem of assigning direction information to key points is to make the key points undeformed to the angle and rotation of the image. The direction assignment is realized by finding the gradient of each extreme point.

对于任意关键点L(x,y)、梯度幅度(梯度模)m(x,y)和梯度方向theta(x,y):[en]For any key point L (x, y), the gradient amplitude (modulus of the gradient) m (x, y) and the gradient direction theta (x, y):

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

每个特征点可以获取三条信息(x,y,σ,theta),即位置、比例和方向。具有多个方向的关键点可以复制到多个副本中,然后将方向值分别分配给复制的特征点,一个特征点产生多个比例相同但方向不同的坐标。[en]Each feature point can get three pieces of information (x, y, σ, theta), that is, position, scale and direction. Key points with multiple directions can be copied into multiple copies, and then the direction values are assigned to the copied feature points respectively, and a feature point produces multiple coordinates with equal scales but different directions.

分类到关键点的方向不直接是关键点的梯度方向,而是以梯度方向直方图的方式给出。具体方法是以关键点为中心计算场内所有点的梯度方向,当然梯度方向必须在0°360度的范围内,而这些梯度方向必须归一化到36个方向,每个方向代表10度的范围。然后累加每个方向上的关键点个数,生成梯度方向直方图。[en]The direction classified to the key point is not directly the gradient direction of the key point, but is given in the way of a gradient direction histogram. The specific method is to calculate the gradient directions of all points in the field with the key points as the center, of course, the gradient direction must be in the range of 0 °360 degrees, and these gradient directions must be normalized to 36 directions, each direction represents the range of 10 degrees. Then accumulate the number of key points in each direction to generate the gradient direction histogram.

在完成关键点的梯度计算后,利用直方图计算邻域内像素的梯度和方向。[en]After the gradient calculation of the key points is completed, the histogram is used to calculate the gradient and direction of pixels in the neighborhood.

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

将梯度直方图中纵坐标最大的项所代表的方向分配给当前关键点作为主方向,如果存在相当于梯度直方图中主峰能量的80%的峰值,则将该方向视为关键点的辅助方向。辅助方向的设计可以增强匹配的稳健性。洛威指出,约15%的关键点有次级方向,而对稳定匹配起关键作用的恰恰是15%的关键点。[en]The direction represented by the item with the largest ordinate in the gradient histogram is assigned to the current key point as the main direction, and if there is a peak equivalent to 80% of the energy of the main peak in the gradient histogram, this direction is regarded as the auxiliary direction of the key point. The design of auxiliary direction can enhance the robustness of matching. Lowe pointed out that about 15% of the key points have secondary directions, and it is precisely 15% of the key points that play a key role in stable matching.

2.2.5 生成关键点特征描述

关键点的描述是后续实现匹配的关键步骤,描述实际上是用数学的方式定义关键点的过程。描述符不仅包含关键点,而且还包含对其有贡献的关键点周围的邻接点。[en]The description of key points is a key step in the subsequent implementation of matching, and description is actually a process of defining key points in a mathematical way. The descriptor contains not only the key points, but also the neighborhood points around the key points that contribute to it.

为了保证特征向量的旋转不变性,需要以特征点为中心,将坐标轴旋转到近场中特征点的主方向。[en]In order to ensure the rotation invariance of the feature vector, it is necessary to take the feature point as the center and rotate the coordinate axis into the main direction of the feature point in the nearby field.

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

旋转后,主方向以8到8的窗口为中心,计算每个像素的梯度幅度和方向,箭头方向代表梯度方向,长度代表梯度幅度,然后用高斯窗口进行加权。最后,在每个4×4块上绘制8个方向的梯度直方图,并计算每个梯度方向的累积值以形成种子点,即每个特征由4个种子点组成。每个种子点具有八个方向的矢量信息。[en]After rotation, the main direction is centered on a window of 8 to 8, and the gradient amplitude and direction of each pixel are calculated, the arrow direction represents the gradient direction, and the length represents the gradient amplitude, and then it is weighted by the Gaussian window. finally, a gradient histogram in eight directions is drawn on each 4×4 block, and the cumulative value of each gradient direction is calculated to form a seed point, that is, each feature is composed of four seed points. Each seed point has vector information in eight directions.

如下图所示,对于2-2个块,每个块中所有像素的梯度用高斯加权,每个块最终取8个方向,即可以生成2-2-8维向量,作为中心关键点的数学描述。[en]As shown in the following figure, for 2-2 blocks, the gradients of all pixels in each block are weighted by Gauss, and each block finally takes 8 directions, that is, we can generate 2-2-8-dimensional vectors, which are used as the mathematical description of the central key points.

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

在本文(David G.Lowe的实验结果)中,建议每个关键点用总共16个种子点来描述,这样一个关键点就可以产生一个128D的SIFT特征向量。也就是说,用128维矢量的描述子来刻画关键点,综合效果最好。[en]In this paper (the experimental results of David G.Lowed), it is suggested that each key point should be described by a total of 16 seed points, so that a key point can produce a 128D SIFT feature vector. That is, the descriptor of 128-dimensional vector is used to characterize the key points, and the comprehensive effect is the best.

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

2.2.6 特征点匹配

通过计算两组特征点128维关键点的欧几里得距离来实现特征点的匹配。欧氏距离越小,相似性越高。当欧几里德距离小于设定的阈值时,可以判断为匹配成功。[en]The matching of feature points is realized by calculating the Euclidean distance of 128-dimensional key points of two groups of feature points. The smaller the Euclidean distance is, the higher the similarity is. When the Euclidean distance is less than the set threshold, it can be judged as a successful match.

2.3,Python实现SIFT特征检测

2.3.1 更新opencv的安装包

3.4.3 以上 就进入了专利保护的阶段,一些函数已经用不了,他们申请专利了,我们需要降版本。

因此,如果我们的版本高于3.4.3,则需要更低的版本。目前,可以使用SIFT的最稳定的OpenCV版本是3.4.1.15。[en]So if our version is greater than 3.4.3, we need a lower version. Currently, the most stable opencv version that can use SIFT is 3.4.1.15.

csharp;gutter:true; pip install opencv-python==3.4.1.15</p> <p>pip install opencv-contrib-python==3.4.1.15</p> <pre><code> 3.4.1.15 使用SIFT函数是没有任何问题的。 安装完成后,接下来我们将进行SIFT特征检测。[en]<u>After installation, we will implement SIFT feature detection next.</u> #### 2.3.2 SIFT代码实现 在得到关键点后,我们需要计算特征,Kp不能直接打印,因为它是列表格式,我们需要转换成np.array()格式。[en]<u>After getting the key points, we need to calculate the features, kp can not print directly, because it is list format, we need to convert to np.array () format.</u> 得到128维的所有向量点和6827个特征点。[en]<u>Get all the vector points for the 128th dimension and 6827 feature points.</u> 代码如下[en]<u>The code is as follows</u> ;gutter:true;
import cv2
import numpy as np

img = cv2.imread(‘test_1.jpg’)
print(‘imgshape’, img.shape)
# imgshape (800, 1200, 3)
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
# gray = np.float32(gray)

# 得到特征点
sift = cv2.xfeatures2d.SIFT_create()
kp = sift.detect(gray, None)
# kp 是封装好的东西,我们看不见,只能展示

img = cv2.drawKeypoints(gray, kp, img)

img = cv2.resize(img, None, fx=0.5, fy=0.5)
cv2.imshow(‘dst’, img)
cv2.waitKey(0)
cv2.destroyAllWindows()

# 计算特征
kp, des = sift.compute(gray, kp)
print(np.array(kp).shape) # (6827,)
print(des.shape) # (6827, 128)
print(des[0])

”’
[ 0. 0. 0. 0. 0. 0. 0. 0. 21. 8. 0. 0. 0. 0.

0. 0. 157. 31. 3. 1. 0. 0. 2. 63. 75. 7. 20. 35.

31. 74. 23. 66. 0. 0. 1. 3. 4. 1. 0. 0. 76. 15.

13. 27. 8. 1. 0. 2. 157. 112. 50. 31. 2. 0. 0. 9.

49. 42. 157. 157. 12. 4. 1. 5. 1. 13. 7. 12. 41. 5.

0. 0. 104. 8. 5. 19. 53. 5. 1. 21. 157. 55. 35. 90.

22. 0. 0. 18. 3. 6. 68. 157. 52. 0. 0. 0. 7. 34.

10. 10. 11. 0. 2. 6. 44. 9. 4. 7. 19. 5. 14. 26.

37. 28. 32. 92. 16. 2. 3. 4. 0. 0. 6. 92. 23. 0.

0. 0.]
”’

具体数字如下:[en]The figure is as follows:

OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

2.3.3 opencv中SIFT 函数中keypoint 数据结构分析

在分析了OpenCV中关于KeyPoint数据结构的信息后,我们首先找到了OpenCV的官方文档:[en]After analyzing the information about the keypoint data structure in opencv, we first find the official document of opencv:

http://docs.opencv.org/java/org/opencv/features2d/KeyPoint.html

在KP的数据结果中,可以看到以下几个关键点:[en]You can see the following key points in the data results of KP:

  • angle:角度,表示关键点的方向,通过 Lowe 大神的论文可以知道,为了保证方向不变形,SIFT算法通过对关键点周围领域进行梯度运算,求得该点方向,-1为初始值。
  • class_id:当要对图像进行分类时,我们可以用 class_id 对每个特征点进行区分,未设定时为 -1,需要靠自己设定。
  • octave:代表是从金字塔哪一层提取得到的数据
  • pt:关键点点的坐标
  • response:响应程度,代表该点强壮大小
  • size:该点直径大小

注意:Keypoint只是保存了opencv的sift库检测到的特征点的一些基本信息,也就是上面所说的这些,但sift所提取出来的特征向量其实不在这里面。特征向量是通过SiftDescriptorExtractor 提取,结果放在一个 Mat 的数据结构中。这个数据结构才真正保存了该特征点所对应的特征向量。

参考地址:https://blog.csdn.net/yangleo1987/article/details/53261637

https://blog.csdn.net/Sakura55/article/details/81506151

https://blog.csdn.net/dcrmg/article/details/52577555

https://www.cnblogs.com/cj695/p/4041399.html

https://www.cnblogs.com/cj695/p/4045443.html

https://wenku.baidu.com/view/b0a2788acc22bcd126ff0c48.html

https://www.cnblogs.com/ronny/p/3886013.html

Original: https://www.cnblogs.com/wj-1314/p/13364875.html
Author: 战争热诚
Title: OpenCV计算机视觉学习-图像特征点检测(Harris角点检测,sift算法)

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/5951/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

发表回复

登录后才能评论
免费咨询
免费咨询
扫码关注
扫码关注
联系站长

站长Johngo!

大数据和算法重度研究者!

持续产出大数据、算法、LeetCode干货,以及业界好资源!

2022012703491714

微信来撩,免费咨询:xiaozhu_tec

分享本页
返回顶部