目標

この章では

BRIEFアルゴリズムの基礎を学ぶ

理論

SIFTは記述子に128次元のベクトルを使うことが知られている。浮動小数点数を使っているため、基本的に512バイトを要する。同様にSURFも最低256バイト (64次元の場合) を必要とする。数千もの特徴に対してこのようなベクトルを生成すると大量のメモリを消費し、特に組み込みシステムなどのリソースに制約のあるアプリケーションでは現実的でない。メモリが大きくなるほど、マッチングに要する時間も長くなる。

しかし、これらの次元すべてが実際のマッチングに必要なわけではない。PCAやLDAなどのいくつかの手法を用いて圧縮できる。さらにLSH (Locality Sensitive Hashing) を用いたハッシュ化などの手法もあり、浮動小数点数によるこれらのSIFT記述子をバイナリ文字列に変換するために使われる。これらのバイナリ文字列はハミング距離を用いて特徴のマッチングに使われる。ハミング距離の計算はXORとビットカウントを適用するだけであり、SSE命令を備えた最新のCPUでは非常に高速であるため、これによってより良い高速化が得られる。しかしここでは、まず記述子を求める必要があり、その後でしかハッシュ化を適用できないため、メモリに関する当初の問題を解決できない。

ここで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になる)。これが得られたら、ハミング距離を用いてこれらの記述子をマッチングできる。

重要な点の1つは、BRIEFは特徴記述子であり、特徴を求める方法を一切提供しないということである。したがって、SIFTやSURFなど他の特徴検出器を使う必要がある。論文では高速な検出器であるCenSurEの使用を推奨しており、BRIEFはSURFの点よりもCenSurEの点に対してわずかに良好に機能する。

要するに、BRIEFは特徴記述子の計算とマッチングをより高速に行う手法である。また、大きな面内回転がない限り高い認識率を提供する。

OpenCVでのSTAR(CenSurE)

STARはCenSurEから派生した特徴検出器である。ただしCenSurEが円に近づけるために正方形・六角形・八角形などの多角形を使うのとは異なり、STARは2つの重なり合う正方形で円を模倣する。1つは正立した正方形、もう1つは45度回転した正方形である。これらの多角形は2レベルである。太い境界を持つ多角形と見なせる。境界と囲まれた領域は符号が逆の重みを持つ。これは他のスケールスペース検出器より優れた計算特性を持ち、リアルタイム実装が可能である。SIFTやSURFが大きなスケールで精度を損なうサブサンプリングされたピクセルで極値を求めるのに対し、CenSurEはピラミッドの全スケールで完全な空間解像度を用いて特徴ベクトルを生成する。

OpenCVでのBRIEF

以下のコードはCenSurE検出器を使ったBRIEF記述子の計算を示す。

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

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt
 
img = cv.imread('simple.jpg', cv.IMREAD_GRAYSCALE)
 
# Initiate FAST detector
star = cv.xfeatures2d.StarDetector_create()
 
# Initiate BRIEF extractor
brief = cv.xfeatures2d.BriefDescriptorExtractor_create()
 
# find the keypoints with STAR
kp = star.detect(img,None)
 
# compute the descriptors with BRIEF
kp, des = brief.compute(img, kp)
 
print( brief.descriptorSize() )
print( des.shape )

関数 brief.getDescriptorSize() は、使われている \(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 Hashing)。