目標

本章では、

FASTアルゴリズムの基本を理解する
FASTアルゴリズム向けのOpenCVの機能を使ってコーナーを見つける。

理論

これまでにいくつかの特徴検出器を見てきたが、その多くは実に優れている。しかしリアルタイムアプリケーションの観点から見ると、それらは十分に高速ではない。よい例の1つはSLAM (Simultaneous Localization and Mapping、自己位置推定と地図作成の同時実行) を行う移動ロボットで、計算資源が限られている。

これに対する解決策として、Edward RostenとTom Drummondが2006年の論文「Machine learning for high-speed corner detection」でFAST (Features from Accelerated Segment Test) アルゴリズムを提案した（後に2010年に改訂された）。アルゴリズムの基本的な概要を以下に示す。詳細は原論文を参照のこと（すべての画像は原論文から引用している）。

FASTを用いた特徴検出

画像中で、注目点(interest point)かどうかを判定する対象となるピクセル \(p\) を選ぶ。その輝度を \(I_p\) とする。
適切なしきい値 \(t\) を選ぶ。
テスト対象のピクセルの周囲にある16ピクセルの円を考える。（下の画像を参照）

image

円（16ピクセル）の中に、すべて \(I_p + t\) より明るいか、またはすべて \(I_p − t\) より暗い \(n\) 個の連続したピクセルの集合が存在すれば、ピクセル \(p\) はコーナーである。（上の画像では白い破線で示されている）。\(n\) は12が選ばれた。
A high-speed test was proposed to exclude a large number of non-corners. This test examines only the four pixels at 1, 9, 5 and 13 (First 1 and 9 are tested if they are too brighter or darker. If so, then checks 5 and 13). If \(p\) is a corner, then at least three of these must all be brighter than \(I_p + t\) or darker than \(I_p − t\). If neither of these is the case, then \(p\) cannot be a corner. The full segment test criterion can then be applied to the passed candidates by examining all pixels in the circle. This detector in itself exhibits high performance, but there are several weaknesses:
- n < 12 の場合、候補をそれほど多く除外できない。
- ピクセルの選択は最適ではない。その効率は質問の順序とコーナーの出現分布に依存するからである。
- 高速テストの結果が捨てられてしまう。
- 複数の特徴が互いに隣接して検出される。

最初の3点は機械学習のアプローチで対処される。最後の1点は非最大抑制(non-maximal suppression)を用いて対処される。

コーナー検出器の機械学習

学習用の画像の集合を選ぶ（対象アプリケーションの分野のものが望ましい）
すべての画像でFASTアルゴリズムを実行し、特徴点を見つける。
各特徴点について、その周囲の16ピクセルをベクトルとして格納する。これをすべての画像に対して行い、特徴ベクトル \(P\) を得る。
これら16ピクセルの各ピクセル（仮に \(x\) とする）は、次の3つの状態のいずれかをとりうる:

image

これらの状態に応じて、特徴ベクトル \(P\) は3つの部分集合 \(P_d\)、\(P_s\)、\(P_b\) に分割される。
新しいブール変数 \(K_p\) を定義する。これは \(p\) がコーナーであれば真、そうでなければ偽である。
ID3アルゴリズム（決定木分類器）を使い、変数 \(K_p\) を用いて各部分集合に対して真のクラスに関する情報を問い合わせる。\(K_p\) のエントロピーで測られる、候補ピクセルがコーナーであるかどうかについて最も多くの情報を与える \(x\) を選択する。
これは、エントロピーが0になるまで、すべての部分集合に対して再帰的に適用される。
こうして作成された決定木は、他の画像での高速な検出に使われる。

非最大抑制 (Non-maximal Suppression)

隣接する位置で複数の注目点が検出されることが、もう1つの問題である。これは非最大抑制(Non-maximum Suppression)を用いて解決される。

検出されたすべての特徴点に対してスコア関数 \(V\) を計算する。\(V\) は \(p\) と周囲の16ピクセルの値との絶対差の総和である。
隣接する2つのキーポイントを考え、それらの \(V\) 値を計算する。
\(V\) 値が低い方を破棄する。

まとめ

既存の他のコーナー検出器より数倍高速である。

ただし、高レベルのノイズに対しては頑健ではない。しきい値に依存する。

OpenCVにおけるFAST特徴検出器

OpenCVの他の特徴検出器と同じように呼び出せる。必要であれば、しきい値、非最大抑制を適用するかどうか、使用する近傍などを指定できる。

近傍に対しては、cv.FAST_FEATURE_DETECTOR_TYPE_5_8、cv.FAST_FEATURE_DETECTOR_TYPE_7_12、cv.FAST_FEATURE_DETECTOR_TYPE_9_16の3つのフラグが定義されている。以下は、FAST特徴点を検出して描画する簡単なコードである。

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt
 
img = cv.imread('blox.jpg', cv.IMREAD_GRAYSCALE) # `<opencv_root>/samples/data/blox.jpg`
 
# Initiate FAST object with default values
fast = cv.FastFeatureDetector_create()
 
# find and draw the keypoints
kp = fast.detect(img,None)
img2 = cv.drawKeypoints(img, kp, None, color=(255,0,0))
 
# Print all default params
print( "Threshold: {}".format(fast.getThreshold()) )
print( "nonmaxSuppression:{}".format(fast.getNonmaxSuppression()) )
print( "neighborhood: {}".format(fast.getType()) )
print( "Total Keypoints with nonmaxSuppression: {}".format(len(kp)) )
 
cv.imwrite('fast_true.png', img2)
 
# Disable nonmaxSuppression
fast.setNonmaxSuppression(0)
kp = fast.detect(img, None)
 
print( "Total Keypoints without nonmaxSuppression: {}".format(len(kp)) )
 
img3 = cv.drawKeypoints(img, kp, None, color=(255,0,0))
 
cv.imwrite('fast_false.png', img3)

結果を見てほしい。1枚目の画像はnonmaxSuppressionありのFAST、2枚目はnonmaxSuppressionなしのFASTである:

image

追加リソース

Edward Rosten and Tom Drummond, "Machine learning for high speed corner detection" in 9th European Conference on Computer Vision, vol. 1, 2006, pp. 430–443.
Edward Rosten, Reid Porter, and Tom Drummond, "Faster and better: a machine learning approach to corner detection" in IEEE Trans. Pattern Analysis and Machine Intelligence, 2010, vol 32, pp. 105-119.