目的

このチュートリアルでは、以下の方法を学ぶ:

多次元空間でのクラスタリングと探索モジュールを使って高速かつ効率的なマッチングを行うために、cv::FlannBasedMatcher インターフェースを使用する

警告: SURF特徴を使用するには OpenCV contribモジュールが必要である(代替としてORB、KAZEなどの特徴がある)。

理論

古典的な特徴記述子(SIFT, SURF, ...)は通常、ユークリッド距離(またはL2ノルム)を用いて比較・マッチングされる。SIFTやSURFの記述子は近傍における勾配方向(SURFの場合はHaarウェーブレット応答)のヒストグラムを表すため、ユークリッド距離の代替としてヒストグラムベースの距離尺度( \( \chi^{2} \), Earth Mover’s Distance (EMD), ...)がある。

Arandjelovicらは [15] においてRootSIFT記述子への拡張を提案した:

‍SIFT記述子間の類似度を測るために標準的なユークリッド距離の代わりに平方根(Hellinger)カーネルを用いると、パイプラインの全段階で性能が劇的に向上する。

バイナリ記述子(ORB, BRISK, ...)はハミング距離を用いてマッチングされる。この距離はバイナリ文字列について異なる要素の数を数えること(XOR演算を適用した後のpopulation count)に等しい:

\[ d_{hamming} \left ( a,b \right ) = \sum_{i=0}^{n-1} \left ( a_i \oplus b_i \right ) \]

マッチをフィルタリングするため、Loweは [179] において誤マッチを除去するための距離比テストの使用を提案した。対象とするキーポイントの最も近い2つのマッチ間の距離比を計算し、この値がしきい値を下回るときに良いマッチとする。実際、この比は曖昧なマッチ(最近傍2つの間の距離比が1に近い)と良好に識別されたマッチとを区別するのに役立つ。下図はSIFTの論文からのもので、最近傍距離比テストに基づいてマッチが正しい確率を示している。

代替または追加のフィルタリングテストには次のものがある:

クロスチェックテスト(特徴 \( f_b \) が \( I_b \) 内で \( f_a \) に対する最良のマッチであり、かつ特徴 \( f_a \) が \( I_a \) 内で \( f_b \) に対する最良のマッチであるとき、 \( \left( f_a, f_b \right) \) を良いマッチとする)
幾何学的テスト(幾何モデルに適合しないマッチを除去する。例えばRANSACや平面物体に対するロバストなホモグラフィ)

コード

このチュートリアルのコードを以下に示す。こちらからダウンロードすることもできる

#include <iostream>
#include "opencv2/core.hpp"
#ifdef HAVE_OPENCV_XFEATURES2D
#include "opencv2/highgui.hpp"
#include "opencv2/features2d.hpp"
#include "opencv2/xfeatures2d.hpp"
 
using namespace cv;
using namespace cv::xfeatures2d;
using std::cout;
using std::endl;
 
const char* keys =
 "{ help h |                  | Print help message. }"
 "{ input1 | box.png          | Path to input image 1. }"
 "{ input2 | box_in_scene.png | Path to input image 2. }";
 
int main( int argc, char* argv[] )
{
 CommandLineParser parser( argc, argv, keys );
 Mat img1 = imread( samples::findFile( parser.get<String>("input1") ), IMREAD_GRAYSCALE );
 Mat img2 = imread( samples::findFile( parser.get<String>("input2") ), IMREAD_GRAYSCALE );
 if ( img1.empty() || img2.empty() )
    {
        cout << "Could not open or find the image!\n" << endl;
        parser.printMessage();
 return -1;
    }
 
 //-- Step 1: Detect the keypoints using SURF Detector, compute the descriptors
 int minHessian = 400;
 Ptr<SURF> detector = SURF::create( minHessian );
    std::vector<KeyPoint> keypoints1, keypoints2;
 Mat descriptors1, descriptors2;
    detector->detectAndCompute( img1, noArray(), keypoints1, descriptors1 );
    detector->detectAndCompute( img2, noArray(), keypoints2, descriptors2 );
 
 //-- Step 2: Matching descriptor vectors with a FLANN based matcher
 // Since SURF is a floating-point descriptor NORM_L2 is used
 Ptr<DescriptorMatcher> matcher = DescriptorMatcher::create(DescriptorMatcher::FLANNBASED);
    std::vector< std::vector<DMatch> > knn_matches;
    matcher->knnMatch( descriptors1, descriptors2, knn_matches, 2 );
 
 //-- Filter matches using the Lowe's ratio test
 const float ratio_thresh = 0.7f;
    std::vector<DMatch> good_matches;
 for (size_t i = 0; i < knn_matches.size(); i++)
    {
 if (knn_matches[i][0].distance < ratio_thresh * knn_matches[i][1].distance)
        {
            good_matches.push_back(knn_matches[i][0]);
        }
    }
 
 //-- Draw matches
 Mat img_matches;
    drawMatches( img1, keypoints1, img2, keypoints2, good_matches, img_matches, Scalar::all(-1),
                 Scalar::all(-1), std::vector<char>(), DrawMatchesFlags::NOT_DRAW_SINGLE_POINTS );
 
 //-- Show detected matches
    imshow("Good Matches", img_matches );
 
    waitKey();
 return 0;
}
#else
int main()
{
    std::cout << "This tutorial code needs the xfeatures2d contrib module to be run." << std::endl;
 return 0;
}
#endif

このチュートリアルのコードを以下に示す。こちらからダウンロードすることもできる

import java.util.ArrayList;
import java.util.List;
 
import org.opencv.core.Core;
import org.opencv.core.DMatch;
import org.opencv.core.Mat;
import org.opencv.core.MatOfByte;
import org.opencv.core.MatOfDMatch;
import org.opencv.core.MatOfKeyPoint;
import org.opencv.core.Scalar;
import org.opencv.features2d.DescriptorMatcher;
import org.opencv.features2d.Features2d;
import org.opencv.highgui.HighGui;
import org.opencv.imgcodecs.Imgcodecs;
import org.opencv.xfeatures2d.SURF;
 
class SURFFLANNMatching {
 public void run(String[] args) {
        String filename1 = args.length > 1 ? args[0] : "../data/box.png";
        String filename2 = args.length > 1 ? args[1] : "../data/box_in_scene.png";
        Mat img1 = Imgcodecs.imread(filename1, Imgcodecs.IMREAD_GRAYSCALE);
        Mat img2 = Imgcodecs.imread(filename2, Imgcodecs.IMREAD_GRAYSCALE);
 if (img1.empty() || img2.empty()) {
            System.err.println("Cannot read images!");
            System.exit(0);
        }
 
 //-- Step 1: Detect the keypoints using SURF Detector, compute the descriptors
 double hessianThreshold = 400;
 int nOctaves = 4, nOctaveLayers = 3;
 boolean extended = false, upright = false;
        SURF detector = SURF.create(hessianThreshold, nOctaves, nOctaveLayers, extended, upright);
        MatOfKeyPoint keypoints1 = new MatOfKeyPoint(), keypoints2 = new MatOfKeyPoint();
        Mat descriptors1 = new Mat(), descriptors2 = new Mat();
        detector.detectAndCompute(img1, new Mat(), keypoints1, descriptors1);
        detector.detectAndCompute(img2, new Mat(), keypoints2, descriptors2);
 
 //-- Step 2: Matching descriptor vectors with a FLANN based matcher
 // Since SURF is a floating-point descriptor NORM_L2 is used
        DescriptorMatcher matcher = DescriptorMatcher.create(DescriptorMatcher.FLANNBASED);
        List<MatOfDMatch> knnMatches = new ArrayList<>();
        matcher.knnMatch(descriptors1, descriptors2, knnMatches, 2);
 
 //-- Filter matches using the Lowe's ratio test
 float ratioThresh = 0.7f;
        List<DMatch> listOfGoodMatches = new ArrayList<>();
 for (int i = 0; i < knnMatches.size(); i++) {
 if (knnMatches.get(i).rows() > 1) {
                DMatch[] matches = knnMatches.get(i).toArray();
 if (matches[0].distance < ratioThresh * matches[1].distance) {
                    listOfGoodMatches.add(matches[0]);
                }
            }
        }
        MatOfDMatch goodMatches = new MatOfDMatch();
        goodMatches.fromList(listOfGoodMatches);
 
 //-- Draw matches
        Mat imgMatches = new Mat();
        Features2d.drawMatches(img1, keypoints1, img2, keypoints2, goodMatches, imgMatches, Scalar.all(-1),
 Scalar.all(-1), new MatOfByte(), Features2d.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS);
 
 //-- Show detected matches
        HighGui.imshow("Good Matches", imgMatches);
        HighGui.waitKey(0);
 
        System.exit(0);
    }
}
 
public class SURFFLANNMatchingDemo {
 public static void main(String[] args) {
 // Load the native OpenCV library
        System.loadLibrary(Core.NATIVE_LIBRARY_NAME);
 
 new SURFFLANNMatching().run(args);
    }
}

このチュートリアルのコードを以下に示す。こちらからダウンロードすることもできる

from __future__ import print_function
import cv2 as cv
import numpy as np
import argparse
 
parser = argparse.ArgumentParser(description='Code for Feature Matching with FLANN tutorial.')
parser.add_argument('--input1', help='Path to input image 1.', default='box.png')
parser.add_argument('--input2', help='Path to input image 2.', default='box_in_scene.png')
args = parser.parse_args()
 
img1 = cv.imread(cv.samples.findFile(args.input1), cv.IMREAD_GRAYSCALE)
img2 = cv.imread(cv.samples.findFile(args.input2), cv.IMREAD_GRAYSCALE)
if img1 is None or img2 is None:
    print('Could not open or find the images!')
    exit(0)
 
#-- Step 1: Detect the keypoints using SURF Detector, compute the descriptors
minHessian = 400
detector = cv.xfeatures2d_SURF.create(hessianThreshold=minHessian)
keypoints1, descriptors1 = detector.detectAndCompute(img1, None)
keypoints2, descriptors2 = detector.detectAndCompute(img2, None)
 
#-- Step 2: Matching descriptor vectors with a FLANN based matcher
# Since SURF is a floating-point descriptor NORM_L2 is used
matcher = cv.DescriptorMatcher_create(cv.DescriptorMatcher_FLANNBASED)
knn_matches = matcher.knnMatch(descriptors1, descriptors2, 2)
 
#-- Filter matches using the Lowe's ratio test
ratio_thresh = 0.7
good_matches = []
for m,n in knn_matches:
 if m.distance < ratio_thresh * n.distance:
        good_matches.append(m)
 
#-- Draw matches
img_matches = np.empty((max(img1.shape[0], img2.shape[0]), img1.shape[1]+img2.shape[1], 3), dtype=np.uint8)
cv.drawMatches(img1, keypoints1, img2, keypoints2, good_matches, img_matches, flags=cv.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS)
 
#-- Show detected matches
cv.imshow('Good Matches', img_matches)
 
cv.waitKey()

解説

結果

距離比テストを用いたSURF特徴マッチングの結果を以下に示す:


原著者	Ana Huamán
互換性	OpenCV >= 3.0

目次

目的

理論

コード

解説

結果