加速セグメントテストからの特徴

FAST（Features from accelerated segment test）は、特徴点を抽出して、多くのコンピュータビジョンタスクでオブジェクトの追跡やマッピングに使用できるコーナー検出方法です。FASTコーナー検出器は、もともとEdward RostenとTom Drummondによって開発され、2006年に発表されました。^{[ 1 ]} FASTコーナー検出器の最も有望な利点は、計算効率です。その名前からわかるように、SIFT、SUSAN、Harris検出器で使用されるガウス差分（DoG）などの他の多くのよく知られた特徴抽出方法よりも高速です。さらに、機械学習技術を適用すると、計算時間とリソースの面で優れたパフォーマンスが実現できます。この高速なパフォーマンスにより、FASTコーナー検出器はリアルタイムビデオ処理アプリケーションに非常に適しています。

FASTコーナー検出器は、16ピクセルの円（半径3のブレゼンハム円）を使用して、候補点pが実際にコーナーであるかどうかを分類します。円内の各ピクセルには、時計回りに1から16までの整数値が付けられます。円内のN個の連続するピクセルがすべて、候補ピクセルpの強度（I _pで表される）に閾値tを加えた値よりも明るいか、または候補ピクセルpの強度から閾値tを引いた値よりも暗い場合、pはコーナーとして分類されます。条件は次のように記述できます。

• 条件 1: N 個の連続するピクセル S のセット、${\displaystyle \forall x\in S}$、${\displaystyle I_{x}>I_{p}+t}$（明るい背景に暗い隅）
• 条件2：N個の連続するピクセルSのセット、${\displaystyle \forall x\in S}$、${\displaystyle I_{x}<I_{p}-t}$（暗い背景に明るい隅）

したがって、2 つの条件のいずれかが満たされると、候補 p はコーナーとして分類されます。連続するピクセル数 N と閾値 t の選択にはトレードオフがあります。一方では、検出されるコーナー点の数が多すぎないようにする必要がありますが、他方では、計算効率を犠牲にして高いパフォーマンスを達成してはなりません。機械学習の改善がない場合、N は通常 12 に選択されます。コーナー点以外の点を除外するために、高速テスト方法を適用できます。

コーナー以外の点を排除するための高速テストは、ピクセル 1、9、5、13 の 4 つのサンプル ピクセルを調べることによって実行されます。候補コーナーよりも明るいか暗いかにかかわらず、少なくとも 12 個の連続するピクセルが存在する必要があるため、これら 4 つのサンプル ピクセルのうち、候補コーナーよりも明るいか暗いピクセルが少なくとも 3 つ存在する必要があります。まず、ピクセル 1 と 9 を調べ、I ₁と I ₉の両方が[I _p - t, I _p + t] の範囲内にある場合、候補 p はコーナーではありません。そうでない場合、ピクセル 5 と 13 をさらに調べて、そのうち 3 つが I _p + t より明るいか、I _p - t より暗いかどうかを確認します。明るいか暗いピクセルが 3 つ存在する場合、残りのピクセルを調べて最終的な結論を出します。また、発明者の最初の論文^{[ 2 ]}によると、平均して 3.8 ピクセルが候補コーナー ピクセルをチェックするために必要です。各候補コーナーの8.5ピクセルと比較すると、3.8ピクセルというのは非常に大きな削減であり、パフォーマンスを大幅に向上させることができる。

しかし、このテスト方法にはいくつかの弱点がある。

1. 高速テストは、N < 12 の場合、うまく一般化できません。N < 12 の場合、候補 p がコーナーである可能性があり、4 つのサンプル テスト ピクセルのうち、I _{p + t より明るいか、I p} - tより暗いかの2 つだけになる可能性があります。
2. 検出器の効率は、選択されたテストピクセルの選択と順序に依存します。しかし、選択されたピクセルが、コーナーの外観分布を考慮した最適なものである可能性は低いでしょう。
3. 複数の特徴が互いに隣接して検出される

高速テストの最初の2つの弱点に対処するため、検出アルゴリズムの改善に役立つ機械学習アプローチが導入されています。この機械学習アプローチは2つの段階で動作します。まず、指定されたNを使用して、対象となるアプリケーションドメインから望ましいトレーニング画像セットでコーナー検出が処理されます。コーナーは、16ピクセルのリングを文字通り抽出し、強度値を適切な閾値と比較するという最も単純な実装によって検出されます。

候補 p について、円 x ∈ {1, 2, 3, ..., 16} 上の各位置を p→x と表すことができる。各ピクセルの状態 S _{p→x は、}次の 3 つの状態のいずれかでなければならない。

• d、I _p→x ≤ I _p - t (より暗い)
• s、I _p - t ≤ I _p→x ≤ I _p + t (同様)
• b、I _p→x ≥ I _p + t (より明るい)

次に、x（すべてのpに対して同じ）を選択すると、P（すべてのトレーニング画像のすべてのピクセルの集合）が3つの異なるサブセット、P _d、P _s、P _bに分割されます。ここで、

• P _d = {p ∈ P  : S _p→x = d }
• P _s = {p ∈ P  : S _p→x = s }
• P _b = {p ∈ P  : S _p→x = b }

次に、情報利得を最大化するために、決定木アルゴリズムであるID3アルゴリズムを16箇所に適用します。K _pをpがコーナーであるかどうかを示すブール変数とすると、 K _pのエントロピーはpがコーナーであることの情報量を測定するために使用されます。ピクセルセットQの場合、K _Qの合計エントロピー（正規化されていない）は次のようになります。

• H(Q) = ( c + n ) log ₂ ( c + n ) - 詰まり₂ c - nlog ₂ n
  • ここで c = |{ i ∈ Q: K _iは真}| (角の数)
  • ここで n = |{ i ∈ Q: K _iは偽}| (非角の数)

情報利得は次のように表すことができます。

• H _g = H(P) - H(P _b ) - H(P _s ) - H(P _d )

各サブセットに対して再帰的な処理を適用し、情報利得を最大化できる各 x を選択します。例えば、最初に、最も情報量の多いx を選択して P を P _d、 P _s、 P _{bに分割します。次に、各サブセット P d}、 P _s、 P _bに対して、情報利得が最大となる別の y を選択します（y は x と同じ場合もあります）。この再帰的な処理は、エントロピーがゼロになった時点で終了します。つまり、そのサブセット内のすべてのピクセルがコーナーであるか、コーナーではないかのいずれかになります。

生成された決定木は、 CやC++などのプログラミングコードに変換できます。これは、入れ子になったif-else文の集合です。最適化のために、プロファイル誘導型最適化を使用してコードをコンパイルします。コンパイルされたコードは、後で他の画像のコーナー検出器として使用されます。

この決定木アルゴリズムを使用して検出された角は、セグメントテスト検出器を使用した結果とは若干異なることに注意してください。これは、決定木モデルがトレーニングデータに依存しており、トレーニングデータではすべての可能な角を網羅できないためです。

「セグメントテストではコーナー応答関数を計算しないため、結果として得られる特徴量に非最大抑制を直接適用することはできません。」ただし、Nが固定されている場合、各ピクセルpについて、コーナー強度は、paをコーナーにするtの最大値として定義されます。したがって、2つのアプローチが考えられます。

• 二分探索アルゴリズムを適用することで、pが依然としてコーナーとなる最大のtを見つけることができます。そのため、決定木アルゴリズムでは毎回異なるtが設定されます。最大のtが見つかった場合、そのtをコーナーの強度とみなすことができます。
• 別のアプローチとしては、反復方式があり、毎回tをテストに合格する最小値まで増加させる。

FAST-ER検出器は、メタヒューリスティックアルゴリズム（この場合はシミュレーテッドアニーリング）を使用してFAST検出器を改良したものです。最適化後、決定木の構造は最適化され、再現性の高い点に適したものになります。ただし、シミュレーテッドアニーリングはメタヒューリスティックアルゴリズムであるため、アルゴリズムを実行するたびに異なる最適化された決定木が生成されます。そのため、実際の最適解に近い解を見つけるには、効率的に多数の反復を実行する方が良いでしょう。Rosten氏によると、 FAST検出器を最適化するには、 3GHzのPentium 4 で約200時間（100,000回の反復を100回繰り返す）かかります。

Rostenの研究では、^{[ 3 ]} FASTおよびFAST-ER検出器がいくつかの異なるデータセットで評価され、DoG、Harris、Harris-Laplace、Shi-Tomasi、およびSUSANコーナー検出器と比較されています。

FAST以外の検出器のパラメータ設定は以下のとおりです。

• 再現性テストの結果は、すべてのデータセット（加算ノイズを除く）について、フレームあたり0～2000個のコーナーにおける再現性曲線下の平均面積として示されます。

•  速度テストは3.0GHz Pentium 4-Dコンピュータで実施しました。データセットはトレーニングセットとテストセットに分割されています。トレーニングセットは、解像度992×668ピクセルのモノクロ画像101枚で構成されています。テストセットは、352×288ピクセルのモノクロ動画4968フレームで構成されています。結果は以下のとおりです。

• Rosten, Edward; Tom Drummond (2005). 「高性能トラッキングのための点と線の融合」.第10回IEEE国際コンピュータビジョン会議（ICCV'05）第1巻（PDF） . 第 2巻. pp. 1508–1511 . CiteSeerX 10.1.1.60.4715 . doi : 10.1109/ICCV.2005.104 . ISBN   978-0-7695-2334-7. S2CID 1505168 . 
• Rosten, Edward; Reid Porter; Tom Drummond (2010). "FASTER and better: 機械学習によるコーナー検出アプローチ". IEEE Transactions on Pattern Analysis and Machine Intelligence . 32 (1): 105–119 . arXiv : 0810.2434 . doi : 10.1109/TPAMI.2008.275 . PMID 19926902 . S2CID 206764370 .  
• Rosten, Edward; Tom Drummond (2006). 「高速コーナー検出のための機械学習」. Computer Vision – ECCV 2006 (PDF) . Lecture Notes in Computer Science. Vol.  1. pp. 430–443 . CiteSeerX 10.1.1.64.8513 . doi : 10.1007/11744023_34 . ISBN   978-3-540-33832-1. S2CID 1388140 . {{cite book}}:|journal=無視されました (ヘルプ)

• アドバンストビジョンホームページ