首页人工智能技术资讯正文

fast算法原理和实现方法【Open CV教程】

更新时间:2021-07-27 来源:黑马程序员 浏览量:

1. Fast算法原理

我们前面已经介绍过几个特征检测器,它们的效果都很好,特别是SIFT和SURF算法,但是从实时处理的角度来看,效率还是太低了。为了解决这个问题,Edward Rosten和Tom Drummond在2006年提出了FAST算法,并在2010年对其进行了修正。

FAST (全称Features from accelerated segment test)是一种用于角点检测的算法,该算法的原理是取图像中检测点,以该点为圆心的周围邻域内像素点判断检测点是否为角点,通俗的讲就是若一个像素周围有一定数量的像素与该点像素值不同,则认为其为角点。


1. 1 FAST算法的基本流程

在图像中选取一个像素点 p,来判断它是不是关键点。$$I_p$$等于像素点 p的灰度值。

以r为半径画圆,覆盖p点周围的M个像素,通常情狂下,设置 r=3,则 M=16,如下图所示:

fast算法原理01

设置一个阈值t,如果在这 16 个像素点中存在 n 个连续像素点的灰度值都高于$$I_p + t$$,或者低于$$I_p - t$$,那么像素点 p 就被认为是一个角点。如上图中的虚线所示,n 一般取值为 12。

由于在检测特征点时是需要对图像中所有的像素点进行检测,然而图像中的绝大多数点都不是特征点,如果对每个像素点都进行上述的检测过程,那显然会浪费许多时间,因此采用一种进行非特征点判别的方法:首先对候选点的周围每个 90 度的点:1,9,5,13 进行测试(先测试 1 和 19, 如果它们符合阈值要求再测试 5 和 13)。如果 p 是角点,那么这四个点中至少有 3 个要符合阈值要求,否则直接剔除。对保留下来的点再继续进行测试(是否有 12 的点符合阈值要求)。

虽然这个检测器的效率很高,但它有以下几条缺点:

·获得的候选点比较多

·特征点的选取不是最优的,因为它的效果取决与要解决的问题和角点的分布情况。

·进行非特征点判别时大量的点被丢弃

·检测到的很多特征点都是相邻的

前 3 个问题可以通过机器学习的方法解决,最后一个问题可以使用非最大值抑制的方法解决。


1. 2 机器学习的角点检测器

选择一组训练图片(最好是跟最后应用相关的图片)

使用 FAST 算法找出每幅图像的特征点,对图像中的每一个特征点,将其周围的 16 个像素存储构成一个向量P。

机器学习角点检测器

每一个特征点的 16 像素点都属于下列三类中的一种

fast算法03

根据这些像素点的分类,特征向量 P 也被分为 3 个子集:Pd ,Ps ,Pb,

定义一个新的布尔变量$$K_p$$,如果 p 是角点就设置为 Ture,如果不是就设置为 False。

利用特征值向量p,目标值是$K_p$,训练ID3 树(决策树分类器)。

将构建好的决策树运用于其他图像的快速的检测。


1. 3 非极大值抑制

在筛选出来的候选角点中有很多是紧挨在一起的,需要通过非极大值抑制来消除这种影响。

为所有的候选角点都确定一个打分函数$$V $$ , $$V $$的值可这样计算:先分别计算$$I_p$$与圆上16个点的像素值差值,取绝对值,再将这16个绝对值相加,就得到了$$V $$的值

Fast算法04

最后比较毗邻候选角点的 V 值,把V值较小的候选角点pass掉。

FAST算法的思想与我们对角点的直观认识非常接近,化繁为简。FAST算法比其它角点的检测算法快,但是在噪声较高时不够稳定,这需要设置合适的阈值。


2.Fast实现

OpenCV中的FAST检测算法是用传统方法实现的,


1.实例化fast

fast = =cv.FastFeatureDetector_create( threshold, nonmaxSuppression)

参数:

·threshold:阈值t,有默认值10

·nonmaxSuppression:是否进行非极大值抑制,默认值True

返回:

Fast:创建的FastFeatureDetector对象


2.利用fast.detect检测关键点,没有对应的关键点描述

kp = fast.detect(grayImg, None)

参数:

gray: 进行关键点检测的图像,注意是灰度图像

返回:

kp: 关键点信息,包括位置,尺度,方向信息


3.将关键点检测结果绘制在图像上,与在sift中是一样的

cv.drawKeypoints(image, keypoints, outputimage, color, flags)

示例:

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt
# 1 读取图像
img = cv.imread('./image/tv.jpg')
# 2 Fast角点检测
# 2.1 创建一个Fast对象,传入阈值,注意:可以处理彩色空间图像
fast = cv.FastFeatureDetector_create(threshold=30)

# 2.2 检测图像上的关键点
kp = fast.detect(img,None)
# 2.3 在图像上绘制关键点
img2 = cv.drawKeypoints(img, kp, None, color=(0,0,255))

# 2.4 输出默认参数
print( "Threshold: {}".format(fast.getThreshold()) )
print( "nonmaxSuppression:{}".format(fast.getNonmaxSuppression()) )
print( "neighborhood: {}".format(fast.getType()) )
print( "Total Keypoints with nonmaxSuppression: {}".format(len(kp)) )


# 2.5 关闭非极大值抑制
fast.setNonmaxSuppression(0)
kp = fast.detect(img,None)

print( "Total Keypoints without nonmaxSuppression: {}".format(len(kp)) )
# 2.6 绘制为进行非极大值抑制的结果
img3 = cv.drawKeypoints(img, kp, None, color=(0,0,255))

# 3 绘制图像
fig,axes=plt.subplots(nrows=1,ncols=2,figsize=(10,8),dpi=100)
axes[0].imshow(img2[:,:,::-1])
axes[0].set_title("加入非极大值抑制")
axes[1].imshow(img3[:,:,::-1])
axes[1].set_title("未加入非极大值抑制")
plt.show()

结果:

fast算法原理05



《图像处理OpenCV入门教程》课程导读


加QQ:2217622915,获取《图像处理OpenCV入门教程》全套视频教程+笔记+源码



猜你喜欢:

SIFT算法原理:SIFT算法详细介绍

什么是图像特征?如何让计算机理解图像特征?

Harris角点检测原理

OpenCV图像叠加和图像混合

黑马程序员人工智能开发课程

分享到:
在线咨询 我要报名
和我们在线交谈!