いろいろな画像を見比べて、「あの画像に写ってるのアレは、この画像に写ってるコレと同じかな？」なんてことを、機械的にやるとしたら、という話。

OpenCVに頼る

難しいことは考えないで、OpenCVに頼る。自分で考えるよりも、世界中の賢い人々が考えてくれた成果物を利用するべきなのだ。

というわけで、早速、 OpenCV: Feature Detection and Descriptionを参照して、お勉強を始める。

画像を用意する

適当な著作権フリーっぽい画像もないし、自分で撮影するのも面倒なので、今回は以下の画像を適当に作った。

このutsu1.png(游明朝)と、utsu2.png(ヒラギノ角ゴシック)を使うことにする。

特徴点の抽出

まずは、http://docs.opencv.org/master/da/df5/tutorial_py_sift_intro.html に従い、utsu1.pngを走査してSIFT特徴量を重畳表示する。

img1 = cv2.imread('img/utsu1.png')
gray1 = cv2.cvtColor(img1, cv2.COLOR_BGR2GRAY)
sift = cv2.xfeatures2d.SIFT_create()
kp1 = sift.detect(gray1)
img1_sift = cv2.drawKeypoints(gray1, kp1, None, flags=4)

グレー画像に変換(gray1 = cv2.cvtColor(img1, cv2.COLOR_BGR2GRAY))してから、SIFT特徴量を抽出する(sift.detect(gray1))。

すると、こんな感じ。

抽出した特徴量を可視化して表示するために、cv2.drawKeypoints()しているのだが、drawKeypoints()のflagsという引数は、ドキュメントによるとenum型で以下のように定義されている。

enum  	{ 
  cv::DrawMatchesFlags::DEFAULT = 0, 
  cv::DrawMatchesFlags::DRAW_OVER_OUTIMG = 1, 
  cv::DrawMatchesFlags::NOT_DRAW_SINGLE_POINTS = 2, 
  cv::DrawMatchesFlags::DRAW_RICH_KEYPOINTS = 4 
}

今回は、4にしたのでDRAW_RICH_KEYPOINTSということで、keypointごとのresponse(特徴点の特徴強度...とでもいうのかな)に合わせた円の半径で画像化されている。

さて、特徴点（特徴量）とは何か？というのは、実に説明が難しい。なぜなら、理解していないからだ。この画像を見ると、なんとなく雰囲気で、「ああ、この払いは特徴的だね、真ん中のぐじゃぐじゃっとしている周辺もこの画像の中では重要なポイントなんだね」って感じだ。
ただ、「信号量が大きく変わるところ」だと単なる輪郭抽出になってしまうワケで、そうではなくて形状とかも考慮されていることは、この画像を見るとよく分かる。

ところで、SIFTという手法は特許が取られているらしいので、とりあえずAKAZE法で同じように書いてみる。

AKAZE

img1 = cv2.imread('img/utsu1.png')
gray1 = cv2.cvtColor(img1, cv2.COLOR_BGR2GRAY)
akaze = cv2.AKAZE_create()
kp1 = akaze.detect(gray1)
img1_akaze = cv2.drawKeypoints(gray1, kp1, None, flags=4)

これによって選ばれるkeypointsは、SIFTとは違うんだけれど、それも踏まえてdetectorとして何を選ぶべきなのか？っていうのは、正直言うとよく分からない。

このように、特徴量を抽出するためのエンジンが変わると、選択される特徴点やその特徴量の大きさも変わるということがよく分かった。

特徴点の比較

これは、http://docs.opencv.org/master/dc/dc3/tutorial_py_matcher.html からコピペに限る。

img1 = cv2.imread('img/utsu1.png')
img2 = cv2.imread('img/utsu2.png')
gray1 = cv2.cvtColor(img1, cv2.COLOR_BGR2GRAY)
gray2 = cv2.cvtColor(img2, cv2.COLOR_BGR2GRAY)
akaze = cv2.AKAZE_create()
kp1, des1 = akaze.detectAndCompute(gray1, None)
kp2, des2 = akaze.detectAndCompute(gray2, None)

bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)
matches = bf.match(des1, des2)
matches = sorted(matches, key = lambda x:x.distance)
img3 = cv2.drawMatches(img1, kp1, img2, kp2, matches[:10], None, flags=2)

コピペしつつ、ORBではなくAKAZEを使うように変更したのと、cv2.drawMatches()の引数がチュートリアルに書いてあるものと微妙に違っているので修正してみた。

ちなみに、結果は以下のようになる。

できあがった画像をみると、「なるほど、游明朝で書いた鬱と、ヒラギノ角ゴシックで書いた鬱に、共通する特徴点というのがあって、対応はこうなっているのだな」ということが分かる。間違っているところもあるけれど、たしかにピンポイントで見てみると、周囲の形状は似ているかもしれないなと思う。

コピペだけでは分からんのが、cv2.BFMatcher()とは何で、その戻り値(matches)には何が格納されているのか？ということだ。

さて、ドキュメントによると、BFMatcher()というのはBrute-force matcherであると書かれている。Brute-forceというと、分かりやすい訳語は力技ということなので、まあ、多分、そういうことなんだろう。力技でどうやって、img1の特徴点と、img2の特徴点を対応させるのかはよく分からないけれど。

ところで、
bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)
のように書いたけれど、これが正しいのかどうかが実際のところよく分からない。

BFMatcher()のコンストラクターの定義は、BFMatcher (int normType=NORM_L2, bool crossCheck=false)のようになっているけれど、
AKAZEのときには、normTypeとして何を選んだら良いんだろうか。これは、AKAZEという手法がSIFTやSURFに近いのか、ORBやBRISKやBRIEFに近いのか？等で判断するのだろうと思うんだけれど、正直、そこまで理解していなくてよく分からない。

Parameters
normtype	One of NORM_L1, NORM_L2, NORM_HAMMING, NORM_HAMMING2. L1 and L2 norms are preferable choices for SIFT and SURF descriptors, NORM_HAMMING should be used with ORB, BRISK and BRIEF, NORM_HAMMING2 should be used with ORB when WTA_K==3 or 4 (see ORB::ORB constructor description).
crossCheck	If it is false, this is will be default BFMatcher behaviour when it finds the k nearest neighbors for each query descriptor. If crossCheck==true, then the knnMatch() method with k=1 will only return pairs (i,j) such that for i-th query descriptor the j-th descriptor in the matcher's collection is the nearest and vice versa, i.e. the BFMatcher will only return consistent pairs. Such technique usually produces best results with minimal number of outliers when there are enough matches. This is alternative to the ratio test, used by D. Lowe in SIFT paper.

Parameters

normtype

One of NORM_L1, NORM_L2, NORM_HAMMING, NORM_HAMMING2. L1 and L2 norms are preferable choices for SIFT and SURF descriptors, NORM_HAMMING should be used with ORB, BRISK and BRIEF, NORM_HAMMING2 should be used with ORB when WTA_K==3 or 4 (see ORB::ORB constructor description).

crossCheck

If it is false, this is will be default BFMatcher behaviour when it finds the k nearest neighbors for each query descriptor. If crossCheck==true, then the knnMatch() method with k=1 will only return pairs (i,j) such that for i-th query descriptor the j-th descriptor in the matcher's collection is the nearest and vice versa, i.e. the BFMatcher will only return consistent pairs. Such technique usually produces best results with minimal number of outliers when there are enough matches. This is alternative to the ratio test, used by D. Lowe in SIFT paper.

さて、戻り値(matches)だが、DMatch classとして定義されていて、内容は以下のとおりだ。

型	メンバ名
float	distance	Distance between descriptors. The lower, the better it is.
int	imageIdx	Index of the descriptor in train descriptors
int	queryIdx	Index of the descriptor in query descriptors
int	trainIdx	Index of the train image.

それぞれ、どういう意味かをもっと知りたくて、http://docs.opencv.org/3.2.0/d4/de0/classcv_1_1DMatch.html#a1cb9bee47b20ad96e16de28f4b9cbdf1 を見てみたのだが、特に何も書いてないのであった。

まあ、しかし意味的にはdistanceが特徴点同士の距離であろうことは想像がつくし、そういう意味では、チュートリアルにあるように、matches = sorted(matches, key = lambda x:x.distance)で、distanceの値が小さい順にsortした後で、cv2.drawMatches(img1, kp1, img2, kp2, matches[:10], None, flags=2)のようにmatches[:10]と上位10個を描画してみるというのは、類似度が高い上位10個の特徴点を抽出しているという意味で、実に分かりやすい話ではある。

続けて、チュートリアルの続きを進める。

bf = cv2.BFMatcher()
matches = bf.knnMatch(des1, des2, k=2)
good = []
for m,n in matches:
    if m.distance < 0.5*n.distance:
        good.append([m])
img4 = cv2.drawMatchesKnn(img1, kp1, img2, kp2, good, None, flags=2)

今度は、bf.knnMatch()をしている。knnとは、k-th nearest neighborのことであろうとは思うのだけれど、matches = bf.match() するのとは、アルゴリズムが違うんでしょうね、というぐらいの違いしか分からない。OpenCVのreferenceを読んでもよく分からないので、おそらくもう少し理論的な話をD. Loweの論文を読んで理解しろということなんでしょう。

This time, we will use BFMatcher.knnMatch() to get k best matches. In this example, we will take k=2 so that we can apply ratio test explained by D.Lowe in his paper.

って書いてあるし。(だったら、そのD. Loweの論文へのReferenceくらい書いておいてほしいもんだけれど、ソレを書いておかないと分からない程度の人はお断り！ってハナシなのかもしれない)

さて、戻り値のmatchesは、以下のような構造になっている。

In[12]: matches
Out[12]:
[[<DMatch 0x11cecd3b0>, <DMatch 0x11cecd4d0>],
 [<DMatch 0x11cecd610>, <DMatch 0x11cecd6f0>],
...
 [<DMatch 0x11cecd9b0>, <DMatch 0x11cecd9d0>]]

ドキュメントには、こう書いてある。

Matches. Each matches[i] is k or less matches for the same query descriptor.

これをfor m, n in matches:のように取り出して、m.distanceとn.distanceを比較するのだけれど、そうするとこのmとnには何が入っていて、どう比較しているのか？という話である。なぜ、if m.distance < 0.5*n.distance:という条件で抽出する必要があるのか、この辺りもD.Loweの論文を読む必要があるのだろう。

というワケで、理論的なところはさっぱり分からないまま、コピペだけで游明朝の鬱とヒラギノ角ゴシックの鬱の特徴点を抽出して、類似していると思われる点のマッチングまでできるようになりました。

まとめ

理論は分かってなくても、画像から特徴点抽出をすることは、OpenCVを使えば簡単にできる。

今回は、文字を画像化したため、画像データとしてはもともと二値化されている状態にあるため、「元画像の輝度の強弱」が特徴量にどのくらい影響するのか？というのが分かりづらいなというのが、反省点といえば反省点である。

本日のコード

https://github.com/fukuit/Python_SelfLearning/blob/master/feature_detect/feature_detection.py