c语言prim函数,prim算法具体实现

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

OpenCV+Python特征提取算法与图像描述符之SIFT / SURF / ORB

算法效果比较博文

用于表示和量化图像的数字列表，简单理解成将图片转化为一个数字列表表示。特征向量中用来描述图片的各种属性的向量称为特征矢量。

参考

是一种算法和方法，输入1个图像，返回多个特征向量（主要用来处理图像的局部，往往会把多个特征向量组成一个一维的向量）。主要用于图像匹配（视觉检测），匹配图像中的物品。

SIFT论文

原理

opencv官网解释

实质是在不同的尺度空间上查找关键点(特征点)，并计算出关键点的方向。SIFT所查找到的关键点是一些十分突出，不会因光照，仿射变换和噪音等因素而变化的点，如角点、边缘点、暗区的亮点及亮区的暗点等。

尺度不变特征转换(Scale-invariant feature transform或SIFT)是一种电脑视觉的算法用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量。

其应用范围包含物体辨识、机器人地图感知与导航、影像缝合、3D模型建立、手势辨识、影像追踪和动作比对。

对现实中物体的描述一定要在一个十分重要的前提下进行，这个前提就是对自然界建模时的尺度。当用一个机器视觉系统分析未知场景时，计算机没有办法预先知道图像中物体的尺度，因此我们需要同时考虑图像在多尺度下的描述，获知感兴趣物体的最佳尺度。图像的尺度空间表达指的是图像的所有尺度下的描述。

KeyPoint数据结构解析

SURF论文

原理

opencv官网解释

SURF是SIFT的加速版，它善于处理具有模糊和旋转的图像，但是不善于处理视角变化和光照变化。在SIFT中使用DoG对LoG进行近似，而在SURF中使用盒子滤波器对LoG进行近似，这样就可以使用积分图像了（计算图像中某个窗口内所有像素和时，计算量的大小与窗口大小无关）。总之，SURF最大的特点在于采用了Haar特征以及积分图像的概念，大大加快了程序的运行效率。

因为专利原因，OpenCV3.3开始不再免费开放SIFT\SURF，需要免费的请使用ORB算法

ORB算法综合了FAST角点检测算法和BRIEFF描述符。

算法原理

opencv官方文档

FAST只是一种特征点检测算法，并不涉及特征点的特征描述。

论文

opencv官方文档

中文版

Brief是Binary Robust Independent Elementary Features的缩写。这个特征描述子是由EPFL的Calonder在ECCV2010上提出的。主要思路就是在特征点附近随机选取若干点对，将这些点对的灰度值的大小，组合成一个二进制串，并将这个二进制串作为该特征点的特征描述子。文章同样提到，在此之前，需要选取合适的gaussian kernel对图像做平滑处理。

1：不具备旋转不变性。

2：对噪声敏感

3：不具备尺度不变性。

ORB论文

OpenCV官方文档

ORB采用了FAST作为特征点检测算子，特征点的主方向是通过矩（moment）计算而来解决了BRIEF不具备旋转不变性的问题。

ORB还做了这样的改进，不再使用pixel-pair，而是使用9×9的patch-pair，也就是说，对比patch的像素值之和，解决了BRIEF对噪声敏感的问题。

关于计算速度：

ORB是sift的100倍，是surf的10倍。

对图片数据、特征分布的一种统计

对数据空间(bin)进行量化

Kmeans

边缘：尺度问题-不同的标准差捕捉到不同尺度的边缘

斑点 Blob：二阶高斯导数滤波LoG

关键点(keypoint)：不同视角图片之间的映射，图片配准、拼接、运动跟踪、物体识别、机器人导航、3D重建

SIFT\SURF

OpenCV-Python之——图像SIFT特征提取

在一定的范围内，无论物体是大还是小，人眼都可以分辨出来。然而计算机要有相同的能力却不是那么的容易，在未知的场景中，计算机视觉并不能提供物体的尺度大小，其中的一种方法是把物体不同尺度下的图像都提供给机器，让机器能够对物体在不同的尺度下有一个统一的认知。在建立统一认知的过程中，要考虑的就是在图像在不同的尺度下都存在的特征点。

在早期图像的多尺度通常使用图像金字塔表示形式。图像金字塔是同一图像在不同的分辨率下得到的一组结果其生成过程一般包括两个步骤：

多分辨率的图像金字塔虽然生成简单，但其本质是降采样，图像的局部特征则难以保持，也就是无法保持特征的尺度不变性。

我们还可以通过图像的模糊程度来模拟人在距离物体由远到近时物体在视网膜上成像过程，距离物体越近其尺寸越大图像也越模糊，这就是高斯尺度空间，使用不同的参数模糊图像（分辨率不变），是尺度空间的另一种表现形式。

构建尺度空间的目的是为了检测出在不同的尺度下都存在的特征点，而检测特征点较好的算子是Δ^2G(高斯拉普拉斯，LoG)

使用LoG虽然能较好的检测到图像中的特征点，但是其运算量过大，通常可使用DoG（差分高斯，Difference of Gaussina）来近似计算LoG。

从上式可以知道，将相邻的两个高斯空间的图像相减就得到了DoG的响应图像。为了得到DoG图像，先要构建高斯尺度空间，而高斯的尺度空间可以在图像金字塔降采样的基础上加上高斯滤波得到，也就是对图像金字塔的每层图像使用不同的参数σ进行高斯模糊，使每层金字塔有多张高斯模糊过的图像。

如下图，octave间是降采样关系，且octave(i+1)的第一张（从下往上数）图像是由octave(i)中德倒数第三张图像降采样得到。octave内的图像大小一样，只是高斯模糊使用的尺度参数不同。

对于一幅图像，建立其在不同尺度scale下的图像，也称为octave，这是为了scale-invariant，也就是在任何尺度都能有对应的特征点。下图中右侧的DoG就是我们构建的尺度空间。

为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。一个点如果在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点。下图中将叉号点要比较的26个点都标为了绿色。

找到所有特征点后，要去除低对比度和不稳定的边缘效应的点，留下具有代表性的关键点（比如，正方形旋转后变为菱形，如果用边缘做识别，4条边就完全不一样，就会错误；如果用角点识别，则稳定一些）。去除这些点的好处是增强匹配的抗噪能力和稳定性。最后，对离散的点做曲线拟合，得到精确的关键点的位置和尺度信息。

近来不断有人改进，其中最著名的有 SURF（计算量小，运算速度快，提取的特征点几乎与SIFT相同）和 CSIFT（彩色尺度特征不变变换，顾名思义，可以解决基于彩色图像的SIFT问题）。

其中sift.detectAndCompute()函数返回kp，des。

上图dog的shape为(481, 500, 3)，提取的特征向量des的shape为(501, 128)，501个128维的特征点。

该方法可以在特征点处绘制一个小圆圈。