SURF (Speeded-Up Robust Features) 入門

目標

本章では、

• SURFの基礎を学ぶ
• OpenCVにおけるSURFの機能を学ぶ

理論

前章では、キーポイント検出と記述のためのSIFTを見た。しかし、それは比較的低速であり、よりスピードアップされたバージョンが求められていた。2006年、Bay, H.、Tuytelaars, T.、Van Gool, L. の3人が、SURFと呼ばれる新しいアルゴリズムを紹介した別の論文「SURF: Speeded Up Robust Features」を発表した。名前が示すとおり、これはSIFTのスピードアップ版である。

SIFTでは、Loweはスケール空間を求めるためにガウシアンのラプラシアン (Laplacian of Gaussian) をガウシアンの差分 (Difference of Gaussian) で近似した。SURFはさらに一歩進めて、LoGをボックスフィルタで近似する。下の画像はそのような近似の実演を示している。この近似の大きな利点の1つは、ボックスフィルタとの畳み込みが積分画像の助けを借りて容易に計算できることである。また、異なるスケールに対して並列に実行できる。さらにSURFは、スケールと位置の両方についてヘッセ行列 (Hessian matrix) の行列式に依拠している。

image

向きの割り当てにおいて、SURFはサイズ6sの近傍について水平・垂直方向のウェーブレット応答を用いる。それには適切なガウス重みも適用される。次に、それらは下図のような空間にプロットされる。支配的な向きは、角度60度のスライディング窓内のすべての応答の和を計算することで推定される。興味深いのは、ウェーブレット応答が積分画像を用いることで任意のスケールにおいて非常に容易に求められる点である。多くのアプリケーションでは回転不変性は不要なため、この向きを求める必要がなく、処理が高速化される。SURFはこのような機能をUpright-SURFまたはU-SURFとして提供する。これは速度を改善し、\(\pm 15^{\circ}\)までロバストである。OpenCVはフラグ upright に応じて両方をサポートする。0の場合は向きが計算される。1の場合は向きが計算されず、より高速になる。

image

特徴記述のために、SURFは水平・垂直方向のウェーブレット応答を用いる（ここでも積分画像の利用により処理が容易になる）。キーポイントの周囲にサイズ20sX20sの近傍を取る。ここでsはサイズである。それを4x4のサブ領域に分割する。各サブ領域について水平・垂直のウェーブレット応答を取り、\(v=( \sum{d_x}, \sum{d_y}, \sum{|d_x|}, \sum{|d_y|})\) のようにベクトルを形成する。これをベクトルとして表すと、合計64次元のSURF特徴記述子が得られる。次元が低いほど計算とマッチングの速度は高くなるが、より高い次元の方が特徴の識別性は優れる。

識別性をさらに高めるため、SURF特徴記述子には拡張された128次元版がある。\(d_x\) と \(|d_x|\) の和は \(d_y < 0\) と \(d_y \geq 0\) について別々に計算される。同様に、\(d_y\) と \(|d_y|\) の和は \(d_x\) の符号に従って分割され、それにより特徴の数が倍になる。これは計算量をあまり増やさない。OpenCVはフラグ extended の値を64次元には0、128次元には1に設定することで両方をサポートする（デフォルトは128次元）。

もう一つの重要な改良点は、対象とする関心点に対してラプラシアンの符号（ヘッセ行列のトレース）を用いることである。これは検出時にすでに計算されているため、計算コストを追加しない。ラプラシアンの符号は、暗い背景上の明るいブロブとその逆の状況を区別する。マッチング段階では、同じ種類のコントラストを持つ特徴のみを比較する（下図参照）。このわずかな情報により、記述子の性能を低下させることなくマッチングが高速化される。

image

要するに、SURFはすべてのステップで速度を改善するために多くの特徴を追加している。解析によれば、性能はSIFTに匹敵しながらSIFTより3倍高速である。SURFはぼけや回転を伴う画像の扱いに優れるが、視点変化や照明変化の扱いは得意でない。

OpenCVにおけるSURF

OpenCVはSIFTと同様にSURFの機能を提供する。64/128次元の記述子、Upright/Normal SURFなど、いくつかの省略可能な条件を指定してSURFオブジェクトを初期化する。すべての詳細はドキュメントで十分に説明されている。その後、SIFTで行ったのと同様に、キーポイントと記述子を求めるためにSURF.detect()、SURF.compute()などを使用できる。

まず、SURFのキーポイントと記述子を求めて描画する簡単なデモを見ていく。SIFTとほぼ同じであるため、すべての例はPythonターミナルで示す。

>>> img = cv.imread('fly.png', cv.IMREAD_GRAYSCALE)
 
# Create SURF object. You can specify params here or later.
# Here I set Hessian Threshold to 400
>>> surf = cv.xfeatures2d.SURF_create(400)
 
# Find keypoints and descriptors directly
>>> kp, des = surf.detectAndCompute(img,None)
 
>>> len(kp)
 699

1199個のキーポイントは画像に表示するには多すぎる。画像に描画するため50個程度に減らす。マッチングの際にはこれらすべての特徴が必要になるかもしれないが、今は不要である。そこでヘッセしきい値を上げる。

# Check present Hessian threshold
>>> print( surf.getHessianThreshold() )
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.setHessianThreshold(50000)
 
# Again compute keypoints and check its number.
>>> kp, des = surf.detectAndCompute(img,None)
 
>>> print( len(kp) )
47

50未満になった。これを画像に描画してみよう。

>>> img2 = cv.drawKeypoints(img,kp,None,(255,0,0),4)
 
>>> plt.imshow(img2),plt.show()

下の結果を見てほしい。SURFがどちらかというとブロブ検出器のように振る舞うのがわかる。蝶の羽の白いブロブを検出している。他の画像でも試してみるとよい。

image

次に、向きを求めないようにU-SURFを適用してみよう。

# Check upright flag, if it False, set it to True
>>> print( surf.getUpright() )
False
 
>>> surf.setUpright(True)
 
# Recompute the feature points and draw it
>>> kp = surf.detect(img,None)
>>> img2 = cv.drawKeypoints(img,kp,None,(255,0,0),4)
 
>>> plt.imshow(img2),plt.show()

下の結果を見てほしい。すべての向きが同じ方向に表示されている。以前より高速である。パノラマのつなぎ合わせなど、向きが問題にならない場合に取り組んでいるなら、こちらの方がよい。

image

最後に記述子のサイズを確認し、64次元のみであれば128次元に変更する。

# Find size of descriptor
>>> print( surf.descriptorSize() )
64
 
# That means flag, "extended" is False.
>>> surf.getExtended()
 False
 
# So we make it to True to get 128-dim descriptors.
>>> surf.setExtended(True)
>>> kp, des = surf.detectAndCompute(img,None)
>>> print( surf.descriptorSize() )
128
>>> print( des.shape )
(47, 128)

残りの部分はマッチングであり、これは別の章で扱う。