fast算法原理和實(shí)現(xiàn)方法【Open CV教程】

更新時(shí)間:2021-07-27 來源:黑馬程序員瀏覽量:

1. Fast算法原理

我們前面已經(jīng)介紹過幾個(gè)特征檢測(cè)器，它們的效果都很好，特別是SIFT和SURF算法，但是從實(shí)時(shí)處理的角度來看，效率還是太低了。為了解決這個(gè)問題，Edward Rosten和Tom Drummond在2006年提出了FAST算法，并在2010年對(duì)其進(jìn)行了修正。

FAST (全稱Features from accelerated segment test)是一種用于角點(diǎn)檢測(cè)的算法，該算法的原理是取圖像中檢測(cè)點(diǎn)，以該點(diǎn)為圓心的周圍鄰域內(nèi)像素點(diǎn)判斷檢測(cè)點(diǎn)是否為角點(diǎn)，通俗的講就是若一個(gè)像素周圍有一定數(shù)量的像素與該點(diǎn)像素值不同，則認(rèn)為其為角點(diǎn)。

1. 1 FAST算法的基本流程

在圖像中選取一個(gè)像素點(diǎn) p，來判斷它是不是關(guān)鍵點(diǎn)。$$I_p$$等于像素點(diǎn) p的灰度值。

以r為半徑畫圓，覆蓋p點(diǎn)周圍的M個(gè)像素，通常情狂下，設(shè)置 r=3，則 M=16，如下圖所示：

設(shè)置一個(gè)閾值t，如果在這 16 個(gè)像素點(diǎn)中存在 n 個(gè)連續(xù)像素點(diǎn)的灰度值都高于$$I_p + t$$，或者低于$$I_p - t$$，那么像素點(diǎn) p 就被認(rèn)為是一個(gè)角點(diǎn)。如上圖中的虛線所示，n 一般取值為 12。

由于在檢測(cè)特征點(diǎn)時(shí)是需要對(duì)圖像中所有的像素點(diǎn)進(jìn)行檢測(cè)，然而圖像中的絕大多數(shù)點(diǎn)都不是特征點(diǎn)，如果對(duì)每個(gè)像素點(diǎn)都進(jìn)行上述的檢測(cè)過程，那顯然會(huì)浪費(fèi)許多時(shí)間，因此采用一種進(jìn)行非特征點(diǎn)判別的方法：首先對(duì)候選點(diǎn)的周圍每個(gè) 90 度的點(diǎn)：1，9，5，13 進(jìn)行測(cè)試(先測(cè)試 1 和 19, 如果它們符合閾值要求再測(cè)試 5 和 13)。如果 p 是角點(diǎn)，那么這四個(gè)點(diǎn)中至少有 3 個(gè)要符合閾值要求，否則直接剔除。對(duì)保留下來的點(diǎn)再繼續(xù)進(jìn)行測(cè)試(是否有 12 的點(diǎn)符合閾值要求)。

雖然這個(gè)檢測(cè)器的效率很高，但它有以下幾條缺點(diǎn)：

·獲得的候選點(diǎn)比較多

·特征點(diǎn)的選取不是最優(yōu)的，因?yàn)樗男ЧQ與要解決的問題和角點(diǎn)的分布情況。

·進(jìn)行非特征點(diǎn)判別時(shí)大量的點(diǎn)被丟棄

·檢測(cè)到的很多特征點(diǎn)都是相鄰的

前 3 個(gè)問題可以通過機(jī)器學(xué)習(xí)的方法解決，最后一個(gè)問題可以使用非最大值抑制的方法解決。

1. 2 機(jī)器學(xué)習(xí)的角點(diǎn)檢測(cè)器

選擇一組訓(xùn)練圖片(最好是跟最后應(yīng)用相關(guān)的圖片)

使用 FAST 算法找出每幅圖像的特征點(diǎn)，對(duì)圖像中的每一個(gè)特征點(diǎn)，將其周圍的 16 個(gè)像素存儲(chǔ)構(gòu)成一個(gè)向量P。

每一個(gè)特征點(diǎn)的 16 像素點(diǎn)都屬于下列三類中的一種

根據(jù)這些像素點(diǎn)的分類，特征向量 P 也被分為 3 個(gè)子集：Pd ，Ps ，Pb，

定義一個(gè)新的布爾變量$$K_p$$，如果 p 是角點(diǎn)就設(shè)置為 Ture，如果不是就設(shè)置為 False。

利用特征值向量p，目標(biāo)值是$K_p$，訓(xùn)練ID3 樹(決策樹分類器)。

將構(gòu)建好的決策樹運(yùn)用于其他圖像的快速的檢測(cè)。

1. 3 非極大值抑制

在篩選出來的候選角點(diǎn)中有很多是緊挨在一起的，需要通過非極大值抑制來消除這種影響。

為所有的候選角點(diǎn)都確定一個(gè)打分函數(shù)$$V $$ ， $$V $$的值可這樣計(jì)算：先分別計(jì)算$$I_p$$與圓上16個(gè)點(diǎn)的像素值差值，取絕對(duì)值，再將這16個(gè)絕對(duì)值相加，就得到了$$V $$的值

Fast算法04

最后比較毗鄰候選角點(diǎn)的 V 值，把V值較小的候選角點(diǎn)pass掉。

FAST算法的思想與我們對(duì)角點(diǎn)的直觀認(rèn)識(shí)非常接近，化繁為簡(jiǎn)。FAST算法比其它角點(diǎn)的檢測(cè)算法快，但是在噪聲較高時(shí)不夠穩(wěn)定，這需要設(shè)置合適的閾值。

2.Fast實(shí)現(xiàn)

OpenCV中的FAST檢測(cè)算法是用傳統(tǒng)方法實(shí)現(xiàn)的，

1.實(shí)例化fast

fast = =cv.FastFeatureDetector_create( threshold, nonmaxSuppression)

參數(shù)：

·threshold：閾值t，有默認(rèn)值10

·nonmaxSuppression：是否進(jìn)行非極大值抑制，默認(rèn)值True

Fast：創(chuàng)建的FastFeatureDetector對(duì)象

2.利用fast.detect檢測(cè)關(guān)鍵點(diǎn)，沒有對(duì)應(yīng)的關(guān)鍵點(diǎn)描述

kp = fast.detect(grayImg, None)

參數(shù)：

gray: 進(jìn)行關(guān)鍵點(diǎn)檢測(cè)的圖像，注意是灰度圖像

kp: 關(guān)鍵點(diǎn)信息，包括位置，尺度，方向信息

3.將關(guān)鍵點(diǎn)檢測(cè)結(jié)果繪制在圖像上，與在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角點(diǎn)檢測(cè)
# 2.1 創(chuàng)建一個(gè)Fast對(duì)象，傳入閾值，注意：可以處理彩色空間圖像
fast = cv.FastFeatureDetector_create(threshold=30)

# 2.2 檢測(cè)圖像上的關(guān)鍵點(diǎn)
kp = fast.detect(img,None)
# 2.3 在圖像上繪制關(guān)鍵點(diǎn)
img2 = cv.drawKeypoints(img, kp, None, color=(0,0,255))

# 2.4 輸出默認(rèn)參數(shù)
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 關(guān)閉非極大值抑制
fast.setNonmaxSuppression(0)
kp = fast.detect(img,None)

print( "Total Keypoints without nonmaxSuppression: {}".format(len(kp)) )
# 2.6 繪制為進(jìn)行非極大值抑制的結(jié)果
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()

結(jié)果：

fast算法原理05