.. _Matcher:


特徴点のマッチング
*********************************************

目的
=====
このチュートリアルでは
    * 二枚の画像の特徴点のマッチングについて学びます．
    * OpenCVが提供する総当たりマッチングとFLANNを使ったマッチングの使い方を学びます．
    

総当たりマッチングの基礎
===================================

総当たりマッチング(Brute-Force matcher)はシンプルです．最初の画像中のある特徴点の特徴量記述子を計算し，二枚目の画像中の全特徴点の特徴量と何かしらの距離計算に基づいてマッチングをします．最も距離が小さい特徴点が対応する特徴点がマッチング結果として返されます．

総当りマッチングでは，まず初めに **cv2.BFMatcher()** を使ってBFMatcher型のオブジェクトを生成します．この関数は2つのオプショナルパラメータがあります．1つ目のパラメータは ``normType`` です．このパラメータはマッチングコストの計算に使われる距離計算方法を指定します．デフォルトは ``cv2.NORM_L2`` となっています．SIFTやSURFといった特徴量記述子に向いています(``cv2.NORM_L1`` も同様です)．ORB, BRIEF, BRISKのようなバイナリベクタ(特徴ベクトルの各要素が2値となる特徴量記述子)については ``cv2.NORM_HAMMING`` を指定し，特徴ベクトル間のハミング距離を使うべきです．もしORBに対して ``VTA_K == 3 or 4`` と指定するのであれば， ``cv2.NORM_HAMMING2`` を使うべきです．

2つ目のパラメータはブール型変数の ``crossCheck`` で，デフォルト値はfalseに設定されています．trueに設定すると，マッチングのクロスチェックが行われ，クロスチェックが確立されたマッチング結果のみが返されます．クロスチェックとは，特徴点群Aの中のi番目の特徴ベクトルの最大マッチング結果が特徴点群Bの中のj番目の特徴ベクトルとなり，かつ特徴点群Bの中のj番目の特徴ベクトルの最大マッチング結果が特徴点群Aの中のi番目の特徴ベクトルとなるか確認することを意味します．両特徴点群の特徴点が互いにベストマッチとなるか確認するわけです．この確認の仕方は安定した結果を海，D. LoweのSIFTの論文で提案されたratio testの良い代替案となります．

BFMatcher型オブジェクトを一度作れば，それ以降重要なのは *BFMatcher.match()* と *BFMatcher.knnMatch()* になります．前者は各点に対して最も良いマッチングスコアを持つ対応点のみを返しますが，後者は上位 `k` 個の特徴点を返します．knnMatchはマッチング以降に追加で処理をする時に便利かもしれません．

検出した特徴点の描画に cv2.drawKeypoints() 関数を使ったように，マッチングの結果を描画するには **cv2.drawMatches()** を使います．この関数を使うと，マッチングを行った2枚の画像を横方向に連結し，対応点を線でつないだ可視化を行います． **cv2.drawMatchesKnn** という関数を使うと，上位k個の対応点を描画します．もし k=2 と設定すれば，各特徴点に対して2本のマッチング結果を示す直線を描画します．特定の検出点のみを描画するのでmaskを与える必要が有ります．

それでは，SURFとORBそれぞれの例を示します(それぞれ違う距離計算をします)．


ORBを使った総当りマッチング
--------------------------------------------

ここでは単純な例を使って2枚の画像の特徴点のマッチングの方法を学びます．今回のケースではクエリ画像と学習画像がそれぞれ1枚ずつあり，特徴点のマッチングによって学習画像の中からクエリ画像を見つけます(画像は ``/samples/c/box.png`` と ``/samples/c/box_in_scene.png`` を使います)．

特徴点のマッチングにはORBを使います．早速始めましょう．
::

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

    img1 = cv2.imread('box.png',0)          # queryImage
    img2 = cv2.imread('box_in_scene.png',0) # trainImage

    # Initiate ORB detector
    orb = cv2.ORB()

    # find the keypoints and descriptors with ORB
    kp1, des1 = orb.detectAndCompute(img1,None)
    kp2, des2 = orb.detectAndCompute(img2,None)


次にBFMatcher型のオブジェクトを作成します．その際，距離測定を ``cv2.NORM_HAMMING`` (ORBを使うから)とし， ``crossCheck`` をtrueに設定します．そして， Matcher.match()関数を使い2画像間の最も良いマッチング結果を取得します．マッチング結果を昇順にソートし最も良いマッチング結果(距離が低い)から順番に並ぶようにします．ここでは見やすさのために，マッチング結果のうち上位10個の対応点のみ描画しますが10にこだわらず好きなだけ描画して構いません．
::

    # create BFMatcher object
    bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)

    # Match descriptors.
    matches = bf.match(des1,des2)

    # Sort them in the order of their distance.
    matches = sorted(matches, key = lambda x:x.distance)

    # Draw first 10 matches.
    img3 = cv2.drawMatches(img1,kp1,img2,kp2,matches[:10], flags=2)

    plt.imshow(img3),plt.show()
    
以下に結果画像を示します:

    .. image:: images/matcher_result1.jpg
        :alt: ORB Feature Matching with Brute-Force
        :align: center
        

このMatcher型オブジェクトとは何か?
-----------------------------------------

 ``matches = bf.match(des1,des2)`` と書いてある行の結果はDMatch型オブジェクトのリストが返ってきます．このDMatch型オブジェクトとは以下のような属性を持っています:

    * ``DMatch.distance`` - 特徴量記述子間の距離．低いほど良い．
    * ``DMatch.trainIdx`` - 学習記述子(参照データ)中の記述子のインデックス．
    * ``DMatch.queryIdx`` - クエリ記述子(検索データ)中の記述子のインデックス．
    * ``DMatch.imgIdx``   - 学習画像のインデックス．
    
    
SIFTを使った総当りマッチングとratio test
-------------------------------------------------------------

今度は上位k個のマッチング結果を得るために ``BFMatcher.knnMatch()`` を使います．この例ではk=2とし，D. Loweが論文中で説明したratio testを行います．
::

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

    img1 = cv2.imread('box.png',0)          # queryImage
    img2 = cv2.imread('box_in_scene.png',0) # trainImage

    # Initiate SIFT detector
    sift = cv2.SIFT()

    # find the keypoints and descriptors with SIFT
    kp1, des1 = sift.detectAndCompute(img1,None)
    kp2, des2 = sift.detectAndCompute(img2,None)

    # BFMatcher with default params
    bf = cv2.BFMatcher()
    matches = bf.knnMatch(des1,des2, k=2)

    # Apply ratio test
    good = []
    for m,n in matches:
        if m.distance < 0.75*n.distance:
            good.append([m])

    # cv2.drawMatchesKnn expects list of lists as matches.
    img3 = cv2.drawMatchesKnn(img1,kp1,img2,kp2,good,flags=2)

    plt.imshow(img3),plt.show()

結果は以下のようになります:

    .. image:: images/matcher_result2.jpg
        :alt: SIFT Descriptor with ratio test
        :align: center
        

FLANNベースのマッチング
==========================

FLANNとはFast Library for Approximate Nearest Neighborsの略で，高速な近似最近傍探索を行うためのライブラリです．大規模データや高次元データに対する高速な最近傍探索のために最適化されたアルゴリズムを提供するライブラリです．大規模データに対してBFMatcherより高速に動作します．上記のSIFTを使ったマッチングにFLANNベースのマッチングを導入してみましょう．

FLANNベースのマッチングのために，使用する検索アルゴリズム及び関連するパラメータを指定するための2つのdictionary型オブジェクトを引数として指定する必要が有ります．一つ目のdictionaryはIndexParamsです．各種アルゴリズムの指定すべき情報はFLANNのドキュメントで説明されています．要約するとSIFTやSURFのようなアルゴリズムに対しては以下のような情報を与えます:
::
    
    index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)
    
一方でORBを使うのであれば，以下のような情報を与えます．コメントアウトされた値はドキュメントにて推奨されていた値ですが，状況次第では要求される結果に至らないこともあります．それ以外の値はうまくいきます:
::

    index_params= dict(algorithm = FLANN_INDEX_LSH,
                       table_number = 6, # 12
                       key_size = 12,     # 20
                       multi_probe_level = 1) #2    

2つ目のdictionaryはSearchParamsです．インデックス中の木構造を再帰的にたどっていく回数を指定します．高い値を設定するほどprecisionは向上しますが，より時間はかかってしまいます．値を変更するのであれば ``search_params = dict(checks=100)`` と指定してください． 

それではコードを見てみましょう．
::

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

    img1 = cv2.imread('box.png',0)          # queryImage
    img2 = cv2.imread('box_in_scene.png',0) # trainImage

    # Initiate SIFT detector
    sift = cv2.SIFT()

    # find the keypoints and descriptors with SIFT
    kp1, des1 = sift.detectAndCompute(img1,None)
    kp2, des2 = sift.detectAndCompute(img2,None)

    # FLANN parameters
    FLANN_INDEX_KDTREE = 0
    index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)
    search_params = dict(checks=50)   # or pass empty dictionary

    flann = cv2.FlannBasedMatcher(index_params,search_params)

    matches = flann.knnMatch(des1,des2,k=2)

    # Need to draw only good matches, so create a mask
    matchesMask = [[0,0] for i in xrange(len(matches))]

    # ratio test as per Lowe's paper
    for i,(m,n) in enumerate(matches):
        if m.distance < 0.7*n.distance:
            matchesMask[i]=[1,0]

    draw_params = dict(matchColor = (0,255,0),
                       singlePointColor = (255,0,0),
                       matchesMask = matchesMask,
                       flags = 0)       
                        
    img3 = cv2.drawMatchesKnn(img1,kp1,img2,kp2,matches,None,**draw_params)

    plt.imshow(img3,),plt.show()  


結果は以下のようになります:

    .. image:: images/matcher_flann.jpg
        :alt: FLANN based matching
        :align: center
        
                
補足資料
========================


課題
=================