ORB (Oriented FAST and Rotated BRIEF, 方向付きFASTと回転BRIEF)

目的

このチュートリアルでは
  • ORBの基礎を学ぶ

理論

OpenCVのファンとして、ORBについての最も重要なことはこれが“OpenCV Labs”から生まれたということである。このアルゴリズムはEthan Rublee, Vincent Rabaud, Kurt Konolige & Gary R. Bradskiにより2011年の論文ORB: An efficient alternative to SIFT or SURF (SIFTやSURFに変わる効率的な手法)で提案された。この題目が示すように、計算コスト、マッチング性能、特に特許の点においてSIFTやSURFに代わる良い手法である。そう、SIFTもSURFも特許が取られており、これらを使う場合には使用料を払わなければならない。しかし、ORBはそうではない!!!

ORBは基本的にFASTキーポイント検出器とBRIEF特徴記述子を融合させたもので、性能を向上させるために多くの修正が施されている。まずFASTを使用してキーポイントを検出し、次に Harrisコーナー尺度を用いてその候補から上位N個に絞りこむ。また画像ピラミッドを用いて多重スケールの特徴を生成する。ここでひとつ問題がある、それはFASTが向きを計算しないということである。回転に対する不変性はどうなるなのだろうか？提案者は次に述べる修正でこの問題に対処した。

コーナーを中央においた画像パッチに対し画素値で重み付けした重心を求める。このコーナー点から重心までのベクトルの方向が向きを与える。 rをパッチのサイズとすると、回転不変性を改善するために、半径 rの円形領域にあるx，y座標を用いてモーメントを計算する。

特徴点記述子に対しては、ORBは BRIEF特徴記述演算器を用いる。しかし前に見たようにBRIEFは回転に対してはとても性能が低い。そこで ORBが行っているのは、キーポイントの向きに応じて BRIEF を「操縦」することである。位置(x_i, y_i)にある n個の二値の試験の特徴集合に対し、これらのピクセルを要素に持つ2 \times n の行列 S を定義する。そしてこのパッチの向き\thetaを用いて回転行列を計算し、これによりSを回転させて、操縦後(回転後)の行列S_\thetaを得る。

ORBでは角度を 2 \pi /30 (12度)単位で離散化し、事前にBRIEFパタンの早見表を作っている。キーポイントの向き\thetaが見え方によらず一定であれば、ポイントの正しい集合 S_\theta が記述子の計算に用いられることになる。

BRIEFには、それぞれのビット特徴量が平均約0.5で大きな分散を持つという重要な性質がある。しかしキーポイントに沿って方向付けされると、平均値はより広がった分布をする。分散が大きいということは特徴量をより弁別的にするということである。なぜなら入力によっていろいろに応答することになるからである。もうひとつの望ましい性質は、この試験に無相関性をもたせるということである。なぜならそれぞれの試験はその結果に貢献するからである。これらを解決するために、ORB はすべての二値試験に対しグリーディー探索を用いて、無相関であり、かつ平均が0.5に近く大きな分散をもつ二値試験を計算する。その結果得られたものを rBRIEFという。

特徴記述子のマッチングについては、今までのLSH(局所性鋭敏型ハッシュ)を改良したマルチプローブ型LSH(注: ハッシュ値が1だけ異なるような項目もチェックする)を用いている。原論文で、ORBは SURF や SIFT よりもかなり高速であり、かつORBの記述子はSURFよりも性能がよいと書かれている。ORBは高機能ではない機器でパノラマ画像作成などをする場合に良い選択である。

OpenCVのORB

前と同様にORB オブジェクトを作らなければならないが、ここで用いるのはcv2.ORB_create([, nfeatures[, scaleFactor[, nlevels[, edgeThreshold[, firstLevel[, WTA_K[, scoreType[, patchSize[, fastThreshold]]]]]]]]]) 関数である。たくさんオプションのパラメタがある。そのうち最も役に立つのは、保持される特徴量の最大数を表す(デフォルトは500である) nFeatures、特徴量のランク付けのために用いるHarrisスコアとFASTスコアの選択(デフォルトはHarrisスコア)を表すscoreTypeである。この他に、回転BRIEF記述子を作り出すための特徴点の個数を指定する WTA_Kパラメタがある。このデフォルト値は2であり、これは一時に2個の点が選ばれることを意味する。この場合、マッチングには NORM_HAMMING 距離が用いられる。もしもWTA_K の値が 3 か 4であれば、 3 ないし 4 個の点を用いてBRIEF記述子が作られ、次にマッチング距離が NORM_HAMMING2で定義されることになる。

以下にORBの使用法を示すための簡単なコードをあげる。(コード, 画像)

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

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

# ORB検出器を作るr
orb = cv2.ORB_create()

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

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

# キーポイントの位置だけを描画、サイズと向きはやらない
img2 = cv2.drawKeypoints(img,kp,None,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.

課題