FAST (Features from Accelerated Segment Test)

FAST（Rosten & Drummond, 2006）は、たった一つの目的のために設計されたコーナー検出器である。速度である。画像勾配と構造テンソルを計算する（Harris/Shi-Tomasi）方式や、スケール空間を構築する（SIFT）方式の代わりに、FASTは候補画素の周囲の小さな円上の画素に対する少数の輝度比較だけでコーナーらしさを判定する — これは高フレームレートで毎フレームの全画素に対して実行できるほど安価であり、そのためリアルタイムSLAMフロントエンド（PTAM、SVO、そしてORBを介してORB-SLAMファミリー）のデフォルトの検出器となった。

セグメントテスト

候補画素 $p$ の輝度 $I_p$ と、その周囲にある半径3のBresenham円上の16個の画素を考える。画素 $p$ がコーナーであると宣言されるのは、その円上に、閾値 $t$ を与えたとき、すべてが有意に $p$ より明るい、あるいはすべてが有意に $p$ より暗い、少なくとも $n$ 画素の連続した弧が存在する場合である。

\forall x \in \text{arc}: \quad I_x > I_p + t \qquad \text{or} \qquad \forall x \in \text{arc}: \quad I_x < I_p - t

古典的な選択は $n = 12$ （FAST-12: 16画素中12画素）であり、これは非常に効果的な高速テストを可能にする。方位の4画素（上、右、下、左 — 位置1、5、9、13）だけを検査する。12画素の連続弧が存在するなら、これら4画素のうち少なくとも3画素は $I_p + t$ より明るいか $I_p - t$ より暗いはずである。3画素未満しか合格しなければ、 $p$ はたった4回の比較で棄却される。画像内の画素の大多数はコーナーではないため、この早期終了が平均コストを支配する。

機械学習版

手作りの方位テストには2つの弱点がある。 $n < 12$ に一般化できないこと、そして固定された質問順序が実際の画像統計に対して最適ではないことである。そこでRosten & Drummondは検出器を学習した。16個の円周画素それぞれを $I_p$ に対して明るい/暗い/類似のいずれかに分類し、決定木（ID3アルゴリズムで構築され、情報利得を最大化する）が、学習用画像上で期待比較回数を最小にする画素の質問順序を学習する。この木はネストしたif文にコンパイルされる。これによって、FAST-9（ $n = 9$ ）— 通常最も再現性が高いバリアント — が実用的になっている。これはOpenCVのcv::FastFeatureDetectorが実装しているものである。

非最大値抑制

セグメントテストは、1つのコーナーの周囲にある多くの隣接画素に対して発火する。コーナーごとに1つの応答を保つため、各検出に対してコーナースコアが計算される。

V = \max\!\left( \sum_{x \in S_{\text{bright}}} (I_x - I_p) - t,\;\; \sum_{x \in S_{\text{dark}}} (I_p - I_x) - t \right),

すなわち、支持する弧の総コントラストの最大値であり、非最大値抑制は3×3近傍における $V$ の局所最大値のみを残す。SLAMフロントエンドでは、検出はさらに画像グリッド上でバケット化され、特徴点が1つのテクスチャの多い領域に集中するのではなく、フレーム全体を覆うようにされる。

変種

FAST-9 / FAST-12: 弧の長さ $n$ 。FAST-9はより多くのコーナーを検出し通常最も再現性が高く、FAST-12は学習された木がなくても4画素の早期終了を可能にする。
AGAST（Mair et al., 2010）: 単一の学習済み木を、実行時にローカルな画像統計に適応する汎用の決定木に置き換え、学習用画像への依存を取り除く（BRISKで使用）。
oFAST: ORBのFASTに、パッチの輝度重心からの方位角、画像ピラミッド全体での検出、検出のランク付けと剪定のためのHarris応答を加えたもの。

FASTが与えないもの

記述子なし — FASTは位置だけを見つける。BRIEF/ORBと組み合わせたり、KLTトラックや直接アライメントの種として使われる。
スケール不変性なし — 複数スケールでコーナーを検出するために、画像ピラミッドの各レベルで実行される。
方位なし — ORBのoFASTはパッチの輝度重心を通じて方位を追加する。
閾値の感度 — 単一のグローバルな $t$ はコントラストが変化するシーン全体でうまく機能しない。システムはセルごとに $t$ を適応させたり、検出される特徴点が少なすぎる場合に緩めたりする（ORB-SLAMが行うように）。

SLAMにおける意義

特徴点検出はトラッキングループ内で毎フレーム実行されるため、そのコストが組み込みハードウェアで達成可能なフレームレートを直接制限する。FASTは検出-記述-マッチングの完全なパイプラインをCPU上でリアルタイムにした — PTAMはトラッキングにFASTを使い、SVOはその深度フィルタをFASTコーナーで初期化し、VIOフロントエンド（VINS-Mono、MSCKF実装）はFASTコーナーを検出してKLTで追跡し、ORB（oFAST + rBRIEF）はそれをORB-SLAMファミリーの完全な特徴点に仕立て上げた。セグメントテストを知ることは、実践で観察するFASTの失敗モードも説明する。ノイズ下でのエッジ上の応答、高コントラストテクスチャ上での密集、そしてモーションブラーに対する感度（勾配がにじむと円のコントラストが崩壊する）である。

ハンズオン

Classical local feature detection