.. _FAST:

コーナー検出のためのFASTアルゴリズム
*************************************

目的
=======

このチュートリアルでは
    * FASTアルゴリズムについて学びます．
    * OpenCVのFASTに関係する関数を使ってコーナー検出を行う．
    

理論
=========

今までのチュートリアルで特徴検出器を幾つか見てきました．しかし実時間アプリケーションという観点で見た時，十分高速とは言えません． その最たる例はSLAM (Simultaneous Localization and Mapping)と呼ばれる限定された計算資源しか持たないモバイルロボットが挙げられます．

この処理速度に関する問題を解決する方法として，Edward RostenとTom Drummondが論文"Machine learning for high-speed corner detection"でFAST (Features from Accelerated Segment Test)アルゴリズムを提案しました．ここではFASTアルゴリズムの概要の説明しかしないので，詳細については原論文を参照してください．  


FASTを使ったコーナー検出
------------------------------

1. 画像中から画素 :math:`p` を選択し，その画素値を :math:`I_p` とします．
2. 適切な閾値 :math:`t` を選択します．
3. 注目画素を中心とし円周が16画素となる円を考えます(以下の図を参照)．

    .. image:: images/fast_speedtest.jpg
        :alt: A corner in the image
        :align: center
        
4. 円上の連続する :math:`n` 画素の画素値が全て :math:`I_p + t` より高い，もしくは全て :math:`I_p − t` より低い時，その画素 :math:`p` をコーナーとして検出します(上の画像中の白い点線を見てください)．
5.  **高速テスト** は大量の非コーナーを排除するために行います．このテストは円周上の4画素(図中の中の1，9，5，13番目の画素)のみをテストします．まずはじめに画素1，9が明かるいか/暗いかを確認します．どちらかの条件を満たした時のみ画素5，13の画素値をテストします．もし画素 :math:`p` がコーナーであれば，上記の4画素の内，少なくとも3画素の画素値は :math:`I_p + t` より大きいか，もしくは :math:`I_p − t` より小さくなります．もしどちらにも当てはまらなければ画素 :math:`p` は非コーナーと判断されます．このテストの条件を満たした画素に対して，円周上の全画素のテストを行います．この検出器は高い性能を誇るものの，幾つかの問題点があります．

    * n < 12と設定すると，多くの候補を除外しなくなる．
    * 計算効率がテストの順番とコーナーの分布に依存するため，画素の選択方法が最適ではない．
    * 高速テストの結果は棄却される．
    * 隣接する画素が両方ともコーナーとして検出される．

最初の3つの問題は機械学習の方法で解決できます．最後の問題はnon-maximal suppressionによって解決します．


コーナー検出器への機械学習の導入
------------------------------------

1. 学習用の画像セットを選択します(対象とするアプリケーションで使用する画像が好ましい)
2. 全ての画像に対してFASTによる特徴点の検出を行います．
3. 検出した全ての特徴点に対して，各特徴点の周囲の16画素の画素値を特徴ベクトル :math:`P` として保持します．
4. 16画素中の各画素　:math:`x` は以下のいずれかの状態になります:

    .. image:: images/fast_eqns.jpg
        :alt: FAST equation
        :align: center

5. 画素の状態に応じて特徴ベクトル :math:`P` を3つの部分集合 :math:`P_d` , :math:`P_s` , :math:`P_b`に分割します．
6. 新たな2値変数 :math:`K_p` を定義し，画素 :math:`p` がコーナーであればtrue，そうでなければfalseと設定します．
7. ID3アルゴリズム(決定木識別器)を使い各部分集合から2値変数 :math:`K_p` を推定します．ID3アルゴリズムは :math:`K_p` のエントロピーを評価し，注目画素がコーナーの候補であるか否かについて最大の情報をもたらします．
8. この処理をエントロピーがゼロになるまで再帰的に繰り返します．
9. 決定木を構築できれば，別の画像のコーナー検出を高速に行えるようになります．


Non-maximal Suppression
---------------------------

もう一つの問題として隣接画素上に複数の特徴点が検出される点が挙げられます．
Detecting multiple interest points in adjacent locations is another problem. It is solved by using Non-maximum Suppression.

1. 検出された全特徴点に対して評価関数 :math:`V` を使って評価値を計算します．:math:`V` は画素 :math:`p` とその周囲の16画素の画素値の絶対差分和になります．
2. 隣接する2画素の評価値を比較します．
3. 評価値 :math:`V` が低い特徴点を候補から除外します．
    

まとめ
-----------

FASTは既存のコーナー検出器より数倍高速に動作します．

しかし，ノイズの影響が大きい画像では閾値に依存してしまい頑健な検出ができません．


OpenCVのFASTコーナー検出器
==================================

OpenCVの他の特徴点検出器と同じように呼び出します．必要であれば，閾値の指定，non-maximum suppressionの使用の有無，高速テストの際に使用する画素などを指定することができます．

高速テストの際に使用する画素のために3つのフラグ　``cv2.FAST_FEATURE_DETECTOR_TYPE_5_8``, ``cv2.FAST_FEATURE_DETECTOR_TYPE_7_12``，``cv2.FAST_FEATURE_DETECTOR_TYPE_9_16`` が定義されています．FASTを使ったコーナー検出について以下に示します．
::

    import numpy as np
    import cv2
    from matplotlib import pyplot as plt

    img = cv2.imread('simple.jpg',0)

    # Initiate FAST object with default values
    fast = cv2.FastFeatureDetector()

    # find and draw the keypoints
    kp = fast.detect(img,None)
    img2 = cv2.drawKeypoints(img, kp, color=(255,0,0))

    # Print all default params
    print "Threshold: ", fast.getInt('threshold')
    print "nonmaxSuppression: ", fast.getBool('nonmaxSuppression')
    print "neighborhood: ", fast.getInt('type')
    print "Total Keypoints with nonmaxSuppression: ", len(kp) 

    cv2.imwrite('fast_true.png',img2)

    # Disable nonmaxSuppression
    fast.setBool('nonmaxSuppression',0)
    kp = fast.detect(img,None)

    print "Total Keypoints without nonmaxSuppression: ", len(kp) 

    img3 = cv2.drawKeypoints(img, kp, color=(255,0,0))

    cv2.imwrite('fast_false.png',img3)

このコードを実行した結果を見てみましょう．左の画像はnon-maximum suppressionを使わずに検出したコーナー，右の画像はnon-maximum suppressionを使って検出したコーナーを描画しています:

    .. image:: images/fast_kp.jpg
        :alt: FAST Keypoints
        :align: center


補足資料
=========================

#. 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.


演習
============