OpenCVのDescriptorMatcherの話 - 今日のごはんは素麺です

特徴量の検出（detect）と記述（compute）については割愛。これはその後の特徴量を比較するときに使うDescriptorMatcherについての話。

まずDescriptorMatcherの使い方

コードはScalaです。

import org.opencv.core.MatOfDMatch
import org.opencv.features2d.DescriptorMatcher

import scala.collection.mutable.ListBuffer
import scala.collection.JavaConverters._

val matcher = DescriptorMatcher.create(アルゴリズム)

val matches = ListBuffer[MatOfDMatch]()
matcher.結果の取得方法(queryDescriptors, trainDescriptors, matches.asJava, ~)

matches // この中にマッチングの結果

基本はこう。結果の取得方法によってシグネチャが違うが、大筋としては:

DescriptorMatcherのアルゴリズムを選択し
descriptorsを2つ渡してマッチングを行う

となる。

アルゴリズム

「どのようにマッチングを行うか」を指定する。大きく分けると:

総当たり法
FLANN

の2つに分けられる。

総当たり法

問い合わせる特徴量の集合（queryDescriptors）のひとつひとつが、訓練特徴量の集合（trainDescriptors）のどれにマッチングするかなんて、それぞれひとつひとつ地道に比較してみないと分かんないよね？

というわけで、それを実際に行うのが総当たり法。

さらに分けると:

BruteForce
BruteForce-SL2（ユークリッド2乗距離）
BruteForce-L1（マンハッタン距離）
BruteForce-Hamming/BruteForce-HammingLUT（ハミング距離）
BruteForce-Hamming(2)（ハミング距離……だと思う）

の5つに分けられます。定数ではBruteForce-Hamming(2)がなく、その代わりBruteForce-Hammingと同等のBruteForce-HammingLUTがあったりはしますが、その辺の事情はよく分かりません。

ユークリッド距離、マンハッタン距離、ハミング距離は適当にググってください。

FLANN

総当たりするとめっちゃ時間かかるから、マッチングする範囲を限定しない？

というわけで、そうするのがFLANN（高速近似近傍探索法）。

総当たり法と比べて以下の特徴がある。

速度は総当たり法のだいたい4〜6倍（自環境でパッと見た感じ）
範囲を限定しているので、本来マッチングしてほしい箇所同士がマッチしないこともある

使えるアルゴリズム

すべてのマッチングアルゴリズムがすべての特徴量に対して適用できるわけではない。使えるものと使えないものがあり、以下のようになる。

総当たり法（BruteForce, BruteForce-SL2, BruteForce-L1）: 何にでも使える
総当たり法（BruteForce-Hamming, BruteForce-Hamming(2)）: 特徴量の表現がバイナリコードのもの（ORB, AKAZEとか）
FLANN: 特徴量の表現が実数ベクトルのもの（SIFT, SURFとか）

使えないものの場合は実行時エラーが出るので分かるはず。

どのアルゴリズム使えば良いんだ！ってなると思うんですが、結局特徴量の表現によって使えるアルゴリズムが決まっているので、迷うこともあんまりない。迷ったらBruteForceで良いのかなと思う。最近の特徴量検出アルゴリズムによるものだとFLANN使えないこと多いしな！

結果の取得方法

アルゴリズムを決めたらいざマッチングで良いんですが、それの取得方法もいくつかあります。

knnMatch, radiusMatch

基本的に結果は「問い合わせる特徴量の個数 * 訓練特徴量の個数」の2次元配列になります。実際はマッチングしなかった場合結果として返されないので、それよりは少なくなります。

そして各マッチング結果には特徴量同士の距離が込められています。この距離が近ければ近いほど（数値的には小さいほど）その特徴量同士は似ていると言えます。

で、各問い合わせる特徴量ごとに距離が近い上位k個を取得するのが、knnMatchです（k-nearest neighbor）。上位k個とかではなく、距離が指定した閾値以下かどうかでフィルターをかけるのがradiusMatchです。この2つは問い合わせる各特徴量ごとに複数個の結果を持ち、その各特徴量ごとにMatOfDMatchを返すので、結果はList[MatOfDMatch]になります。複雑ですね。

import org.opencv.core.MatOfDMatch
import org.opencv.features2d.DescriptorMatcher

import scala.collection.mutable.ListBuffer
import scala.collection.JavaConverters._

val matcher = DescriptorMatcher.create(DescriptorMatcher.BRUTEFORCE)

val matches = new ListBuffer[MatOfDMatch]()
matcher.knnMatch(queryDescriptors, trainDescriptors, matches.asJava, 2)

これは各特徴量ごとに距離が近い上位2個を取得します。2個に満たない場合もあるので、それよりも少なくはなる可能性はあります。

radiusMatchについては割愛。knnMatchのように個数を指定する箇所に距離の閾値を指定するだけです。

match

じゃあ何も修飾していないmatchはどうなるかと言うと、各特徴量において最も距離の近い1点を結果とする、となります。結果としては「問い合わせる特徴量の個数 * 1」となるので、ただの配列になります。よってMatOfDMatchで表されます。こう見ると、matchの方が特殊な形で、knnMatch, radiusMatchの方がより一般形のようですね。

import org.opencv.core.MatOfDMatch
import org.opencv.features2d.DescriptorMatcher

val matcher = DescriptorMatcher.create(DescriptorMatcher.BRUTEFORCE)

val matches = new MatOfDMatch()
matcher.`match`(queryDescriptors, trainDescriptors, matches)

matches変数をprintlnなりすると、次元数が「問い合わせる特徴量の個数 * 1」になっているのが分かると思います。

マッチングの結果を描画する方法

マッチングの結果によってはその結果の描画方法も異なります。なぜなら結果がknnMatch, radiusMatchはList[MatOfDMatch]になるけど、matchはMatOfDMatchになり、型が異なるからです。

型を揃えても良いんですが、それぞれの型に描画する方法があるので、使い分けてあげれば大丈夫です。

// matchesの型がMatOfDMatchの場合
val result = new Mat()
Features2d.drawMatches(image1, keyPoints1, image2, keyPoints2, matches, result)

// matchesの型がList[MatOfDMatch]の場合
val result = new Mat()
Features2d.drawMatches2(image1, keyPoints1, image2, keyPoints2, matches, result)

drawMatchesかdrawMatches2の違いです。どうでもいいですけど、この命名の感じ、古臭さを感じますね。

実際は結果を描画せず、matchesの中身を見て類似しているか判定して終わることが多いと思いますが、一応。