目標

本章では、

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 は特許で保護されており、使用にあたっては対価を支払う必要がある。しかし ORB はそうではない !!!

ORB は基本的に、FAST キーポイント検出器と BRIEF 記述子を融合させ、性能を高めるために多くの改良を加えたものである。まず FAST を使ってキーポイントを見つけ、次に Harris のコーナー尺度を適用してその中から上位 N 個の点を見つける。また、マルチスケールの特徴を生成するためにピラミッドも使用する。しかし1つ問題があり、FAST は方向を計算しない。では回転不変性はどうするのか? 著者たちは次のような改良を考え出した。

検出されたコーナーを中心としたパッチについて、強度で重み付けした重心を計算する。このコーナー点から重心へ向かうベクトルの方向が方向を与える。回転不変性を高めるために、モーメントは半径 \(r\) の円形領域内にあるべき x と y で計算される。ここで \(r\) はパッチのサイズである。

次に記述子についてだが、ORB は BRIEF 記述子を使用する。しかし BRIEF が回転に対して弱いことはすでに見た通りである。そこで ORB が行うのは、キーポイントの方向に応じて BRIEF を「操舵 (steer)」することである。位置 \((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付近になるという重要な性質がある。しかしいったんキーポイントの方向に沿って向きを揃えると、この性質を失い、より分散した状態になる。分散が大きいほど特徴はより識別力を持つ。なぜなら入力に対して差を持って応答するからである。もう1つの望ましい性質は、テスト同士が無相関であることである。そうすれば各テストが結果に寄与するからである。これらすべてを解決するため、ORB はあり得るすべての二値テストの中から、大きな分散と0.5に近い平均の両方を持ち、かつ無相関であるものを見つけるための貪欲探索を実行する。その結果は rBRIEF と呼ばれる。

記述子マッチングには、従来のLSHを改良したマルチプローブLSHを用いる。論文によれば、ORBはSURFやSIFTよりも非常に高速であり、ORB記述子はSURFより良好に動作する。ORBはパノラマスティッチングなどの用途で低消費電力デバイスに適した選択肢である。

OpenCVにおけるORB

いつものように、関数 cv.ORB() を使うか、特徴量の共通インターフェースを使ってORBオブジェクトを作成する必要がある。これには多くの省略可能なパラメータがある。最も有用なものは、保持する特徴量の最大数を表す nFeatures（デフォルトは500）、特徴量をランク付けする際にHarrisスコアとFASTスコアのどちらを用いるかを表す scoreType（デフォルトはHarrisスコア）などである。別のパラメータ WTA_K は、oriented BRIEF記述子の各要素を生成する点の数を決める。デフォルトでは2、すなわち一度に2点を選ぶ。この場合、マッチングには NORM_HAMMING 距離が使われる。WTA_K が3または4の場合、BRIEF記述子を生成するのに3点または4点を取り、マッチング距離は NORM_HAMMING2 で定義される。

以下はORBの使用法を示す簡単なコードである。

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt
 
img = cv.imread('simple.jpg', cv.IMREAD_GRAYSCALE)
 
# Initiate ORB detector
orb = cv.ORB_create()
 
# 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 = cv.drawKeypoints(img, kp, None, color=(0,255,0), flags=0)
plt.imshow(img2), plt.show()

以下の結果を参照のこと。

image

ORBの特徴マッチングについては、別の章で扱う。

追加リソース

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