OpenCV 3とPython 3で特徴量マッチング（A-KAZE, KNN）

# OpenCVで特徴量マッチング
特徴量マッチングとは、異なる画像でそれぞれ抽出した特徴量の対応付けのことです。

+ パノラマ画像の作成
+ 物体検知
+ 動体追跡

で登場する技術です。

OpenCVには、以下のライブラリが用意されています。

+ 特徴量抽出
+ 特徴量マッチング
+ マッチング結果の表示

今回は、OpenCV 3 + Python 3 を使って、下記のような、回転、ズームした画像の特徴量マッチングをしてみます。

![match_thumbnail.jpg](https://qiita-image-store.s3.amazonaws.com/0/107056/39fb126e-40d0-13f2-e228-4f22f6c84aaf.jpeg)
　　　　　　　　**マッチング結果を描画**

# OpenCVとは
OpenCV(Open Source Computer Vision Library)はBSDライセンスの映像/画像処理ライブラリ集です。画像のフィルタ処理、テンプレートマッチング、物体認識、映像解析、機械学習などのアルゴリズムが多数用意されています。

■ OpenCVを使った動体追跡の例 (OpenCV Google Summer of Code 2015)
[https://www.youtube.com/watch?v=OUbUFn71S4s](https://www.youtube.com/watch?v=OUbUFn71S4s)

■ インストールと簡単な使い方はこちら
[OpenCV 3（core + contrib）をPython 3の環境にインストール＆OpenCV 2とOpenCV 3の違い＆簡単な動作チェック](http://qiita.com/olympic2020/items/d5d475a446ec9c73261e)  

■ 静止画像の処理についてはこちら
[OpenCVでエッジ検出してみる](http://qiita.com/olympic2020/items/2c3a2bfefe73ab5c86a4)
[OpenCVで各種フィルター処理をする（グラディエント、ハイパス、ラプラシアン、ガウシアン）](http://qiita.com/olympic2020/items/93e01ef22e46b14a60a9)
[OpenCVで特徴点を抽出する（AgastFeature, FAST, GFTT, MSER, AKAZE, BRISK, KAZE, ORB, SimpleBlob）](http://qiita.com/olympic2020/items/62989573a30ec1d8180b)
[OpenCVを使った顔認識（Haar-like特徴分類器）](http://qiita.com/olympic2020/items/04b1b26c1bc2e8081427)
[OpenCVを使って誰の顔なのかを推定する（Eigenface, Fisherface, LBPH）](http://qiita.com/olympic2020/items/8f2f37646179aca68649)
[OpenCVで形状のある物体の輪郭と方向を認識する（主成分分析：PCA、固有ベクトル）](http://qiita.com/olympic2020/items/92fc43226ca37c0f90f6)

■ 動画の処理についてはこちら
[OpenCVで動画をリアルタイムに変換してみる](http://qiita.com/olympic2020/items/ce00fab38d829965db3b)
[OpenCVでWebカメラ/ビデオカメラの動画をリアルタイムに変換してみる](http://qiita.com/olympic2020/items/12a2eceaf65f142ec3df)
[OpenCVでオプティカルフローをリアルタイムに描画する（Shi-Tomasi法、Lucas-Kanade法）](http://qiita.com/olympic2020/items/772549d0fc3c89fb3cc4)
[OpenCVを使った物体追跡（マウスで指定した特徴点をLucas-Kanade法で追跡する](http://qiita.com/olympic2020/items/3d8973f855e963c9d999)
[OpenCVを使ったモーション テンプレート解析（リアルタイムに物体とその動く方向を認識する）](http://qiita.com/olympic2020/items/a4ecf7babdbe710208ae)


# A-KAZE
+ ホームページ  
    　http://www.robesafe.com/personal/pablo.alcantarilla/kaze.html  
    　  
+ ライセンス  
    　https://github.com/pablofdezalc/akaze/blob/master/LICENSE  
    　  
+ 特徴  
    　OpenCV 3では、特許で保護されている SIFT (Scale-invariant feature transform)、SURF (Speed-Upped Robust Feature) はcontribライブラリに移動になり、ライセンス的に利用しやすい KAZE, A-KAZE がcoreライブラリに含まれるようになりました。A-KAZE(ACCELERATED-KAZE)は、KAZEを高速に改良したアルゴリズムです。  
    　KAZE, A-KAZEは、SIFTやSURFと同様に、拡大縮小・回転・照明変化に強いロバストな特徴量抽出アルゴリズムです。SIFTやSURFは、ガウスフィルターを用いるアルゴリズムのため、フラットな部分の特徴量抽出に弱いですが、KAZE, A-KAZEはフラットな部分からも特徴量を抽出します。  
    　  
+ ORBとA-KAZEの比較  
    　SIFT, SURF同様に拡大縮小・回転にロバストでありながら、高速（SURFの10倍、SIFTの100倍）であるORB（Oriented-BRIEF）と同様の追跡性能をもっています。  
    　  
    　**ORB vs A-KAZE[（youtubeリンク）](https://www.youtube.com/watch?v=LWY-w8AGGhE)**  
    　　A-KAZEはORBよりもフラットな部分の特徴量もよく追跡しているようです。

# KNN、Brute-Force、FLANN
　KNN（K-Nearest Neighbor algorithm）は、探索空間から最近傍のラベルをK個選択し、多数決でクラスラベルを割り当てるアルゴリズムです。
　学習は、トレーニングデータをそのまま記憶するだけです。学習コストがゼロなため、高速に動作します。怠惰学習アルゴリズムの代表選手です。
　探索空間から最近傍のラベルをK個探索する方法として、OpenCVは、総当たり法（Brute-Force）と高速近似近傍探索法（FLANN）をサポートしています。  

+ 総当たり法（Brute-Force）  
    　全探索空間を探索する総当たり探索のため時間がかかりますが、確実に最近傍の特徴量を検索することができます。
+ 高速近似近傍探索法（FLANN: Fast Library for Approximate Nearest Neighbors）
    　探索対象の特徴点と近い空間のみを検索します。探索空間が減るので高速に検索することができます。ただし、探索のパラメータに誤ったものを指定してしまうと、探索空間の選択を誤ってしまい、最近傍の特徴点が含まれていない探索空間だけを検索して終わってしまう状況が発生してしまいます。
    　  
### ● 備考（Python3とFLANN）
    　以前、OpenCV 3では、動作しないチュートリアルがあることを書きました（[リンク](http://qiita.com/olympic2020/items/d5d475a446ec9c73261e)）が、FLANNの特徴点マッチングは、私の環境（OpenCV 3.1.0 ＋ Python 3.5.2 + Windows 10）では動作しませんでした。
        
        > matches = flann.knnMatch(des1,des2,k=2)
        > 
        > \# 以下のエラー発生
        > \# error: C:\dev\opencv-3.1.0\modules\python\src2\cv2.cpp:163: error: (-215) The data should normally be NULL! in function NumpyAllocator::allocate
        
    　FLANNは、C++やOpenCV2では問題なく動作しているいるので、FLANNを利用したい場合は、C++または、OpenCV2の環境で実行します。OpenCV 3とPython 3の組み合わせで動かす場合は、現状は「総当たり法（Brute-Force）」を利用します。

# プログラム
+ 動作環境
    - OpenCV 3.1.0
    - Python 3.5.2
+ サンプル画像  
    　別々に撮影した画像を準備しました（img1.jpg, img2.jpg）。  
    　画像は、回転、ズームが入っています。  

```knn.py
# -*- coding: utf-8 -*-
import cv2

# 画像１
img1 = cv2.imread("img1.jpg")
# 画像２
img2 = cv2.imread("img2.jpg")

# A-KAZE検出器の生成
akaze = cv2.AKAZE_create()                                

# 特徴量の検出と特徴量ベクトルの計算
kp1, des1 = akaze.detectAndCompute(img1, None)
kp2, des2 = akaze.detectAndCompute(img2, None)

# Brute-Force Matcher生成
bf = cv2.BFMatcher()

# 特徴量ベクトル同士をBrute-Force＆KNNでマッチング
matches = bf.knnMatch(des1, des2, k=2)

# データを間引きする
ratio = 0.5
good = []
for m, n in matches:
    if m.distance < ratio * n.distance:
        good.append([m])

# 対応する特徴点同士を描画
img3 = cv2.drawMatchesKnn(img1, kp1, img2, kp2, good[], None, flags=2)

# 画像表示
cv2.imshow('img', img3)

# キー押下で終了
cv2.waitKey(0)
cv2.destroyAllWindows()
```

# マッチング結果
D.Loweが提唱したRatio Testで、マッチング結果を間引いて表示します。

```lowe.py
# データを間引きする
ratio = 0.5
lowe = []
for m, n in matches:
    if m.distance < ratio * n.distance:
        lowe.append([m])

# 対応する特徴点同士を描画
img3 = cv2.drawMatchesKnn(img1, kp1, img2, kp2, lowe[], None, flags=2)
```

この方法は、画像全体のマッチング状況を視覚的に把握することができます。
このテストでは、誤検知はないようです。

![match_result.png](https://qiita-image-store.s3.amazonaws.com/0/107056/5ac0cd05-8d9a-05ff-f3f0-673ba630bd8f.png)

特徴量同士のマッチング状況が良好なもののみ表示するようにコードを一部変更してみます。

```knn_good.py
# 特徴量をマッチング状況に応じてソートする
good = sorted(matches, key = lambda x : x[1].distance)

# 対応する特徴点同士を描画
img3 = cv2.drawMatchesKnn(img1, kp1, img2, kp2, good[:30], None, flags=2)
```

![match_good.png](https://qiita-image-store.s3.amazonaws.com/0/107056/92e9f2ca-61e3-d3b4-e37d-58da267329de.png)

先ほどとは別の特徴量が描画されました。
今回は、特徴量が分散しているため、全体的にマッチしていますが、特徴点が一部に偏っている画像の場合は、そこにマッチング状況が良好なものが集中することになります。


# KeyPoint（特徴点オブジェクト）

|属性|内容|
|:-----|:----------|
|pt|ポイント（x, y）|
|size|特徴点の直径|
|angle|[0, 360) の範囲の角度。y軸が下方向で右回り。計算不能な場合は-1。|
|response|特徴点の強度|
|octave|特徴点を検出したピラミッドレイヤー|
|class_id|特徴点が属するクラスのID|

# DMatch（マッチング結果オブジェクト）

特徴量同士のマッチング結果、DMatchには次の項目が格納されています。

|属性|内容|
|:-----|:----------|
|distance|特徴量同士の距離。距離が近いほうがよくマッチしている。|
|trainIdx|トレーニング特徴量のインデックス|
|queryIdx|クエリー特徴量のインデックス|
|imgIdx|トレーニング画像のインデックス|