SURF (Speeded-Up Robust Features)の導入

目的

このチュートリアルでは
  • SURFの基礎を学びます．
  • OpenCVが提供するSURFに関する関数の使い方を学びます．

理論

前のチュートリアルでSIFTによるキーポイント検出，特徴量の計算について学びました．しかしSIFTの検出器・記述子は相対的に遅く，より高速な検出器・記述子を必要としていました．2006年にBay, H., Tuytelaars, T. and Van Gool, Lらが発表した論文 “SURF: Speeded Up Robust Features” でSURFと呼ばれるアルゴリズムを提案しました．SURFはその名前が示すように，SIFTの高速化版です．

SIFTはLaplacian of GaussianをDifference of Gaussianで近似していました．SURFはBox filterを使ってこの近似を行います．以下の画像はSURFの近似方法を説明する画像です．この近似の最大の利点は，box filterのconvolutionは積分画像を使って簡単に計算できる点にあります．また，異なるスケールの計算を並列にできる点も利点として挙げられます．更に，SURFはスケールと位置両方の極値を見つけるためにHessian行列の行列式を使います．

Box Filter approximation of Laplacian

回転角の計算は6sx6sの領域の横，縦方向のwavelet係数を使います．十分なGaussianの重みも与えます．次に，以下の画像あるようにwaelet係数を空間中にプロットします．60度のwindowをスライドさせながら，wavelet係数の総和を計算することで支配的な回転角を推定します．wavelet係数はあらゆるスケールに対して積分画像を使って非常に簡単に計算できます．多くのアプリケーションにとって回転不変性は不必要なため，この回転角の計算をしなければ高速化が図れます．SURFが提供するこの機能はUpright-SURFもしくはU-SURFと呼ばれます．これによって計算速度を改善できると共に \pm 15^{\circ} の回転まで頑健性があります．OpenCVは両方をサポートしており，フラグ upright の値を0にすると回転角を計算し，1にすると回転角の計算をスキップします．

Orientation Assignment in SURF

特徴量の計算では，縦・横方向のwavelet係数を使います(ここでも積分画像を使うことで計算を簡単化します)．20sx20s画素の近傍領域を4x4の少ブロックに分割します．各小ブロックに対して縦・横方向のwavelet係数から以下のようにベクトルを構成します v=( \sum{d_x}, \sum{d_y}, \sum{|d_x|}, \sum{|d_y|})．これはSURFを64次元ベクトルとして表す時の特徴量になります．次元数を減らせば減らすほど計算，マッチングの速度は上がりますが，特徴量の識別性は下がります．

識別性を上げるためには128次元バージョンの特徴量を計算します． d_y < 0 と d_y \geq 0 に対して d_x と |d_x| の合計を別々に計算します．同様に， また，d_x の符号によって d_y と |d_y| を使い分けます．これによって特徴が2倍になります．この処理の追加は計算の複雑性をそこまで上げません．OpenCVはフラグ extended を0とすると64次元ベクトル，1とすると128次元ベクトルを計算するようになっています(デフォルトは128次元)．

もうひとつの改善点はLaplacian(Hessian行列の跡(trace))の符号を使用することです．点の検出時に既に計算しているため，この処理のために追加計算が不要です．Laplacianの符号は黒い背景上に存在する明るいブロブを白い背景上に存在する暗いブロブから区別するように作用します．マッチング時には，同様の性質を持つ特徴同士のみ比較をすることで，特徴量のパフォーマンスを下げること無くマッチングの高速化を実現します．

Fast Indexing for Matching

まとめると，SURFはSIFTの各処理を高速化する様々な特徴を追加しました．マッチングの精度を保ちつつ3倍の高速化に成功したと解析結果が示しています．SUFTは焦点ボケや回転をうまく扱える一方で，照明変化や視点変化に弱い性質を持ちます．

OpenCVにおけるSURF

OpenCVはSIFT同様，SURFに関する機能を提供しています．SURFオブジェクトの初期化はオプションで特徴量の次元数やUpright/Normal SURFの選択などを指定することができます．詳しくはドキュメントを参照してください．SIFTと同様，SURF.detect()によってキーポイントの検出，SURF.compute()によって点の検出と特徴量の計算を行います．

まずはじめにSURFキーポイントの検出と特徴量の計算，キーポイントの描画を行います．SIFTとほとんど同じコードになるため，Pythonターミナル上で実行した結果を示します．

>>> img = cv2.imread('fly.png',0)

# Create SURF object. You can specify params here or later.
# Here I set Hessian Threshold to 400
>>> surf = cv2.SURF(400)

# Find keypoints and descriptors directly
>>> kp, des = surf.detectAndCompute(img,None)

>>> len(kp)
 699

1199個のキーポイントを1枚の画像上に描画するのは多すぎるため，Hessian行列の閾値を上げて特徴点の数を50個に減らしましょう．ただし，マッチング時では全ての検出したキーポイントを使います．

# Check present Hessian threshold
>>> print surf.hessianThreshold
400.0

# We set it to some 50000. Remember, it is just for representing in picture.
# In actual cases, it is better to have a value 300-500
>>> surf.hessianThreshold = 50000

# Again compute keypoints and check its number.
>>> kp, des = surf.detectAndCompute(img,None)

>>> print len(kp)
47

特徴点の数が50以下になったので，画像上に描画してみましょう．

>>> img2 = cv2.drawKeypoints(img,kp,None,(255,0,0),4)

>>> plt.imshow(img2),plt.show()

以下に結果を示します．SURFがブロブ検出器のようになっていることがわかるかと思います．ちょうちょの羽に白いブロブが検出されています．他の画像のキーポイントも検出してみましょう．

SURF Keypoints with Orientation

次にU-SURFを使ってみましょう．回転角の計算が行われないことが分かります．

# Check upright flag, if it False, set it to True
>>> print surf.upright
False

>>> surf.upright = True

# Recompute the feature points and draw it
>>> kp = surf.detect(img,None)
>>> img2 = cv2.drawKeypoints(img,kp,None,(255,0,0),4)

>>> plt.imshow(img2),plt.show()

以下に結果を示します．全てのキーポイントの回転角が同じ方向を示し，U-SURFを指定しない時に比べ速度が上がっています．パノラマ合成のように回転角が不要なケースであれば，U-SURFを使う方が良いでしょう．

Upright-SURF

最後に特徴量のサイズを確認し，64次元だった場合のみ128次元に変更します．

# Find size of descriptor
>>> print surf.descriptorSize()
64

# That means flag, "extended" is False.
>>> surf.extended
 False

# So we make it to True to get 128-dim descriptors.
>>> surf.extended = True
>>> kp, des = surf.detectAndCompute(img,None)
>>> print surf.descriptorSize()
128
>>> print des.shape
(47, 128)

マッチングについては別のチャプターで扱います．

補足資料

演習