ORB (Oriented FAST and Rotated BRIEF)

目的

このチュートリアルでは
  • ORBについて学びます．

理論

OpenCVフリークにとってORBについて一番重要なことはORBがOpenCV Labsが生み出したという点です．ORBはEthan Rublee, Vincent Rabaud, Kurt Konolige，Gary R. Bradskiが2011年に発表した論文 ORB: An efficient alternative to SIFT or SURF で提案されました．論文のタイトルに書いてあるように，計算コスト，マッチング精度，特許を考慮するとSIFTとSURFの良い代替と言えます．SIFTとSURFは特許使用料を支払う必要はありますが，ORBは違います．

ORBは基本的にFASTによる特徴点検出とBRIEFによる特徴量記述子を組合わせたものです．まず始めにFASTによって特徴点を検出し，Harrisのコーナー評価により上位N点を選びます．また，マルチスケールの特徴を得るため，ピラミッドを使います．一点気を付けなければいけないのはFASTは特徴点の回転角を計算しないため，論文では以下の改良を加えます．

中心にコーナーが位置するパッチに対して，画素値で重み付けした重心を計算します．このコーナーから重心に向かうベクトルを回転角とします．回転不変性を改善するために，半径　r の円内のモーメントを計算します．

特徴ベクトルの計算はBRIEFを使います．位置　(x_i, y_i) における n 個のバイナリテストの結果から，これらの画素の座標情報を含む 2 \times n の行列 S を定義します．パッチの回転角:math:theta を使い回転行列を計算し，行列　S を回転させた　S_\theta を求めます．

ORBは角度を 2 \pi /30 刻みで量子化し，BRIEFのパターンをあらかじめルックアップテーブルに保存しておきます．特徴点の回転角 \theta が視点間で一貫性があれば，正しい点の集合 S_\theta を使って特徴ベクトルを計算します．

BRIEFは各bitが表す特徴が大きな分散を持ち，平均は0.５程度になるという重要な特徴を持っています．しかし，特徴点の方向に対して回転するとこの性質は失われ，特徴が更に分散してしまいます．分散が大きければ特徴の識別可能性は高くなります．もう一つの望ましい性質として各テストが無相関である点が挙げられます．これらを解決するため，ORBは全てのバイナリテストに対して貪欲探索(greedy search)を行い，高い分散となり平均が平均が0.5程度になるように，また無相関になるようにします．これを rBRIEF と呼びます．

特徴ベクトルのマッチングでは，従来のLSHを改良したmulti-probe LSHを使います．論文ではORBはSIFTやSURFよりだいぶ高速に動作し，SURFより精度が良いと書かれています．以上より，ORBは非力な装置に搭載する特徴量記述子として良い選択肢になりえます．

OpenCVでのORB

他の特徴量記述子同様， cv2.ORB() 関数，もしくはfeature2dの共通インタフェースを使いORBオブジェクトを作成します．幾つかのオプションパラメーターがあります． nFeatures は検出する最大特徴点数(デフォルトは500)， scoreType は特徴点のランク付けに使う評価値をHarrisスコアにするかFASTスコアにするか指定します(デフォルトはHarrisスコア)．他に重要なパラメータは WTA_K で，oriented BRIEFの各要素を計算するために使う点の数(デフォルトでは2)を指定できます．WTA_Kが3もしくは4の時，BRIEFの要素の計算に3,4点使用するため，マッチングの際の距離は NORM_HAMMING2 になります．

以下のORBの検出例のコードを示します．

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

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

# Initiate STAR detector
orb = cv2.ORB()

# find the keypoints with ORB
kp = orb.detect(img,None)

# compute the descriptors with ORB
kp, des = orb.compute(img, kp)

# draw only keypoints location,not size and orientation
img2 = cv2.drawKeypoints(img,kp,color=(0,255,0), flags=0)
plt.imshow(img2),plt.show()

以下に結果を示します:

ORB Keypoints

ORBの特徴マッチングについては，別のチュートリアルで扱います．

補足資料

  1. Ethan Rublee, Vincent Rabaud, Kurt Konolige, Gary R. Bradski: ORB: An efficient alternative to SIFT or SURF. ICCV 2011: 2564-2571.

演習