sift算法harris算法

① sift算法是什么

Sift算法是David Lowe于1999年提出的局部特征描述子，并于2004年进行了更深入的发展和完善。Sift特征匹配算法可以处理两幅图像之间发生平移、旋转、仿射变换情况下的匹配问题，具有很强的匹配能力。

这一算法的灵感也十分的直观，人眼观测两张图片是否匹配时会注意到其中的典型区域（特征点部分），如果我们能够实现这一特征点区域提取过程，再对所提取到的区域进行描述就可以实现特征匹配了。

sift算法的应用

SIFT算法目前在军事、工业和民用方面都得到了不同程度的应用，其应用已经渗透了很多领域，典型的应用如下：物体识别；机器人定位与导航；图像拼接；三维建模；手势识别；视频跟踪；笔记鉴定；指纹与人脸识别；犯罪现场特征提取。

② 图像角点特征之Harris、SIFT、SURF、ORB

角点检测(Corner Detection)是计算机视觉系统中用来获得图像特征的一种方法，广泛应用于运动检测、图像匹配、视频跟踪、三维建模和目标识别等领域中。也称为特征点检测。 角点通常被定义为两条边的交点，更严格的说，角点的局部邻域应该具有两个不同区域的不同方向的边界。而实际应用中，大多数所谓的角点检测方法检测的是拥有特定特征的图像点，而不仅仅是“角点”。这些特征点在图像中有具体的坐标，并具有某些数学特征，如局部最大或最小灰度、某些梯度特征等。

这些角点通常在图像中是稳定存在的。角点的微小偏移就能反映出图像帧的相对运动。

Harris角点检测算法就是对角点响应函数R进行阈值处理：R > threshold，即提取R的局部极大值。
特点：具有角度不变性

SIFT克服了Harris的不足，缩放也没影响，具有尺度不变性。
特点：角度不变性，尺度不变性

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

更多

ORB（Oriented FASTand Rotated BRIEF）算法是目前最快速稳定的特征点检测和提取算法，许多图像拼接和目标追踪技术利用ORB特征进行实现。
ORB采用FAST（features from accelerated segment test）算法来检测特征点，采用BRIEF算法来计算一个特征点的描述子。
特点：角度不变性，尺度不变性，计算速度快（ORB是sift的100倍，是surf的10倍）

1、OpenCV版本

③ HartSift: 一种基于GPU的高准确性和实时SIFT

尺度不变特征变换 (SIFT) 是最流行和最强大的特征提取算法之一，因为它对尺度、旋转和光照保持不变。它已被广泛应用于视频跟踪、图像拼接、同时定位和映射（SLAM）、运动结构（SFM）等领域。然而，高计算复杂度限制了其在实时系统中的进一步应用。这些系统必须在准确性和性能之间进行权衡以实现实时特征提取。他们采用其他更快但精度较低的算法，如 SURF 和 PCA-SIFT。为了解决这个问题，本文提出了一种使用 CUDA 的 GPU 加速 SIFT，命名为 HartSift，充分利用单机CPU和GPU的计算资源，实现高精度、实时的特征提取。实验表明，在 NIVDIA GTX TITAN Black GPU 上，HartSift 可以根据图像的大小在 3.14-10.57ms (94.61-318.47fps) 内处理图像。此外，HartSift 分别比 OpenCV-SIFT（CPU 版本）和 SiftGPU（GPU 版本）快 59.34-75.96 倍和 4.01-6.49 倍。同时，HartSift 的性能和 CudaSIFT（迄今为止最快的 GPU 版本）的性能几乎相同，而 HartSift 的准确度远高于 CudaSIFT。

SIFT算法可以提取大量显着特征，这些特征在缩放、旋转、光照和3D视点保持不变，还提供了跨越噪声和仿射失真的稳健匹配。但SIFT的高计算复杂度限制了其在大规模数据和实时系统中的进一步应用。而复杂度较低的算法，如SURF、PCA-SIFT的准确性又不太高。因此，在主流计算平台上实现高精度、实时的SIFT是一个重要而有意义的研究课题。

而SIFT算法具有很好的并行性，可以正确移植到GPU上。因此，在配备GPU的异构计算系统上实现高性能的SIFT具有重要的实用价值。

SIFT 算法包含三个阶段，包括高斯差分（DoG）金字塔的构建、精确的关键点定位和 128 维描述符生成。由于每个阶段都有自己的并行特性，因此必须使用不同的并行粒度和优化来实现高性能。尤其是后两个阶段，负载不平衡不利于GPU优化，会导致性能下降。

本文的主要贡献和创新可以概括如下：

有许多工作尝试在GPU上使用SIFT算法。

然而，为了实现高性能，他们省略了 SIFT 算法的一些重要步骤，例如将输入图像加倍、保持尺度变化的连续性和拟合二次函数以定位准确的关键点信息。作者的实验表明，这些遗漏会导致 SIFT 丢失很多关键点和准确性。

Lowe将输入图像尺寸加倍作为高斯金字塔 的最底层，每个尺度 通过高斯卷积产生：

高斯金字塔确定之后，利用相同Octave的层级相减，得到差分金字塔：

其中 ，在本文中， .

检测尺度空间极值

将DoG金字塔每个像素与相邻像素比较，同层8个，上下层9个，若像素是局部最大值或局部最小值，将其视为关键点候选。

去除无效关键点

去除较低对比度和不稳定边缘响应的候选关键点，通过将3D二次函数拟合到附近数据执行子像素插值，以获取精确的位置、比例和主曲率比。

方向分配

将候选关键点周围的梯度累积到36 bins的直方图中，根据每层的尺度计算搜索半径。每个紧邻像素由一个高斯加权窗口加权，梯度方向累计到36 bins的方向直方图中。峰值为主要梯度方向，同时超过峰值80%的局部峰值bin也被视为关键点方向。

对关键点周围像素计算梯度直方图，搜索半径比上一步骤大得多，同样用一个高斯加权函数用于为每个邻居的梯度值分配权重。

根据梯度方向将最终的梯度值累积到一个 360-bin 的圆形方向直方图。最后，直方图将被归一化、平滑并转换为 128D 描述符。

构建金字塔应该保持顺序，以保证尺度空间变化连续性。Acharya和Bjorkman为加快这一过程，牺牲准确性打破构建顺序。考虑到不能使准确性降低，构建顺序在HartSift中保留。

分离卷积核

对于 大小的卷积核处理 大小的图像需要进行 次运算，如果将2D卷积核拆解为两个1D的卷积核，计算量减少至 . 通过使用共享内存和向量化方法，更容易实现合并全局内存访问并减少一维卷积的冗余访问。

Uber 内核

Uber内核将多个不同任务放到一个物理内核中，在一个内核中并行处理任务，而不需要在内核之间切换。差分金字塔第 层由高斯金字塔第 和第 层决定。将高斯差分金字塔和高斯卷积核封装在单个核中，可以充分挖掘并行性。

线程不需要重复读取高斯金字塔第 层的值，这是由于第 层的值计算完后，结果会放在寄存器内而不是全局内存中。借助Uber内核的优势，我们可以节省 的空间和 的内核运行时间

异构并行

HartSift 采用异构并行方法来加速这一阶段。CPU 和 GPU 将并行协作，构建 DoG 金字塔。

由于GPU处理小图像没有优势，作者将 以下的图像放到CPU处理，大图像放到GPU处理。用户也可以自行设置分离点，确保CPU和GPU负载平衡。

存在两个问题：

负载均衡

Warp是GPU最小并行执行单元，即以锁步方式执行的 32 个线程的集合。若负载不均衡，则warp执行时间取决于最后一个线程完成的时间，warp负载不均衡会导致GPU效率降低。

由于候选关键点分布的随机性，几乎所有经线都包含不同数量的空闲线程。如果这些warp继续处理以下部分，就会出现两个级别的负载不平衡.

在去除无效的候选关键点部分时，线程将进行亚像素插值以获得准确的候选关键点信息，从而去除具有低对比度或不稳定边缘响应的关键点候选。换句话说，一些线程会比其他线程更早返回一次。负载不平衡会变得更加严重。

为了突破性能瓶颈，HartSift 引入了重新平衡工作负载和多粒度并行优化。

重新平衡工作负载

当检测到负载不平衡时，HartSift 将通过启动具有适当粒度的新内核并分派每个具有 32 个活动线程的新经线来重新平衡工作负载。

此外，启动三个内核分别处理这三个部分，不仅可以重新平衡工作量，还可以根据不同部分的并行特性提供多粒度的并行。

多粒度并行

重新平衡工作负载优化保证每个内核中的线程和经线被完全加载，多粒度并行优化保证工作负载将平均分配到线程和经线。此外，不同内核的并行粒度取决于工作负载的特性。

HartSift通过将一个线程映射到一个或多个像素，采用与关键点候选检测部分和无效关键点去除部分并行的线程粒度。然而，线程粒度并行会导致方向分配部分的负载不平衡，因为不同关键点的相邻区域半径不同。线程粒度并行会为单个线程分配过多的工作，这在某些情况下限制了硬件资源的利用率。所以在这部分应用混合粒度并行：扭曲粒度构建直方图，线程粒度找出并将主导方向分配给相应的关键点。

基于扭曲的直方图算法

作者针对每个关键点提出了一种基于扭曲粒度和原子操作的高性能直方图算法，以充分利用局部性。

该阶段关键点的邻域半径远大于前一阶段。需要为每个关键点累积数千个邻居到一个 360-bin 直方图。如果采用前一阶段的基于原子扭曲的直方图算法，会对这一阶段的性能产生不同的影响。

HartSift引入了一种atomic-free的直方图算法，进一步提升了这一阶段的性能。

该算法包含三个步骤：

为了消除线程间的负载不平衡，实现全局合并访问，HartSift 使用一个warp 来处理一个keypoint 的所有邻居。当线程计算出它们的方向 bin 时，它们需要根据bin变量的值将梯度值累加到局部直方图。考虑到有如此多的邻居并且一个经线的一些线程可能具有相同的 bin，算法1引入了一种无原子的多键约简方法来累积每个经线的部分和。这种方法可以利用warp级shuffle和vote指令完全消除原子操作和本地同步。它根据bin对经纱的线程进行分组并指定每组具有最低车道的线程作为队长线程。队长线程将保存他们自己的 bin 的部分总和，并将它们并行地累积到驻留在共享内存中的本地直方图，而不会发生 bank 冲突和同步。在遍历所有邻居后，HartSift 将最终的局部直方图复制到驻留在全局内存中的全局直方图。

本文提出了一种GPU上的并行SIFT，命名为Hart-Sift，它可以在单机内同时使用CPU和GPU来实现高精度和实时的特征提取。HartSift根据每个阶段的不同特点，通过适当采用不同的优化策略来提升性能，例如负载均衡、基于warp的直方图算法和不同尺度样本的atomic-free直方图算法等。在NVIDIA GTX TITAN Black GPU上，HartSift可以在3.14 ~ 10.57ms（94.61 ~ 318.47fps）内提取高精度特征，轻松满足高精度和实时性的苛刻要求。另外，与OpenCV-SIFT和SiftGPU相比，HartSift获得了59.34 ~ 75.96倍和4.01 ~ 6.49倍加速分别。同时，HartSift 和 CudaSIFT 的性能几乎相同，但 HartSift 远比 CudaSIFT 准确。

④ 在图像处理方面什么是SIFT匹配

一、特征点（角点）匹配
图像匹配能够应用的场合非常多，如目标跟踪，检测，识别，图像拼接等，而角点匹配最核心的技术就要属角点匹配了，所谓角点匹配是指寻找两幅图像之间的特征像素点的对应关系，从而确定两幅图像的位置关系。
角点匹配可以分为以下四个步骤：
1、提取检测子：在两张待匹配的图像中寻找那些最容易识别的像素点（角点），比如纹理丰富的物体边缘点等。
2、提取描述子：对于检测出的角点，用一些数学上的特征对其进行描述，如梯度直方图，局部随机二值特征等。检测子和描述子的常用提取方法有：sift，harris，surf，fast，agast，brisk，freak，brisk，brief/orb等。
3、匹配：通过各个角点的描述子来判断它们在两张图像中的对应关系，常用方法如 flann等。
4、消噪：去除错误匹配的外点，保留正确的匹配点。常用方法有KDTREE，BBF，Ransac，GTM等。
二、SIFT匹配方法的提出
为了排除因为图像遮挡和背景混乱而产生的无匹配关系的关键点，SIFT的作者Lowe提出了比较最近邻距离与次近邻距离的SIFT匹配方式：取一幅图像中的一个SIFT关键点，并找出其与另一幅图像中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离得到的比率ratio少于某个阈值T，则接受这一对匹配点。因为对于错误匹配，由于特征空间的高维性，相似的距离可能有大量其他的错误匹配，从而它的ratio值比较高。显然降低这个比例阈值T，SIFT匹配点数目会减少，但更加稳定，反之亦然。
Lowe推荐ratio的阈值为0.8，但作者对大量任意存在尺度、旋转和亮度变化的两幅图片进行匹配，结果表明ratio取值在0. 4~0. 6 之间最佳，小于0. 4的很少有匹配点，大于0. 6的则存在大量错误匹配点，所以建议ratio的取值原则如下:
ratio=0. 4：对于准确度要求高的匹配；
ratio=0. 6：对于匹配点数目要求比较多的匹配；
ratio=0. 5：一般情况下。
三、常见的SIFT匹配代码
1、vlfeat中sift toolbox中的vl_ubcmatch.c使用的是普通的欧氏距离进行匹配（该SIFT代码贡献自Andrea
Vedaldi）。
2、Lowe的C++代码中使用的是欧氏距离，但是在matlab代码中为了加速计算，使用的是向量夹角来近似欧氏距离：先将128维SIFT特征向量归一化为单位向量（每个数除以平方和的平方根），然后点乘来得到向量夹角的余弦值，最后利用反余弦（acos函数）求取向量夹角。实验证明Lowe的办法正确率和耗时都很不错。
同样，也可以采用knnsearch函数求最近点和次近点：knnsearch采用euclidean距离时得到的结果与lowe采用的近似方法结果几乎一致，正好印证了模拟欧氏距离的效果。
3、Rob Hess的OpenSIFT采用了KDTREE来对匹配进行优化。
4、CSDN大神v_JULY_v实现了KDTREE+BBF对SIFT匹配的优化和消除错误匹配：从K近邻算法、距离度量谈到KD树、SIFT+BBF算法
- 结构之法 算法之道 - 博客频道 - CSDN.NET。
5、OpenCV中features2d实现的SIFT匹配有多种matcher：VectorDescriptorMatcher，BFMatcher（Brute-force descriptor matcher），FernDescriptorMatcher，OneWayDescriptorMatcher，FlannBasedMatcher 等等。目前只知道采用knnsearch，提供了多种距离度量方式，具体区别不懂。

⑤ 机器视觉算法有哪些

机器视觉算法基本步骤；
1、图像数据解码
2、图像特征提取
3、识别图像中目标。
机器视觉是人工智能正在快速发展的一个分支。
简单说来，机器视觉就是用机器代替人眼来做测量和判断。
机器视觉系统是通过机器视觉产品(即图像摄取装置，分CMOS和CCD两种)将被摄取目标转换成图像信号，传送给专用的图像处理系统，得到被摄目标的形态信息，根据像素分布和亮度、颜色等信息，转变成数字化信号;图像系统对这些信号进行各种运算来抽取目标的特征，进而根据判别的结果来控制现场的设备动作。

现在做视觉检测的公司比较多，国内国外都有，许多视觉算是很好的。
能提供完整的机器视觉软件解决方案，也可以为客户提供算法级的定制，覆盖所有的工业应用领域，适用范围比较广。机器视觉的应用会越来越多，因为计算的水平越来越高，可以处理更复杂的视觉算法；其实好多的东西，包括现在流行的GPS，最早都是外国的公司在做，程序都是中国人在做外包；
光机电的应用我个人觉得已经很成熟了，不会再有新东西。