BRIEF (Binary Robust Independent Elementary Features, 二値頑健独立基本特徴)

目的

このチュートリアルでは
  • BRIEFアルゴリズムの基礎を学ぶ

理論

SIFTでは特徴記述子に128次元のベクトルを用いていた。この要素は浮動小数点数で、基本的に512バイト必要とする。同様にSURFも最小限 256 バイト(64次元)必要とする。このようなベクトルを何千もの特徴点に対して作るとすれば、特に埋め込みシステムのような計算資源の成約が厳しいアプリケーションでは使えるものではない。マッチングをするために、記憶容量をたくさん必要とすればするほど時間がその分長くかかる。

しかし実際のマッチングにはすべての次元が必要とされるわけではない。PCAやLDAのような手法を用いて圧縮することができる。LSH(Locality Sensitive Hashing, 局所性鋭敏型ハッシュ)のようなハッシュ法でさえ、SIFTの特徴記述子を浮動小数点数から二値コード列に変換するのに使える。そして、二値コード列で表された特徴点はハミング距離によりマッチング(照合)させられる。ハミング距離の計算は単にXORとビット数の数え上げだけで計算でき、またこれ自体SSEをもつCPUではとても高速に演算可能なので、マッチングの高速化が可能になる。しかしここで、まず特徴記述子を先に決定しなければならない。そしてハッシュ法の適用だけではメモリ容量についての最初の問題を解決しているわけではない。

ここでBRIEFが解決の戸口を開く。BRIEFは特徴記述子を求めず、直接二値コード列を返すという「近道」を与える。BRIEFは平滑化された画像のパッチを取り、ユニークな方法(論文で記述されている)で n_d 個の(x,y)位置のペアを選び出す。そして、これらの位置のペアにおいて輝度値の比較を行う。例えば最初の位置のペアをp と qとする。もしも I(p) < I(q)であればその結果を1，そうでなければ0とする。これを n_d個の位置のペアすべて対して行い、 n_d次元のビットコード列を得る。

この n_d は、128, 256、512の値を取りうる。OpenCVはこれらすべてをサポートしているが、デフォルトでは 256である (OpenCVではバイト数で表すので、値は 16, 32, 64である).これが求まれば、ハミング距離を用いてこれらの記述子のマッチングが行える。

一つ重要な点は、BRIEFは特徴記述器であり、特徴点を検出する方法を与えていないということである。そこで、SIFTやSURFなどのような特徴点検出器が必要である。論文では CenSurE という高速の検出器の使用を勧めており、BRIEFはSURFの特徴点に対するよりもCenSurEの特徴点に対する方が少しだけ性能がよい。

要するに、BRIEFは高速の特徴記述子演算器であり、照合器でもある。また平面内での大きな回転がなければ、高い認識性能をももつ。

OpenCVのBRIEF

以下にCenSurE特徴検出器を用いたBRIEF特徴記述子の計算方法を示す。(CenSurE特徴検出器はOpenCVではSTAR特徴検出器と呼ばれている)

注意: これを使うにはopencv contrib が必要である。

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

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

# STAR検出器を作る
star = cv2.xfeatures2d.StarDetector_create()

# BRIEF抽出器を作る
brief = cv2.xfeatures2d.BriefDescriptorExtractor_create()

# STARでキーポイントを計算
kp = star.detect(img,None)

# BRIEFで特徴記述子を計算
kp, des = brief.compute(img, kp)

print brief.descriptorSize()
print des.shape

補足資料

  1. 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.
  2. LSH (Locality Sensitive Hasing, 局所性鋭敏型ハッシュ) at wikipedia.

課題