.. _BRIEF:


BRIEF (Binary Robust Independent Elementary Features)
***********************************************************

目的
=======
このチュートリアルでは
    * BRIEFについて学びます．


理論
=============

これまでのチュートリアルでSIFTの特徴ベクトルは128次元であることを学びました．各要素が実数値であるため，1つの特徴ベクトルが512byteになります．SURFは64次元であれば256byteになります．このような特徴ベクトルを何千個も保持するには大量のメモリが必要になりますしマッチングにも時間がかかってしまうため，埋め込みシステムなどの計算リソースに制限のある環境では実現不可能と言えます．

しかし実際のマッチングに全次元の情報が必要というわけではありません．PCAやLDAといった方法を使って圧縮することが可能ですし，hashingやLSH(Locality Sensitive Hashing)を使って実数値ベクトルを2値ベクトルに変換することもできます．2値ベクトルのマッチングはハミング距離によって計算できます．ハミング距離の計算はXORとビットカウントのみで実現可能なため，最近のCPUとSSE命令によってとても高速に計算可能です．ここでは最初に特徴ベクトルを計算し，hashingを使うのみにします．

BRIEFは特徴量記述子を使うことなく直接2値ベクトルを計算します．平滑化した画像パッチに対して :math:`n_d` 個の画素(x,y)のペアを構築します．次に，各ペアに対して画素値を比較します．例えば，二つの画素 :math:`p` と :math:`q` を選択し，もし :math:`I(p) < I(q)` であれば1，そうでなければ0とします．この画素の比較を :math:`n_d` 個の画素ペアに対して行い， :math:`n_d` 次元2値ベクトルを計算します．

OpenCVでは :math:`n_d` の値は128，256，512から選択します(デフォルト値は256)．それぞれ整数値に変換すると16,32,64となります．これらの特徴ベクトルのマッチングにはハミング距離を使います．

BRIEFは特徴量記述子であるため特徴点の検出は行いません．そのため，SIFTやSURFなど任意の特徴点検出器を使うようにしてください．論文ではCenSurEを使うよう勧めています．

まとめると，BRIEFは計算，マッチングを高速に行える特徴量記述子です．平面内の回転に対しても高い認識率を実現できます．

OpenCVでのBRIEF
=====================

以下のコードはCenSurEによる特徴点検出とBRIEFによる特徴ベクトルの計算を行うコードです(OpenCVではCenSurEはSTAR検出器と呼ばれています)．

::

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

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

    # Initiate STAR detector
    star = cv2.FeatureDetector_create("STAR")

    # Initiate BRIEF extractor
    brief = cv2.DescriptorExtractor_create("BRIEF")

    # find the keypoints with STAR
    kp = star.detect(img,None)

    # compute the descriptors with BRIEF
    kp, des = brief.compute(img, kp)

    print brief.getInt('bytes')
    print des.shape

関数 ``brief.getInt('bytes')`` によって :math:`n_d` をバイト数で指定します．デフォルト値は32に設定されています．マッチングについては別のチュートリアルで扱います．


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

#. Michael Calonder, Vincent Lepetit, Christoph Strecha, and Pascal Fua, "BRIEF: Binary Robust Independent Elementary Features", 11th European Conference on Computer Vision (ECCV), Heraklion, Crete. LNCS Springer, September 2010.

#. LSH (Locality Sensitive Hasing) at wikipedia.